Zarządzanie transportem
Zarządzanie transportem
Programowanie liniowe
Programowanie liniowe
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
pok. 719, tel. [phone]
E-mail: [e-mail]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs
URL: http://www.put.poznan.pl/~piotrs
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 / Zarządzanie transportem
Programowanie liniowe
Istota
Jedna z najpopularniejszych i najbardziej użytecznych technik
menedżerskich (badań operacyjnych)
Programowanie liniowe znajduje powszechne zastosowanie przy
rozwiązywaniu problemów alokacji (przydziału) ograniczonych zasobów do
zasobów
konkurencyjnych operacji (zadań)
operacji
" 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
3
Piotr Sawicki / Zarządzanie transportem
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 x1
oferta przewozów klasy IC  zmienna x2
&
oferta przewozów towarowych  zmienna xn
" osiągnięcie maksymalnego zysku ograniczają posiadane (limitowane zasoby)
 np.: posiadanie: 15 zestawów kolei podmiejskiej, 20 wagonów klasy IC, 3 lokomotywy
spalinowe do 180 km/h,& . 5 otwartych wagonów towarowych
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
4
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Istota
Model matematyczny problemu Przykłady
sformułowany w postaci zadania
" sformułowanie równań i nierówności
programowania liniowego
w postaci nieliniowej
" funkcja celu (kryterium  jakości/
2
Min Z(x1, x2) = 2x1 + 3x2
doskonałości rozwiązania)
 funkcja liniowa
3
Min Z(x1, x2) =
 zmienne decyzyjne w pierwszej
x1 + x2
potędze
2
2x1 + 3x2 d" 45
" ograniczenia
 funkcja liniowa
" sformułowanie równań i nierówności
 zmienne decyzyjne w pierwszej w postaci liniowej
potędze
Min Z(x1, x2) = 2x1 + x2
 zależności w postaci >, <, =
3x1 + 4x2 + x3 e" 10
" liniowość w praktyce oznacza, że
zależność funkcyjna pomiędzy
zmiennymi decyzyjnymi posiada
graficzną reprezentację w postaci
linii prostych
5
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Ogólne sformułowanie
Ogólne sformułowanie zadania programowania liniowego
" funkcja celu
Max Z = c1x1 + c2x2 + ... + cnxn
x1 x2 xn
" ograniczenia (ograniczone zasoby)
a11x1 + a12x2 + ... + a1nxn d" b1
x1 x2 xn
a21x1 + a22x2 + ... + a2nxn d" b2
x1 x2 xn
...
am1x1 + am2x2 + ... + amnxn d" bm
x1 x2 xn
x1 e" 0, x2 e" 0, ..., xn e" 0
x1 x2 xn
cj  jednostkowy przyrost j  tej czynności w ocenie globalnej Z (j = 1, 2, ...,n)
bi  ilość i  tego zasobu dostępnego do alokacji do czynności (i = 1, 2, ...,m)
aij  ilość i  tego zasobu konsumowanego przez j  tą czynność
cj, bi, aij  parametry;
parametry;
x1, x2, ..., x3  zmienne decyzyjne
zmienne decyzyjne
6
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu
Proces rozwiązywania
Identyfikacja problemu decyzyjnego
problemu decyzyjnego
" zidentyfikuj stan aktualny
 rozpoznaj realizowane działania
Identyfikacja problemu
decyzyjnego
 określ trudności w podjęciu decyzji
" opisz sytuację (zaistniały problem)
Model matematyczny
Konstrukcja modelu matematycznego
problemu
" zidentyfikuj zmienne decyzyjne
 czego poszukujesz?
Dobór metody rozw.
 jakie wielkości mają być wyznaczone?
Rozwiązanie problemu
 ile jest niewiadomych?
" zidentyfikuj parametry zadania
Interpretacja rozw.
 jakie wielkości są znane (stałe)?
Analiza wrażliwości
" 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ć?
7
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu
Proces rozwiązywania
Rozwiązanie problemu (sformułowanego modelu)
problemu decyzyjnego
" poszukiwanie rozwiązania
Identyfikacja problemu
 maksymalizacja funkcji celu
decyzyjnego
 minimalizacja funkcji celu
