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

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

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

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

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

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

того, блок 2 содержит, группу элементов И 15i - 15m. группу регистров 16i - 16п1(шины задания начальных затрат не показаны). Блок 3 содержит блок 17 сравнения, группу блоков 18i - 18п сравнения, первый 19 и второй 20 регистры, группу регистров 21i - 21 п, группу счетчиков 22i - 22п, первую группу ключей 23i - 23п, первый элемент И 24, шестой элемент И 25, четвертый 26 и пят-ый 27 элементы И, второй 28 и третий 29 элементы И, группу триггеров 30i-30n, триггер 31, элемент ИЛИ 32, сумматор 33, третью и вторую группы ключей 34i - 34п, 35i - 35п. четвертый 36, третий 37 и второй 38 элементы задержки, третий 39, второй 40 и первый 41 разделительные диоды, шины 42 л 43 задания типа решаемой задачи, третий регистр 44.

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

Ю

hO Ю

Сл)

Ю

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

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

f(a)Finin{f(oj)lu)ci}, где

2 СР + mInCij, если решается задача первого типа

1сШ IcJ .leCO

ЕСР.

Icrt)

если решается задача второго типа

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

mInCij bj, j J ,

leOJ

где - начальнь1е затраты, связанные с использованием изделий i-ro тмпа и не зависящие от числа этих изделий:

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

bj - максимально допустимые затраты на выполнение J-ro вида работ.

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

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

Счетчик 6 и регистр 44 обнуляются, а в регистр 13 каждой ячейки 10tj(l 1,т; j 1,п) записывается число Cij, равное производственно-эксплуатационным затратам при вы- полнении i-й работы j-м типом изделий, В регистры 1б| записываются числа, равные величинам начальных затрат Ci° на разработку и производство 1-го типа изделий. Если количество анализируемых изделий mi m, то в регистры с номерами записываются максимально возможные числа. В регистр 20 также записывается максимально возможное число (111...11), В случае, когда решается второй тип задач, в

5

0

5

0

5

0

5 0 5

0 5

регистры 21 записываются числа bj, равные максимально допустимым затратам на выполнение j-ro вида работ (если решается первый тип задач, то регистры 21 обнулены).

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

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

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

После того, как во всех столбцах будет определено минимальное число Cij, все триггеры 30i - ЗОп перейдут в единичное состояние и на выходе элемента И 24 появится сигнал 1, поступающий далее на считывающие входы счетчиков 221 - 22п, на первые входы элементов И 28 и 29 и на первые входы элементов И 15, на вторые входы которых подается сигнал с соответствующего разряда счетчика 6, и, если 1-й разряд счетчика 6 установлен в единичное

ствующего разряда счзтчика 6, и, если 1-й разряд счетчика 6 установлен в единичное состояние, то сигнал с выхода соответствующего элемента И 15i поступает на считывающий вход регистра 16|, обеспечивая поступление записанной в них информации на входы сумматора 33. При этом на выходе сумматора 33 формируется величина, соответствующая задаче первого типа, причем вариант используемых изделий определяет- -ся комбинацией О и 1 в счетчике 6, которая записывается в регистр 19 и поступает на второй вход блока 17 сравнения, на первый вход которого подается величина, равная f минимальному значению f(ft) ) из ранее просмотренных вариантов и записанная в регистр 20 (при первом сравнении в регистре 20 находится максимально возможное число 111... 111). Единичный сигнал с выхода элемента И 24 (только в том случае, когда все триггеры 301 - ЗОп установлены в состояние 1) поступает на первые входы элементов И 28 и 29, а так как триггер 31 находится в единичном состоянии, то и на втором входе элемента ИЛИ 32 также будет поддерживаться единичное напряжение.

Сигнал с выхода элемента ИЛИ 32, задержанный элементом 37 задержки на вре- мя, необходимое для выполнения суммирования в сумматоре 33, поступает на управляющий вход блока 17 сравнения, в результате чего в нем выполняется операция сравнения величин f(rt)) и f .

