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

 

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

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

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

РЕСПУБЛИК (я)з 6 06 G 7/122

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1501094 (21) 4615687/24-24 (22) 06.12,88 (46) 07.12.90. Бюл. ¹ 45 (72) О.Г.Алексеев, В.А.Буслаев, С.А.Васильковский и Н.И.Ячкула (53) 681,3 (088.8) (56) Авторское свидетельство СССР

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

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

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

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

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

Блок 2 содержит ячейки 10 (m групп по и ячеек в каждой группе), каждая ячейка содержит шину 11 задания производственно-эксплуатационных затрат, элемент И 12, регистр 13, вычитающий счетчик 14. Кроме. БЦ.«, 1612293 А2 учета ограничения затрат на выполнение различных видов работ. Устройство содержит шину опорного напряжения, блок задания затрат, блок выбора оптимального варианта, ключ управления, генератор тактовых импульсов, счетчик задания вариантов, элементы задержки, выключатель установки исходного состояния, выключатель запуска.

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

151 — 15, группу регистров 161 — 16п, (шины задания начальных затрат не показаны).

Блок 3 содержит блок 17 сравнения, группу блоков 181 — 18П сравнения, первый 19 и второй 20 регистры, группу регистров 211—

21л, группу счетчиков 221 — 22л, первую группу ключей 23> — 23л, первый элемент И 24, шестой элемент И 25, четвертый 26 и пятый

27 элементы И, второй 28 и третий 29 элементы И, группу триггеров 301 — 30П, триггер

31, элемент ИЛИ 32, сумматор 33, третью и вторую груп и ы ключей 341 — 34л, 351 — 35п. четвертый 36, третий 37 и второй 38 элементы задержки, третий 39, второй 40 и первый, 41 разделительные диоды, шины 42 4 43 задания типа решаемой задачи, третий регистр 44.

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

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

Математически задача формулируется следующим образом, Необходимо опреде- 5 лить a c l такое, что

f(a) =, min(1(м)1ас i), где

, CI +, mlnc>, если решается аадача первого типа

IcOJ IcJ, е(0, Р сР если решаетсл аадвча второго типа иГл

,т(м) = при ограничении на максимально допустимые затраты (потребности), необходимые для выполнения работ(только для задач второго типа) 20

minCIi = bi, j C J, 1 ею где С вЂ” начальные затраты, связанные с использованием изделий i-ro типа и не зависящие от числа этих изделий; 25

Cii — производственно-эксплуатационные затраты на удовлетворение изделиями

i-го типа потребностей, связанных с выпол. нением j-ro вида работ;

bi — максимально допустимые затраты 30 на выполнение j-го вида работ, Устройство работает следующим образом.

Перед началом решения подачей единичного напряжения на одну из шин 42 или 35

43 определяется тип решаемой задачи, Если напряжение подано на шину 43, то триггер 31 установится в состояние "1" и сигнал с его прямого выхода поступит на управляющие входы ключей 35> — 35п и на второй 40 вход элемента И 28. Если напряжение подано на шину 42, то триггер 31 установится в нулевое состояние и сигнал с его инверс-. ного выхода поступит. на управляющие входы ключей 34> — 34, замыкая их контакты, 45 и на второй вход элемента И 29.

Счетчик 6 и регистр 44 обнуляются, а в регистр 13 каждой ячейки 10л (! = 1,m; j = 1, и) записывается число Сл, равное производственно-эксплуатационным затратам при вы- 50 полнении i-й работы J-м типом изделий, B регистры 16 записываются числа, равные величинам начальных затрат С на разработку и производство i-ro типа изделий. Если количество анализируемых изделий 55 т1< m, то в регистры с номерами i m< записываются максимально возможные числа. В регистр 20 также записывается максимально возможное число (111...11). В случае, когда решается второй тип задач, в регистры 21 записываются числа bi, равные максимально допустимым затратам на выполнение )-го вида работ (если решается первый тип задач, то регистры 21 обнулены).

