Подробное решение симплекс-методом в базовой форме записи
Решим прямую задачу линейного программирования симплекс-методом.Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = -x1-2x2+6x3-x4 при следующих условиях-ограничений.
x1+x2-x3+x4≤1
x1-2x2+x3≥4
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус.
1x1 + 1x2-1x3 + 1x4 + 1x5 + 0x6 = 1
1x1-2x2 + 1x3 + 0x4 + 0x5-1x6 = 4
Введем искусственные переменные x: в 2-м равенстве вводим переменную x7;
1x1 + 1x2-1x3 + 1x4 + 1x5 + 0x6 + 0x7 = 1
1x1-2x2 + 1x3 + 0x4 + 0x5-1x6 + 1x7 = 4
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = Mx7 → min
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x7 = 4-x1+2x2-x3+x6
которые подставим в целевую функцию:
F(X) = M(4-x1+2x2-x3+x6) → min
или
F(X) = (-1M)x1+(2M)x2+(-1M)x3+()x4+(1M)x6+(4M) → min
Введем новую переменную x0 = -x1+2x2-x3.
Выразим базисные переменные <5, 7> через небазисные.
x0 = 4-x1+2x2-x3+x6
x5 = 1-x1-x2+x3-x4
x7 = 4-x1+2x2-x3+x6
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на минимум, то переменную для включения в текущий план выбирают по минимальному отрицательному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
max(-1,2,-1,0,0,1,0) = -1
1x1 + 1x2-1x3 + 1x4 + 1x5 + 0x6 + 0x7 = 1
x0 = 4-x1+2x2-x3+x6
x5 = 1-x1-x2+x3-x4
x7 = 4-x1+2x2-x3+x6
В качестве новой переменной выбираем x3.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai3
и из них выберем наименьшее:
Вместо переменной x7 в план войдет переменная x3.
4. Пересчет всех уравнений.
Выразим переменную x3 через x7
x3 = 4-x1+2x2+x6-x7
и подставим во все выражения.
x0 = 4-x1+2x2-(4-x1+2x2+x6-x7)+x6
x5 = 1-x1-x2+(4-x1+2x2+x6-x7)-x4
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 0+x7
x5 = 5-2x1+x2-x4+x6-x7
x3 = 4-x1+2x2+x6-x7
Полагая небазисные переменные x = (5, 3) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 0, 0, 0, 0, -1), x0 = 0
Выражение для x0 не содержит отрицательных элементов. Найден оптимальный план.
x0 = 0+x7
x5 = 5-2x1+x2-x4+x6-x7
x3 = 4-x1+2x2+x6-x7
На этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.
x5 = 5-2x1+x2-x4+x6
x3 = 4-x1+2x2+x6
Выразим базисные переменные:
x3 = 4-x1+2x2+x6
которые подставим в целевую функцию:
F(X) = -x1-2x2 + 6(4-x1+2x2+x6)-x4
или
F(X) = 24-7x1+10x2-x4+6x6
Получаем новую систему переменных.
x0 = 24-7x1+10x2-x4+6x6
x5 = 5-2x1+x2-x4+x6
x3 = 4-x1+2x2+x6
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
max(-7,10,0,-1,0,6) = -7
x0 = 24-7x1+10x2-x4+6x6
x5 = 5-2x1+x2-x4+x6
x3 = 4-x1+2x2+x6
В качестве новой переменной выбираем x1.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai1
и из них выберем наименьшее:
Вместо переменной x5 в план войдет переменная x1.
4. Пересчет всех уравнений.
Выразим переменную x1 через x5
x1 = 2.5+0.5x2-0.5x4-0.5x5+0.5x6
и подставим во все выражения.
x0 = 24-7(2.5+0.5x2-0.5x4-0.5x5+0.5x6)+10x2-x4+6x6
x3 = 4-(2.5+0.5x2-0.5x4-0.5x5+0.5x6)+2x2+x6
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 6.5+6.5x2+2.5x4+3.5x5+2.5x6
x1 = 2.5+0.5x2-0.5x4-0.5x5+0.5x6
x3 = 1.5+1.5x2+0.5x4+0.5x5+0.5x6
Полагая небазисные переменные x = (1, 3) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, -6.5, 0, -2.5, -3.5, -2.5), x0 = 6.5
Выражение для x0 не содержит отрицательных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 6.5+6.5x2+2.5x4+3.5x5+2.5x6
x1 = 2.5+0.5x2-0.5x4-0.5x5+0.5x6
x3 = 1.5+1.5x2+0.5x4+0.5x5+0.5x6
Оптимальный план можно записать так:
x1 = 2.5
x3 = 1.5
F(X) = -1*2.5 + 6*1.5 = 6.5