Симплекс-метод решения ЗЛП

Допустим, имеется исходная ЗЛП в канонической форме:
F(X)=c₁X₁+c₂X₂+...+c_nX_n => max

a_1,1X₁+a_1,2X₂+...+a_1,nX_n=b₁
a_2,1X₁+a_2,2X₂+...+a_2,nX_n=b₂
.....................
a_m,1X₁+a_m,2X₂+...+a_m,nX_n=b_m

В общем случае m любых переменных можно выразить через оставшиеся (n-m) переменных, например - X₁...X_m через X_m+1...X_n:

X₁=B₁-(A_1,m+1X_m+A_1,m+2X_m+2+...+A_1,nX_n)
...........................................................
X_m=B_m-(A_m,m+1X_m+1+A_m,m+2X_m+2+...+A_m,nX_n)

Здесь коэфициенты В_i и А_i,j выражаются через b_i и a_i,j.

Переменные X₁... X_m называются базисными, а X_m+1...X_n- свободными.

Если положить X_m+1=...=X_n=0, то X_i=B_i и если при этом все B_i =0, то и X_i =0, и такой вектор:

X=(B₁, B₂,..., B_m, 0, 0,..., 0)

называется базисным или опорным.
Выражение целевой функции через свободные переменные:

F=C₀-(C_m+1X_m+1+...+ C_nX_n)

Здесь коэффициенты C₀, C_m+1,..., C_n выражаются через с_j, B_i, a_{i, j}.

Начальная симплекс-таблица

Составим по этим данным так называемую начальную симплекс-таблицу.

Замечание: В простейшем случае в качестве базисных переменных можно взять такие m переменных, каждая из которых входит только в одно ограничение, причем с положительным знаком, а все свободные члены b_i>0.

Алгоритм симплекс-метода:

1. Определить число и состав базисных и свободных переменных.
2. Выразить базисные переменные через свободные переменные.
3. Выразить целевую функцию через свободные переменные.
4. Построить начальную симплекс-таблицу.
5. Проверить решение на оптимальность: если в F-строке (кроме С₀) все С_j0, то получено оптимальное решение: X=(B₁,...,B_m,0,...,0), F=C₀. Если же существует C_j<0, то решение можно улучшить, но предварительно надо проверить факт существования решения.
6. Проверить существование решения: рассмотрим все столбцы, у которых С_j<0, если существует хотя бы один столбец, у которого все коэффициенты A_i,j<0, то задача решения не имеет, т.к. множество допустимых решений D не ограничено и целевая функция неограниченно возрастает. Если таких столбцов нет, то переходим к следующему этапу.
7. Выбрать свободную переменную, которую надо ввести в базис (выбор разрешающего столбца): это столбец, с минимальным значением С_j (пусть это k-й столбец)
8. Выбрать базисную переменную, которую надо вывести из базиса (выбор разрешающей строки): рассмотрим k-й столбец и все его элементы, которые больше нуля, т.е. A_i,k>0; для всех этих элементов находим отношение B_i/A_i,k и выбираем строку, которая соответствует минимальному значению этого отношения (пусть это i-я строка); соответствующая i-я переменная X_i выводится из базиса; при нескольких одинаковых отношениях берем любую строку; элемент A_i,k называется разрешающим элементом.
9. Пересчитать симплекс-таблицу: составляем новую симплекс-таблицу заменив в составе базисных переменных X_i на X_k; заполняем сначала новую k-ю строку, записывая в нее элементы старой i-ой строки, поделенные на разрешающий элемент; после заполнения k-ой строки заполняем оставшиеся строки; для этого k-ю строку умножаем последовательно на такие числа, чтобы после сложения ее с каждой строкой старой таблицы в k-ом столбце получить везде ноль (кроме единицы в k-ой строке).
10. После заполнения новой симплекс-таблицы алгоритм возвращается к 5-му пункту.

Конец работы алгоритма:

1. либо когда в F-строке все коэффициенты (кроме С₀) будут больше нуля, тогда получаем оптимальное решение,
2. либо когда существует столбец, у которого C_j<<0 и все коэффициенты A_i,j<<0, в этом случае решения на существует.