Решение задачи начинается кратковременным включением выключателя 8 установки начального состояния, в результате чего напряжение от опорного источника питания поступает на считывающие входы регистров 13 ячеек 10 и осуществляет перезапись содержащегося в них числа в вычитающие счетчики 14, а также на входы обнуления счетчиков 22, на R-входы триггеров 30, переводя их в состояние "0", и, кроме того, на вход элемента 7 задержки, с выхода которого через время задержки, необходи.мое для завершения всех переходных процессов, сигнал поступает на счетный вход счетчика 6, на выходе которого образуется комбинация 000„,1, т,е. множество (с = 11) включает только первый тип изделий. На этом этап предварительной настройки устройства заканчивается.

При замыкании выключателя 9 запуска опорное напряжение подается на информационный вход ключа 4 и через его замкнутые контакты поступает на вход генератора 5 тактовых импульсов, импульсы с которого поступают на первые входы элементов И 12 ячеек 10», на вторых входах которых поддер-. живается сигнал, определяемый выходной комбинацией счетчика 6.

Одновременно импульсы от генератора

5 тактовых импульсов поступают на входы ключей 23 и через них — на счетные входы счетчиков 22. Этот процесс продолжается до тех пор, пока на выходе одного из вычитающих счетчиков 14 j-ro толбца ячеек 10 не появится сигнал обнуления счетчика, который поступит на $-вход соответствующего RS-триггера 30, переводя их в состояние

"1". Сигнал с прямого выхода триггера 30 закрывает соответствующий ключ, в результате чего в счетчике 22 будет записано число, равное minCii. Процесс определения минимальной величины Cii в каждом столбце осуществляется аналогично описанному, После того, как во всех столбцах будет .определено минимальное число С 1, все триггеры 301 — 30п перейдут в единичное состояние и на выходе элемента И 24 появится сигнал "1", поступающий далее на считывающие входы счетчиков 221 — 22n, на первые входы элементов И 28 и 29 и на первые входы элементов И 15, на вторые входы которых подается сигнал с соответствующего разряда счетчика 6, и, если I-й разряд счетчика 6 установлен в единичное

1612293 ствующего разряда счетчика 6, и, если 1-й выхода которого сигнал поступает на счетразряд счетчика 6 установлен в единичное ный вход счетчика 6, в результате чего на состояние, то сигнал с выхода соответству- выходе последнего образуется новая комющего элемента И 15 поступает на считы- бинация "0" и "1" соо, соответствующая новому вающий вход регистра 16, обеспечивая 5 варианту используемых изделий. поступление записанной в них информации Если решается задача второго типа, то на входы сумматора 33. При этом на выходе на предварительном этапе подается напрясумматора 33 формируется величина, соот- жение на вход 42, которое устанавливает ветствующая задаче первого типа, причем триггер31 всостояние "0". Приэтомединичвариант используемых изделий определяет- 10 ный сигнал с инверсного выхода триггера 31 ся комбинацией "0" и "1" в счетчике 6, кото- поступает на второй вход элемента И 29 и рая записывается в регистр 19 и поступает на управляющие входы ключей 34, замыкая, на второй вход блока 17 сравнения, на пер- их контакты. вый вход которого подается величина, рав- После запуска рабо ра ота устройства ная 1* минимальному значению f(N ) из 15 вплоть до определения величин т1п C для ранее просмотренных вариантов и записанная в регистр 20 (при первом сравнении в /-го столбца происходит аналогично расрегистре 20 находится максимально воз- смотренному выше. можное число 111„.111), Единичный сигнал После того, как во всех столбцах будет свыходаэлементаИ24(только втомслучае, 20 о ределено минимальное число С, все когда все триггеры 301 — 30„установлены в триггеры 30 перейдут в состояние "1" и на состояние "1") поступает на первые входы выходе элемента И 24 появится сигнал логизлементов И 28 и 29, а так как триггер 31 ческой единицы, который поступит на счинаходится в единичном состоянии, то и на тывающие входы счетчиков 22, первые втором входе элемента ИЛИ 32 также будет 25 входы элементов И 28 и 29 и вторые вхоДы поддерживаться единичное напряжение. элементов И 15, на первые входы которых

