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

 

ОП ИСАЙ ИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик (tl 739562

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 01.11.77 (21) 2539933/18-24 с присоединением заявки №вЂ” (51) М. Кл

G 06 G 7/48

Гооударстееииый комитет

СССР (23) Приоритет—

Опубликовано 05.06.80. Бюллетень №21 (53) УДК 681.335 (088.8) ао делам иаобретеиий и открытий

Дата опубликования описания 15.06.80 (72) Авторы изобретения О. Г. Алексеев, А. А. Бабаев, В. Ю. Мержанов и В. Н. Огнев (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ с = max,йс х

1-"1 при условиях: : a> x> (6; я (1) 10

0 (х (1; (2) х. — целые, Изобретение относится к вычислительной технике и может быть использовано для решения задачи дискретного программирования, заключающейся в наилучшем выборе некоторого комплекта из общего числа и номенклатур (оборудования, грузов и т. п.) чтобы суммарные затраты не превышали указанного предела b, а их суммарная полезность с была максимальной, т. е. где с а 0 и g. o-соответственно коэффи1 циенты полезности и затрат, характеризующие

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

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

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

$0

$$ дов блока задания коэффициентов ограничений (2) .

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

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

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

4Î

1$

20 и

Зе

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

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

Устройство содержит блок 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 †, 15 > — 15, 16 — 16, имеют размыкающие контакты 10 — 10, 13, 14 — 14, 15 — 15„ „

16 — 16„ .

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

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

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

Блок 1 предназначен для задания напряжений, пропорциональных коэффициентам полезности С, с помощью потенциометров

1 — 1 . Блок 2 предназначен для установки напряжений, пропорциональных коэффициентам затрат а и ограничению b, с помощью потенциометров 2 — 2„и 2<+< соответственно.

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

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

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

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

Щетки потенциометров 11 — 1„, 2 — 2 и 2 + устанавливаются в положения, которые соответствуют выходным напряжениям, пропорциональным

739562

Выполнение первого шага решения начинается с подачи питания на устройство.

При этом напряжения с выходов блока 1 и первых выходов блока 2 поступают на входы блоков 4 — 4n, с выходов которых напряжения, пропорциональные величинам †ивЂ, через размыкающие контакты 15 — 15 реле

15 — 15 блока 8 подаются на входы блока 6.

Выходное напряжение усилителя 9 блока 6, на который подано максимальное из напряжений с выходов блоков.4 — 4, обусловит протекание тока по обмотке реле 10, подключенного к выходу этого усилителя, срабатывание реле и запирание диодов цепей обратной связи остальных усилителей 9, т. е. отсутствие тока в выходных цепях последних.

Предположим для простоты описания,. что на первом шаге решения .< — k — = "—

J. ai а„

Следовательно, в блоке 6 срабатывает реле 10„и своими замыкающими контактами подключает первые выходы блоков 1 и 2 ко входам блоков 3 и 5 соответственно, а также готовит цепь питания реле 14» блока 8. При этом напряжение, пропорциональное a„с выхода блока 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 д соответствует а4

Тогда в блоке 6 сработает реле 10д, которое готовит цепь питания обмотки реле 144, блока 8 и подключает s-ые выходы блоков

1 и 2 ко входам блоков 3 и 5.

Если при этом напряжение, пропорциональное суммарным затратам, подаваемое с выхода блока 5 на первый вход блока 7, превышает опорное, то срабатывает реле 13 и своими размыкающими контактами размыкает цепь питания реле 16 блока 8.

Во избежание игры контактов реле 13 и 14 последние обладают замедлением при срабатывании. Для стабильной блокировки реле 10> предусмотрено замедление при срабатывании реле 15. Таким образом, при срабатывании реле 14» реле 164 не срабатывает, т. е. реле 10 не блокируется, и транспарант 17 не загорается. После срабатывания реле 15в обнуляется s-HblH вход блока 6, реле 10 отпускает. Происходит переход к следующему шагу решения. При этом одновременно с отпусканием реле 10в происходит срабатывание очередного реле блока 6 и подключение соответствующего выхода блока 2 ко входу блока 5. Во избежание

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

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

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

21 блока 3 пропорционально суммарной полезности, а индикатора 23 блока 5 — суммарным затратам 2e>x . Возврат схемы в з исходное положенйе обеспечивается снятием напряжения с устройства.

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

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

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

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

Составитель Г. Сорокин

Техред К. Шуфрнч Корректор Н. Стец

Тираж 75! Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений н открытий! l 3D35, Москва, Ж 35, Раушская наб., д. 4/5

Филиал ППП «Патент» г. Ужгород, ул. Проектная, 4

Редактор Н. Ахмедова

Заказ 2927/44

7 бора максимума, которые через замыкающие контакты соответствующих реле первой группы блока коммутации и индикаций соедине»b> с шиной питания, а цепи обратной свя зи операционных усилителей содерЖат последовательно соединенные резистор и диод, узлы соедийения которых у всех операцион ньгх усилителей обьединены, блок коммутации и индикации содержит три группы реле, управляющие обмотки реле первой из которЫх соединены с соответствующими транспарантами непосредственно, а с шинон питания —. через собственные замыкающие кон — такты н через последовательно соединенные замыкающие контакты одноименных реле второй группы и размыкающий контакт реле блока сравнения, управляющие обмотки реле второй группы через замыкаюгцие контакты реле блока выбора максимума соединены с шиной питания, управляющие обмотки реле третьей группы через параллельно включенные соб ственные замыкающие контакты и замыкавшие контакты соответствующих реле блока выбора максимума соединены с шиной питания, которая через последовательно сое диненные размыкаюшие контакты третьей группы соедйнена с подвижными контактами переключателя, неподвижный контакт которого соединен с соответствующим транс-. парантом, первые входы блоков деления подклю ены к соответствующим выходам блока задания коэффициентов целевой функции, которые через замыкающие контакты соответствующих реле блока выбора максимума соединены со входами блока вычисленйя целевой функции; вторые входы блоков деления подключены к соответствующим выл ходам блока задания коэффициентов ограничений, которые через замыкающие контакты соответствующих реле блока выбора максимума соединены со входами блока вычисления ограничений, а выходы блоков деления через" размыкающие контакты соответствующих реле третьей группы блока коммутации и индикации соединены со входами блока выбора максимума.

Источники информации, принятые во внимание при экспертизе

>6 1, Авторское свидетельство СССР № 475630, кл. G 06 G 7/48, 1973.

2. Авторское свидетельство СССР по заявке № 2523949/18-24, кл. G 06 G 7/48, 12.09.77 (прототип).