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

 

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

Социапистическик

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (iii928372 (6l ) Дополнительное к авт. саид-ву № 739562 (51)М. Кл.

G 06Q 7/48 (22)Заявлено 09.06.80 (2l ) 2938913/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 15.05.82. Бюллетень М 18

Дата опубликования описания 18.05.82 р3С J48pCllNIN4 ll0lIINT9T

СССР

IIo делам иэебретений и открытий (53) УДК 681.3 (088.8) О. Г. Алексеев, В. Ю. Мержанов и B. Ф. Григорьев (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

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

По основному авт. св. ¹ 739562 известно устройство, предназначенное для решения задачи дискретного программирования, заключающейся в выборе оптимального числа номенклатур при ограничении на суммарные затраты (1) .

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

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

= Я„, ...,о„„ набора подмножеств 6, обеспечивающего и = min+ Q-X„. (1)

1=1 при ограничении и у; .«=, °,в

1=1 где С; — затраты, приписанные подмножеству 5 l

4„. = 1,если h е 3; и 0 в противном случае;

X = 1, если S; войдет в покрытие, и 0 в противном случае.

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

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

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

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

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

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

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

2,..., 2„„, блок 3 вычисления целевых функций, группу блоков 4.„ ...,- 4„ деления, блок 5 вычисления ограничений, блок В выбора максимума, блок 7 сравнения, блок 8 коммутации и индикации, блок 9 моделирования топологии покрытия.

В состав блока 6 выбора максимума входят группа реле 10„...,, 10д, груп па диодов 11„, ..., 11,, группа опера ционных усилителей 12„,..., 12п. Блок 7 сравнения включает реле 13 и операционный усилитель 14. Блок 8 коммутации и индикации содержит три группы реле

15,, ..., 15,, 16,, ..., 16,, 171, ..., 17)1 транспаранты f8 18 и, переключатель 19. Блок 3 вычисления целевой функции включает сумматор 20 и индикатор 21. Блок 5 вычисления ограничений включает сумматор 22 и индикатор 23.

Блок 9 моделирования топологии покрытия включает группу сумматоров 24„ ..., 24,, каждый из которых имеет по щ входных переменных резисторов 24;> (1 - 1, и, j = 1, tn ) во входных цепях, группу последовательно соединенных шунтируюших ключей (25 < — 25„„)... (25„25, ), кнопку 26, реле 27, транспарант, 28, шина 29 питания. Блок 9 предназначен для задания структуры подмножеств и моделирования условия (2).

Принцип работы устройства основан на пошаговом формировании покрытия путем выбора на каждом шаге подмножества Як,, которому соответствует r радиент 4 =mcnab, где b;= : Q. >!Ñ;

5 92 и преобразования коэффициентов с ; таким образом, чтобы согласно условию (2) с, . = 0 для всех 6;e sinS<. Процесс решения заканчивается по признаку g О.

М

Перед решением задаются числа т и п, соответствующие количествам подмножеств S; и алементов множества ф.

Подвижные контакты резисторов (241124 п ) — (24п - 24 щ)блока 9 устанавливаются вположения,,которые соответствуют напряжениям, пропорциональным исходным коэффициентам с ;.

С помощью ключей (25 „„- 25,( (25,1 — 25п ) формируется топология подмножеств (9„- S„) таким образом, что разомкнутому положению ключа 25д соответствует Й- ь S„., а замкнутому—

6- 4. 5„.

Подвижные контакты резисторов 2 1—

2 блока 2 устанавливаются в положение, соответствующее напряжениям, пропорциональным коэффициентам С, — С,„.

С помощью потенциометра 2, +1 блока 2 задается достаточно большое напряжение, позволяющее исключить влияние блока 7, не используемого при решении задачи о покрытии, переключатель 19 блока 8 перед решением устанавливается в положение, соответствующее числу и .

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

28, сигналйзируюший о готовности устройства к работе. С подвижных контактов потенциометров 2 1 — 2 блока 2 на вторые входы блоков 41 — 4 1поступают напряжения, пропорциональные величинам С „- .

На первые входы блоков 4 — 4 „, а следовательно, и с их выходов на входы блока 6 первоначально напряжения не поступают, поскольку входные цепи усилителей блока 9 отключены от шины 29.

При нажатии кнопки 26 напряжения с минусовой шины 29 через контакт 27

1 через 27, контакты кнопки 26 и цепи, образованные контактами реле 15 - 15 и ключами 25„„- 25 п„поступает на входы усилителей 24, — 24,„. С выходов усилителей блока 9 через резисторы 1 — 1 блока 1 на первые входы блоков 41 — 4„поступают положитель ные напряжения, пропорциональные Г d 1=9, а на выходах блоков 4-=I 1

4 „образуются напряжения, пропорционал ные градиентам 1 ;

Напряжение, пропорциональное величине „=шпак И;, обусловит срабатыва8372 6 ние реле 27, подключенного к общему выходу усилителей 12., — 12, блока 6, которое своим контактом 27 "подключает шину 29 к входным цепям усилителей 24 — 24 „. Гаснет транспарант28.

В блоке 6 срабатывает реле 10, которое обусловит срабатывание реле 15, 17 блока 8 и самоблокирование реле

15,. Замыкающий контакт реле 17» образует совместно с раэмыкающим кон- . тактом реле 13 блока 7 цепь питания обмотки реле 161. Последнее срабатывает, контактом 16 блокирует цепь питания реле 104, в блоке 6, своим замыкающим контактом в блоке 8 самоблоки руется и образует цепь питания транспаранта 18, загорание которого сигнализирует о.том, что подмножество 5 включено в минимальное покрытие множества S ..

Работа блока 5 состоит в следующем.

При срабатывании на некотором шаге решения реле 10 замыкающий контакт

10 подключает резистор 2 флока 2 к k

25 соответствующему входу сумматора 22 блока 5. Напряжение, пропорциональное коэффициенту С, поступающее с тюдвижного контакта резистора 2, поддерживается на К-м входе сумматора 22.

В результате срабатывания реле 15 ч. пи размыкаются контакты 15 - 151, которые разрывают те входные цепМ усилителей 24 „— 24» которыми с помощью разомкнутых ключей группы 251,„- 25 „, 35 моделировалось условие c S; . Тем самым обеспечивается с . = о чб. ь. 5 A Ь, т. е. учет условия (2) и с выходов усилителей 24 1 — 24 > через резисторы 111д на первые входы, блоков деления 41—

4 поступают новые значения сумм козф40 11 J фнциентов 4.- . С выходов блоков 4 1)

4п, за исключением выхода блока 4

1 который отключен контактом 15k на соответствующие входы блока 6 подаются

45 перерассчитанные величины градиентов.

Происходит переход ко второму шагу решения, на котором аналогично осуществляется выбор нового максимального градиента для включения следующего подмножества S ° (ig g ) в покрытие.

На некотором шаге решения все входы усилителей 24 „— 24 „окажутся отключенными, т. е. с выходов блоков 4 -4, на входы блока 6 напряжения поступать не будут. В результате этого обесточиь- вается обмотка реле 27, контакт кото55 рого образует цепь питания транспаранта 28, сигнализируюшего об окончании процесса решения. Горящие транспаранты

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

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

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

7 8283

18 „ - 18 блока 8 визуально фиксируют соответствующие множества, 5 - Ь „, 1 включенные в минимальные покрытия. По окончании процесса решения ко входам сумматора 22 будут подключены резисторы блока 2,,соответствующие множеств вам, вошедшим в покрытие, а показание индикатора 23 дает сумму (1), отражая полученное значение целевой функции.

Аналогично, в блоке 3 происходит 10 запоминание суммы

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

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

1. Авторское свидетельство СССР

% 739562, кл. 5 06 7/48, 1977 (прототип) .

928372

Составитель В. фукалов

Редактор И. Касарда Техред С. Мигунова Корректор О. Билак

Заказ 3242/62 Тираж 732 Подписнбе

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушскаи наб., д. 4/5 филиал ППП "Патент", г. Ужгород, ул. Проектная, 4