Устройство для решения задач дискретного программирования Советский патент 1987 года по МПК G06G7/122 

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

1

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

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

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

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

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

гп

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

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

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

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

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

0

5

0

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

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

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

Блок-4 оптимальных последовательностей предназначен для запоминания

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

0

цессе решения.

Блок 4 содержит п каналов 17 обработки информации, каждый из которых содержит m узлов 18 памяти, первый элемент 19 задержки, второй элемент 20 задержки, каждый узел 18 памяти выполнен в виде элемента И 21 и триггера 22,

Количество узлов 18 памяти равно количеству номенклатур исходной совокупности.

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

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

ем, источник 35 опорного напряжения.

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

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

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

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

причем а.

клатур; j 1, п - номера номенклатур в i-й группе; п - количество номенклатур в i-й группе;45

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

а i, К и 1

KI

0.

случае задача может быть задаче

X. .

tj

max

при

i:1

) a .. X .. b

iTT J -

есяи j-я номенклатура исходной совокупности оптимальньй набор и X..

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

С,- и ij коэффициенты целе-JQ

j 0 с

5

Q

0

5

5

0

5

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

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

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

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

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

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

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

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

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

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

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

ч.- - . 1

левом состоянии, но подключение выхода d к исполнительной цепи ключа Ч- обеспечивает срабатывание клю- ча 10.

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

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

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

Второй этап каждого шага решения начинается с поступления сигнала от источника опорного напряжения через исполнительные цепи соответству- кицего ключа 16, выходы блока 3 подключаются к входу установки в 1 соответствующего триггера 25 блока 5. Триггер переходит в единичное состояние и сигнал с его прямого выхода поступает на соответствующий выход блока 5 через один из разделительных диодов 31, а непосредственно - на один из входов элемента ШТИ 26.

Ю

t5

20

25

30

35

40

45

50

55

С выхода элемента Ш1И 26 сигнал поступает на один из входов элемента И 27f на другом входе которого есть сигнал с выхода элемента НЕ 32.

С выхода элемента И 27 сиг нал поступает на нулевой вход триггера 29 и генератора 30. Триггер 29 переходит в нулевое состояние, при этом снимается сигнал с входного полюса а элемента 34 коммутации и выходов d ,,... ,dj этого элемента. Обеспечиваются управляющие цепи всех групп ключей 9 блока 2, кроме группы, соответствующей оптимальной для данного шага решения последовательности номенклатур. При этом снимаются сигналы с входов всех операционных усилителей 12 блока 3, кроме усилителя, соответствующего оптимальной последовательности. Генератор 30 вырабатывает один импульс, который поступает на входной полюс с элемента 34, при этом готовится подключение следующего выхода d ,...,d элемента 34, если еще не произведено m шагов решения.

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

С выхода элемента И 39 сигнал.поступает на единичньй вход триггера 36, которьй переходит в единичное состояние, и сигнал с его выхода поступает на управляющую цепь ключа 37,,j, исполнительные цепи которого подключают выход d к выходу а элемента 34. Кроме того, сигнал с прямого выхода триггера 36 i2 поступает через канала 17, возвращая их-на один из выходов элемента И 39,, готовя подключенные на втором этапе второго шага решения выхода d к входу а.

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

, tn-(-l

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

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

При этом срабатывают триггеры, соответствующие оптимальной последовательности, Далее сигнал поступает на элемент 20 задержки. С выхода блока 4 сигнал поступает на входы установки в ноль 25|,.,,,25 блока 5, возвращая соответствующий из них в нулевое состояние. При этом снимаетс сигнал с установки в ноль триггера 29, с входа генератора 30, соответствующих выходов блока 5, и все элементы блоков 2 и 3 возвращаются в исходное состояние. С выхода элемент 20 задержки сигнал последовательно поступает на объединенные входы установки нуля триггеров и через соот- .ветствующий элемент задержки - на объединенные входы элементов И каналов 17 обработки информации, начиная .с т-й и кончая 1-й.

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

В результате прохождения сигнала по узлам 18 памяти каналов 17 осуществляется сдвиг, скольжение оптимальных последовательностей, т.е. в т-й группе запоминается та последовательность, которая была в (т-1)-й группе, в (т-1)-й та, что была в (т-2)-й группе,и т.д., в 1-й группе та, что заполнена на данном ntare в нулевой группе.

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

С появлением сигнала на выходе элемента И 28 заканчивается второй этап данного шага решения и автоматически начинается следующий шаг решения, который происходит аналогично На последнем шаге решения после выработки генератором 30 очередного импульса на выходе счетчика 33 появляется сигнал переполнения, при этом возвращается в исходное состояние элемент 34 коммутации, снимается сигнал с входов элементов И 27 и 28, прекращая дальнейшую работу устрой0

5

0

5

0

5

0

5

0

5

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

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

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

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

коэффициентов целевых функций подключены соответственно к первой группе информационных входов блока коммутации, первая группа информационных выходов которого подключена к группе ВХОДОВ- блока выбора максимума, группа управляющих входов блока коммутации подключена к группе информационных выходов блока управления, вторая группа информационных выходов блока коммутации подключена к группе входов блока индикации, отличающееся тем, что, с целью повышения точности решения задачи дискретного программирования, в него введены группа элементов ИЛИ и блок запоминания оптимальных последовательностей, в блок управления дополнительно введены элемент коммутации с противофазным управлением, генератор импульсов, счетчик и переключатель режима работы, блок запоминания оптимальных последовательностей выполнен в виде п-каналов обработки информации, каждый из которых содержит m узлов памяти, каждый из каналов обработки информации, кроме первого, содержит два элемента задержки, первый канал обработки информации содержит один

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

5

0

5

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

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

5 обработки информации бло ка запоминания оптимальных последовательностей подключен к информационному входу второго переключателя блока управления, каладый i-й выход группы ВЫХО-, доз блока выбора максимума подключен к входу установки в i-ro триггера группы .блока управления .

0

0

Редактор Е.Папп

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

Техред Л.Сердюкова Корректор Л,Патаи

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4

Фиг. 2

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