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

сл

01

о

Изобретение относится к вычислительной технике и может быть использовано fisiii реьчения задач .оптимизации многомерных параметрических рядов Эти задачи возникают при необходи- ocти определения оптимального набора из исходного множества {1 1, 2,,., , тп) типов изделий, обладающих ограниченной взаимозаменяемостью по удовлетворению потребностей из заданного множества их видов 1 , 2,... .. ., п.

Математически одна из наиболее общих задач стандартизации - задача оптим11зации многомерных параметрических рядов-формулируется следующим образом:

Определить L I такое, что

f(c) (co)/a) /41, .

где

(ы) С° + X. minC,.. ;

-- je3 ieuJ

feuj о

С; - начальные затраты, связанные с использованием изде- i-ro типа и не зависящие от числа этих изделий; Cj- - нроизводственно-злссплуатадионные затраты на удовлет- ворение изделиями i-ro тина потребностей j-ro вида Цель изобретения - повышение точности работы устройства.

Функциональная схема устройства преде 1авлена на чертеже.

Устройство содержит блок 1 производств енно-экплуатационных затрат, блок 2 начальных затрат, блок 3 сумматоров, блок 4 управления,

Блок 1 производственно-эксллу- атациоиных затрат содержит матрицу ячее1 задан1 Я затрат 5.;, i 1 m, j 1 ,n и шунтлрую11и1х резисторов 6;, j 1 ,п. Ячейки 5 задания затрат предназначены для задания величин С - производственно-зксплуатационных затрат и каждая из них содержит ключ 7, задатчик 8, нагрузочный резистор 9 и диод 10.

Блок 2 начальных затрат содержит m ячеек задания начальных затрат П

,,,, w Ксшдая из которых предназначена для задания величины С, , i 1,m и содержит ключ 12 и задатчик 1 3,

Блок 4 управления предназначен дл задания варианта используемых изделий (JS 1), подани сигнала начала

5

0

5

о

решения, (определения наилучшего варианта о( S 1 и содержит счетчик 14 аналог(;-цмфровой преобразователь 15, схему 16 сравнения, триггеры 17 - 19, регистры 20 и 21, элемент И 22, злемент ИЛИ 23, элементы 24 и 25 задержки, вход 26 запуска устройства, транспарант 27.

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

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

Перед началом решения на шины питания подается напряжение и задатчика- ми 8 ячеек задания затрат 5; , i 1,m, j 1,п устанавливаются напряжения U- , пропорциональные величи- 5 нам С,, производственно-эксплуатационных затрат, а задатчиками 13 ячеек задания начальных затрат llj i- I ,m устанавливаются напр5шения, пропорциональные величинам С° начальных затрат.

Кроме того, счетчик 14, регистр 21 обнуляются, в регистр 20 записывается максимально-возможное двоичное число (111...1), триггеры 17 - 19 устанавливаются в состояние О.

Решение задачи начинается подачей кратковременного импульса на вход запуска устройства (продолжительность импульса должна быть меньше времени задержки импульса в элементе 25 задержки ). По данный импульс поступает на первый вход элемента ШШ 23, с выхода которого сигнал поступит на вход установки триггера 17, переводя его в состояние 1. С выхода триггера 17 сигнал поступает на вход элемента 25 задержки, где задерживается на время, необходимое для вычисления величины (ы) в блоке сумматоров, и на счетный вход счетчика 14, на выходах которого образуется двоич ная комбинация 000...01, т.е. задается вариант а; f включающий только изделия первого типа.

С выходов счетчика 14 двоичная комбинация 000...01 поступит на входы регистра 21 и на управляющие входы блоков 1 и 2, замыкая ключи 7 первой строки ячеек задания затрат 5 ,...,

0

5

0

5

...,5,, блока 1 и ключ 12 ячейки ll блока 2,

В блоке 1 производственно-эксплуатационных затрат для каждого из j 1,п столбцов ячеек задания затра 5,-j , i 1 ,m нагрузочные резисторы 9, диоды 10 ячеек столбца и резистор 6 образуют схему выбора минимального напряжения, на выходе которой всегда поддерживается напряжение, равное минимальному из напряжений на задат- чиках, подключенных ячеек столбца, т.е. на резисторах 6:, j 1,п всегда будет поддерживаться напряжение, пропорциональное min С;- , j 1,п,

i€(J

которое поступает на первые входы блока сумматоров, на вторые входы которого с подключенных ячеек задания затрат поступит напряжение, пpoпopL o нальное величинам С , ieu) .

В блоке 3 сумматоров определяется величина

Z

lELO

С

+ min , je J iew

которая поступает на вх1)д аналого- цифрового преобразователя 15.

После определения величины f(u) сигнал-, задержанный элементом 25 задержки, поступает на вход сброса триггера 17, переводя его в О - состояние и на вход установки триггера 18, единичный сигнал с выхода которого поступает на вход элемента 24 задержки, где задерживается на время, необходимое для завершения сравнения чисел в схеме 16 сравнения, на управляющий вход аналого-цифрового преобразователя 15, с выхода которого число, равное f (w) , поступает на первый вход схемы 16 сравнения и на вход регистра 20. Одновременно сигнал с выхода триггера 18 поступит на первый вход элемента И 22, на втором входе которого поддерживается сигнал логической единицы, с инверсного выхода триггера 19, который также поступает на вход считывания регистра 20, обеспечивая поступление числа f на второй вход схемы 16 сравнения.

Сигнал с выхода элемента К 22 поступает на управляющей вход схемы 16

5Q Далее весь описанный процесс повто ряется многократно до тех пор, пока не будут перебраны все возможные комбинации используемых изделий (при этом счетчик 14 каждый раз изменяет свое состояние на единицу и общее

сравнения, разрешая осуществить срав-сс

нение чисел f(ci;) и f , поданных на количество комбинаций равно 2 ). Пос10

поступит на вход установки триггера

19,переводя его в состояние I. При этом сигнал с инверсного выхода триггера 19 становится равным О, что закрывает элемент И 22, не разрешая осуществлять сравнение чисел, и запрещает считьшание числа f из регистра 20 в устройство 16 сравнения. Одновременно сигнал с выхода триггера 19 поступает на вход записи регистра

20,в который записьшается новое значение f f (о)), а также на вход записи регистра 21, в который записываетJ5 ся комбинация ы , давшая лучшее значение ffu)).

