Katedra Mechaniki Stosowanej i Robotyki

Wydział Budowy Maszyn i Lotnictwa, Politechnika Rzeszowska

TEORIA I METODY OPTYMALIZACJI

Laboratorium nr 02

Temat: Zadanie programowania liniowego – metoda graficzna

Damian Lew

Jakub Mikrut MRDU2 L1 4 17.10.2012 r.

Imię i nazwisko kierunek nr grupy zespół data wykonania ćwiczenia data, ocena, podpis

rok studiów

Wstęp teoretyczny

Zadanie optymalizacji statycznej, zwane również programowaniem matematycznym, można sformułować następująco:

Wyznaczyć wektor decyzyjny x, należący do zbioru rozwiązań dopuszczalnych x₀, dla którego funkcja f(x) osiąga ekstremum (minimum lub maksimum), czyli:

$$f\left( \hat{x} \right) = \operatorname{}{f(x)}\backslash n$$

Rozpatrywać będziemy tylko minimum, gdyż jak wiadomo zadanie maksymalizacji można sprowadzić do zadania minimalizacji korzystając z zależności:

f(x) = −[ − f(x)]

Funkcję f(x) nazywać będziemy funkcją celu lub wskaźnikiem jakości. W zagadnieniu sterowania funkcja f(x) wyraża różne wielkości techniczno-ekonomiczne, takie jak wydajność produkcji, koszt produkcji, zużycie materiałów i energii, zysk.

Zadania optymalizacji statycznej dzielą się na:

1. zadania programowania liniowego

2. zadania programowania nieliniowego

Sformułowanie zadania programowania liniowego w postaci standardowej

• Postać ogólna

Zadanie programowania liniowego (ZPL) w postaci ogólnej formułuje się następująco:

Wyznaczyć wektor x, który minimalizuje funkcję:  z = e^Tx przy ograniczeniach Ax ≤ b,     x ≥ 0

• Postać standardowa

Zadanie programowania liniowego w postaci standardowej (kanonicznej) można sformułować następująco:

Wyznaczyć wektor x który minimalizuje funkcję: z = e^Tx przy ograniczeniach Ax = b,    x ≥ 0 przy czym A jest stałą, znaną macierzą o wymiarach mxn, a, b, c są stałymi znanymi wektorami o wymiarach odpowiadających m i n.

Wprowadzając nowe nieujemne zmienne x_a + 1,  x_a + 2,  …, x_a + n zwane zmiennymi dopełniającymi możemy ograniczenia nierównościowe sprowadzić do ograniczeń równościowych

Przebieg ćwiczenia

Zadanie 1 – zespół 4 – przykład a)

z = 3x₁ + 4x₂ → min

x₁+x₂ ≥ 17

3x₁ + 2x₂ ≥ 42

x₁ + 2x₂ ≥ 20

x₁ + 4x₂ ≥ 24

x₁ ≥ 0, x₂ ≥ 0

• Zbiór rozwiązań dopuszczalnych, wygenerowany za pomocą programu Matlab:

Listing kodu Matlab:

clear all

clc

x1=(0:0.01:20);

j=1;

for i=0:.01:20;

x21(j)=17-i;

x22(j)=21-3/2*i;

x23(j)=10-1/2*i;

x24(j)=6-1/4*i;

j=j+1;

end

plot(x1,x21,x1,x22,x1,x23,x1,x24)

axis ([9 15 2 8])

grid on

xlabel('x1')

ylabel('x2')

title('Zbiór rozwiązań dopuszczalnych')

Ograniczenia wykreślone na płaszczyźnie x₁ ,  x₂:

Rys. 1 Zbiór rozwiązań dopuszczalnych, przy podanych powyżej warunkach ograniaczających

Wartości zmiennych x₁ i x₂ spełniające warunki oznaczono na wykresie zacieniowanym obszarem. Otrzymany zbiór jest zbiorem nieograniczonym.

• Warunek konieczny istnienia rozwiązania:

Jest on spełniony, ponieważ zbiór rozwiązań dopuszczalnych jest zbiorem wypukłym.

• Rysowanie funkcji celu:

Listing kodu Maple:

>

>

Wykres funkcji celu:

Rys. 2 Funkcja celu: z = 3x₁ + 4x₂

• Wyznaczanie wektora –grad(z) oraz punktu, w którym funkcja osiąga wartość minimalną:

