ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.03.2024
Просмотров: 11
Скачиваний: 0
Табличный алгоритм замены базисных переменных (лекции Л.А. Манило)
(продолжение лекции)
В задаче линейного программирования (ЛП) кроме уравнений-ограничений существует ещѐ и линейная функция
L c0 c1x1 ... cj xj ... cn xn , которую нужно минимизировать.
После замены xj yi еѐ нужно выразить через новые свободные переменные
x1, x2 ,..., xj 1, yi , xj 1,..., xn .
Для этого можно использовать тот же алгоритм, что и для преобразования любой строки таблицы.
Действительно, т.к.
L c0 ( 1x1 ... |
j xj ... |
n xn ) , где 1 c1; 2 c2 ; ... |
n cn , |
мы получим ещѐ одну строку (добавочную) стандартной таблицы, в которой никогда не выбирается разрешающий элемент.
С помощью табличного алгоритма обмена переменных в уравнениях основной задачи ЛП (ОЗЛП) можно решить любую задачу ЛП.
Нахождение решения распадается на 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 ).
|
|
|
|
|
|
|
Св. член |
|
|
|
|
x1 , x1 y3 |
|
|
|
|
|
x2 |
|
|
|
x3 |
||||
|
|
y1 |
1 |
|
|
|
|
|
-1 |
|
|
|
|
-2 |
|
1 |
|
|||||||||
|
|
|
|
|
|
2 |
|
|
|
|
|
|
1 |
|
|
|
|
1 |
0 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
y2 |
-5 |
|
|
|
|
-2 |
|
|
|
|
|
|
1 |
|
|
-1 |
|||||||||
|
|
|
|
|
|
4 |
|
|
|
|
|
|
2 |
|
|
|
|
2 |
0 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
y3 , y3 x1 |
|
2 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
0 |
|
|||||||
|
|
|
|
|
2 |
|
|
|
|
λ=1 |
|
|
|
1 |
0 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
y4 |
1 |
|
|
|
|
|
0 |
|
|
|
|
-1 |
|
1 |
|
||||||||||
|
|
|
|
|
|
0 |
|
|
|
|
|
|
0 |
|
|
|
|
0 |
0 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Св. член равен -5 – это плохо! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
5 2 |
1 |
; - это для строки |
y |
|
. |
|
|
|
2 |
2; |
- это для строки |
y . |
|
|
|
|||||||||||
|
|
2 |
|
|
|
|
|
|
|
|||||||||||||||||
2 |
2 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
3 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
2 2 |
1 |
. Производим замену |
y |
x |
, получаем |
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
2 |
|
|
|
|
|
|
|
3 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Св. член |
|
|
|
|
|
|
|
|
y3 |
|
|
|
|
x2 |
x3 , x3 y2 |
|||
|
|
|
|
y1 |
|
3 |
|
|
|
|
|
|
|
1 |
|
-1 |
|
|
1 |
|
|
||||
|
|
|
|
|
|
-1 |
|
2 |
|
|
|
|
3 |
|
1 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
y2 , y2 x3 |
|
-1 |
|
|
|
|
|
|
|
|
2 |
|
|
3 |
|
|
|
-1 |
|
|
||||
|
|
|
|
|
|
1 |
|
-2 |
|
|
|
|
-3 |
λ= -1 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
x1 |
|
2 |
|
|
|
|
|
|
|
1 |
|
1 |
|
|
|
0 |
|
|
|||
|
|
|
|
|
|
0 |
|
0 |
|
|
|
|
0 |
|
0 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
y4 |
|
1 |
|
|
|
|
|
|
|
0 |
|
-1 |
|
|
1 |
|
|
||||
|
|
|
|
|
|
-1 |
|
2 |
|
|
|
|
3 |
|
1 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
Св. член равен -1 – это плохо! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
3 |
3; |
- это для строки |
y |
. |
1 |
|
1; - это для строки y |
|
. |
|
|
|
||||||||||||
1 |
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
1 |
1; |
- это для строки |
y |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Минимум для строк y2 , y4 |
(можно выбрать любой). |
|
|
|
|
|
|
|
|
||||||||||||||||
Производим замену y2 x3 , получаем |
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
Св. член |
|
|
|
|
|
|
|
|
y3 |
|
|
|
|
x2 |
y2 |
|||
|
|
|
|
y1 |
|
2 |
|
|
|
|
|
|
3 |
|
|
|
|
2 |
1 |
|
|
||||
|
|
|
|
x3 |
|
1 |
|
|
|
|
|
|
-2 |
|
|
|
|
-3 |
-1 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
x1 |
|
2 |
|
|
|
|
|
|
1 |
|
|
|
|
1 |
0 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
y4 |
|
0 |
|
|
|
|
|
|
2 |
|
|
|
|
2 |
1 |
|
|
||||
Опорное решение найдено. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
y3 x2 y2 0; y1 2; |
x3 1; x1 2; y4 0. |
|
|
|
|
|
|
|
|
Отыскание оптимального решения основной задачи ЛП
Надо найти такое опорное решение, которое обращает в минимум линейную функцию
L c0 ( 1x1 ... j xj ... n xn ) .
Принципиальную сторону вопроса мы уже рассматривали. Здесь мы на примере покажем, как эта оптимизация м. б. проведена с помощью табличного алгоритма замены xj yi .
Сформулируем правила нахождения оптимального решения симплекс-методом.
1.Если все свободные члены (не считая строки L) в симплекс таблице неотрицательны, а в строке L (не считая свободного члена) нет ни одного положительного элемента, то оптимальное решение достигнуто.
2.Если в строке L есть положительный элемент, а в столбце, соответствующем ему, нет ни одного положительного элемента, то линейная функция L не ограничена снизу и оптимального решения не существует.
3.Если в этом столбце есть положительные элементы, то следует произвести замену одной из свободных переменных на одну из базисных, причѐм в качестве разрешающего надо взять тот элемент этого столбца, для которого отношение к нему соответствующего свободного члена минимально.
Пример
Найти решение задачи ЛП с уравнениями
y1 2 (x1 x2 2x3 ); y2 1 (x1 x2 x3 ); y3 5 (x2 x3 );
y4 2 (2x1 x2 );
обращающее в минимум линейную функцию L 0 ( x1 2x2 x3 ).
Решение. Т.к. все свободные члены неотрицательны, то опорное решение налицо:
x1 x2 x3 0; y1 y4 2; y2 1; y3 5; |
L 0. |
|
|
|
|
|
||||||||||
Это решение не оптимально, т.к. коэффициент при x2 и x3 |
положительны. Выберем x3 , |
|||||||||||||||
его надо поменять. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Св. член |
|
|
|
x1 |
|
|
|
|
x2 |
x3 , x3 y2 |
||||
|
|
|
|
|
|
|
|
|
|
|
||||||
L |
0 |
|
|
-1 |
|
2 |
|
|
1 |
|
|
|
||||
|
|
|
|
-1 |
|
|
|
-1 |
|
|
|
1 |
|
-1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y1 |
2 |
|
|
1 |
|
|
1 |
|
|
-2 |
|
|
|
|||
|
|
|
2 |
|
|
|
2 |
|
|
|
-2 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
y2 , y2 x3 |
|
1 |
|
|
|
1 |
|
|
|
-1 |
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
-1 |
λ=1 |
||||
|
|
|
|
|
|
|
|
|
|
|||||||
y3 |
5 |
|
|
0 |
|
|
1 |
|
|
1 |
|
|
|
|||
|
|
|
-1 |
|
|
|
-1 |
|
|
|
1 |
|
-1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
y4 |
2 |
|
|
2 |
|
|
-1 |
|
|
0 |
|
|
|
|||
|
|
|
0 |
|
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 1; - это для строки y2 . 15 5; - это для строки y3 . По min выбираем y2 .
|
|
|
|
|
Св. член |
|
|
|
|
|
|
|
x1 |
|
x2 , x2 y3 |
|
|
y2 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
L |
|
-1 |
|
|
|
|
-2 |
|
|
3 |
|
|
|
|
|
-1 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
-6 |
|
3/2 |
|
|
|
|
-3/2 |
|
3/2 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y1 |
|
4 |
|
|
|
|
|
3 |
|
|
-1 |
|
|
|
|
|
2 |
|
|
|
|
||||
|
|
|
|
|
2 |
|
-1/2 |
|
|
|
|
|
1/2 |
|
-1/2 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
x3 |
|
1 |
|
|
|
|
|
1 |
|
|
-1 |
|
|
|
|
|
1 |
|
|
|
|
||||
|
|
|
|
|
2 |
|
-1/2 |
|
|
|
|
|
1/2 |
|
-1/2 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
y3 , y3 x2 |
|
4 |
|
|
|
|
|
-1 |
|
|
2 |
|
|
|
|
|
|
-1 |
|
|
|
|
||||
|
|
|
|
|
2 |
|
-1/2 |
|
|
|
λ=1/2 |
-1/2 |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
y4 |
|
2 |
|
|
|
|
|
2 |
|
|
-1 |
|
|
|
|
|
0 |
|
|
|
|
||||
|
|
|
|
|
2 |
|
-1/2 |
|
|
|
|
|
1/2 |
|
-1/2 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Св. член |
|
|
|
|
|
|
|
x1 |
|
|
|
y3 |
|
|
y2 , y2 y1 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
L |
|
-7 |
|
|
|
|
-1/2 |
-3/2 |
|
|
|
|
1/2 |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
-2 |
|
-5/6 |
|
|
|
-1/6 |
|
|
-1/3 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
y1 , y1 y2 |
|
6 |
|
|
|
|
|
5/2 |
|
|
1/2 |
|
|
|
|
|
3/2 |
|
|
|
||||||
|
|
|
|
|
4 |
|
5/3 |
|
|
|
1/3 |
|
|
|
λ=2/3 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
x3 |
|
3 |
|
|
|
|
|
1/2 |
|
1/2 |
|
|
|
|
|
1/2 |
|
|
|
||||||
|
|
|
|
|
-2 |
|
-5/6 |
|
|
|
-1/6 |
|
|
|
|
-1/3 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
x2 |
|
2 |
|
|
|
|
|
-1/2 |
1/2 |
|
|
|
|
|
-1/2 |
|
|
|
|||||||
|
|
|
|
|
2 |
|
5/6 |
|
|
|
1/6 |
|
|
|
|
|
1/3 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
y4 |
|
4 |
|
|
|
|
|
3/2 |
|
1/2 |
|
|
|
|
|
-1/2 |
|
|
|
||||||
|
|
|
|
|
2 |
|
5/6 |
|
|
|
1/6 |
|
|
|
|
|
1/3 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
6 |
4; |
- это для строки |
y . |
|
3 |
|
6; - это для строки |
x . По min выбираем y |
||||||||||||||||||
32 |
|
|
|
|
|
1 |
12 |
|
|
|
|
|
|
3 |
|
|
|
1 . |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
Св. член |
|
|
|
|
|
|
|
x1 |
|
|
|
y3 |
|
|
y1 |
|||||||
|
|
L |
|
-9 |
|
|
|
|
-8/6= -4/3 |
-10/6 = -5/3 |
|
-1/3 |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
y2 |
|
4 |
|
|
|
|
5/3 |
|
|
|
1/3 |
|
|
|
2/3 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
x3 |
|
1 |
|
|
|
|
-2/6 = -1/3 |
|
|
|
2/6 = 1/3 |
|
|
|
-1/3 |
|
|
|
|||||||
|
|
x2 |
|
4 |
|
|
|
|
1/3 |
|
|
|
4/6=2/3 |
|
|
|
1/3 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
y4 |
|
6 |
|
|
|
|
14/6=7/3 |
|
|
|
2/3 |
|
|
|
1/3 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т.к. в строке L нет ни одного положительного элемента, то оптимальное решение достигнуто.
x1 y3 y1 0; y2 x2 4; x3 1; y4 6; |
L 9. |