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

Пусть необходимо найти оптимальный план производства двух видов продукции (х₁ и х₂).

Исходные данные:

1 Построим оптимизационную модель

- ограничение по ресурсу А;

- ограничение по ресурсу В.

2 Приведем задачу к приведенной канонической форме. Для этого достаточно ввести дополнительные переменные Х₃ и Х₄. В результате неравенства преобразуются в строгие равенства.

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

x₃ =20 и x₄ =36

1- я итерация. Находим генеральный столбец и генеральную строку

max (7,3) = 7

Генеральный элемент равняется 5.

2-я итерация. Найденное базисное решение не является оптимальным, т. к. cтрока оценок (F_j-C_j) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:

max (0,0.2,-1.4,0) = 0.2

Найденное решение оптимально, так как все специальные оценки целевой функции F_j - C_j равны нулю или отрицательны. F(x)=29 x₁ =2; x₂ =5.

Примечания к симплекс-методу.

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

2. Несовместимость системы ограничений (в канонической форме) обнаруживается при построении начального д.б.р. (оно не существует).

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

4. Симплекс-метод за конечное число итераций либо приводит к оптимальному решению, либо устанавливает неразрешимость задачи (см. пп. 1,2,3).

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

6. На каждой итерации целевая функция убывает (в задаче на минимум) или возрастаем (в задаче на максимум); это свойство нарушается только в случае зацикливания (см. примечания 11,12).

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

8. Слабые переменные со знаком "+" (вводимые для преобразования неравенств вида " ") можно использовать в качестве базисных переменных, а слабые переменные со знаком "-" (вводимые для преобразования неравенств вида " ") - нет.

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

10. При решении симплекс-методом задачи на максимум изменяется только правило выбора ведущей строки (столбик с минимальной отрицательной оценкой) и критерий оптимальности (отсутствие в нулевой строке отрицательных оценок).

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

12. Для выхода из зацикливания: в критерии определения ведущей строки вместо элементов 0-го столбика применяют элементы 1-го столбика; если и здесь ведущая строка неоднозначна, то применяют элементы 2-го столбика и т.д., пока ведущая строка не будет определена однозначно.