PODSTAWY LOGISTYKI
dr inż. Paweł Gomoliński
p. 3.15 A
Literatura
1. M. Siudak, Badania operacyjne , OWPW, 1997
2. H. Wagner, Badania operacyjne , PWE, 1980
3. F. Hillier, G. Lieberman, Introduction to Operations
Research , McGraw-Hill International Editions
16-02-2010
Warunki zaliczenia
2 prace kontrolne:
1. Analiza sieciowa 30 pkt.
(min. 16 pkt.)
2. Programowanie liniowe, modele decyzyjne 60 pkt.
(min. 31 pkt.)
______________
Ł 90 pkt.
47 54 3,0
55 64 3,5
65 74 4,0
75 84 4,5
85 90 5,0
Paweł Gomoliński, Podstawy logistyki 0-1 16-02-2010
Logistyka rys historyczny
Korzenie etymologiczne pojęcia logistyka sięgają języka
greckiego, w którym występują m.in. słowa:
" Logos słowo, mowa, myśl, rachunek;
" Logike logika;
" Logistike sztuka liczenia, sztuka kalkulowania.
Początkowo termin logistyka używany był w obszarze
militarnym. Obejmował wszystkie działania służące
zaopatrzeniu oddziałów, takie jak:
" planowanie dróg i magazynów wojskowych,
" transport osób i sprzętu,
" dostawa zaopatrzenia i części zamiennych.
Paweł Gomoliński, Podstawy logistyki 0-2 16-02-2010
Pierwsze zastosowania logistyki
Działania wojskowe: - Cesarz Leon VI (865-912 n.e.)
- Baron de Jomini (1837 r.)
Gospodarka: - USA (1955 r.)
Logistyka występowała pod nazwą
bussines logistics, a jej celem było
osiągnięcie optymalnej koordynacji
przepływu materiałów, surowców,
czynności związanych z ich
magazynowaniem, czynności
manipulacyjnych towarów, problemów
dotyczących opakowania,
magazynowania i przepływu wyrobów
gotowych do ich ostatecznych odbiorców
- Europa RFN (1970 r.)
Paweł Gomoliński, Podstawy logistyki 0-3 16-02-2010
Przyczyny rozwoju logistyki
" recesja w USA (1950)
" wysoki poziom wydajności produkcji
" wzrost kosztów transportu
" zmiana filozofii podejścia do klienta
" rozwój techniki komputerowej
" rozwój telekomunikacji
Obecne zastosowania logistyki
" wojsko
" gospodarka
" służba zdrowia (szpitale)
" turystyka
" ...
Paweł Gomoliński, Podstawy logistyki 0-4 16-02-2010
Definicja logistyki
Obecnie logistyka pojmowana jest jako:
Zintegrowane zarządzanie, planowanie i sterowanie
przepływem materiałów i informacji, mające na celu
optymalne tworzenie i transformację wartości (dóbr).
Cele logistyki
Ekonomiczne (tj. przy minimalnych kosztach) dostarczanie:
" właściwego dobra (materiały, wyroby, informacje, usługi,
energia),
" we właściwej ilości,
" o właściwej jakości,
" z właściwą informacją (nie więcej niż potrzeba!),
" o właściwym czasie,
" do właściwego miejsca.
Paweł Gomoliński, Podstawy logistyki 0-5 16-02-2010
Logistyka jest obecnie dziedziną wiedzy dążącą do
integracji przedsiębiorstw w celu optymalnego kształtowania
łańcuchów zaopatrzeniowych dóbr od momentu pozyskania
surowców, poprzez wytworzenie produktu, aż po jego
dystrybucję do ostatecznego nabywcy.
Logistyka wykorzystuje i integruje wiedzę z zakresu
informatyki, techniki i komercji, stawiając za cel badanie i opis
związków, których znajomość umożliwia analizę strat i
zysków, i które stanowią bazę do podejmowania decyzji w
ramach strategicznego planowania działań przedsiębiorstwa.
W obecnych czasach warunkiem przetrwania dla
przedsiębiorstw uczestniczących w wytwarzaniu wszelkiego
rodzaju dóbr i usług jest konieczność produkcji wyrobów o
możliwie wysokiej jakości i funkcjonalności, przy
minimalnym koszcie zarówno wytwarzania, jak i dystrybucji.
Paweł Gomoliński, Podstawy logistyki 0-6 16-02-2010
Interdyscyplinarny charakter logistyki
Paweł Gomoliński, Podstawy logistyki 0-7 16-02-2010
Paweł Gomoliński, Podstawy logistyki 0-8 16-02-2010
Schemat strukturalny logistyki i poziomy jej działania
Logistyka produkcji
Naczelną ideą logistyki produkcji jest zasada Just-In-Time
(dokładnie na czas), wywodząca się z japońskiej metody
planowania procesu produkcyjnego, zwanej Kanban.
Realizacja tej zasady pozwala do minimum ograniczyć
koszty magazynowania. Warunkiem jest synchronizacja
procesów produkcyjnych, ale przede wszystkim
przedprodukcyjnych (szczególnie w sferze zaopatrzenia i
kooperacji) i poprodukcyjnych (odbiór, dystrybucja), aby
wyeliminować lub do minimum ograniczyć zakłócenia.
Wdrożenie zasady Just-In-Time umożliwia zmniejszenie
poziomu zapasów nawet o połowę, co jest o tyle istotne, że
90% czasu pozostawania materiału w przedsiębiorstwie
dotyczy różnego rodzaju magazynowania.
Paweł Gomoliński, Podstawy logistyki 0-9 16-02-2010
Paweł Gomoliński, Podstawy logistyki 0-10 16-02-2010
Podstawa logistyki myślenie systemowe
" Analiza (i optymalizacja) całego systemu logistycznego, a nie
jego podsystemów (kompromis)
" Globalne ujęcie kosztów funkcjonowania systemu
logistycznego
Optymalizacja w logistyce
Oczekiwane efekty:
- poprawa organizacji systemu logistycznego
- spadek kosztów magazynowania
- skrócenie czasu realizacji zamówienia
- ...
Kryterium:
Stosunek wydajności do kosztów
Paweł Gomoliński, Podstawy logistyki 0-11 16-02-2010
Przykład
Logistyka porozumień handlowych: realizacja kontraktu w
przedsiębiorstwie przy minimalnych kosztach. Inaczej mówiąc,
jest to spełnienie oczekiwań klienta przy równoczesnym
zapewnieniu odpowiedniej rentowności przedsięwzięcia.
Ważnym atutem rynkowym jest szybkość realizacji
zamówień, jednak może to wiązać się z koniecznością
utrzymywania wysokiego poziomu zapasów magazynowych.
Zadaniem logistyki jest tu znalezienie kompromisu
pomiędzy możliwościami technicznymi, poziomem zapasów i
terminem realizacji zamówienia.
Paweł Gomoliński, Podstawy logistyki 0-12 16-02-2010
Paweł Gomoliński, Podstawy logistyki 0-13 16-02-2010
Metody optymalizacji i planowania w logistyce
" rachunek różniczkowy
" programowanie liniowe i nieliniowe
" drzewo decyzyjne
" heurystyka
" teoria kolejek
" symulacja
Poziomy optymalizacji systemu logistycznego:
" Optymalizacja wyboru środków transportu (struktura środków
transportu)
" Optymalizacja kosztów dla każdego środka transportu
(organizacja, redundancja)
" Optymalizacja konstrukcji maszyny jako ogniwa systemu
logistycznego (trwałość, wydajność, sprawność, efektywność,
gotowość)
Paweł Gomoliński, Podstawy logistyki 0-14 16-02-2010
Przykład: optymalizacja kosztów
Paweł Gomoliński, Podstawy logistyki 0-15 16-02-2010
Typowe problemy w logistyce
Klasyczny problem transportu
Jednakowe towary od pewnej liczby dostawców muszą być
dostarczane do różnych miejsc przeznaczenia (odbiorców).
Dostawcy dysponują określonymi zapasami, zaś odbiorcy mają
określone zapotrzebowania.
Należy tak sporządzić plan transportu (dostaw), aby
zadanie zrealizować przy najniższych kosztach. Zakłada się
przy tym, że koszty transportu są proporcjonalne do ilości
towarów i długości trasy, i że w rozpatrywanym czasie są stałe.
Problem skąpej przestrzeni
W tym przypadku chodzi o optymalne wypełnienie pewnej
ograniczonej przestrzeni towarami, które mogą mieć różne
wymiary lub przynosić różne korzyści.
Do tych problemów należą takie zagadnienia, jak:
" najlepsze rozplanowanie wykrojów z blachy (minimalizacja
odpadów),
" optymalne wypełnienie skrzyni ładunkowej samochodu,
palety, przestrzeni magazynowej itp.
Paweł Gomoliński, Podstawy logistyki 0-16 16-02-2010
Problem przyporządkowania
Poszukuje się najkorzystniejszego przyporządkowania
określonych ilości różnych elementów, np.:
" personelu dla maszyn,
" przedmiotów obrabianych do maszyn,
" środków transportu do towarów,
" pomocniczych środków transportu do towarów.
Znane są przy tym koszty wszystkich możliwych par
przyporządkowania. Koszty te są wzajemnie niezależne.
Problem przepływu materiału
Zadanie polega na przetransportowaniu przy pomocy
istniejącego systemu transportu maksymalnej ilości towarów z
miejsca nadania do miejsca przeznaczenia poprzez zadaną
sieć dróg, przy czym znane są długości oraz przepustowości
wszystkich tras.
Paweł Gomoliński, Podstawy logistyki 0-17 16-02-2010
Problem akwizytora (Traveling salesman problem)
Zadanie polega na takim zaplanowaniu trasy z miejsca
startu do miejsca przeznaczenia poprzez różne punkty
pośrednie, które będzie optymalne pod względem:
" czasu,
" długości trasy
i/lub
" kosztów.
W zależności od postawionego celu, znane są:
" czasy transportu,
" odległości lub koszty transportu pomiędzy wszystkimi
stacjami itd.
Przykładem może tu być optymalizacja trasy układnicy w
magazynie wysokiego składowania przy realizacji zamówienia.
Paweł Gomoliński, Podstawy logistyki 0-18 16-02-2010
Systemy i procesy logistyczne
Systemy logistyczne: systemy uczestniczące w czasowo-
przestrzennej transformacji dóbr.
Procesy logistyczne: procesy dokonujące się w systemach
logistycznych.
Realizuje się w nich przepływ dóbr oraz towarzyszących im
informacji i wartości pomiędzy systemami wytworzenia i
użytkowania.
Paweł Gomoliński, Podstawy logistyki 0-19 16-02-2010
System logistyczny przedsiębiorstwa
Paweł Gomoliński, Podstawy logistyki 0-20 16-02-2010
Podstawowe struktury systemów logistycznych
System jednostopniowy (przepływ bezpośredni)
Punkt Punkt
nadania odbioru
System wielostopniowy z dekoncentracją (przepływ pośredni)
Punkt Punkt de-
nadania koncentracji
Punkty
odbioru
System wielostopniowy z koncentracją (przepływ pośredni)
Punkt Punkt
koncentracji odbioru
Punkty
nadania
Paweł Gomoliński, Podstawy logistyki 0-21 16-02-2010
System kombinowany (przepływ bezpośredni i pośredni)
Punkt Punkt de-
nadania koncentracji
Punkty
odbioru
Paweł Gomoliński, Podstawy logistyki 0-22 16-02-2010
Sieciowe modele decyzyjne
" Analiza sieciowa elementy teorii grafów
" Modele sieciowe procesów
" Metoda ścieżki krytycznej minimalizacja czasu realizacji
przedsięwzięcia
" Optymalizacja kosztów przedsięwzięcia
Paweł Gomoliński, Podstawy logistyki 1-1 16-02-2010
Paweł Gomoliński, Podstawy logistyki 1-2 16-02-2010
Paweł Gomoliński, Podstawy logistyki 1-3 16-02-2010
Paweł Gomoliński, Podstawy logistyki 1-4 16-02-2010
1. Problem najmniejszego rozpięcia drzewa
Zadanie polega na stworzeniu sieci w postaci drzewa, które
połączy wszystkie węzły przy najkrótszej sumie połączeń.
Problem ten może mieć zastosowanie przy planowaniu:
" sieci komunikacyjnych i telekomunikacyjnych
" sieci komputerowych
" sieci dystrybucji (połączenie magazynów, punktów sprzedaży)
" pokładowej sieci CAN pojazdu
Algorytm rozwiązania
Poszukiwanie najkrótszego połączenia od dotychczas
wybranego (wybranych) węzła (węzłów) do kolejnych, jeszcze
nie połączonych węzłów.
Paweł Gomoliński, Podstawy logistyki 1-5 16-02-2010
Paweł Gomoliński, Podstawy logistyki 1-6 16-02-2010
Przykład 1
Zużywając jak najmniej przewodu sieciowego połączyć serwer
komputerowy z terminalami tak, aby każdy łączył się z nim
bezpośrednio lub pośrednio.
Dane:
Odległości pomiędzy poszczególnymi stanowiskami roboczymi:
S K1 K2 K3 K4 K5
S 190 70 115 270 160
K1 190 100 240 215 50
K2 70 100 140 120 220
K3 115 240 140 175 80
K4 270 215 120 175 310
K5 160 50 220 80 310
Paweł Gomoliński, Podstawy logistyki 1-7 16-02-2010
Rozwiązanie:
Algorytm:
1. Wybranie węzła początkowego ( S).
2. Wybranie węzła, którego odległość od węzła początkowego
jest najmniejsza.
3. Wybranie kolejnego, jeszcze nie wybranego węzła, którego
odległość od jednego z wcześniej wybranych węzłów jest
najmniejsza.
4. Powtarzanie kroku 3. aż do zrównania liczby wybranych
węzłów z liczbą węzłów sieci.
Paweł Gomoliński, Podstawy logistyki 1-8 16-02-2010
S K1 K2 K3 K4 K5
S 190 70 (1) 115 270 160
K1 190 100 (2) 240 215 50 (3)
K2 70 (1) 100 (2) 140 120 (5) 220
K3 115 240 140 175 80 (4)
K4 270 215 120 (5) 175 310
K5 160 50 (3) 220 80 (4) 310
1) S S K2 70
2) S, K2 K2 K1 100
3) S, K1, K2 K1 K5 50
4) S, K1, K2, K5 K5 K3 80
5) S, K1, K2, K3, K5 K2 K4 120
420
S K2 K1 K5 K3
|
K4
Paweł Gomoliński, Podstawy logistyki 1-9 16-02-2010
Graf
100
K1 K2
190
50 215
140
70
240
220
S
160
115
K3
K5
80
270
120
310 175
K4
100
K1 K2
190
50 215
140
70
240
220
S
160
115
K3
K5
80
270
120
310 175
K4
Paweł Gomoliński, Podstawy logistyki 1-10 16-02-2010
100
K1 K2
190
50 215
140
70
240
220
S
160
115
K3
K5
80
270
120
310 175
K4
100
K1 K2
190
50 215
140
70
240
220
S
160
115
K3
K5
80
270
120
310 175
K4
Paweł Gomoliński, Podstawy logistyki 1-11 16-02-2010
100
K1 K2
190
50 215
140
70
240
220
S
160
115
K3
K5
80
270
120
310 175
K4
100
K1 K2
190
50 215
140
70
240
220
S
160
115
K3
K5
80
270
120
310 175
K4
Ł = 420
Paweł Gomoliński, Podstawy logistyki 1-12 16-02-2010
2. Problem najkrótszej trasy przejazdu
Przykład 1
A
7
2
2
D
4
5
5
O
B 1
4 T
3
7
1
4
E
C
Dane:
" Sieć połączeń
" Czas przejazdu wzdłuż każdej drogi
Wyznaczyć najkrótszą trasę z punktu O do T.
Paweł Gomoliński, Podstawy logistyki 1-13 16-02-2010
Algorytm rozwiązania:
Poszukiwanie najkrótszych dróg zaczynając od punktu
startowego i kolejno poprzez wszystkie możliwe połączenia.
Uwaga:
1. Boki grafu mogą reprezentować koszty określonej
działalności. Wówczas zadanie polega na minimalizacji
kosztów całkowitych.
2. Boki grafu mogą reprezentować czasy trwania określonych
działań. Wówczas zadanie polega na minimalizacji czasu
trwania przedsięwzięcia.
Paweł Gomoliński, Podstawy logistyki 1-14 16-02-2010
Rozwiązanie:
Krok Wybrane Sąsiednie Aączna Następny Najkrótsza Ostatnie
iteracji węzły węzły nie odległość do najbliższy odległość połączenie
n wybrane rozpatrywanego węzeł (od startu)
wcześniej węzła
1 O A 2 A 2 OA
O B 5
O C 4
2 O B 5
O C 4 C 4 OC
A B 2 + 2 = 4 B 4 AB
A D 2 + 7 = 9
3 A D 9
B D 4 + 4 = 8
B E 4 + 3 = 7 E 7 BE
C E 4 + 4 = 8
4 A D 9
B D 8 D 8 BD
E D 7 + 1 = 8 D 8 ED
E T 7 + 7 = 14
5 D T 8 + 5 = 13 T 13 DT
E T 14
Paweł Gomoliński, Podstawy logistyki 1-15 16-02-2010
Rozwiązanie cd. (wyznaczenie najkrótszej trasy):
Krok Wybrane Sąsiednie Aączna Następny Najkrótsza Ostatnie
iteracji węzły węzły nie odległość do najbliższy odległość połączenie
n wybrane rozpatrywanego węzeł (od startu)
wcześniej węzła
1 O A 2 A 2 OA
O B 5
O C 4
2 O B 5
O C 4 C 4 OC
A B 2 + 2 = 4 B 4 AB
A D 2 + 7 = 9
3 A D 9
B D 4 + 4 = 8
B E 4 + 3 = 7 E 7 BE
C E 4 + 4 = 8
4 A D 9
B D 8 D 8 BD
E D 7 + 1 = 8 D 8 ED
E T 7 + 7 = 14
5 D T 8 + 5 = 13 T 13 DT
E T 14
Wynik znajduje się od końca:
1. T-D-E-B-A-O (= 13)
lub
2. T-D-B-A-O (= 13)
Paweł Gomoliński, Podstawy logistyki 1-16 16-02-2010
A
7
2
2
D
4
5
5
O
B 1
T
4
3
7
1
4
E
C
T-D-E-B-A-O (13)
A
7
2
2
D
4
5
5
O
B
1
4 T
3
7
1
4
E
C
T-D-B-A-O (13)
Paweł Gomoliński, Podstawy logistyki 1-17 16-02-2010
Przykład 2
6
A
D
3
5
4 2
3
3 3
1
C
O E T
2
4 2 6
2
7
B
F
Wyznaczyć najkrótszą trasę z punktu O do T.
Paweł Gomoliński, Podstawy logistyki 1-18 16-02-2010
Krok Wybrane Sąsiednie Aączna Następny Najkrótsza Ostatnie
iteracji węzły węzły nie odległość do najbliższy odległość połączenie
n wybrane rozpatrywanego węzeł (od startu)
wcześniej węzła
1 O A 3 A 3 OA
O B 4
2 O B 4 B 4 OB
A B 3 + 1 = 4 B 4 AB
A C 3 + 4 = 7
A D 3 + 6 = 9
3 A C 7
A D 9
B C 4 + 2 = 6 C 6 BC
B F 4 + 7 = 11
4 A D 9
B F 11
C D 6 + 2 = 8 D 8 CD
C E 6 + 3 = 9
C F 6 + 2 = 8 F 8 CF
5 C E 9 E 9 CE
D E 8 + 3 = 11
D T 8 + 5 = 13
F E 8 + 2 = 10
F T 8 + 6 = 14
6 D T 13
E T 9 + 3 = 12 T 12 ET
F T 14
O-A-B-C-E-T lub O-B-C-E-T (= 12)
Paweł Gomoliński, Podstawy logistyki 1-19 16-02-2010
3. Problem maksymalnego przepływu
(przepustowości sieci)
Zadanie polega na takim zorganizowaniu tras przejazdów, aby
uzyskać maksymalną ilość przejazdów w ciągu dnia.
Należy przy tym uwzględnić ograniczenia przejazdów wzdłuż
poszczególnych boków grafu.
Paweł Gomoliński, Podstawy logistyki 1-20 16-02-2010
Algorytm rozwiązania polega na realizacji następujących
kroków:
1. Znalezć dowolną, wcześniej nie wybraną, trasę od punktu
startowego do punktu końcowego o dodatniej
przepustowości. (Jeżeli taka nie istnieje koniec iteracji.)
2. Znalezć na tej trasie drogę o minimalnej przepustowości
(cmin) i o tę liczbę powiększyć dotychczasową wartość
przepustowości całej sieci. (Początkowa wartość
przepustowości sieci = 0).
3. Pomniejszyć przepustowość wszystkich dróg wybranej
trasy o wartość cmin.
Paweł Gomoliński, Podstawy logistyki 1-21 16-02-2010
Paweł Gomoliński, Podstawy logistyki 1-22 16-02-2010
Twierdzenie teorii sieci o optymalności rozwiązania problemu
maksymalnego przepływu ( max-flow min-cut ):
Maksymalna przepustowość każdej sieci z jednym punktem
startowym i jednym punktem końcowym równa jest
najmniejszej sumie przepustowości dróg z wszystkich
przecięć.
Paweł Gomoliński, Podstawy logistyki 1-23 16-02-2010
Modele sieciowe procesów nieregularnych
Proces nieregularny jest to przedsięwzięcie
wieloczynnościowe (na ogół jednorazowe), o nietypowej
strukturze i przebiegu.
Przykłady:
" procesy technicznego przygotowania produkcji
" przedsięwzięcia badawczo-rozwojowe
" modernizacja zakładu przemysłowego
" przedsięwzięcia inwestycyjne lub organizacyjne (niektóre)
" produkcja na zamówienie (jednostkowa)
Opisu struktury procesu nieregularnego dokonuje się za
pomocą modelu sieciowego, zwanego siecią czynności.
Sieć stanowi połączenie grafu ze zbiorem funkcji określonych
na zbiorze jego wierzchołków i zbiorze jego gałęzi.
Model sieciowy pozwala na rozwiązywanie różnorodnych
problemów decyzyjnych za pomocą odpowiednich metod
analizy.
Paweł Gomoliński, Podstawy logistyki 2-1 16-02-2010
Sieć czynności Model sieciowy do opisu struktury
procesów nieregularnych.
Jest to graf przedstawiający strukturę kolejności realizacji
poszczególnych czynności.
j
bok
i
wierzchołek
wierzchołek
boki czynności (procesy)
wierzchołki zdarzenia (stany realizacji przedsięwzięcia)
" Boki są skierowane (czynność
)
" Zdarzenie j zaistnieje w momencie zakończenia czynności
.
" Rozpoczęcie czynności jest możliwe z chwilą zajścia
zdarzenia j.
Paweł Gomoliński, Podstawy logistyki 2-2 16-02-2010
Porządek czynności zależy od następujących ograniczeń:
" technologicznych wynikających z technologii procesu;
" czasowych gdy dana czynność musi zostać rozpoczęta lub
zakończona w określonym momencie;
" wynikających z niepodzielności zasobów np. 1 koparka i
kilka wykopów do wykonania narzuca konieczność realizacji
czynności szeregowo (a nie równolegle);
" wynikających z wielkości zasobów np. ograniczona ilość
siły roboczej, która musi być dzielona pomiędzy czynności
(fronty czynności).
Zbudowanie sieci czynności wymaga znajomości listy
czynności oraz odwzorowania powyższych ograniczeń.
Paweł Gomoliński, Podstawy logistyki 2-3 16-02-2010
Czynności fikcyjne
Określenie relacji chronologicznych w sieci, wynikających
z wymogów np. technologicznych, wymaga niekiedy
wprowadzenia czynności fikcyjnych (pozornych).
Określają one jedynie następstwa czynności w przypadku
działań realizowanych równolegle, lecz w określonej
chronologii.
Ich czas realizacji jest zerowy.
Przykład:
2
1 4
3
Czynność <3, 4> nie może się rozpocząć przed zakończeniem
czynności <1, 2> (oraz czynności <1, 3>).
Paweł Gomoliński, Podstawy logistyki 2-4 16-02-2010
Przykład
Sieć czynności ujmująca ograniczenia technologiczne
i czasowe pewnego przedsięwzięcia [1]:
<1, 3> badanie popytu
<1, 2> nabycie surowców na prototypy
<3, 4> wyprodukowanie prototypów i ocena ich jakości
<4, 6> nabycie surowców do produkcji
<4, 5> wybór opakowań
<5, 9> nabycie opakowań
<6, 7> analiza kosztów produkcji
<6, 10> reklama, zbieranie zamówień
<7, 8> analiza ekonomiczna
<8, 9> proces produkcji wyrobu
<9, 10> pakowanie wyrobu gotowego
<10, 11> dystrybucja do handlu
5 9
2
1 4 7 8 11
3 10
6
Paweł Gomoliński, Podstawy logistyki 2-5 16-02-2010
Uporządkowanie zdarzeń w sieci tak, aby
dla każdego i < j
(odzwierciedlenie następstwa w czasie)
Porządkowanie warstwowe
Podział zdarzeń na warstwy:
W0 zdarzenia bez poprzedników;
Wk zdarzenia, dla których poprzedniki należą do warstw
W0,..., Wk-1.
Algorytm porządkowania warstwowego:
1. Zbudowanie binarnej macierzy przejść Pb.
2. Przyporządkowanie warstwie W0 zdarzeń odpowiadających
zerowym kolumnom macierzy przejść. (Ponieważ sieć
czynności nie może zawierać pętli, zawsze musi istnieć co
najmniej jedna kolumna zerowa.)
3. Wykreślenie z macierzy Pb kolumn zerowych, a następnie
wierszy o tych samych numerach, co wykreślone kolumny.
4. Przyporządkowanie warstwie W1 zdarzeń odpowiadających
zerowym kolumnom zredukowanej macierzy przejść.
5. Powtarzanie czynności 3. i 4. aż do wyczerpania zbioru
zdarzeń.
Paweł Gomoliński, Podstawy logistyki 2-6 16-02-2010
Przykład
5 2
4
1
3
Binarna macierz przejść Pb:
1 2 3 4 5
j
i
1
0 1 1 0 0
2
0 0 0 1 0
3
0 0 0 1 0
4
0 0 0 0 0
5
1 1 0 0 0
Paweł Gomoliński, Podstawy logistyki 2-7 16-02-2010
j 1 2 3 4 5
i
1 0 1 1 0 0
2 0 0 0 1 0
3 0 0 0 1 0
4 0 0 0 0 0
5 1 1 0 0 0 W0
j 1 2 3 4 5
i
1 0 1 1 0 0 W1
2 0 0 0 1 0
3 0 0 0 1 0
4 0 0 0 0 0
5 1 1 0 0 0 W0
j 1 2 3 4 5
i
1 0 1 1 0 0 W1
2 0 0 0 1 0
W2
3 0 0 0 1 0
4 0 0 0 0 0 W3
5 1 1 0 0 0 W0
Paweł Gomoliński, Podstawy logistyki 2-8 16-02-2010
4
1
5 2
5
4
2
3
1
3
W0 W1 W2 W3
W0 5
W1 1
W2 2, 3
W3 4
Paweł Gomoliński, Podstawy logistyki 2-9 16-02-2010
Metoda ścieżki krytycznej
(CPM Critical Path Method)
Historycznie najwcześniejsza metoda analizy sieciowej.
Umożliwia takie zaplanowanie harmonogramu przedsięwzięcia,
aby czas realizacji był najkrótszy.
Wymaga uprzedniego określenia sieci czynności
(zdeterminowania struktury) oraz określenia czasów realizacji
czynności tij (zdeterminowania czasów).
Paweł Gomoliński, Podstawy logistyki 3-1 16-02-2010
5
2 5
3
3
8
7
1 3
4
2
5
3
4 6
tij
i j
i zdarzenie poprzedzające
j zdarzenie następujące
tij czas realizacji czynności
tij = 0 czynność pozorna (najpierw musi zajść zdarzenie i)
Paweł Gomoliński, Podstawy logistyki 3-2 16-02-2010
Z kolei czasy realizacji czynności determinują:
Twi najwcześniejszy możliwy termin wystąpienia zdarzenia i
Tpi najpózniejszy dopuszczalny termin wystąpienia
zdarzenia i
Twi tij Twj
j
i
Tpi Tpj
Twj = max {Twi + tij} (j = 2, 3,..., n; i = j-1)
Tpi = min {Tpj - tij} (i = n-1, n-2,..., 1; j = i+1)
Tw1
1
Tp1
t1,4
Tw4
Tw2
t2,4
i 4
2
Tp4
Tp2
t3,4
j
Tw3
3
t3,5
Tp3
Tw5
5
Tp5
Paweł Gomoliński, Podstawy logistyki 3-3 16-02-2010
Najwcześniejszy możliwy termin wystąpienia zdarzenia j
(zdarzenie j może zajść wtedy, gdy zakończą się wszystkie
czynności, dla których jest ono zdarzeniem końcowym)
Twj = max {Twi + tij} j = 2, 3, ..., n (następniki)
i = 1, 2, ..., n-1 (poprzedniki)
5
3 8
2 5
3
3
8
0 6
7 14
1 3
4
2
5
3
2 8
4 6
Paweł Gomoliński, Podstawy logistyki 3-4 16-02-2010
Najpózniejszy dopuszczalny termin wystąpienia zdarzenia i
Tpi = min {Tpj - tij} i = n-1, n-2, ..., 1
j = n, n-1, n-2, ..., 2
5
2 5
4 9
3
3
8
7 14
1 3
0 6
4
2
5
3
4 6
2 9
Paweł Gomoliński, Podstawy logistyki 3-5 16-02-2010
Przykład obliczania czasów Twj i Tpi:
2
2 5
5
7
9 2
1 3 6
2
7
12
3
4
Twi tij Twj
i j
Tpi Tpj
Twj = max {Twi + tij} (j = 2, 3,..., n; i = j-1)
Tpi = min {Tpj tij} (i = n-1, n-2,..., 1; j = i+1)
Paweł Gomoliński, Podstawy logistyki 3-6 16-02-2010
2
5 9
2 5
5
7
9 2
0 9 11
1 3 6
2
16
7
12
3
12
4
Twi tij Twj
i j
Twj = max {Twi + tij}
Tw1 = 0
Tw2 = max {0+5} = 5 i " {1}
Tw3 = max {0+9} = 9 i " {1}
Tw4 = max {0+12} = 12 i " {1}
Tw5 = max {5+2, 9+0} = 9 i " {2, 3}
Tw6 = max {9+2} = 11 i " {3}
Tw7 = max {12+3, 11+2, 9+7} = 16 i " {4, 5, 6}
Paweł Gomoliński, Podstawy logistyki 3-7 16-02-2010
2
5 9
2 5
7 9
5
7
9 2
0 9 11
1 3 6
2
0 9 14
16
7
16
12
3
12
4
13
tij
j
i
Tpi Tpj
Tpi = min {Tpj tij}
Tp7 = Tw7 = 16
Tp6 = min {16-2} = 14 j " {7}
Tp5 = min {16-7} = 9 j " {7}
Tp4 = min {16-3} = 13 j " {7}
Tp3 = min {9-0, 14-2} = 9 j " {5, 6}
Tp2 = min {9-2} = 7 j " {5}
Tp1 = Tw1 = 0
Paweł Gomoliński, Podstawy logistyki 3-8 16-02-2010
Ścieżka krytyczna
Definicje
" Luz zdarzenia zapas czasu pomiędzy najwcześniejszym i
najpózniejszym terminem jego wystąpienia.
Li = Tpi Twi
" Zdarzenie krytyczne zdarzenie, dla którego luz jest równy
zeru, czyli: Tpi = Twi
Przykład:
2
5 9
2
5
7 9
5
7
9 2
0 9 11
1 6
2
3
0 9 14
16
7
16
12
3
12
4
13
Zdarzenia krytyczne: 3, 5
Paweł Gomoliński, Podstawy logistyki 3-9 16-02-2010
" Zapas całkowity czasu dopuszczalne opóznienie
rozpoczęcia czynności bez zmiany najpózniejszego
terminu wystąpienia zdarzenia j, tzn. bez naruszenia Tpj.
Zcij = Tpj Twi tij
" Zapas swobodny czasu dopuszczalne opóznienie
rozpoczęcia czynności bez zmiany najwcześniejszego
terminu wystąpienia zdarzenia j, tzn. bez naruszenia Twj.
Zsij = Twj Twi tij
" Zapas niezależny czasu dopuszczalne opóznienie
czynności w przypadku, gdy zdarzenie i zaistniałoby w
terminie najpózniejszym, a zdarzenie j powinno rozpocząć się
w terminie najwcześniejszym.
(Inaczej: o ile można wydłużyć czynność , jeśli nawet
wydłuży się do maksimum czynności poprzedzające.)
Znij = Twj Tpi tij
Paweł Gomoliński, Podstawy logistyki 3-10 16-02-2010
Ścieżka krytyczna jest to droga łącząca zdarzenie
początkowe ze zdarzeniem końcowym, dla której
sumaryczny czas realizacji jest najdłuższy.
W danej sieci może istnieć jedna lub więcej ścieżek
krytycznych.
Czynności leżące na ścieżce krytycznej są czynnościami
krytycznymi.
Czynności krytyczne wyznaczają najkrótszy możliwy cykl
realizacji przedsięwzięcia, tzn. nie można go zakończyć
wcześniej, niż w czasie:
= Twn = Tpn
Zdarzenia leżące na ścieżce krytycznej są zdarzeniami
krytycznymi. Jednak ciąg zdarzeń krytycznych nie wyznacza
jednoznacznie ścieżki krytycznej (zdarzenia te mogą również
występować poza ścieżką krytyczną).
Paweł Gomoliński, Podstawy logistyki 3-11 16-02-2010
Twierdzenie
Warunkiem koniecznym i dostatecznym na to, aby czynność
była czynnością krytyczną, jest zerowa wartość zapasu
całkowitego Zcij.
Dowód:
Jeżeli jest czynnością krytyczną i Zcij > 0, tzn.:
Tpj Twi tij > 0 [1]
Natomiast z założenia, że jest czynnością krytyczną
wynika, że zdarzenia i oraz j są krytyczne, czyli:
Tpj = Twj
Wstawiając tę równość do [1], otrzymujemy:
Twj Twi tij > 0
czyli
Twj > (Twi + tij)
co pozostaje w sprzeczności z definicją Twj:
Twj = max {Twi + tij}
c.b.d.o.
Paweł Gomoliński, Podstawy logistyki 3-12 16-02-2010
Przykłady wyznaczania ścieżki krytycznej
2
5 9
2 5
7 9
5
7
9 2
0 9 11
1 3 6
2
0 9 14
16
7
16
12
3
12
4
13
Twi tij, Zcij Twj
i j
Tpi Tpj
Zcij = Tpj Twi tij
Paweł Gomoliński, Podstawy logistyki 3-13 16-02-2010
2,2
5 9
2 5
7 9
5,2
7,0
9,0 2,3
0 9 11
1 3 6
2,3
0 9 14
16
7
16
12,1
3,1
12
4
13
Zc12 = Tp2 Tw1 t12 = 7 0 5 = 2
Zc13 = Tp3 Tw1 t13 = 9 0 9 = 0
Zc14 = Tp4 Tw1 t14 = 13 0 12 = 1
Zc25 = Tp5 Tw2 t25 = 9 5 2 = 2
Zc36 = Tp6 Tw3 t36 = 14 9 2 = 3
Zc47 = Tp7 Tw4 t47 = 16 12 3 = 1
Zc57 = Tp7 Tw5 t57 = 16 9 7 = 0
Zc67 = Tp7 Tw6 t67 = 16 11 2 = 3
Paweł Gomoliński, Podstawy logistyki 3-14 16-02-2010
4
2 5
4 3
8
2
7
1 4
5
4
5
3 6
5
2 5
3
3
8
7
1 3
4
2
5
3
4 6
Paweł Gomoliński, Podstawy logistyki 3-15 16-02-2010
4,7
8
2 5 12
8 19
4,0 3,7
8,0
2,10
0
7 22
1 4 12
22
0 12
5,0
4,13
5,0
4
3 17 6 17
17
5,1
3 8
2 5
4 9
3,3
3,1
8,0
0 6
7 14
1 3
14
0 6
4,0
2,0
5,1
3,4
2 8
4 6
2 9
Paweł Gomoliński, Podstawy logistyki 3-16 16-02-2010
Harmonogram realizacji przedsięwzięcia
Znajomość najwcześniejszych i najpózniejszych terminów
wystąpienia zdarzeń jest niezbędna w celu wyznaczenia
ścieżki krytycznej.
Natomiast z punktu widzenia planowania harmonogramu
przedsięwzięcia istotna jest również znajomość odpowiednich
terminów odnoszących się do czynności:
Pwij najwcześniejszy możliwy termin rozpoczęcia czynności
,
Ppij najpózniejszy dopuszczalny termin rozpoczęcia
czynności ,
Kwij najwcześniejszy możliwy termin zakończenia czynności
,
Kpij najpózniejszy dopuszczalny termin zakończenia
czynności .
Paweł Gomoliński, Podstawy logistyki 4-1 16-02-2010
Terminy rozpoczęcia czynności
Najwcześniejszy Najpózniejszy
Pwij = Twi Ppij = Tpj - tij
Terminy zakończenia czynności
Najwcześniejszy Najpózniejszy
Kwij = Twi + tij Kpij = Tpj
Twi tij Twj
i j
Tpi Tpj
Pwij = Twi Kwij = Twi + tij
tij
tij
Ppij = Tpj - tij Kpij = Tpj
Zcij
Paweł Gomoliński, Podstawy logistyki 4-2 16-02-2010
Parametry czasowe realizacji przedsięwzięcia
4,1
2 7
3 5
3 7
2,3 9,0
2,1
7,2
0 7
7 16
1 4
16
0 7
3,0
4,0
5,3
5,3
3 8
2 6 11
3
Twi Tpj - tij Twi+tij Tpj
Czynność tij Pwij Ppij Kwij Kpij Zcij Zsij Znij
1, 2 3 0 0 3 3 0 0 0
1, 3 2 0 1 2 3 1 0 0
2, 4 4 3 3 7 7 0 0 0
2, 6 5 3 6 8 11 3 0 0
3, 4 2 2 5 4 7 3 3 2
3, 5 4 2 3 6 7 1 1 0
4, 5 0
4, 7 7 7 9 14 16 2 2 2
5, 6 0
5, 7 9 7 7 16 16 0 0 0
6, 7 5 8 11 13 16 3 3 0
Paweł Gomoliński, Podstawy logistyki 4-3 16-02-2010
Harmonogram czynności
[jednostki czasu]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
tij
1, 2 3 - - - - - - - - -
1, 3 2 - - - - - -
2, 4 4 - - - - - - - - - - - -
2, 6 5 - - - - - - - - - - - - - - -
3, 4 2 - - - - - -
3, 5 4 - - - - - - - - - - - -
4, 5 0
4, 7 7 - - - - - - - - - - - - - - - - - - - - -
5, 6 0
5, 7 9 - - - - - - - - - - - - - - - - - - - - - - - - - - -
6, 7 5 - - - - - - - - - - - - - - -
- - - - - najwcześniejsze terminy rozpoczęcia i zakończenia
najpózniejsze terminy rozpoczęcia i zakończenia
Paweł Gomoliński, Podstawy logistyki 4-4 16-02-2010
Optymalizacja harmonogramu czynności
4,1
2 7
3 5
3 7
2,3 9,0
2,1
7,2
0 7
7 16
1 4
16
0 7
3,0
4,0
5,3
5,3
3 8
2 6 11
3
Skrócenie <5, 7> kosztem
<6, 7>
4,1
2 7
3 5
3 7
2,3 7,0
2,1
7,0
0 7
7 14
1 4
14
0 7
3,0
4,0
6,0
5,0
3 8
2 6
3 8
Pojawiają się nowe czynności krytyczne i pozostają jeszcze
rezerwy czasowe dla czynności <1, 3>, <3, 4> i <3, 5>.
Paweł Gomoliński, Podstawy logistyki 4-5 16-02-2010
4,1
2 7
3 5
3 7
2,3 9,0
2,1
7,2
0 7
7 16
1 4
16
0 7
3,0
4,0
5,3
5,3
3 8
2 6 11
3
4,0
2 6
3 5
2 6
4,0 (+2) 7,0 (-2)
2,0
7,0
0 6
7 13
1 4
13
0 6
2,0 (-1)
4,0
6,0 (+1)
5,0
2 7
2 6
2 7
Nie ma już dalszych możliwości optymalizacji czasowej
Paweł Gomoliński, Podstawy logistyki 4-6 16-02-2010
Optymalizacja kosztów realizacji przedsięwzięcia
metoda CPM-MCX
Kryteria optymalizacji harmonogramu przedsięwzięcia:
" Czas realizacji (metoda CPM ścieżka krytyczna)
" Analiza czasowo-kosztowa (metoda CPM-MCX ścieżka
krytyczna z minimalizacją nakładów finansowych)
Analiza czasowo-kosztowa harmonogramu realizacji
przedsięwzięcia
Na całkowity koszt realizacji przedsięwzięcia składają się dwa
rodzaje kosztów, powiązane z czasem:
" Koszty bezpośrednie
" Koszty pośrednie
Paweł Gomoliński, Podstawy logistyki 4-7 16-02-2010
Koszty bezpośrednie dotyczą każdej czynności oddzielnie
(koszty robocizny, materiałów itp.):
KB = Ł Kij
gdzie Kij koszt bezpośredni czynności .
Koszty pośrednie dotyczą całości przedsięwzięcia
(koszty administracyjne, zamrożenia kapitału itp.):
KP = ą T = ą Twn
gdzie:
ą koszt pośredni na jednostkę czasu,
T czas realizacji przedsięwzięcia (dla którego zdarzenie n jest
końcowe).
4,1
2 7
3 5
3 7
2,3 9,0
2,1
Twn
7,2
0 7
7 16
1 4
16
0 7
3,0
4,0
5,3
5,3
3 8
2 6 11
3
Paweł Gomoliński, Podstawy logistyki 4-8 16-02-2010
Koszty bezpośrednie KB związane są zależnością odwrotną z
czasem realizacji poszczególnych czynności. Angażując
dodatkowe środki produkcji, maszyny, siły robocze itd., można
skracać czas tij, ale powoduje to przyrost kosztu KB:
Kij
tij
Koszt pośredni KP całości przedsięwzięcia jest wprost
proporcjonalny do czasu jego realizacji (T):
Kp
T
Zatem skracanie czasu realizacji przedsięwzięcia powoduje:
" wzrost kosztów bezpośrednich KB
" spadek kosztów pośrednich KP
Paweł Gomoliński, Podstawy logistyki 4-9 16-02-2010
Należy tak dobierać czasy tij, aby łączne koszty realizacji
przedsięwzięcia były jak najniższe.
K = KB + KP = min
Koszty
K
KP
KB
Czas realizacji
opt
przedsięwzięcia
Dla kosztów bezpośrednich ścisła zależność pomiędzy tij i Kij
jest nieznana.
Z racji jednorazowości rozpatrywanego przedsięwzięcia (proces
nieregularny), nie istnieje też możliwość empirycznego
określenia tej zależności.
Można jednak aproksymować przebieg krzywej zależności
kosztów bezpośrednich od czasu za pomocą interpolacji
liniowej.
Paweł Gomoliński, Podstawy logistyki 4-10 16-02-2010
Warunkiem jest znajomość dwóch punktów tej krzywej:
normalnego N i granicznego G, które dla specjalisty-technologa
nie są trudne do wyznaczenia.
Kij
Punkt graniczny
G
Kij
Punkt normalny
N
Kij
G N
tij tij
tij
N N
Kij
(tij , ) punkt normalny;
N
Kij
minimalny koszt bezpośredni realizacji czynności ,
zwany kosztem normalnym;
(np. zaangażowana jedna maszyna/operator/linia itp.)
N
tij
czas normalny realizacji dla czynności , będący
N
Kij
najkrótszym możliwym przy koszcie ;
G G
Kij
(tij , ) punkt graniczny;
G
tij
czas graniczny realizacji czynności , będący
najkrótszym możliwym do uzyskania (ze względów
technologicznych) bez względu na koszty;
(np. zaangażowane wszystkie maszyny/operatorzy/linie itp.)
G
Kij
koszt bezpośredni realizacji czynności w czasie
granicznym.
Paweł Gomoliński, Podstawy logistyki 4-11 16-02-2010
Rzeczywisty czas realizacji czynności zawiera się w
przedziale:
G N
tij tij
d" tij d"
Znając współrzędne punktów N i G można aproksymować
przebieg zależności kosztów bezpośrednich od czasu:
Kij
G
Kij
N
Kij
G N
tij tij
tij
G N
Kij Kij
-
aij =
N
tij G
- tij
gdzie aij wyraża współczynnik przyrostu kosztów bezpośrednich
czynności przy skróceniu czasu realizacji czynności o
jednostkę.
Paweł Gomoliński, Podstawy logistyki 4-12 16-02-2010
G N
Kij
Kij Kij
-
G aij =
Kij
N G
tij tij
-
Kij
N
Kij
G N
tij tij tij
tij
Stąd koszt bezpośredni czynności :
N N N N
Kij Kij tij
Kij = + aij (tij - tij) = + aij - aij tij
zaś całkowity koszt bezpośredni przedsięwzięcia:
N N N N
Kij tij Kij
KB = Ł Kij = Ł [ + aij - aij tij] = Ł [ + aij tij ] - Ł aij tij
K
KB = - Ł aij tij
K
gdzie jest wielkością stałą, niezależną od zmiennych tij.
Paweł Gomoliński, Podstawy logistyki 4-13 16-02-2010
Minimum kosztów łącznych K = KP + KB:
K
(min) K = (min) ą T + - Ł aij tij
K
jest wielkością stałą, stąd:
(min) K = (min) ą T - Ł aijtij
dla warunków ograniczających:
G N
tij tij
d" tij d" (maks. i min. możliwy czas realizacji czynności)
tij d" Tpj - Twi (maksymalny czas, który nie zwiększy T)
Jest to model liniowy, w którym niewiadome są tij, Twi, Tpi oraz
T.
W praktyce zadanie to rozwiązuje się za pomocą postępowania
heurystycznego, metodą MCX (Minimum Cost Expenditing).
Jest to modyfikacja metody CPM, dlatego najczęściej określana
jest jako CPM-MCX.
Paweł Gomoliński, Podstawy logistyki 4-14 16-02-2010
Algorytm rozwiązania
Dane:
N G
G
t t Kij
Dla danej sieci czynności znane są parametry: , , ,
ij ij
N
Kij , a stąd również aij.
Znany jest również współczynnik ą
ą kosztów pośrednich na
ą
ą
jednostkę czasu.
Rozwiązanie:
Rozwiązanie polega na iteracyjnej modyfikacji harmonogramu
przedsięwzięcia. W każdej iteracji następuje określone
skrócenie jego cyklu.
Paweł Gomoliński, Podstawy logistyki 4-15 16-02-2010
Krok 1
N
t
Wyznaczamy T = Twn, przyjmując tij = .
ij
N
Kij
Koszt całkowity wynosi: K = Ł + ą T
Krok 2
Skrócenie czasu realizacji przedsięwzięcia jest możliwe przez
skrócenie czasów realizacji czynności krytycznych tkl.
Jednak jest to opłacalne jedynie wówczas, gdy:
akl < ą
ą
ą
ą
Tylko wtedy spadek kosztów pośrednich jest większy od
przyrostu kosztów bezpośrednich:
K' = K + "KB - "KP
K' = K + A - ą
K' = K - "K
gdzie:
= tkl - t'kl (skrócenie czasu realizacji czynności krytycznej )
A = Ł akl (suma współczynników aij dla czynności krytycznych, które
uległy skróceniu o )
Warunek opłacalności: A < ą ("KB < "KP)
"K = "KP - "KB
Paweł Gomoliński, Podstawy logistyki 4-16 16-02-2010
Ograniczenia:
Czynność można skrócić tylko o wartość , spełniającą
następujący warunek:
G
. = min {tkl t kl; Zcil; Zckj}
i " -1 {k}
j " -1 {l}
tGij - tij, Zcij
j
i
aij
8
Ścieżka krytyczna (k, l): <6, 7>
4
9
1-4, 3
l
Skrócenie:
i
4
= min {4; 3; 4} = 3
1-5, 4
6
15
5 11
7
2
15
t67 - tG67; Zc47; Zc57
1-5, 0
3
k j
6 10
10
Tw
8
8 Tp
8
8
2 ścieżki krytyczne:
4
9
1-4, 0
<4, 7> i <6, 7>
4
1-5, 1
6
12
5 11
7
Obie trzeba skracać równolegle,
2
12
1-2, 0
o tę samą wielkość:
3
= min {3; 1; 1} = 1
6 10
10
t47 - tG47; t67 - tG67; Zc57
Paweł Gomoliński, Podstawy logistyki 4-17 16-02-2010
Krok 3
Koniec iteracji, gdy:
a) "KB > "KP
Wartość współczynnika A dla wszystkich potencjalnie
możliwych do skrócenia czynności krytycznych (lub ich grup
gdy wymagają jednoczesnego skracania) jest większa od
ą.
ą
ą
ą
W takiej sytuacji skracanie T przestaje być opłacalne,
ponieważ wzrost kosztów bezpośrednich nie jest
rekompensowany spadkiem kosztów pośrednich.
b) Osiągnięto czas graniczny dla czynności na ścieżce
krytycznej (tzn. dalsze skracanie czasu nie jest możliwe ze
względów technologicznych).
Paweł Gomoliński, Podstawy logistyki 4-18 16-02-2010
Przykład
Kp
KP1
Dane:
"KP
T = Tw7 = 16
ą =
"T
ą = 5
KP2
T2 T1
T
Graf czynności:
2 1-4,1 7
2 5
3 5 7
4-9,0
1-2,1
3
3
1-2,3
2
3-7,2
0 7
7 16
1 4
4 16
0 7
1-4,0
6
1-3,0
2-5,3
4
3
3 2-5,3 8
3 6 11
3 5
tGij - tij, Zcij
j
i
aij
Paweł Gomoliński, Podstawy logistyki 4-19 16-02-2010
1. Obliczamy składowe koszty bezpośrednie i koszt
całkowity.
tGij - tij, Zcij
j
i
(KNij) aij
2 1-4,1 7
2 5
3 (20) 5 7
4-9,0
1-2,1
(27) 3
(6) 3
1-2,3
(4) 2
3-7,2
0 7
7 16
1 4
(28) 4 16
0 7
1-4,0
(24) 6
1-3,0
2-5,3
(12) 4
(15) 3
3 2-5,3 8
3 6 11
3 (25) 5
Ł KNij
ą T
K = Ł aij tij + ą T
K = 3 2 + 4 3 + 2 2 + 6 4 + 5 4 + 5 5 + 4 7 + 3 9 + 3 5 + 5 16
<1, 2> <1, 3> <2, 4> <3, 4> <2, 5> <3, 6> <4, 7> <5, 7> <6, 7>
K = 161 + 80 = 241
Paweł Gomoliński, Podstawy logistyki 4-20 16-02-2010
2. Skracamy czynność <5, 7> na ścieżce krytycznej
a57 = 3 < ą (= 5) (kryterium zysku bezwzględnego)
oraz
a57 = min {akl} (kryterium minimalnego kosztu)
= min {tkl - tGkl; Zcil; Zckj}
9 4
= min {t57 - tG57; Zc47; Zc67} = min {5; 2; 3} = 2
"K = (ą - a57) = 2 (5 - 3) = 4
K' = K - "K = 241 - 4 = 237
2 1-4,1 7
2 5
3 5 7
4-7,0
1-2,1
3
3
1-2,3
2
3-7,0
0 7
7 14
1 4
4 14
0 7
1-4,0
6
T = 14
1-3,0
2-5,1
4
3
3 2-5,1 8
3 6
3 5 9
Pojawiła się nowa ścieżka krytyczna. (1-3-4-7)
Paweł Gomoliński, Podstawy logistyki 4-21 16-02-2010
3. Skracamy czynność <1, 3> na ścieżce krytycznej
a13 = 4 < ą (= 5) (kryterium zysku bezwzględnego)
oraz
a13 = min { a13; a34; a57 + a47} (kryterium minimalnego kosztu)
podwójna ścieżka krytyczna
= min {tkl - tGkl; Zcil; Zckj}
3
1
= min {t13 - tG13; Zc12} = min {2; 1} = 1
"K = (ą - a13) = 5 - 4 = 1
K' = K - "K = 237 - 1 = 236
2 1-4,0 6
2 5
2 5 6
4-7,0
1-2,0
3
3
1-2,2
2
3-7,0
0 6
7 13
1 4
4 13
0 6
1-4,0
6
T = 13
1-2,0
2-5,1
4
3
2 2-5,1 7
3 6
2 5 8
Pojawiła się kolejna ścieżka krytyczna. (1-2-5-7)
Paweł Gomoliński, Podstawy logistyki 4-22 16-02-2010
Pozostały możliwości skrócenia:
1) <1, 2>
2) <2, 5>
3) <3, 4>
4) <5, 7> i <4, 7>
Współczynnik wzrostu kosztów bezpośrednich:
1) a12 = 3
2) a25 = 5
3) a34 = 6
4) a57 + a47 = 7
Opłacalne jest tylko skracanie czynności <1, 2>
(ponieważ ą = 5)
Wielkość skrócenia czasu realizacji <1, 2>:
= min {t12 - tG12; Zc13} = min {1; 0} = 0
Koniec iteracji
Paweł Gomoliński, Podstawy logistyki 4-23 16-02-2010
LINIOWE MODELE DECYZYJNE
Sytuacje decyzyjne ogół czynników, które wyznaczają w
sposób bezpośredni postępowanie decyzyjne podmiotu
podejmującego decyzję ( decydenta ).
Zbiór możliwych
Decydent
decyzji
Sytuacja decyzyjna
Okoliczności Kryteria wyboru
przyczynowe decyzji
sytuacji
Model decyzyjny sformułowanie problemu decyzyjnego,
pozwalające rozwiązać go metodami badań operacyjnych.
Na przykład ustalenie programu produkcyjnego
przedsiębiorstwa musi uwzględniać m.in.:
" popyt,
" dostępność surowców i półfabrykatów,
" moce produkcyjne,
" ograniczenia technologiczne itd., itp.
Paweł Gomoliński, Podstawy logistyki 5-1 16-02-2010
Proces rozwiązywania problemu decyzyjnego
Rozpoznanie sytuacji
decyzyjnej
i wynikającego z niej
problemu decyzyjnego
Budowa modelu
decyzyjnego
Rozwiązanie zadania
decyzyjnego
Ocena poprawności
i realności
uzyskanych
rozwiązań
Ostateczna decyzja
Paweł Gomoliński, Podstawy logistyki 5-2 16-02-2010
1. Rozpoznanie sytuacji decyzyjnej i wynikającego z niej
problemu decyzyjnego
" Rozpoznanie wszystkich uwarunkowań
" Rozpoznanie wszystkich elementów sytuacji decyzyjnej
2. Budowa modelu decyzyjnego
" Matematyczne sformułowanie zadania decyzyjnego
" Model decyzyjny powinien uwzględniać wszystkie istotne
dla podejmowanej decyzji aspekty
3. Rozwiązanie zadania decyzyjnego
" Metody badań operacyjnych i programowania
matematycznego:
- Programowanie liniowe
- Metoda simpleks
- Modelowanie sieciowe (CPM, CPM-MCX) itd.
4 Ocena poprawności i realności uzyskanych rozwiązań
" Analiza wpływu aspektów nie uwzględnionych w modelu
decyzyjnym
" Ewentualna korekta modelu decyzyjnego
5 Ostateczna decyzja
" Uwzględnienie dodatkowych uwarunkowań
Paweł Gomoliński, Podstawy logistyki 5-3 16-02-2010
Terminologia i definicje
Model matematyczny idealizowane odtworzenie
rzeczywistości
Optimum najlepsze możliwe rozwiązanie problemu
Suboptimum poszukuje się, gdy:
- problem jest zbyt złożony i można rozwiązać jedynie zadanie
częściowe,
- występuje jednocześnie wiele optimów,
- nie ma ścisłych metod rozwiązania problemu i przyjmuje się
rozwiązanie metodami przybliżonymi.
Rozwój modelu model prosty udoskonalanie
Analizy postoptymalizacyjne analiza czułości
Poszukiwanie parametrów krytycznych (w największym stopniu
decydujących o wyniku), które muszą być przygotowane
najdokładniej.
Paweł Gomoliński, Podstawy logistyki 5-4 16-02-2010
Budowa modelu decyzyjnego
Model decyzyjny zawiera tzw. parametry modelu. Są to
wielkości, na które decydent nie ma wpływu, określające
uwarunkowania zewnętrzne, np. zysk jednostkowy z produkcji
określonego wyrobu.
Postać sformułowanego modelu determinuje możliwości
efektywnego rozwiązania zadania optymalizacyjnego. Należy
dobierać taką postać modelu, która pozwoli uzyskać
rozwiązanie przy rozsądnym nakładzie czasu i kosztów.
MOTTO:
Nie należy poszukiwać rozwiązania optymalnego za wszelką
cenę lecz rozwiązania zadowalającego przy optymalnym
sposobie rozwiązania.
(Herbert Simon)
Nie ma dotychczas teorii, które pozwoliłyby w jednoznaczny
sposób determinować sposób budowania modelu decyzyjnego.
Opracowano jedynie szereg ogólnych reguł postępowania.
Paweł Gomoliński, Podstawy logistyki 5-5 16-02-2010
Postać matematyczna modelu decyzyjnego:
Z = f(x1, x2, ..., xn)
gdzie:
x1, x2, ... , xn zmienne decyzyjne, określające alternatywne
sposoby działania, zależne od decyzji
decydenta (np. wielkości produkcji
poszczególnych wyrobów);
f funkcja celu (odwzorowanie zależności
pomiędzy zmiennymi decyzyjnymi, a miarą
oceny Z);
Z miara oceny podjętej decyzji.
Na ogół podejmowanie decyzji przebiega w warunkach
pewnych ograniczeń, określających zbiór dopuszczalnych
rozwiązań.
gi(x1, x2, ..., xn) e" 0 (i = 1, 2, ...m)
Paweł Gomoliński, Podstawy logistyki 5-6 16-02-2010
Poszukiwanie rozwiązania optymalnego polega na
maksymalizacji bądz minimalizacji funkcji celu:
(max) Z = f(x1, x2, ..., xn)
lub
(min) Z = f(x1, x2, ..., xn)
przy warunkach ograniczających:
gi(x1, x2, ..., xn) e" 0 (i = 1, 2, ...m)
Model wielokryterialny zadanie optymalizacyjne z wieloma
funkcjami celu (np. gdy jest kilka różnych miar oceny decyzji)
Paweł Gomoliński, Podstawy logistyki 5-7 16-02-2010
W przypadku liniowego modelu decyzyjnego, funkcja celu i
ograniczenia mają postać liniową.
Zatem matematyczny zapis liniowego modelu decyzyjnego ma
postać:
(max) Z = Ł cj xj
lub
(min) Z = Ł cj xj
przy warunkach ograniczających:
Ł aij xj e" bi (i = 1, 2, ...m)
aij, bi, cj parametry.
Przykład modelu liniowego:
Z = 3x1 + 2x2 + 5x3
gdzie:
3, 2, 5 parametry
x1, x2, x3 zmienne decyzyjne
Ograniczenia:
3x1 + 2x1x2 + 5x3 e" 12
Paweł Gomoliński, Podstawy logistyki 5-8 16-02-2010
Liniowe modele decyzyjne rozwiązuje się za pomocą metod
tzw. programowania liniowego.
Zastosowanie tych metod do procesów wymaga spełnienia
dwóch podstawowych aksjomatów liniowości modelu
decyzyjnego:
1. Aksjomat podzielności Wielkość nakładu i
odpowiadający mu efekt są wzajemnie proporcjonalne.
Innymi słowy x-krotne zwiększenie nakładu powoduje
x-krotne zwiększenie efektów (x może mieć również
wartość ułamkową).
2. Aksjomat addytywności Ogólna wielkość nakładu
(wyniku) dla całego przedsięwzięcia jest sumą nakładów
(wyników) dla poszczególnych procesów składowych.
Spełnienie tych aksjomatów warunkuje możliwość
sformułowania modelu decyzyjnego w postaci zależności
liniowych.
Paweł Gomoliński, Podstawy logistyki 5-9 16-02-2010
PROGRAMOWANIE LINIOWE
Metody programowania liniowego służą do rozwiązywania
liniowych zagadnień optymalizacyjnych.
Programowanie liniowe = planowanie działalności
Zastosowania
Problem alokacji ograniczonych zasobów na konkurujące
działania.
Poszukuje się max (Z), np.:
" Ustalenie odpowiedniego programu produkcji
" Problemy transportu
" Podział budżetu
" ...
Problem substytucji jednych składników innymi dla
uzyskania określonego efektu. Poszukuje się min (Z), np.:
" Ustalenie odpowiedniego składu benzyny
" Ustalenie diety
" ...
Paweł Gomoliński, Podstawy logistyki 6-1 16-02-2010
Przykład wprowadzający
Firma produkująca drzwi i okna dysponuje 3 zakładami,
w których realizowane są następujące zadania:
Zakład nr 1: Produkcja ram aluminiowych i okuć.
Zakład nr 2: Produkcja ram drewnianych.
Zakład nr 3: Produkcja szyb + montaż.
Dział marketingu żąda wprowadzenia 2 nowych produktów:
1. Drzwi aluminiowo-szklanych
2. Dużych okien drewnianych
Zapotrzebowanie rynku jest duże i najlepiej by było
doprowadzić do jak największej produkcji obu tych wyrobów (z
zachowaniem jednak określonego poziomu produkcji wyrobów
dotychczasowych).
Istotnym ograniczeniem są możliwości montażu gotowych
wyrobów (szklenie + montaż okuć), ponieważ jest tylko jedna
linia montażowa w zakładzie nr 3.
Z punktu widzenia rentowności przedsięwzięcia konieczne
zatem jest ustalenie, jaka wielkość produkcji obu nowych
wyrobów będzie najkorzystniejsza.
Paweł Gomoliński, Podstawy logistyki 6-2 16-02-2010
Sformułowanie zadania
W pierwszej kolejności niezbędne jest zebranie następujących
danych:
1. Zasoby produkcyjne każdej fabryki, które mogą zostać
przeznaczone dla nowych wyrobów.
Zasoby te wyrażone są np. udziałami procentowymi w
stosunku do pełnej zdolności produkcyjnej zakładu.
2. Jednostkowe zapotrzebowanie zasobów produkcyjnych dla
nowych wyrobów w odniesieniu do każdego zakładu.
3. Zysk jednostkowy dla nowych wyrobów.
Paweł Gomoliński, Podstawy logistyki 6-3 16-02-2010
Produkt Możliwości
Zakład produkcyjne
1 2
(zasoby)
1 1 0 4
2 0 2 12
3 3 2 18
Zysk
3 5
jednostkowy
Jest to klasyczne zagadnienie produkcji mieszanej, w którym
należy ustalić optymalny program produkcji.
Matematyczne sformułowanie problemu
" Funkcja celu (max zysk)
Z = 3x1 + 5x2
gdzie:
x1, x2 liczba jednostek produktu 1 i produktu 2 wytwarzanych
w jednostce czasu.
Z wielkość zysku na jednostkę czasu
Paweł Gomoliński, Podstawy logistyki 6-4 16-02-2010
" Ograniczenia
x1 d" 4 (wytworzenie jednostki produktu 1 na
jednostkę czasu angażuje 1%, a
dostępnych jest 4% mocy produkcyjnych
zakładu 1)
2x2 d" 12 (wytworzenie jednostki produktu 2 na
jednostkę czasu angażuje 2%, a
dostępnych jest 12% mocy produkcyjnych
zakładu 2)
3x1 + 2x2 d" 18 (wytworzenie jednostki produktu 1 na
jednostkę czasu angażuje 3%, wytworzenie
jednostki produktu 2 na jednostkę czasu
angażuje 2%, a dostępnych jest 18% mocy
produkcyjnych zakładu 3)
oraz
x1 e" 0, x2 e" 0 (wielkość produkcji nie może być ujemna)
Paweł Gomoliński, Podstawy logistyki 6-5 16-02-2010
Zatem poszukujemy:
(max) Z = 3x1 + 5x2
przy ograniczeniach:
x1 d" 4
2x2 d" 12
3x1 + 2x2 d" 18
x1 e" 0, x2 e" 0
Ponieważ są tylko dwie zmienne decyzyjne, można posłużyć
się metodami wykreślnymi.
Paweł Gomoliński, Podstawy logistyki 6-6 16-02-2010
Krok 1: Określenie obszaru dopuszczalnego.
x2
10
9
8
7
6
5
x1 e" 0
x2 e" 0
4
x1 d" 4
3
2
1
0 3 4 5 6 7 8 9 10
1 2
x1
x2
10
9
3x1 + 2x2 = 18
8 x1 = 4
7
6 2x2 = 12
5
x1 e" 0
4
x2 e" 0
x1 d" 4
3
2x2 d" 12
3x1 + 2x2 d" 18
2
1
0 1 2 3 4 5 6 7 8 9 10
x1
Paweł Gomoliński, Podstawy logistyki 6-7 16-02-2010
Krok 2: Znalezienie punktu obszaru dopuszczalnego, w
którym funkcja celu osiąga wartość maksymalną
x2
10
9
8
7
6
5
4
3
Z = 10 = 3x1 + 5x2
2
1
0 1 2 3 4 5 6 7 8 9 10 x1
x2
10
9
8
7
6
5
Z = 20 = 3x1 + 5x2
4
3
Z = 10 = 3x1 + 5x2
2
1
0 1 2 3 4 5 6 7 8 9 10 x1
Paweł Gomoliński, Podstawy logistyki 6-8 16-02-2010
x2
10
9
8
Z = 36 = 3x1 + 5x2
7
(2; 6)
6
5
Z = 20 = 3x1 + 5x2
4
3
Z = 10 = 3x1 + 5x2
2
1
0 1 2 3 4 5 6 7 8 9 10 x1
Zmax = 36 dla x1 = 2; x2 = 6
Wnioski:
Maksymalny zysk, w wysokości 36 zł na jednostkę czasu,
będzie generowany przy wytwarzaniu następujących ilości
produktów:
" produkt 1 2 sztuki na jednostkę czasu
" produkt 2 6 sztuk na jednostkę czasu
Paweł Gomoliński, Podstawy logistyki 6-9 16-02-2010
Przykład 2
Firma przewozowa dysponuje samochodami ciężarowymi z
przyczepami, które mają następujące parametry:
Środek Aadowność [t] Pojemność skrzyni
transportu ładunkowej [m3]
Samochód 12 50
Przyczepa 10 40
Do przewiezienia są następujące towary:
Objętość Zysk
Towar jednostkowa jednostkowy
[m3/t] [zł/t]
1 2 50
2 6 80
Należy ustalić najbardziej rentowny sposób załadunku środka
transportu w postaci samochodu z przyczepą (traktowanych
łącznie). Innymi słowy: w jakich proporcjach należy zabierać
oba rodzaje towarów, aby zysk z transportu był maksymalny?
Paweł Gomoliński, Podstawy logistyki 6-10 16-02-2010
Rozwiązanie:
xi masa towaru i załadowanego na samochód z przyczepą
" Funkcja celu (max zysk)
Z = 50x1 + 80x2
" Ograniczenia
x1 + x2 d" 22 (tony)
2x1 + 6x2 d" 90 (m3)
x1 e" 0, x2 e" 0
x2
50
45
40
35
30
25
20
15
10
5
0 5 10 15 20 25 30 35 40 45 50
x1
x1 + x2 = 22 2x1 + 6x2 = 90
Paweł Gomoliński, Podstawy logistyki 6-11 16-02-2010
x2
50
45
40
35
30
25
Z=1445=50x1+80x2
20
15
10.5; 11.5
Z=500=50x1+80x2
10
5
0 5 10 15 20 25 30 35 40 45 50
x1
x1 + x2 = 22 2x1 + 6x2 = 90
Zmax = 1445 dla x1 = 10.5; x2 = 11.5
Maksymalny zysk, w wysokości 1445 zł, będzie generowany
przy następującym sposobie załadunku:
" Towar 1 10.5 t
" Towar 2 11.5 t
Paweł Gomoliński, Podstawy logistyki 6-12 16-02-2010
Przykłady graficznych rozwiązań zadań
programowania liniowego
Przykład 1
Zadanie:
(max) Z = 0.25 x1 + x2
przy warunkach ograniczających:
-x1 + x2 d" 2
0.75 x1 + x2 d" 3
x1, x2 e" 0
-x1+x2=2
x2
0.75x1+x2=3
0.75x1 + x2 = 3
-x1 + x2 = 2
Ó!
4 18
x1 = ; x2 =
7 7
-2 -1 1 2 3 4 5 x1
-x1 + x2 = 2:
0.75x1 + x2 = 3:
x1 = 0 ! x2 = 2
x1 = 0 ! x2 = 3
x2 = 0 ! x1 = -2
x2 = 0 ! x1 = 4
Paweł Gomoliński, Podstawy logistyki 7-1 16-02-2010
x2
0.75x1+x2=3
-x1+x2=2
19
4 18
Z =
optimum: x1 = ; x2 =
7
7 7
Z = 2
Z = 1
warstwice
-2 -1 1 2 3 4 5 x1
funkcji celu
Dokładnie 1 rozwiązanie
4
Zmax = 19 dla x1 = ; x2 = 18
7 7
7
Paweł Gomoliński, Podstawy logistyki 7-2 16-02-2010
Przykład 2
Zadanie:
(max) Z = x1 + x2
przy warunkach ograniczających:
x1 + x2 d" 4
-x1 + x2 d" 2
x1, x2 e" 0
x1+x2=4
x2
-x1+x2=2
-2 -1 1 2 3 4 5 x1
-x1 + x2 = 2:
x1 + x2 = 4
x1 + x2 = 4:
-x1 + x2 = 2
x1 = 0 ! x2 = 2
x1 = 0 ! x2 = 4
x2 = 0 ! x1 = -2 Ó!
x2 = 0 ! x1 = 4
x1 = 1; x2 = 3
Paweł Gomoliński, Podstawy logistyki 7-3 16-02-2010
x1+x2=4
x2
-x1+x2=2
Z = 3
Z = 2
(1; 3)
zbiór rozwiązań optymalnych
Z = 0
(4; 0)
-2 -1 1 2 3 4 5 x1
warstwice
funkcji celu
Nieskończenie wiele rozwiązań
Zmax = 4 dla każdego punktu odcinka o końcach w punktach
(1; 3) i (4; 0)
Paweł Gomoliński, Podstawy logistyki 7-4 16-02-2010
Przykład 3
Zadanie:
(max) Z = 2x1 + x2
przy warunkach ograniczających:
3
x1 + x2 e" 3
5
1
- x1 + x2 e" 1
2
x1, x2 e" 0
x2
3
x1+x2=3
5
1
- x1+x2=1
2
-2 -1 1 2 3 4 5 x1
3
x1 + x2 = 3
5
1
- x1 + x2 = 1
3
1
2
x1 + x2 = 3:
- x1 + x2 = 1:
5
2
Ó!
x1 = 0 ! x2 = 3
x1 = 0 ! x2 = 1
20 21
x1 = ; x2 =
x2 = 0 ! x1 = 5
x2 = 0 ! x1 = -2
11 11
Paweł Gomoliński, Podstawy logistyki 7-5 16-02-2010
x2
1
- x1+x2=1
3
2
x1+x2=3
5
-2 -1 1 2 3 4 5 x1
Z=12
Z=6
Z=2
warstwice funkcji celu
Zero rozwiązań
Paweł Gomoliński, Podstawy logistyki 7-6 16-02-2010
Zadanie 1
(max) Z = 3x1 + 6x2
ograniczenia: 3x1 + 6x2 d" 18
5x1 + 2x2 d" 10
x1, x2 e" 0
(x1 = 1; x2 = 2.5; Zmax = 18)
Zadanie 2
(max) Z = 18x1 + 6x2
ograniczenia: -4x1 + 3x2 d" 6
-x1 + 2x2 d" 12
x1 - x2 e" 6
x1, x2 e" 0
(x1 = 24; x2 = 18; Zmax = 540)
Zadanie 3
(max) Z = 3x1 + 4x2
ograniczenia: 2x1 + 3x2 d" 6
x1 + x2 e" 1
x1, x2 e" 0
(x1 = 3; x2 = 0; Zmax = 9)
Paweł Gomoliński, Podstawy logistyki 7-7 16-02-2010
Ogólne zasady tworzenia modeli zagadnień
decyzyjnych
Przykład wprowadzający Uogólnienie
Możliwości produkcyjne Zasoby
!
3 zakłady produkcyjne m zasobów
!
Wytwarzanie produktów Działanie
!
2 produkty n działań
!
Wielkość jednostkowa produkcji Poziom działania j (xj)
!
produktu j (xj)
Zysk (Z) Miara sprawności
!
działania (Z)
Paweł Gomoliński, Podstawy logistyki 8-1 16-02-2010
Dostępna
Działanie
Nr zasobu wielkość
1 2 . . . n zasobu
1 a11 a12 . . . a1n b1
2 a21 a22 . . . a2n b2
. . .
. . .
. . .
m am1 am2 . . . amn bm
c1 c2 . . . cn
"Z / jedn. działania
x1 x2 . . . xn
Poziom działania
aij, bi, cj parametry modelu
Dla działania j (j = 1, 2, 3,.... , n):
xj zmienne decyzyjne
cj wzrost funkcji celu Z spowodowany jednostkowym
przyrostem xj
Dla zasobu i (i = 1, 2, 3,.... , m):
bi dostępne zasoby
aij wielkość zasobu i spożytkowana na działanie j
(i = 1, 2, 3,.... , m; j = 1, 2, 3,.... , n)
Paweł Gomoliński, Podstawy logistyki 8-2 16-02-2010
Funkcja celu:
(max) Z = c1 x1 + c2 x2 + .... + cn xn
Restrykcje (warunki brzegowe):
a11 x1 + a12 x2 + .... + a1n xn d" b1
a21 x1 + a22 x2 + .... + a2n xn d" b2
a31 x1 + a32 x2 + .... + a3n xn d" b3
.
.
.
am1 x1 + am1 x2 + .... + amn xn d" bm
oraz
x1 e" 0, x2 e" 0, ...., xn e" 0 (warunki nieujemności)
Podstawowe założenia:
" proporcjonalność:
funkcji celu cj xj oraz wyczerpywania zasobu aij xj
(warunek liniowości modelu)
" addytywność:
wzajemna niezależność parametrów aij, cj
" podzielność:
aij dowolne wartości ułamkowe (nie tylko liczby całkowite)
Paweł Gomoliński, Podstawy logistyki 8-3 16-02-2010
Doprowadzanie zadania do postaci kanonicznej
(klasycznej)
Postać kanoniczna zadania programowania liniowego:
(max) Z = Ł cj xj
przy ograniczeniach:
Ł aij xj d" bi
xi e" 0
Twierdzenie
Dla każdej funkcji Z = f(x) spełnione są równości:
min f(x) = -max [-f(x)]
max f(x) = -min [-f(x)]
Zatem:
Dowolne zadanie programowania matematycznego można
przekształcić do zadania równoważnego z przeciwnym
rodzajem ekstremum.
Paweł Gomoliński, Podstawy logistyki 8-4 16-02-2010
Przykład:
f(x)
z0
x0
x
-z0
-f(x)
Funkcja f(x) osiąga minimum w tym samym punkcie x0, w
którym funkcja -f(x) osiąga maksimum.
Paweł Gomoliński, Podstawy logistyki 8-5 16-02-2010
Operacje zmiany postaci zadania programowania
liniowego
I. Zamiana rodzaju ekstremum (zamiana znaku funkcji celu)
min f(x) = -max [-f(x)]
np.:
f(x) = 2x1 - 3x2 ! -f(x) = -2x1 + 3x2
II. Zamiana zmiennych dowolnych co do znaku na zmienne
nieujemne.
Jeżeli zmienna x jest dowolnego znaku, to podstawiając
x = x+ - x- gdzie: x+ = max (0, x),
x- = max (0, -x)
otrzymujemy nieujemne przedstawienie tej zmiennej za
pomocą zmiennych x+ i x- (x+, x- e" 0)
III. Zamiana równości na nierówność:
aijxj = bi
jest równoważne dwóm nierównościom:
aijxj d" bi
-aijxj d" -bi
np.:
2x1 + 3x2 = 5 ! 2x1 + 3x2 d" 5
-2x1 - 3x2 d" -5
Paweł Gomoliński, Podstawy logistyki 8-6 16-02-2010
Przykład
Doprowadzić następujące zadanie do postaci klasycznej:
(min) Z = 2x1 - x2 + 5x3 - 2x4
przy ograniczeniach:
x1 + x2 + 2x3 + 5x4 d" 20
2x1 - x2 - x4 e" 15
3x2 + x3 -2x4 = 14
x1, x3, x4 e" 0
x2 dowolne
1. Zmiana rodzaju ekstremum:
(min) Z = 2x1 - x2 + 5x3 - 2x4
Ó!
(max) -Z = -2x1 + x2 - 5x3 + 2x4
2. Zamiana zmiennej x2 na zmienne nieujemne x2 = x2+ - x2-
np. x1 + x2 + 2x3 + 5x4 d" 20
Ó!
x1 + x2+ - x2- + 2x3 + 5x4 d" 20
-2x1 + x2 - 5x3 + 2x4 (funkcja celu)
Ó!
-2x1 + x2+ - x2- - 5x3 + 2x4
Paweł Gomoliński, Podstawy logistyki 8-7 16-02-2010
3. Zmiana kierunku nierówności:
2x1 - x2 - x4 e" 15
Ó!
-2x1 + x2+ - x2- + x4 d" -15
4. Zamiana równości na nierówność:
3x2 + x3 -2x4 = 14
Ó!
3x2+ - 3x2- + x3 - 2x4 d" 14
-3x2+ + 3x2- - x3 + 2x4 d" -14
Ostateczna postać klasyczna zadania:
(max) -Z = -2x1 + x2+ - x2- - 5x3 + 2x4
przy ograniczeniach:
x1 + x2+ - x2- + 2x3 + 5x4 d" 20
-2x1 + x2+ - x2- + x4 d" -15
3x2+ - 3x2- + x3 - 2x4 d" 14
-3x2+ + 3x2- - x3 + 2x4 d" -14
x1, x2+, x2-, x3, x4 e" 0
Paweł Gomoliński, Podstawy logistyki 8-8 16-02-2010
Przykład
Doprowadzić następujące zadanie do postaci klasycznej:
(min) Z = 2x1 - 3x2 + 4x3
przy ograniczeniach:
3x2 - x3 e" 4
2x1 + 4x2 = 10
x1, x2 e" 0
x3 dowolne
(max) -Z = -2x1 + 3x2 - 4x3+ + 4x3-
-3x2 + x3+ - x3- d" -4
2x1 + 4x2 d" 10
-2x1 - 4x2 d" -10
x1, x2, x3+, x3- e" 0
Paweł Gomoliński, Podstawy logistyki 8-9 16-02-2010
Przykłady tworzenia modeli decyzyjnych
Zagadnienie dystrybucyjne
Wytwórca rozsyła taki sam towar z kilku składnic do kilku
punktów docelowych. Każdy z tych punktów może przyjąć
określoną ilość jednostek poszczególnych towarów, jak również
każda ze składnic może dostarczyć ograniczoną ilość towaru.
Należy sformułować liniowy model decyzyjny, pozwalający
określić sposób dystrybucji poszczególnych towarów dający
maksymalną rentowność (minimalizacja kosztu, długości
całkowitej trasy, czasu przejazdu itp., bądz zagadnienie
odwrotne: maksymalizacja zysku.)
Rozwiązanie z minimalizacją kosztu:
Przyjmujemy następujące oznaczenia:
m ilość składnic;
n ilość punktów docelowych;
ai całkowita ilość towaru w składnicy i ;
bj całkowite zapotrzebowanie towaru w punkcie
docelowym j ;
cij koszt przesłania jednostki towaru ze składnicy i do punktu
docelowego j ;
xij ilość towaru przesyłana ze składnicy i do punktu
docelowego j .
Paweł Gomoliński, Podstawy logistyki 9-1 16-02-2010
Wartości xij są nieznanymi ilościami przewożonych towarów,
które należy wyliczyć.
Np. dla m = 2 oraz n = 3:
Punkty docelowe
1 2 3
1 x11 x12 x13 a1
Składnice
2 x21 x22 x23 a2
b1 b2 b3
Stąd całkowita ilość towaru przewożona ze składnicy może być
wyrażona zależnością liniową:
Składnica 1: x11 + x12 + x13 d" a1
Składnica 2: x21 + x22 + x23 d" a2
Całkowite ilości towarów przesyłane do punktów docelowych
wyrażone są zależnościami liniowymi:
x11 + x21 d" b1
x12 + x22 d" b2
x13 + x23 d" b3
Koszt przesłania towaru jest funkcją liniową, tzn. koszt
przesłania xij jednostek wynosi:
cijxij
Paweł Gomoliński, Podstawy logistyki 9-2 16-02-2010
Warunek maksymalizacji rentowności otrzymuje się poprzez
minimalizację liniowej funkcji kosztu transportu:
c11x11 + c12x12 + c13x13 + c21x21 + c22x22 + c23x23
Ponieważ ujemne wartości xij mogłyby przedstawiać ilości
towarów przesyłanych w kierunku odwrotnym do założonego,
wymagane jest:
xij e" 0
Stąd dla m = 2 i n = 3 zagadnienie transportowe z minimalizacją
kosztu może być sformułowane jako:
(min) Z = c11x11 + c12x12 + c13x13 + c21x21 + c22x22 + c23x23
przy ograniczeniach:
x11 + x12 + x13 d" a1
x21 + x22 + x23 d" a2
x11 + x21 d" b1
x12 + x22 d" b2
x13 + x23 d" b3
x11, x12, x13, x21, x22, x23 e" 0
Paweł Gomoliński, Podstawy logistyki 9-3 16-02-2010
Przykład
Sformułować liniowy model decyzyjny, pozwalający określić
najmniej kosztowny sposób dystrybucji towarów z magazynów
do poszczególnych odbiorców w ramach realizacji zamówienia.
Zapasy towarów:
Magazyn 1: 1000 sztuk
Magazyn 2: 2200 sztuk
Zamówienia:
Odbiorca 1: 350 sztuk
Odbiorca 2: 650 sztuk
Odbiorca 3: 750 sztuk
Odbiorca 4: 900 sztuk
Koszty jednostkowe transportu z magazynu do odbiorcy [zł]
(w przeliczeniu na 1 sztukę towaru):
Odbiorca 1 Odbiorca 2 Odbiorca 3 Odbiorca 4
Magazyn 1 4,00 3,00 1,20 2,70
Magazyn 2 3,00 1,80 2,50 4,50
Paweł Gomoliński, Podstawy logistyki 9-4 16-02-2010
Rozwiązanie
1. Zmienne decyzyjne:
xij liczba sztuk towaru przewożona z magazynu i do
odbiorcy j
x11 liczba sztuk towaru z magazynu 1 do odbiorcy 1
x12 liczba sztuk towaru z magazynu 1 do odbiorcy 2
x13 liczba sztuk towaru z magazynu 1 do odbiorcy 3
x14 liczba sztuk towaru z magazynu 1 do odbiorcy 4
x21 liczba sztuk towaru z magazynu 2 do odbiorcy 1
x22 liczba sztuk towaru z magazynu 2 do odbiorcy 2
x23 liczba sztuk towaru z magazynu 2 do odbiorcy 3
x24 liczba sztuk towaru z magazynu 2 do odbiorcy 4
Odbiorca 1 Odbiorca 2 Odbiorca 3 Odbiorca 4
Magazyn 1 x11 x12 x13 x14
Magazyn 2 x21 x22 x23 x24
Paweł Gomoliński, Podstawy logistyki 9-5 16-02-2010
Odbiorca 1 Odbiorca 2 Odbiorca 3 Odbiorca 4
Magazyn 1 x11 x12 x13 x14
Magazyn 2 x21 x22 x23 x24
Odbiorca 1 Odbiorca 2 Odbiorca 3 Odbiorca 4
Magazyn 1 4,00 3,00 1,20 2,70
Magazyn 2 3,00 1,80 2,50 4,50
2. Funkcja celu:
(min) Z = 4,00x11 + 3,00x12 + 1,20x13 + 2,70x14 + 3,00x21 +
1,80x22 + 2,50x23 + 4,50x24
3. Ograniczenia:
x11 + x12 + x13 + x14 d" 1000 (magazyn 1)
ilości towaru
x21 + x22 + x23 + x24 d" 2200 (magazyn 2)
x11 + x21 d" 350 (odbiorca 1)
x12 + x22 d" 650 (odbiorca 2)
wielkości
zamówień
x13 + x23 d" 750 (odbiorca 3)
x14 + x24 d" 900 (odbiorca 4)
x11, x12, x13, x14, x21, x22, x23, x24 e" 0
Paweł Gomoliński, Podstawy logistyki 9-6 16-02-2010
Uogólnione zagadnienie transportowe
Przy użyciu m typów środków transportu należy wykonać n
zadań przewozowych. Liczebność środka transportu i wynosi
ai (i = 1, 2, ..., m). Zadanie transportowe j polega na
przewiezieniu bj (j = 1, 2, ..., n) jednostek produktów.
Aadowność środka transportu i użytego do realizacji zadania
j wynosi dij, a jego koszt wynosi cij (i = 1, 2, ..., m;
j = 1, 2, ..., n).
Należy tak rozdzielić zadania przewozowe pomiędzy dostępne
środki transportu, aby sumaryczny koszt transportu był
najniższy.
Paweł Gomoliński, Podstawy logistyki 9-7 16-02-2010
Rozwiązanie:
Zmienne decyzyjne:
xij liczba środków transportu i użytych do realizacji
zadania j .
Funkcja celu:
m n
(min) Z = cijxij
" "
i=1 j=1
przy warunkach ograniczających:
x11 + x12 + ... + x1n d" a1
x21 + x22 + ... + x2n d" a2
ograniczona liczba środków
transportu
. . .
xm1 + xm2 + ... + xmn d" am
d11x11 + d21x21 + ... + dm1xm1 e" b1
d12x12 + d22x22 + ... + dm2xm2 e" b2
wymóg realizacji wszystkich
zadań transportowych
. . .
d1nx1n + d2nx2n + ... + dmnxmn e" bn
oraz
xij e" 0; xij " C
Paweł Gomoliński, Podstawy logistyki 9-8 16-02-2010
Przykład
Firma przewozowa, mająca do dyspozycji 4 rodzaje
samochodów dostawczych różniących się ładownością,
otrzymała zlecenie przewiezienia określonych ilości 3 rodzajów
towarów drobnicowych . Koszty przewozu poszczególnych
rodzajów towarów zależą od użytego środka transportu.
Należy ustalić, w jaki sposób rozdzielić zadania przewozowe
pomiędzy dostępne środki transportu, aby uzyskać najniższy
koszt realizacji zlecenia.
Wartości parametrów ładunkowych, ilościowych i kosztowych
są następujące:
Paweł Gomoliński, Podstawy logistyki 9-9 16-02-2010
Środki transportu:
Liczba sztuk Aadowność
[kg]
Van 1 7 400
Van 2 12 600
Van 3 6 950
Van 4 4 1600
Towary:
Liczba sztuk Masa 1 sztuki
[kg]
1 3000 3,5
2 400 42,0
3 75 210,0
Zryczałtowane koszty użycia samochodów do transportu
poszczególnych towarów [zł]:
Towar 1 Towar 2 Towar 3
Van 1 11 12 13
Van 2 21 22 23
Van 3 31 32 33
Van 4 41 42 43
Paweł Gomoliński, Podstawy logistyki 9-10 16-02-2010
Rozwiązanie:
1. Zmienne decyzyjne
xij liczba środków transportu i użytych do przewozu
towaru j .
x11 liczba samochodów Van 1 przewożących towar 1
x12 liczba samochodów Van 1 przewożących towar 2
x13 liczba samochodów Van 1 przewożących towar 3
x21 liczba samochodów Van 2 przewożących towar 1
x22 liczba samochodów Van 2 przewożących towar 2
x23 liczba samochodów Van 2 przewożących towar 3
x31 liczba samochodów Van 3 przewożących towar 1
x32 liczba samochodów Van 3 przewożących towar 2
x33 liczba samochodów Van 3 przewożących towar 3
x41 liczba samochodów Van 4 przewożących towar 1
x42 liczba samochodów Van 4 przewożących towar 2
x43 liczba samochodów Van 4 przewożących towar 3
Paweł Gomoliński, Podstawy logistyki 9-11 16-02-2010
2. Funkcja celu
(min) Z = 11x11 + 12x12 + 13x13 + 21x21 + 22x22+ 23x23 +
31x31 + 32x32+ 33x33 + 41x41 + 42x42+ 43x43
3. Ograniczenia
x11 + x12 + x13 d" 7 (Van 1)
x21 + x22 + x23 d" 12 (Van 2)
x31 + x32 + x33 d" 6 (Van 3)
x41 + x42 + x43 d" 4 (Van 4)
400 x11 + 600 x21 + 950 x31 + 1600 x41 e" 3000 x 3,5 (towar 1)
400 x12 + 600 x22 + 950 x32 + 1600 x42 e" 400 x 42,0 (towar 2)
400 x13 + 600 x23 + 950 x33 + 1600 x43 e" 75 x 210,0 (towar 3)
Sumaryczna nośność użytych środków Masa towaru do
transportu przewiezienia
oraz
xij e" 0; xij " C
Paweł Gomoliński, Podstawy logistyki 9-12 16-02-2010
Zagadnienie załadunku
Przewoznik dysponuje określonymi rodzajami środków
transportu. Aadowność środka transportu rodzaju i wynosi Li,
zaś jego pojemność Vi. Do przewiezienia są różnego rodzaju
towary j w ilościach Mj (jednostek masy lub sztuk), o różnej
masie jednostkowej mj (jeżeli ilości podane są w sztukach), o
różnej objętości jednostkowej vj oraz o różnej zyskowności
jednostkowej cj (oba parametry na jednostkę masy lub jedną
sztukę).
Ustalić najkorzystniejszy sposób załadunku środków transportu.
Środki transportu Aadowność Pojemność
1 L1 V1
2 L2 V2
. . . . . . . . .
n Ln Vn
Ilość do Masa Objętość Zysk
przewiezienia jednostkowa jednostkowa jednostkowy
Towar
(masa lub szt.) (na 1 szt.) (na jedn. masy (na jedn. masy
lub 1 szt.) lub 1 szt.)
1 M1 m1 v1 c1
2 M2 m2 v2 c2
. . . . . . . . . . . . . . .
k Mk mk vk ck
Paweł Gomoliński, Podstawy logistyki 9-13 16-02-2010
Rozwiązanie:
Zmienne decyzyjne:
xij ilość towaru i załadowanego na środek transportu j .
Funkcja celu:
n k
(min) Z = cixij
" "
i=1 j=1
przy warunkach ograniczających:
m1x11 + m2x21 + ... + mkxk1 d" L1
m1x12 + m2x22 + ... + mkxk2 d" L2
ładowność środków
transportu
. . .
m1x1n + m2x2n + ... + mkxkn d" Ln
v1x11 + v2x21 + ... + vkxk1 d" V1
v1x12 + v2x22 + ... + vkxk2 d" V2
pojemność środków
transportu
. . .
v1x1n + v2x2n + ... + vkxkn d" Vn
x11 + x12 + ... + x1n d" M1
x21 + x22 + ... + x2n d" M2
ilości towarów do
przewiezienia
. . .
xk1 + xk2 + ... + xkn d" Mk
xij e" 0 (oraz xij " C gdy ilości towarów są w sztukach)
Paweł Gomoliński, Podstawy logistyki 9-14 16-02-2010
Przykład 1
Firma transportowa, dysponująca samochodami ciężarowymi z
przyczepami, przewozi 2 rodzaje ładunków paletowych.
Sformułować liniowy model decyzyjny, pozwalający określić,
jakie ilości poszczególnych rodzajów ładunków paletowych
należy ładować na samochód oraz na przyczepę (traktowane
odrębnie), aby zysk z transportu był maksymalny.
Środki transportu:
Aadowność [t] Pojemność [m3]
Samochód 12 50
Przyczepa 10 40
Aadunki paletowe (dane dla 1 sztuki):
Liczba Masa Objętość Zysk
[t] [m3] [zł]
1 110 0.15 0.3 60
2 75 0.25 0.6 80
Paweł Gomoliński, Podstawy logistyki 9-15 16-02-2010
Rozwiązanie:
1. Zmienne decyzyjne:
xij liczba palet i załadowana na środek transportu j
x11 liczba palet 1 w samochodzie
x21 liczba palet 2 w samochodzie
x12 liczba palet 1 w przyczepie
x22 liczba palet 2 w przyczepie
2. Funkcja celu (maksymalizacja zysku):
(max) Z = 60 (x11 + x12) + 80 (x21 + x22)
3. Ograniczenia:
x11 + x12 d" 110
ilość (liczba sztuk) do przetransportowania
x21 + x22 d" 75
0.15x11 + 0.25x21 d" 12 (palety 1 i 2 w samochodzie)
ładowność
0.15x12 + 0.25x22 d" 10 (palety 1 i 2 w przyczepie)
0.3x11 + 0.6x21 d" 50 (palety 1 i 2 w samochodzie)
pojemność
0.3x12 + 0.6x22 d" 40 (palety 1 i 2 w przyczepie)
xij e" 0; xij " C
Paweł Gomoliński, Podstawy logistyki 9-16 16-02-2010
Przykład 2
Samolot transportowy ma trzy przedziały bagażowe (przedni,
środkowy i tylny) o następujących parametrach:
Przedział Aadowność [t] Pojemność [m3]
Przedni 12 70
Środkowy 18 90
Tylny 10 50
Do przetransportowania zaoferowano następujące towary
masowe:
Objętość
Ilość (ciężar) Zysk
Towar jednostkowa
[t] [zł/t]
[m3/t]
1 20 5 320
2 16 7 400
3 25 6 360
4 13 4 290
Akceptowalny jest załadunek dowolnej części każdego
z towarów.
Sformułować liniowy model decyzyjny, pozwalający określić,
jakie ilości każdego z towarów powinny być lokowane
w poszczególnych przedziałach, aby zysk z transportu był
maksymalny.
Paweł Gomoliński, Podstawy logistyki 9-17 16-02-2010
Rozwiązanie:
1. Zmienne decyzyjne:
xij masa towaru i w przedziale ładunkowym j
P1 P2 P3
(Ł = sumaryczna masa tow. 1
T1 x11 x12 x13
we wszystkich przedziałach
(Ł = sumaryczna masa tow. 2
T2 x21 x22 x23
we wszystkich przedziałach
(Ł = sumaryczna masa tow. 3
T3 x31 x32 x33
we wszystkich przedziałach)
(Ł = sumaryczna masa tow. 4
T4 x41 x42 x43
we wszystkich przedziałach)
(Ł = (Ł = (Ł =
obciążenie obciążenie obciążenie
przedz. P1) przedz. P2) przedz. P3)
W celu zwiększenia przejrzystości funkcji celu można dokonać
podstawienia, wprowadzając zmienne pomocnicze:
x11 + x12 + x13 = x1 (sumaryczna masa towaru 1
we wszystkich przedziałach)
x21 + x22 + x23 = x2 (sumaryczna masa towaru 2 we
wszystkich przedziałach)
x31 + x32 + x33 = x3 (sumaryczna masa towaru 3 we
wszystkich przedziałach)
x41 + x42 + x43 = x4 (sumaryczna masa towaru 4 we
wszystkich przedziałach)
Paweł Gomoliński, Podstawy logistyki 9-18 16-02-2010
2. Funkcja celu (maksymalizacja zysku):
(max) Z = 320 x1 + 400 x2 + 360 x3 + 290 x4
3. Ograniczenia:
x1 d" 20
x2 d" 16
ilość (masa) do przetransportowania
x3 d" 25
x4 d" 13
x11 + x21 + x31 + x41 d" 12 (PP)
x12 + x22 + x32 + x42 d" 18 (PS)
ładowność
x13 + x23 + x33 + x43 d" 10 (PT)
5x11 + 7x21 + 6x31 + 4x41 d" 70 (PP)
pojemność
5x12 + 7x22 + 6x32 + 4x42 d" 90 (PS)
5x13 + 7x23 + 6x33 + 4x43 d" 50 (PT)
xij e" 0
Paweł Gomoliński, Podstawy logistyki 9-19 16-02-2010
Przykład 2a
Samolot transportowy ma trzy przedziały bagażowe (przedni,
środkowy i tylny) o następujących parametrach:
Przedział Aadowność [t] Pojemność [m3]
Przedni 12 70
Środkowy 18 90
Tylny 10 50
Do przetransportowania zaoferowano następujące ładunki
paletowe:
Ciężar Objętość
Ilość Zysk
Towar jednostkowy jednostkowa
[szt.] [zł/szt.]
[t/szt.] [m3/szt.]
1 20 3,1 5 320
2 16 1,5 7 400
3 25 2,2 6 360
4 13 1,7 4 290
Sformułować liniowy model decyzyjny, pozwalający określić,
jakie ilości każdego z towarów powinny być lokowane
w poszczególnych przedziałach, aby zysk z transportu był
maksymalny.
Paweł Gomoliński, Podstawy logistyki 9-20 16-02-2010
Rozwiązanie:
1. Zmienne decyzyjne:
xij liczba sztuk towaru i w przedziale ładunkowym j
P1 P2 P3
(Ł = liczba sztuk towaru 1 we
T1 x11 x12 x13
wszystkich przedziałach
(Ł = liczba sztuk towaru 2 we
T2 x21 x22 x23
wszystkich przedziałach
(Ł = liczba sztuk towaru 3 we
T3 x31 x32 x33
wszystkich przedziałach)
(Ł = liczba sztuk towaru 4 we
T4 x41 x42 x43
wszystkich przedziałach)
(Ł = (Ł = (Ł =
wypełnienie wypełnienie wypełnienie
przedz. P1) przedz. P2) przedz. P3)
x11 + x12 + x13 = x1 (liczba sztuk towaru 1
we wszystkich przedziałach)
x21 + x22 + x23 = x2 (liczba sztuk towaru 2 we
wszystkich przedziałach)
x31 + x32 + x33 = x3 (liczba sztuk towaru 3 we
wszystkich przedziałach)
x41 + x42 + x43 = x4 (liczba sztuk towaru 4 we
wszystkich przedziałach)
Paweł Gomoliński, Podstawy logistyki 9-21 16-02-2010
2. Funkcja celu (maksymalizacja zysku):
(max) Z = 320 x1 + 400 x2 + 360 x3 + 290 x4
3. Ograniczenia:
x1 d" 20
x2 d" 16
ilość (liczba sztuk) do przetransportowania
x3 d" 25
x4 d" 13
3,1x11 + 1,5x21 + 2,2x31 + 1,7x41 d" 12 (PP)
3,1x12 + 1,5x22 + 2,2x32 + 1,7x42 d" 18 (PS)
ładowność
3,1x13 + 1,5x23 + 2,2x33 + 1,7x43 d" 10 (PT)
5x11 + 7x21 + 6x31 + 4x41 d" 70 (PP)
pojemność
5x12 + 7x22 + 6x32 + 4x42 d" 90 (PS)
5x13 + 7x23 + 6x33 + 4x43 d" 50 (PT)
xij e" 0; xij " C
Paweł Gomoliński, Podstawy logistyki 9-22 16-02-2010
Zagadnienie produkcyjne
Wytwórca dysponuje określonymi ilościami różnych środków
produkcji i (surowce, siła robocza, sprzęt itp.), które mogą być
wykorzystane do wytworzenia określonej kombinacji różnych
wyrobów j . Wiadomo, jaka ilość środka i jest potrzebna do
wytworzenia wyrobu j , jak również znany jest zysk, jaki daje
każda wyprodukowana jednostka wyrobu j .
Należy sformułować liniowy model decyzyjny, pozwalający
określić kombinację wielkości produkcji poszczególnych
towarów dającą maksymalną rentowność.
Rozwiązanie:
Przyjmujemy następujące oznaczenia:
m ilość środków;
n ilość wyrobów;
aij ilość jednostek środka i niezbędna do wytworzenia
jednostki towaru j ;
bi maksymalna dostępna ilość jednostek środka i ;
cj zysk, jaki daje wyprodukowana jednostka wyrobu j ;
xj wielkość produkcji wyrobu j .
Współczynniki aij nazywane są niekiedy współczynnikami
nakładów i wyników.
Paweł Gomoliński, Podstawy logistyki 9-23 16-02-2010
Dostępna
Współczynniki nakładów
Nr środka produkcji wielkość
1 2 . . . n zasobu
1 a11 a12 . . . a1n b1
2 a21 a22 . . . a2n b2
. . . . . . . . . . . . . . . . . . . . . .
m am1 am2 . . . amn bm
Zysk jednostkowy c1 c2 . . . cn
Wielkość produkcji x1 x2 . . . xn
Całkowite zużycie środka i określa zależność liniowa:
ai1x1 + ai2x2 + . . . + ainxn
Nie może ono być większe od dostępnej ilości jednostek środka
produkcji i . Zatem dla każdego i obowiązuje zależność
liniowa:
ai1x1 + ai2x2 + . . . + ainxn d" bi
Ponieważ ujemne wartości xj nie mają interpretacji, musi być
spełniona nierówność:
xj e" 0
Zysk osiągany z wytworzenia xj jednostek wyrobu j wynosi:
cjxj
Paweł Gomoliński, Podstawy logistyki 9-24 16-02-2010
Sformułowanie zadania prowadzi zatem do maksymalizacji
funkcji zysku:
Z = c1x1 + c2x2 + . . . + cnxn
przy ograniczeniach:
a11 x1 + a12 x2 + .... + a1n xn d" b1
a21 x1 + a22 x2 + .... + a2n xn d" b2
a31 x1 + a32 x2 + .... + a3n xn d" b3
. . . . . . . . . . . . . . . . . . . . . . . . . . .
am1 x1 + am2 x2 + .... + amn xn d" bm
oraz
xj e" 0 j = 1, 2, ..., n
xj " C
Paweł Gomoliński, Podstawy logistyki 9-25 16-02-2010
Przykład
W fabryce zaprzestano produkcji nieopłacalnego wyrobu.
Powstały w ten sposób pewne rezerwy produkcyjne, które
można skierować do wytwarzania co najmniej jednego spośród
trzech nowych wyrobów, oznaczonych symbolami 1, 2 oraz 3.
Rezerwy produkcyjne określone są poprzez dostępny czas
maszynowy:
Typ maszyny Czas pracy w tygodniu
Wiertarka 500
Tokarka 350
Szlifierka 150
Jednostkowe obciążenie poszczególnych maszyn przy
produkcji nowych wyrobów oraz przypadający na nie zysk
jednostkowy:
Wyrób 1 Wyrób 2 Wyrób 3
Wiertarka 9 3 5
Tokarka 5 4 0
Szlifierka 3 0 2
Zysk
50 20 25
jednostkowy
Zapotrzebowanie na wyroby 1 i 2 przekracza zdolności
produkcyjne fabryki. Zapotrzebowanie na wyrób 3 wynosi 20
sztuk tygodniowo.
Sformułować liniowy model decyzyjny, pozwalający określić
program produkcji o maksymalnej rentowności.
Paweł Gomoliński, Podstawy logistyki 9-26 16-02-2010
Rozwiązanie:
Zmienne decyzyjne:
x1 tygodniowa wielkość produkcji wyrobu 1
x2 tygodniowa wielkość produkcji wyrobu 2
x3 tygodniowa wielkość produkcji wyrobu 3
Funkcja celu
(maksymalizacja zysku):
(max) Z = 50x1 + 20x2 + 25x3
Ograniczenia:
(wynikające z jednostkowego zapotrzebowania na zasoby i
wielkości dostępnych zasobów):
9x1 + 3x2 + 5x3 d" 500
tygodniowa dostępność
5x1 + 4x2+ 0x3 d" 350
maszyn
3x1 + 0x2 + 2x3 d" 150
możliwości sprzedaży
x3 d" 20 (x3 = 20)
wyrobu 3
oraz
x1, x2, x3 e" 0
x1, x2, x3 " C
Paweł Gomoliński, Podstawy logistyki 9-27 16-02-2010
Zagadnienie optymalnego podziału
Dana jest nieograniczona liczba jednowymiarowych produktów
wyjściowych (rury, pręty, kształtowniki, deski itp.) o jednakowej
długości L. Produkty te należy pociąć na różne odcinki o
długościach li (i = 1, 2, ..., m). Wymagana liczba
poszczególnych odcinków wynosi bi (i = 1, 2, ..., m).
Należy określić sposób cięcia, który zapewni najmniejszą ilość
odpadów.
Rozwiązanie:
1. Określenie wariantów cięcia
Dla skończonej liczby elementów L zawsze można określić
skończoną liczbę wariantów ich podziału na skończoną liczbę
odcinków li. Warianty te można ująć w macierzy [aij], dla której:
aij liczba odcinków typu i otrzymywanych z jednego
produktu wyjściowego ciętego sposobem j ;
i = 1,2, ..., m typy odcinków;
j = 1,2, ..., n sposoby cięcia produktów wyjściowych.
Elementy macierzy [aij] są liczbami całkowitymi. Wyznacza się
je na podstawie znanych wielkości L oraz li.
Paweł Gomoliński, Podstawy logistyki 9-28 16-02-2010
2. Określenie wielkości odpadu
Dla sposobu cięcia j :
rj = L - Ł aijli
3. Określenie zmiennych decyzyjnych
Zmienne te określają zastosowanie poszczególnych sposobów
cięcia w powiązaniu z wielkością odpadu produktu.
xj (j = 1,2, ..., n) krotność zastosowania sposobu cięcia j .
Zestawienie parametrów:
Sposoby cięcia
Zapotrzebowanie
Typy odcinków
1 2 . . . n na dane odcinki
1 a11 a12 . . . a1n b1
2 a21 a22 . . . a2n b2
. . . . . . . . . . . . . . . . . . . . . .
m am1 am2 . . . amn bm
Odpad r1 r2 . . . rn
Zastosowanie x1 x2 . . . xn
sposobów cięcia
Paweł Gomoliński, Podstawy logistyki 9-29 16-02-2010
Model zagadnienia minimalizacji odpadów przy cięciu
produktów
(min) Z = r1x1 + r2x2 + ... + rnxn = Ł rjxj
przy warunkach ograniczających:
a11x1 + a12x2 + ... + a1nxn = b1
zapotrzebowanie na
a21x1 + a22x2 + ... + a2nxn = b2
poszczególne odcinki
. . .
produktu
am1x1 + am2x2 + ... + amnxn = bm
xj e" 0
xj " C (xj całkowite)
Jeżeli w zagadnieniu pominiemy parametr determinujący
wielkość odpadu, otrzymamy funkcję celu:
(min) Z = Ł xj
pozwalającą wyznaczyć minimalną liczbę produktów, z których
można uzyskać żądane ilości odcinków, bądz zminimalizować
liczbę operacji cięcia.
Paweł Gomoliński, Podstawy logistyki 9-30 16-02-2010
Przykład
Dane są rury o standardowej długości 20 m. Potrzebne są
odcinki tych rur o długościach 11, 7 i 3 m. Wymagane liczby
tych odcinków wynoszą odpowiednio: b1, b2 oraz b3.
Należy określić optymalny program cięcia ze względu na
minimalizację odpadu.
Rozwiązanie:
Możliwe sposoby cięcia rury o długości 20 m i odpowiadające
im wielkości odpadów:
Sposób cięcia
Długość Zapotrzebowanie
1 2 3 4 5 6 7
odcinka
11 m 1 0 0 1 0 1 0 b1
7 m 0 2 1 1 0 0 2 b2
3 m 3 2 4 0 6 0 0 b3
Odpad 0 0 1 2 2 9 6
Teoretycznie nieracjonalne sposoby cięcia 6 i 7 (a w
ogólnym przypadku także i 5 ) mają zastosowanie np. w
sytuacji, gdy potrzebne są odcinki tylko o jednej długości np.
pod koniec realizacji zamówienia.
Paweł Gomoliński, Podstawy logistyki 9-31 16-02-2010
Zmienne decyzyjne:
xi krotność zastosowania sposobu cięcia i (i = 1, 2, ..., 7)
Funkcja celu:
(min) Z = x3 + 2x4 + 2x5 + 9x6 + 6x7
Ograniczenia:
x1 + x4 + x6 = b1
2x2 + x3 + x4 + 2x7 = b2
3x1 + 2x2 + 4x3 + 6x5 = b3
x1, x2, ..., x7 e" 0
x1, x2, ..., x7 " C
Paweł Gomoliński, Podstawy logistyki 9-32 16-02-2010
Zadanie 1
Sformułować model zagadnienia transportowego:
W czterech wagonach kolejowych przewożone są 3 rodzaje
towarów. Jakie ilości sztuk poszczególnych rodzajów towarów
należy zabierać do każdego z wagonów, aby zysk z transportu
był maksymalny?
Środki transportu:
Nośność Pojemność
[t] [m3]
Wagon 1 60 240
Wagon 2 40 160
Wagon 3 40 160
Wagon 4 55 225
Towary:
Masa 1 sztuki Objętość 1 sztuki Zysk z 1 sztuki
[t] [m3] [zł]
1 0,3 3 60
2 0,4 6 80
3 0,2 4 20
Paweł Gomoliński, Podstawy logistyki 9-33 16-02-2010
Zadanie 2
Sformułować model zagadnienia produkcyjnego:
Przygotowywana jest produkcja 3 nowych wyrobów
wytwarzanych na 3 rodzajach maszyn. Dla podanych danych
(dyspozycyjność oraz zapotrzebowanie czasu pracy maszyn,
zysk jednostkowy i możliwości zbytu produktów) określić
optymalny tygodniowy program produkcyjny, zapewniający
maksymalną rentowność.
Maszyny:
Maksymalny czas pracy w tygodniu [godz.]
Maszyna 1 48
Maszyna 2 42
Maszyna 3 52
Produkty (jednostkowe zapotrzebowanie czasu pracy maszyn):
Produkt 1 Produkt 2 Produkt 3
Maszyna 1 [godz./szt.] 0.7 0 0.3
Maszyna 2 [godz./szt.] 0.5 0.2 0.1
Maszyna 3 [godz./szt.] 0 0.4 0.6
Zysk jedn. [zł./szt.] 25 15 30
Zbyt w tygodniu [szt.] 17 nieograniczony nieograniczony
Paweł Gomoliński, Podstawy logistyki 9-34 16-02-2010
Rozwiązywanie zadań programowania
liniowego metodą SIMPLEKS
Metoda simpleks służy do wyznaczania rozwiązań optymalnych
zadań programowania liniowego.
Algorytm postępowania:
Algorytm ogólny Algorytm metody simpleks
Inicjalizacja Inicjalizacja
Iteracja Iteracja
test
warunek
n n
optymalnoS
ci
przerwania
t t
stop stop
Za każdym razem rozwiązanie układu
równań prowadzące do uzyskania nowego
rezultatu, poddawanego testowi
optymalności.
Paweł Gomoliński, Podstawy logistyki 10-1 16-02-2010
Interpretacja graficzna metody simpleks:
x2
Z = 3x1 + 5x2
10
(0,9)
9
8 x1 = 4
7
(0,6)
(2,6)
(4,6)
6 2x2 = 12
5
4
(4,3)
3
3x1 + 2x2 = 18
2
1
(6,0)
(4,0)
(0,0)
0
1 2 3 4 5 6 7 8 9 10 x1
Oznaczenia:
Dopuszczalne rozwiązania narożne:
(0,0), (0,6), (2,6), (4,3), (4,0)
Niedopuszczalne rozwiązania narożne:
(0,9), (4,6), (6,0)
Dopuszczalne rozwiązania narożne sąsiadują ze sobą.
Paweł Gomoliński, Podstawy logistyki 10-2 16-02-2010
Trzy główne własności dopuszczalnych rozwiązań
narożnych:
1a. Jeśli istnieje dokładnie jedno rozwiązanie optymalne, to
musi ono być dopuszczalnym rozwiązaniem narożnym.
1b. Jeśli istnieje więcej niż jedno rozwiązanie optymalne, to
przynajmniej dwa z nich muszą być sąsiednimi
dopuszczalnymi rozwiązaniami narożnymi.
2. Istnieje skończona liczba dopuszczalnych rozwiązań
narożnych.
3. Jeśli jedno dopuszczalne rozwiązanie narożne jest lepsze
od dwóch sąsiednich, to jest ono jednocześnie lepsze od
wszystkich pozostałych rozwiązań, czyli jest rozwiązaniem
optymalnym.
Z własności 1 wynika, że poszukiwanie rozwiązania
optymalnego może zostać ograniczone wyłącznie do
dopuszczalnych rozwiązań narożnych, a więc do skończonej
ich liczby (co wynika z własności 2).
Własność 3 stanowi bardzo wygodny test optymalności.
Własności te tworzą podstawę metody SIMPLEKS.
Paweł Gomoliński, Podstawy logistyki 10-3 16-02-2010
Zarys algorytmu SIMPLEX
1. Krok początkowy: Rozpoczęcie od dopuszczalnego
rozwiązania narożnego.
2. Iteracja: Przejście do sąsiedniego
dopuszczalnego rozwiązania
narożnego, które jest lepsze.
3. Test optymalności: Aktualnie wybrane dopuszczalne
rozwiązanie narożne jest optymalne,
gdy żadne z sąsiednich
dopuszczalnych rozwiązań narożnych
nie jest od niego lepsze.
Paweł Gomoliński, Podstawy logistyki 10-4 16-02-2010
x2
Z = 3x1 + 5x2
(0,9)
x1 d" 4
(0,6) (2,6)
(4,6)
2x2 d" 12
(4,3)
3x1 + 2x2 d" 18
(6,0)
(4,0)
(0,0)
x1
1. Krok początkowy: Rozpoczęcie od punktu (0, 0).
2a. Iteracja 1: Przejście od punktu (0, 0) do punktu
(0, 6).
2b. Iteracja 2: Przejście od punktu (0, 6) do punktu
(2, 6).
3. Test optymalności: Ani (0, 6), ani (4, 3) nie jest lepsze od
(2, 6) koniec iteracji.
(2, 6) jest optimum.
Paweł Gomoliński, Podstawy logistyki 10-5 16-02-2010
W celu przystosowania algorytmu do rozwiązania drogą
numeryczną, konieczne jest jego przekształcenie w procedurę
algebraiczną.
Z punktu widzenia procedury algebraicznej wygodniej jest
przetwarzać równania niż nierówności.
Przekształcenia dokonuje się za pomocą zmiennych
różnicowych.
Np. dla: x1 d" 4
wprowadzamy: x3 = 4 - x1
i otrzymujemy: x1 + x3 = 4
x3 e" 0
W ten sposób tworzy się równoważny model, będący
rozszerzonym sformułowaniem problemu, składający się z
równań:
(max) Z = 3x1 + 5x2
x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18
xj e" 0 dla j = 1, 2, ..., 5
Paweł Gomoliński, Podstawy logistyki 10-6 16-02-2010
Rozwiązanie rozszerzone: rozwiązanie (dowolne) dla modelu
równoważnego, np.
(1, 1, 3, 10, 13) zamiast (1, 1)
x3, x4, x5 dla x1 = 1 i x2 = 1
(3, 2, 1, 8, 5) zamiast (3, 2)
Rozwiązanie bazowe: rozszerzone rozwiązanie narożne, np.
(0, 9, 4, -6, 0) zamiast (0, 9)
x3, x4, x5 dla x1 = 0 i x2 = 9
(4, 6, 0, 0, -6) zamiast (4, 6)
Dopuszczalne rozwiązanie bazowe: rozszerzone
dopuszczalne rozwiązanie narożne, np.
(0, 6, 4, 0, 6) zamiast (0, 6)
x3, x4, x5 dla x1 = 0 i x2 = 6
(0, 0, 4, 12, 18) zamiast (0, 0)
Paweł Gomoliński, Podstawy logistyki 10-7 16-02-2010
W modelu rozszerzonym liczba zmiennych jest większa niż
liczba równań. Różnica tych wartości tworzy tzw. stopnie
swobody rozwiązania.
Liczba stopni swobody = liczba zmiennych liczba równań
Nadmiarowym zmiennym można nadać dowolne wartości.
W metodzie simplex zmiennym tym nadaje się wartość zero.
Zmienne niebazowe: zmienne, których wartość przyjmuje się
równą zeru.
Zmienne bazowe: pozostałe zmienne (tyle, ile równań)
Zasady:
1. Liczba zmiennych niebazowych = liczba stopni swobody
2. Liczba zmiennych bazowych = liczba ograniczeń (l. równań)
3. Przejście od aktualnie wybranego dopuszczalnego
rozwiązania bazowego do sąsiedniego dopuszczalnego
rozwiązania bazowego związane jest ze zmianą jednej ze
zmiennych niebazowych na bazową oraz jednej ze
zmiennych bazowych na niebazową.
Paweł Gomoliński, Podstawy logistyki 10-8 16-02-2010
Rozważmy sąsiednie dopuszczalne rozwiązania narożne
(0, 0) i (0, 6):
x2
(0,9)
(0,6) (2,6)
(4,6)
(4,3)
(6,0)
(4,0)
(0,0)
x1
Rozwiązania rozszerzone:
(0, 0, 4, 12, 18) oraz (0, 6, 4, 0, 6)
są sąsiednimi dopuszczalnymi rozwiązaniami bazowymi.
Zmienne niebazowe (których wartość przyjmuje się = 0), to:
(x1, x2) oraz (x1, x4)
(0, 0, 4, 12, 18) (0, 6, 4, 0, 6)
Różnica między nimi sprowadza się do zastąpienia x2 przez x4.
W związku z tym przejście od (0, 0, 4, 12, 18) do (0, 6, 4, 0, 6)
wymaga zmiany statusu x2 ze zmiennej niebazowej na bazową,
zaś x4 z bazowej na niebazową.
Paweł Gomoliński, Podstawy logistyki 10-9 16-02-2010
Ostateczna postać układu równań do rozwiązania metodą
simplex:
(max) Z
przy ograniczeniach:
(0) Z 3x1 5x2 = 0
(1) x1 + x3 = 4
(2) 2x2 + x4 = 12
(3) 3x1 + 2x2 + x5 = 18
zm. niebazowe zm. bazowe
(= 0) (`" 0)
oraz xj e" 0 dla j = 1, 2, ..., 5.
Każde równanie zawiera tylko jedną zmienną bazową.
W równaniu (0) są tylko zmienne niebazowe.
Paweł Gomoliński, Podstawy logistyki 10-10 16-02-2010
Schemat postępowania przy rozwiązywaniu zagadnień
programowania liniowego
1. Inicjalizacja: Znalezć pierwsze dopuszczalne rozwiązanie
bazowe (dopuszczalne rozwiązanie narożne).
Można zacząć od dowolnego dopuszczalnego rozwiązania
narożnego (bazowego). Najlepiej jednak wybrać takie,
w którym wszystkie zmienne pierwotne są równe zeru.
2. Iteracja: Przejść do następnego, sąsiedniego
dopuszczalnego rozwiązania bazowego (narożnego)
a) Kierunek ruchu która zmienna niebazowa powinna stać
się zmienną bazową?
Zmienną bazową powinna stać się ta zmienna niebazowa,
która powoduje większy wzrost funkcji celu (Z).
b) Punkt docelowy która zmienna bazowa powinna stać
się zmienną niebazową?
Zmienną niebazową (= 0) powinna stać się ta zmienna
bazowa, przy której wybrana w punkcie a) zmienna bazowa
przyjmuje najmniejszą wartość (ale nieujemną, jeżeli xi e" 0).
Paweł Gomoliński, Podstawy logistyki 10-11 16-02-2010
c) Znalezienie nowego rozwiązania sąsiedniego
(narożnego)
Nowe rozwiązanie znajduje się, przekształcając metodami
algebraicznymi układ równań do postaci, w której
współczynniki przy zmiennych bazowych mają wartość 1.
3. Test optymalizacji: Rozpoznanie, czy aktualne
dopuszczalne rozwiązanie bazowe (narożne) nie ma
żadnych lepszych punktów sąsiadujących
Sprawdzenie, jak wzrost wartości zmiennych niebazowych
wpłynie na wartość funkcji celu.
Paweł Gomoliński, Podstawy logistyki 10-12 16-02-2010
Przykład
(max) Z = 3x1 + 5x2
x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18
1. Inicjalizacja
Zmienne niebazowe: x1 = 0, x2 = 0.
(1) x1 + x3 = 4
(2) 2x2 + x4 = 12
(3) 3x1 + 2x2 + x5 = 18
Rozwiązanie początkowe: (0, 0, 4, 12, 18)
2. Iteracja
a) Wybór zmiennej niebazowej, która powinna stać się
zmienną bazową
Spośród aktualnych zmiennych niebazowych (x1 oraz x2) należy
wybrać tę, która spowoduje większy wzrost aktualnej funkcji
celu (Z = 3x1 + 5x2).
Jest to zmienna x2.
Paweł Gomoliński, Podstawy logistyki 10-13 16-02-2010
b) Wybór zmiennej bazowej, która powinna stać się zmienną
niebazową (= 0)
Będzie to ta zmienna, przy której x2 przyjmuje najmniejszą
wartość:
Zmienna Równanie Wartość x2
bazowa
x3 (1) x1 + x3 = 4 Nieograniczona
x4 (2) 2x2 + x4 = 12 x2 = 12/2 = 6 (min)
x5 (3) 3x1 + 2x2 + x5 = 18 x2 = 18/2 = 9
Nowa postać układu równań:
(0) Z 3x1 5x2 = 0
(1) x1 + x3 = 4
(2) 2x2 + x4 = 12
(3) 3x1 + 2x2 + x5 = 18
Z odgrywa rolę zmiennej bazowej w równaniu funkcji celu.
Paweł Gomoliński, Podstawy logistyki 10-14 16-02-2010
c) Znalezienie nowego rozwiązania sąsiedniego (narożnego)
Należy teraz rozwiązać uzyskany w kroku b) układ równań dla
zmiennych Z, x2, x3 oraz x5.
Dokonuje się tego metodą eliminacji Gaussa.
Z równania (2) otrzymujemy:
x2 + 1/2x4 = 6 ! x2 = 6 1/2x4
stąd równanie dla lewej strony funkcji celu:
Z 3x1 5x2 = Z 3x1 5(6 1/2x4) = Z 3x1 30 + 5/2x4
Następnie należy wyeliminować x2 z pozostałych równań
oprócz (2), doprowadzając je działaniami algebraicznymi do
postaci ze współczynnikami przy zmiennych bazowych
równymi 1.
Nowa postać lewej strony równania (3):
3x1 + 2x2 + x5 = 3x1 + 2(6 1/2x4) + x5 = 3x1 + 12 x4 + x5
Paweł Gomoliński, Podstawy logistyki 10-15 16-02-2010
Uzyskany w ten sposób nowy układ równań:
(0) Z 3x1 + 5/2x4 = 30
(1) x1 + x3 = 4
(2) x2 + 1/2x4 = 6
(3) 3x1 x4 + x5 = 6
Nowe rozwiązanie: (0, 6, 4, 0, 6)
3. Test optymalizacji: Sprawdzenie, jak zachowa się obecnie
funkcja celu przy wzroście zmiennych niebazowych
Z = 30 + 3x1 - 5/2x4 wzrost x1 może spowodować wzrost Z:
To rozwiązanie nie jest optymalne
Paweł Gomoliński, Podstawy logistyki 10-16 16-02-2010
2. Iteracja II
a) Wybór zmiennej niebazowej, która powinna stać się zmienną
bazową
x1 (ponieważ spowoduje większy wzrost Z = 30 + 3x1 5/2x4)
b) Wybór zmiennej bazowej, która powinna stać się zmienną
niebazową (= 0)
Będzie to ta zmienna, przy której x1 przyjmuje najmniejszą
wartość:
Zmienna Równanie Wartość x1
bazowa
x3 (1) x1 + x3 = 4 4
x2 (2) x2 + 1/2x4 = 6 Nieograniczona
x5 (3) 3x1 x4 + x5 = 6 x1 = 6/3 = 2 (min)
Paweł Gomoliński, Podstawy logistyki 10-17 16-02-2010
c) Znalezienie nowego rozwiązania sąsiedniego (narożnego)
Należy wyeliminować x1 z pozostałych równań oprócz (3),
doprowadzając je działaniami algebraicznymi do postaci ze
współczynnikami przy zmiennych bazowych równymi 1.
Z równania (3):
3x1 = 6 + x4 x5
Ó!
Z 3x1 30 + 5/2x4 = Z (6 + x4 x5) 30 + 5/2x4 =
Z 36 x4 + x5 + 5/2x4 ! Z + 3/2x4 x5 = 36
(0) Z + 3/2x4 + x5 = 36
(1) x3 + 1/3x4 1/3x5 = 2
(2) x2 + 1/2x4 = 6
(3) x1 1/3x4 + 1/3x5 = 2
Nowe rozwiązanie: (2, 6, 2, 0, 0)
3. Test optymalizacji: Sprawdzenie, jak zachowa się obecnie
funkcja celu przy wzroście zmiennych niebazowych
Z = 36 3/2x4 x5
Żadna zmienna nie może spowodować wzrostu Z.
To rozwiązanie jest optymalne.
Paweł Gomoliński, Podstawy logistyki 10-18 16-02-2010
Podsumowanie zasad algorytmu simpleks
1. Poruszamy się wyłącznie po narożach.
2. Zadanie klasyczne zadanie standardowe
nierówność równanie
rozwiązanie
rozszerzone
(dodatkowe zmienne)
3. Zmienne decyzyjne = zmienne bazowe + niebazowe
liczba równań xNB = 0
xB `" 0
4. W każdym równaniu tylko 1 zmienna bazowa ze
współczynnikiem 1.
5. Funkcja celu wyrażona tylko za pomocą zmiennych
niebazowych.
Paweł Gomoliński, Podstawy logistyki 10-19 16-02-2010
Wyszukiwarka
Podobne podstrony:
wykład 1 Podstawy Logistyki
Podstawy logistyki Wyk 1 3
logistyka podstawowe zagadnieania cz 1
Wyk6 ORBITA GPS Podstawowe informacje
Podstawowe informacje o Rybnie
3 podstawy teorii stanu naprezenia, prawo hookea
zestawy cwiczen przygotowane na podstawie programu Mistrz Klawia 6
podstaw uniw
Jezyk angielski arkusz I poziom podstawowy (5)
07 GIMP od podstaw, cz 4 Przekształcenia
rynek pracy logistyka
więcej podobnych podstron