Устройство для решения задач оптимизации

(56) Авторское свидеМ 1379787, кл, б 06Авторское свидеМ 1711174, кл. 6 061988. 7Буслаев, С.А, Васильи В.А. Шалимовельство СССР7/122, 1988,льство СССР15/20, О 06 0 7/122Сь ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР АНИЕ ИЗОБ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ(57) Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства за счет оптимизации решения транспортной задачи линейного программирования по критерию времени перевозок. Устройство содержит блок 1 синхронизации, накапливающий блок 2 сортировки по возрастанию элементов матрицы времен перевозок, блок 3 проварки выполнения условий баланса транспортной задачи, блок 4 формирования плана перевозок транспортной задачи, вход 5 пуска, выходы 6, 7 блока 1 синхронизации, входы 8 задания времен перевозок из пунктов отправления в пункты назначения, входы 9, 10 задания объемов запасов пунктов отправления и потребностей пунктов назначения и выходы 11 объемов перевозок из пунктов отправления в пункты назначения, Перед началом работы по входам 8, 9, 10 задают необходимые для решения исходные данные. На вход 5 пуска устройства подают импульс уровня логической "1". При этом блок 1 синхронизации формирует на своих выходах 6, 7 последовательность синхроимпульсов, под управлением которой на выходах 11 устройства формируется план перевозок, 1 ил,при ограничениях пХ, = бь ( =1, ПО;40м=1 и Х 1 с.м = Ьм, М 1, , ПН,(2) 45 где Т - общее время перевозок;ПО - количество пунктов отправления; ПН - коичество пунктов назначения;а - запасы К-го пункта отправления;Ь - потребности м-го пункта назначе ния транспортной сети,т. е. требуется составить такой план перевозок в транспортной сети, чтобы при выполнении условий баланса (2) суммарное время перевозок в сетибыло минимально. 55Перед началом работы в блок 2 сортировки по входам задания значений элементов заносят матрицу времен перевозок (из пунктов отправления в пункты назначения) Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования,Целью изобретения является расширение функциональных возможностей устройства за счет оптимизации решения транспортной задачи линейного программирования по критерию времени перевозок, 10На чертеже представлена функциональная схема устройства.Устройство содержит блок 1 синхронизации, накапливающий блок 2 сортировки по возрастанию элементов матрицы времен 15 перевозок, блок 3 проверки выполнения условий баланса транспортной задачи, блок 4 формирования плана перевозок транспортной задачи; вход 5 пуска устройства, первый и второй выходы 6 и 7 блока 1 20 синхронизации, входы 8 задания времен перевозок из пунктов отправления в пункты назначения, выходы 9 задания объемов запасов пунктов отправления, входы 10 задания объемов потребностей пунктов 25 назначения и выходы 11 объемов перевозок из пунктов отправления в пункты назначения.Устройство работает следующим образом, 30Пусть требуется определить план перевозок Х, , для которого и устанавливают в ноль выходы признаков принадлежности элементов подмножеству выбранных, по входам 9, 10 устройства задают объемы запасов пунктов. отправления и потребностей пунктов назначения, блок 3 настраивают на проверку условий баланса транспортной задачи, заданных выражениями (2).На вход 5 пуска устройства подают импульс уровня логической "1". При этом блок 1 синхронизации формирует на своих выходах 6, 7 последовательность сигналов, предусмотренную временной диаграммой его работы. Блок 1 синхронизации формирует импульс уровня логической "1" на своем выходе 6. При этом блок 2 сортировки добавляет к сигналам, установленным на его выходах в предыдущих тактах работы, потенциал (потенциалы) уровня логической "1" на том выходе(или на тех выходах), позиция которого (которых) соответствует элементу (элементам) матрицы времен перевозок, величина которого(которых) следует по возрастанию за элементами, уже выбранными в предыдущих тактах работы (тем самым среди еще не выбранных направлений перевозок выбираются направления с минимальными затратами времени). Через время, достаточное для выполнения указанной операции, блок 1 синхронизации формирует импульс уровня логической "1" на своем выходе 7. При этом блок 3 проверяет выполнение заданных условий баланса.В том случае, если условия баланса транспортной задачи при заданных объемах запасов пунктов отправления, объемах по- требностей пунктов назначения и разрешенных направлениях перевозок выполнены, блок 3 формирует на своем выходе потенциал уровня логической "1". При этом блок 4 формирует на тех своих выходах, позиции которых соответствуют оптимальным направлениям перевозок(из числа разрешенных перевозок направлений), соответствующие им объемы (т. е. решение задачи), исходя из заданных объемов 6 запасов пунктов отправления и объемов потребностней пунктов назначения, а блок 1 синхронизации прекращает формирование синхроимпульсов (останавливается).В том случае, если условия баланса транспортной задачи не выполняются, блок 3 не формирует потенциал уровня логической "1" на своем выходе. При этом блок 1 синхронизации повторяет цикл выдачи синхроимпульсов на свои выходы 5, 6,Формула изобретения Устройство для решения задач оптимизации, содержащее блок синхронизации и накапливающий блок сортировки по возра1767504 30 35 40 45 50 Составитель А.МишинРедактор С.Кулакова Техред М.Моргентал, Корректор М.Максимишинец . Заказ 3549 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва. Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 станию элементов матрицы времен перевозок, причем вхс,пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу накапливающего блока сортировки по возрастанию элементов матрицы времен перевозки, вход задания (К, М)-го элемента матрицы которого (К = 1, ., ПО; М = 1, , ПН, где ПО - количество пунктов отправления, а ПН - количество пунктов назначения в транспортной сети), о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет оптимизации решения транспортной задачи линейного программирования по критерию времени перевозок, в него введены блок проверки выполнения условий баланса транспортной задачи и блок формирования плана перевозок транспортной задачи, причем выход признака принадлежности (К, М)-го элемента подмножеству выбранных накапливающего блока сортировки по возрастанию элементов матрицы времен перевозок подключен к входам признаков разрешения перевозок из К-го пункта отправления в М-й пункт назначения блока проверки выполнения условий баланса транспортной задачи и блока формирования плана перевозок транспортной задачи, выход объема перевозок из К-го пун кта отправления в М-й пункт назначениякоторого является одноименным выходом устройства, вход задания объема запасов К-го пункта отправления которого подключен к одноименным входам блока формиро вания плана перевозок транспортнойзадачи и блока проверки выполнения условий баланса транспортной задачи, выход признака выполнения условий баланса которого является выходом признака окончания 15 решения устройства и подключен к входуопроса блока формирования плана перевозок транспортной задачи и к входу останова блока синхронизации, второй выход которого подключен к входу опроса проверки вы полнения условий баланса транспортнойзадачи, вход задания объема потребностей М-го пункта назначения устройства подключен к одноименным входам блока проверки выполнения условий баланса транспортной 25 задачи и блока формирования плана перевозок транспортной задачи.