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

Номер патента: 384107

Автор: Авторы

ZIP архив

Текст

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ исимое от авг. свидетельства Ст Обд 73 0(1 Заявлено ОЗ,У.1971 ( 1653 4) с присоединением заявки ЪПриоритет Комитет по делам изобретений и открытийУДК 681,334(088.8 убликовано 23,7.1973. Бюллете о 24 ри Совете Министров СССРта опубликования описания 8 Х 111.1973 Авторыизобретени В. Костенко и Л. М. Бойчук Институт кибернетики АН Украинской СС Заявите НЕЙНО РОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДА ПРОГРАММИРОВАН И Предложенное устройство относится к области аналоговой вычислительной техники.Извество устройство для решения задач линейного программирования, содержащее интеграторы, входы которых присоединены к выходу блока управления, а выходы через блок ограничений и блок логики подключены к входам блока управления.Предложенное устройство отличается тем, что оно содержит блок перекрестных связей, с подключенным к нему вспомогательным блоком управления и реле, нормально замкнутые контакты которого включены между выходами вспомогательного блока и вторыми входами интеграторов, а обмотка подключена к одному из выходов блока логики, подключенного остальными выходами к входам вспомогательного блока управления и к входам блока перекрестных связей.Это позволяет повысить быстродействие устройства.На чертеже показана блок-схема предложенного устройства.Устройство содержит интеграторы 1, 2 и 8, предназначенные для изменения переменных, блок 4 ограничений, который определяет значения функций ограничений, блок б управления, формирующий основные управляющие воздействия, блок б перекрестных связей, вычисляющий коэффпциенп ы перекрестных связей, вспомогательный блок 7 управления для формирования вспомогательных управляющих воздействий, блок 8 логики, который оп ределяет наименьшее из значений функцийограничений, инвертирует его и производит переключения в схемах блока управления, блока перекрестных связей и вспомогательного блока управления, реле 9 с нормально 10 замкнутыми контактамп 10, 11 и 12 для подачи вспомогательных управляющих воздействий на входы интеграторов.Выходы интеграторов подключены к входам блока ограничешш, выходы которого сое динены с входами блока логики. Выход блока логики подключен к входу блока управления и к обмотке реле 9, Блок логики содержит релейные элементы (на чертеже не показаны), переключающие контакты которых 20 включены в схемы основного блока 5 управления, блока перекрестных связей и вспомогательного блока 7 управления. Выходы основного блока 5 управления подключены к входам соответствующих интеграторов. Выход 25 блока перекрестных связей соединен с входомвспомогательного блока управления, выходы которого через нормально замкнутые контакты реле 9 подключены к входам интеграторов.(4) где Устройство предназначено для определения значений переменных Х,(= 1,2,п), при которых целевая функцияР(Х) =а,Х, (1) достигает наибольшего (или наименьшего) значения при выполнении ограничивающих условийлд,(Х)= Й,Х.+ЙО, 1=1,2 т, (2) Ограничения выражения (2) определяют допустимую область изменения переменных Х;. Точка решения задачи линейного программирования находится на границе допустимой области.Уравнение границы допустимой области представим в видеЙ(Х) = О. (3) Значение функции Й(Х) в любой точке пространства переменных, не принадлежащей границе (3), рассматриваем как расстояние от этой точки до границы (3), Это расстояние Й представляет собой наименьшее (алгебраически) из значений функцпй ограничений я;(Х) в рассматриваемой точкеЙ = мин.(,. В устройстве искомые значения переменных фиксируют на выходах интеграторов, количество которых в общем случае равно количеству переменных, Управляющие напряжения, подаваемые на входы интеграторов, приняты в виде 1, = Л; =- - ЙЙ,. + т Х сЙе + , (о) е=1где С; - коэффициенты перекрестных связей,с= -1- (Р,Й, - Рей,); В выражении (6) знак + соответствует поиску максимума целевой функции, а-поиску минимума. Выражение (5) можно представить в следующем видеВ, = Х, = Р + Ьь Уг -- ЙЙ, - управляющее воздействие; вырабатываемое основным блоком управления; ОдУг = , Сы Йе - управляющее воздействие,е=1вырабатываемое вспомогательным блоком управления. Таким образом, устройство имеет переменную структуру, Первая структура работает в том случае, если значения переменных на выходах интеграторов не удовлетворяют системе 5 10 15 го г 5 30 35 40 45 50 55 60 65 ограничений (2). При этом Й(0, у=О и устройство приводит переменные к соотношению (3). Вторая структура работает в том случае, когда значения переменных удовлетворяют системе ограничений (2). При этом Й) О и устройство изменяет переменные так, чтобы выполнять условие (3) и одновременно увеличивать (или уменьшать) целевую функцию. Когда переменные достигают значений, соответствующих условию (3), дальнейшее их изменение происходит в направлении оптимизации целевой функции при поддержании между ними соотношения (3).Пусть, например, начальные значения переменных на выходах интеграторов таковы, что значение первой функции ограничений отрицательно, а остальных двух положительны.1-1 апряжения с выходов интеграторов подают на входы блока ограничений. На выходе этого блока напряжение, равное значению первой функции ограничений, отрицательно, а два остальных напряжения положительны. Эти напряжения с выходов блока ограничений подают на входы блока логики, На выходе блока логики получают напряжение, равное значению первой функции ограничений с обратным знаком, так как в рассматриваемом случае это напряжение является наименьшим ( алгебраически),Релейные элементы блока логики переключают свои контакты в схемах основного блока управления, блока перекрестных связей и вспомогательного блока управления. В результате этих переключений в схему вычислений вводятся частные производные той функции ограничений, значение которой выбрано блоком логики - в рассматриваемом случае первой функции ограничений, Напряжение с выхода блока логики подают на вход основного блока управления. С выходов основного блока управления на входы интеграторов подают напряжения, обеспечивающие такое изменение переменных на их выходах, в результате которого переменные достигают значений, соответствующих границе допустимой области.Напряжение с выхода блока логики подают также на обмотку реле 9. Так как в рассматриваемом случае это напряжение положительно, то реле 9 размыкает свои нормально замкнутые контакты 10, 11 и 12, отключая входы интеграторов 1, 2 и 3 от выходов вспомогательного блока управления, на входы которого подают напряжения с выходов блока перекрестных связей.Управляющие напряжения, которые подают на входы интеграторов из основного блока управления, обеспечивают такое изменение переменных на выходах интеграторов, при котором напряжение на выходе блока ограничений, равное значению первой функции ограничений, уменьшается (по абсолютной величпне). Когда напряжение ва выходе блока логики достигает нуля. реле управления замыкает свои нормально замкнутые контакты. Калмык Борисова оставител Техред корректор Е. Зимина ыбалов дакт Заказ 2187/16 Изд. М 1632 Тирани 647 ПодппсноЦЕ 11111 П 1 Комитета по делам изобретений и открытии при Совете Мшшстров СССР Москва, Ж, Раршская наб., д. 45 ппография, пр. Сапунов и подключает выходы вспомогательного блока управления к входам интеграторов.Управляющие напряжения, которые подают на входы интеграторов с выходов вспомогательного блока управления 7, обеспечивают такое изменение переменных на выходах интеграторов, при котором целевая функцця увеличивается (в рассматриваемом случае определяют, например, максимум целевой функции), а значение первой функции ограничений поддерживается равным нулю. При этом значение одной из двух остальных функций ограничений, например, второй увеличивается, третьей - уменьшается и достигает нуля,При дальнейшем изменении переменных значение третьей функции ограничений становится отрицательвым. В этом случае соответствующее напряжение на выходе блока ограничений отрицательно, а на выходе блока логики напряжение положительно. Вследствие этого реле 9 размыкает контакты отключая выходы вспомогательного блока управлеп.я от входов интеграторов,Управляющие напряжения основного блока управления обеспечивают такое измененв 1 е переменных, в результате которого значение третьей функции ограничений снова становится равным нулю. Реле 9 управления замыкает контакты 10, 11 и 12, и переменные на выходах интеграторов изменяют г, зап 11 авле нии увеличения значение целевой функции гри сохранен и значения третьей функции ог 1 анкче шравного нулю,Таким образом, в устройстве возникает режим переключений, при котором переменные5 удерживают вблизи значений, при которыхдве функции ограничений равны нулю. Этизначения переменных определяют пересечения двух соответствующих участков границы.Коорднаты этого пересечснпопределяют10 значения переменных, прп которых целеваяфункция достигает наибольшей величины прпсоблюденип ограничивающих условий,Устройство для решения задач лпие"ногопрограммирования, содержа:цее интеграторы,первые входы которых присоединены к выходу блока управления, а выходы через блок20 ограничений и блок логики подключены квходам блока управления, отлича 1 ощеесятем,что, с целью повышения быстродействия, оносодерж.;блок перекрестных связей, с подключенным к нему вспомогательным блоком25 правления и реле, нормально замкнутыеконтакты которого включены между выходамивспомогательного блока управления и вторымп входами интеграторов, а обмотка подключена к одному из выходов блока логики, под 30 ключенн;го остальвыми выходамп к входамиспо.,. га-нного блока управления и к входам блока перекрестных связей,

Смотреть

Заявка

1653240

Ю. В. Костенко, Л. М. Бойчук Институт кибернетики Украинской ССР

Авторы изобретени

МПК / Метки

МПК: G06G 7/122

Метки: задач, линейного, программирования, решения

Опубликовано: 01.01.1973

Код ссылки

<a href="https://patents.su/3-384107-ustrojjstvo-dlya-resheniya-zadach-linejjnogo-programmirovaniya.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для решения задач линейного программирования</a>

Похожие патенты