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