Устройство для решения оптимизационных задач стандартизации

 

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

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

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

РЕСПУБЛИН рц G 06 G 7/122

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМ

ПРИ ГННТ СССР

f (21) 4615733/24-24 (22) 06.12.88 (46) 23.09.90. Бюл, N 35 (72) О.Г. Алексеев, В.А. Бурцев, С.А. Васильковский и H.È. Ячкула (53) 681,3 (088.8) (56) Авторское свидетельство СССР

И 1265800, кл. G 06 G 7/122, 1985.

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

Р 1501093, кл. G 06 G 7/122, 1988, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СТАНДАРТИЗАЦИИ

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

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

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

Устройство содержит шину 1 питапервую. вторую и третью груп-, пы (по mn) регистров 2« -2 3

3, 4, -4 „. соответственно, накапmh ливающий сумматор 5, гятый элемент

6 задержки, счетчик 7 задания вариантон, генератор 8 тактовых импульсов, третий регистр 9, сумматор 10 первый II и второй 12 регистры, блок

13 сравнения, второй 14, третий 15, первый 16 и четвертый 17 элементы задержки, первый 18, второй 19 и тре„„Я0„„1 594568 А 1

2 (57) Изобретение относится к вычислительной технике, Цель изобретения расширение функциональных возможностей за счет учета ограничений на возможности производства. достигнута . введением дополнительных групп ре-. гистров, хранящих заданные ограничения, вычитающих счетчиков, арифметических блоков, определяющих очередное значение целевой функции при переборе вариантов, а также соответсвующим усложнением цепей управления и логики. 1 ил ° тий 20 разделительные диоды, ключ 21, выключатель 22 установки начального состояния, выключатель 23 запуска, матрицу из m

И 32,-32,„, группу из m регистров 33, группу из (mn-2) элементов ИЛИ 34 и группу из (mn-1) элементов И 35, группу из m элементов И 36, первую группу из ш элементов ИЛИ 37, группу из п элементов ИЛИ 38, группу из ш вычитающих счетчиков 39, группу регистров из m 40,,четвертый элемент И 41, группу из m триггеров 42 вторую и третью группы элементов И

43 и 44, вторую группу из m элементов ИЛИ 45, третий элемент И 46, .1594568 группу из п триггеров 47, первый элемент И 48, первый 49 и второй 50 формирователи импульсов.

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

Определить о2 4 ? такое, что

