Устройство для решения оптимизационных задач стандартизации Советский патент 1990 года по МПК G06G7/122 

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

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

На чертеже изображена схема устройства.

Устройство содержит шину 1 питайся, первую, вторую и третью груп- пы (по ran) регистров 2.,-2.„„, 3 31 tГИГР тт

rnti соответственно, накапливающий сумматор 5, пятый элемент 6 задержки, счетчик 7 задания вариантов, генератор 8 тактовых импульсов, третий регистр 9, сумматор 10, первый 11 и второй 12 регистры, блок 1-3 сравнения, второй 14, третий 15, первый 16 и четвертый 17 элементы задержки, первый 18, второй 19 и третий 20 разделительные диоды, ключ 21, выключатель 22 установки начального состояния, выключатель 23 запуска, матрицу из mxn ячеек 24 задания про- изводственно-эксплуатационных затрат, при этом каждая ячейка, содержит первый 24, третий 26 и второй 27 элементы И, регистр 28 и вычитающий счет- адк 29, элемент ИЛИ-НЕ 30, второй элемент И 31, первую группу элементов И 32 ,-32, группу из m регистров 33, группу из (тп-2) элементов ИЛИ 34 и группу из (тп-1) элементов И 35, группу из m элементов И 36, первую группу из m элементов ИЛИ 37, груп- пу из п элементов ИЛИ 38, группу из m вычитающих счетчиков 39, группу регистров из m 40, четвертый элемент И 41, группу из m триггеров 42, вторую и третью группы элементов И 43 и 44, вторую группу из m элементов ИЛИ 45, третий элемент И 46,

Сд

:о

4

сл

ОС

группу из п триггеров 47, первый элемент И 48, первый 49 и второй 50 формирователи импульсов.

Задача, решаемая устройством, формируется следующим образом.

Определить с/4 I такое, что

f(ff) min|f(w)Ao; l}, (1)

4j

K,j,

ные с использованием изде ЛИЙ i-ro типа и не зависящие от числа этих изделий;

производственно-эксплуата ционные затраты на удовлетворение изделиями типа потребностей j-ro вида;

максимально возможный объем произ Еюдства изделий i-ro .типа; если изделие i-ro типа используется для удовлетворения j-й потребности и - в противном случае. Устройство работает следующим образом.

Перед началомрешения счетчик 7 обнуляется, в регистр 28 каждой ячейки 24j; (1 1,т, j I,n) записывается-число .С--, равное пронз- водственно-эксплуатационнььм затратам при выполнении j-й работы i-м изделием. В регистры 33 записываются числа, равные BejjH4HHaM начальных затрат на разработку и производство изделий соответствующего типа. Если количество анализируемых изделий - меньше т, то в оставшиеся регистры записываются максимально возможные числа, В-регистры 40 записываются числа.: равные ограничениям на. возможности производства а-, Б регистр 12 записывается максимально возможное число ( 1.1 ,,, J Ь ).

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

10

t5

20

15

30

35

0

от шины питания поступает на считывающие входь регистров 28 и осуществляется запись содержащегося в них числа в вычитающие счетчики 29, а также через элемент 17 задержки на считывающие входы регистров 40 и осуществляют запись содержащегося в них числа в вычитающие счетчики 39 и, кроме того, на первые входы элементов И 43 и 44, обнуляет регистры 3 и сумматор 5 и переводит в нулевое состояние триггеры 47, Одновременно сигнал поступает через элемент 14 задержки на счетный вход счетчика 7, на выходе которого образуется комбинация 000.,,01, При этом сигнал с i-ro выхода счетчика 7 посту-- пает на вторые входы элементов И 43- и 44. и, если сигнал единичный, то

сигнал с выхода элемента И 43- посту- 1

пает на к-вход соответствующего триггера 42 и сигнал с инверсного выхода триггера поступает на второй вход элемента И 27 ячеек i-й строки. Если на 1-м входе счетчика 7 имеется О, то эта строка затрат не задействована-.