" rozwiązanie problemu za pomocą dostępnych metod
Model matematyczny
problemu  metoda graficzna (stosowana tylko dla 2 zmiennych
decyzyjnych)
 metoda algebraiczna SIMPLEX (nie ma ograniczenia liczby
Dobór metody rozw.
zmiennych decyzyjnych)
Rozwiązanie problemu
Interpretacja rozwiązania
Interpretacja rozw. " wartość zmiennych decyzyjnych
Analiza wrażliwości
" pozostające zasoby
" analiza wrażliwości
 zmiana dostępności zasobów
8
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu
Proces rozwiązywania
Tok postępowania przy rozwiązywaniu problemu
problemu decyzyjnego
sformułowanego w postaci zadania programowania
liniowego analiza przykładu
Identyfikacja problemu
decyzyjnego
"  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
9
Piotr Sawicki / Zarządzanie transportem
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 = zs+zH
 zs - jednostkowy zysk ze sprzedaży wózków typu 20S
zs = 15% " 19.000 Ź " S = 2.850 S
 zH  jednostkowy zysk ze sprzedaży wózków typu 45H
zH = 19% " 33.000 Ź " H = 6.270 H
 ostateczne sformułowanie funkcji celu
Max Z(S, H) = 2.850 S + 6.270 H
10
Piotr Sawicki / Zarządzanie transportem
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 d" 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 d" 520
11
Piotr Sawicki / Zarządzanie transportem
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 d" 100
dostępność wózków 45H
H d" 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 e" 10
zapotrzebowanie firmy FLS na wózki typu 45H
H e" 5
 formalnie poszukiwane rozwiązanie (S, H) nie powinno przyjmować wartości ujemnych
S e" 0
H e" 0
12
Piotr Sawicki / Zarządzanie transportem
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 d" 2.400
(2) 6 S + 4 H d" 520
(3) S d" 100
(4) H d" 75
(5) S e" 10
(6) H e" 5
(7) S e" 0
(8) H e" 0
13
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Programowanie liniowe
Graficzna metoda rozwiązywanie
Graficzna metoda rozwiązywanie
zadania programowania liniowego
zadania programowania liniowego
14
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
Obszar rozwiązań niedopuszczalnych
H
" rysowanie obszaru rozwiązań
(5)
S e" 10
140
(3) S d" 100
dopuszczalnych
(1) 19 S + 33 H d" 2.400
(2) 6 S + 4 H d" 520
(3) S d" 100
100
(4) H d" 75
(5) S e" 10
H d" 75
75
(6) H e" 5
(4)
(7) S e" 0
(8) H e" 0
(7)
S e" 0
Obszar rozwiązań dopuszczalnych
dla ograniczeń (3)  (8)
H e" 5
20
H e" 0
(6)
(8)
5
0
10 20
100 120
Ograniczenia (7) i (8) są nieaktywne S
15
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
Ograniczenia (3) staje się nieaktywne
programowania liniowego
H
" rysowanie obszaru rozwiązań
(5)
S e" 10
140
(3) S d" 100
dopuszczalnych
(0;130)
(1) 19 S + 33 H d" 2.400
(2) 6 S + 4 H d" 520
(3) S d" 100
6S + 4H d" 520
100
(4) H d" 75
(2)
(5) S e" 10
H d" 75
75
(6) H e" 5
(4)
(7) S e" 0
(8) H e" 0
" ograniczenie (2)
6 S + 4 H = 520
(7)
S e" 0
S = 0 H = 130 (0;130)
H e" 5
20
H e" 0
(6)
H = 0 S = 86,7 (86,7;0)
(8)
5
0
10 20
100 120
S
(86,7; 0)
16
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
H
" rysowanie obszaru rozwiązań
(5)
S e" 10
140
(3) S d" 100
dopuszczalnych
(0;130)
(1) 19 S + 33 H d" 2.400
(2) 6 S + 4 H d" 520
(3) S d" 100
6S + 4H d" 520
100
(4) H d" 75
(2)
(5) S e" 10
H d" 75
75
(6) H e" 5
(0; 72,7)
(4)
(7) S e" 0
(8) H e" 0
19S +33H d" 2 400
" ograniczenie (1)
(1)
19 S + 33 H = 2.400
(7)
S e" 0
S = 0 H = 72,7 (0; 72,7)
H e" 5
20
H e" 0
(6)
H = 0 S = 126,3 (126,3; 0)
(8)
5
0
10 20
100 120
S
(86,7; 0) (126,3; 0)
17
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
H
" określanie kierunku zmiany wartości
S e" 10
140
S d" 100
funkcji celu (tu kierunek przyrostu)
(0;130)
Max Z(S, H) = 2.850 S + 6.270 H
2.850 S + 6.270 H = 0
2 850
6S + 4H d" 520
100
H = - S = -0,45 S
6 270
 Ostatni wierzchołek
 Ostatni wierzchołek
