Симплекс метод

 
Итерация №3. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x₅, так как это наибольший коэффициент по модулю. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i5 
и из них выберем наименьшее: 
Следовательно, 1-ая строка является ведущей. 
Разрешающий элемент равен (¹²/₂₃) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

min

x4

921/23

18/23

0

0

1

-4/23

7/23

12/23

4/23

-7/23

19

x3

88/23

-9/23

0

1

0

-2/23

-7/23

-5/23

-2/23

7/23

5/23

-

x2

511/23

2/23

1

0

0

3/23

-1/23

-4/23

3/23

1/23

4/23

42

F(X4)

-2412/23

32/23

0

0

0

22/23

119/23

13/23+M

-22/23+M

-119/23+M

0

 
 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	19	27/12	0	0	111/12	1	-1/3	7/12	1	1/3	-7/12
x3	10	-1/6	0	1	1/6	0	-1/3	-1/6	0	1/3	1/6
x2	3	-1/4	1	0	-1/4	0	0	-1/4	0	0	1/4
F(X4)	11	711/12	0	0	37/12	0	1/3	211/12	3+M	-1/3+M	-211/12+M

 
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план 
Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	19	27/12	0	0	111/12	1	-1/3	7/12	1	1/3	-7/12
x3	10	-1/6	0	1	1/6	0	-1/3	-1/6	0	1/3	1/6
x2	3	-1/4	1	0	-1/4	0	0	-1/4	0	0	1/4
F(X5)	11	711/12	0	0	37/12	0	1/3	211/12	3+M	-1/3+M	-211/12+M

 
Оптимальный план можно записать так: 
x₅ = 19 
x₃ = 10 
x₂ = 3 
F(X) = 3•19 + -4•10 + -2•3 = 11 
Составим двойственную задачу к прямой задаче. 
2y₁ - y₃=>1 
3y₁ - 2y₂ + 4y₃=>-2 
- y₁ + 3y₂=>-4 
y₁ + y₂ - y₃=>2 
y₁=>3 
18y₁ + 24y₂ + 12y₃ → min 
y₂ <= 0 
y₃ <= 0 
Решение двойственной задачи дает оптимальную систему оценок ресурсов. 
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. 
Из теоремы двойственности следует, что Y = C*A^-1. 
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

A = (A5, A3, A2, ) =

1 -1 3 0 3 -2 0 0 4

 
Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

D = A-1 =

1 1/3 -7/12 0 1/3 1/6 0 0 1/4

 
Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных. 
Тогда Y = C*A^-1 =

(3, -4, -2) x

1 1/3 -7/12 0 1/3 1/6 0 0 1/4

= (3;-1/3;-35/12)

 
Оптимальный план двойственной задачи равен: 
y₁ = 3 
y₂ = ^-1/₃ 
y₃ = -2¹¹/₁₂ 
Z(Y) = 18*3+24*^-1/₃+12*-2¹¹/₁₂ = 11

 

 

 

 

Симплекс-метод

Решим прямую задачу линейного программирования симплексным  методом, с использованием симплексной  таблицы. 
Определим максимальное значение целевой функции F(X) = 3x₁ + 2x₃ - 6x₆ при следующих условиях-ограничений. 
2x₁ + x₂ - 3x₃ + 6x₆=18 
- 3x₁ + 2x₃ + x₄ - 2x₆=24 
x₁ + 3x₃ + x₅ - 4x₆=36 
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 
2x₁ + 1x₂-3x₃ + 0x₄ + 0x₅ + 6x₆ = 18 
-3x₁ + 0x₂ + 2x₃ + 1x₄ + 0x₅-2x₆ = 24 
1x₁ + 0x₂ + 3x₃ + 0x₄ + 1x₅-4x₆ = 36 
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =

2 1 -3 0 0 6 -3 0 2 1 0 -2 1 0 3 0 1 -4

 
Решим систему уравнений относительно базисных переменных: 
x₂, x₄, x₅, 
Полагая, что свободные переменные равны 0, получим первый опорный план: 
X1 = (0,18,0,24,36,0)

Базис	B	x1	x2	x3	x4	x5	x6
x2	18	2	1	-3	0	0	6
x4	24	-3	0	2	1	0	-2
x5	36	1	0	3	0	1	-4
F(X0)	0	-3	0	-2	0	0	6

 
Переходим к основному алгоритму  симплекс-метода. 
Итерация №0. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 
и из них выберем наименьшее: 
Следовательно, 1-ая строка является ведущей. 
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x2	18	2	1	-3	0	0	6	9
x4	24	-3	0	2	1	0	-2	-
x5	36	1	0	3	0	1	-4	36
F(X1)	0	-3	0	-2	0	0	6	0

 
 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x1	9	1	1/2	-11/2	0	0	3
x4	51	0	11/2	-21/2	1	0	7
x5	27	0	-1/2	41/2	0	1	-7
F(X1)	27	0	11/2	-61/2	0	0	15

 
Итерация №1. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 
и из них выберем наименьшее: 
Следовательно, 3-ая строка является ведущей. 
Разрешающий элемент равен (4¹/₂) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x1	9	1	1/2	-11/2	0	0	3	-
x4	51	0	11/2	-21/2	1	0	7	-
x5	27	0	-1/2	0	1	-7	6
F(X2)	27	0	11/2	0	0	15	0