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

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

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

Основное достоинство таких моделей - сравнительно малое число требуемых усилителей. Основной недостаток - низкая точность, вызываемая использованием реальных диодов, характеристики которых отличаются от характеристик идеальных диодов. В результате переменные задачи обращаются в нуль неточно. Эти переменные становятся равными напряжениям на открытых диодах, которые составляют 0,2-0,3 в для германиевых и 0,4-0,7 в для кремниевых диодов и колеблются в зависимости от тока диода. Возникающая при этом относительная погрешность оказывается значительной, так как уровень напряжений, моделирующих искомые неизвестные в таких схемах, сравнительно низок.

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

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

На чертеже показана схема набора следующей задачи:

c₁x₁+с₂х₂+с₃х₃+с₄х₄+с₅х₅=max (min),

a₁₁x₁+а₁₂х₂+а₁₃х₃+а₁₄х₄+а₁₅х₅-b₁=0,

при

a₂₁x₁+a₂₂x₂+a₂₃x₃+a₂₄x₄+а₂₅х₅-b₂=0,

х₁≥0; х₂≥0; x₃≥0; х₄≥0; x₅≥0.

В схеме устройства диоды 1 включены последовательно в проводники, соединяющие прямую 2 и транспонированную 3 матрицы проводимостей. Роль искомых неизвестных x_i играют напряжения на катодах диодов 1.

Коэффициенты уравнении моделируются проводимостями схемы. Масштаб неизвестных выбирается достаточно малым, чтобы проводимости b_i были намного меньше проводимостей a_ij.

Показание миллиамперметра 4 пропорционально величине целевой функции. Изменение целевой функции в сторону увеличения или уменьшения осуществляется перемещением движка потенциометра 5. Это перемещение продолжается до тех пор, пока выходное напряжение какого-либо усилителя 6 не достигнет границы линейного диапазона (например, 100). Если к этому моменту показание миллиамперметра 4 уже перестало изменяться, то решение получено. В противном случае следует еще более уменьшить масштаб неизвестных.

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

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

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

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