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

1

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

,)

С MQKC

I 1-1

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

.

YI i

(-1.

Х,0,Г., и,, 2

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

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

Ь- предельно допустимое значение суммарных затрат,

i- предельное допустимое значение количества изделий i-го типа.

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

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

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

Блоки 1 предназначены для задания дискретных функций f , (х) и f| (х ) . Блок 1 содержит 2 п потенциометров 10, 11 и 2 -| полюсов 12 и 13 где м макс(п, ) + 1 ,

184042

Шюки 2 преднАзначе ы для сосди- неш1я выходов блоков 1 со входами блоков 3-5 в соответствии со значениями X ,, вошедшим в оптимальное

5 решение до данного шага реше}гия. Блоки 2 содержат полюсы 14-23, (n-t-1 ) канальный распределитель 24 ур(звней однотактного действия с прямой и обратной последовательностью

О переключения каналов и четыре группы ключей 25-28. Распределитель 24 монет быть выполнен на основе кольцевых сдвигающих схем, регистровых схем или многоустойчивых схем.

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

a,b,c,d и выходы (каналы) ео,е,..-5 е,. Питание подается на вход а , при этом в исходном состоянии нагфяжение подается на выход е. Поступление

20 сигнала на вход с обеспечивает пе- рерслючение напряжения с канала на канал в прямой последовательности, а поступление сигнала на вход d - в обратной последовательности. При

25 поступлении импульса на вход Ъ распределитель 24 возвращается в исходное Состояние.

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

30 Блок 4 предназначен для определения значений at , (х, ) f; (xj+-l)-f; (х; ,1

:: ДЧ--, (х, ) i, + i)- fnXi)- содержит 2hi сумматоров 32, 33 и

полюсы 34-39.

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

отношений h,(х, / дГ,v х ,;/дv, (х ;).

5лок 7 содержит операционный уси- 40 лисель 43 с выпрямительными диодами - , 44-1, 442 и масштабными резисторами

45,, 45 в цепи обратной связи, масштабным резистором 46 в первой входной цепи и переменным

45 резистором 47 - во второй входной цепи. В состав блока 7 входит также ключ 48.

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

55 масштабными резисторами 58 во входных цепях.

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

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

Решение заканчивается при исключении из рассмотрения всех и fj(xi), Vi(x), о чем сигнализирует индикаторный элемент 72. Результаты решения определяются: значения х j - по показаниям счетчиков 75, значение С - по показаниям индикаторного прибора 30, знаvriчение Vi(Xi) по показаниям ин 1 1

дикаторНого прибора 41.

Перед решением щетки потенциометров 10 и 11 устанавливаются в пложения, которым соответствуют выходные напряжения, пропорциональные fjCx;) и Ч |(х,-), :. ГТт, Xj 1,2,...,п , соответственно, щетка потенциометра 47 устанавливается в положение, которому соответствует выходное напряжение, пропорциональное Ъ, а щетки потенциометров IO|(v-,,+i) i(ii.i)- в положения, которым соответствуют выходные на- пряжения, пропорциональные и руЪ соответственно. Подается напряжение на шины устройства, при этом сигналы с нулевых выходов тригге218404Л

ров 63 и 69 подаются на входы элементов И 65, с выходов которых напряжения подаются на полюсы 61 блока 9 и далее на полюса 49 блока 8. 5 С полюсов 49 сигналы поступают на управляющие входы ключей 52, которые подключают полюсы 50 блока 8 ко входам соответствующих операционных усилителей 55.

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

5 80 этого блока и далее на полюсы 16 блоков 2. С полюсов 16 напряжение поступает на вход а распределителя 24 каждого из блоков 2, а с него - на выход е каждого распре20 делителя 24, С выхода ej, напряжение поступает на управляющие входы ключей и26 каждого из блоков 2. Ключи и 26 соединяют полюсы 14 с полюсами 20, а полюсы

2 15 - с полюсами 22 блоков 2. При этом напряжения, пропорциональные f,(l) и Ч ;(}, с полюсов 12(и 13),- блоков 1 поступают через полюсы 14; и 15;- блоков 2 и ключи 25. и

30 26 на полюсы 20 и 22. С этих полюсов блоков 2 напряжение поступает на полюсы 34 и 35 блока 4, с которых оно поступает на неинвертирующие входы сумматоров 32 и 33. С

35 выходов сумматоров блока 4 напряжения, пропорциональные д fj (х) и (х|), через полюсы 38 и 39 блока 4 поступают на входы соответствующих блоков 6, с выходов которых

40 сигналы поступают через полюсы 50 и ключи 52 блока 8 на входы соответствующих операционньк усилителей 55. Происходит выбор максимального из поданных на входы операционных

45 усилителей 55 сигналов, срабатывает тот из ключей 5.4, которому соответствует максЬ; (х,). Для определенности будем считать, что .MftKchj; (xj. ) h(x.)i. Тогда сработает ключ

