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

 

Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования . Целью изобретения является расширение функциональных возможностей устройства за счет оптимизации решения транспортной задачи линейного программирования по критерию времени перевозок . Устройство содержит блок 1 синхронизации, накапливающий блок 2 сортировки по возрастанию элементов матрицы времен перевозок, блок 3 проварки выполнения условий баланса транспортной задачи, блок 4 формирования плана перевозок транспортной задачи, вход 5 пуска, выходы 6, 7 блока 1 синхронизации, входы 8 задания времен перевозок из пунктов отправления в пункты назначения, входы 9,10 задания объемов запасов пунктов отправления и потребностей пунктов назначения и выходы 11 объемов перевозок из пунктов отправления в пункты назначения. Перед началом работы по входам 8, 9, 10 задают необходимые для решения исходные данные . На вход 5 пуска устройства подают импульс уровня логической 1. При этом блок 1 синхронизации формирует на своих выходах 6,7 последовательность синхроимпульсов , под управлением которой на выходах 11 устройства формируется план перевозок. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 15/419

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4721353/24 (22) 15.05.89 (46) 07.10.92. Бюл. hL 37 (72) О.Г. Алексеев, В.А. Буслаев, С.А, Васильковский, В.А, Кежаев и В.А. Шалимов (56) Авторское свидетельство СССР

N -1379787, кл, G 06 G 7/122, 1988, Авторское свидетельство СССР

М 1711174, кл. G 06 F 15/20, G 06 G 7/122, 1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ОПТИМИЗАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства за счет оптимизации решения транспортной задачи линейного программирования по критерию времени перевозок. Устройство содержит блок 1

„„5U„„1767504 А1 синхронизации, накапливающий блок 2 сортировки по возрастанию элементов матрицы времен перевозок, блок 3 проварки выполнения условий баланса транспортной задачи, блок 4 формирования плана перевозок транспортной задачи, вход 5 пуска, выходы 6, 7 блока 1 синхронизации. входы 8 задания времен перевозок из пунктов отправления в пункты назначения, входы 9, 10 задания объемов запасов пунктов отправления и потребностей пунктов назначения и выходы 11 объемов перевозок из пунктов отправления в пункты назначения. Перед началом работы по входам 8, 9, 10 задают необходимые для решения исходные данные. На вход 5 пуска устройства подают импульс уровня логической "1". При этом блок 1 синхронизации формирует на своих выходах 6, 7 последовательность синхроимпульсов, под управлением которой на выходах 11 устройства формируется план перевозок, 1 ил, 1767504 (1)

Т = min maxt a.м, Хк,м >0 при ограничениях п

Xk,M = dt<, k = 1, .„, ПО;

40 м =1

f1

XI<.м = Ьм, М 1, ..., ПН, (2) 45 где Т вЂ” общее время перевозок;

ПΠ— количество пунктов отправления;

ПН вЂ” Kof!!".÷åcòaî пунктов назначения, а — запасы k-го пункта отправления;

Ь вЂ” потребности м-го пункта назначе- 50 ния транспортной сети, т. е. требуется составить такой план перевозок в транспортной сети, чтобы при выполнении условий баланса (2) суммарное время перевозок в сети было минимально. 55

Перед началом работы в блок 2 сортировки по входам задания значений элементов заносят матрицу времен перевозок (из пунктов отправления в пункты назначения) Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования, Целью изобретения является расшире- 5 ние функциональных возможностей устройства за счет оптимизации решения транспортной задачи линейного программирования по критерию времени перевозок. 10

На чертеже представлена функциональная схема устройства.

Устройство содержит блок 1 синхронизации, накапливающий блок 2 сортировки по возрастанию элементов матрицы времен 15 перевозок, блок 3 rроверки выполнения условий баланса транспортной задачи, блок

4 формирования плана перевозок транспортной задачи; вход 5 пуска устройства. первый и второй выходы 6 и 7 блока 1 20 синхронизации, входы 8 задания времен перевозок из пунктов отправления в пункты назначения, выходы 9 задания объемов запасов пунктов отправления, входы 10 задания объемов потребностей пунктов 25 назначения и выходы 11 объемов перевозок из пунктов отправления в пункты назначения.

Устройство работает следующим образом. 30

Пусть требуется определить план перевозок ! Х,м I, для которого и устанавливают в ноль выходы признаков принадлежности элементов подмножеству выбранных, по входам 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

35

45

Составитель А.Мишин

Редактор С.Кулакова Техред М.Моргентал, Корректор M.Максимишинец

Заказ 3549 Тираж Подписное

ВНИИПИ Государственного комитета-по изобретениям и открытиям при ГКНТ СССР

113035, Москва. Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 станию элементов матрицы времен перевозок, причем вхс. „пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу накапливающего блока сортировки по возрастанию элементов матрицы времен перевозки, вход задания (К, M)-го элемента матрицы которого (К = 1, ..., ПО; М

= 1, ..., ПН, где ПΠ— количество пунктов отправления, а ПН вЂ” количество пунктов назначения в транспортной сети). о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет оптимизации решения транспортной задачи линейного программирования по критерию времени перевозок, в него введены блок проверки выполнения условий баланса транспортной задачи и блок формирования плана перевозок транспортной задачи, причем выход признака принадлежности (K, М)-ro элемента подмножеству выбранных накапливающего блока сортировки по возрастанию элементов матрицы времен перевозок подключен к входам признаков разрешения перевозок из

К-ro пункта отправления в М-й пункт назнаI чения блока проверки выполнения условий баланса транспортной задачи и блока формирования плана перевозок транспортной задачи, выход объема перевозок из К-го пун5 кта отправления в М-й пункт назначения которого является одноименным выходом устройства, вход задания объема запасов

К-го пункта отправления которого подключен к одноименным входам блока формиро10 вания плана перевозок транспортной задачи и блока проверки выполнения условий баланса транспортной задачи, выход признака выполнения условий баланса которого является выходом признака окончания

15 решения устройства и подключен к входу опроса блока формирования плана перевозок транспортной задачи и к входу останова блока синхронизации, второй выход которого подключен к входу опроса проверки вы20 полнения условий баланса транспортной задачи, вход задания объема потребностей

М-го пункта назначения устройства подключен к одноименным входам блока проверки выполнения условий баланса транспортной

25 задачи и блока формирования плана перевозок транспортной задачи.