Лабораторная работа №1.  Решение задачи

     линейного программирования

1. Решение задачи геометрическим способом.

2. Решение задачи с помощью симплекс-таблицы.

3. Решение задачи с помощью программы simplecs.

Входные данные:

 N – число переменных;

 М – число ограничений;

 eps – точность;

 ip–признак вида задачи (если на максимум ,то ip=1,если на минимум, то ip=0);

 T[i] – коэффициенты целевой функции;

 S – массив из М–2 чисел ,содержащий правые части системы;

 R – массив из (М–2)* N чисел, содержащий коэффициенты при неизвестных в системе ограничений.

     Выходные данные:

 ip–признак окончания решения( ip=1–найдено оптимальное решение; ip=2–задача не имеет решения; ip =3– целевая функция не ограничена);

 nb– массив ,содержащий номера переменных в массиве x;

 x–массив из М чисел ,содержащий оптимальное решение;

 f–оптимальное значение целевой функции.

Пример. Найти максимальное значение целевой функции

, , , .

    Текст программы.

program simplecs;

type mas=array[1..100] of real;

mas1=array[1..100] of integer;

var

    r,s,t,a,u,x,xk:mas;

    nb:mas1;

   i,l,k,z1,mi,m1,ni,ne,ip,m,n:integer;

    eps,tmin,teta:real;

procedure sol00(r,s,t:mas;var a,x:mas; n,m:integer);

var k1,k2,k3,j,mj,l,i:integer;

BEGIN

  l:=m-2;

for j:=1 to n do

begin

mj:=m*j;

a[mj]:=0;

for i:=1 to l do

begin

k1:=m*(j-1)+i;

 k2:=l*(j-1)+i;

a[k1]:=r[k2];

a[mj]:=a[mj]-r[k2];

end;

end;

for i:=1 to n do

begin

k3:=m*i-1;

a[k3]:=t[i];

end;

x[m-1]:=0;

x[m]:=0;

for i:=1 to l do

begin

x[i]:=s[i];

x[m]:=x[m]-x[i];

end;END;

 procedure sol01(var u:mas;m:integer);

 var i,j,l:integer;

BEGIN

for j:=1 to m do

for i:=1 to m do

begin

l:=m*(j-1)+i;

u[l]:=0;

if (i-j)=0 then

u[l]:=1;

end;

END;

procedure sol02(u,a:mas;m,n,j:integer;var del:real);

var i,im,ij:integer;

begin

del:=0;

for i:=1 to m do

begin

im:=i*m;

ij:=m*(j-1)+i;

del:=del+u[im]*a[ij];

end;

EnD;

procedure sol03(var tmin:real;a,u:mas;nb:mas1;m,n:integer;var k:integer);

          var bul,i,j,m1:integer;

          del:real;

begin

tmin:=0;

m1:=m-2;

for j:=1 to n do

begin

bul:=1;

i:=1;

while (bul=1) and (i<=m1) do

if (j-nb[i])=0 then bul:=2

else

i:=i+1;

if bul<>2 then

begin

sol02(u,a,m,n,j,del);

if (del-tmin)<=0 then

begin

tmin:=del;

k:=j;

end;

end;

end;

end;

procedure sol04(u,a:mas;m,n,k:integer;var xk:mas);

var

   ij,jk,i,j:integer;

begin

for i:=1 to m do

begin

xk[i]:=0;

for j:=1 to m do

begin

ij:=m*(j-1)+i;

jk:=m*(k-1)+j;

xk[i]:=xk[i]+u[ij]*a[jk];

end;

end;

end;

 procedure sol05(x,xk:mas;m:integer;var l:integer;var teta:real;eps:real);

 var

i,m1:integer;

r:real;

begin

teta:=10000;

  m1:=m-2;

for i:=1 to m1 do

if(xk[i]-eps)>=0 then

begin

r:=x[i]/xk[i];

if (r-teta)<=0 then

