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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) (51) 4 G 06 G 7/48

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3795735/24-24 (22) 02.08.84 (46) !5 03.86. Бюл. № 10 (72) О.Г.Алексеев, В,Ю.Мержанов, В.В.Спичкин и Н.И.Ячкула (53) 681.333(088.8) (56) Авторское свидетельство СССР

¹ 475630, кл. G 06 G 7/48, 1973.

Букреев И.Н. и др. Микроэлектронные схемы цифровых устройств.

М.: Советское радио, 1975, с. 262299.

Авторское свидетельство СССР (- 739562, кл. G 06 G 7/48, 198&. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ (57) Изобретение относится к области вычислительной техники и. может быть использовано для решения задач дискретного программи" рования. Цель изобретения состоит в расширении функциональных возможностей за счет решения задач дискретного программирования при нелинейных функциях целевого функционала и ограничения. Устройство содержит блоки задания исходных данных, блоки коммутации, блок вычисления целевой функции, блок определения приращений, блок вычисления ограничений, блоки деления, блок сравнения, блок выбора максимума и блок управления 0 соответствующими функциональными связями между ними. 4 ил.

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

1218404

Блоки 2 предназначены для соединения выходов блоков 1 со входами блоков 3-5 в соответствии со эка—

10!

20

30

55 дискретного программирования, заключающейся в наилучшем выборе некоторого комплекта из общего числа m номенклатур (оборудования, грузов и т.п.), чтобы суммарные затраты не превышали допустимого предела Ь, а их суммар— ная полезность С (целевой функционал) была максимальной

С=макс,> f; (x;1

XI 1-1 при ограничениях

XI =O,1

2 где Г,(х;) — функция, характеризующая полезность х, изделий (номенклатур, грузов, ресурсов и т,п .)

i-го типа (здесь и далее i=1,m);

,, (Х;)- функция, характеризующая затраты, связанные с использованием х; изделий i -го типа, предельное допустимое значение суммарных затрат, предельное допустимое значение количества изделий -го типа.

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

На фиг. 1 приведена блок-схема устройства, на фиг. 2-4 — функцио альные схемы блоков коммутации, выбора максимума и управления.

Ф

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

Блоки 1 предназначены для задания дискретных функций 1",(õ,, и

М;(х; ). Блок 1 содержит 2 г потенциаметров 10, 11 и 2 полюсов 12 и 13 где =макс(п;)+1, чениями х;, вошедшими в оптимальное решение до данного шага решения.

Блоки 2 содержат полюсы 14 — 23, (и+1) канальный распределитель 24 уровней однотактного действия с прямой и обратной последовательностью переключения каналов и четыре группы ключей 25-28. Распределите. ь 24 может быть выполнен на основе коль— цевых сдвигающих схем, регистровых схем или многоустойчивых схем.

Распределитель 24 имеет входы

B 1),с,4 и выходы (каналы) е,е „,..., Питание подается на вход а, при этом в исходном состоянии напряжение подается на выход е, Поступление сигнала на вход с обеспечивает переключение напряжения с канала на канал в прямой последовательности, а поступление сигнала на вход Й в обратной последовательности. При поступлении импульса на вход в рас— пределитель 24 возвращается в исходное состояние.

Блок 3 29, индикаторный прибор 30 и полюсы 31.

Блок 4 предназначен для определения значений 1Г,(х,)=Г;(х;+1, -:";(х;)

:. " р. (х, )=,(х;+>) — 1. (х;). Блок 4 содержит 2 6, сумматоров 32, 33 и полюсы 34 — 39.

Блок 5 содержит сумматор 40, индикаторный прибор 41, полюсы 2.

Блоки 6 служат для определения

1 отношении и, (х,, =,1.,х,, а у,х;) .

Блок 7 содержит операционный усили егп 43 с выпрямительными диодами

- 4.,, 44 и масштабными резисторами

45,, 45> в цепи обратной связи, ма«штабным резистором 46 в первой входной цепи и перемекным резистором 47 — во второй входной цепи. В состав блока 7 входит также ключ 48.

Блок 8 содержит полюсы 49-51> втсрую группу ключей 52, группу раэделительных диодов 53, первую группу ключей 54, группу операционных усилителей 55 с выпрямителькыми диодами 56 и масштабными резисторами 57 в цепях обратной связи и масштабными резисторами 58 во входных цепях.

Блок 9 предназначен для управления блоками устройства в соот1218404 4 ветствии с алгоритмом градиентного метода решения задачи дискретного программирования, выдачи сигнала об окончании решения и индикации его результатов. Блок 9 содержит полюсы 59 — 61, элемент ИЛИ 62, триггер 63, элемент задержки 64, первую группу элементов И 65, разделительный диод 66, первую группу элементов задержки 67, вторую группу элементов И 68, группу триггеров 69, элемент И 70, ключ 71, элемент индикации 72, вторую группу элементов задержки 73, третью группу элементов И 74, группу счетчиков 75, выключатель кнопочный 76, выключатель 77, полюса

78-80.

Устройство решает задачу дискретного программирования (1)-(3) градиентным методом. Решение осуществляется за К шагов поиска, на каждом из которых автоматически определяется maxh,(х;), соответствующее ему значение х; увеличивается на единицу, если выполняется условие (2 ), в противном случае соответствующие функции Г;(х ) и (;(х;) исключаются из дальнейшего рассмотрения. На первом шаге решения х; =О.

Решение заканчивается при исключении из рассмотрения всех и

f (õ;), g;(x;), о чем сигнализирует индикаторный элемент 72. Результаты решения определяются: значения х; — по показаниям счетчиков 75, значение С вЂ” по показаниям индикаторного прибора 30, эна— чение ) Р;(X;) по показаниям инj 1=1 дикаториого прибора 41.

Перед решением щетки потенциометров 10 и 11 устанавливаются в по- ложения, которым соответствуют выходные напряжения, пропорциональные fi(хi) и, (х;), .=l,m, х;=

=l,2,...,ni соответственно, щетка ,потенциометра 47 устанавливается в положение, которому соответствует выходное напряжение, пропорциональное Ь, а щетки потенциометров

10 l(hj+1} и 11;(„;+ 1}- в положения, которым соответствуют выходные на пряжения, пропорциональные g>0 и р Ь соответственно. Подается напряжение на шины устройства, при этом сигналы с нулевых выходов триггеров 63 и 69 подаются на входы элементов И 65, с выходов которых напряжения подаются на полюсы 61 блока 9 и далее на полюса 49 блока 8.

С полюсов 49 сигналы поступают на управляющие входы ключей 52, которые подключают полюсы 50 блока

8 ко входам соответствующих операционных усилителей 55.

Первый шаг решения начинается вкл.счением выключателя 77 блока 9.

При этом напряжение с шины питания через замыкающие контакты выключателя 77 блока 9 подается на полюс

80 этого блока и далее на полюсы

16 блоков 2. С полюсов 16 напряжение поступает на вход а распределителя 24 каждого из блоков 2, а с него — на выход е каждого распре>О делителя 24, С выхода е напряжение поступает на управляющие входы ключей 25 и264 каждого из блоков 2. Ключи 251 и 26 соединяют полюсы 14 с полюсами 20, а полюсы

l5 — с полюсами 22 блоков 2. При этом напряжения, пропорциональные

f„ (1) и Ч,(1 ), с полюсов 12, и 13; блоков 1 поступают через полюсы

14;1и 15;„ блоков 2 и ключи 251. и

ЗО 26,, ка полюсы 20 и 22. С этих полюсов блоков 2 напряжение поступает на полюсы 34 и 35 блока 4, с которых оно поступает на неинвертирующие входы сумматоров 32 и 33. С выходов сумматоров блока 4 напряжения, пропорциональные д Г;(х;) и ду (х;), через полюсы 38 и 39 блока 4 поступают на входы соответствующих блоков 6, с выходов которых

411 сигналы поступают через полюсы 50 и ключи 52 блока 8 на входы соответствующих операционных усилителей

55. Происходит выбор максимального из поданных на входы операционных

45 усилителей 55 сигналов, срабатывает тот иэ ключей )4, которому соответствует макс)т, (X ). Для определенности будем считать, что Makcll<(x „)=