S = 10 H = - 4,5 (10; - 4,5)
H d" 75
75
S = 20 H = - 9 (20; - 9)
19S +33H d" 2 400
Z2=364 800
(40; 40)
Z1=239 400
(40; 20)
20
H e" 5
5
0
Z= 2 850S + 6 270H
-4,5
20
40 100 120
S
-9
(86,7; 0) (126,3; 0)
18
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
H
" określenie punktu przecięcia prostych
S=10
140
S d" 100
S = 10
(0;130)
19S + 33H = 2.400
H = - 19/33 S + 2.400/33
6S + 4H d" 520
S = 10 H = 66,96
100
" określenie wartości funkcji celu
S=10 i H=66,96
H d" 75
75

(10; 66,96)
Z=448.400

19S +33H = 2 400
(40; 40)
Zmax
(40; 20)
20
H e" 5
5
0
-4,5
20
40 100 120
S
-9
(86,7; 0) (126,3; 0)
19
Piotr Sawicki / Zarządzanie transportem
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
20
Piotr Sawicki / Zarządzanie transportem
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 Ź
LHS
" analiza ograniczeń
(1) 19.000 S + 33.000 H d" 2.400.000 (dostępne zasoby finansowe)
dla S=10 szt. i H=66,96 szt. LHS1 = 2.399.680 Ź H" 0 Ź rezerwy finansowej
(2) 6 S + 4 H d" 520 (dostępna liczba roboczogodzin)
dla S=10 szt. i H=66,96 szt. LHS2 = 327,84 rbh 192,16 rbh rezerwy czasu
21
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Interpretacja rozwiązania
" analiza ograniczeń& cd
(3) S d" 100 (maksymalna dostępność wózków typu 20S)
dla S=10 szt. i H=66,96 szt. LHS3 = 10 szt. 90 szt. rezerwy
(4) H d" 75
dla S=10 szt. i H=66,96 szt. LHS4 = 66,96 szt. 8,04 szt. rezerwy
(5) S e" 10
(6) H e" 5
(7) S e" 0
(8) H e" 0
22
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Zastosowanie Solvera Excel / Rozwiązanie problemu
Zapis modelu matematycznego w obszarze roboczym arkusza kalkulacyjnego
23
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport wyników
Maksymalna wartość FC
Wartość zmiennych
decyzyjnych (S, H)
Wartość ograniczenia (LHS) przy
Status ograniczenia
Pozostała do wykorzystania
uzyskanych wartościach zmiennych
 wiążące  zasób w pełni wykorzystany
rezerwa  luz
decyzyjnych
 niewiążący  pozostają rezerwy
