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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авг. свндетсльства ¹

Ч. Кл. 6 06д 7 34

Заявлено ОЗ.V.1971 (№ 1653240/18-24) с присоединением з",ë",;Iû №

Комитет по делам изобретений и открытий при Совете Министров

СССР

Приоритет

Опубликовано 23,V.1973. Бюллетень .й 24

Дата опубликования описания 8Х111.1973

УДК 681.334(088.8) Авторы изобретения

Ю. В. Костенко и Л. М. Бойчук

Институт кибернетики АН Украинской ССР

Заявитель

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

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

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

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

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

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

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

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

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

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

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

384107 (4) где

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

Е(Х) = g atÕ, (1)

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

gt(Х)= gb,,Õ.+b,,- О, !=1,2,..., m. (2)

Ограничения выражения (2) определяют допустимую область изменения переменных Х;.

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

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

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

h представляет собой наименьшее (алгебраически) из значений функцпй ограничений я;(Х) в рассматриваемой точке

h = мин.(g>).

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

Vt = Л; =- — hh,. + y g с,Й„е + i, (5) е — I где Сч — коэффициенты перекрестных связей, ct + (Fthe — Р,Й,);

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

V,=Х,=1";+Vt, Vt — — — ЙЙ, — управляющее воздействие; вырабатываемое основным блоком управления;

fl и

Vt =, Ct Й вЂ” управляющее воздействие, e=I вырабатываемое вспомогательн ым блоком управления.

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

15 г0 г5

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

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

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

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

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

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

384107

Предмет из обрсте:1ця

Г

1 Г

Составитель И. Калмыков

Редактор Т. Рыбалова Техред Е. Борисова Корректор Е. Зимина

Заказ 2187/16 Изд. М 1632 Тираня 547 Подписное

ЦЕ11111П1! Комитета по делам изобретений и открытии прп Совете MIIIIIicTpoB СССР

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

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

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

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

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

Таким образом, в устройстве возникает режим переключений, при котором переменные

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

Еоорд,.н аты этого пересечения определяют

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

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

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

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