Пример решения симплекс-методом в столбцовой форме записи

(Существуют и другие формы записи симплекс-метода)

Решим прямую задачу линейного программирования симплексным методом, с использованием столбцовой формы (через калькулятор).
Определим максимальное значение целевой функции 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.

Перейти к онлайн решению своей задачи

загрузка...