На этом этап предварительной настройки устройства закончен. После за- i мыкания выключателя 23 опорное напряжение через замкнутые контакты ключа 2 поступает на вход генератора 8, с выхода которого импульсы поступают на первые входы элементов И 36 и первый вход элемента И 31, на втором входе которого поддерживается единичное напряжение от элемента РШИ-НЕ 30, На выходе элемента И 27 ячейки затрат 24 -. имеется единичное напряже- ние в том случае, если i-й тип изде- .лия входит в исследуемьш вариант (j i(l на третьем входе элемента И 27) I возможности по использованию его не ДЗ исчерпатт (1 на втором входе эле- ментаИ27)и -я потребность не удовлетворена ( 1 на первом входе , элемента И 27),

С выхода элеме нта И 25 импульсы от генератора 8 .поступают на счетный вход вычитающего счетчика 29. После того, как один или несколько счетчи- ков обнуляются, сигнал об обнулении проходит через элемент М 26 и поступает на соответствующий вход элем ента ИЛИ-НЕ 30, на выходе которого появляется сигнал О, который элемент И 31,

закрывает

Пусть, наприм.ер, одновременно появились сигналы об обнулении из ячеек 24j , 24п,п (это происходит в случае, когда С. При этом сигнал из 2А , поступает на . вход элемента И 36, и одновременно через элементы ИЛИ 34 , 34 ,..., 34 поступает на инверсные входы элементов И 35 ,.., ,35, запрещая прохождение сигналов об обнулении от ячеек 24,, . Таким образом, осуществляется выделение одного сигнала из нескольких поступивших на его входы. На выходе имеется только сигm15 не-,могут (при этом все триггеры 42 переходят в единичное состояние, а хотя бы один из триггеров 47 остается в состоянии О).

В первом случае сигнал с выхода

нал от ячейки 24 , в результате чего следующий импульс от генератора 8 : проходит через элемент И 36 , поступает на вход регистра 3,, и записывается в нем, на считывающий вход регкст- 20 элемента И 48 поступает на инверсный ра 2. , с выхода которого величина вход элемента И 41 и вход формирова- С« , записанная в нем, поступает на теля 50 импульсов, сигнал с выхода вход накапливающего сумматора 5 и поступает на считывающий вход сум- складывается тем.числом, что там за- матора 5, с выхода ,которого величи- писано, а также на первые входы эле- 25 на С(со) подается, на вход сумматора

10. Кроме того, импульс с формирователя 50 поступает на вторые входы элементов И 32, на первые входы котоментов ИЛИ 37, и. 38 ,.

С выхода элемента ИЛИ 38.

сигнал поступает на вход триггера 47 , переводя его в единичное состояние и исключая из дальнейшего рассмотрения первый столбец матрицы ячеек. С выхода элемента ИЛИ 37 сигнал поступает на вход вычитающего счетчика 39., , вычитая из его содержимого единицу. Если в результате этого на выходе счетчика 39, появляется сигнал обнуления (что свидетельствует об исчерпании возможности по производству изделия первого типа), то этот сигнал проходит через элемент ИЛИ 45;, и поступает на/вход триггера 42,, переводя его в единичное состояние и

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

Пусть в рассмотренном примере импульс от генератора, прошедший через элемент И 36 и элемент ИЛИ

38,, отключает первый столбец матрицы ячеек. Это приводит к тому, что появляется сигнал I ки 24. Следующий импульс от генератора 8 осуществляется запись единицы в регистр Зщ, добавление величины. С из регистра 2 к содержимому сумматора 5 и отключение п-го столбца-матриць ячеек, в результате чего на всех входах элемента ИЛИ-НЕ 30 присутствует О, а на выходе - 1, и следующие импульсы от генерарых подается сигнал от соответству- ЗС ющего разряда счет-сика 7 (таким образом единичные сигналы имеются только на выходах тех элементов И 32, которые соответствуют изделиям, включенным в анализируемый вариант u)) JJ сигналы с выходов которых поступают на считывающие входы соответств тоищх регистров 33, обеспечивая выдачу хра- НЯШД1ХСЯ в них величин на сумматор 10. Одновременно сигнал с выхода генера- 40 тора 50 поступает на вход второго элемента 15 задержки, где задерживается на время, достаточное для завершения суммирования в сумматоре 10. С выхода сумматора 10 число, соответ- 45 ствующее формуле (2), поступает на первый вход блока 13 сравнения, на второй вход которого поступает величина -, записанная в регистре 12. Сигнал с выхода формирователя 50 посту- на выходе ячей- 5Q управляющий вход блока 13

сравнения, в результате чего в нем , вьтолняется сравнение.

Если f (to) f , то сигнал с пер- 5; вого .выхода блока 13 сравнения через разделительный диод 18 поступает на считывающие входы регистров 28 ячеек затрат, осуществляя запись величин Сjj в вычитающие счетчики 29, на вход эле

i

тора 8 через элемент И 31 поступают на первые входы элементов И 25,.обес печивая дальнейшее вычитание из счетчиков 29 еще не отключенных ячеек затрат.

Описанный процесс повт:оряется до тех пор, пока не удовлетворены все потребности (т.е. все триггеры 47,,,.

д ...,47„ переходят в единичное состояние), или выяснено, что при заданных ограничениях на производство изделий, включенных в анализируемый вариант, все потребности удовлетворены быть

15 не-,могут (при этом все триггеры 42 переходят в единичное состояние, а хотя бы один из триггеров 47 остается в состоянии О).

В первом случае сигнал с выхода

20 элемента И 48 поступает на инверсный вход элемента И 41 и вход формирова- теля 50 импульсов, сигнал с выхода поступает на считывающий вход сум- матора 5, с выхода ,которого величи- 25 на С(со) подается, на вход сумматора

Если f (to) f , то сигнал с пер- вого .выхода блока 13 сравнения через разделительный диод 18 поступает на считывающие входы регистров 28 ячеек затрат, осуществляя запись величин Сjj в вычитающие счетчики 29, на вход элемента 17 задержки и с его выхода - иа считывающие входы регистт:)ов 40, осу-, ществляя запись величин в вычитающие счетчики 39, а также на входы обнуления регистров 3, сумматора 5 и пер- аые входы элементов И АЗ и 44.