f (о() min(f (u) !со (1 1 (1) где f ((4 = С, +minX g С; x... !

" end x.. !

1 е ".! (2) (ерш при ограничениях: (3) х,.«< à,, i ею, ХЕ ."! (4) где С; начальные затраты, связанные с использованием изделий i-го типа и не зависяшие от числа этих изделий;

С вЂ” производственно-эксплуата1) ционные затраты на удовлетворение изделиями 1-го типа потребностей j-го вида а — максимально возможный объем производства изделий i-ro,типа; х.. =1 — если изделие i-го типа !

1 используется для удовле.творения j é потребности и х < =0 — в противном случае.

Устройство работает следующим образом.

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

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

1J ("1" на третьем входе элемента И 27) возможности по использованию его не

45 исчерпаны ("1" на втором входе эле1 мента И 2/) и j--я потребность не удовлетворена ("1" на первом входе элемента И 27) .

5

35 от шины питания поступает на считывающие входы регистров 28 и осуществляется запись содержащегося в них числа в вычитающие счетчики 29, а также через элемент 17 задержки на считыва!ощие входы регистров 40 и осуществляют запись содержащегося в них числа в вычитающие счетчики

39 и, кроме того, на первые входы элементов И 43 и 44 обнуляет регистры 3 и сумматор 5 и переводит в нулевое состояние триггеры 47. Одновременно сигнал поступает через элемент

14 задержки на счетный вход счетчика 7, на выходе которого образуется комбинация 000...01, При этом сигнал с i-го выхода счетчика 7 поступает на вторые входы элементов И 43. ! и 44 и, если сигнал единичный; то

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

На этом этап предварительной настройки устройства закопчен. После замыкания выключателя 23 опорное напряжение через замкнутые контакты ключа 21 поступает на вход генератора 8, с выхода которого импульсы поступают на первые входы элементов И 36 и первый вхоц элемента И 31, на втором входе которого поддерживается единичHое напряжение от элемента ИЛИ-НЕ 30.

На выходе элемента И 27 ячейки затние в том случае, если i-й тип изделия входит в исследуемый вариант И

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

ИЛИ-HE 30, на выходе которого появля(! !! ется сигнал 0, который з акры ва ет элемент И 3 1 .

1594568 1, 5

1

3С

5.

Пусть, например, одновременно по- . явились сигналы об обнулении из ячеек 24, 24ю,, 24 (это происходит в случае, когда С и =С „= С „,„) . При этом сигнал из 24 и поступает на вход элемента И 36„ и одновременно через элементы HJIH 34, 34 ...,,34 поступает на инверсные входы элементов И 35 ... °,35„,„, запрещая прохождение сигналов об обнулении от ячеек 24 „ 24„,„ ° Таким образом, осуществляется выделение одного сигнала из нескольких поступивших на его входы. На выходе имеется только сигнал от ячейки 24ц, в результате чего следующий импульс от генератора 8 . проходит через элемент И 36 и, поступает на вход регистра 3„ и записывает ся в нем, на считывающий вход регистра 2 1, с выхода которого величина

С „, записанная в нем, поступает на вход накапливающего сумматора 5 и складывается тем.числом, что там записано, а также на первые входы элементов ИЛИ 37, и. 38,.

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

39„, вычитая из его содержимого единицу. Если в результате этого на выходе счетчика 39, появляется сигнал обнуления (что свидетельствует об исчерпании возможности по произвЬдству изделия первого типа), то этот сигнал проходит через элемент ИЛИ

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

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

38,, отключает первый столбец матрицы ячеек. Это приводит к тому, что появляется сигнал "1" на выходе ячейки 24 „. Следующий импульс от генератора 8 осуществляется запись единицы в регистр 3, добавление велишь чи. С,„. Из регистра 2„„к содержимому сумматора 5 и отключение и-го столбца матрицы ячеек, в результате чего на всех входах элемейта ИЛИ-НЕ .

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

Описанный процесс повторяется цо тех пор, пока не удовлетвореньt все потребности (т.е. все триггеры 47,, ...,47„ переходят в единичное состояние), или выяснено, что при заданных ограничениях на производство изцелий, включенных в анализируемый вариант, все потребности удовлетворены быть не-,могут (при этом все триггеры 42 переходят в единичное состояние, а хотя бы один из триггеров 47 остается в состоянии "0").

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

10. Кроме того, импульс с формирователя 50 поступает на вторые входы элементов И 32, на первые входы которых подается сигнал от соответствующего разряда счет чика 7 (таким образом единичные сигналы имеются только на выходах тех элементов И 32, которые соответствуют изделиям, включенным в анализируемый вариант д), сигналы с выходов которых поступают на считывающие входы соответствующих регистров 33, обеспечивая выдачу хранящихся в них величин на сумматор 10.

Одновременно сигнал с выхода генера40 тора 50 поступает на вход второго элемента 15 задержки, где задерживается на время, достаточное для завершения суммирования в сумматоре 10. С выхода сумматора 10 число, соответ45 ствующее формуле (2), поступает на первый вход блока 13 сравнения, на второй вход которого поступает величина f+, записанная в регистре 1?. Сигнал с выхода формирователя 50 посту56 пает на управляющий вход блока 13 сравнения, в результате чего в нем выполняется сравнение.

Если f(я) y f", то сигнал с первого выхода блока 13 сравнения через разделительный диод 18 поступает на считывающие входы регистров 28 ячеек затрат, осуществляя запись величии С; в вычитающие счетчики 29, на вход эле1594568 мента 17 задержки и с его выхода — на . считывающие входы регистров 40, осу-, ществляя запись величин в вычитающие счетчики 39, а также на входы обнуления регистров 3, сумматора 5 и пер, 5

Вые входы элементов И 43 и 44.

Одновременно сигнал с выхода блока сравнения через разделительный диод

1;.8 и элемент 14 задержки поступает а счетный вход счетчика 7, в результате чего на выходе счетчика 7 образуется новая кодовая комбинация,. срответствующая новому варианту ис" пользуемых изделий. Если B i-ом раз11 11

15 рйде 1, то триггер 42 установлен

11 11 в. состояние О ° ус тройство готово для анализа нового варианта издеЗ ИЙ .

Если f(jd) (2 1 то сигнал с второго выхода блока 13 сравнения постуг(ает на вход записи регистра 9, в ко1ором фиксируется комбинация из елий, а также через элемент 16 заержки на считывающий вход регист- 25 ра 11, с выхода которого, число Х Ьу) поступает в регистр 12 и становится опорным У для последующих шагов решения. Одновременно сигнал с выхода блока сравнения поступает 30 на входы записи регистров 4,,..., 4, запоминая план ((x; ((и через разделительный диод 19 на считываюп1ие входы регистров 29 ячеек зат11ат, осуществляя запись величин С 1 вычитающие счетчики 29 и через элемент 17 задержки на считывающие ходы регистров 40, осуществляя запись величин С; в вычитающие счетчики 39, а также на входы обнуления .регистров 53„ сумматора 5, первые входы элементов И 43 и 44. Одновременно сигнал с выхода блока сравнения через разделительный диод 19 и элемент 14 задержки поступает на 45 счетный вход счетчика 7, в результате чего на его выходе образуется новая комбинация "О" и "1", соответствующая новому варианту используемых изделий. При этом сигнал с i ãî разряда счетчика 7 поступает на вторые входы элементов И 43, 44 и, ес- ли в i-ом разряде "1", триггер 42 установлен в состояние "0". Устройство готово для анализа нового варианта изделий.

В том, случае, если удовлетворейие всех потребностей достигается при задействовании всех имеющихся. в распоряжении (в данном варианте rd) изделий, то все триггеры 47 и 42

11 I t в состоянии 1 сигнал с выхода элемента И 48 поступает на вход формирователя 50, импульс с выхода которого обеспечивает сравнение текущего варианта с предыдущими аналогично описанному, а также на инверсный вход элемента И 41, сигнал с выхода элемента И 46 поступает на вход формирователя 49, импульс с выхода которого поступает на второй вход элемента И 41,сигнала с выхода элемента

И 41 нет и устройство работает аналогично описанному, (Если имеющихся в анализируемом варианте запасов иэделий недостаточно для удовлетворения всех потребностей, то не все триггеры 47 переходят в состояние "1" и на выходе элемента И 48 "0", в то время как исчерпание всех запасов ведет к тому, что все триггеры 42 переходят в состояние "1" и на выходе элемента И 46 появляется сйгнал логичес11 ll кои 1, в результате на выходе элемента И 4 1 появляется сигнал " 1 ", говоря о т ом, ч то анализируемая комбинация н е является допустимой (р ешения нет ) ° Сигнал с выхода эл емента И 4 1 через разделительный диод

2 0 поступает на входы элементов 1 4 и 1 7 задержки, сигналы с выходов которых об е сп ечивают переход к новому варианту изделий и подготавливают устройство для е го анализа анало гично описанному .

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

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

1594568

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

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

И вЂ” со счетным входом вычитающего счетчика, группу из m регистров задания начальных затрат, вьгходы которых соединены с соответствующими входами сумматора, первую группу из m элементов И, первые входы которых соединены с выходами соответствующих разрядов m-разрядного счетчика задания вариантов, а выходы — с входами считывания соответствующих регистров группы, группу из п триггеров, единичные выходы которых соединены с соответствующими входами первого элемента

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

ИЛИ, группа из m регистров, группа из

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

40 вторыми входами первых элементов И ячеек задания производственно-эксплуатационных затрат, выходы третьих элементов И всех ячеек соединены с соответствующими входами элемента

45 ИЛИ НЕ Выход которого соединен с вторым входом второго элемента И, выход третьего элемента И первой ячейки соединен с вторым входом первого элемента И группы из mn элементов

О И, с инверсным входом первого элемента И группы из (тп-1) элементов И и с вторым входом первого элемента

ИЛИ группы из (mn-2) элементов ИЛИ, выход третьего элемента И каждой

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

12 центов ИЛИ, причем выход каждого

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

Й группы из тп элементов, начиная с второго, выходы всех элементов И этой группы соединены со считывающими вхоДаии соответствующих регистров первой группы из mn регистров и с инфор-. мационными входами соответствующих 2р регистров второй группы, выходы эле-

Ментов И группы из mn элементов, соответствующих i-й строке матрицы яче" ек задания производственно-эксплуатационных затрат, i l m соединены 2$ соответствующими входами i-го элемента ИЛИ первой группы:из m элементов,выходы которых соединены со счетными входами соответствующих вычитающих счетчиков группы, кодовые входы которых соединены с выходами соответствующих регистров группы из m регистров, выходы элементов И группы из mn, 1леиеитов, соответствующие )-иу столбцу матрицы ячеек, j=l,n, соеди-, нены с соответствукпрщи Входаии J-ro э лемента ИЛИгруппы изп элементов,вы4оды элементов ИЛИ группы соединены с единичными входами триггеров группы из и .триггеров, инверсные выходы которых 4р соединены с вторыми входами вторых элеМентов И ячеек соответстующего столбца матрицы, выходы разрядов счетчика задания вариантов соединены с пер®ыми входаии соответствующих эле- 45 йеитов И второй грцппы и с инверсными входами соответствующих элемен.тов И третьей группы, катоды перво" го и второго разделительных диодов через четвертый элемент задержки . gg соединены с вторыми входами элемен тов И второй группы и с неинвертирую"

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

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

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

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

1594568

Составитель Г. Осипов

Редактор М. Бланар Техред Л.Оли цык Корректор Т. Малец

Заказ 2832

Тираж 562

Подписное

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

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

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