Исследование операций. Готовые лабораторные работы (5 вариантов готовых) - Лабораторная работа

1. Геометрический способ решения задач линейного программирования

Решить задачи своего варианта графически (преподаватель назначает номера задач (не менее четырех) для вашего варианта). Записать для решенных задач двойственные задачи и определить их решения, используя теорему о дополняющей нежесткости. Проверить и записать решения тех и других задач на MAPLE.

11) f(x )=x1x2max,

x1,x20,

1x1+x22,

2x12x23,

2x1+3x22.

Построим множество, ограниченное прямыми 1=x1+x2, x1+x2=2,

2=x12x2, x12x2=3, 2x1+3x2=2.

Данное множество не пересекает первую координатную четверть ни в одной точке, значит данная задача не имеет решения.

f(x )=x1x2max,

x1,x20,

-x1-x2-1

x1+x22,

x12x23,

-x1+2x2-2

2x1+3x22.

Формулировка двойственной задачи:

G(y)=-y1 +2y2+3 y3-2 y4+2 y5 min,

y1,y2, y3, y4, y5 0,

-y1 +y2+ y3- y4+2 y5 1,

-y1 +y2-2 y3+2 y4+3 y5 -1.

По теореме о дополняющей нежесткости получаем, что двойственная задача не имеет решения, т.к. если бы существовало решение двойственной задачи, то по нему можно было бы восстановить, исходя из теоремы, решение прямой задачи, а его нет.

> with(simplex);

> maximize(x1-x2,{x1+x2>=1,x1+x2<=2,x1-2*x2>=2,x1-2*x2<=3,2*x1+3*x2<=2},NONNEGATIVE);

7) f=x1-x2max,

x1,x20,

x1+x21,

x1-2x22,

2x1+3x22,

3x1+2x23,

x1+x21/2.

> inequal({y1>=0,y2>=0,y1+y2<=1,y1-2*y2<=1,2*y1+3*y2<=2,3*y1+2*y2<=3,y1+y2>=1/2},y1=-0.5.2,y2=0.1,optionsfeasible=(color=red),optionsopen=(color=blue,thickness=2),optionsclosed=(color=black,thickness=2),optionsexcluded=(color=white));

> with(simplex);maximize(x1-x2,{x1>=0,x2>=0,x1+x2<=1,x1-2*x2<=1,2*x1+3*x2<=2,3*x1+2*x2<=3,x1+x2>=1/2});

f=x1-x2max,

x1,x20,

x1+x21,

x1-2x21,

2x1+3x22,

3x1+2x23,

-x1-x2-1/2.

Формулировка двойственной задачи:

G(y)=y1 +y2+2 y3+3 y4-1/2 y5 min,

y1,y2, y3, y4, y5 0,

y1 +y2+2y3+3y4- y5 1,

y1 -2y2+3y3+2y4-y5 -1.

По теореме о дополняющей нежесткости получаем:

1(y1 +y2+2y3+3y4- y5-1)=0,

0 (y1 -2y2+3y3+2y4-y5 +1)=0,

y1(1-1)=0,

y2(1-1)=0,

y3(2-2)=0,

y4(3-3)=0,

y5(-1+1/2)=0.

Решение системы: бесконечное множество оптимальных планов;y5=0.

> minimize(y1+2*y2+3*y3+y4-1/2*y5, {y1>=0,y2>=0,y3>=0,y4>=0,y5>=0,-1 <= -2*y1+3*y2+2*y3+y4-y5, 1 <= y1+2*y2+3*y3+y4-y5});

т. е. Gmin(0,0,1/3,0,0)=1.

19) f=12x1-4x2max,

x1,x20,

-3x1-x2-4,

x1+5x21,

-2x1-2,

-x1+x20,

-x1-x2-1.

Построим множество

x1,x20, -3x1-x2-4,

x1+5x21,

-2x1-2,

-x1+x20,

-x1-x2-1.

Данная задача не имеет решения.

> maximize(12*x1-4*x2,{x1>=0,x2>=0,3*x1+x2>=4,-x1-5*x2>=-1,2*x1>=2,x1-x2>=0,x1+x2>=1});

f=12x1-4x2max,

x1,x20,

-3x1-x2-4,

x1+5x21,

-2x1-2,

-x1+x20,

-x1-x2-1.

Формулировка двойственной задачи:

G(y)=-4y1 +y2-2y3-y5min,

y1,y2, y3, y4 0,

