Cwiczenie 3 – Programowanie Liniowe

Rozwiązać problemy programowania liniowego, wykreślić przestrzeń optymalizacji i ograniczenia.

a – ilość liter w nazwisku

Zadanie 1
dana jest funkcja celu

f(X) = x

1

+ 2x

2

+ a

i ograniczenia

x

1

≥

1

x

2

≥

2

7/9x

1

+ x

2

≤

10

1/2x

1

- x

2

≤

1

wyznaczyć wartości zmiennych stanu (x

1

, x

2

) dla których funkcja celu osiąga minimum

Zadanie 2

Przedsiębiorstwo produkcyjne wytwarza 2 rodzaje produktów A i B, w ciągu godziny może
wyprodukować 14t wyrobu A lub 7t wyrobu B. Posiadany transport pozwala na przewiezienie w ciągu
godziny do 7t produktu A lub do 12t produktu B. Urządzenia załadowcze pozwalają załadować nie więcej
niż 8t dowolnego z produktów. Przedsiębiorstwo otrzymuje 5000 PLN/t produktu A i a*1000 PLN/t B.
Jaką ilość produktów na h przedsiębiorstwo powinno produkować. Założyć że nie istnieje problem
sprzedaży produkcji.

POLECENIA MATLABA

LP Programowanie liniowe.

Funkcja LP została zastąpiona przez funkcję LINPROG. LP jest obecnie dostępna, ale w przyszłości
zostanie usunięta z przybornika. Poleca się używanie LINPROG.

X=LP(f,A,b) rozwiązuje problem programowania liniowego:

min f'x przy ograniczeniach: Ax <= b x

X=LP(f,A,b,VLB,VUB) definiuje zbiór dolnych i górnych ograniczeń na zmienne decyzyjne, X, zatem
rozwiązanie jest zawsze w przedziale:
VLB <= X <= VUB.

X=LP(f,A,b,VLB,VUB,XO) ustawia warunek początkowy w punkcie X0.

X=LP (f,A,b,VLB,VUB,X0, N) wskazuje dodatkowo, że pierwszych N ograniczeń zdefiniowanych w A
i B są ograniczeniami równościowymi.
X=LP(f,A,b,VLB,VUB,X0,N,DISPLAY) dodatkowo włącza sterowanie ostrzeżeniami. Wyłącza się je poprzez:
DISPLAY = -l.
[x,LAMBDA]=LP(f,A,b) zwraca zbiór mnożników Lagrange'a, LAMBDA rozwiązania.

LP wysyła komunikat, jeśli rozwiązanie jest nieograniczone, lub niedopuszczalne.

»
help linprog

LINPROG Programowanie liniowe.

X=LINPROG(f,A,b) rozwiązuje problem programowania liniowego:

min f'*x przy ograniczeniach: A*x <= b

X=LINPROG(f,A,b,Aeq,beq) rozwiązuje powyższy problem, przy dodatkowych ograniczeniach równościowych:

Aeq*x = beq.

X=LINPROG(f,A,b,Aeq,beq,LB,UB) definiuje zbiór dolnych i górnych ograniczeń na zmienne decyzyjne, X, zatem
rozwiązanie jest zawsze w przedziale:

VLB <= X <== VUB.

Wykorzystaj puste macierze dla LB i UB, jeśli ograniczenia nie istnieją Przypisz LB(i) = -Inf if
X(i) jeśli brak ograniczenia dolnego;
Przypisz UB(i) = Inf if X(i) jeśli brak ograniczenia górnego.

X=LINPROG(f,A,b,Aeq,beq,LB,UB,XO) ustawia warunek początkowy w punkcie X0.

Opcja jest dostępna jedynie z algorytmem aktywnego zbioru. Domyślny algorytm punktu wewnętrznego
ignoruję punkt startowy.


X=LINPROG(f,A,b,Aeq,Beq,LB,UB,X0,OPTIONS) minimalizuje zastępując domyślne parametry optymalizacyjne
parametrami zawartymi z strukturze OPTIONS, utworzonej za pomocą funkcji OPTIMSET.

[X,FVAL]=LINPROG(f,A,b) zwraca wartość funkcji celu w X:

FVAL = f' *X.

[X,FVAL,EXITFLAG] = LINPROG(f,A,b) zwraca EXITFLAG zawierający warunek zakończenia LINPROG.
If EXITFLAG is:

> O then LINPROG dał rozwiązanie zbieżne do X.
O then LINPROG osiągnął maksymalną liczbę iteracji nie uzyskując
zbieżności
< O then problem jest nierozwiązywalny lub LINPROG nie zadziałał.

[X,FVAL,EXITFLAG,OUTPUT] = LINPROG(f,A,b) zwraca strukturę

OUTPUT z liczbą iteracji w OUTPUT.iterations, typem
algorytmu w OUTPUT.algorithm, liczbią operacji gradientowych (jeśli
wykorzystywane) w OUTPUT.cgiterations.

[X,FVAL,EXITFLAG,OUTPUT,LAMBDA]=LINPROG(f,A,b) zwraca mnożniki Lagrange'a
LAMBDA, dla rozwiązania: LAMBDA.ineqlin dla ograniczeń nierównościowych A,
LAMBDA.eqlin dla ograniczeń równościowych Aeq, LAMBDA.Iower dla LB, i
LAMBDA.upper dla UB.

Przykład

Elektrownia

składa się z dwóch wydziałów, wydziału produkującego energię elektryczną

