1. Решение симплекс-методом задачи линейного программирования. Составление и решение двойственной задачи. Вариант № 2

f (x)= x₁-3x₂-7x₃+5x₄max

x₁+x₂-3x₃-x₄≥8

5x₁+x₂+x₃+7x₄≤80

x₁-x₂+2x₃+2x₄=16

РЕШЕНИЕ.

Приведем задачу к каноническому виду, т.е. все неравенства представим в виде равенств, введя дополнительные переменные:

В уравнение (1) с «-»

В уравнение (2) с «+»

S (x)= x₁-3x₂-7x₃+5x₄+0х₅+0х₆max

x₁+x₂-3x₃-x₄-х₅=8

5x₁+x₂+x₃+7x₄+х₆=80

x₁-x₂+2x₃+2x₄=16

Для создания базиса введем искусственные переменные x_7, x₈. Дополнительные переменные входят в целевую функцию с коэффициентом 0, а искусственные с коэффициентом (-M).

Тогда целевая функция примет следующий вид:

f(x) max = x₁-3x₂-7x₃+5x₄+0х₅+0х₆-М_х7-М_х8max

x₁-x₂+2x₃+2x₄ +х₈=16

х₇=8

х₀= х₆=80 х₁=х₂=х₃=х₄=х₅=0

х₈=16

f(x⁰)=0-3*0-7*0+5*0+0*0+0*80-М*8-М*16=0-24М

Составим первую симплексную таблицу.

Таблица 1.

i	базис	Сбаз	А0	1	-3	-7	5	0	0	- М	-М
				A1	A2	A3	A4	A5	A6	A7	A8
1	А7	-М	8	1	1	-3	-1	-1	0	1	0
2	А6	0	80	5	1	1	7	0	1	0	0
3	А8	- М	16	1	-1	2	2	0	0	0	1
m+1	Zj-Cj		0	-1	3	7	-5	0	0	0	0
m+2	Zj-Cj		-24	-2	0	1	-1	1	0	0	0

Проверяем оптимальность данного плана по m+2 строке.

Z₁-C₁= - М*1+0*5-М-1= - М - М-1= - 2М-1

Z₂-C₂= - М*1+0*1+М-3= - М +М+3= 3

Z₃-C₃= 3М+0*1-2М+7= М +7

Z₄-C₄= М+0*7-2М-5= - М -5

Z₅-C₅= М+0*0-0= М

Z₆-C₆= 0

Z₇-C₇= 0

Z₈-C₈= 0

План не оптимален, т.к. есть отрицательные элементы в m+2 строке для столбцов А1 и А4.

Выбираем наибольшее по модулю отрицательное число из m+2 строки: -2. Следовательно вектор А1 включаем в базис.

Выбираем вектор который будем исключать из базиса

Θ=min(8/1;80/5;16/1)=8/1=2 => ключевой элемент 1, исключаем из базиса вектор А7.

Для этого применим метод Жордана-Гаусса (чтобы у вектора А1 были координаты как сейчас у вектора А7).

8 80	1 5	1 1	-3 1	-1 7	-1 0	0 1	1 0	0 0
16	1	-1	2	2	0	0	0	1

1)1 строка остается неизменной

2)1 строку умножаем на 5, получаем

40 5 5 -15 -5 -5 0 5 0

3) результат п.2 вычитаем из 2-ой строки, получаем новую 2 строку

40 0 -4 16 12 5 1 -5 0

4) из 3 стр. вычитаем 1 строку и получаем 3 стр.

8 0 -2 5 3 1 0 -1 1

Составим вторую симплексную таблицу.

Таблица 2.

i	базис	Сбаз	А0	1	-3	-7	5	0	0	- М	-М
				A1	A2	A3	A4	A5	A6	A7	A8
1	А1	1	8	1	1	-3	-1	-1	0	1	0
2	А6	0	40	0	-4	16	12	5	1	-5	0
3	А8	- М	8	0	-2	5	3	1	0	-1	1
m+1	Zj-Cj		8	0	4	4	-6	-1	0	1	0
m+2	Zj-Cj		8	0	2	-5	-3	-1	0	2	0

План не оптимален, т.к. в m+2 строке с А3 по А5 столбец есть отрицательные элементы. Выбираем наибольшее по модулю отрицательное число из m+2 строки: -5. Следовательно будем включать в базис вектор А3.

Выбираем вектор, который будем исключать из базиса

Θ=min(8/-3; 40/16; 8/5)=8/5 => ключевой элемент 5, исключаем из базиса вектор А8.

Для этого применим метод Жордана-Гаусса (чтобы у вектора А3 были координаты как сейчас у вектора А8).

8	1	1	-3	-1	-1	0	1	0
40	0	-4	16	12	5	1	-5	0
8	0	-2	5	3	1	0	-1	1

1) 3 стр. делим на 5, получаем новую 3 стр.

1,6 0 -0,4 1 0,6 0,2 0 -0,2 0,2

2) 3 стр.умножаем на 16, получаем

