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

 

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

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

РЕСПУБЛИК

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

К А BTOPCKOMY СВИДЕТЕЛЬСТВУ

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

fl0 ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

flPH ГКНТ СССР (61) 1501094 (21) 4466773/24-24 (22) 11. 05.88

; (46) 23.08.90. Бюл. У 31 . (72) О.Г.Алексеев, В.А.Буслаев, С.А.Васипьновский и Н.И.Ячкула (53) 681.3(088."8) (56) Авторское свидетельство СССР

К - 1501094, кл, G 06 G 7/122, 1987. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СТАНДАРТИЗАЦИИ (57) Изобретение относится к вычисИзобретение относится к вычислительной технике и является усовершенствованием изобретения по авт.св.

Р 1501094.

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

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

Устройство содержит шину 1 питания, блок 2 задания затрат, блок 3 выбора оптимального варианта, второй сумматор 4, генератор 5 тактовых импульсов, ключ 6, элементы И 7, — 7 дополнительной группы, второй блок 8 сравнения, дополнительный элемент

И 9, дополнительный регистр 10, четвертый элемент 11 задержки, третий элемент 12 задержки, счетчик 13 задания вариантов, третий регистр 14, третий и четвертый диоды 15 и 16, выклю„.SUÄÄ 1587545 А 2 (gl)g С 06 G 7/122

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

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

20 ячеек, каждая из которых состоит 2 из регистра 21, вычитающего счетчика

22, элемента И 23 и шины 24 задания эксплуатационных затрат; группу элементов И 25, — 25„„, группу регистров 26, — 26, шины 27, — 27 задания в начальных затрат. Блок 3 содержит первый блок 28 сравнения, первый 29 и второй 30 регистры, группу счетчиков

31, — 31„„элемент И 32, ключи 33

33, триггеры 34, — 34, первый и второй элементы 35 и 36 задержки, первый и второй разделительные диоды 37 и 38, первый сумматор 39.

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

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

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

Перед началом решения счетчик 13 обнуляется, в регистр 21 каждой ячейки

20 записьвается число, равное произЪ водственно-эксплуатационным затратам при выполнении j-й работы -м типом изделия С;

В регистры 26 записьваются числа, равные величинам начальных затрат С; на раз работку и произв одс тв î i-ro ти- 15 па изделий. Если количество анализируемых изделий m (m, то в регистры

1 с номерами i (m записываются максимально возможные числа. В регистре

29 записьвается максимально возможное 2р число (111 .... 11), а в регистр 10— число К, равное максимально допустимому к олич е ству типов из де лий .

Решение задачи начинается кратковременным включением выключателя 17, 25 в результате чего напряжение от опорного источника питания поступает на считывающие входы регистров 2 1 ячеек 20 и осуществляет запись содержащегося в них числа в вычитающие счет- 30 чики 22, а также обнуляет счетчики

31, триггеров 34 и триггеры 19.

Кроме того, напряжение от источника опорного питания поступает на вход элемента 12 задержки, с выхода

35 которого через время задержки,достаточное для завершения всех переходных процессов, через диод 15 поступает на счетный вход счетчика 13,на выходе которого образуется комбина- 4 ция 000,.01 (только первый тип изделий), а также на вход элемента 11 задержки, где сигнал задерживается на время, достаточное для осуществления. суммирования в сумматоре 4.

С выхода сумматора 4 число M равное количеству используемых типов изде, лий, поступает на второй вход блока

8 сравнения, на первый вход которого из регистра 10 подается число 4, равное максимально допустимому числу изделий. При М (К триггер 19 открывает элементы И 7 и 9.

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

При замыкании выключателя 18 запу55 ска опорное напряжение через замкнутые контакты ключа 6 поступает на вход генератора 5 тактовых импульсов, импульсы с которого поступают на первые входы элементов И 23 ячеек 20, на вторые входы которых подаются сигналы с выходов элементов И 7, и если на выходе какого-либо элемента И 7 имеется "1", то тактовые импульсы с выхода элемента И 23 поступают на вычитающий вход счетчика 22. Одновременно импульсы с выхода элемента И

9 поступают на счетный вход счетчиков 31. Этот процесс продолжается до тех пор, пока на выходе одного из вычитающих счетчиков 22 j-го столбца ячеек 20 не появится сигнал обнулется, который поступит на S-вход

RS-триггера 34 и переведет его в со3 стояние 1 . При этом соответствующий ключ 33 разомкнется и тактовые импульсы с генератора 5 тактовых импульсов перестанут поступать на соответствующий счетчик 31, в результате чего в нем будет записано число, равное min С,, ° Процесс определения

1еы Ч минимальной величины С .. в каждом

ij столбце осуществляется аналогично.

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

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

f (у) = > С. + Q min C,"

|ей где,à — вариант используемых изделий, определяемый комбинацией "1" и "0" в счетчике 13. По сигналу элемента И 32 блок 28 сравнения выполняет сравнение величины f(w) и f ", Если f(u)) 7 f,,то сигнал с перI I вого выхода блока 28 сравнения через разделительный диод 38 поступает на выходы обнуления счетчиков 31 и триг1587545

1О

I5

2S

40 героя 34, а также на считывающие входы регистров 21 и осуществляет запись величин С в соответствующие

tJ вычитающие счетчики 22, а также через элемент 12 задержки поступает на счетный вход счетчика 13, в результате чего на выходе счетчика 13 образуется новая комбинация "0" и

tt It

1, соответствующая новому варианту используемых иэделий. Кроме того сигнал с катода диода 38 поступает на R-вход триггера 19, устанавливая его в состояние "Ott, прекращая при этом прохождение импульсов от генератора 5 через элемент И 9 и запрещая прохождение следующего варианта используемых изделий через элементы И 7 без его проверки на допустимость °

Если f (у) (f, то сигнал с второго выхода блока 28 сравнения поступает на вход записи регистра 14, в котором фиксируется комбинация изделий, соответствующая общим затратам

Е(Ы), а также через элемент 36 задержки поступает на считывающий вход регистра 30, с выхода которого число

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

Кроме того, сигнал с катода диода 37 поступает на R-вход триггера

19, устанавливая его в "0", прекращая прохождение импульсов от генератора 5 через элемент И 9 и закрывая элементы И 7, а сигнал с выхода диода 15 поступает на вход элемента

11 задержки, где задерживается на время, достаточное для определения количества типов изделий в новом варианте в сумматоре 4.

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

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

По окончании решения задачи в регистре 14 хранится оптимальное множество используемых изделий Q), а в регистре 29 — величина минимапьных затрат, соответствующих этому множеству.

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

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

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

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

ВТоРоА 8MxoP BToporo блока сравнения четвертый элемент задеру <и через четвертый разделительный диод с синхронизирукщим входом второго блосоединен со счетным входом счетчика ка сравнения.

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

Редактор С.Патрушева Техред А.Кравчук Корректор g qерни

Заказ 2422 Тираж 562 Подписное

ВНИИПИ

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина, 101