=Ь1(х 1 )i. Тогда сработает ключ

gp 544, и напряжение поступает через полюс 511 на полюс 781 блока 9 и полюс 181 блока 2 . С полюса 781 сигнал поступает на элементы задержки 67 и 73<, а через элемент

ИЛИ 62 — на единичный вход триггера

63, который переходит в единичное состояние. При этом снимается напряжение с одного из входов эле1218404 ментов И 65 и далее с полюсов

61 блока 9, полюсов 49 и управляющих входов ключей 52, которые отключают входные полюсы 49, и управляющих входов ключей 52, которые отключают входные полюсы 50 от входов операционных усилителей 55.

Снимается напряжение с упранляющего входа ключа 544, который отключает шину питания от полюса 51„.

Одновременно сигнал, поступивший на полюс 18п блока 2„, вызывает переключение напряжения с выхода е, распределителя 24 этого блока на выход е,.При этом закрываются ключи 254, 261 и открываются ключи

27<, 8< и 252, 26, вследствие чего полюсы 14„„ 15„„ соединяются с полюсами 21„, 23„, соотнетствен— но, а полюсы 141, 15„. — с полюсами

20, 22, соответственно. С полю— сов 20, 21 блока 2 1 напряжения поступают на полюсы 34„ 35, блока

4, а с полюсов 22, 23, блока 2 1 на полюсы 36,, 37„ блока 4. Кроме того, напряжение, пропорциональное

1,(1), с.полюса 211 блока 2 „ поступает через полюс 31„ блока 3 на вход сумматора 29, а напряжение, пропорциональное Ф„(1), с полюса

