1
Piotr Sawicki
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs
Wydzia
Wydzia
ł
ł
Maszyn Roboczych i Transportu
Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
pok. 719, tel. 665 22 30, 665 21 29
E
E
-
-
:
:
piotr.sawicki@put.poznan.pl
piotr.sawicki@put.poznan.pl
URL:
URL:
www.put.poznan.pl
www.put.poznan.pl
/
/
~
~
piotrs
piotrs
Programowanie liniowe
Programowanie liniowe
Programowanie liniowe
Piotr Sawicki / Programowanie liniowe
2
52
Plan prezentacji
Istota programowania liniowego
•
informacje wprowadzające
•
przykładowe problemy
Ogólne sformułowanie zadania programowania liniowego
Programowanie liniowe na przykładzie
•
identyfikacja problemu
•
konstrukcja modelu matematycznego
•
rozwiązanie problemu
•
interpretacja rozwiązania i analiza wrażliwości
Procedura rozwiązywania zadania programowania liniowego
•
metoda graficzna
•
metoda algebraiczna - SIMPLEX
•
zastosowanie Solvera MS Excel
Podsumowanie
2
Piotr Sawicki / Programowanie liniowe
3
52
Programowanie liniowe
Istota
Jedna z najpopularniejszych i najbardziej użytecznych technik
menedżerskich
•
wywodzi się z badań operacyjnych
Programowanie liniowe znajduje powszechne zastosowanie przy
rozwiązywaniu problemów alokacji (przydziału) ograniczonych
zasobów
zasobów
do
konkurencyjnych
operacji
operacji
(zadań), np.:
•
wybór portfela oferowanych usług transportowych przy ustalonych kosztach przewozu i
posiadanym taborze
•
określenie rodzaju magazynowanych wyrobów przy uwzględnieniu ich zyskowności
oraz możliwościach magazynowych
Problemy sformułowane w kategoriach programowania liniowego
najczęściej polegają na
•
maksymalizacji zysku
•
minimalizacji kosztów
Piotr Sawicki / Programowanie liniowe
4
52
Programowanie liniowe
Istota
Problem maksymalizacji zysku
•
osiągany poprzez realizację zestawu czynności (zadań) lub rodzajów usług
transportowych
•
każdemu zadaniu (rodzajowi usługi) odpowiada zmienna decyzyjna
– np.: oferta przewozu pasażerów na odległość do 50km – zmienna x
1
oferta przewozów dalekobieżnych – zmienna x
2
…
oferta przewozów towarowych do 12 ton – zmienna x
n
•
osiągnięcie maksymalnego zysku ograniczają dostępne (limitowane) zasoby
– np.: posiadanie: 15 zestawów autobusów podmiejskich, 20 autobusów dalekobieżnych,
3 autobusy turystyczne,….3 zestawy drogowe (do 24 ton),…
Problem minimalizacji kosztów
•
osiągany poprzez realizację zestawu czynności (zadań) lub rodzajów usług
transportowych
•
każdemu zadaniu (rodzajowi usługi) odpowiada zmienna decyzyjna
•
osiągnięcie minimalnego kosztu wymaga dostępności zasobów
3
Piotr Sawicki / Programowanie liniowe
5
52
Programowanie liniowe
Istota
Model matematyczny problemu
sformułowany w postaci zadania
programowania liniowego
•
funkcja celu (kryterium „jakości/
doskonałości” rozwiązania)
– funkcja liniowa
– zmienne decyzyjne w pierwszej
potędze
•
ograniczenia
– funkcja liniowa
– zmienne decyzyjne w pierwszej
potędze
– zależności w postaci >, <, =
Przykłady
•
sformułowanie równań i nierówności
w postaci nieliniowej
•
sformułowanie równań i nierówności
w postaci liniowej
•
liniowość w praktyce oznacza, że
zależność funkcyjna pomiędzy
zmiennymi decyzyjnymi posiada
graficzną reprezentację w postaci
linii prostych
2
2
1
2
1
3
2
Min
x
x
x
x
Z
+
=
)
,
(
2
1
2
1
3
Min
x
x
x
x
Z
+
=
)
,
(
45
3
2
2
2
1
≤
+ x
x
2
1
2
1
2
Min
x
x
x
x
Z
+
=
)
,
(
10
4
3
3
2
1
≥
+
+
x
x
x
Piotr Sawicki / Programowanie liniowe
6
52
Programowanie liniowe
Ogólne sformułowanie
Ogólne sformułowanie zadania programowania liniowego
•
funkcja celu
Max Z = c
1
x
x
1
1
+ c
2
x
x
2
2
+ ... + c
n
x
x
n
n
•
ograniczenia
(ograniczone zasoby)
a
11
x
x
1
1
+ a
12
x
x
2
2
+ ... + a
1n
x
x
n
n
≤
b
1
a
21
x
x
1
1
+ a
22
x
x
2
2
+ ... + a
2n
x
x
n
n
≤
b
2
...
a
m1
x
x
1
1
+ a
m2
x
x
2
2
+ ... + a
mn
x
x
n
n
≤
b
m
x
x
1
1
≥
0,
x
x
2
2
≥
0, ...,
x
x
n
n
≥
0
c
j
– jednostkowy przyrost j – tej czynności w ocenie globalnej Z (j = 1, 2, ...,n)
b
i
– ilość i – tego zasobu dostępnego do alokacji do czynności (i = 1, 2, ...,m)
a
ij
– ilość i – tego zasobu konsumowanego przez j – tą czynność
c
j
, b
i
, a
ij
–
parametry;
parametry;
x
1
, x
2
, ..., x
3
–
zmienne decyzyjne
zmienne decyzyjne
4
Piotr Sawicki / Programowanie liniowe
7
52
Programowanie liniowe
Proces rozwiązywania problemu
Model matematyczny
problemu
Dobór metody rozw.
Rozwiązanie problemu
Interpretacja rozw.
Analiza wrażliwości
Proces rozwiązywania
problemu decyzyjnego
Proces rozwiązywania
problemu decyzyjnego
Identyfikacja problemu
decyzyjnego
Identyfikacja problemu decyzyjnego
•
zidentyfikuj stan aktualny
– rozpoznaj realizowane działania
– określ trudności w podjęciu decyzji
•
opisz sytuację (zaistniały problem)
Konstrukcja modelu matematycznego
•
zidentyfikuj zmienne decyzyjne
– czego poszukujesz?
– jakie wielkości mają być wyznaczone?
– ile jest niewiadomych?
•
zidentyfikuj parametry zadania
– jakie wielkości są znane (stałe)?
•
zdefiniuj cel swoich poszukiwań Æ skonstruuj funkcję celu
– jaki cel chcesz osiągnąć?
•
określ wszystkie ograniczenia podjęcia decyzji Æ
skonstruuj warunki ograniczające
– co stanowi ograniczenie dla podjęcia Twojej decyzji?
– z jakimi ograniczeniami musisz się liczyć?
Piotr Sawicki / Programowanie liniowe
8
52
Programowanie liniowe
Proces rozwiązywania problemu
Model matematyczny
problemu
Dobór metody rozw.
Rozwiązanie problemu
Interpretacja rozw.
Analiza wrażliwości
Proces rozwiązywania
problemu decyzyjnego
Proces rozwiązywania
problemu decyzyjnego
Identyfikacja problemu
decyzyjnego
Rozwiązanie problemu (sformułowanego modelu)
•
poszukiwanie rozwiązania
– maksymalizacja funkcji celu
– minimalizacja funkcji celu
•
rozwiązanie problemu za pomocą dostępnych metod
– metoda graficzna (stosowana tylko dla 2 zmiennych
decyzyjnych)
– metoda algebraiczna SIMPLEX (nie ma ograniczenia liczby
zmiennych decyzyjnych)
Interpretacja rozwiązania
•
wartość zmiennych decyzyjnych
•
pozostające zasoby
•
analiza wrażliwości
– zmiana dostępności zasobów
5
Piotr Sawicki / Programowanie liniowe
9
52
Programowanie liniowe
Proces rozwiązywania problemu
Tok postępowania przy rozwiązywaniu problemu
sformułowanego w postaci zadania programowania
liniowego Æ analiza przykładu
•
„Firma ForkLift Service (FLS) jest jednym z (…)”
zobacz treść zadania
Model matematyczny
problemu
Dobór metody rozw.
Rozwiązanie problemu
Interpretacja rozw.
Analiza wrażliwości
Proces rozwiązywania
problemu decyzyjnego
Proces rozwiązywania
problemu decyzyjnego
Identyfikacja problemu
decyzyjnego
Piotr Sawicki / Programowanie liniowe
10
52
Programowanie liniowe
Proces rozwiązywania problemu / Model
Konstrukcja modelu matematycznego
•
zmienne decyzyjne w analizowanym problemie
– S
– liczba zakupionych przez FLS wózków widłowych typu 20S
– H
– liczba zakupionych przez FLS wózków widłowych typu 45H
•
funkcja celu Æ cel postawiony przez firmę FLS
– maksymalizacja zysku ze sprzedaży wózków widłowych typu 20S i 45H
– zysk całkowity:
Z = z
s
+z
H
– z
s
- jednostkowy zysk ze sprzedaży wózków typu 20S
z
s
= 15% • 19.000 € •
S
= 2.850
S
– z
H
– jednostkowy zysk ze sprzedaży wózków typu 45H
z
H
= 19% • 33.000 € •
H
= 6.270
H
– ostateczne sformułowanie funkcji celu
Max Z(S, H) = 2.850
S
+ 6.270
H
6
Piotr Sawicki / Programowanie liniowe
11
52
Programowanie liniowe
Proces rozwiązywania problemu / Model
Konstrukcja modelu matematycznego … cd
•
identyfikacja ograniczeń
– zasoby finansowe firmy FLS Æ max. 2.400.000 zł/rok
– dostępny fundusz czasu pracy poświęcany przez pracowników FLS na sprzedaż wózków
20S i 45H Æ max. 520 rbh/rok
– dostępność wózków u producenta
{
max 100 szt./rok 20S
{
max 75 szt./rok 45H
– rynkowy popyt na wózki widłowe
{
min 10 szt. 20S
{
min 5 szt. 45H
•
matematyczny zapis ograniczeń
– zasoby finansowe firmy FLS ograniczają na przestrzeni roku możliwość zakupu wózków
widłowych u producenta
19.000
S
+ 33.000
H
≤ 2.400.000
– czas pracy ludzi zatrudnionych w FLS i zajmujących się sprzedażą wózków 20S i 45H jest
ograniczony
6
S
+ 4
H
≤ 520
Piotr Sawicki / Programowanie liniowe
12
52
Programowanie liniowe
Proces rozwiązywania problemu / Model
•
matematyczny zapis ograniczeń … cd
– możliwości produkcyjne firmy Clark w zakresie dostarczenia firmie FLS wózków widłowych
typu 20S i 45H
{
dostępność wózków 20S
S
≤ 100
{
dostępność wózków 45H
H
≤ 75
– minimalna liczba wózków w jednorazowym zamówieniu, zapewniająca ciągłość sprzedaży
przy jednoczesnym zachowaniu satysfakcji klientów firmy FLS
{
zapotrzebowanie firmy FLS na wózki typu 20S
S
≥ 10
{
zapotrzebowanie firmy FLS na wózki typu 45H
H
≥ 5
– formalnie Æ poszukiwane rozwiązanie (S, H) nie powinno przyjmować wartości ujemnych
S
≥ 0
H
≥ 0
7
Piotr Sawicki / Programowanie liniowe
13
52
Programowanie liniowe
Proces rozwiązywania problemu / Model
Ostateczna postać modelu matematycznego problemu decyzyjnego
sformułowanego w postaci zadania programowania liniowego
•
funkcja celu
Max Z(S, H) = 2.850
S
+ 6.270
H
•
przy ograniczeniach
(1) 19
S
+ 33
H
≤ 2.400
(2) 6
S
+ 4
H
≤ 520
(3)
S
≤ 100
(4)
H
≤ 75
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
Piotr Sawicki / Programowanie liniowe
14
52
Programowanie liniowe
Graficzna metoda rozwiązywania
zadania programowania liniowego
Programowanie liniowe
Programowanie liniowe
Graficzna metoda rozwi
Graficzna metoda rozwi
ą
ą
zywania
zywania
zadania programowania liniowego
zadania programowania liniowego
8
Piotr Sawicki / Programowanie liniowe
15
52
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19
S
+ 33
H
≤ 2.400
(2) 6
S
+ 4
H
≤ 520
(3)
S
≤ 100
(4)
H
≤ 75
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
H
0
20
100
140
S
20
100
120
S ≥ 0
(7)
H ≥ 0
(8)
5
(6)
H ≥ 5
S ≥ 10
(5)
10
S ≤ 100
(3)
Obszar rozwiązań dopuszczalnych
dla ograniczeń (3) – (8)
Ograniczenia (7) i (8) są nieaktywne
(4)
H ≤ 75
75
Obszar rozwiązań niedopuszczalnych
Piotr Sawicki / Programowanie liniowe
16
52
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19
S
+ 33
H
≤ 2.400
(2) 6
S
+ 4
H
≤ 520
(3)
S
≤ 100
(4)
H
≤ 75
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
•
ograniczenie (2)
6
S
+ 4
H
= 520
S = 0 Æ H = 130 Æ (0;130)
H = 0 Æ S = 86,7 Æ (86,7;0)
H
0
20
100
140
S
20
100
120
S ≥ 0
(7)
H ≥ 0
(8)
5
(6)
H ≥ 5
S ≥ 10
(5)
10
S ≤ 100
(0;130)
(86,7; 0)
(4)
H ≤ 75
75
(3)
(2)
6S + 4H ≤ 520
Ograniczenia (3) staje się nieaktywne
9
Piotr Sawicki / Programowanie liniowe
17
52
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19
S
+ 33
H
≤ 2.400
(2) 6
S
+ 4
H
≤ 520
(3)
S
≤ 100
(4)
H
≤ 75
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
•
ograniczenie (1)
19
S
+ 33
H
= 2.400
S = 0 Æ H = 72,7 Æ (0; 72,7)
H = 0 Æ S = 126,3 Æ (126,3; 0)
H
0
20
100
140
S
20
100
120
S ≥ 0
(7)
H ≥ 0
(8)
5
(6)
H ≥ 5
S ≤ 100
(0;130)
(86,7; 0)
(3)
(2)
6S + 4H ≤ 520
(126,3; 0)
(0; 72,7)
S ≥ 10
(5)
10
19S +33H ≤ 2 400
(1)
(4)
H ≤ 75
75
Piotr Sawicki / Programowanie liniowe
18
52
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
określanie kierunku zmiany wartości
funkcji celu (tu kierunek przyrostu)
Max Z(S, H) = 2.850
S
+ 6.270
H
2.850
S
+ 6.270
H
= 0
S = 10 Æ H = - 4,5 Æ (10; - 4,5)
S = 20 Æ H = - 9 Æ (20; - 9)
H
0
20
100
140
S
20
100
120
5
H ≥ 5
S ≤ 100
(0;130)
(86,7; 0)
6S + 4H ≤ 520
(126,3; 0)
S ≥ 10
19S +33H ≤ 2 400
H ≤ 75
75
S
0,45
S
270
6
850
2
H
−
=
−
=
-4,5
-9
Z= 2 850S + 6 270H
40
(40; 20)
Z
1
=239 400
Z
2
=364 800
„
„
Ostatni wierzchołek”
Ostatni wierzchołek”
(40; 40)
10
Piotr Sawicki / Programowanie liniowe
19
52
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
określenie punktu przecięcia prostych
S = 10
19
S
+ 33
H
= 2.400
H
= - 19/33
S
+ 2.400/33
S = 10 Æ H = 66,96
•
określenie wartości funkcji celu
S=10 i H=66,96
È
Z=448.400
È
Z
max
H
0
20
100
140
S
20
100
120
5
H ≥ 5
S ≤ 100
(0;130)
(86,7; 0)
6S + 4H ≤ 520
(126,3; 0)
S = 10
19S +33H = 2 400
H ≤ 75
75
-4,5
-9
40
(40; 20)
(40; 40)
(10; 66,96)
Piotr Sawicki / Programowanie liniowe
20
52
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu programowania liniowego
Algorytm metody
(1) narysuj obszar rozwiązań dopuszczalnych i określ jego wierzchołki
– jeżeli obszar rozwiązań jest pusty Æ wszystkie rozwiązania są niedopuszczalne Æ
ponownie rozważ sformułowanie ograniczeń
(2) narysuj 2 różne wykresy funkcji celu (FC) i określ kierunek optymalizacji
(max vs. min)
– jeżeli problem dotyczy maksymalizacji FC równolegle przesuń linię reprezentującą FC w
kierunku przyrostu jej wartości
– jeżeli problem polega na minimalizacji FC przesuń linię w kierunku przeciwnym, tj.
zmniejszania się wartości FC
(3) przesuń funkcję celu znajdując „ostatni wierzchołek”
– w przypadku, gdy FC jest równoległa do jednego z boków obszaru rozwiązań
dopuszczalnych (ORD), wówczas problem posiada szereg rozwiązań alternatywnych
leżących pomiędzy wierzchołkami ORD
(4) równania prostych, które przecinają się w punkcie wierzchołkowym (patrz p.3)
tworzą układ równań określających współrzędne punktu optymalnego
11
Piotr Sawicki / Programowanie liniowe
21
52
Programowanie liniowe
Proces rozwiązywania problemu / Interpretacja rozwiązania
Rozwiązanie optymalne
•
optymalna liczba sprzedanych wózków widłowych 20S wynosi S=10 szt.
•
optymalna liczba sprzedanych wózków widłowych 45H wynosi H=66,96 szt.
– w praktyce H=66 lub H=67 (rozwiązanie poza obszarem rozwiązań dopuszczalnych)
•
zysk ze sprzedaży wózków obu typów
Z=2.850 S + 6.270 H
S=10 szt. i H=66,96 szt. Æ Z=448.401,9 € Æ maksymalny zysk
lub
S=10 i H=66 Æ Z=442.320 €
•
analiza ograniczeń
(1) 19.000
S
+ 33.000
H
≤ 2.400.000 (dostępne zasoby finansowe)
dla S=10 szt. i H=66,96 szt. LHS
1
= 2.399.680 € Æ ≈ 0 € rezerwy finansowej
(2) 6
S
+ 4
H
≤ 520 (dostępna liczba roboczogodzin)
dla S=10 szt. i H=66,96 szt. LHS
2
= 327,84 rbh Æ 192,16 rbh rezerwy czasu
LHS
Piotr Sawicki / Programowanie liniowe
22
52
Programowanie liniowe
Proces rozwiązywania problemu / Interpretacja rozwiązania
•
analiza ograniczeń… cd
(3)
S
≤ 100 (maksymalna dostępność wózków typu 20S)
dla S=10 szt. i H=66,96 szt. LHS
3
= 10 szt. Æ 90 szt. rezerwy
(4)
H
≤ 75
dla S=10 szt. i H=66,96 szt. LHS
4
= 66,96 szt. Æ 8,04 szt. rezerwy
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
12
Piotr Sawicki / Programowanie liniowe
23
52
Programowanie liniowe
Zastosowanie Solvera Excel / Rozwiązanie problemu
Zapis modelu matematycznego w obszarze roboczym arkusza kalkulacyjnego
Przykład
Przykład
Piotr Sawicki / Programowanie liniowe
24
52
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport wyników
Maksymalna wartość FC
Wartość zmiennych
decyzyjnych (S, H)
Status ograniczenia
„wiążące” – zasób w pełni wykorzystany
„niewiążący” – pozostają rezerwy
Wartość ograniczenia (LHS) przy
uzyskanych wartościach zmiennych
decyzyjnych
Pozostała do wykorzystania
rezerwa „luz”
analizowanych zasobów
13
Piotr Sawicki / Programowanie liniowe
25
52
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport wrażliwości
Optymalna
wartość
zmiennych
decyzyjnych
Współczynniki
funkcji celu
Przedziały zmienności współczynników FC dla których
wartości zmiennych decyzyjnych nie ulegną zmianie
O ile zmieni się wartość FC jeżeli prawa
strona (RHS) odpowiedniego warunku
ograniczającego ulegnie zmianie o 1
Wartość RHS
warunków
ograniczających
Krańce przedziałów zmienności RHS,
przy których nie nastąpi zmiana zestawu
zmiennych decyzyjnych
Piotr Sawicki / Programowanie liniowe
26
52
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport granic
Wartość (max)
funkcji celu
Optymalna wartość
zmiennych
decyzyjnych
Obszar rozwiązań dopuszczalnych
S – nie ulega zmianie DG=10, GG=10
H – ulega zmianie: DG=5, GG=66,96
14
Piotr Sawicki / Programowanie liniowe
27
52
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport granic –
interpretacja dolnej i górnej
granicy
H
0
20
100
140
S
20
100
120
5
H ≥ 5
S ≤ 100
(0;130)
(86,7; 0)
6S + 4H ≤ 520
(126,3; 0)
S ≥ 10
19S +33H ≤ 2 400
H ≤ 75
75
(10; 66,96)
(10; 5)
Z(min)=59.850
Z(max)=448.400
Piotr Sawicki / Programowanie liniowe
28
52
Programowanie liniowe
Algebraiczna metoda rozwiązywania
zadania programowania liniowego –
metoda SIMPLEX
Programowanie liniowe
Programowanie liniowe
Algebraiczna metoda rozwi
Algebraiczna metoda rozwi
ą
ą
zywania
zywania
zadania programowania liniowego
zadania programowania liniowego
–
–
metoda SIMPLEX
metoda SIMPLEX
15
Piotr Sawicki / Programowanie liniowe
29
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Algebraiczna metoda rozwiązywania zadania programowania liniowego
•
metoda SIMPLEX
– brak ograniczeń dotyczących liczby zmiennych decyzyjnych
– metoda wykorzystująca redukcję Gaussa-Jordana (G-J)
•
wyjaśnienie istoty metody SIMPLEX wymaga wprowadzenia kilku pojęć
– redukcja Gaussa-Jordana
– przekształcanie nierówności do postaci równań
•
redukcja G-J prowadzi do uzyskania rozwiązania spełniającego układ równań, poprzez
jego redukcję do innego układu równań, w którym
(1) każde równanie zawiera wyłącznie jedną zmienna decyzyjną (niewiadomą)
(2) współczynnik każdej zmiennej decyzyjnej (niewiadomej) w każdym równaniu wynosi 1
Piotr Sawicki / Programowanie liniowe
30
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Istotę redukcji G-J wyjaśniono na 2 przykładach
•
liczba równań i zmiennych decyzyjnych jest jednakowa (przypadek 1)
•
liczba równań jest mniejsza niż zmiennych decyzyjnych (przypadek 2)
Redukcja G-J dla przypadku 1
•
2 zmienne (x, y)
•
2 równania
Przykład
•
układ równań
(A)
x + 3y = 17
(B)
4x – y = 3
•
zredukuj zmienną x z równania (B) Æ zmienna x będzie występować tylko w
równaniu (A) Æ pomnóż równanie (A) przez 4 i odejmij od (B)
(B)
4x – y = 3
4(A)
4x + 12y = 68
(B)-4(A)
–13y = –65
(1)
16
Piotr Sawicki / Programowanie liniowe
31
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Przykład…cd
•
podziel rezultat przez –13 Æ współczynnik przy zmiennej y wyniesie 1
(B
1
)
y = 5
(A
1
)
x + 3y = 17
•
współczynniki przy zmiennej x w równaniu A
1
oraz zmiennej y w równaniu B
1
wynoszą 1
– wyeliminuj zmienną y z równania B
1
aby w każdym równaniu była tylko jedna zmienna
decyzyjna (niewiadoma) Æ pomnóż równanie (B
1
) przez 3 i odejmij od równania (A
1
)
(A
1
)
x + 3y = 17
3(B
1
)
3y = 15
(A
1
)-3(B
1
)
x = 2
•
rozwiązanie układu równań (1) stanowi punkt (x, y) = (2, 5)
Piotr Sawicki / Programowanie liniowe
32
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Redukcja G-J dla przypadku 2 (większa liczba zmiennych niż równań)
•
3 zmienne (x, y, z)
•
2 równania
Przykład
•
układ równań
(A)
2x + 3y + 4z = 12
(B)
3x + 5y – z = 20
•
klasyczna redukcja G-J nie jest możliwa Æ większa liczba zmiennych niż równań
– redukcja G-J powinna być prowadzona do chwili zredukowania największej możliwej liczby
zmiennych decyzyjnych (równej liczbie równań)
•
zredukuj (wyeliminuj) zmienną x z równania (B) – (wybór arbitralny) Æ pomnóż
równanie (A) przez 3/2 i odejmij od (B)
(B)
3x + 5y – z = 20
3/2(A)
3x + 9/2y + 6z = 18
(B)-3/2(A)
1/2y – 7z = 2
(2)
17
Piotr Sawicki / Programowanie liniowe
33
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Przykład … cd
•
uzyskaj współczynnik 1 przy zmiennej y w równaniu (B) i zmiennej x w równaniu (A) Æ
pomnóż przekształcone równanie (B) przez 2, a przekształcone równanie (A) przez 1/3
(B
1
)
y – 14z = 4
(A
1
)
x + 3/2y + 2z = 6
•
następnie wyeliminuj zmienną y z równania (A
1
) Æ pomnóż równanie (B
1
) przez 3/2 i
odejmij od równania (A
1
)
(A
1
)
x + 3/2y + 2z = 6
3/2(B
1
)
3/2y – 21z = 6
(A
1
)-3/2(B
1
)
x + 23z = 0
•
ostatecznie zredukowany za pomocą procedury G-J układ równań zawiera
(A
2
)
x + 23z = 0
(B
2
)
y – 14z = 4
dalsza redukcja G-J nie jest możliwa Æ powstały układ równań ma nieskończoną
liczbę rozwiązań
Piotr Sawicki / Programowanie liniowe
34
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Przykład … cd
•
jeżeli arbitralnie przyjąć, że z = 1, to pozostałe zmienne przyjmą wartości
x = - 23, y = 18 Æ (x, y, z) = (-23, 18, 1)
czy uzyskane rozwiązanie zredukowanego układu równań spełnia również oryginalny
układ rówań(2)
2(-23) + 3(18) + 4(1) = 12
3(-23) + 5(18) – (1) = 20
•
jeżeli arbitralnie przyjąć, że z = 0, to pozostałe zmienne przyjmą wartości
x = 0, y = 4 Æ (x, y, z) = (0, 4, 0)
uzyskane rozwiązanie również spełnia oryginalny układ równań (2)
•
ostatni przypadek (z = 0) stanowi podstawę procesu rozwiązywania zadań
programowania liniowego za pomocą metody SIMPLEX
18
Piotr Sawicki / Programowanie liniowe
35
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Pojęcia dotyczące redukcji G-J
•
po redukcji G-J wszystkie zmienne
– które w układzie równań pojawiają się tylko raz
– których współczynnik wynosi 1
nazywane są zmiennymi
bazowymi
bazowymi
•
po redukcji G-J wszystkie zmienne, które nie zostały zredukowane nazywane są
zmiennymi
niebazowymi
niebazowymi
– aby uzyskać rozwiązanie układu równań niebazowe zmienne decyzyjne przyjmują wartość 0
Piotr Sawicki / Programowanie liniowe
36
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Przekształcenia nierówności do postaci równań
•
redukcja G-J ma uzasadnienie tylko w przypadku równań
•
większość ograniczeń modelu matematycznego sformułowanych jest w postaci
nierówności (<, ≤, ≥, >)
•
praktyczna interpretacja wprowadzenia przekształceń
– rozważane są dwa przykładowe ograniczenia dot. problemu firmy FLS
{
np. ogr (2): 6S + 4H
≤ 520 dotyczące zasobu czasu pracy
{
np. ogr. (5): S
≥ 10, dotyczące rynkowego popytu na wózki typu S
– założyć można, że S i H przyjmują wartości, dla których 6S + 4H jest znacznie mniejsze
od 520, wówczas
{
nie wszystkie dostępne zasoby zostaną (muszą być) wyczerpane
{
można powiedzieć, że: „ istnieje pewna rezerwa zasobu”
{
wprowadzając dodatkową zmienną, tzw.
zmienn
zmienn
ą
ą
niedoboru
niedoboru
N
1
(N
1
≥0) do lewej strony
nierówności typu (< lub ≤), możliwe jest przekształcenie nierówności do postaci równania
6S + 4H
≤ 520 Æ 6S + 4H + N
1
= 520
{
w problemie firmy FLS zmienna niedoboru musi być wprowadzona do 4 ograniczeń, tj. (1),
(2), (3) i (4)
19
Piotr Sawicki / Programowanie liniowe
37
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
•
praktyczna interpretacja wprowadzenia przekształceń … cd
{
np. ogr. (5): S
≥ 10, dotyczące rynkowego popytu na wózki typu S
– założyć można, że zmienna S w ograniczeniu S
≥ 10 przyjmuje wartość znacznie większą
od 10, wówczas
{
wielkość zasobu będzie większa od wymaganego (minimalnego)
{
istnieje możliwość „odjęcia” części zasobu, tak aby S = 100
{
wprowadzając dodatkową zmienną, tzw.
zmienn
zmienn
ą
ą
nadmiaru
nadmiaru
N
2
(N
2
≥0) do lewej strony
nierówności typu (> lub ≥), możliwe jest przekształcenie nierówności do postaci równania
S
≥ 10 Æ S - N
2
= 10
{
w problemie firmy FLS zmienna nadmiaru musi być wprowadzona do 2 ograniczeń, tj.
ograniczenie (5) i (6)
Piotr Sawicki / Programowanie liniowe
38
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Istota metody SIMPLEX na podstawie analizy modelu matematycznego dla
problemu FLS
•
przekształcenie nierówności warunków ograniczających do postaci równań
(1) 19
S
+ 33
H
≤ 2.400
19
S
+ 33
H + N
1
= 2.400
(2) 6
S
+ 4
H
≤ 520
6
S
+ 4
H + N
2
= 520
(3)
S
≤ 100
S
+ N
3
= 100
(4)
H
≤ 75
H + N
4
= 100
(5)
S
≥ 10
S
- N
5
= 10
(6)
H
≥ 5
H - N
6
= 5
•
formalnie zmienne N
1
-N
6
musza być wprowadzone do równania funkcji celu Z
Z = 2.850
S
+ 6.270
H
Æ
Z = 2.850
S
+ 6.270
H +0N
1
+0N
2
+ 0N
3
+0N
4
-0N
5
-0N
6
•
zakładamy nieujemność wszystkich zmiennych
S
,
H
,
N
1
,
N
2
,
N
3
,
N
4
,
N
5
,
N
6
≥ 0
Układ nierówności
Układ równań
20
Piotr Sawicki / Programowanie liniowe
39
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Istota metody SIMPLEX … cd
•
przedstawienie całego modelu matematycznego problemu FLS Æ jednocześnie
wszystkie zmienne przenoszone są na lewą stronę układu równań (LHS)
Z – 2.850
S
- 6.270
H
= 0
19
S
+ 33
H + N
1
= 2400000
6
S
+ 4
H + N
2
= 520
S
+ N
3
= 100
H + N
4
= 75
S
– N
5
= 10
H – N
6
= 5
•
czy istnieje rozwiązanie przedstawionego układu równań?
– uznając wstępnie, że S = 0 i H = 0, wówczas:
{
Z = 0 (wartość funkcji celu)
{
N
1
= 2400000, N
2
= 520, N
3
= 100, N
4
= 75 (zmienne niedoboru)
{
N
5
= -10, N
6
= -5 (zmienne nadmiaru)
– pierwsze rozwiązanie
{
(Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
) = (0, 0, 0, 2400000, 520, 100, 75, -10, -5)
Piotr Sawicki / Programowanie liniowe
40
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Istota metody SIMPLEX … cd
•
interpretacja rozwiązania dopuszczalnego układu równań
( Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
)= ( 0, 0, 0, 2400000, 520, 100, 75, -10, -5)
– uzyskane rozwiązanie nazywane jest
dopuszczalnym rozwiązaniem bazowym
dopuszczalnym rozwiązaniem bazowym
– zmienne przyjmujące wartość 0 Æ
zmienne
zmienne
niebazowe
niebazowe
, pozostałe
zmienne bazowe
zmienne bazowe
brak sprzedaży wózków typu 20S
brak sprzedaży wózków typu 45H
brak zysku ze sprzedaży wózków widłowych typu 20S i 45H
zasoby pozostałe do wykorzystania
(finansowe, czasu pracy, dostępność wózków 20S i 45H)
niewykorzystane możliwości
(niedostarczenie do FLS wózków: 10szt. 20S i 5 szt. 45H)
21
Piotr Sawicki / Programowanie liniowe
41
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Istota metody SIMPLEX … cd
•
poszukiwanie kolejnego dopuszczalnego rozwiązania bazowego, które powiększy
wartość funkcji celu (Z = 0, Z Æ max)
– analiza równanie FC:
Z – 2.850
S
– 6.270
H
= 0
– S i H są zmiennymi niebazowymi (S=0 i H=0) Æ jedna z nich powinna wejść do bazy
{
jeżeli przyjmiemy, że S=10 a H=0, to Z=28.500
{
jeżeli przyjmiemy, że S=0 a H=10, to Z=62.700
– zmienna niebazowa H najbardziej podnosi wartość Z Æ powinna zostać
wprowadzona do
wprowadzona do
bazy
bazy
(ukształtować nowe dopuszczalne rozwiązanie bazowe)
– która zmienna powinna opuścić bazę?
– konieczna jest analiza wszystkich ograniczeń
Piotr Sawicki / Programowanie liniowe
42
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Istota metody SIMPLEX … cd
•
istota poszukiwania kolejnego dopuszczalnego rozwiązania bazowego…
– analiza ograniczeń
19
S
+ 33
H + {N
1
}
= 2.400
6
S
+
4
H + {N
2
}
= 520
S
+ {N
3
}
= 100
H + {N
4
}
= 75
S
– {N
5
}
= 10
H – {N
6
}
= 5
– minimalna nieujemna wartość ilorazu jest maksymalną dopuszczalną wartością zmiennej H
– zmienna H przyjmuje wartość 5 Æ S=0, H=5
– nowe dopuszczalne rozwiązanie bazowe
(Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
) = (31.350, 0, 5, 2.235, 500, 100, 70, -10, 0)
{
S i N
6
Æ
zmienne niebazowe (N
6
wyszła z bazy)
{
H, N
1
, N
2
, N
3
, N
4
i N
5
Æ
zmienne bazowe (H weszła do bazy)
2.400 / 33 = 72 24/33
520 / 4 = 130
100 / 0 = 0
75 / 1 = 75
10 / 0 = 0
5 / 1 = 5
RHS / Współczynnik przy H
Å
Å
minimum
minimum
22
Piotr Sawicki / Programowanie liniowe
43
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
•
mechanizm poszukiwania kolejnych bazowych rozwiązań dopuszczalnych
– identyfikacja tzw. równania głównego
(A)
Z – 2.850
S
–
6.270
H
= 0
(B)
19
S
+ 33
H + N
1
= 2.400
(C)
6
S
+ 4
H + N
2
= 520
(D)
S
+ N
3
= 100
(E)
H + N
4
= 75
(F)
S
– N
5
= 10
(G)
H – N
6
= 5
– eliminacja zmiennej H z równania A wg zasady redukcji G-J
(A)
Z – 2.850
S
–
6.270
H
= 0
(G)x6.270
6.270
H
– 6.270
N
6
= 31.350
(A)+(G)x6.270 Z – 2850
S
–
6.270
N
6
= 31.350
– eliminacja zmiennej H z równania B wg zasady redukcji G-J
(B)
19
S
+ 33
H + N
1
= 2.400
(G)x33
33
H
– 33
N
6
= 165
(B)-(G)x33
19
S +
N
1
+
33
N
6
= 2.235
równanie główne
równania, z
których należy
wyeliminować
zmienną H
Piotr Sawicki / Programowanie liniowe
44
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
•
mechanizm poszukiwania kolejnych bazowych rozwiązań dopuszczalnych
– ostateczny układ równań w I-szej iteracji
(A
1
)
Z – 2.850
S
–
6.270
N
6
= 31.350
(B
1
)
19
S
+
N
1
+33
N
6
= 2.235
(C
1
)
6
S
+
N
2
+4
N
6
= 500
(D
1
)
S
+
N
3
= 100
(E
1
)
+
N
4
+
N
6
= 70
(F
1
)
S
–
N
5
= 10
(G
1
)
H
–
N
6
= 5
– nowe dopuszczalne rozwiązanie bazowe:
(Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
) = (31.350, 0, 5, 2.235, 500, 100, 70, -10, 0)
– poszukiwanie kolejnej zmiennej niebazowej wchodzącej do bazy Æ zmienna S
– poszukiwanie nowego równania głównego Æ równanie F
1
– eliminacja zmiennej S z równania A
1
wg zasady redukcji G-J
(A
1
)
Z – 2.850
S
–
6.270
N
6
= 31.350
(F
1
)x2.850
2.850
S
–2.850
N
5
= 28.850
(A
1
)+(F
1
)x2.850 Z
–
2.850
N
5
–
6.270
N
6
= 59.850
RHS / Współczynnik przy S
Å
Å
minimum
minimum
2.235
/
19
= 117
12
/
19
500
/
6
= 83
1
/
3
100
/
1
= 100
75
/
0
= 0
10
/
1
= 10
5
/
0
= 0
równanie główne
23
Piotr Sawicki / Programowanie liniowe
45
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
•
mechanizm poszukiwania kolejnych bazowych rozwiązań dopuszczalnych
– ostateczny układ równań w II-giej iteracji
(A
2
)
Z –2.850
N
5
–
6.270
N
6
= 59.850
(B
2
)
+
N
1
+19
N
5
+33
N
6
= 2.045
(C
2
)
+
N
2
+6
N
5
+4
N
6
= 440
(D
2
)
+
N
3
+
N
5
= 90
(E
2
)
+
N
4
+
N
6
= 70
(F
2
)
S
–
N
5
= 10
(G
2
)
H
–
N
6
= 5
– nowe dopuszczalne rozwiązanie bazowe:
(Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
) = (59.850, 10, 5, 2.045, 440, 90, 70, 0, 0)
– poszukiwanie kolejnej zmiennej niebazowej wchodzącej do bazy Æ zmienna N
6
– poszukiwanie nowego równania głównego Æ równanie B
2
– równanie B
2
po przekształceniu Æ współczynnik 1 przy zmiennej N
6
(B
2
)
+
1
/
33
N
1
+
19
/
33
N
5
+
N
6
=
2.045
/
33
RHS / Współczynnik przy N
6
2.045
/
33
= 61
32
/
33
440
/
4
= 110
90
/
0
= 0
70
/
1
= 70
10
/
0
= 0
-
5
/
1
= -5
równanie główne
Piotr Sawicki / Programowanie liniowe
46
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
•
mechanizm poszukiwania kolejnych bazowych rozwiązań dopuszczalnych
– ostateczny układ równań w III-giej iteracji
(A
3
)
Z +
2.045
/
33
N
1
+760
N
5
= 448.400
(B
3
)
+
1
/
33
N
1
+
19
/
33
N
5
+
N
6
=
2.045
/
33
≈ 61,96
(C
3
)
–
4
/
33
N
1
+
N
2
+
122
/
33
N
5
=
6.340
/
33
≈ 192,12
(D
3
)
+
N
3
+
N
5
= 90
(E
3
)
–
1
/
33
N
1
+
N
4
–
19
/
33
N
5
=
265
/
33
≈ 8,03
(F
3
)
S
–
N
5
= 10
(G
3
)
H
+
1
/
33
N
1
+
19
/
33
N
5
=
2.210
/
33
≈ 66,96
– rozwiązanie optymalne
(Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
) = (448.400; 10; 66,96; 0; 192,12; 90; 8,03; 0; 61,96)
24
Piotr Sawicki / Programowanie liniowe
47
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Algorytm metody SIMPLEX
Rozpoczęcie algorytmu
(1) przenieś prawą stronę funkcji celu na lewą stronę i przyrównaj ją do zera
(2) przekształć nierówności do postaci równań wykorzystując zmienne niedoboru i
nadmiaru (zmienne dodatkowe)
(3) przyjmij, że wartość funkcji celu – Z oraz pozostałe zmienne dodatkowe są
początkowymi zmiennymi bazowymi
(4) określ pierwsze dopuszczalne rozwiązanie bazowe
Poszukiwanie kolejnych dopuszczalnych rozwiązań bazowych
(5) najbardziej ujemny współczynnik pierwszego równania wskazuje nową zmienną
wchodzącą do bazy
(6) dla pozostałych równań określ iloraz RHS i współczynnika zmiennej wchodzącej do
bazy
(7) znajdź minimalny nieujemny iloraz; bieżąca zmienna bazowa związana ze wskazanym
ilorazem opuszcza bazę i stanowi zmienną niebazową w nowym bazowym rozwiązaniu
dopuszczalnym
(8) przeprowadź redukcje G-J na nowej zmiennej bazowej
(9) określ nowe bazowe rozwiązanie dopuszczalne
Piotr Sawicki / Programowanie liniowe
48
52
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Algorytm metody SIMPLEX ...cd
Określenie rozwiązania optymalnego
(10) jeżeli po kroku (9) w pierwszym równaniu (funkcji celu) znajdują się ujemne
współczynniki, wróć do kroku (4) i poszukuj kolejnego bazowego rozwiązania
dopuszczalnego
(11) jeżeli po kroku (9) w pierwszym równaniu brak jest ujemnych współczynników bieżące
bazowe rozwiązanie dopuszczalne jest rozwiązaniem optymalnym
25
Piotr Sawicki / Programowanie liniowe
49
52
Przykłady obszarów rozwiązań
dopuszczalnych
•
funkcja celu może przyjmować
nieograniczone wartości
•
obszar rozwiązań dopuszczalnych jest
pusty
Programowanie liniowe
Podsumowanie
Podstawowe pojęcia do zapamiętania
•
rozwiązanie dopuszczalne –
rozwiązanie dla którego spełnione są
wszystkie ograniczenia
•
obszar rozwiązań dopuszczalnych –
obszar wyznaczony poprzez aktywne
ograniczenia
•
rozwiązania niedopuszczalnych –
rozwiązania znajdujące się poza
obszarem rozwiązań dopuszczalnych
•
rozwiązanie optymalne (optimum) –
rozwiązanie dopuszczalne osiągające
wartość ekstremalną
•
ograniczenie aktywne – ograniczenie
wyznaczające obszar rozwiązań
dopuszczalnych
•
ograniczenie nieaktywne –
ograniczenie nie należące do obszaru
rozwiązań dopuszczalnych
Piotr Sawicki / Programowanie liniowe
50
52
Programowanie liniowe
Podsumowanie
Pojęcia do zapamiętania
•
redukcja Gaussa-Jordana
•
zmienna bazowa
•
zmienna niebazowa
•
zmienne dodatkowe
– zmienna niedoboru
– zmienna nadmiaru
•
równanie główne
26
Piotr Sawicki / Programowanie liniowe
51
52
Programowanie liniowe
Podsumowanie
Warunki sformułowania problemu w postaci zadania programowania
liniowego
•
identyfikacja ograniczonych zasobów (w przeciwnym wypadku nie ma problemu)
– ograniczona liczba pracowników,
– ograniczona dostępność środków transportowych,
– limitowane zasoby finansowe,…
•
określony kierunek zmiany wartości funkcji celu
– maksymalizacja zysku
– minimalizacja kosztów (czasu transportu)
•
liniowość funkcji celu i ograniczeń
– np.: zysk z kursu 2 składów pociągu jest dwa razy większy jak zysk z kursu jednego
pociągu”
•
homogeniczność rozważanych zasobów
– analizowane składy pociągów charakteryzują się identycznym standardem funkcjonowania
(realizacji usługi przewozowej)
•
podzielność zasobów
– 0,5 dm
3
oleju napędowego, pobór 45 kWh energii
– przejazd 1,5 pociągu na trasie Poznań-Warszawa?
Wyszukiwarka
Podobne podstrony:
Li Yadav Lin Exploring the role of privacy programs on initial online trust formation
Nowy Prezentacja programu Microsoft PowerPoint 5
Charakterystyka programu
1 treści programoweid 8801 ppt
Programowanie rehabilitacji 2
Rola rynku i instytucji finansowych INowy Prezentacja programu Microsoft PowerPoint
Nowy Prezentacja programu Microsoft PowerPoint ppt
Szkoła i jej program
wykluczenie społ program przeciwdział
ProgrammingJavaLecture9
Nowa podstawa programowa WF (1)
Programowanie robotów przemysłowych FANUC
więcej podobnych podstron