begin

teta:=r;

l:=i;

end;

end;

end;

procedure sol06(var x,xk:mas;m,l:integer;var teta:real);

var i:integer;

begin

for i:=1 to m do begin

If (i-l)<>0 then

x[i]:=x[i]-teta*xk[i]

else

x[i]:=teta;

end;

end;

procedure sol07(var u:mas;m,l:integer;xk:mas);

var

   m1,j,lj,i,ij:integer;

  begin

m1:=m-2;

for j:=1 to m1 do

  begin

lj:=m*(j-1)+l;

u[lj]:=u[lj]/xk[l];

end;

for i:=1 to m do

for j:=1 to m1 do

if (i-l)<>0 then

begin

ij:=m*(j-1)+i;

lj:=m*(j-1)+l;

u[ij]:=u[ij]-u[lj]*xk[i];

end;

end;

procedure sol08(u,a:mas;m,j:integer;var del:real);

var mi,ij,i:integer;

begin

del:=0;

for i:=1 to m do

begin

mi:=m*i-1;

ij:=m*(j-1)+i;

del:=del+u[mi]*a[ij];

end;

end ;

 procedure sol09(var tmin:real;var k:integer;a,u:mas;nb:mas1;m,n:integer);

 var bul,m1,i,j:integer;

del:real;

begin

tmin:=0;

m1:=m-2;

for j:= 1 to n do

begin

bul:=1;

i:=1;

while (bul=1) and (i<=m1) do

if (j-nb[i])=0 then

bul:=2

else

i:=i+1;

if bul<>2 then

begin

sol08(u,a,m,j,del);

if (del-tmin)<=0 then

begin

tmin:=del;

k:=j;

end;

end;

end;

end;

procedure sol10(var tmin:real;u,a:mas;nb:mas1;m,n:integer;var k:integer;

eps:real);

 var bul,m1,i,j:integer;

del,del1:real;

begin

  tmin:=0;

  m1:=m-2;

for j:=1 to n do

begin

   bul:=1;

   i:=1;

while (bul=1) and (i<=m1) do

    if (j-nb[i])=0 then

      bul:=2

      else

i:=i+1;

if bul<>2 then

begin

sol02(u,a,m,n,j,del);

sol08(u,a,m,j,del1);

if (abs(del1)-eps)<=0 then

if (del-tmin)<=0 then

begin

tmin:=del;

k:=j;

end;

end;

end;

end;

BEGIN

write(‘ n’);

read(n);

writeln(‘m’);readln(m);

writeln(' (eps)=>');read(eps);

writeln('ip(ip=1 if MAKS;ip=0 if MIN )=>');

read(ip);

for i:=1 to n do

begin

writeln('t[',i, ']= ');

read(t[i]);

end;

for i:=1 to m-2 do

begin

writeln('s[',i, ']= ');

read(s[i]);

end;

for i:=1 to (m-2)*n do

begin

writeln('r[',i, ']= ' );

read(r[i]);end;

sol00(r,s,t,a,x,n,m);

if (ip-1)=0 then

for i:=1 to n do

begin

mi:=m*i-1;

a[mi]:=-a[mi];

 end;

sol01(u,m);

m1:=m-2;

for i:=1 to m1 do

nb[i]:=100011+i;

ni:=0;

ne:=1;

3: sol03(tmin,a,u,nb,m,n,k);

2: if (tmin+eps)>=0 then

if (ne)=1 then

if (x[m]+eps)>=0 then

begin

ne:=2;

for i:=1 to m1 do

if (nb[i]-10000)>0 then

ne:=3 ;

if ne=3 then

begin

sol10(tmin,u,a,nb,m,n,k,eps);

goto 2;

end else

begin

sol09(tmin,k,a,u,nb,m,n);

goto 2;

 end;end else

begin

ip:=2;

goto 10;

end

else

if (ip-1)<>0 then

begin

x[m-1]:=-x[m-1];