-3y1 +y2- 2y3- y4 –y512,

-y1 +5y2+y4 –y5-4.

По теореме о дополняющей нежесткости получаем, что двойственная задача не имеет решения, т.к. если бы существовало решение двойственной задачи, то по нему можно было бы восстановить, исходя из теоремы, решение прямой задачи, а его нет.

31) f=2x14x2min,

x1,x20,

2x1-x2-1,

x1+2x21,

x1-x2-2,

5x1-3x2 15

2x1+3x26.

Построим множество

Вектор градиента направлен как (5\20,-11\20), значит, точка минимума функции будет располагаться на пересечении прямых 3x1+x2=8 и x1+x2=2. Т.е. x1=3\2, x2=7\2. fmin(3\2,7\2)=-31.

> minimize(5*x1-11*x2 ,{-2*x1+x2<=1,-x1+x2<=2,3*x1+x2<=8,-2*x1+3*x2>=-9,4*x1+3*x2>=0},NONNEGATIVE);

f=5x111x2min,

x1,x20,

2x1-x2-1,

x1-x2-2,

-3x1-x2-8,

2x1+3x29,

4x1+3x20.

Формулировка двойственной задачи:

G(y)=-y1 -2y2-8 y3 -9 y4 max,

y1,y2, y3, y4 , y50,

2y1 +y2- 3y3- 2y4 +4y5 5,

-y1 -y2- y3 +3y4 +3 y5-11.

По теореме о дополняющей нежесткости получаем:

3\2(2y1 +y2- 3y3- 2y4 +4y5 -5)=0,

7\2(-y1 -y2- y3 +3y4 +3 y5+11)=0,

y1 (3-7\2+1)=0,

y2 (3\2-7\2+2)=0,

y3 (-9\2-7\2+8)=0,

y4 (3+21\2+9)=0,

y5 (6+21\2)=0.

Получаем:

y1 =0, y4=0,y5 =0

y2- 3y3-5=0,

-y2- y3 +11=0, т.е:

y1 =0, y2 =19\2, y3 =3\2, y4=0,y5 =0.

> maximize(-y1-2*y2-8*y3-9*y4,{2*y1+y2-3*y3-2*y4+4*y5<=5,-y1-y2-y3+3*y4+3*y5<=-11},NONNEGATIVE);

1. Геометрический способ решения задач линейного программирования

Решить задачи своего варианта графически (преподаватель назначает номера задач (не менее четырех) для вашего варианта). Записать для решенных задач двойственные задачи и определить их решения, используя теорему о дополняющей нежесткости. Проверить и записать решения тех и других задач на MAPLE.

11) f(x )=x1x2max,

x1,x20,

1x1+x22,

2x12x23,

2x1+3x22.

Построим множество, ограниченное прямыми 1=x1+x2, x1+x2=2,

2=x12x2, x12x2=3, 2x1+3x2=2.

Данное множество не пересекает первую координатную четверть ни в одной точке, значит данная задача не имеет решения.

f(x )=x1x2max,

x1,x20,

-x1-x2-1

x1+x22,

x12x23,

-x1+2x2-2

2x1+3x22.

Формулировка двойственной задачи:

G(y)=-y1 +2y2+3 y3-2 y4+2 y5 min,

y1,y2, y3, y4, y5 0,

-y1 +y2+ y3- y4+2 y5 1,

-y1 +y2-2 y3+2 y4+3 y5 -1.

По теореме о дополняющей нежесткости получаем, что двойственная задача не имеет решения, т.к. если бы существовало решение двойственной задачи, то по нему можно было бы восстановить, исходя из теоремы, решение прямой задачи, а его нет.

> with(simplex);

> maximize(x1-x2,{x1+x2>=1,x1+x2<=2,x1-2*x2>=2,x1-2*x2<=3,2*x1+3*x2<=2},NONNEGATIVE);

7) f=x1-x2max,

x1,x20,

x1+x21,

x1-2x22,

2x1+3x22,

3x1+2x23,

x1+x21/2.

> inequal({y1>=0,y2>=0,y1+y2<=1,y1-2*y2<=1,2*y1+3*y2<=2,3*y1+2*y2<=3,y1+y2>=1/2},y1=-0.5.2,y2=0.1,optionsfeasible=(color=red),optionsopen=(color=blue,thickness=2),optionsclosed=(color=black,thickness=2),optionsexcluded=(color=white));

