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

(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

1

Изобретение относится к вычислительной технике и может быть использовано для решения задачи дискретного программирования, заключающейся в наилучшем выборе Некоторого комплекса из обш,его числа п номенклатур (оборудования, грузов и т. п.) чтобы суммарные затраты не п-ревышали указанного предела Ь, а их суммарная полезность с была максимальной, т. е. с max .л cj,xj., при условиях: где а1 0-соответственно коэффициенты полезности и затрат, характеризующие j-ю номенклатуру. -..-Известно устройство для решения дискретных задач оптимизации градиентным методом, содержащее блоки нелинейности, блоки умножения на постоянный коэффициент, блоки установки затрат, блок развертки, блок измерения градиента и блок суммирования 1.

Однако это устройство содержит большое количество сложных узлов (блоки нелинейности, блоки перемножения, блок измерения градиента). Кроме того, поиск решения осуществляется ручным переключением и связан с анализом показаний приборов на каждом шаге рещения, что требует больщих затрат времени. (1) 10 (2) , 20 Наиболее близким техническим решением к изобретению является устройство, которое также содержит блоки задания коэффициентов целевой . функции и ограничений, блок вычисления целевой функции, блок вычисления ограничений и блок сравнения, который содержит операционный усилитель диоднорезистивным релейным элементом в цепи обратной связи, входы операционного усилителя подключены ко входам блока сравнения, а выход операционного усилителя соединён с управляющей обмоткой реле блока сравнения, один вход которого подключен к выходу блока вычисления ограничений, а другой его вход соединен с одним из выходов блока задания коэффициентов ограничений 2.

Кроме того, это устройство содержит блок генерирования соседних точек, регистры точек и блок счетчиков. Однако устройство сложно и решает поставленную задачу методом перебора, что требует много времени.

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

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

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

Блок-схема устройства для решения задач дискретного программирования приведена на чертеже.

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

Блок б выбора .максимума содержит операционные усилители 91-9п, реле 10i - Юн и разделительные диоды 111 - 1 Ы . Блок 7 сравнения содержит операционный усилитель 12 с диодно-резистивным релейным элементом в цепи обратной связи и реле 13.

Блок 8 коммутации и индикации содержит реле 14: - 14п, реле 15i - 15ц, реле 16i - 0 16fl, транспаранты 171 -17„ и 18 и переключатель 19. Реле 10 - 10п, 13, 141-14п, 151-15п, 16 -16(7, имеют размыкающие контакты 10, -10, 13, 14 -14, 15, -15 16,-1б;,.

Блок 3 вычисления целевой функции содержит сумматор 20 и индикатор 21.

Блок 5 вычисления ограничений содержит сумматор 22 и индикатор 23.

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

Блок 1 предназначен для задания напряжений, пропорциональных коэффициентам полезности С, с помощью потенциометров . Блок 2 предназначен для установки напряжений, пропорциональных коэффициентам затрат at и ограничению Ь, с помощью потенциометров 21-2п и 2n.| соответственно.

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

которых автоматически определяется шах. Соответствук)щее значение х путем коммутации входных цепей блоков 3, 5 и цепей транспарантов 17 блока 8 полагается равным единице, если при этом.выполняется условие (2), в противном случае - х: 0.

На следующем шаге процедура повторяется для оставшихся номенклатур и т. д. Об окончании решения сигнализирует TpaiHcnaрант 18 блока 8.

I

Перед решением выбирается число п, соответствующее количеству номенклатур и определяющее число задействованных потенциометров блоков 1, 2, число блоков 4, усилителей 9 блока 6, обмоток реле 14-16 и положение переключателя 19 в блоке 8.

Щетки потенциометров 1,, 2i-2г1И 2n+i устанавливаются в положения, которые соответствуют выходным напряжениям, пропорциональным f, а и Ь.

Выполнение первого шага решения начинается с подачи питания на устройство. При этом напряжения с выходов блока 1 и первых выходов блока 2 поступают на входы блоков 4i-4п, с выходов которых напряжения, пропорциональные величинам , через размыкаюш,ие контакты 151-15цр ле 15f-15п блока 8 подаются на входы блока 6. Выходное напряжение усилителя 9 блока 6, на который подано максимальное из напряжений с выходов блоков .4i-4n, обусловит протекание тока по обмотке реле 10, подключенного к выходу этого усилителя, срабатывание реле и запирание диодов цепей обратной связи остальных усилителей 9, т. е. отсутствие тока в выходных цепях последних.

Предположим для простоты описания,, что на первом шаге решения . Следовательно, в блоке 6 срабатывает реле 10(5 и своими замыкающими контактами подключает первые выходы блоков 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 происходит выбор нового максимального напряжения с выходов блоков 4f-4п , т. е. выполнение второго шага решения. Второй и последующие шаги аналогичны первому до тех пор, пока не нарушится условие (2).

Пусть на некотором шаге решения максимальное напряжение с выходов неотключенных блоков 4|-4п соответствует . Тогда в блоке 6 сработает реле lOg, которое готовит цепь питания обмотки реле 14 блока 8 и подключает выходы блоков 1 и 2 ко входам блоков 3 и 5.

Если при этом напряжение, пропорциональное суммарным затратам, подаваемое с выхода блока 5 на первый вход блока 7, превышает опорное, то срабатывает реле 13 и своими размьжающими контактами размыкает цепь питания реле 16 блока 8. Во избежание игры контактов реле 13 и 14 последние обладают замедлением при срабатывании. Для стабильной блокировки реле 10s предусмотрено замедление при срабатывании реле 15. Таким образом, при срабатывании реле 14s реле 16s не срабатывает, т. е. реле 10 не блокируется, и транспарант 17а не загорается. После срабатывания реле 15s обнуляется 5-ный°вход блока 6,

реле 10s отпускает. Происходит переход к следующему шагу решения. При этом одновременно с .отпусканием реле 10s происходит срабатывание очередного реле блока 6 и подключение соответствующего выхода блока 2 ко входу блока 5. Во избежание

0 переброски схемы блока-7 в момент переключений реле 13 обладает замедлением при отпускании. Если при подключении нового входа блока 5 условие (2) вновь не выполнено, реле 13 не изменит своего состояния. Очередной шаг будет аналогичен предыдущему и т. д., пока условие (2) остается не выполненным. Если на некотором шаге условие (2) будет выполнено, реле 13 отпускает и очередной шаг выполняется аналогично первому. После выполнения п

0 шагов в результате срабатывания реле 15i - 15п отключаются все входы блока 6. В блоке 8 загорается транспарант 18, сигнализирующий об окончании процесса. Номерам номенклатур, вошедших в решение, соответствуют горящие транспаранть 17 блока 8

и подключенные к выходам блоков 1 и 2 входы блоков 3 и 5. Показание индикатора 21 блока 3 пропорционально суммарной полезности, а индикатора 23 блока 5 - суммарным затратам .|1о|Х| . Возврат схемы в

исходное положение обеспечивается снятием напряжения с устройства.

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

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

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

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