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

ОП ИСАЙ ИЕ ИЗОБВЕТЕ Н ИЯ Союз СоветскихСоциалистическихРеспублик(53) УДК 681.335 (088.8) ао делам иаобретеиий и открытийДата опубликования описания 15.06.80(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ(2) х - целые,Изобретение относится к вычислительной технике и может быть использовано для решения задачи дискретного программирования, заключающейся в наилучшем выборе некоторого комплекта из общего числа и номенклатур (оборудования, грузов и т. п.) чтобы суммарные затраты не превышали указанного предела Ь, а их суммарная полезность с была максимальной, т. е. где сОИ а 0-соответственно коэффициенты полезности и затрат, характеризующие 1-ю номенклатуру, -,.Известно устройство для решения дискретных задач оптимизации градиентным методом, содержащее блоки нелинейности, блоки умножения на постоянный коэффи 2циент, блоки установки затрат, блок развертки, блок измерения градиента и блок суммирования 1).Однако это устройство содержит большое количество сложных узлов (блоки нелинейности, блоки перемножения, блок измерения градиента). Кроме того, поиск решения осуществляется ручным переключением и связан с анализом показаний приборов на каждом шаге решения, что требует больших затрат времени. Наиболее близким техническим решением к изобретению является устройство, которое также содержит блоки задания коэффициентов целевой, функции и ограничений, блок вычисления целевой функции, блок вычисления ограничений и блок сравнения, который содержит операционный усилитель диоднорезистивным релейным элементом в цепи обратной связи, входы операционного усилителя подключены ко входам блока сравнения, а выход операционного усилителя соединен с управляющей обмоткой реле блока сравнения, один вход которого подключен к выходу блока вычисления ограничений, а другой его вход соединен с одним из выходов блока задания коэффициентов ограничений 12.Кроме того, это устройство содержит блок генерирования соседних точек, регистры точек и блок счетчиков. Однако устройство сложно и решает поставленную задачу методом перебора, что требует много времени. Целью данного изобретения является упрощение устройства и повышение его быстродействия. Указанная цель достигается тем, что устройство содержит блок выбора максимума, блок коммутации и индикации и блоки деления, причем блок выбора максимума содержит операционные усилители, входы которых соединены со входами блока выбора максимума, а выходы через соответствующие разделительные диоды соединены с управляющими обмотками соответствующих реле блока выбора максимума, которые через замыкающие контакты соответствующих реле первой группы блока коммутации и индикации соединены с шиной питания, а цепи обратной связи операционных усилителей содержат последовательно соединенные резистор и диод, узлы соединения которых у всех операционных усилителей объединены, блок коммутации и индикации содержит три группы реле, управляющие обмотки реле первой из которых соединены с соответствую- шими транспарантами непосредственно, а с шиной питания - через собственные замыкающие контакты и через последовательно соединенные замыкающие контакты одноименных реле второй группы и размыкающий контакт реле блока сравнения, управляющие обмотки реле второй группы через замыкающие контакты реле блока выбора максимума соединены с шиной питания, управляющие обмотки реле третьей группы через параллельно включенные собственные замыкающие контакты И замыкающие контакты соответствующих реле блока выбора максимума соединены с шиной питания, которая через последовательно соединенные размыкающие контакты третьей группы соединена с подвижными контактами переключателя, неподвижный контакт которого соединен с соответствующим транспарантом,первые входы блоков деления подключены к соответствующим выходам блока задания коэффициентов целевой функции, которые через замыкающие контакты соответствующих реле блока выбора максимума соединены со входами блока вычисления целевой функции, вторые входы блоков деления подключены к соответствующим выходам блока задания коэффициентов ограничений, которые через замыкающие контакты соответствующих реле блока выбора максимума соединены со входами блока вычисления ограничений, а выходы блоков деления через размыкающие контактысоответствующих 5 1 О 15 ло и зо 35 реле третьей группы блока коммутации и индикации соединены со входами блока выбора максимума,Блок-схема устройства для решения задач дискретного программирования приведена на чертеже.Устройство содержит блок 1 задания коэффициентов целевой функции, блок 2 задания коэффициентов ограничений, блок 3 вычисления целевой функции, блоки 41 - 4 деления, блок 5 вычисления ограничений, блок 6 выбора максимума, блок 7 сравнения и блок 8 коммутации и индикации.Блок 6 выбора, максимума содержит операционные усилители 9- 9, реле 10- 10 л и разделительные диоды 11 - 11 л,Блок 7 сравнения содержит операционный усилитель 12 с диодно-резистивным релейным элементом в цепи обратной связи и реле 13.Блок 8 коммутации и индикации содержит реле 141 в 1, реле 15 в 1, реле 161 - 16, транспаранты 17 ви 18 и переключатель 19, Реле 10 в 1, 13, 14 в 1, 15- 15 п, 16- 16 и, имеют размыкающие контакты 10 - 10, 13, 14- 14 и, 15 - 15 16- 16 и.Блок 3 вычисления целевой функции содержит сумматор 20 и индикатор 21.Блок 5 вычисления ограничений содержит сумматор 22 и индикатор 23.Устройство работает следующим образом.Блок 1 предназначен для задания напряжений, пропорциональных коэффициентам полезности С, с помощью потенциометров 1 - 1. Блок 2 предназначен для установки напряжений, пропорциональных коэффициентам затрат а и ограничению Ь, с помощью потенциометров 2 - 2 и 2+ соответственно,Устройство решает поставленную задачу градиентным методом. Решение осуществляется за п шагов поиска, на каждом из которых автоматически определяется тахЯ.о Соответствующее значение х путем коммутации входных цепей блоков 3, 5 и цепей транспарантов 17 блока 8 полагается равным единице, если при этом выполняется условие (2), в противном случае - х -- О. На следующем шаге процедура повторяется для оставшихся номенклатур и т. д. Об окончании решения сигнализирует транспарант 18 блока 8. Перед решением выбирается число п, соответствующее количеству номенклатур и определяющее число задействованных потенциометров блоков 1, 2, число блоков 4, усилителей 9 блока 6, обмоток реле 14 - 16 и положение переключателя 19 в блоке 8. Щетки потенциометров 11 - 1, 2 - 2 и 2+ устанавливаются в положения, которые соответствуют выходным напряжениям, пропорциональным , а и Ь.Выполнение первого шага решения начинается с подачи питания на устройство, При этом напряжения с выходов блока 1 и первых выходов блока 2 поступают на входы блоков 4 - 4 п, с выходов которых напряжения, пропорциональные величинам в 4 в , через размыкающие контакты 15 - 15 реле 15 - 15 блока 8 подаются на входы блока 6.Выходное напряжение усилителя 9 блока 6, на который подано максимальное из напряжений с выходов блоков.4, - 4 п, обусловит протекание тока по обмотке реле 10, подключенного к выходу этого усилителя, срабатывание реле и запирание диодов цепей обратной связи остальных усилителей 9, т,е.отсутствие тока в выходных цепях последних.Предположим для простоты описания,.что на первом шаге решения4 - = ф -3 йа аСледовательно,в блоке 6 срабатывает реле 10 и своими замыкающими контактами подключает первые выходы блоков 1 и 2 ко входам блоков 3 и 5 соответственно, а также готовит цепь питания реле 14 блока 8, При этом напряжение, пропорциональное а, с выхода блока 5 подается на первый вход блока сравнения 7. Если оно не превышает опорного, снимаемого с 2 блока 2, то состояние блока 7 не изменится (реле 13 не срабатывает). В блоке 8 срабатывает реле 14 и своими замыкающими контактами готовит цепи питания реле 15 и 16, Реле 16 ксрабатывает, своими замыкающими контактами самоблокируется, образует цепи блокировки реле 10 к блока 6 и питания транспаранта 17 блока 8. Транспарант 17 загорается. Затем срабатывает реле 15, своими замыкающими контактами самоблокируется и готовит цепь питания транспаранта 18, а размыкающими - отключает выход блока 4 н от соответствующего входа блока 6. В результате обнуления к-го входа блока 6 происходит выбор нового максимального напряжения с выходов блоков 4 - 4, т. е. выполнение второго шага решения. Второй и последующие шаги аналогичны первому до тех пор, пока не нарушится условие (2).Пусть на некотором шаге решения максимальное напряжение с выходов неотключенных блоков 4- 4 д соответствуета Тогда в блоке 6 сработает реле 10, которое готовит цепь питания обмотки реле 14 , блока 8 и подключает з-ые выходы блоков 1 и 2 ко входам блоков 3 и 5.Если при этом напряжение, пропорциональное суммарным затратам, подаваемое с выхода блока 5 на первый вход блока 7, превышает опорное, то срабатывает реле 13 и своими размыкающими контактами размыкает цепь питания реле 16 блока 8.Во избежание игры контактов реле 13 и 14 последние обладают замедлением при срабатывании. Для стабильной блокировки реле 10 предусмотрено замедление при срабатывании реле 15. Таким образом, при срабатывании реле 14 з реле 16 не срабатывает, т. е. реле 1 О не блокируется, и транспарант 17 не загорается. После срабатывания реле 15 в обнуляется з-ныйвход блока 6, реле 10 отпускает. Происходит переход к следующему шагу решения. При этом одновременно с отпусканием реле 10 а происходит срабатывание очередного реле блока 6 и подключение соответствующего выхода блока 2 ко входу блока 5. Во избежание 1 о переброски схемы блока 7 в момент переключений реле 13 обладает замедлением при отпускании. Если при подключении нового входа блока 5 условие (2) вновь не выполнено, реле 13 не изменит своего состояния. Очередной шаг будет аналогичен предыдущему и т. д., пока условие (2) остается не выполненным. Если на некотором шаге условие (2) будет выполнено, реле 13 отпускает и очередной шаг выполняется аналогично первому. После выполнения и 20 шагов в результате срабатывания реле 15 -15 отключаются все входы блока 6. В блоке 8 загорается транспарант 18, сигнализирующий об окончании процесса. Номерам номенклатур, вошедших в решение, соответствуют горящие транспаранты 17 блока 8 и подключенные к выходам блоков 1 и 2 входы блоков 3 и 5. Показание индикатора 21 блока 3 пропорционально суммарной полезности, а индикатора 23 блока 5 - суммарным затратам 2 ох 1 . Возврат схемы в з исходное положенйе обеспечивается снятием напряжения с устройства.Формула изобретенияУстройство для решения задач дискретного программирования, содержащее блоки задания коэффициентов целевой функции и ограничений, блок вычисления целевой функции, блок вычисления ограничений и блок 4 сравнения, который содержит операционный усилитель с диодно-резистивным релейным элементом в цепи обратной связи, входы операционного усилителя подключены ко входам блока сравнения, а выход операционного усилителя соединен суправляющей 4 обмоткой реле блока сравнения, один входкоторого подключен к выходу блока вычисления ограничений, а другой его вход соединен с одним из выходов блока задания коэффициентов ограничений, отличающееся, тем, что, с целью упрощения устройства и повышения его быстродействия, оно содержит блок. выбора максимума, блок коммутации и индикации и блоки деления, причем блок выбора максимума содержит операционные усилители, входы которых соеи динены со входами блока выбора максимумаа выходы через соответствующие разделительные диоды соединены с управляющими обмотками соответствующих реле блока вы739562 Составитель Г. Сорокин Техред К. Шуфрнч Ко Тираж 75 П ЦНИИПИ Государственного комитета по делам изобретений и открыт3035, Москва, Ж 35, Раушскаи наб иал ППП Патент г. Ужгород, ул. Пррентор Н.СтецдпвсноеСССРйд. 4/5оектнаи, 4 едактор Н. Ахмедова аказ 2927/44 7бора максимума, которые через замыкающие контакты соответствующих реле первой группы блока коммутации и индикаций соединены с виной питания, а цепи обратной связи операционных усилителей содерКатпосле. "довательно соединенные резистор и диод,узлы соедийения которых у всех операцнонкьх усилителей обьединены, блок коммутации и индикации содержит три группы реле, управляющие обмотки реле первой из ко.торЫх соединены с соответствующими транспарантами непосредственно, а с щипай питания - . через собственные замыкающие кон "- такты н через последовательно соединенныезамыкающие контакты одноименных реле второй группы и размыкающий контакт реле блока сравнения, управляющие обмотки реле второй группы через замыкаюгцие контакты реле блока выборамаксимула соединены с шиной питания, управлявшие обмотки реле третьей группы через параллельно включенные соб "ственные залыкающие контакты и замыка вшие контакты соответствующих реле бло.- ка выбора максимума соединены с шиной питания, которая через последовательно сое диненные размыкатощие контакты третьей" группы соедйнена с подвижными контактами переключателя, неподвижный контакткоторого соединен с соответствующим транс-.парантом, первые входы блоков деления подключены к соответствующим выходам блока задания коэффициентов целевой функции, которые через замыкающие контактысоответствующих реле блока выбора максимума соединены со входами блока вычисленйя целевой функции; вторые входы блоковделения подключены к соответствующим вы 40 ходам блока задания коэффициентов ограничений, которые через замыкающие контакты соответствующих реле блока выборамаксимума соединены со входами блока вычисления ограничений, а выходы блоков деления через" размыкаюшие контакты соответствующих реле третьей группы блокакоммутациии индикации соединены со входами блока выбора максимума.Источники информации,принятые во внимание при экспертизе1 1, Авторское свидетельство СССР475630, кл. б 06 Ст 7/48, 1973.2. Авторское свидетельство СССР позаявке2523949/18-24, кл. б 06 б 7/48,12.09.77 (прототип).