$$- \nabla z = - \left\lbrack \frac{\partial z}{\partial x_{1}},\frac{\partial z}{\partial x_{2}} \right\rbrack = - \left\lbrack \frac{\partial\left( 3x_{1} + 4x_{2} \right)}{\partial x_{1}},\frac{\partial\left( 3x_{1} + 4x_{2} \right)}{\partial x_{2}} \right\rbrack = \left\lbrack - 3, - 4 \right\rbrack$$

Rys. Zbiór ograniczeń funcji celu wraz z zaznaczonym wektrorem –grad(z) i punktem, w którym funcja celu osiąga wartość minimalną

Prostą prostopadłą do wektora gradientu przesuwano zgodnie z kierunkiem zmniejszania się funkcji celu, do momentu aż prosta ta miała ostatni punkt wspólny z obszarem rozwiązań dopuszczalnych. W ten sposób ustalono, że funkcja celu osiąga wartość minimalną w punkcie P(14,3).

• Wyznaczenie wartości minimalnej funkcji celu:

z = 3x₁ + 4x₂ = 3 • 14 + 4 • 3 = 54

Współrzędne punktu P: x₁ = 14 oraz x₂ = 3 wprowadzono do równania funkcji celu, tym samym wyznaczają optymalną wartość funkcji celu:

Zadanie 1 – zespół 4 – przykład b)

z = x₁ − 2x₂ → max

2x₁+3x₂ ≥ 6

−4x₁ + 5x₂ ≤ 10

2x₁ + x₂ ≥ 3

x₁ ≥ 0, x₂ ≥ 0

• Zbiór rozwiązań dopuszczalnych, wygenerowany za pomocą programu Matlab:

Listing kodu Matlab:

x1=(0:0.01:40);

j=1;

for i=0:.01:40;

x21(j)=2-(2/3)*i;

x22(j)=2+(4/5)*i;

x23(j)=3-2*i;

j=j+1;

end

plot(x1,x21,'b',x1,x22,'g',x1,x23,'r')

axis ([0 4 0 3])

grid on

xlabel('x1')

ylabel('x2')

title('Zbiór rozwiązań dopuszczalnych')

hold on

Ograniczenia wykreślone na płaszczyźnie x₁ ,  x₂:

Rys. 5 Zbiór rozwiązań dopuszczalnych

Wartości zmiennych x₁ i x₂ spełniające warunki oznaczono na wykresie zacieniowanym obszarem. Otrzymany zbiór jest zbiorem nieograniczonym.

• Warunek konieczny istnienia rozwiązania:

Jest on spełniony, ponieważ zbiór rozwiązań dopuszczalnych jest zbiorem wypukłym.

• Rysowanie funkcji celu:

Listing kodu Maple:

>

>

Wykres funkcji celu:

Rys. 7 Wykres funkcji Celu z = x₁ − 2x₂

• Wyznaczanie wektora grad(z) oraz punktu, w którym funkcja osiąga wartość maksymalną:

$$\nabla z = \left\lbrack \frac{\partial z}{\partial x_{1}},\frac{\partial z}{\partial x_{2}} \right\rbrack = \left\lbrack \frac{\partial\left( x_{1} - 2x_{2} \right)}{\partial x_{1}},\frac{\partial\left( x_{1} - 2x_{2} \right)}{\partial x_{2}} \right\rbrack = \left\lbrack 1, - 2 \right\rbrack$$

Rys. 8 WEKTOR GRADIENTU I PROSTOPADŁE DO NIEGO WARSTWICE FUNKCJI CELU

Prostą prostopadłą do wektora gradientu przesuwano zgodnie z kierunkiem zwiększania się funkcji celu, jednak nie pozwoliło to na określenie wartości optymalnej funkcji.

Wnioski

W pierwszym wykonanym zadaniu dla funkcji celu z = 3x₁ + 4x₂, zgodnie z podanymi warunkami ograniczającymi wyznaczono zbiór rozwiązań dopuszczalnych, będący zbiorem wypukłym i nieograniczonym. Wyznaczenie gradientu i linii prostopadłej do niego, a następni przesunięcie jej zgodnie z kierunkiem zmniejszania się funkcji celu pozwoliło na znalezienie punktu w którym osiąga ona wartość minimalną.

W przypadku drugiego zadania, w wyniku obliczeń otrzymano również zbiór nieograniczony, wypukły, lecz w tym przypadku nie można określić wartości optymalnej funkcji celu, ponieważ osiąga ona swoją wartość optymalną (maksimum) w nieskończoności.