Если f((y) f , то сигнал с первого выхода блока 17 сравнения через диод 41 поступает на входы обнуления счетчиков 22i - 22п и R-входы триггеров 30i - ЗОп, на считывающие входы регистров 13, осуществляя запись величин Cij в соответствующие вычитающие счетчики 14. а также на вход элемента 7 задержки, с выхода которого сигнал поступает на счетный вход счетчика 6. обеспечивая образование новой комбинации О и 1.

Если f(ft ) f , то сигнал с второго выхода блока 17 сравнения поступает на вход записи регистра 19, в котором фиксируется комбинация изделий, а также на вход элемента 38 задержки, с выхода которого сигнал поступает на считывающий вход регистра 19, с выхода которого значение f( ш) поступает в регистр 20. Одновременно сигнал с второго выхода блока 17 сравнения через разделительный диод 40 поступает на .входы обнуления счетчиков 22, на R-входы триггеров 30, на считывакг.щие входы регистров 13 и осуществляет запись величин Cij в соответствующие вычитающие счетчики 14, а также на вход элемента 7 задержки, с

4

50

55

выхода которого сигнал поступает на счетный вход счетчика 6, в результате чего на выходе последнего образуется новая комбинация О и Г, соответствующая новому 5 варианту используемых изделий.

Если решается задача второго типа, то на предварительном этапе подается напряжение на вход 42, которое устанавливает триггер 31 в состояние О. При этом единич- 10 ный сигнал с инверсного выхода триггера 31 поступает на второй вход элемента И 29 и на управляющие входы ключей 34, замыкая их контакты.

После запуска работа устройства 15 вплоть до определения величин min

eU)

j-ro столбца происходит аналогично рассмотренному выше.

После того, как во всех столбцах будет 20 определено минимальное число Cij, все триггеры 30 перейдут в состояние 1 и на выходе элемента И 24 появится сигнал логической единицы, который поступит на считывающие входы счетчиков 22, первые

5 входы элементов И 28 и 29 и вторые вхоДы элементов И 15, на первые входы которых подается сигнал с соответствующего 1-го разряда счетчика б, и если в 1-м разряде счетчика установлена Г, то сигнал с выхо0 Д.з элемента И 15i поступает на считывающий вход регистра 16i, обеспечивая считывание записанной в нем информации

на соответствующий вход сумматора 33, на первых п входах которого поддерживается

5 сигнал логического О (ключи 35 разомкнуты). Полученное в сумматоре 33 число, равное

Н-2СР,

i о й

поступает на вход регистра 19 и на первый вход блока 17 сравнения, на второй вход которого поступает величина f , рассчитанная на предыдущих шагах решения и запи- санная в регистр 20. Одновременно

информация со счетчиков 22 (числа minCij)

ieO)

через замкнутые контакты ключей 34 посту- пает на первые входы соответствующих блоков 18 сравнения, на вторые входы которых с выходов соответствующих регистров 21 подаются числа bj.

Сигнал с выхода элемента И 29 поступает нз з;:оды разрешения операций сравнения блоков 18 сравнения, а также на вход

элемента 36 задержки, где задерживается на врегуя, достаточное для завершения операций сравнения в блоках сравнения. При этом, если выполняется условие minCij bj, то на выходе соответствующе О блока 18 сравнения появится сигнал ло- .

гической единицы, который поступит на вход элемента И 25. Если условие выполняется для всех столбцов, то на выходах всех блоков 18 сравнения будут сигналы единичного уровня, которые вызовут срабатывание элемента И 25. единичный сигнал с выхода которого поступит на инверсный вход элемента И 26 и на второй вход элемента И 27.

G выхода элемента И 27 сигнал через элемент ИЛИ 32 поступит на вход элемента 37 задержки, с выхода которого сигнал подается на вход разрешения операции сравнения блока П.сравнения.

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

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

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

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

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

0 целью расширения функциональных возможностей за счет учета ограничения затрат на выполнение различных видов работ, в блок выбора оптимального варианта введены вторая и третья группы из п ключей каж5 дая, группа из п регистров, группа из п блоков сравнения, с второго по шестой элементы И, элемент ИЛИ, четвертый элемент задержки, третий разделительный диод и. триггер, при это1М выходы каждого j-ro счет0 чика группы О 1.п) через соответствующий ключ второй группы соединен с соответствующим входом сумматора и через соответствующий ключ третьей группы - с первым входом соответствующего блока сравнения

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

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

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