Основы симплексного метода решения ЗЛП: идеология и общая схема метода. Получение оптимальных решений средствами MS Excel

Сначала кратко напомним некоторые математические понятия и факты.

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

Определение 1. Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель из коэффициентов при них отличен от нуля. Тогда остальные n - m переменных называются неосновными (свободными).

Определение 2. Базисным решением системы m линейных уравнений с n переменными (m < n) называется всякое её решение, в котором неосновные переменные имеют нулевое значение.

Определение 3. Решение системы m линейных уравнений с n переменными (m < n) называется допустимым, если в нём все основные переменные неотрицательны.

Теорема. Существует взаимнооднозначное соответствие между угловыми точками множества допустимых решений системы m линейных уравнений с n переменными (m < n) и её допустимыми базисными решениями.

Сначала необходимо ЗЛП привести к каноническому виду (КЗЛП).

Доказано, что оптимальное решение ЗЛП (если оно существует и притом единственное) совпадает с одним из допустимых базисных решений системы ограничений, следовательно, с угловой точкой многогранника решений.

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

Для реализации симплекс-метода – метода последовательного улучшения плана – необходимо знать три основные операции:

1) способ определения какого-либо первоначального допустимого базисного решения;

2) алгоритм перехода от одного допустимого базисного решения к другому;

3) критерий проверки оптимальности решения.

Замечание. Если первоначальное базисное решение недопустимо, то удобно использовать симплекс-метод с искусственным базисом.

9. Двойственность в линейном программировании, свойства двойственных оценок и их использование в анализе оптимального плана

Рассмотрим основные понятия и выводы специального раздела линейного программирования — теории двойственности.

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

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

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

Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой задачи. Однако при определении симплексным методом оптимального плана одной из задач находится решение и другой задачи.

Правило построения двойственной задачи по отношению к исходной задаче определяется системой соотношений:

Исходная задача	Двойственная задача

Двойственная задача составляется согласно следующим правилам:

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид «£», а в задаче на минимум — «³».

2) матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи; число ограничений двойственной задачи равно числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи;

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства «£», соответствует переменная, связанная условием неотрицательности.

Основные утверждения о двойственных задачах содержатся в двух следующих теоремах

Теорема 1 (основная теорема двойственности). Если одна из двойственных задач разрешима, то разрешима и другая, причем экстремальные значения целевых функций задач равны: . Если одна из двойственных задач неразрешима, то неразрешима и другая.

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

То есть для оптимальных планов двойственных задач имеют место соотношения: