ЭЛЕКТРОННОЕ МОДЕЛИРОВАНИЕ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

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

Ограничения моделируются с помощью усилителя операционного с диодом в цепи обратной связи.

3. Модель задачи сетевого планирования и управления: а — сетевой график; б — электрическая модель сетевого графика.

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

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

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

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

аналогично схеме модели Денниса для определения кратчайшего пути, однако, в отличие от нее диод и источник напряжения включены последовательно. На рис. 3, б приведена электр. модель сетевого графика рис. 3, а. Величины эдс на рис. 3, б обозначены цифрами в условных единицах. Критический путь на графе между исходным и завершающим событиями будет изображаться путем протекания тока от внешнего источника. Описанные схемы послужили основой для создания машин «АСОР-1» и «Оптимум-2».

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

Лит.: Пухов Г. Е. Избранные вопросы теории математических машин. К., 1964; Васильев В. В., Клепикова А. Н., Тимошенко А. Г. Решение задач оптимального планирования на электронных моделях. К., 1966 [библиогр. с. 161— 164]; Рыбашов М. В., Дудников Е. Е. Градиентные методы решения линейных равенств, неравенств и задач линейного программирования на аналоговых вычислительных машинах. М., 1970 [библиогр. с. 141—142]; Pyne I. В. Linear programming on an electronic analogue computer. «Communication and electronics», 1956, JSli 24; Деннис Дж. В. Математическое программирование и электрические цепи. Пер. с англ. М., 1961 [библиогр. с. 212-214]. А. Н. Клепикова.