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

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

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

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

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

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

(1)

i-1

при ограничении

П a-jX. ,(, ,)

где CT - затраты, приписанные подмножеству Si;

1, если ij е Si и О в против 1Jном случае; . 1, если S; войдет в покрытие, X; и О в противном случае. Эта цель юстигается тем, что в уст10ройство для реш.ения задач дискретного программирования, содержащее блоки задания коэффициентов целевой функции и ограничений, блок вычисления и блок сравнения, который содержит операцион15ный усилитель с диодно-резистивным релейным элементом в цепи обратной . связи, входы операционного усилителя подключены к входам блока сравнения, а выход операционного усилителя соеди20нен с управляющей обмоткой реле блока сравнения, один вход которого подключен к выходу блока вычисления ограничений, а другой его вход соединен с одним из выходов блока задания коэффициентов ограничения, блок выбора MaKCHt wa, блок коммутации и индикации, и блоки деления, блок выбора максимума содержит операционные усилители, входы которых соединены с входами блока выбора максимума, а выходы через соответствующие разделительные диоды соединены с управ ляющими обмотками соответствующих реле блока быбора максимума, которые через замыкающие контакты соответствук щих реле первой группы блока коммутации и индикации соединены с шиной питания, а цепи обратной связи операционных усилителей содержат последовательно соединенные резистор и диод,узлы соедийения которых у всех операционных усилителей объединены, блок коммутации и индикации содержит три группы реле, управляющие обмотки реле первой из которых соединены с соответствующими транспарантами непосредственно, а с шиной питания - через собственные замыкающие контакты и через последовательно соединенные замыкающиеконтакты одноименных реле второй группы и размыкающий контакт реле блока сравнения, управляющие обмотки реле второй группы через замьшающие контакты реле блока выбора максимума соединены с шиной пита ния, управляющие обмотки реле третьей группы через параллельно включенные собственные замьпсающие контакты и замыкающие контакты соответствующих реле блока выбора максимума соединены с шиной питания, которая через последовательно соединенные размыкающие контакты третьей группы соединена с подвижными контактами переключателя, неподвижный контакт которого соединен с соатветс1вующим транспарантом, первые входы блоков деления Подключены к соответствующим выходам блока задания коэффициентов целевой функции, которые через замыкающие контакты соответствующих реле блока выбора максимума соединены с входами блока вычисления ограничений, а выходы блоков деления через размыкающие контакты соответствующих реле третьей группы блока коммутации и индикации соединены с входам блока выбора максимума, введен блок моделирования топологии покрытия, при этом блок моделирования топологии покрытия содержит группу сумматоров, группу последовательно соединенных шунтирующих ключей, кнопку, реле и транспарант, причем выход блока выбора максимума подключен к управляющей обмотке реле, выход каждого сумматора группы соединен с соответствующим входом блока задания коэффишентов целевой функции, одноименные входы сумматоров группы объединены и через Cooтвeтcтвytoщиe последовательно соединенные шунтирующие ключи группы и общий замьпсаюший контакт реле подключены к шине минусового потенциала, замыкающий контакт реле через .кнопку запуска соединен с размыкающим контактом и входом транспаранта, параллельно каждому щунтируюшему -ключу подключен размыкакщий контакт одноименного реле второй группы блока коммутании и индикации. На чертеже приведена структурная схема устройства. Устройство содержит блок 1 задания коэффициентов целевых функций, состоящий из переменных резистороЬ 1, ,.., Ij. блок 2 задания коэффициентов ограничений, состоящий из переменных резисторов 2, ..,, 2, блок 3 вычисления/ целевых 4ункций, группу блоков 4, ..., 4, деле™ блок 5 вычисления ограничений. блок в выбора максимума, блок 7 сравнения, блок 8 коммутации и индикации, блок 9 моделирования топологии покрытия.. В состав блока 6 выбора максимума входят группа реле Ю.,, ..., 10,, группа диодов 11-,, ..., llji группа операционных усилителей 12 ., ..., 12р. Блок 7 сравнения включает реле 13 и операционный усилитель 14. Блок 8 коммутации и индикации содержит три группы реле 1х| .... 1п 15;, ... I 15, ID, . I Ib)., транспаранты 4.8,..,, 18 п переключатель 19. Блок 3 вычисления целевой функции включает сумматор 20 и индикатор 21. Блок 5 вычисления ограничений включает сумматор 22 и индикатор 23. Блок 9 моделирования топологии покрытия включает группу сумматоров 24i, ..., 24, каждый из которых имеет по тп входных переменных резисторов 24 j; (. 1, л , j 1, m ) во входных цепях, группу последовательно соединенных шунтирующих ключей (25 - 25j,) ... (,j), кнопку 26, реле 27, транспарант 28, шина 29 питания. Блок 9 предназначен для задания структуры подмножеств и моделирования условия (2). Принцип работы устройства основан на пошаговом формировании покрытия путем выбора на каждом шаге подмножества SK , которому соотв1ртствует градиент V mcixh,, где h-,r 5: OL ij/с , 5 и преобразования коэффициентов с(;; таКИМ образом, чтобы согласно условию (2) О для всех sinS. Проце решения заканчивается по признаку (1 О Перед решением задаются числа г и m , соответствующие количествам подмножеств ; и элементов множества S. Подвижные контакты резисторов (24j.24) - (24п-,-24у,т)бпока 9 устанавливаются в положения, которые соответствуют напряжениям, пропорциональным исходным коэффициентам ci;;. С помощью ключей (25 ,.- 25 (25,, - ) формируется топология подмножеств ( ) таким образом, что разомкнутому положению ключа 25 соответствует 6 - 5 , а замкнутому 6,,- 9t Si . Подвижные контакты резисторов 2 2 блока 2 устанавливаются в положение, соответствующее напряжениям, пропорциональным коэффициентам С - С. С помощью потенциометра 2 t блока 2 задается достаточно большое напряжени позволяющее исключить влияние блока 7 не используемого при решении задачи о покрытии, переключатель 19 блока 8 перед решением устанавливается в положение, соответствующее числу п . Устройство работает следующим образом. При подаче напряжения на шины питания в блоке 9 загорается транспарант 28, сигнализирующий о готовности устройства к ршботе. С подвижных контактов потенциометров блока 2 на вторые входы блоков 4- - 4| посту. пают напряжения, пропорциональные величинам С j . На первые входы блоков 4 -. - 4 , а следовательно, и с их выходов на входы блока 6 первоначально напряжения не поступают, поскольку входные цепи усилителей блока 9 отключены от щины 29 При нажатии кнопки 26 напряжения с минусовой шины 29 через контакт 27 через 27, контакты кнопки 26 и цепи, образованные контактами реле 15 - 15 и ключами 25 „ поступает н;а входы усилителей 24 - 24 . С выходов усилителей блока 9 через резисторы блока 1 на первые входы блоков 4- - 4 поступают положительные напряжения, пропорциональные И с( j , , а на выходах блоков 4 - 4 р образуются напряжения, пропорционал ные градиентам Vt- . Напряжение, пропорциональное величине .. vnc(Xh- , обусловит срабатыва26ние реле 27, подключенного к общему выходу усилителей 12 - 12 „ блока 6, которое своим контактом 27 подклк чает шину 29 к входным нецям уснлителей . Гаснет транспарант 28.. В блоке 6 срабатывает реле Юл, которое обусловит срабатывание реле 15, 17 Y блока 8 и самоблокирование реле 151,. ,1кающий контакт реле 17 образует совместно с размьжаюшим контактом реле 13 блока 7 цепь питания обмотки реле 16. Последнее срабатывает, контактом 16 блокирует цепь питания реле 10 в блоке 6, своим замыкаюшим контактом в блоке 8 самоблок№руется и образует цепь питания транспаранта 18/, загорание которого сигнализирует о-том, что подмножество S включено в минимальное покрытие множества . Работа блока 5 состоит в следующем. При срабатывании на некотором шаге решения реле 10, замыкающий контакт П 10 - подключает резистор 2| лока 2 к соответствующему входу сумматора 22 . блока 5, Напряжение, пропорциональное коэффициенту С. , поступающее с подвижного контакта резистора 2, поддерживается на К-м входе сумматора 22. В результате соабатывания реле 15 г- г.Н размыкактся контакты 15 - 15 , которые разрывают те входные цепи усилителей 24 - 24п . которыми с помощью разомкнутых ключей группы 251 моделировалось условие 6 к. 6 S . Тем самым обеспечивается 0| 0 vij , т. е. учет условия (2) и с выходов усилителей 24 - 24 j через резисторы 1 1 „ на первые входы блоков деления 4 4 U поступают новые значения сумм коэффициентов . С выходов блоков 4 4 , за исключением выхода блока 4 который отключен контактом 15 , на соответствующие входы блока 6 подаются перерассчитанные величины градиентов. Происходит переход ко второму шагу решения, на котором аналогично осуществляется выбор нового максимального градиента для включения следующего подмножества S- ( i# k ) в покрытие. На некотором шаге решения все входы усилителей 24 - 24 окажутся отключенными, т. е. с выходов блоков 4 п на входы блока 6 напряжения поступать не будут. В результате этого обесточивается обмотка реле 27, контакт которого образует цепь питания транспаранта 28, сигнализирующего об окончании процесса решения. Горяшие транспаранты 18, - 18 j блока 8 визуально фиксирую соответствующие множества; 5j S, включенные в минимальные покрытия. П OKOHiaHHH процесса решения ко входам сумматора 22 будут подключены резисторы блока 2, .соответствующие множес вам, вошедшим в покрытие, а показание индикатора 23 дает сумму (1), отража полученное значение целевбй функции. Аналогично, в блоке 3 происходит запоминание суммы m п : ppc.,V,j, Таким образом, благодаря введению блока моделирования топологии покрыти выходы которого соединены со входами блока задания коэффициентов целевой функции, а вход - с выходом блока выбора максимума, обеспечивается положительный эффект, выражающийся в расширении функциональных возможностей устройства на класс задач типа задачи о покрытии. Формула изобретени Устройство для решения задач дискр ного программирования по авт. св. №739562, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет моделирования процесса решения задачи о минимальном покрытии, оно дополнительно содержит блок моделирования топологии покрытия, йри этом блок моделирования топологии покрытия содержит группу сумматоров, группу последовательго соединенных шунтирующих ключей, кнопку, реле и транспарант, причем выход блока выбора максимума подключен к управляющей обмотке реле, выход каждого сумматора группы соединен с соответствующим входом блока задания коэффициентов целевой функции, одноименные входы сумматоров группы объединены и через соответствующие последовательно соединенные шунтирующие ключи группы и общий замыкающий контакт реле подключены к шине минусового потенциала, замыкающий контакт реле через кнопку запуска соединен с размыкающим контактом и входом транспаранта, параллельно каждому шунтирующему ключу подключен размьпсающий контакт одноименного реле второй группы блока коммутации и индикации. Источники информации, принятые во внимание при экспертизе 1. Авторское свиде ельство СССР № 739562, кл. Q 06G, 7/48, 1977 (прототип).

- i Л

,- rigja

|M| III . - -- j.ti Jl - -.

|M| III . - -- -, - -j. -f--t , t t1 I t tf

P -t-1 , 1 IIf I. .tf yJife- I

Гч.; .

10. / . I I i I IГ t I. , I 1 T т

/Дп йгМ А сЬ

.v;5r-:

«, «„ M-xH

I

)

..

jf 5fl/

sVn

#

27

--- tt tbvfr/f/f