Одновременно сигнал с выхода блока Сравнения через разделительный длод 118 и элемент 14 задержки поступает .счетный вход счетчика 7, в резуль- TJaTe чего на выходе счетчика 7 об- |азуется новая кодовая комбинацией, срответствующая новому варианту ис ользуемых изделий. Если в i-ом раз- зде 1, то триггер 42 установлен ; состояние О. Устройство готово. анализа нового варианта иэдеJJHU.

Если f (iO) f, то сигнал с вто- pjoro выхода блока 13 сравнения посту- на вход записи регистра 9, в ко- ilopOM фиксируется .комбинация изделий, а также через элемент 16 задержки на считывающий вход регист- 11, с выхода которого, число f (ц/) Поступает в регистр 12 и становится опорным f для последующих ша iloB решения. Одновременно сигнал с 1|ыхода бло1са сравнения поступает rta входы записи регистров А 4j , запоминая план fx -. ff и через Х азделительный диод 19 на считываю- п1;ие входы регистров 29 ячеек зат- , осуществляя запись величин С.. i вычитающие счетчики 29 и через злемент 17 задержки на считывающие 4ходь1 регистров 40, осуществляя за - величин С ,.- в вычитающие счет- 4ики 39, а также на входы обнуления регистров 53, сумматора 5, первые йходы элементов И.43 и 44. Одновременно сигнал с выхода блока сравне- 1ШЯ через разделительный диод 19 и элемент 14 задержки поступает на счетный вход счетчик а 7, в результа- te чего на его выходе образуется но- )вая комбинация О и 1, соответствующая новому варианту используемых изделий. При этом сигнал с i-ro разряда счетчика 7 поступает на вторые входы элементов И 43, 44 и, ее- яи в i-oM разряде 1, триггер 42 установлен в состояние О. Устройство готово для анализа нового варианта изделий.

В том, случае, если удовлетворение всех потребностей достигается при задействовании всех имеющи ;ся.

0

5

в распоряжении (в данном варианте и)} изделий, то все триггеры 47 и 42 в состоянии 1 сигнал с выхода элемента И 48 поступает на вход формирователя 50, импульс с выхода которого обеспечивает сравнение текущего варианта с предыдущими аналогично описанному, а также на инверсный вход элемента И 41, сигнал с выхода элемента И 46 поступает на вход формирователя 49, импульс с выхода которого поступает на второй вход элемента И 41,сигнала с выхода элемента И 41 нети устройство работает аналогично описанному.

