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

Изобретение относится к вычислительной технике и является усовершенствованием изобретения по авт.св. К 1501094.

I

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

На чертеже представлена схема устройства.

Устройство содержит шину 1 питания, блок 2 задания затрат, блок 3 выбора оптимального варианта, второй сумматор 4, генератор 5 тактовых импульсов, ключ 6, элементы И 7, - 7 дополнительной группы, второй блок 8 сравнения, дополнительный элемент И 9, дополнительньй регистр 10, четвертый элемент 11 задержки, третий элемент 12 задержки, счетчик 13 задания вариантов,третий регистр 14, третий и четвертый диоды 15 и 16, выключатель 17 начального положения, выключатель 18 запуска, дополнител-ьный триггер 19. Блок 2 содержит матрицу 20 ячеек, каждая из которых состоит из регистра 21, вычитающего счетчика 22, элемента И 23 и шины 24 задания эксплуатационных затрату группу элементов И 25 - 25, группу регистров 26, - 26 , шины 27, - 27 j задания начальных затрат. Блок 3 содержит первый блок 28 сравнения, первый 29 и второй 30 регистры, группу счетчиков 31 - 31,, элемент И 32, ключи 33 - 33, триггеры 34, - 34,, первый и второй элементы 35 и 36 задержки, первый и второй разделительные диоды 37 и 38, первый сумматор 39.

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

Л

:л

эо :л

tsu

:д

на количество входящих в него типов изделий и выбор наилучшего из допустмых вариантов,

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

Перед началом решения счетчик 13 обнуляется, в регистр 21 каждой ячей 20 записьгоается число, равное производственно-эксплуатационным затратам при выполнении j-и работы i-м типом изделия С,, .

В регистры 26 записьшаются числа, равные величинам начальных затрат С; на разработку и производство i-ro ти па изделий. Если количество анализируемых изделий m m, то в регистры с номерами i m, записываются максимально возможные числа. В регистре 29 записывается максимально возможно число (111....11), а в регистр 10 - число К, равное максимально допустимому количеству типов изделий.

Решение задачи начинается кратковременным включением выключателя 17, в результате чего напряжение от опорного источника питания поступает на считывающие входы регистров 21 ячеек 20 и осуществляет запись содержащегося в них числа в вычитающие счет чики 22, а также обнуляет счетчики 31, триггеров 34 и триггеры 19.

Кроме того, напряжение от источника опорного питания поступает на вход элемента 12 задержки, с выхода которого через время задержки,достаточное для завершения всех переходных процессов, через диод 15 поступает на счетньй вход счетчика 13,на выходе которого образуется комбинация 000..01 (только первый тип изделий), а также на вход элемента 11 задержки, где сигнал задерживается на время,, достаточное для осуществления, суммирования в сумматоре 4. С выхода сумматора 4 хшсло М, равное количеству используемых типов изделий, поступает на второй вход блока 8 сравнения, на первый вход которого из регистра 10 подается число 4, равное максимально допустимому числу изделий. При М К триггер 19 открывает элементы И 7 и 9.

На этом зтап предварительной настройки устройства заканчивается.

При замыкании выключателя 18 запуска опорное напряжение через замк- нутые контакты ключа 6 поступает на вход генератора 5 тактовых импульсов.

O

5 0

5 п

s

5

импульсы с которого поступают на первые входы элементов И 23 ячеек 20, на вторые входы которых подаются сигналы с выходов элементов И 7, и если на выходе какого-либо элемента И 7 имеется 1, то тактовые импульсы с выхода элемента И 23 поступают на вычитающий вход счетчика 22. Одновременно импульсы с выхода элемента И 9 поступают на счетный вход счетчиков 31. Этот процесс продолжается до тех пор, пока на выходе одного из вычитающих счетчиков 22 j-ro столбца ячеек 20 не появится сигнал об- нулется, который поступит на S-вход RS-триггера 34у и переведет его в состояние 1. При этом соответствующий ключ 33 разомкнется и тактовые импульсы с генератора 5 тактовых импульсов перестанут поступать на соответствующий счетчик 31, в результате чего в нем будет записано число,

равное min С.. . Процесс определения i ей; J

минимальной величины С . в каждом столбце осуществляется аналогично.

После того, как во всех столбцах будет определено минимальное число, все триггеры 34 перейдут в состояние 1 и на выходе элемента И 21 появится сигнал логической единицы, который поступит на считывающие входы счетчиков 31 и вторые входы элементов И 25, на первые входы которых подается сигнал от соответствующего элемента И 7, и если элемент И 7 находится в состоянии 1, то сигнал логической единицы с выхода соответствующего элемента И 25 поступит на считывающий вход регистра 26,- .

