Билет 16. Вопрос 1. Регулярные методы оптимизации: симплекс-метод решения задач линейного программирования.

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

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

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

Рассмотрим задачу линейного программирования: найти минимум функции

Формально изложенный метод сводится к выполнению следующих этапов.

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

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

З. В соответствии с симплекс-критерием II выбирается путь улучшения плана, т.е. новая базисная переменная, и опре­деляется ее максимально допустимое значение. Одновременно определяется переменная, которую нужно исключить из базиса.

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

Как уже отмечалось, задачи линейного программирования
могут иметь множество равнозначных оптимальных решении.
Симплекс-метод гарантирует получение одного из этих решений. Сама процедура симплекс-метода неоднозначна. Опреде­ленный произвол заключен как в выборе первоначального ба­зисного решения, так и пути совершенствования этого решения.
В частности, в рассмотренном примере при первоначаль­ном улучшении по переменной х будет получено равнозначное
(6.88) оптимальное решение (точка IV на рис. 6.12). I

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

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

????????????????????????????????????????????????????????? стр 269

Дата добавления: 2015-07-15