ip:=1;

goto 10;

end

else

begin

ip:=1;

goto 10;

end

else

begin

sol04(u,a,m,n,k,xk);

sol05(x,xk,m,l,teta,eps);

if (teta+5-10000)<0 then

begin

sol06(x,xk,m,l,teta);

sol07(u,m,l,xk);

nb[l]:=k;

ni:=ni+1;

if ne<>1 then

if ne=2 then

begin

sol09(tmin,k,a,u,nb,m,n);

goto 2;

end

else

begin

sol10(tmin,u,a,nb,m,n,k,eps);

goto 2;

end

else

goto 3 ;end

else

begin

ip:=3;

goto 10;

end; end;

10: writeln('ip=',ip);

 if ip=1 then begin

for i:=1 to m-2 do

   writeln('x[', nb[i], ']=',x[i]:13);

   for i:=1 to m-2 do

   writeln('nb[',i,']=',nb[i]);end;

   writeln('f=', x[m-1]:13);

   readln; readln;readln;

END.

Входные данные:

N=6

M=6

EPS=0.1e–6

ip=1

10 –1 –9 –8 0 0

 2 5 1 10

–2 1 3 1 0 0

–5 2 0 3 0 0 

 7 –4 1 4 1 0

 3 2 5 6 0 1

Результаты расчета:

ip=1

x(1)=0.1428e+0000

x(2)=0.1142e+0001

x(4)=0.1142e+0001

x(6)=0.4285e+0000

f =-0.8857e+0001

    Варианты заданий.

1 f(x)=x1 + x2  max (min) x1 + 2x2 14 -5x1 – 3x2 15 2x1 – 3x2 12	2 f(x) =5x1 + 4x2 max(min) x1 - 2x2 6 -x1 + x2 8 x1 – x2 10
3 f(x)=3x1 + 2x2 max(min) x1 + x2 6 x1 – 2x2 4 x1 – 3x2 3	4 f(x)=5x1 + 4x2 max(min) x1 + x2 18 5x1 – x2 20 x1 – x2 8
5 f(x)=x1 + 3x2  max (min) 2x1 + x2 6 -x1 – 3x2 6 x1 + 2x2 8	6 f(x)=2x1+3x2 max(min) 2x1 + x2 10 -2x1 + 3x2 6 x1 + x2 8
7 f(x)=x1 + 4x2 max (min) -x1 + 5x2 20 3x1 – x2 15 x1 + x2 6	8 f(x)=6x1 + 2x2 max(min) x1 - x2 4 -x1 + 3x2 6 x1 – x2 3
9 f(x)=5x1 + 7x2 max (min) 5x1 - 6x2 30 -3x1 + 14x2 42 x1 + 4x2 28	10 f(x)=x1 + 2x2 max (min) x1 + 3x2 6 -x1 + x2 1 3x1 – x2 6
11 f(x)=3x1 − 2x2 max (min) x1 + 2x2 8 -2x1 + x2 2 x1 – x2 12	12 f(x)=2x1+3x2 max (min) x1 + x2 10 -2x1 + 3x2 6 x1 – x2 4
13 f(x)=3x1+2x2 max (min) 2x1 + x2 8  x1 + 3x2 6	14 f(x)=x1 + 4x2 max (min) 2x1 + x2 6 x1 + 3x2 9
15 f(x)=x1 + x2 max (min) 3x1 + 4x2 12 2x1 – x2 6	16 f(x)=2x1 + 3x2 max (min) x1 + 4x2 12 x1 + x2 4
17 f(x)=x1 + 2x2 max (min) 5x1 + 4x2 20 3x1 – x2 6	18 f(x)=x1 + x2  max (min) x1 + 2x2 8 6x1 – x2 3
19 f(x)=x1 + 5x2 max (min) 2x1 + x2 24 -x1 + x2 12   
	Последнее изменение этой страницы: 2018-04-12; просмотров: 159. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...