Табличный алгоритм

Табличный алгоритм замены базисных переменных (лекции Л.А. Манило)

(продолжение лекции)

В задаче линейного программирования (ЛП) кроме уравнений-ограничений существует ещѐ и линейная функция

L c0 c1x1 ... cj xj ... cn xn , которую нужно минимизировать.

После замены xj yi еѐ нужно выразить через новые свободные переменные

x1, x2 ,..., xj 1, yi , xj 1,..., xn .

Для этого можно использовать тот же алгоритм, что и для преобразования любой строки таблицы.

Действительно, т.к.

мы получим ещѐ одну строку (добавочную) стандартной таблицы, в которой никогда не выбирается разрешающий элемент.

С помощью табличного алгоритма обмена переменных в уравнениях основной задачи ЛП (ОЗЛП) можно решить любую задачу ЛП.

Нахождение решения распадается на 2 этапа.

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

2.Отыскание оптимального решения, минимизирующего линейную функцию L (попутно выясняется, ограничена ли снизу минимизируемая функция L).

Отыскание опорного решения (ОР) основной задачи ЛП

Пусть имеется ОЗЛП с ограничениями-равенствами, в следующей форме

y1 b1 ( 11x1 12 x2 ... 1n xn );

...

ym bm ( m1x1 m2 x2 ... mn xn ).

Первое пробное решение x1 x2 ... xn 0 . Если все bi 0 , то это допустимое решение. Следовательно, оно опорное. Если какие-либо bi 0 , то это решение не

допустимое и не опорное. Для нахождения ОР нужно шаг за шагом обменивать базисные и свободные переменные пока не найдем его, либо убедимся, что система уравнений несовместима с неравенствами x1 0, x2 0,..., xn 0; y1 0, y2 0,..., ym 0.

Очевидно, нужно так обменивать базисные переменные со свободными, чтобы эта процедура приближала нас к границе ОДР, т.е. чтобы число отрицательных свободных членов уменьшалось или при том же числе убывали их абсолютные величины.

Способ выбора разрешающего элемента для приближения к опорному решению

Пусть имеется одно из уравнений с отрицательным свободным членом.

Ищем в этой строке отрицательный ij . Если они все положительные (значит все aij 0 ))

и данная базисная никогда не будет положительной.

Выберем столбец, в котором находится отрицательный ij , в качестве разрешающего столбца.

Рассмотрим только те элементы столбца, которые имеют один знак со свободным членом.

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

Пример

Найти опорное решение задачи ЛП

y1 1 ( x1 2x2 x3 ); y2 5 ( 2x1 x2 x3 ); y3 2 (x1 x2 );

y4 1 ( x2 x3 ).

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

Надо найти такое опорное решение, которое обращает в минимум линейную функцию

L c0 ( 1x1 ... j xj ... n xn ) .

Принципиальную сторону вопроса мы уже рассматривали. Здесь мы на примере покажем, как эта оптимизация м. б. проведена с помощью табличного алгоритма замены xj yi .

Сформулируем правила нахождения оптимального решения симплекс-методом.

Т.к. в строке L нет ни одного положительного элемента, то оптимальное решение достигнуто.