> with(simplex);maximize(x1-x2,{x1>=0,x2>=0,x1+x2<=1,x1-2*x2<=1,2*x1+3*x2<=2,3*x1+2*x2<=3,x1+x2>=1/2});

f=x1-x2max,

x1,x20,

x1+x21,

x1-2x21,

2x1+3x22,

3x1+2x23,

-x1-x2-1/2.

Формулировка двойственной задачи:

G(y)=y1 +y2+2 y3+3 y4-1/2 y5 min,

y1,y2, y3, y4, y5 0,

y1 +y2+2y3+3y4- y5 1,

y1 -2y2+3y3+2y4-y5 -1.

По теореме о дополняющей нежесткости получаем:

1(y1 +y2+2y3+3y4- y5-1)=0,

0 (y1 -2y2+3y3+2y4-y5 +1)=0,

y1(1-1)=0,

y2(1-1)=0,

y3(2-2)=0,

y4(3-3)=0,

y5(-1+1/2)=0.

Решение системы: бесконечное множество оптимальных планов;y5=0.

> minimize(y1+2*y2+3*y3+y4-1/2*y5, {y1>=0,y2>=0,y3>=0,y4>=0,y5>=0,-1 <= -2*y1+3*y2+2*y3+y4-y5, 1 <= y1+2*y2+3*y3+y4-y5});

т. е. Gmin(0,0,1/3,0,0)=1.

19) f=12x1-4x2max,

x1,x20,

-3x1-x2-4,

x1+5x21,

-2x1-2,

-x1+x20,

-x1-x2-1.

Построим множество

x1,x20, -3x1-x2-4,

x1+5x21,

-2x1-2,

-x1+x20,

-x1-x2-1.

Данная задача не имеет решения.

> maximize(12*x1-4*x2,{x1>=0,x2>=0,3*x1+x2>=4,-x1-5*x2>=-1,2*x1>=2,x1-x2>=0,x1+x2>=1});

f=12x1-4x2max,

x1,x20,

-3x1-x2-4,

x1+5x21,

-2x1-2,

-x1+x20,

-x1-x2-1.

Формулировка двойственной задачи:

G(y)=-4y1 +y2-2y3-y5min,

y1,y2, y3, y4 0,

-3y1 +y2- 2y3- y4 –y512,

-y1 +5y2+y4 –y5-4.

По теореме о дополняющей нежесткости получаем, что двойственная задача не имеет решения, т.к. если бы существовало решение двойственной задачи, то по нему можно было бы восстановить, исходя из теоремы, решение прямой задачи, а его нет.

31) f=2x14x2min,

x1,x20,

2x1-x2-1,

x1+2x21,

x1-x2-2,

5x1-3x2 15

2x1+3x26.

Построим множество

Вектор градиента направлен как (5\20,-11\20), значит, точка минимума функции будет располагаться на пересечении прямых 3x1+x2=8 и x1+x2=2. Т.е. x1=3\2, x2=7\2. fmin(3\2,7\2)=-31.

> minimize(5*x1-11*x2 ,{-2*x1+x2<=1,-x1+x2<=2,3*x1+x2<=8,-2*x1+3*x2>=-9,4*x1+3*x2>=0},NONNEGATIVE);

f=5x111x2min,

x1,x20,

2x1-x2-1,

x1-x2-2,

-3x1-x2-8,

2x1+3x29,

4x1+3x20.

Формулировка двойственной задачи:

G(y)=-y1 -2y2-8 y3 -9 y4 max,

y1,y2, y3, y4 , y50,

2y1 +y2- 3y3- 2y4 +4y5 5,

-y1 -y2- y3 +3y4 +3 y5-11.

По теореме о дополняющей нежесткости получаем:

3\2(2y1 +y2- 3y3- 2y4 +4y5 -5)=0,

7\2(-y1 -y2- y3 +3y4 +3 y5+11)=0,

y1 (3-7\2+1)=0,

y2 (3\2-7\2+2)=0,

y3 (-9\2-7\2+8)=0,

y4 (3+21\2+9)=0,

y5 (6+21\2)=0.

Получаем:

y1 =0, y4=0,y5 =0

y2- 3y3-5=0,

-y2- y3 +11=0, т.е:

y1 =0, y2 =19\2, y3 =3\2, y4=0,y5 =0.

> maximize(-y1-2*y2-8*y3-9*y4,{2*y1+y2-3*y3-2*y4+4*y5<=5,-y1-y2-y3+3*y4+3*y5<=-11},NONNEGATIVE);