Если имеющихся в анализируемом

варианте запасов изделий недостаточно для удовлетворения всех потреб0 ностей, то н.е все триггеры 47 переходят в состояние J и на выходе элемента И 48 О, в то время как исчерпание всех запасов ведет к тому, что все триггеры 42 переходят в состояние 1 и на выходе элемента И 46 появляется сигнал логической I, в результате на выходе элемента И 41 появляется сигнал 1, . говоря о том, что анализируемая ком0 бинация не является допустимой (решения нет), Сигнал с выхода элемента И 41 через разделительный диод 20 поступает на входы элементов 14 И 17 задержки, сигналы с выходов ко5 торых обеспечивают переход к новому варианту изделий и подготавливают устройство для его анализа аналогично описанному.

5

Далее весь описанный процесс повторяется многократно до тех пор, пока не будут просмотрены все возможные комбинации используемых изделий. После того, как проанализирован последний вариант, на следующем шаге на выходе счетчика 7 появляется сигнал переполнения, который размыкает ключ 21, в результате чего прекращается подача напряжения на генератор 8 и решение задачи заканчивает- ся. По окончании решения задачи в регистре 9 зафиксирован оптимальный вариант используемых изделий, в регистре 12 - величина минимальных затрат, соответствующая оптимальному- варианту, а в регистрах 4 - оптималъ- ньй план распределения изделий по потребностям.

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

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

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

вторым входом второго элемента И, в ход третьего элемента И первой ячей ки соединен с вторым входом первого элемента И группы из mn элементов И, с инверсным входом первого элеме та и группы из (тп-1) элементов И и с вторым входом первого элемента ИЛИ группы из {тп-2) элементов ИЛИ выход третьего элемента И каждой К-й ячейки, К 2, mn-1, соединен неинвертирующим -входом (К-1)-го элемента И группы из (mn-1) элементов и с первым входом (K-l)-ro

делительных диодов, отличаю-j

щ е е с я тем, что, с целью расшире- элемента ИЛИ группы из (mn-2) эле10

15

25

JQ

-, и94568 10

ния функциоанльных возможностей за счет учета ограничений на возможное- - ти производства, в него введены второй, третий и четвертый элементы И, элемент ИЛИ-НЕ, третий разделительный диод, четвертьш и пятый элементы задержки, два формирователя импульсов, три группы из тхп регистров, накапливающий сумматор, группа из (mn-1) элементов И, группа из (mn-2) элементов ИЛИ, группа из ran элементов И, первая и вторая группы из m элементов ИЛИ, группа из п элементов ИЛИ, группа из m регистров, группа из m вычитающих счетчиков, вторая и третья группы из m элементов И, грун- па из m триггеров, а в каждую ячейку задания производственно-эксплуатационных затрат введены второй и третий элементы И, причем выход второго элемента И соединен с первыми входами первого и третьего элементов И ячейки, а выход обнуления вычитающего счетчика ячейки соединен с вторым входом третьего элемента И ячейки, при этом выход i-ro разряда счетчи- ка задания вариантов, i 1 ,in, соединен с первыми входами вторых элементов И i-й строки ячеек задания производственно-эксплуатационных затрат,, с перв ым входом i-ro элемента И второй группы из щ элементов и с инверсным входом i-ro элемента И третьей ,. выход генератора тактовых импульсов соединен с первыми входами второго элемента И и всех . элементов И группы из тп.элементов, выход второго элемента И соединен с вторыми входами первых элементов И ячеек задания производственно-эксплуатационных затрат, выходы третьих элементов И всех ячеек соединены с соответствующими входами элемента дс ИЛИ-НЕ, выход которого соединен с

вторым входом второго элемента И, выход третьего элемента И первой ячейки соединен с вторым входом первого элемента И группы из mn элементов И, с инверсным входом первого элемента и группы из (тп-1) элементов И и с вторым входом первого элемента ИЛИ группы из {тп-2) элементов ИЛИ, выход третьего элемента И каждой К-й ячейки, К 2, mn-1, соединен с неинвертирующим -входом (К-1)-го элемента И группы из (mn-1) элементов и с первым входом (K-l)-ro