После осуществления этих операций сигнал, задержанный в элементе 24 задержки, поступает на входы сброса 20 триггеров 18 и 19, переводя их в состояние О. При этом сигнал с инверсного выхода триггера 19 разрешит подачу нового числа из регистра 20 на второй вход схемы 16 сравнения и на

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

В том случае, если f f(u)), то сигнала на выходе схемы 16 сравнения

30 нет и сигнал с выхода элемента 24 задержки переведет триггер 18 в состояние О, снимая управляющий сигнал

35

40

с аналого-цифрового преобразователя 15 и прекращая подачу числа f(co) на устройство 16 сравнения и регистр 20. И в первом и во втором случае сигнал с выхода элемента 24 задержки поступает так же на второй вход элемента ИЛИ 23 сигнал с выхода которогэ переводит триггер 17 в состояние 1, сигнал с выхода которого поступает иа счетный вход счетчика 14, на выходах которого образуется новая комбинация 000...10, что соответствует новому

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

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

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

его входы.

Если выполняется условие f(uf) f то сигнал с выхода схемы сравнения

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

сигнал переполнения, который поступи на транспарант 27, сигнализируя об окончании решения. При этом в регстре 21 хранится оптимальный вариант используемых изделий (о(«1) а в регистре 20 - величина минимальных затрат (f(o)), соответствующих этому варианту.

При этом задача решена точно, ибо просмотрены все возможные комбинации изделий.

При этом время решения задачи размерности (тчО может быть оценено величиной t реш 2(-У + 1)), где f, С 7. время задержки в элементах 24 и 25 задержки, т.е. не зависит от величины п, что существенно для задач большой размерности-.

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

Устройство для оптимизации многомерных параметрических рядов, содержащее блок производственно-эксплуа- 25 тационных затрат, блок сумматоров и блок управления, отличающее- с я тем, что, с целью повышения точности работы Устройства/- блок управления содержит устройство сравне-30 ния, аналого-цифровой преобразователь, первый, второй и третий триггеры, первый и второй регистры, первый и второй элементы задержки, элемент И, элемент ИЛИ, счетчик и транспарант,35 первый вывод которого заземлен, второй вывод подключен к выходу переполнения счетчика, выход которого поразрядно объединен с информационным входом второго регистра и являет-40 ся выходом блока управления, счетный вход счетчика соединен с выходом первого триггера и входом второго элемента задержки, выход которого соединен с входом сброса первого триггера и с 45 входом установки второго триггера, выход которого соединен с входом первого элемента задержки, первым входом элемента И и с управляющим входом аналого-цифрового преобразователя, , информационный вход которого является информационным входом блока управления, а выход соединен с первым входом схемы сравнения и с информационным входом первого регистра, вькод которого ,с соединен с вторым входом схемы сравнения, вход разрешения считывания первого регистра соединен с вторым входом элемента И и инверсным выходом

5

0

50 5 40 5 ,, ,с

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

91517044,0

выходом блока начальных затрат и со-чальных затрат образ тот входы блика

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