Информация, записанная в счетчиках 31 и регистрах 26, поступает на сумматор 39 с целью определения величины, равной

(W)

Е

i€u;

с +

21 min Cj. , jeJ et

где ц| - вариант используемых изделий, определяемьй комбинацией 1 и О в счетчике 13. По сигналу элемента И 32 блок 28 сравнения выполняет сравнение величины f(w) и f .

Если f(cj) f , то сигнал с первого выхода блока 28 сравнения через разделительньй диод 38 поступает на выходы обнуления счетчиков 31 и тригrepoB 34, a также на считывающие входы регистров 21 и осуществляет за пись величин С- в соответствующие вычитающие счетчики 22, а также через элемент 12 задержки поступает на с-четный вхэд счетчика 13, в результате чего на выходе счетчика 13 образуется новая комбинация О и 1, соответствующая новому варианту Ш используемых изделий. Кроме того, сигнал с катода диода 38 поступает на R-вход триггера 19, устанавливая его в состояние О, прекращая при этом прохождение импульсов от генератора 5 через элемент И 9 и запрещая прохождение следующего варианта используемых изделий через элементы И 7 без его проверки на допустимость.

15

Если f(u) f, то сигнал с

вто25

30

рого выхода блока 28 сравнения поступает на вход записи регистра 14, в котором фиксируется комбинация изделий, соответ.ствующая общим затратам f (сх;) , а также через элемент 36 задержки поступает на считывающий вход регистра 30, с выхода которого число f (о;) поступает в регистр 29 и становится f для.последующих шагов решения. Одновременно сигнал с второго выхода блока 28 сравнения через разделительный диод 37 поступает на входы обнуления счетчиков 31,триггеров 34, а также на считывающие входы регистров 21.

Кроме того, сигнал с катода диода 37 поступает на R-вход триггера 19, устанавливая его в О, прекращая прохождение имп льсов от генератора 5 через элемент И 9 и закрывая элементы И 7, а сигнал с выхода диода 15 поступает на вход элемента 11 задержки, где задерживается на время, достаточное для определения количества типов изделий в новом варианте в сумматоре 4.

Если дпя некоторого варианта количество используемых типов изделий больше заданного, то появляется сигнал на первом выходе блока 8 сравнения, который через диод 16 поступит на. счетный вход счетчика 13, в результате чего на его выходах образуется новая комбинация О и 1. Далее весь процесс повторяется многократно до тех пор,, пока не будут перебраны все возможные комбинации используемьк изделий. После того.

д5

40

50

75456

как проанализирован последний вариант, на следующем шаге на выходе счетчика 13 появляется сигнал пере- цолнения, контакты ключа 6 размыкаются и решение задачи заканчивается. По окончании решения задачи в регистре 14 хранится оптимальное множество используемых изделий (У), а в JO регистре 29 - величина минимальных затрат, соответствующих этому множеству.

5

0

5

0

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

Устройство для решения оптимизационных задач стандартизации по авт.св. № 1501094, отлича ю- щ е е с я тем, что, с целью расширения функциональньк возможностей за счет варьирования ограничения на ко- личестБО. типов изделш {, в него дополнительно введены второй сумматор, второй блок сравнения, дополнительный регистр, дополнительньв триггер, дополнительная группа элементов И, дополнительный элемент Н, третий и четвертый разделительные диоды и четвертый элемент задержки, при этом выходы разрядов счетчика задания вари- aiiTOB соединены с соответствующими входами второго сумматора и с первыми входами элементов Н дополнительной группы, выходы дополнительного регистра и второго сумматора соединены с соответс вунидими информационными входами в-торог о блока сравнения, первьш выход которого соединен с S-входом дополнительного триггера, единичный выход которого соединен с вторыми входами элементов И дополнительной группь и с первым входом дополнительного элемента И, второй вход. которого соединен с выходом генератора .тактовьк импульсов, а выход - с 5 первыми входами элементов И ячеек блока задания затрат, выходы элементов И дополнительной группы соединены с вторыми входами элементов И соответствующих ячеек блока задания затрат и с информационными входами соответствующих разрядов третьего регистра, катоды первого и второго разделительных диодов блока выбора оптимального варианта соединены с R-BXO- дом дополнительного триггера, с выводом выключателя начального положения и через последовательно соединенные первый элемент задержки и третий разделительньй диод - со счетным

0

0

входом счетчика задания вариантов,задания вариантов, который через

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

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

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