УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Советский патент 1973 года по МПК G06G7/122 

1

Предложенное устройство относится к области аналоговой вычислительной техники.

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

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

Это позволяет повысить быстродействие устройства.

На чертеже показана блок-схема предложенного устройства.

Устройство содержит интеграторы 1, 2 и 3, предназначенные для изменения переменных, блок 4 ограничений, который определяет значения функций ограничений, блок 5 управления, формирующий основные управляющие воздействия, блок 6 перекрестных связей, вы9

числяющий коэффпциенпгы перекрестных связей, вспомогательный блок 7 управления для формирования вспомогательных управляющих воздействий, блок 8 логики, который определяет Н1а 1меньщее нз значений функций ограничений, инвертирует его и производит переключения в схемах блока управления, блока перекрестных связей и вспомогательного блока управления, реле 9 с нормально замкнутыми контактами 10, 11 и 12 для подачи вспомогательных управляющих воздействий на входы интеграторов.

Выходы интеграторов подключены к входам блока ограничений, выходы которого соединены с входами блока логики. Выход блока логики подключен к входу блока управления и к обмотке реле 9. Блок логики содержит релейные элементы (на чертеже не показаны), переключающие контакты которых включены в схемы основного блока 5 управления, блока перекрестных связей и вспомогательного блока 7 управления. Выходы основного блока 5 управления подключены к входам соответствующих интеграторов. Выход блока перекрестных связей соединен с входом вспомогательного блока зправления, выходы которого через нормально замкнутые контакты реле 9 подключены к входал интеграторов.

Устройство предназначено для определения значений переменных Xi(,2,.. .п), при которых целевая функция

F(X) 2 (1)

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

g,(X) S bjiX, + bj, :5 о, / 1,2, ... , m. (2)

I t

Ограничения выражения (2) определяют допустимую область изменения переменных Xi. Точка решения задачи линейного программирования Н1аходится на границе допустимой области.

Уравнение границы допустимой области представим в виде

h(X) 0.(3)

Значение функции h(X) в любой точке пространства переменных, не принадлежащей границе (3), рассматриваем как «расстояние от этой точки до границы (3). Это «расстояние h представляет собой наименьщее (алгебраически) из значений функций ограничений gi(X) в рассматриваемой точке

/I -мин:{ у1.(4)

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

V, Х,.- hh, + т 2 Ci,h,, е i, (5)

e I

где Си - коэффициенты перекрестных связей,

(Plhe-fA}с Р ,8/1

1 При /I (С-)

при

В выражении (6) знак «+ соответствует поиску максимума целевой функции, а «- поиску минимума. Выражение (5) можно представить в следующем виде

VI XI YI + I/;,

где Кг -hhi-- управляющее воздействие; вырабатываемое основным блоком управления;

г/

Vi Ciehe - управляющее воздействие,

вырабатываемое вспомогательным блоком управления.

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

ограничений (2). При этом , у 0 и устройство приводит переменные к соотнощению (3). Вторая структура работает в том случае, когда значения переменных удовлетворяют системе ограничений (2). При этом и устройство изменяет переменные так, чтобы выполнять условие (3) и одновременно увеличивать (или уменьшать) целевую функцию. Когда переменные достигают значений, соответствующих условию (3), дальнейщее их изменение происходит в направлении оптимизации целевой функции при поддержании между ними соотношения (3).

Пусть, например, начальные значения переменных на выходах интеграторов таковы, что значение первой функции ограничений отрицательно, а остальных двух положительны. Напряжения с выходов интеграторов подают на входы блока ограничений. Па выходе этого блока напряжение, равное значению первой функции ограничений, отрицательно, а два остальных напряжения положительны. Эти напряжения с выходов блока ограничений подают на входы блока логики. Па выходе блока логики ползчают напряжение, равное значению первой функции ограничений с обратным знаком, так как в рассматриваемом случае это напряжение является наименьшим (алгебраически).

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

Папряжение с выхода блока логики подают также ва обмотку реле 9. Так как в рассматриваемом случае это напряжение цоложительно, то реле 9 размыкает свои нормально замкнутые контакты 10, 11 и 12, отключая входы интеграторов 1, 2 } 3 от выходов вспомогательного блока управления, на входы которого подают напряжения с выходов блока

перекрестных связей.

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

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

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

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

Управляющие напряжения основного блока управления обеспечивают такое изменение переменных, в результате которого значение третьей функции ограничений снова становится равным нулю. Реле 9 управления замыкает контакты 10, 11 и 12, и переменные на выходах интеграторов изменяют в ;:1ап11авле НИИ увеличения значение целевой функции

при гохраненпи значения третьей функции огjaHi-.4eun,i, равного нулю.

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

Предмет изобретения

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