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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для решения задачи дискретного программирования, известной как задача о ранце. Данная задача возникает в тех практических ситуациях, когда из общей совокупности номенклатур необходимо выбрать оптимальный их набор. Цельюизобретеел ND СО оо - 4; uz.f

СОНЭЗ СОВЕТСКИХ

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

РЕСПУ БЛИН

8К 1298774

А1 (51) 4 С 06 С 7/122

ОПИСАНИЕ ИЗОБРЕТЕНИЯ !и (ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н ASTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3864990/24-24

{22) 07.03.85 (46) 23,03.87. Бюл. У 11 (72) О.Г.Алексеев, В.Ю.Мержанов, В.В.Спичкин и Н.И.Ячкула (53) 681.333(088.8) (56) Авторское свидетельство СССР

В 739562, кл. С 06 С 7/48, 1980 °

Авторское свидетельство ГССР .по заявке Ф 3853670/24-24, кл. С 06 С 7/122, 1985. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ (57) Изобретение относится к вычислительной технике и может быть ис« пользовано для решения задачи дискретного программирования, известной как "задача о ранце". Данная задача возникает в тех практических ситуациях, когда из общей совокупности номенклатур необходимо выбратьоптимальный их набор. Целью изобрете-.

129877 ння является повышение точности решения задачи дискретного программирования. Устройство содержит блок

1 задания коэффициентов целевых фунJ кций, блок 2 коммутации, блок 3 выбора максимума, блок 4 запоминания оптимальных последовательностей, 4 блок 5 управления, блок 6 индикации и группу элементов ИЛИ 7. Новым является введение группы элементов

ИЛИ 7, блока 4 запоминания оптимальных последовательностей, а также конструктивное выполнение блока 5 управления. 2 ил.

Изобретение относится к вычислительной технике и может быть использовано для решения задачи дискретного программирования, известной как

"задача. о ранце", возникающей в тех практических ситуациях, когда из общей совокупности номенклатур необходимо выбрать оптимальный.

Цель изобретения — повышение точности решения задачи дискретного программирования.

На @иг.1 приведена функциональная схема устройства для решения задачи дискретного программирования; на фйг.2 — функциональная схема элемента коммутации с противофазным управлением.

Устройство содержит блок 1 задания коэффициентов целевых функций, блок 2 коммутации, блок 3 выбора максимума, блок 4 запоминания опти5чальных последовательностей, блок 5 управления, блок 6 индикации и группу элементов ИЛИ 7;блок задания коэффициентов целевых функций предназначен для формирования и подачи на входы блока 2 коммутации электрических сигналов, пропорциональных полезности номенклатур исходной совокупности.

Блок 1 содержит потенциометры 8.

Количество потенциометров равно

tn

N = n., где m — - количество номен1

i=1 клатур, n. — количество номенклатур в i-й группе.

Блок 2 коммутации предназначен для соединения в соответствии с альтернативными последовательностями, получаемыми на основе оптимальных последовательностей, запоминаемых на каждом шаге решения в блоке 4,соответствующих выходов блока 1 задания коэффициентов целевых функций с входами блока 3 выбора максимума и подачи на входы блока 4 сигналов, соответствующих оптимальной для данного

5 шага решения последовательности номенклатур.

Блок 2 содержит группы ключей 9

50 и 10, транспаранты 11.

Блок 3 выбора максимума предназначен для определения оптимальной последовательности из альтернативных последовательностей данного шага решения по максимуму соответствующего им значения целевой функции и подачи сигнала с выхода блока, соответствующего этой последовательности, на вход блока 5 управления, Блок 3 содержит

20 операционные усилители 12 с N входами, выход которых подключен к входу цепью обратной связи из последовательно соединенных резисторов 13 и диода 14, узлы соединения которых у

2 всех усилителей объединены и подключены к индикатору 15. Кроме того, блок 3 содержит ключи 16.

Блок 4 оптимальных последовательностей предназначен для запоминания оптимальной последовательности, получаемой на данном шаге решения, и оптимальных последовательностей, получаемых на предшествующих шагах решения, а также "динамического скольжения" этих последовательностей в про цессе решения, Блок 4 содержит и каналов 17 обработки информации, каждый из которых

40 содержит m узлов 18 памяти, первый элемент 19 задержки, второй элемент

20 задержки, каждый узел 18 памяти выполнен s виде элемента И 21 и триггера 22.

12987

Количество узлов 18 памяти равно

1количеству номенклатур исходной совокупности.

Блок 5 управления преДназначен для управления коммутацией элементов блоков устройства в соответствии с алгоритмом скользящей динамической последовательности решения задачи дискретного программирования.

Блок 5 содержит двухпозиционный переключатель 23 режима работы, переключатель 24, группу триггеров 25, элемент ИЛИ 26, первый и второй элементы И 27 и 28, триггер 29 пуска, генератор 30 импульсов, группу разделительных диодов 31, элемент НЕ

32, счетчик 33 импульсов, элемент 34 коммутации с противофазным управлени-20 ем, источник 35 опорного напряжения.

Элемент 34 коммутации предназначен для обеспечения участия в работе устройства на К-м шаге решения К групп узлов 18 памяти при К < m u

° m каналов обработки информации.

Элемент 34 коммутации содержит триггеры 36, ключи 37, элементы 38 задержки, элементы И 39.

Принцип работы устройства основан 3О на использовании метода скользящей динамической последовательности.

Метод позволяет получить точное решение задачи. Для использования этого метода номенклатуры должны быть упорядочены в исходную совокупность в порядке возрастания коэффициентов ограничений в ш группу, а внутри каждой группы — в порядке убывания коэффициентов целевой функции, 4О причем а.. = i, где i = 1, m номенклатур1 j = 1, л, - номера номенкла. тур в i A группе; n. — количество номенклатур в i-й группе. 45

При отсутствии номенклатур с коэффициентом ограничения, равным К, К-я группа представляется в исходной совокупности группой, содержащей один элемент с а = К и С „, = О.

К1 50

В этом случае задача может быть сведена к задаче

Рп 11

С;„. х.. — max

1=1 1 -л1

55 при

1=1 4л1

74 4 где х, = 1, если j-я номенклатура

i-й группы исходной совокупности включена в оптимальный набор и х.. =

1J

= О в противном случае;

С;„. и а.,„— коэффициенты целевой функции и ограничения соответст,венно, характеризующие j-ю номенклатуру i-й группы исходной совокупности.

Работа устройства основана на выборе оптимальной для ограничения, соответствующего данному шагу решения, последовательность из альтернативных, определяемых по оптимальным последовательностям предшествующих шагов решения.

Устройство для решения задач дискретного программирования работает следующим образом.

Перед решением подвижные контакты потенциометров 8 устанавливаются в положения, соответствующие выходным напряжениям, пропорциональным полезности номенклатур исходной совокчпности. Счетчик 33 блока 5 устанавливается в состояние (Ч вЂ” Ь), где Ч емкость счетчика.

Двухпозиционный переключатель 23 переводится в положение "И". При этом триггеры 19 блока 4, находящиеся не в нулевом состоянии, переходят в него.

Двухпозиционный переключатель 23 возвращается в исходное положение "P", цепь возврата триггеров блоков 5 и

4 — в нулевое состояние, при этом разрывается и готовится цепь поступ-. ления сигналов на вход элемента И 28.

Решение происходит автоматически и начинается кратковременным включением переключателя 24. Процесс решения может быть разбит на R шагов (R = Ь), каждый из которых состоит из двух этапов. На первом этапе каждого шага решения триггер 29 переходит в единичное состояние.

Сигнал с его выхода поступает на полюс а элемента 34 коммутации. С полюса а элемента 34, в зависимости от шага решения, сигнал поступает на соответствующие выходы d,,... d так как на первом шаге сигнал поступит только на полюс d . С выходных

1 полюсов элемента коммутации сигналы поступают на управляющие входы групп ключей 9 и 10 блока 2.

Полные выходы триггеров 22 соответствующих каналов 17 узлов 18 па1298774 мяти блока 4 подключаются к второй группе информационных входов блока 2.

При этом срабатывают соответствующие ключи 10 блока 2.

Подключение исполнительных цепей ключей 9 таково, что при этом срабатывает и ключ, соответствующий следующей за последней, включенной в оптимальную последовательность, номенклатурой соответствующей группы номенклатур исходной совокупности.

Так, на первом шаге решения все триг, геры 22,...,22 находятся в ну-. левом состоянии, но подключение выхода Й к исполнительной цепи ключа

9 обеспечивает срабатывание ключа 10

Таким образом, сработавшие ключи

10 группы подключают исполнительными цепями выходы блока 1 в соответствии с альтернативными последовательностями, получаемыми добавлением следующей номенклатуры соответствующей группы исходной совокупности к оптимальной последовательности, получаемой на предшествующем шаге решения, к входам соответствующих операционных усилителей 12 блока 3, Происходит выбор максимального значения целевой функции и срабатывают ключи 16, соответствующие лучшей из альтернативных последовательностей данного шага решения. На этом первый этап шага решения заканчивается.

Таким образом, на. первом этапе сформированы на основе оптимальных последовательностей, заполненных триггерами блока 4, альтернативные последовательности и выбрана лучшая из них по максимуму целевой функции для ограничения, соответствующего данному шагу решения.

Второй этап каждого шага решения начинается с поступления сигнала от источника опорного напряжения через исполнительные цепи соответствующего ключа 16, выходы блока 3 подключаются к входу установки в "1" соответствующего триггера 25 блока

5. Триггер переходит в единичное состояние и сигнал с его прямого выхода поступает на соответствующий выход блока 5 через один из разделительных диодов 31, а непосредственно — на один из входов элемента

ИЛИ 26.

С выхода элемента ИЛИ 26 сигнал поступает на один из входов элемента

И 27, на другом входе которого есть сигнал с выхода элемента НЕ 32.

С выхода элемента И 27 сигнал поступает на нулевой вход триггера

29 и генератора 30. Триггер 29 пере1 Ф ходит в нулевое состояние, при этом снимается сигнал"с входного полюса а элемента 34 коммутации и выходов

d „,,......,,д этого элемента. Обеспечиваются управляющие цепи всех групп ключей 9 блока 2, кроме группы, соответствующей оптимальной для данного шага решения последовательности номенклатур. При этом снимаются сигналы с входов всех операционных усилителей 12 блока 3, кроме усилителя, соответствующего оптимальной последовательности. Генератор 30 вырабатывает один импульс, который поступает на входной полюс с элемента

34, при этом готовится подключение следующего выхода Й,...,d мента 34, если еще не произведено m шагов решения.

Так, на втором этапе первого шага решения, после поступления сигнала на вход с элемента 34, он поступает на вход элемента И 39, на другом входе которого есть сигнал с нулевого выхода триггера 36 .

С выхода элемента И 39 сигнал.поступает на единичный вход триггера

36, который переходит в единичное состояние, и сигнал с его выхода поступает на управляющую цепь ключа

37,, исполнительные цепи которого

4 .мента 34 ° Кроме того, сигнал с прямого выхода триггера 36 q поступает через канала 17, возвращая их-на один из выходов элемента И 39„, готовя

45 подключенные на втором этапе втоРого шага решения выхода d к входу а.

Импульс от генератора 30 поступает на счетный вход счетчика 33, который при этом изменяет на единицу свое содержимое, а через диод 31 — на

tn+ i выход блока 5, с которого импульс поступает на соответствующий вход блока 4.

С входа блока 4 импульс поступает на входы установки в ноль триггеров

22 первого канала 17,возвращая их в исходное нулевое состояние, а через элемент 19, задержки — на входы элементов И 21„ На других входах эле7 12 ментов И 21,соответствующих оптимальной последовательностидля данного шага решения, есть сигнал, поступающий с выходов соответствующих элементов

ИЛИ 7 группы.

При этом срабатывают триггеры, соответствующие оптимальной последовательности. г алее сигнал поступает на элемент 20 задержки. С выхода блока 4 сигнал поступает на входы установки в ноль 25,,...,25 блока 5, возвращая соответствующий из них в нулевое состояние. При этом снимается сигнал с установки в ноль триггера

29, с входа генератора 30, соответствующих выходов блока 5, и все элементы блоков 2 и 3 возвращаются в исходное состояние. С выхода элемента

20 задержки сигнал последовательно поступает на объединенные входы установки нуля триггеров и через соот.ветствующий элемент задержки — на объединенные входы элементов И каналов 17 обработки информации, начиная .с m-й и кончая I-й.

С элемента 19 задержки сигнал поступает на вход блока 4.

В результате прохождения сигнала по узлам 18 памяти каналов 17 осуществляется сдвиг. "скольжение" оптимальных последовательностей, т.е. в

m-й группе запоминается та последовательность, которая была в (m-1)-й группе, в (1п-1)-й та, что была в (m-2)-й группе,и т.д., в .1-й группе та, что заполнена на данном Маге в нулевой группе.

С выхода элемента 19 задержки блока 4 сигнал поступает на соответствующий вход блока 5 и далее через подвижной контакт двухпозиционного переключателя 23 и неподвижный контакт "P" на один из входов элемента И 28, на другом входе которого есть сигнал с выхода элемента НЕ 29.

С появлением сигнала на выходе элемента И 28 заканчивается второй этап данного шага решения и автоматически начинается следующий шаг решения, который происходит аналогично.

На последнем шаге решения после выработки генератором 30 очередного импульса на выходе счетчика 33 появляется сигнал переполнения, при этом возвращается в исходное состояние элемент 34 коммутации, снимается сигнал с входов элементов И 27 и 28, прекращая дальнейшую работу устрой98774 8 ства, срабатывают управляющие цепи ключей 9 блока 6, соответствующие о11тимапьной последовательности номенклатур для данного ограничения, значения целевой функции определяются по показаниям индикатора 15 блока 3.

Формула изобретения

10 Устройство для решения задач дискретного программирования, содержащее блок задания коэффициентов целевых функций, блок управления, блок коммутации, блок индикации и блок выбора максимума, блок управления содержит группу триггеров, элемент ИЛИ, два элемента И, триггер пуска, источник опорного напряжения, переключа,тель, элемент НЕ, группу разделитель-.

20-. ных диодов, выход источника опорного напряжения через переключатель подключен к входу установки в "1" триггера пуска, блок задания коэффициен25 TOB целевых функции содержит потен циометры, одноименные выводы которых .объединены и подключены к соответствующим шинам питания, а подвижные контакты являются соответствующими входами, группы выходов блока задания

1 коэффициентов целевых функций подключены соответственно к первой группе информационных входов блока коммутации, первая группа информационных

35 выходов которого подключена к группе входов блока выбора максимума, группа управляющих входов блока коммутации подключена к группе информационных выходов блока управления, вторая группа информационных выходов блока коммутации подключена к группе входов блока индикации, о т л и ч а ю щ е— е с я тем, что, с целью .повышения точности решения задачи дискретного программирования, в него введены группа элементов ИЛИ и блок запоминания оптимальных последовательностей, в блок управления дополнительно введены элемент коммутации с противофаз50 ным управлением, генератор импульсов, счетчик и переключатель режима работы, блок запоминания оптимальных последовательностей выполнен в виде

11 каналов обрабогки информации, каждый иэ которых содержит m узлов памяти, каждый из каналов обработки информации, кроме первого, содержит два элемента задержки, первый канал обработки информации содержит один

4 1О к выходу первого элемента И блока управления, выход генератора импульсов подключен к первому электроду (m + i)-го разделительного диода группы, второй вход первого элемента

И блока управления подключен к первому выходу переключателя режима работы, второй выход которого объединен с выходом источника опорного напряжения, выход счетчика блока управления подключен к (m + 1}-му управляющему входу группы управляющих входов блока коммутации, каждый i-й выход второй группы информационных выходов блока коммутации подключен к первому входу i-го элемента ИЛИ группы, а каждый i-й выход третьей группы информационных выходов блока коммутации подключен к второму входу

i-го элемента ИЛИ группы, выход каждого i-го элемента ИЛИ группы подключен к второму входу элемента И

i-ro узла памяти первого канала обработки информации блока запоминания оптимальных последовательностей, второй электрод (m + 1)-го разделительного диода подключен к входу установки нуля триггеров всех узлов памяти первого канала обработки информации блока запоминания оптимальных после- довательностей, прямой вход триггера каждого i-го узла памяти каждого jro канала обработки информации блока запоминания оптимальных последовательностей подключен к i-му входу j""й подгруппы второй группы информационных входов блока коммутации, выход второго элемента задержки n-ro канала обработки информации подключен к первым входам элементов И первого канала обработки информации и к вхо1 дам установки в "0" всех триггеров группы блока управления, выход первого элемента задержки второго канала обработки информации блока запоминания оптимальных последовательностей подключен к информационному входу второго переключателя блока упI разления,каждый i-й выход группы выхо-, дов блока выбора максимума подключен к входу установки в 1" с -го триггера группы, блока управления.

9

129877 элемент задержки, узел памяти каждого . канала обработки информации содержит, элемент И и триггер, выход элемента

И подключен к входу установки в "1" триггера, в каждом канале обработки информации входы установки в "д" триггеров всех узлов памяти объединены и подключены к входу первого элемента задержки, выход которого подключен к первым входам элементов 10

И всех узлов памяти, входы установки в "0" триггеров всех узлов памяти каждого из каналов обработки информации, кроме первого, блока запоминания оптимальных последовательнос- 15 тей подключены к входу второго элемента задержки, прямой выход триггера каждого i-го узла памяти (i

1,2... °,m) каждого j-го канала обработки информации подключен к второму входу элемента И i-ro узла памяти (j + 1)-ro канала обработки информации, при этом прямой выход каждого i-ro триггера группы подключен к i-му входу элемента ИЛИ блока управления (i = 1,2,...,m) и к одному электроду i-ro разделительного диода групп, другой электрод которого объединен с i-ым выходом группы выходов элемента коммутации с противофазным управлением и является ,соответствующим выходом групп инфор,мационных выходов блока управления, выход элемента ИЛИ блока управления подключен к первому входу первого эле- 35 мента И блока управления, второй вход которого объединен с первым входом второго элемента И блока управления и подключен к выходу элемента НЕ, вход элемента НЕ подключен к выходу 40 счет щка, выход первого элемента И блока управления подключен к входу установки: нуля триггера пуска, пря/ мой выход которого подключен к инфор-. мационному входу элемента коммутации 4> с противофазным управлением, первый управляющий вход которого подключен к входу счетчика, второй управляющий вход коммутационного элемента с противогазным управлением объеди- 50 нен со счетным входом счетчика и подключен к выходу генератора импульсов, вход запуска которого подключен

1298774

Фиг. 2

Составитель Т.Сапунова

Редактор Е.Папп Техред Д.Сердокова Корректор Л.Патай

Заказ 891/52 Тираж 673 Подписное

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

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

Производственно-полиграфическое предприятие, r.Óæãîðoä, ул,Проектная,4