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

ВАРИАНТ 2

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

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

1) f=x1-x2max,

x1,x20,

x1+x21,

x1-2x22,

2x1+3x22,

3x1+2x23,

x1+x21/2.

Построим множество, ограниченное прямыми ½=x1+x2, x1+x2=1, x12x2=1, 2x1+3x2=2. 3x1+2x2=3. (используем МAРLE)

> 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.

2) f=x1-x2min,

x1,x20,

x1+x21,

x1-2x22,

2x1+3x22,

3x1+2x23,

x1+x21/2.

Построим множество, ограниченное прямыми ½=x1+x2, x1+x2=1, x12x2=1, 2x1+3x2=2. 3x1+2x2=3. (используем МAРLE)

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

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

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.

> maximize(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});

3) f=x1+x2min,

0x11,

0x21,

0x1+ x23,

-1x1-x20,

Построим множество, ограниченное прямыми:

with(plots);

> inequal( { x1>=0,x1<=1,x2>=0,x2<=1,x1+x2>=0,x1+x2<=3,x1-x2>=-1,x1-x2<=0}, x1=-1.3, x2=-0.5.4 );

> with(simplex);minimize(x1+x2,{x1>=0,x1<=1,x2>=0,x2<=1,x1+x2>=0,

x1+x2<=3,x1-x2>=-1,x1-x2<=0});

{x1 = 0, x2 = 0}

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

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

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

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

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

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

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);

4) f=x1+x2max,

0x11,

0x21,

0x1+ x23,

-1x1-x20,

Построим множество, ограниченное прямыми:

with(plots);

> inequal( { x1>=0,x1<=1,x2>=0,x2<=1,x1+x2>=0,x1+x2<=3,x1-x2>=-1,x1-x2<=0}, x1=-1.1, x2=-0.4 );

> with(simplex);maximize(x1+x2,{x1>=0,x1<=1,x2>=0,x2<=1,

x1+x2>=0,x1+x2<=3,x1-x2>=-1,x1-x2<=0});

{x1 = 1, x2 = 1}

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

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

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);

3. Симплекс – метод

Использовать искусственный базис. Составить решение двойственной задачи по решению прямой задачи. Заметим, что решением задачи является пара (x, f(x)), если (y, g(y)) – решение двойственной задачи, то компоненты вектора y – произвольные числа, когда прямая задача записана в канонической форме. Проверить и записать решения тех и других задач на MAPLE.

1. f=-x1-11x2-x3-2x4+x5 min,

2x1+6x2+x3+x4+x5=13,

2x1+5x2+x4=11,

x1-x2+x5=1.

Решим задачу используя искусственный базис Составим вспомогательную задачу

G=U1+U2+U3min,

U1+2x1+6x2+x3+x4+x5=13,

U2+2x1+5x2+x4=11,

U3+ x1-x2+x5=1.

Из каждого равенства ограничений выражаем U1 U2 U3 через свободные переменные x1 x2 x3 x4 x5 и подставляем эти значения для целевой функции G Получим

G=25(5x1+ 10x2+x3 +2x4+2x5)

При такой записи вспомогательной задачи мы уже можем составить первую симплекстаблицу

Б п x1 x2 x3 x4 x5 Свчл

2 6 1 1 1 13

2 5 0 1 0 11

1 -1 0 0 1 1

G 5

10

1

2

2

25

Выбираем разрешающий столбец 1:

Для созания таблиц используем программу

program D;

const n=6;m=4;

type massiv=Array[1.m,1.n] of real;

type Nomer=set of 1. 11;

var i,j,k,t:integer;

a,L:massiv; h:real;

ch:char; var Isprasre:Nomer;

procedure wwod;

var k,t:integer;

begin

writeln(' Enter');

for k:=1 to m do for t:=1 to n do readln(a[k,t]); end;

procedure writ;

var k,t:integer;

begin

for k:=1 to m do begin

for t:=1 to n do write(a[k,t]:3:2,' ');

writeln; end;

end;

function rasre(j:integer):integer;

var k,t:integer; g:real;

begin

k:=1;

while (a[k,j]<=0) do k:=k+1;

rasre:=k; g:=a[k,n]/a[k,j];

if kfor t:=k+1 to m do if (not(t in Isprasre)) and (a[t,j]>0)

and(a[t,n]/a[t,j]begin g:=a[t,n]/a[t,j]; rasre:=t end; end;

procedure postab;

var k,t:integer;

begin for k:=1 to n do L[i,k]:=a[i,k]/h;

for t:=1 to m do if t<>i then

for k:=1 to n do L[t,k]:=a[t,k]-a[t,j]*L[i,k]; for k:=1 to n do

for t:=1 to m do a[t,k]:=L[t,k] end;

begin

Isprasre:=[];

wwod;

repeat

write ('vvedite nomer stolbsa');

readln (j);

i:=rasre(j); h:=a[i,j]; postab; writ;

writeln('y/n');read(ch); until ch<>'y'

end.

Выбираем разрешающий столбец2:

Выбираем разрешающий столбец 3 4:

Таким образом задача решена поскольку G приняла оптимальное значение 0 Решив вспомогательную задачу мы тем самым нашли базис для основной задачи. Базисом будет A1 A2 A4 а базисными переменными являются x3 x1 x4 Выразим базисные переменные x3 x1 x4 через свободные переменные x2 x5 используя последнюю таблицу Получим

x3 =2,29-x2 -0,x5 x4 =2,295,67x2 +0,71x5 x1 = 2+0,67x2 0,33x5

Подставим эти значения в выражение для функции f основной задачи Получим

f = -14-(-0,6x2-0,71x5) min.

> minimize(-x1-7*x2-2*x3-x4+x5 ,{6*x1+3*x2+x3+x4+x5=20,4*x1+3*x2+x4=12,3*x1-2*x2+x5=6

},NONNEGATIVE);