i wydziału produkującego parę.

Wyprodukowanie 1t pary wymaga:

2.1

j.p.

środków finansowych,

0.4

węgla brunatnego,

0.045MWh

energii

elektrycznej,

zaś 1MWh
6

j.p.

środków finansowych,

5t

pary

wodnej.

Jedna tona węgla kosztuje 4 j.p., zaś cena sprzedaży 1t pary wodnej wynosi 6j.p, a 1MWh 40j.p.

Określić plan produkcji zapewniający maksymalny zysk, jeśli zasoby środków finansowych wynoszą
600 j.p. a węgla brunatnego 800t.
Oznaczamy

przez

x

1

ilość produkowanej pary a przez x

2

produkcje energii elektrycznej.

Elektrociepłownia powinna wytwarzać parę i energię elektryczną na sprzedaż więc:

x

1

– 5x

2

≥ 0

x

2

– 0.045x

1

≥ 0

zużycie węgla

0.4x

1

≤ 800

wartość zużytych środków finansowych

2.1x

1

+ 6x

2

≤ 600

produkcja nie może być ujemna

x

1

, x

2

≥ 0

Uzyskany efekt finansowy jest różnicą między środkami uzyskanymi ze sprzedaży a kosztami
wytwarzania:

f = 6(x

1

– 5x

2

) + 40(x

2

– 0.045x

1

) – (2.1x

1

+ 4(0.4x

1

) + 6x

2

) =

= 0.5x

1

+ 4x

2

Podsumowując
max { 0.5x

1

+ 4x

2

}

x

1

, x

2

∈

Ω



x

1

– 5x

2

≥ 0

Ω

:



x

2

– 0.045x

1

≥ 0

 0.4x

1

≤ 800

 2.1x

1

+ 6x

2

≤ 600



x

1

≥ 0



x

2

≥ 0

MALTAB



rozwiązuje zagadnienia:

min

f(X)

przy

ograniczeniach

AX

≤ b

Ostatecznie
min {-0.5x

1

– 4x

2

}

x

1

, x

2

∈

Ω



-x

1

+ 5x

2

≤ 0

Ω

:



0.045x

1

– x

2

≤ 0

 0.4x

1

≤ 800

 2.1x

1

+ 6x

2

≤ 600



-x

1

≤ 0



-x

2

≤ 0

Rozwiązanie problemu:

>> f=[-.5 -4];
>> A=[-1 5
0.045

-1

0.4

0

2.1

6

-1

0

0

-1];

>> b=[0 0 800 600 0 0]';
>> x=linprog(f,A,b)
Optimization terminated successfully

x =
181.8182
36.3636

Rys. 1 Przestrzeń optymalizacji z naniesionymi ograniczeniami

Skrypt kreślący funkcje przestrzeń optymalizacji z ograniczeniami z rysunku 1

clc
clear
f=[.5 4];
A=[-1 5
0.045

-1

0.4

0

2.1

6

-1

0

0

-1];

b=[0 0 800 600 0 0]';
x1=0:100:2100;
x2=[-5:4:70]';
X1=ones(length(x2),1)*x1;

X2=x2*ones(1,length(x1));
F=f(1)*X1 + f(2)*X2;
mesh(X1,X2,F)
hold on;
colormap([0 0 1]);
x2_1=1/5*x1;
ogr=f(1)*x1 + f(2)*x2_1;
indx=find(x2_1 >= min(x2) & x2_1 <= max(x2));
plot3(x1(indx),x2_1(indx),ogr(indx),'k','LineWidth',1.5)

x2_1=0.045*x1;
ogr=f(1)*x1 + f(2)*x2_1;
indx=find(x2_1 >= min(x2) & x2_1 <= max(x2));

plot3(x1(indx),x2_1(indx),ogr(indx),'k','LineWidth',1.5)

x1_1=ones(length(x2),1)*800/0.4;
ogr=f(1)*x1_1 + f(2)*x2;
indx=find(x1_1 >= min(x1) & x1_1 <= max(x1));
plot3(x1_1(indx),x2(indx),ogr(indx),'k','LineWidth',1.5)

x2_1=( 600 - 2.1*x1)/6;
ogr=f(1)*x1 + f(2)*x2_1;
indx=find(x2_1 >= min(x2) & x2_1 <= max(x2));
plot3(x1(indx),x2_1(indx),ogr(indx),'k','LineWidth',1.5)

x1_1=zeros(length(x2),1);
ogr=f(1)*x1_1 + f(2)*x2;
plot3(x1_1,x2,ogr,'k','LineWidth',1.5)

x2_1=zeros(1,length(x1));
ogr=f(1)*x1 + f(2)*x2_1;
plot3(x1,x2_1,ogr,'k','LineWidth',1.5)
clear x1_1 x2_1 indx X1 X2

x=linprog(-f,A,b);
plot3(x(1), x(2), f*x,'ro','MarkerEdgeColor','r',...
'MarkerFaceColor','r',...
'MarkerSize',7);

x=[x [0 ; 0] (A([2 4],:)\b([2 4])), x];
ogr=f(1)*x(1,:) + f(2)*x(2,:);
plot3(x(1,:), x(2,:), ogr,'r','LineWidth',3);

axis([min(x1) max(x1) min(x2) max(x2) min(F(:)) max(F(:))]);
xlabel('x1')
ylabel('x2')
zlabel('f')
clear F x1 x2 ogr
x=x(:,1);