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

Пусть ЗЛП представлена в виде:

при

Выделим зависимость между m и n и количеством решений системы уравнений.

Пусть m>n. Количество уравнений больше числа переменных и нет линейно-зависимых уравнений. Система не имеет решений.

Если m=n и нет линейно зависимых, то система ограничений имеет единственное решение. Следовательно, ЗЛП имеет единственное решение именно в этой точке.

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

Запишем ЗЛП в векторном виде:

при

Пусть m<n. Все m уравнений линейно- независимы. Тогда переменные можно выразить через переменные. Назовем- базисными переменными, а– свободными.

Область допустимых значений будем называть многогранником планов (для ЗЛП от двух неизвестных – выпуклый многоугольник). Точку пересечения линий будем называть крайней точкой многогранника планов.

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

Теорема1. Если система векторов , имеет линейно-независимую подсистему, то допустимое решение (,0,0,…,0) является крайней точкой многогранника планов.

Замечание: Среди крайних точек многогранника плана и находится оптимальное (max) решение.

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

2.4. Общая идея симплексного метода

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

.

Для примера: m=5, n=7. Количество крайних точек: 21. каждую из них необходимо найти, посчитать значение целевой функции. Потом все их сравнить.

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

Таким образом, общая идея симплексного метода состоит в следующем: перемещаясь от данной крайней точки к смежной по ребру лучшей, а затем еще лучшей, найти оптимальное решение ЗЛП.

Алгоритм решения ЗЛП симплексным методом:

1. Найти начальное опорное решение ЗЛП.

2. Проверить, не является ли оно оптимальным.

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

4. Перейти к пункту 2.

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

1. уметь строить начальный опорный план ЗЛП;

2. знать признак оптимальности опорного плана;

3. уметь переходить к нехудшему опорному плану.