Метод искусственного базиса
Идея использования искусственных переменных предполагает включение неотрицательных переменных в левую часть каждого из уравнений, в которых не содержится очевидных начальных базисных переменных (когда неравенство имеет знак ≥ или задано в виде равенства). Эти дополнительно вводимые переменные выполняют ту же роль, что и остаточные переменные. Но так как искусственные переменные не имеют отношения к поставленной задаче (отсюда их название - искусственные), то их введение допустимо только в том случае, если симплекс метод будет обеспечивать получение оптимального решения, в котором все искусственные переменные будут равны 0, то есть эти переменные следует использовать только для стартовой точки, причем итерационный метод оптимизации должен "вынуждать" эти переменные принимать нулевые значения в конечном оптимальном решении, обеспечивая допустимость оптимума.Разработаны два метода получения стартовой точки:
Пример. Решить задачу ЛП, найдя начальный опорный план методом искусственного базиса.
Определим максимальное значение целевой функции F(X) = 3x3 - 2x4 - x5 при следующих условиях:
2x1 + x2 + x3 + x4 + 3x5=5
3x1 + 2x3 - x4 + 6x5=7
x1 - x3 + 2x4 + x5=2
Решим прямую задачу линейного программирования двухфазным симплекс-методом.
Введем искусственные переменные x.
2x1 + 1x2 + 1x3 + 1x4 + 3x5 + 1x6+ 0x7 + 0x8 = 5
3x1 + 0x2 + 2x3-1x4 + 6x5 + 0x6+ 1x7 + 0x8 = 7
1x1 + 0x2-1x3 + 2x4 + 1x5 + 0x6+ 0x7 + 1x8 = 2
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = - Mx6 - Mx7 - Mx8 => max
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x6 = 5-2x1-x2-x3-x4-3x5
x7 = 7-3x1-2x3+x4-6x5
x8 = 2-x1+x3-2x4-x5
которые подставим в целевую функцию:
F(X) = - M(5-2x1-x2-x3-x4-3x5) - M(7-3x1-2x3+x4-6x5) - M(2-x1+x3-2x4-x5)=> max
или
F(X) = (6M)x1+(1M)x2+(2M)x3+(2M)x4+(10M)x5+(-14M)=> max
Введем новую переменную x0 = 6x1 + x2 + 2x3 + 2x4+ 10x5.
Выразим базисные переменные <6, 7, 8> через небазисные.
x0 = -14+6x1+x2+2x3+2x4+10x5
x6 = 5-2x1-x2-x3-x4-3x5
x7 = 7-3x1-2x3+x4-6x5
x8 = 2-x1+x3-2x4-x5
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
max(6,1,2,2,10,0,0,0) = 10
x0 = -14+6x1+x2+2x3+2x4+10x5
x6 = 5-2x1-x2-x3-x4-3x5
x7 = 7-3x1-2x3+x4-6x5
x8 = 2-x1+x3-2x4-x5
В качестве новой переменной выбираем x5.
Вычислим значения D5 по всем уравнениям для этой переменной.
и из них выберем наименьшее:
min (5 : 3 , 7 : 6 , 2 : 1 ) = 11/6
Вместо переменной x7 в план войдет переменная x5.
Выразим переменную x5 через x7
x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7
и подставим во все выражения.
x0 = -14+6x1+x2+2x3+2x4+10(11/6-1/2x1-1/3x3+1/6x4-1/6x7)
x6 = 5-2x1-x2-x3-x4-3(11/6-1/2x1-1/3x3+1/6x4-1/6x7)
x8 = 2-x1+x3-2x4-(11/6-1/2x1-1/3x3+1/6x4-1/6x7)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = -21/3+x1+x2-11/3x3+32/3x4-12/3x7
x6 = 11/2-1/2x1-x2-11/2x4+1/2x7
x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7
x8 = 5/6-1/2x1+11/3x3-21/6x4+1/6x7
Полагая небазисные переменные x = (6, 5, 8) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-1, -1, 11/3, -32/3, 0, 0, 12/3,0), x0 = -21/3
max(1,1,-11/3,32/3,0,0,-12/3,0)= 32/3
x0 = -21/3+x1+x2-11/3x3+32/3x4-12/3x7
x6 = 11/2-1/2x1-x2-11/2x4+1/2x7
x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7
x8 = 5/6-1/2x1+11/3x3-21/6x4+1/6x7
В качестве новой переменной выбираем x4. <з> Вычислим значения D4 по всем уравнениям для этой переменной.
и из них выберем наименьшее:
min (11/2 : 11/2 , - , 5/6 : 21/6) = 5/13
Вместо переменной x8 в план войдет переменная x4.
Выразим переменную x4 через x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
и подставим во все выражения.
x0=-21/3+x1+x2-11/3x3+32/3(5/13-3/13x1+8/13x3+1/13x7-6/13x8)-12/3x7
x6=11/2-1/2x1-x2-11/2(5/13-3/13x1+8/13x3+1/13x7-6/13x8)+1/2x7
x5=11/6-1/2x1-1/3x3+1/6(5/13-3/13x1+8/13x3+1/13x7-6/13x8)-1/6x7
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = -12/13+2/13x1+x2+12/13x3-15/13x7-19/13x8
x6 = 12/13-2/13x1-x2-12/13x3+5/13x7+9/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
Полагая небазисные переменные x = (6, 5, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-2/13, -1, -12/13, 0, 0, 0, 15/13, 19/13),x0 = -12/13
max(2/13,1,12/13,0,0,0,-15/13,-19/13)= 1
x0 = -12/13+2/13x1+x2+12/13x3-15/13x7-19/13x8
x6 = 12/13-2/13x1-x2-12/13x3+5/13x7+9/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
В качестве новой переменной выбираем x2.
Вычислим значения D2 по всем уравнениям для этой переменной.
и из них выберем наименьшее:
min (12/13 : 1 , - , - ) = 12/13
Вместо переменной x6 в план войдет переменная x2.
Выразим переменную x2 через x6
x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8
и подставим во все выражения.
x0=-12/13+2/13x1+(12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8)+12/13x3-15/13x7-19/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 0-x6-x7-x8
x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
Полагая небазисные переменные x = (2, 5, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 0, 0, 0, 1, 1, 1), x0 = 0
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
x0 = 0-x6-x7-x8
x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
На этом первый этап (первая фаза) симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.
x2 = 12/13-2/13x1-12/13x3
x5 = 13/13-7/13x1-3/13x3
x4 = 5/13-3/13x1+8/13x3
Выразим базисные переменные:
x5 = 13/13-7/13x1-3/13x3
x4 = 5/13-3/13x1+8/13x3
которые подставим в целевую функцию:
F(X) = + 3x3-2(5/13-3/13x1+8/13x3)-(13/13-7/13x1-3/13x3)
или
F(X) = -2+x1+2x3
Получаем новую систему переменных.
x0 = -2+x1+2x3
x2 = 12/13-2/13x1-12/13x3
x5 = 13/13-7/13x1-3/13x3
x4 = 5/13-3/13x1+8/13x3
max(1,0,2,0,0) = 2
x0 = -2+x1+2x3
x2 = 12/13-2/13x1-12/13x3
x5 = 13/13-7/13x1-3/13x3
x4 = 5/13-3/13x1+8/13x3
В качестве новой переменной выбираем x3.
Вычислим значения D3 по всем уравнениям для этой переменной.
и из них выберем наименьшее:
min (12/13 : 12/13 , 13/13 : 3/13, - ) = 1
Вместо переменной x2 в план войдет переменная x3.
Выразим переменную x3 через x2
x3 = 1-1/6x1-11/12x2
и подставим во все выражения.
x0 = -2+x1+2(1-1/6x1-11/12x2)
x5 = 13/13-7/13x1-3/13(1-1/6x1-11/12x2)
x4 = 5/13-3/13x1+8/13(1-1/6x1-11/12x2)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 0+2/3x1-21/6x2
x3 = 1-1/6x1-11/12x2
x5 = 1-1/2x1+1/4x2
x4 = 1-1/3x1-2/3x2
Полагая небазисные переменные x = (3, 5, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-2/3, 21/6, 0, 0, 0), x0 = 0
max(2/3,-21/6,0,0,0) = 2/3
x0 = 0+2/3x1-21/6x2
x3 = 1-1/6x1-11/12x2
x5 = 1-1/2x1+1/4x2
x4 = 1-1/3x1-2/3x2
В качестве новой переменной выбираем x1.
Вычислим значения D1 по всем уравнениям для этой переменной.
и из них выберем наименьшее:
min (1 : 1/6 , 1 : 1/2 , 1 : 1/3 ) = 2
Вместо переменной x5 в план войдет переменная x1.
Выразим переменную x1 через x5
x1 = 2+1/2x2-2x5
и подставим во все выражения.
x0 = 0+2/3(2+1/2x2-2x5)-21/6x2
x3 = 1-1/6(2+1/2x2-2x5)-11/12x2
x4 = 1-1/3(2+1/2x2-2x5)-2/3x2
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 11/3-15/6x2-11/3x5
x3 = 2/3-11/6x2+1/3x5
x1 = 2+1/2x2-2x5
x4 = 1/3-5/6x2+2/3x5
Полагая небазисные переменные x = (3, 1, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 15/6, 0, 0, 11/3), x0 = 11/3
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 11/3-15/6x2-11/3x5
x3 = 2/3-11/6x2+1/3x5
x1 = 2+1/2x2-2x5
x4 = 1/3-5/6x2+2/3x5
Оптимальный план можно записать так:
x1 = 2
x3 = 2/3
x4 = 1/3
F(X) = 3•2/3 + 0•2 = 11/3
Примечание:
- Число операций в симплекс-методе не превосходит n!/((n-m)!*m!)
- Решение х системы уравнений, в котором все небазисные переменные равны 0, называется базисным решение.
- Если все компоненты базисного решения неотрицательны, то оно называется допустимым базисным решение или опорным планом.