50 , и напряжение поступает через полюс 5 Ц на полюс 78 блока 9 и полюс 18 блока 2. С полюса 78 сигнал поступает на элементы задержки 67 и 73|, а через элемент

55 ИЛИ 62 - на единичный вход триггера 63, который переходит в единич |ое состояние. При этом снимается напряжение с одного из входов элементов И 65 и далее с полюсов 61 блока 9, полюсов 49 и управляющих входов ключей 52, которые отклчают входные полюсы 49, и управляющих входов ключей 52, которые отключают входные полюсы 50 от входов операционных усилителей 55. Снимается напряжение с управляющего входа ключа 54), который отключает шину питания от полюса 51. Одновременно сигнал, поступивший на полюс 18 блока 2/,, вызывает переключение напряжения с выхода е распределителя 24 этого блока на выход е.При этом закрываются ключи 25-) , 26 и открываются ключи 27 , 28 и 252, 262, вследствие чего полюсы 14, 15 соединяются с полюсами 21, 23-,, соответственно, а полюсы 14.,2, с полюсами 20, 22 соответственно. С полюсов 20, 21 блока 2.( напряжения поступают на полюсы 34 35 блока 4, а с полюсов 22, 23,, блока 2,, - на полюсы 36, 37 блока 4. Кроме того, напряжение, пропорциональное f,, ( 1 ), с. полюса 21,, блока 2,, поступает через полюс 31 блока 3 на вход сумматора 29, а напряжение, пропорциональное (lj с: полюса 23 блока 2 поступает на вход сумматора 40 блока 5. С выхода сумматора 40 сигнал поступает на индикаторный прибор 41 и через масштабный резистор 46 - на вход операционного усилителя 43. Дальнейшая работа схемы зависит от выполнения ограничения (2) задачи дискретного программирования С .)-(3) . Если V(1)Ъ, то открывается ключ 48 блока 7, и напряжение питания поступает на полюс 79 блока 9. К этому времени сигнал, поступивший от блока 8 на элемент задержки 67 поступает на первый вход элемента И 68, на второй вход которого подан сигнал с полюса 79. С выхода элемента И 68j сигнал поступает на единичный вход триггера 69, который переходит в единичное состояние , и напряжение с его единичного выхода поступает на первый вход элемента И 70, через полюс 60 блока 9 - на полюс 19-1 блока 2/. Распределитель 24 этого блока переключается в обратной последовательности, и блок 2,f возвращается в состояние, которое было в начале

5

0

первого шага решения. При этом снимаются напряжения с по.гтюса 31 бло-- ка 3 и полюса 42 блока 5, закрывается ключ 48 блока 7 и отключает питание от полюса 57 блока 9. Если величина f (1 )Ь, то ключ 48 остается закрытым, и сигнал от блока 8 через элемент задержки 73/j, время задержки которого больше времени задержки элемента 67 , поступает на первый вход элемента И 74.,, на втором входе которого присутствует напряжение с инверсного выхода триггера 69i. С выхода элемента И 74-, сигнал поступает на вход счетчика 75-,, который увеличивает сзюе содержание на единицу. На этом первый шаг решения заканчивается, и через время, определяемое элементом задержки 64, сигнал с единичного выхода триггера 63 поступает на его нз левой вход. Триггер переходит в нулевое состояние, и дальнейшая

5 работа схемы аналогична рассмотренной, за исключением тог о, что если на первом шаге решения f(l)b, то после возврата в нулевое состояние триггера 63 в начале второго шага решения не поступит сигнал на полюс 61 блока 9, т.е. дискретные функции f(x) и Ч (х) исключаются из дальнейшего рассмотрения.

Решение заканчивается, когда все триггеры 69 перейдут в единичное

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

0

45

hi

X , - m,

где х - окончательное значение

x;(,in), вошедшее в оптимальное решение.

Для возврата устройства в исходное состояние необходимо нажать и отпустить выключатель 76, затем вы- кл)чить выключатель 77 и снять пи- тание с шин устройства. При нажатии выключателя 76 напряжение от шины питания поступает на нулевые входы триггеров 75 и 63, входы возрата п ноль счетчиков 75 и полюс 59 блока 9. Триггеры и счетчики переходят в исходные состояния, а сигнал с полюса 59 поступает на олюсы 17 блоков 2 и далее на входы I-J распределителей 24, которые также ерейдут в исходное состояние.

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

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

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

S

0

.5

0

5

5

0

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

g 5 0 5 о

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

It/J/nr,i

L.JFJ L:.

+ 0-( 5//Г

фиг.З

фиг. 2

73

781 78

т

п

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

Составитель А,Шеренков Редактор К.Горват Техред О.НецеКорректор В. Синицкая

Заказ 1133/57 Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д, 4/5

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