Симплексный метод или метод последовательного улучшения плана основан на идее перехода от одного базисного решения в вершине многоугольника допустимых решений к другому базисному решению, более близкому к оптимальному.
Задача ЛП формулируется следующим образом:
задана система ограничений .
Требуется найти максимум целевой функции .
Предполагается, что ранг системы равен числу уравнений m и меньше числа переменных n.
Пронумеруем переменные таким образом, чтобы вначале шли свободные переменные, а далее базисные переменные:
.
Выразим базисные переменные и целевую функцию через свободные переменные:
Для удобства использования алгоритма свободные переменные выделяем с отрицательными знаками:
(5.1)
(5.2)
Решение задачи осуществляется в симплексной таблице, у которой каждая строка соответствует уравнению из (5.1):
.
Т. е. каждая строка симплекс-таблицы соответствует базисной переменной, а каждому столбцу соответствует свободная переменная xj и выделен столбец свободных членов (правых частей ограничений) bi. Внизу помещена строка целевой функции F.
|
|
Свободные переменные
Базисные | -x1 … | -хj … | -xk | b | |
xk+1 … | a11 | a1j | a1k | b1 … | |
xk+ i … | ai1 | ajj | aik | bi … | |
xn | am1 | amj | amk | bm | |
F | c1 | ck | c0 |
Решение системы, полученное приравниванием свободных переменных к нулю, называется базисным (опорным) решением.
Таким образом, в таблице записано следующее опорное решение:
xk+1=b, …, xk+i=bi , …, xn=bm, xj=0, j = .
При этом, как видно, целевая функция будет равна F=c0 .
Рассматриваются только те свободные переменные, которые входят в целевую функцию с отрицательным коэффициентом, например . Увеличение такой переменной ведет к увеличению максимизируемой целевой функции. Если сохранить за остальными свободными переменными нулевое значение и начать увеличивать xj, то целевая функция будет увеличиваться, что и нужно для оптимизации.
Переменную xj можно увеличивать до тех пор, пока одна из базисных переменных xk+1,…,xn не обратится в ноль, например xk+i. Дальше увеличивать xj нельзя, т.к. переменная xk+i станет отрицательной, т.е. нарушится условие неотрицательности (xk+i ³ 0). А когда произойдет обращение в ноль базисной переменной можно установить из соотношений:
xk+1 = b1 - a1j xj,
…
xk+i = bi - aij xj, (5.3)
…
xn = bm - amj xj ;
F = c0 + cj xj .
Причем нас интересуют только те уравнения, в которых коэффициент aij>0, т.к. при aij£ 0 с увеличением xj соответствующая базисная переменная никогда не обратится в ноль.
Базисная переменная обратится в ноль, когда выполнится соотношение .
Быстрее всех обратится в ноль та базисная переменная, для которой отношение является минимальным. Это отношение называется симплексным отношением. Остальные базисные переменные при этом будут еще положительны.
|
|
Коэффициент аij называется генеральным коэффициентом или разрешающим элементом.
Выведем переменную xj из числа свободных и сделаем ее базисной (т.к. раньше установили, что ее можно увеличить для оптимизации), а вместо нее введем переменную xk+i, которая быстрее других базисных переменных обратится в ноль. Теперь необходимо выразить целевую функцию F и новый набор базисных переменных (в который вошла xj) через набор новых свободных переменных, куда вошла xk+i. Допустим, надо поменять переменную xj на yi при разрешающем элементе aij в таблице 1 и получить новую таблицу 2.
Исходная таблица 1 Таблица 2
-x1 | … | -xj | ® | -x1 | … | -yi | ||
y1 | a11 | … | a1j | y1 | a11+ai1(-a1j/aij) | … | -a1j/aij | |
… | … | … | … | … | … | … | … | |
yi | a i1 | … | а ij | xj | ai1/aij | … | 1/aij |
Эти преобразования осуществляются в симплексной таблице по следующему алгоритму:
1. В таблице 1 выделяется разрешающий элемент на пересечении i -й строки и j -го столбца (aij).
2. В таблице 2 разрешающий элемент заменяется на обратную величину.
3. Все остальные элементы разрешающей строки i делятся на разрешающий элемент.
4. Все элементы разрешающего столбца j делятся на разрешающий элемент и меняют знак на противоположный.
5. Все остальные элементы, не принадлежащие разрешающим столбцу и строке, вычисляются по правилу «прямоугольника». Мысленно выделяется прямоугольник, в котором подлежащий пересчету элемент и разрешающий элемент образуют одну из диагоналей. Из произведения этих элементов вычитается произведение элементов, образующих другую диагональ прямоугольника, а результат делится на разрешающий элемент.
Сам алгоритм нахождения оптимального решения включает следующие операции.
1. Просматривается строка целевой функции F, и если среди ее коэффициентов, не считая свободного члена c0, все элементы положительны, то оптимальное решение достигнуто.
2. Если в строке F есть отрицательный коэффициент, а в столбце, соответствующем ему, нет ни одного положительного элемента, то целевая функция не ограничена и оптимального решения не существует.
3. Если в столбце над отрицательным коэффициентом целевой функции есть положительные элементы, то необходимо произвести замену соответствующей свободной переменной на базисную. В качестве разрешающего берется тот элемент выбранного столбца, который имеет одинаковый знак со свободным членом, и для которого симплексное соотношение минимально. С этим разрешающим элементом осуществляется шаг преобразования таблицы.
4. Операции 1, 2, 3 повторяются до получения оптимального решения.