Симплекс-метод решения задачи линейного программирования
Симплексная таблица канонической задачи
Баз. |
x0 |
x1 |
x2 |
x3 |
x4 |
x3 x4 |
b1 b2 |
a11 a21 |
a12 a22 |
1 0 |
0 1 |
f |
C0 |
C1 |
C2 |
0 |
0 |
Если в задаче ЛП система уравнений каноническая, а целевая функция выражена не только через свободные неизвестные, то такую задачу будем называть "почти канонической". При внесении такой задачи в симплексную таблицу индексная строка подсчитывается по правилу цен. Это правило будет рассмотрено ниже.
Для решения канонической ("почти канонической") задачи, записанной в симплексную таблицу, применяется алгоритм симплекс-метода. Существуют две разновидности этого алгоритма: для задачи максимизации и для задачи минимизации. Можно использовать только одну из них, сводя Каждый раз, например, задачу минимизации целевой функции f(X) к задаче максимизации функции -f(X), умножив все коэффициенты функции f(X) на -1. Это возможно в силу линейности целевой функции. Приведем алгоритм симплекс-метода для случая задачи максимизации.
Алгоритм симплекс-метода
. Запишем каноническую задачу максимизации (4)-(б) в исходную симплексную таблицу и проанализируем знаки элементов индексной строки, не считая элемента С0. При этом возможны три случая.
.1. Все элементы индексной строки неотрицательны. Следовательно, базисный план Xbas=(0, 0, b1, b2), является оптимальным, a f(Xbas) = C0 есть максимальное значение целевой функции. Вычисления прекращаем.
.2. Среди элементов индексной строки есть хотя бы один отрицательный, а над ним в таблице нет ни одного положительного. В этом случае целевая функция не ограничена сверху на множестве планов задачи и, значит, оптимального плана не существует. Вычисления прекращаем.
.3. Над каждым отрицательным элементом индексной строки есть хотя бы один положительный. Это значит, что исходный базисный план можно улучшить, построив новую симплексную таблицу, содержащую новый базисный план с неменьшим значением целевой функции. Переходим к п. 2.
. Среди отрицательных элементов индексной строки, над каждым из которых есть хотя бы один положительный, выбираем наибольший по абсолютной величине и выделяем ключевой столбец, в основании которого оказался выбранный элемент. Ключевой столбец указывает на неизвестное, вводимое в базис.
. Подсчитываем ключевое отношение - наименьшее из отношений свободных членов уравнений только к соответствующим положительным элементам ключевого столбца.
. В ключевом столбце выбираем и выделяем ключевой элемент -знаменатель ключевого отношения. Если ключевых отношений несколько, то выбираем знаменатель любого из них. Ключевой элемент указывает на неизвестное, выводимое из базиса.