30

35

40

50

j

Л

ментов ИЛИ, причем вьпсод каждого

К-го элемента ИЛИ группы ,mn-2, соединен с инвертирующим входом (К+О-го элемента И группы из (тпп-1) элементов и с лторым входом следую- njiero элемента ИЛИ группы из .(mn-2) : лементов, а выход третьего элемен- ija И последней mn-й ячейки соединен с| нёинвертирующим входом (mn-l)-ro з|лемента И группы из (mn-l) элемент i|oB, выходы элементов И группы из irm-l) эл-ементов соединены с вторы- йи входами соответствующих элементов И группы из mn элементов, начиная с : торого, выходы всех элементов И это 1|рупЬы соединены со. считывающими входами соответствующих регистров пер- ой группы иэ mn регистров и с инфор faциoннымй входами соответствуюпдах pfeгиcтpoв второй группы, выходы элеЦентов И группы иэ ran элементов, со с|тветствующих t-й строке матрИ10 1 яче 4к задания производственно-эксплуа- 1|ационных затрат, ,т, соединены 4 соответствующими входами i-ro эле- Цента ИЛИ первой группы из m элементов, выходы которых соединены со счет входами соответствующих вычитаи 1Ф1Х счетчиков группы, кодовые вз4оды |оторых соединены с выходами соответ с|твующих регистров группы из m регисров, выходы элементов И грзтпы из m э|лементов, соответствующие j-му Столбцу матрицы ячеек, j l,n, соеди ены с соответствукяцч }и взводами JTO э|пемента ИЛИ группы из п элементов,вы- х|оды элементов ИЛИ группы соединены с циничными входами триггеров группы из п триггеров, инверсные выходы которых соединены с вторыми входами вторых элементов И ячеек соответстующего столбца матрицы, вькоды разрядов счетчика з адания вариантов соединены с пер- входами соответствуюдзих элементов И второй грцптты и с инверсными входами соответствующих элементов И третьей группы, катоды перво- и второго разделительных диодов через четвертый элемент задержки Соединены с вторыми входами элемея

0

4568

12

тов и второй группы и с 1№инвертирую- г

щими входами элементов И третьей

группы, выходы элементов И второй группы соединены с единкчными входами соответствующих триггеров группы из m триггеров, выходы обнуления iro вычитающего счетчика.и i-ro элемента И третьей группы соедине1сы с входами i-ro элемента ИЛИ второй группы, ,m

,m, выход которого соединен с

нулевым входом соответствующего триггера группы из m триггеров,единичные выходы всех триггеров этой группы соединены с соответствующими входами третьего элемента И, а нулевые выходы триггеров группы соединены с третьими входами вторых элементов И ячеек соответствующих строк матрицы, выход первого элемента И соединен с входом первого формирователя импульсов и с I инверсным входом четвертого элемен- та И, выход третьего элемента И через последовательно соединенные второй формирователь импульсов и пятый элемент задержки-соединен .с неинвертирующим входом четвертого элемента И, выход которого соединен с анодом третьего разделительного диода, катод которого соединен с катодом первого и второго разделительных диодов, выход первого формирователя импульсов соединён со считывающим входом накапливающего сумматора, с вторыми вхо- дами элементов И первой группы и с входом треть.его элемента задержки, выходы регистров первой группы из Ш1 регистров соединены с соответст- вукядими информационными входами на- капливгиощего сумматора, выходы регистров второй группы из mn регистров соединены каждый с информационным входом соответствующего регистра третьей группы, входы записи которых соединены с п ервым выходом блока сравнения, а входы обнуления регистров второй группы накапливающего сумматора подключены к выходу четвертого элемента задержки, выход накапливактще- го сумматора соединен с соответству- к(цим входом сумматора.

,V--

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

Составитель Г. Осипов Редактор М. Бланар Техред Л.Олийиык Корректор Т. Малец

Заказ 2832

Тираж 562

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Рауиюкая наб., д. 4/5

ПроизводстБвнно-издательский комбинат Патент, г. Ужгород, ул. Гагарина, 101

Подписное