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

;Ь ФигОСУДАРСТВЕННЫй НОМИТЕТ СССР ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ОПИСАН И Н АВТОРСКОМУ(56) Авторское свидВ 739562, кл. С 06 САвторское свидетпо заявке У 38536 Окл. С 06 С 7(122, 1(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ(57) Изобретение относится к вычислительной технике и может быть использовано для решения задачи дискретного программирования, известной как "задача о ранце". Даннаязадача возникает в тех практическихситуациях, когда из общей совокупности номенклатур необходимо выбратоптимальный их набор. Целью изобрет129877 ння является повышение точности решения задачи дискретного программирования. Устройство содержит блок 1 задания коэффициентов целевых функций, блок 2 коммутации, блок 3 выбора максимума, блок 4 запоминания оптимальных последовательностей,4блок 5 управления, блок 6 индикациии группу элементов ИЛИ 7. Новым является введение группы элементовИЛИ 7, блока 4 запоминания оптимальных последовательностей, а также конструктивное выполнение блока 5 управления. 2 ил.Изобретение относится к вычислительной технике и может быть использовано для решения задачи дискретного программирования, известной как "задача. о ранце", возникающей в тех практических ситуациях, когда из общей совокупности номенклатур необходимо выбрать оптимальный.Цель изобретения - повышение точности решения задачи дискретного программирования.На фиг.1 приведена функциональная схема устройства для решения задачи дискретного программирования; на фйг,2 - функциональная схема элемента коммутации с противофазным управлением.Устройство содержит блок 1 задания коэффициентов целевых функций, блок 2 коммутации, блок 3 выбора максимума, блок 4 запоминания оптимальных последовательностей, блок 5 управления, блок 6 индикации и группу элементов ИЛИ 7;блок задания коэффициентов целевых функций предназначен для формирования и подачи на входы блока 2 коммутации электрических сигналов, пропорциональных полезности номенклатур исходной совокупности. Блок 1 содержит потенциометры 8.Количество потенциометров равно Я =и где ш - количество номен =1клатур, и, - количество номенклатур в -й группе.Блок 2 коммутации предназначен для соединения в соответствии с альтернативными последовательностями, получаемыми на основе оптимальных последовательностей, запоминаемых на каждом шаге решения в блоке 4,соответствующих выходов блока 1 задания коэффициентов целевых функций с входами блока 3 выбора максимума и подачи на входы блока 4 сигналов, соответствующих оптимальной для данного5 шага решения последовательности номенклатур.Блок 2 содержит группы ключей 9Юи 10, транспаранты 11.Блок 3 выбора максимума предназначен для определения оптимальной последовательности из альтернативныхпоследовательностей данного шага решения по максимуму соответствующегоим значения целевой функции и подачисигнала с выхода блока, соответствующего этой последовательности, на входблока 5 управления, Блок 3 содержит20операционные усилители 12 с М входами, выход которых подключен к входуцепью обратной связи из последовательно соединенных резисторов 13 идиода 14, узлы соединения которых у25 всех усилителей объединены и подключены к индикатору 15, Кроме того,блок 3 содержит ключи 16.Блок 4 оптимальных последовательностей предназначен для запоминанияоптимальной последовательности, получаемой на данном шаге решения, и оптимальных последовательностей, получаемых на предшествующих шагах решения, а также "динамического скольжения" этих последовательностей в про цессе решения,Блок 4 содержит и каналов 17 обработки информации, каждый из которых 40 содержит ш узлов 18 памяти, первыйэлемент 19 задержки, второй элемент 20 задержки, каждый узел 18 памяти выполнен в виде элемента И 21 и триггера 22, 12987Количество узлов 18 памяти равно количеству номенклатур исходной совокупности.Блок 5 управления преДназначен для управления коммутацией элементов блоков устройства в соответствии с алгоритмом скользящей динамической последовательности решения задачи дискретного программирования.Блок 5 содержит двухпозиционный переключатель 23 режима работы, переключатель 24, группу триггеров 25, элемент ИЛИ 26, первый и второй элементы И 27 и 28, триггер 29 пуска, генератор 30 импульсов, группу разделительных диодов 31, элемент НЕ 32, счетчик 33 импульсов, элемент 34 коммутации с противофазньм управлением, источник 35 опорного напряжения.Элемент 34 коммутации предназначен для обеспечения участия в работе устройства на К-м шаге решения К групп узлов 18 памяти при Кш иш каналов обработки информации.Элемент 34 коммутации содержит триггеры 36, ключи 37, элементы 38 задержки, элементы И 39.Принцип работы устройства основан 3 О на использовании метода скользящей динамической последовательности.Метод позволяет получить точное решение задачи. Для использования этого метода номенклатуры должны быть упорядочены в исходную совокупность в порядке возрастания коэффициентов ограничений в ш группу, а внутри каждой группы - в порядке убывания коэФфициентов целевой функции, 4 О причем а = , где д = 1, ш номенклатур; 1 1, и, - НОмера номенкла тур в д-й группе; и. - количество номенклатур в д-й группе. 45При отсутствии номенклатур с коэфФициентом ограничения, равным К, К-я группа представляется в исходной совокупности группой, содержащей один элемент с а = К и С , = О. 50В этом случае задача может быть сведена к задачеС;. х - -ф шаху=1 3 л 155прикм Ьл 1 74 4где х, = 1, если 1-я номенклатура -й группы исходной совокупности включена в оптимальный набор и х =1 = О в противном случае;С; и а., - коэффициенты целевой Функции и ограничения соответст,венно, характеризующие 1-ю номенклатуру 1-й группы исходной совокупности.Работа устройства основана на выборе оптимальной для ограничения, соответствующего данному шагу решения, последовательность из альтернативных, определяемых по оптимальным последовательностям предшествующих шагов решения.Устройство для решения задач дискретного программирования работает следующим образом.сПеред решением подвижные контакты потенциометров 8 устанавливаются в положения, соответствующие выходным напряжениям, пропорциональным полезности номенклатур исходной совокупности. Счетчик 33 блока 5 устанавливается в состояние (Ч - Ь), где Ч емкость счетчика.Двухпозиционный переключатель 23 переводится в положение "И", При этом триггеры 19 блока 4, находящиеся не в нулевом состоянии, переходят в него.Двухпозиционный переключатель 23 возвращается в исходное положение "Р", цепь возврата триггеров блоков 5 и 4 - в нулевое состояние, при этом разрывается и готовится цепь поступ-. ления сигналов на вход элемента И 28.Решение происходит автоматически и начинается кратковременным включением переключателя 24, Процесс решения может быть разбит на 3 шагов Ж = Ь), каждый из которых состоит из двух этапов. На первом этапе каждого шага решения триггер 29 переходит в единичное состояние.Сигнал с его выхода поступает на полюс а элемента 34 коммутации. С полюса а элемента 34, в зависимости от шага решения, сигнал поступаетна соответствующие выходы с 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, 5 Ю 15 20 С выхода элемента ИЛИ 26 сигналпоступает на один из входов элемента И 27, на другом входе которого есть сигнал с выхода элемента НЕ 32,С выхода элемента И 27 сигнал поступает на нулевой вход триггера 29 и генератора 30. Триггер 29 переФходит в нулевое состояние, при этом снимается сигнал"с входного полюса а элемента 34 коммутации и выходов д д этого элемента. Обеспечиваются управляющие цепи всех групп ключей 9 блока 2, кроме группы, соотВетствующей оптимальной для данного шага решения последовательности номенклатур, При этом снимаются сигналы с входов всех операционных усилителей 12 блока 3, кроме усилителя, соответствующего оптимальной последовательности. Генератор 30 вырабатывает один импуцьс, который поступает на входной полюс с элемента34, при этом готовится подключение 25 следующего Выхода ЙЙ элемента 34, если еще не произведено шшагов решения.Так, на втором этапе первого шагарешения, после поступления сигналана вход с элемента 34, он поступаетна вход элемента И 39, на другом входе которого есть сигнал с нулевоговыхода триггера 36.С выхода элемента И 39 сигнал,поступает на единичный вход триггера 3536, который переходит в единичноесостояние, и сигнал с его выхода поступает на управляющую цепь ключа37исполнительные цепи которого 4 О подключают выход Й к выходу а элемента 34Кроме того, сигнал с прямого выхода триггера 36поступает через канала 17, возвращая ихна одиниз выходов элемента И 39, готовя 45 подключенные на втором этапе второгошага решения выхода Йз к входу а.Импульс от генератора 30 поступает на счетный вхо счетчика 33, который при этом изменяет на единицу своесодержимое, а через диод 31 - нап+ 1выход блока 5, с которого импульс поступает на соответствующий вход блока 4,С входа блока 4 импульс поступаетна входы установки в ноль триггеров22 первого канала 17,возвращая ихВ исходное нулевое состояние, а через элемент 19, задержки - на входыэлементов И 21 На других Входах эле7 12 ментов И 21,соответствующих оптимальной последовательностидля данного шага решения, есть сигнал, поступающий с выходов соответствующих элементов ИЛИ 7 группы.При этом срабатьвают триггеры, соответствующие оптимальной последовательности. Чалее сигнал поступает на элемент 20 задержки. С выхода блока 4 сигнал поступает на входы установки в ноль 25,25 блока 5, возвращая соответствующий из них в нулевое состояние. При этом снимается сигнал с установки в ноль триггера 29, с входа генератора 30, соответствующих выходовблока 5, и все элементы блоков 2 и 3 возвращаются в исходное состояние. С выхода элемента 20задержки сигнал последовательно поступает на объединенные входы установки нуля триггеров и через соот.ветствующий элемент задержки - на объединенные входы элементов И каналов 17 обработки информации, начиная с ш-й и кончая -й. С элемента 19задержки сигнал поступает на вход блока 4.В результате прохождения сигналапо узлам 18 памяти каналов 17 осуществляется сдвиг, "скольжение" оптимальных последовательностей, т.е. вш-й группе запоминается та последовательность, которая была в (ш)-йгруппе, в (ш)-й та, что была в(т)-й группе,и т.д., в 1-й группета, что заполнена на данном Маге внулевой группе,С выхода элемента 19 задержкиблока 4 сигнал поступает на соответствующий вход блока 5 и далее черезподвижной контакт двухпозиционногопереключателя 23 и неподвижный контакт "Р" на один из входов элемента И 28, на другом входе которогоесть сигнал с выхода элемента НЕ 29,С появлением сигнала на выходеэлемента И 28 заканчивается второйэтап данного шага решения и автоматически начинается следующий шаг решения, который происходит аналогично.На последнем шаге решения после выработки генератором 30 очередногоимпульса на выходе счетчика 33 появляется сигнал переполнения, при этомвозвращается в исходное состояниеэлемент 34 коммутации, снимается сигнал с входов элементов И 27 и 28,прекращая дальнейшую работу устрой 98774 8ства, срабатывают управляющие цепиключей 9 блока 6, соответствующие оптимапьной последовательности номенклатур для данного ограничения, значения целевой функции определяютсяпо показаниям индикатора 15 блока 3. Формула изобретения 10 Устройство для решения задач дискретного программирования, содержащееблок задания коэффициентов целевыхфункций, блок управления, блок коммутации, блок индикации и блок выбора максимума, блок управления содержит группу триггеров, элемент ИЛИ,два элемента И, триггер пуска, источник опорного напряжения, переключа,тель, элемент НЕ, группу разделитель-. го-ных диодов, выход источника опорногонапряжения через переключатель подключен к входу установки в "1" триггера пуска, блок задания коэффициентов целевых функций содержит потенциометры, одноименные вьводы которых.объединены и подключены к соответствующим шинам питания, а подвижные контакты являются соответствующими входами, группы выходов блока задания1коэффициентов целевых функций подключены соответственно к первой группеинформационных входов блока коммутации, первая группа информационных 35выходов которого подключена к группевходов. блока выбора максимума, группа управляющих входов блока коммутации подключена к группе информационныхвыходов блока управления, вторая группа информационных выходов блока коммутации подключена к группе входовблока индикации, о т л и ч а ю щ е -е с я тем, что, с целью .повышенияточности решения задачи дискретногопрограммирования, в него введены группа элементов ИЛИ и блок запоминанияоптимальных последовательностей, вблок управления дополнительно введены элемент коммутации с противофаз ным управлением, генератор импульсов,счетчик и переключатель режима работы, блок запоминания оптимальных последовательностей выполнен в видеи-каналов обрабогки информации, каж дый иэ которых содержит ш узлов памяти, каждый из каналов обработкиинформации, кроме первого, содержитдва элемента задержки, первый каналобработки информации содержит один4 1 Ок выходу первого элемента И блокауправления, выход генератора импульсов подключен кпервому электроду(щ + 1)-го разделительного диодагруппы, второй вход первого элементаИ блока управления подключен к первому выходу переключателя режима работы, второй выход которого объединен с выходом источника опорного напряжения, выход счетчика блока управления подключен к (щ + 1)-му управляющему входу группы управляющих входов блока коммутации, каждый -й выход второй группы информационных выходов блока коммутации подключен кпервому входу -го элемента ИЛИ группы , а каждый -й выход третьей группы информационных выходов блока коммутации подключен к второму входуд-го элемента ИЛИ группы, выход каждого д-го элемента ИЛИ группы подключен к второму входу элемента Иь-го узла памяти первого канала обработки информации блока запоминанияоптимальных последовательностей, второй электрод(щ ф 1)-го разделительного диода подключен к входу установки нуля триггеров всех узлов памятипервого канала обработки информацииблока запоминания оптимальных после-довательностей, прямой вход триггеракаждого -го узла памяти каждого 1 го канала обработки информации блоказапоминания оптимальных последовательностей подключен к -му входу "йподгруппы второй группы информационных входов блока коммутации, выходвторого элемента задержки и-го канала обработки информации подключен кпервым входам элементов И первогоканала обработки информации и к вхо 1дам установки в "О" всех триггеровгруппы блока управления, выход первого элемента задержки второго каналаобработки информации блока запоминания оптимальных последовательностей подключен к информационному входу второго переключателя блока упразления,каждый -й выход группы выхо-,дов блока выбора максимума подключен к входу установки в "1"с -го триггера группы , блока Управления. 9129877 элемент задержки, узел памяти каждого . канала обработки информации содержит, элемент И и триггер, выход элемента И подключен к входу установки в "1" триггера, в каждом канале обработки информации входы установки в "д" триггеров всех узлов памяти объединены и подключены к входу первого элемента задержки, выход которого подключен к первым входам элементов 10 И всех узлов памяти, входы установки в "О" триггеров всех узлов памяти каждого из каналов обработки информации, кроме первого, блока запоминания оптимальных последовательностей подключены к входу второго элемента задержки, прямой выход триггера каждого х-го узла памяти Ы1,2,в) каждого 1-го канала обработки информации подключен к , 20 второму входу элемента И -го узла памяти (1 + 1)-го канала обработки информации, при этом прямой выход каждого 1-го триггера группы подключен к -му входу элемента ИЛИ блока управления ( = 1,2а) ик одному электроду д-го разделительного диода групп, другой электрод которого объединен с 1-ым выходом группы выходов элемента коммутации с противофазным управлением и является ,соответствующим выходом групп инфор,мационных выходов блока управления, выход элемента ИЛИ блока управления подключен к первому входу первого эле мента И блока управления, второй вход которого объединен с первым входом второго элемента И блока управления и подключен к выходу элемента НЕ, вход элемента НЕ подключен к выходу 40 счетчика, выход первого элемента И блока управления подключен к входу установки: нуля триггера пуска, пря/мой выход которого подключен к информационному входу элемента коммутации 45 с противофазным управлением, первый управляющий вход которого подключен к входу счетчика, второй управляющий вход коммутационного элемента с противофазным управлением объеди нен со счетным входом счетчика и подключен к выходу генератора импульсов, вход запуска которого подключен1298774Фиг.2Составитель Т.СапуноваРедактор Е.Папп Техред Л,Сердюкова Корректор Л,Патай Заказ 891/52 Тираж 673 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Я, Раушская наб., д.4/5 Производственно"полиграфическое предприятие, г.ужгород, ул,Проектная,4