25,6 0 -6,4 16 9,6 3,2 0 -3,2 3,2

3) результат п. 2 вычитаем из 2 стр., получаем новую 2 стр.

14,4 0 2,4 0 2,4 1,8 1 -1,8 -3,2

4) 3 стр. умножаем на 3, получаем

4,8 0 -1,2 3 1,8 0,6 0 -0,6 0,6

5)результат п. 4 складываем с 1 стр., получаем новую 1 стр.

12,8 1 -0,2 0 0,8 -0,4 0 0,4 0,6

Составим третью симплексную таблицу.

Таблица 3.

i	базис	Сбаз	А0	1	-3	-7	5	0	0	- М	-М
				A1	A2	A3	A4	A5	A6	A7	A8
1	А1	1	12,8	1	-0,2	0	0,8	-0,4	0	0,4	0,6
2	А6	0	14,4	0	2,4	0	2,4	1,8	1	-1,8	-3,2
3	А3	-7	1,6	0	-0,4	1	0,6	0,2	0	-0,2	0,2
m+1	Zj-Cj		1,6	0	5,6	0	-8,4	-1,8	0	1,8	-0,8
m+2	Zj-Cj		0	0	0	0	0	0	0	1	1

Проверяем оптимальность данного плана по m+1 строке. План не оптимален, так как среди элементов m+1 строки есть отрицательные.

Выбираем наибольшее по модулю отрицательное число из m+1 строки: -8,4. Следовательно будем включать в базис вектор А4.

Выбираем вектор, который будем исключать из базиса

Θ=min(12,8/0,8; 14,4/2,4; 1,6/0,6)= 1,6/0,6 => ключевой элемент 0,6, исключаем из базиса вектор А3.

Для этого применим метод Жордана-Гаусса (чтобы у вектора А4 были координаты как сейчас у вектора А3).

12,8	1	-0,2	0	0,8	-0,4	0	0,4	0,6
14,4	0	2,4	0	2,4	1,8	1	-1,8	-3,2
1,6	0	-0,4	1	0,6	0,2	0	-0,2	0,2

1) стр. 3 делим на 0,6, получаем новую 3 стр.

2,666 0 9,333 1,666 1 0,333 0 -0,333 0,333

2) 3 стр. умножаем на 2,4

6, 3984 0 22,3992 3,9984 2,4 0,7992 0 -0,7992 0,7992

3) результат п. 2 вычитаем из 2 стр., получаем новую 2 стр.

8,0016 0 -19,9992 3,9984 0 1,0008 1 -1,0008 -3,9992

4) 3 стр. умножаем на 0,8

2,1328 0 7,4664 1,3328 0,8 0,2664 0 -0,2664 0,2664

5) результат п. 4 вычитаем из 1 стр., получаем новую 1 стр.

10,6672 1 -7,6664 -1,3328 0 -0,6664 0 0,6664 0,3336

Составим четвертую симплексную таблицу.

Таблица 4.

i	базис	Сбаз	А0	1	-3	-7	5	0	0	- М	-М
				A1	A2	A3	A4	A5	A6	A7	A8
1	А1	1	10,6672	1	-7,6664	-1,3328	0	-0,6664	0	0,6664	0,3336
2	А6	0	8,0016	0	-19,9992	3,9984	0	1,0008	1	-1,0008	-3,9992
3	А4	5	2,666	0	9,333	1,666	1	0,333	0	-0,333	0,333
m+1	Zj-Cj		23,9972	0	41,9986	13,9972	0	0,9986	0	-0,9986	1,9986

План оптимальный.

Z(X*)=23,9972

х₂=х₃=х₅=х₇=х₈=0 х₁=10,6672

х₆=8,0016

х₇=2,666

Составим двойственную задачу.

x₁+x₂-3x₃-x₄-х₅=8

5x₁+x₂+x₃+7x₄+х₆=80

x₁-x₂+2x₃+2x₄=16

Исходная задача Двойственная задача

max z =c*x min f=Y₀*A₀

AX=A₀ Y*A^T≥C

x≥0

max z= x₁-3x₂-7x₃+5x₄+0х₅+0х₆

1 способ:

y₁+5y₂+y₃≥1

y₁+y₂-y₃≥-3

-3y₁+y₂+2y₃≥-7

-y₁+7y₂+2y₃≥5

-y₁≥0

y₂≥0

min f= 8y₁+80y₂+16y₃

Оптимальный план для двойственной задачи

y^*=C^**D^-1 (A7;А6;А8)

y₁^*=z₇-c₇= - 0,9986

y₂^*=0

y₃^*=1,9986

min f=23,9888

2 способ:

Нахождение y^*

y^*=C^**D^-1

C ^*=(1;0;5)

D^-1 =(A7;А6;А8) 0,6664 0 0,3336

-1,0008 1 -3,9992

-0,333 0 0,333

y₁^*= = - 1,0026

y₂^*=0

y₃^*=32,0416

f min=24,0208