analizowanych zasobów
24
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Krańce przedziałów zmienności współczynników FC przy których nie
Raport wrażliwości nastąpi zmiana zestawu zmiennych decyzyjnych
Zmiana z (S`"0 i H`"0) na (S`"0 i H=0) lub (S=0 i H`"0)
Optymalna wartość
zmiennych
decyzyjnych
Współczynniki funkcji
celu
O ile zmieni się wartość FC jeżeli prawa Wartość RHS Krańce przedziałów zmienności RHS,
strona (RHS) odpowiedniego warunku warunków przy których nie nastąpi zmiana zestawu
ograniczającego ulegnie zmianie o 1 ograniczających zmiennych decyzyjnych
25
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Wartość (max)
Raport granic
funkcji celu
Optymalna wartość Obszar rozwiązań dopuszczalnych
zmiennych S  nie ulega zmianie DG=10, GG=10
decyzyjnych H  ulega zmianie: DG=5, GG=66,96
26
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport granic 
H
interpretacja dolnej i górnej
granicy
S e" 10
140
S d" 100
(0;130)
6S + 4H d" 520
100
H d" 75
75
(10; 66,96)
Z(max)=448.400
19S +33H d" 2 400
20
(10; 5)
H e" 5
Z(min)=59.850
5
0
20
100 120
S
(86,7; 0) (126,3; 0)
27
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Programowanie liniowe
Algebraiczna metoda rozwiązywania
Algebraiczna metoda rozwiązywania
zadania programowania liniowego 
zadania programowania liniowego 
metoda SIMPLEX
metoda SIMPLEX
28
Piotr Sawicki / Zarządzanie transportem
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
29
Piotr Sawicki / Zarządzanie transportem
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
(1)
(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
30
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Przykład& cd
" podziel rezultat przez  13 współczynnik przy zmiennej y wyniesie 1
(B1) y = 5
(A1) x + 3y = 17
" współczynniki przy zmiennej x w równaniu A1 oraz zmiennej y w równaniu B1
wynoszą 1
 wyeliminuj zmienną y z równania B1 aby w każdym równaniu była tylko jedna zmienna
decyzyjna (niewiadoma) pomnóż równanie (B1) przez 3 i odejmij od równania (A1)
(A1) x + 3y = 17
3(B1) 3y = 15
(A1)-3(B1) x = 2
" rozwiązanie układu równań (1) stanowi punkt (x, y) = (2, 5)
31
Piotr Sawicki / Zarządzanie transportem
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
(2)
(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
32
Piotr Sawicki / Zarządzanie transportem
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
(B1) y  14z = 4
(A1) x + 3/2y + 2z = 6
" następnie wyeliminuj zmienną y z równania (A1) pomnóż równanie (B1) przez 3/2 i
odejmij od równania (A1)
(A1) x + 3/2y + 2z = 6
3/2(B1) 3/2y  21z = 6
(A1)-3/2(B1) x + 23z = 0
" ostatecznie zredukowany za pomocą procedury G-J układ równań zawiera
(A2) x + 23z = 0
(B2) y  14z = 4
dalsza redukcja G-J nie jest możliwa powstały układ równań ma nieskończoną
liczbę rozwiązań
33
Piotr Sawicki / Zarządzanie transportem
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
34
Piotr Sawicki / Zarządzanie transportem
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
35
Piotr Sawicki / Zarządzanie transportem
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 (<, d", e", >)
" praktyczna interpretacja wprowadzenia przekształceń
 rozważane są dwa przykładowe ograniczenia dot. problemu firmy FLS
np. ogr (2): 6S + 4H d" 520 dotyczące zasobu czasu pracy
np. ogr. (5): S e" 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ą niedoboru N1 (N1e"0) do lewej strony
zmienną niedoboru
nierówności typu (< lub d"), możliwe jest przekształcenie nierówności do postaci równania
6S + 4H d" 520 6S + 4H + N1 = 520
w problemie firmy FLS zmienna niedoboru musi być wprowadzona do 4 ograniczeń, tj. (1),
(2), (3) i (4)
36
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
" praktyczna interpretacja wprowadzenia przekształceń & cd
np. ogr. (5): S e" 10, dotyczące rynkowego popytu na wózki typu S
 założyć można, że zmienna S w ograniczeniu S e" 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ą nadmiaru N2 (N2e"0) do lewej strony
zmienną nadmiaru
nierówności typu (> lub e"), możliwe jest przekształcenie nierówności do postaci równania
S e" 10 S- N2 = 10
w problemie firmy FLS zmienna nadmiaru musi być wprowadzona do 2 ograniczeń, tj.
ograniczenie (5) i (6)
37
Piotr Sawicki / Zarządzanie transportem
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) 19S + 33H d" 2.400 19S + 33H + N1 = 2.400
(2) 6S + 4H d" 520 6S + 4H + N2 = 520
(3) S d" 100 S+ N3 = 100
(4) H d" 75 H + N4 = 100
(5) S e" 10 S- N5 = 10
(6) H e" 5 H - N6 = 5
Układ nierówności Układ równań
" formalnie zmienne N1-N6 musza być wprowadzone do równania funkcji celu Z
Z = 2.850S + 6.270H Z = 2.850S + 6.270H +0N1+0N2+ 0N3+0N4-0N5-0N6
" zakładamy nieujemność wszystkich zmiennych
S, H, N1, N2, N3, N4, N5, N6 e" 0
38
Piotr Sawicki / Zarządzanie transportem
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.850S - 6.270H = 0
19S + 33H + N1 = 2.400
6S + 4H + N2 = 520
S+ N3 = 100
H + N4 = 75
S N5 = 10
H  N6 = 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)
N1 = 2.400, N2 = 520, N3 = 100, N4 = 75 (zmienne niedoboru)
N5 = -10, N6 = -5 (zmienne nadmiaru)
 pierwsze rozwiązanie
(Z, S, H, N1, N2, N3, N4, N5, N6) = (0, 0, 0, 2.400, 520, 100, 75, -10, -5)
39
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Istota metody SIMPLEX & cd
" interpretacja rozwiązania dopuszczalnego układu równań
( Z, S, H, N1, N2, N3, N4, N5, N6 )= ( 0, 0, 0, 2.400, 520, 100, 75, -10, -5)
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)
 uzyskane rozwiązanie nazywane jest dopuszczalnym rozwiązaniem bazowym
dopuszczalnym rozwiązaniem bazowym
 zmienne przyjmujące wartość 0 zmienne niebazowe, pozostałe zmienne bazowe
zmienne niebazowe zmienne bazowe
40
Piotr Sawicki / Zarządzanie transportem
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 (ukształtować nowe dopuszczalne rozwiązanie bazowe)
bazy
 która zmienna powinna opuścić bazę?
 konieczna jest analiza wszystkich ograniczeń
41
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
Istota metody SIMPLEX & cd
" istota poszukiwania kolejnego dopuszczalnego rozwiązania bazowego&
 analiza ograniczeń
19S + 33H + {N1} = 2.400 2.400 / 33 = 72 24/33
6S + 4H + {N2} = 520 520 / 4 = 130
S+ {N3} = 100 100 / 0 = 0
H + {N4} = 75 75 / 1 = 75
S {N5} = 10 10 / 0 = 0
H  {N6} = 5 5 / 1 = 5 minimum
minimum
RHS / Współczynnik przy H
 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, N1, N2, N3, N4, N5, N6) = (31.350, 0, 5, 2.235, 500, 100, 70, -10, 0)
S i N6 zmienne niebazowe (N6 wyszła z bazy)
H, N1, N2, N3, N4 i N5 zmienne bazowe (H weszła do bazy)
42
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
" mechanizm poszukiwania kolejnych bazowych rozwiązań dopuszczalnych
 identyfikacja tzw. równania głównego
(A) Z  2.850S  6.270H = 0
równania, z
(B) 19S + 33H + N1 = 2.400
których należy
wyeliminować
(C) 6S + 4H + N2 = 520
zmienną H
(D) S+ N3 = 100
(E) H + N4 = 75
(F) S N5 = 10
(G) H  N6 = 5
równanie główne
 eliminacja zmiennej H z równania A wg zasady redukcji G-J
(A) Z  2.850S  6.270H = 0
(G)x6.270 6.270H  6.270N6 = 31.350
(A)+(G)x6.270 Z  2850S  6.270N6 = 31.350
 eliminacja zmiennej H z równania B wg zasady redukcji G-J
(B) 19S + 33H + N1 = 2.400
(G)x33 33H  33N6 = 165
(B)-(G)x33 19S + N1 + 33N6 = 2.235
43
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
" mechanizm poszukiwania kolejnych bazowych rozwiązań dopuszczalnych
 ostateczny układ równań w I-szej iteracji
RHS / Współczynnik przy S
(A1) Z  2.850S  6.270N6 = 31.350
2.235 / 19 = 117 12/19
(B1) 19S + N1 +33N6 = 2.235
500 / 6 = 83 1/3
(C1) 6S +N2 +4N6 = 500
100 / 1 = 100
(D1) S + N3 = 100
75 / 0 = 0
(E1) +N4 +N6 = 70
10 / 1 = 10
minimum
(F1) S  N5 = 10 minimum
5 / 0 = 0
(G1) H  N6 = 5
równanie główne
 nowe dopuszczalne rozwiązanie bazowe:
(Z, S, H, N1, N2, N3, N4, N5, N6) = (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 F1
 eliminacja zmiennej S z równania A1 wg zasady redukcji G-J
(A1) Z  2.850S  6.270N6 = 31.350
(F1)x2.850 2.850S  2.850N5 = 28.850
(A1)+(F1)x2.850 Z  2.850N5  6.270N6= 59.850
44
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
" mechanizm poszukiwania kolejnych bazowych rozwiązań dopuszczalnych
 ostateczny układ równań w II-giej iteracji
RHS / Współczynnik przy N6
(A2) Z  2.850N5  6.270N6 = 59.850
równanie główne
2.045 / 33 = 61 32/33
(B2) + N1 +19N5 +33N6 = 2.045
440 / 4 = 110
(C2) +N2 +6N5 +4N6 = 440
90 / 0 = 0
(D2) + N3 +N5 = 90
70 / 1 = 70
(E2) +N4 +N6 = 70
10 / 0 = 0
(F2) S  N5 = 10
5 / -1 = -5
(G2) H  N6 = 5
 nowe dopuszczalne rozwiązanie bazowe:
(Z, S, H, N1, N2, N3, N4, N5, N6) = (59.850, 10, 5, 2.045, 440, 90, 70, 0, 0)
 poszukiwanie kolejnej zmiennej niebazowej wchodzącej do bazy zmienna N6
 poszukiwanie nowego równania głównego równanie B2
 równanie B2 po przekształceniu współczynnik 1 przy zmiennej N6
(B2) +1/33 N1 +19/33N5 +N6 = 2.045/33
45
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Proces rozwiązywania problemu / Metoda SIMPLEX
" mechanizm poszukiwania kolejnych bazowych rozwiązań dopuszczalnych
 ostateczny układ równań w III-giej iteracji
(A3) Z +2.045/33 N1 +760N5 = 448.400
(B3) +1/33 N1 +19/33N5 +N6 = 2.045/33 H" 61,96
(C3)  4/33 N1 +N2 +122/33N5 = 6.340/33 H" 192,12
(D3) + N3 +N5 = 90
(E3)  1/33 N1 +N4 19/33N5 = 265/33 H" 8,03
(F3) S  N5 = 10
(G3) H +1/33N1 +19/33N5 = 2.210/33 H" 66,96
 rozwiązanie optymalne
(Z, S, H, N1, N2, N3, N4, N5, N6) = (448.400; 10; 66,96; 0; 192,12; 90; 8,03; 0; 61,96)
46
Piotr Sawicki / Zarządzanie transportem
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) znajdz
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) przeprowadz
redukcje G-J na nowej zmiennej bazowej
(9) określ nowe bazowe rozwiązanie dopuszczalne
47
Piotr Sawicki / Zarządzanie transportem
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
48
Piotr Sawicki / Zarządzanie transportem
Programowanie liniowe
Podsumowanie
Podstawowe pojęcia do zapamiętania Przykłady obszarów rozwiązań
dopuszczalnych
" rozwiązanie dopuszczalne 
rozwiązanie dla którego spełnione są " funkcja celu może przyjmować
wszystkie ograniczenia nieograniczone wartości
" 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) 
" obszar rozwiązań dopuszczalnych jest
rozwiązanie dopuszczalne osiągające
pusty
wartość ekstremalną
" ograniczenie aktywne  ograniczenie
wyznaczające obszar rozwiązań
dopuszczalnych
" ograniczenie nieaktywne 
ograniczenie nie należące do obszaru
rozwiązań dopuszczalnych
49
Piotr Sawicki / Zarządzanie transportem
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
50
Piotr Sawicki / Zarządzanie transportem
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 dm3 oleju napędowego, pobór 45 kWh energii
 przejazd 1,5 pociągu na trasie Poznań-Warszawa?
51
Piotr Sawicki / Zarządzanie transportem
Zarządzanie transportem
Zarządzanie transportem
Programowanie liniowe
Programowanie liniowe
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
pok. 719, tel. [phone]
E-mail: [e-mail]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs
URL: http://www.put.poznan.pl/~piotrs