Пример решения симплекс-методом в столбцовой форме записи
(Существуют и другие формы записи симплекс-метода)Решим прямую задачу линейного программирования симплексным методом, с использованием столбцовой формы (через калькулятор).
Определим максимальное значение целевой функции F(X) = 3x1+5x2+4x3 при следующих условиях-ограничений.
0.1x1+0.2x2+0.4x3≤1100
0.05x1+0.02x2+0.02x3≤120
3x1+x2+2x3≤8000
Для построения первого
опорного плана систему неравенств приведем к системе уравнений путем введения
дополнительных переменных (переход к канонической форме).
0.1x1 +
0.2x2 + 0.4x3 + 1x4 + 0x5 +
0x6 = 1100
0.05x1 + 0.02x2 +
0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 +
0x5 + 1x6 = 8000
Переходим к столбцовой форме
симплекс-метода. Выразим каждую переменную через небазисные.
x0 =
0-3(-x1)-5(-x2)-4(-x3)+0(-x4)+0(-x5)+0(-x6)
x1 =
0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x2 =
0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x3 =
0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 =
1100+0.1(-x1)+0.2(-x2)+0.4(-x3)+1(-x4)+0(-x5)+0(-x6)
x5 =
120+0.05(-x1)+0.02(-x2)+0.02(-x3)+0(-x4)+1(-x5)+0(-x6)
x6 =
8000+3(-x1)+1(-x2)+2(-x3)+0(-x4)+0(-x5)+1(-x6)
Данной системе соответствует таблица T0.
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1100 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
8000 |
3 |
1 |
2 |
0 |
0 |
1 |
0 |
-3 |
-5 |
-4 |
0 |
0 |
0 |
В качестве начальной допустимой базы можно взять B0 = <4, 5, 6>.
Поскольку задача решается на максимум, то ведущий столбец выбирают по минимальному отрицательному числу в последней строке.
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1100 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
8000 |
3 |
1 |
2 |
0 |
0 |
1 |
0 |
-3 |
-5 |
-4 |
0 |
0 |
0 |
В качестве направляющего выберем столбец, соответствующий переменной x2.
Вычислим значения Di по строкам как частное от деления.
и из них выберем наименьшее:
Чтобы теперь выразить все переменные через небазисные, в выражении для x4 выразим x2 и подставим полученное выражение во все остальные равенства.
x2 = 5500+0.5x1+5x4+2x3+5x4+0x5+0x6
После приведения подобных получим:
x0 = 27500-0.5(-x1)+0(-x2)+6(-x3)+25(-x4)+0(-x5)+0(-x6)
x1 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x2 = 5500+0.5(-x1)+0(-x2)+2(-x3)+5(-x4)+0(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x5 = 10+0.04(-x1)+0(-x2)-0.02(-x3)-0.1(-x4)+1(-x5)+0(-x6)
x6 = 2500+2.5(-x1)+0(-x2)+0(-x3)-5(-x4)+0(-x5)+1(-x6)
Представим в виде таблицы T1:
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
5500 |
0.5 |
0 |
2 |
5 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
10 |
0.04 |
0 |
-0.02 |
-0.1 |
1 |
0 |
2500 |
2.5 |
0 |
0 |
-5 |
0 |
1 |
27500 |
-0.5 |
0 |
6 |
25 |
0 |
0 |
Таким образом, очередная база равна B1 = <2, 5, 6>. Небазисные переменные следующие: N1 = <1, 3, 4>
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
5500 |
0.5 |
0 |
2 |
5 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
10 |
0.04 |
0 |
-0.02 |
-0.1 |
1 |
0 |
2500 |
2.5 |
0 |
0 |
-5 |
0 |
1 |
27500 |
-0.5 |
0 |
6 |
25 |
0 |
0 |
В качестве направляющего выберем столбец, соответствующий переменной x1.
Вычислим значения Di по строкам как частное от деления.
и из них выберем наименьшее:
Чтобы теперь выразить все переменные через небазисные, в выражении для x5 выразим x1 и подставим полученное выражение во все остальные равенства.
x1 = 250+25x5+0x2+-0.5x3+-2.5x4+25x5+0x6
После приведения подобных получим:
x0 = 27625+0(-x1)+0(-x2)+5.75(-x3)+23.75(-x4)+12.5(-x5)+0(-x6)
x1 = 250+0(-x1)+0(-x2)-0.5(-x3)-2.5(-x4)+25(-x5)+0(-x6)
x2 = 5375+0(-x1)+0(-x2)+2.25(-x3)+6.25(-x4)-12.5(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x5 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x6 = 1875+0(-x1)+0(-x2)+1.25(-x3)+1.25(-x4)-62.5(-x5)+1(-x6)
Представим в виде таблицы T2:
250 |
0 |
0 |
-0.5 |
-2.5 |
25 |
0 |
5375 |
0 |
0 |
2.25 |
6.25 |
-12.5 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1875 |
0 |
0 |
1.25 |
1.25 |
-62.5 |
1 |
27625 |
0 |
0 |
5.75 |
23.75 |
12.5 |
0 |
Таким образом, очередная база равна B2 = <2, 1, 6>. Небазисные переменные следующие: N2 = <3, 4, 5>
Последняя строка не содержит отрицательных элементов. Найден оптимальный план.
Окончательный вариант таблицы:
250 |
0 |
0 |
-0.5 |
-2.5 |
25 |
0 |
5375 |
0 |
0 |
2.25 |
6.25 |
-12.5 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1875 |
0 |
0 |
1.25 |
1.25 |
-62.5 |
1 |
27625 |
0 |
0 |
5.75 |
23.75 |
12.5 |
0 |
Оптимальный план можно записать так:
x2 = 5375
x1 = 250
x6 = 1875
F(X) = 5*5375 + 3*250 + 0*1875 = 27625
Примечание:
1. Для предотвращения зацикливания используется правило Бленда.
2. Столбец s, строка r и элемент trs называются направляющими.
3. Матрица T = t(ij) называется столбцовой симплекс-таблицей, соответствующей перестановке N.