Сигнал с выхода элемента ИЛИ 32, за- подается сигнал с соответствующего l-ro держанный элементом 37 задержки на вре- Разряда счетчика 6, и если в I-м разряде мя, необходимое для выполнения счетчика установлена "1", то сигнал с выхосуммирования в сумматоре 33, поступает на 30 дз элемента И 15 поступает на считываюуправляющий вход блока 17 сравнения, в q вход Регистра 16ь обеспечивая результате чего в нем выполняется опера- -,÷è ывание записанной в нем информации ция сравнения величин 1((д) и 1*. на соответствующий вход сумматора 33, на

Если (м ) >f* то сигнал с первого пеРв --х и входах KOTQPoro поддерживаетсЯ выхода блока 17 сравнения через диод 41 35 си-нал логического "0" (ключи 35 РазомкнУ поступает на входы обнуления счетчиков ты). Полученное в сумматоре 33 число, рав221 — 22 и R-входы триггеров 301 — 30,, на считывающие входы регистров 13, осущест- 1(ы) =- Х CI, вляя запись величин Сл в соответствующие вычитающие счетчики 14, а также на вход 40 поступает на вход регистра lg и на первый элемента .7 задержки, с выхода которого вход блока 17 сравнения, на второй вход сигнал поступает на счетный вход счетчика которого поступает величина f*, рассчитан, обеспечивая образование новой комби- ная на предыдущих аг нации "0" и "1". их шагах решения и записанная в регистр 20. Одновременно

Если f(m ) < f* то (), сигнал с второго 45 информация со счетчиков 22 (числа пппСл) выхода блока 17 сравнения поступает на вход записи регистра 19, в котором фикси- чеРез замкнУтые контакты ключей 34 постУруется комбинация изделии, а также на вход пает на первые входы соответствующихблоэлемента 38 задержки, с выхода которого «в18сравнениЯ, на втоРые входы котоРых сигнал поступает на считывающий вход ре- 50 с выходов соответствующих регистров 21 гистра 19, с выхода которого значение f(cu) подаю гсЯ числа bl поступает в регистр 20. Одновременно сиг- Си нал с выхода элемента И 29 поступанал с второго выхода блока 17 сравнения через разделительный диод 40 поступает на Н« ""«ов " сравнения а такЖе» вход .входы обнуления счетчиков,".2, на р-входы 55 элемента 36 задеРжки, где задерживается триггеров 30, на считывающие входы реги- на вРекЯ, достаточное длЯ завеРшениЯ опестров13 иосуществляетза ись величин Ctl Раций сравнениЯ в блоках сравнениЯ. При в соответствующие вычитагощ е счетчики этом, если ыполн е ся условие

14, а также на вход элемента 7 задержки, с пнпС .Я Ь . то на выходе соответствующего блока 18 сравнения появится сигнал ло1612293 гической единицы, который поступит на вход элемента И 25. Если условие выполняется для всех столбцов, то на выходах всех блоков 18 сравнения будут сигналы единич. ного уровня, которые вызовут срабатывание элемента И 25, единичный сигнал с выхода которого поступит на инверсный вход элемента И 26 и на второй вход элемента И 27.

С выхода элемента И 27 сигнал через элемент ИЛИ 32 поступит на вход элемента

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

В том случае, если хотя бы для одного столбца условие minCi Ь не выполняется;.то сигнала на выходе соответствующего блока 18 сравнения и элемента И 25 не будет. Одновременно сигнал, задержанный элементом 36 задержки, поступает на первые входы элементов И 26 и 27. Так как на втором входе элемента И 27 поддерживается сигнал "0", то и на выходе данного элемента сигнал также отсутствует, а так как на выходе элемента И 28 поддерживается сигнал логического нуля, то на управляющий вход блока сравнения импульс не поступает. С выхода элемента И 26 единичный сигнал поступает на анод разделительного диода 39 и далее с катода — на входы обнуления счетчиков 2, входы триггеров 30, на считывающие входы регистров 13, а также на вход элемента 7 задержки, с выхода ко-! торого сигнал поступает на счетный вход счетчика 6, в результате чего на его выходе образуется новая комбинация "0" и "1", соответствующая новому варианту используемых типов изделий.

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

30 го и третьего элементов И, вторые входы которых подключены к выходу первого we35 мента И, выход второго элемента И соединен

50 ство типов используемых изделий, а в регистре 20 — величина минимальных затрат, соответствующих этому множеству, Формула изобретения

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

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

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

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

Техред M,Ìîðã"íòàë Корректор А.Обручар

Редактор Н.Тупица

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

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

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

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