23 1 блока 2 „поступает на вход сумматора 40 блока 5. С выхода сумматора 40 сигнал поступает на индикаторный прибор 41 и через масштабный резистор 46 — на вход операционного усилителя 43. ДальнейШая работа схемы зависит от выполнения ограничения (2) задачи дискретного программирования (!)-(3) .

Если Р1(1))Ь, то открывается ключ

48 блока 7, и напряжение питания поступает на полюс 79 блока 9. К этому времени сигнал, поступивший от блока 8 на элемент задержки 671, поступает на первый вход элемента

И 68, на второй вход которого подан сигнал с полюса 79. С выхода элемента И 68 1 сигнал поступает на единичный вход триггера 69, кото— рый переходит в единичное состояние, и напряжение с его единичного выхода поступает на первый вход элемента И 70, через полюс 60 блока 9 — на полюс 19 блока 21. Распределитель 24 этого блока переключается в обратной последовательности, и блок 21 возвращается в состояние, которое было в начале первого шага репи.ния. При этом снимаются напряжения с пnãïîса 31, блока 3 и полюса 42 блока 5, закрывается ключ 48 блока 7 и отклкчает питание от полюса 57 блока 9. .сли величина P„(!)

8 через элемент задержки 73, время задержки которого больше времени задержки элемента 67„, поступает на первый вход элемента

И 74, на втором входе которого при5

Н1

К = Х", + т1, 45 где х. — окончательное значение (x;(i=1,m), вошедшее н оптимальное решение.

Для возврата устройства в исходное состояние необходимо нажать и отпустить выключатель 76, затем выключить выключатель 77 и снять пи— тание с шин устройства. При нажатии выключателя 76 напряжение от шины питания поступает на нулевые входы триггеров 75 и 63, входы воз50

55 сутствует напряжение с инверсного выхода триггера 69 1. С выхода элемента И 74 „ сигнал поступает на вход счетчика 75,1, который увеличивает свое содержание на единицу. На этом первый шаг решения заканчивается, и через время, определяемое элементом задержки 64, сигнал с единичного выхода триггера 63 поступает на его нулевой вход. Триггер переходит н нулевое состояние, и дальнейшая работа схемы аналогична рассмотренной, за исключением того, что если на первом шаге решения ч> (1)>Ь, то после возврата н нулевое состояние триггера 63 в начале второго ,шага решения не поступит сигнал на

30 полюс 61 блока 9, т. е. дискретные функции Г1(х „) и p (x ) исключаются из дальнейшего рассмотрения.

Решение заканчивается, когда все триггеры 69 перейдут в единичное состояние. При этом сигнал с выхода элемента И 70 поступает на управляюший вход ключа 71, который подключает к шине питания элемент индикации 72, загорание которого сигна40 лизирует об окончании решения. Количество шагов решения определяется выражением

1218404 врата в ноль счетчиков l5 и полюс

59 блока 9. Триггеры и счетчики переходят в исходные состояния, а сигнал с. полюса 59 поступает на полюсы 17 блоков 2 и далее на входы

g распределителей 24, которые также перейдут в исходное состояние.

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

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

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

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

И, выход которого соединен с управляющим входом ключа, информационный вход и выход которого подключены соответственно к шине питания и первому выводу элемента индикации, вто- рой вывод которого соединен с шиной нулевого потенциала, выходы элементов задержки второй группы под12I8404 ключены к первым в:".oäàì элементов И третьей группы, выходы которых соединены с входами соответствующих счетчиков группы, выходы которых соединены с нулевыми входами триггеров группы, а через разделительный диод — с нулевым входом триггера, инверсные выходы триггеров группы подключены ко вторым входам соответствующих элементов И первой и третьей групп, а кнопочный выключатель соединен с шиной питания и нулевыми входами триггеров группы, в блоке сравнения выводы потенциометра соединены с шинами питания и нулевого потенциала, а подвижный контакт петенциометра подключен ко второму входу операционного усилителя, в блоке выбора максимума выходы ключей второй группы через масштабные резисторы соединены с входами соответствующих операционных усилителей, а информационные входы ключей первой группы — с шиной питания в блоках коммутации выходы распределителя уровней подключены к управляющим входам соответствующих ключей групп, в блоках задания исходных данных первые и вторые вы— воды потенциометров обеих групп соединены соответственно с шиной питания ишиной нулевого потенциала, подвижные контактыкаждой парыпотенциометров обеих групп подключены к.информационным входам каждой пары соответствующих ключей групп блока коммутации, выходы которых соединены с соответствующими входами сумматоров блока вычисления целевой функции, блока определения приращений

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

35 управления, а входы питания распределителей уровней блоков коммутации через выключатель блока управления подключены к шине питания.! 2 I (Ч4 () l

f2l8404

181 51

Й1 771

Р1 Я 1

Составитель A,Øeðåíêoâ

Техред О.Неце Корректор Б.Синицкая

Редактор h.Ãîðíàò

Заказ ll33/57

Тираж б73 Подписное

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

ll3035, Москва, Ж-35, Раулская наб., д. 4/5

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