Zagadnienia transportowe
Zagadnienia transportowe
T.Trzaskalik
Wprowadzenie
do badań operacyjnych
z komputerem
Sformułowanie zadania transportowego
Sformułowanie zadania transportowego
Mamy ustaloną liczbę dostawców i odbiorców,
znamy podaż każdego dostawcy i
zapotrzebowanie każdego odbiorcy w ustalonym
odcinku czasu oraz koszty jednostkowe
transportu pomiędzy poszczególnymi
dostawcami i odbiorcami, proporcjonalnie do
ilości przewiezionego towaru. Należy znalez
ć
taki plan przewozów, który minimalizuje łączny
ich koszt
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 2
Zadanie transportowe w ujęciu programowania liniowego (1)
Zadanie transportowe w ujęciu programowania liniowego (1)
Przykład 3.1
Przykład 3.1
Miejscowość O1 O2 O3
D1 1 4 7
D2 3 5 11
D3 6 7 9
1
20 D1 O1 10
4
7
3
5
20 D2 11 O2 15
7
6
30 D3 9 O3 45
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 3
Zadanie transportowe w ujęciu programowania liniowego (2)
Zadanie transportowe w ujęciu programowania liniowego (2)
Cel
Cel
Określenie planu przewozów, który minimalizuje łączny koszt.
Zmienne decyzyjne
Zmienne decyzyjne
x11 - planowany przewóz na trasie od D1 do O1
x12 - planowany przewóz na trasie od D1 do O2
x13 - planowany przewóz na trasie od D1 do O3
x21 - planowany przewóz na trasie od D2 do O1
x22 - planowany przewóz na trasie od D2 do O2
x23 - planowany przewóz na trasie od D2 do O3
x31 - planowany przewóz na trasie od D3 do O1
x32 - planowany przewóz na trasie od D3 do O2
x33 - planowany przewóz na trasie od D3 do O3
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 4
Zadanie transportowe w ujęciu programowania liniowego (3)
Zadanie transportowe w ujęciu programowania liniowego (3)
Funkcja celu
Funkcja celu
f (x11, x12, x13, x21, x22, x23, x31,x32, x33) = x11 +4x12 +7x13 +
+3x21 +5x22 +11x23 +6x31 +7x32 +9x33 min
Ograniczenia
Ograniczenia
x11 +x12 +x13 = 20
x21 +x22 +x23 = 20
x31 +x32 +x33 = 30
x11 +x21 +x31 = 10
x12 +x22 +x32 = 15
x13 +x23 +x33 = 45
x11,..., x33 e" 0
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x11 = 5 x12 = 0 x13 = 15
x21 = 5 x22 = 15 x23 = 0
x31 = 0 x32 = 0 x33 = 30
Minimalny koszt transportu wynosi 470.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 5
Zadanie transportowe w ujęciu programowania liniowego (4)
Zadanie transportowe w ujęciu programowania liniowego (4)
Postać macierzowa
Postać macierzowa
c - wektor funkcji celu,
cx max
cx min
A - macierz współczynników,
Ax = b
Ax = b
Ò!
x e" 0
b - wektor warunków
przy czym c = -c
x e" 0
ograniczajÄ…cych,
x - wektor zmiennych.
x11
îÅ‚ Å‚Å‚
c = [1 4 7 3 5 11 6 7 9]
ïÅ‚x śł
12
ïÅ‚ śł
îÅ‚20Å‚Å‚
x13
ïÅ‚ śł
ïÅ‚20śł
îÅ‚1 1 1 0 0 0 0 0 0Å‚Å‚ ïÅ‚x śł
ïÅ‚ śł
21
ïÅ‚0 0 0 1 1 1 0 0 0śł ïÅ‚ śł
30
ïÅ‚ śł
b =
ïÅ‚ śł x = x22
ïÅ‚ śł
ïÅ‚10śł
0 0 0 0 0 0 1 1 1
ïÅ‚ śł ïÅ‚x śł
ïÅ‚ śł
A =
23
ïÅ‚1 0 0 1 0 0 1 0 0śł ïÅ‚ śł
15
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚x31śł
ïÅ‚45śł
ðÅ‚ ûÅ‚
0 1 0 0 1 0 0 1 0
ïÅ‚ śł
ïÅ‚x śł
32
ïÅ‚0 0 1 0 0 1 0 0 1śł
ïÅ‚ śł
ðÅ‚ ûÅ‚
ïÅ‚ śł
ðÅ‚x ûÅ‚
33
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 6
Zadanie prymalne i dualne (1)
Zadanie prymalne i dualne (1)
Zadanie prymalne (ZP) Zadanie dualne (ZD)
cx max yb min
Ax = b yA e" c
x e" 0 y - dowolne
y = [y1 y2 y3 y4 y5 y6]
Przyjmujemy, że y = [u, v]
u  wektor zmiennych ZD odpowiadajÄ…cych dostawcom,
v  wektor zmiennych ZD odpowiadajÄ…cych odbiorcom.
u = [u1 u2 u3] v = [v1 v2 v3]
y = [u1 u2 u3 v1 v2 v3]
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 7
Zadanie prymalne i dualne (2)
Zadanie prymalne i dualne (2)
Zadanie dualne
Zadanie dualne
min
yb = [u1 u2 u3 v1 v2 v3] îÅ‚20Å‚Å‚ = 20u1 + 20u2 + 30u3 +10v1 +15v2 + 45v3
ïÅ‚20śł
30
ïÅ‚ śł
10
ïÅ‚ śł
15
ïÅ‚ śł
ïÅ‚45śł
ðÅ‚ ûÅ‚
-1Å‚Å‚
îÅ‚
- 4śł
yA
= [u1 u2 u3 v1 v2 v3] îÅ‚1 1 1 0 0 0 0 0 0Å‚Å‚ ïÅ‚ - 7śł
ïÅ‚
ïÅ‚0 0 0 1 1 1 0 0 0śł ïÅ‚ - 3śł
0 0 0 0 0 0 1 1 1
ïÅ‚ śł
e"
= c
- 5
ïÅ‚ śł
1 0 0 1 0 0 1 0 0
ïÅ‚ śł
ïÅ‚-11
śł
0 1 0 0 1 0 0 1 0
ïÅ‚ śł
ïÅ‚ - 6
śł
ïÅ‚0 0 1 0 0 1 0 0 1śł
ðÅ‚ ûÅ‚
ïÅ‚ - 7
śł
ïÅ‚ - 9śł
ðÅ‚ ûÅ‚
u1 + v1 e" -1 u1 + v2 e" -4 u1 + v3 e" -7
u2 + v1 e" -3 u2 + v2 e" -5 u2 + v3 e" -11
u3 + v1 e" -6 u3 + v2 e" -7 u3 + v3 e" -9
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 8
Zadanie prymalne i dualne (3)
Zadanie prymalne i dualne (3)
Zadanie prymalne
 x11  4x12  7x13  3x21  5x22  11x23  6x31  7x32  9x33 max
x11 +x12 +x13 = 20 x11 +x21 +x31 = 10
x21 +x22 +x23 = 20 x12 +x22 +x32 = 15
x31 +x32 +x33 = 30 x13 +x23 +x33 = 45
x11,..., x33 e" 0
Zadanie dualne
20u1 + 20u2 + 30u3 + 10v1 + 15v2 + 45v3 min
u1 + v1 + 1 e" 0 u1 + v2 + 4 e" 0 u1 + v3 + 7 e" 0
u2 + v1 + 3 e" 0 u2 + v2 + 5 e" 0 u2 + v3 + 11 e" 0
u3 + v1 + 6 e" 0 u3 + v2 + 7 e" 0 u3 + v3 + 9 e" 0
u1, u2, u3, v1, v2, v3 - dowolne
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 9
Zadanie prymalne i dualne (4)
Zadanie prymalne i dualne (4)
Zależności między zmiennymi i warunkami ograniczającymi
Zależności między zmiennymi i warunkami ograniczającymi
x11 odpowiada warunkowi u1 + v1 + 1 e" 0
x12 odpowiada warunkowi u1 + v2 + 4 e" 0
x13 odpowiada warunkowi u1 + v3 + 7 e" 0
x21 odpowiada warunkowi u2 + v1 + 3 e" 0
x22 odpowiada warunkowi u2 + v2 + 5 e" 0
x23 odpowiada warunkowi u2 + v3 + 11 e" 0
x31 odpowiada warunkowi u3 + v1 + 6 e" 0
x32 odpowiada warunkowi u3 + v2 + 7 e" 0
x33 odpowiada warunkowi u3 + v3 + 9 e" 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
10
Zadanie prymalne i dualne (5)
Zadanie prymalne i dualne (5)
Twierdzenie o komplementarności
Twierdzenie o komplementarności
(yA - c) = 0
czyli:
([u, v] A - c) x = 0
stÄ…d:
(u1 + v1 + 1) x11 = 0 (u1 + v2 + 4) x12 = 0
(u2 + v1 + 3) x21 = 0 (u2 + v2 + 5) x22 = 0
(u3 + v1 + 6) x31 = 0 (u3 + v2 + 7) x32 = 0
(u1 + v3 + 7) x13 = 0
(u2 + v3 + 11) x23 = 0
(u3 + v3 + 9) x33 = 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
11
Zadanie prymalne i dualne (6)
Zadanie prymalne i dualne (6)
Wnioski z twierdzenia o komplementarności
Wnioski z twierdzenia o komplementarności
Jeżeli x11 > 0, to u1 + v1 + 1 = 0
Jeżeli x12 > 0, to u1 + v2 + 4 = 0
Jeżeli x13 > 0, to u1 + v3 + 7 = 0
Jeżeli x21 > 0, to u2 + v1 + 3 = 0
Jeżeli x22 > 0, to u2 + v2 + 5 = 0
Jeżeli x23 > 0, to u2 + v3 + 11 = 0
Jeżeli x31 > 0, to u3 + v1 + 6 = 0
Jeżeli x32 > 0, to u3 + v2 + 7 = 0
Jeżeli x33 > 0, to u3 + v3 + 9 = 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
12
Zbilansowane zadanie transportowe
Zbilansowane zadanie transportowe
Oznaczenia
Oznaczenia
m - liczba dostawców,
n - liczba odbiorców,
ai - podaż i -tego dostawcy (i = 1,...,m),
bj - popyt j -tego odbiorcy (j = 1,...,n),
xij - ilość towaru przewieziona od i-tego dostawcy do j-tego odbiorcy,
cij - koszt przewozu jednostki towaru od i-tego dostawcy do j-tego odbiorcy.
m n
"a = "b
i j
i=1 j=1
Sformułowanie zadania
Sformułowanie zadania
m n
""c xij min
ij
i=1 j=1
n
= ai
dla i = 1,...,m
"xij
j=1
xij e" 0
m
= bj
dla j = 1,...,n
"xij
i=1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
13
Pierwsze dopuszczalne rozwiÄ…zanie bazowe
Pierwsze dopuszczalne rozwiÄ…zanie bazowe
Definicje
Definicje
Macierz przewozów Macierz kosztów
îÅ‚ _ _ _ Å‚Å‚ îÅ‚ Å‚Å‚
1 4 7
ïÅ‚ śł ïÅ‚ śł
= =
X _ _ _ C
ïÅ‚ śł ïÅ‚3 5 11 śł
ïÅ‚ śł ïÅ‚6 7 9 śł
_ _ _
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
RozwiÄ…zanie bazowe - zawiera n + m - 1 zmiennych bazowych
Węzły bazowe - odpowiadają zmiennym bazowym
Linia - węzły ustalonego wiersza lub ustalonej kolumny
xij = min (ai ,bj)
Wielkość przewozu
Podaż i popyt po modyfikacji
a i = ai  xij
b j = bj  xij
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
14
Metoda minimalnego elementu macierzy kosztów (1)
Metoda minimalnego elementu macierzy kosztów (1)
Rozwiązanie początkowe Podaż
10 20 10
*
20
0
30
0
10 0 15 45 Zapotrzebowanie
Macierz kosztów jednostkowych
*
1 4 7
3 5 11
6 7 9
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
15
Metoda minimalnego elementu macierzy kosztów (2)
Metoda minimalnego elementu macierzy kosztów (2)
Rozwiązanie początkowe Podaż
10 0 10 0
10
*
0 20
0
0 30
0
0 15 5 45 Zapotrzebowanie
Macierz kosztów jednostkowych
* *
1 4 7
3 5 11
6 7 9
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
16
Metoda minimalnego elementu macierzy kosztów (3)
Metoda minimalnego elementu macierzy kosztów (3)
Rozwiązanie początkowe Podaż
10 10 0 0
*
15
0 5 20
0 0 30
0 5 0 45 Zapotrzebowanie
Macierz kosztów jednostkowych
* *
1 4 7
3 5 11
*
6 7 9
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
17
Metoda minimalnego elementu macierzy kosztów (4)
Metoda minimalnego elementu macierzy kosztów (4)
Rozwiązanie początkowe Podaż
10 10 0 0
0 5 15
0
*
0 0 30 30
0 0 45 15 Zapotrzebowanie
Macierz kosztów jednostkowych
* *
1 4 7
3 5 11
*
6 7 9
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
18
Metoda minimalnego elementu macierzy kosztów (5)
Metoda minimalnego elementu macierzy kosztów (5)
Rozwiązanie początkowe Podaż
10 10 0 0
*
0
0 5 15 15
0 0 30 0
0
0 0 15 Zapotrzebowanie
Macierz kosztów jednostkowych
* *
1 4 7
3 5 11
* *
6 7 9
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
19
Metoda minimalnego elementu macierzy kosztów (6)
Metoda minimalnego elementu macierzy kosztów (6)
Rozwiązanie początkowe Podaż
10 10 0 0
* *
0 5 15 0
* *
0 0 30 0
*
0 0 0 Zapotrzebowanie
Macierz kosztów jednostkowych
* *
1 4 7
3 5 11
* *
6 7 9
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
20
Metoda VAM (1)
Metoda VAM (1)
Rozwiązanie początkowe Podaż
10 20
*
10
0 20
0 30
10 15 45 Zapotrzebowanie
0
Różnice w wierszach
Macierz kosztów jednostkowych
1 4 7 3
*
3 5 11 2
6 7 9 1
Różnice w kolumnach
2 1 2
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
21
Metoda VAM (2)
Metoda VAM (2)
Rozwiązanie początkowe Podaż
10 0 10
5
0 15 20
*
0 0 30
0 15 45 Zapotrzebowanie
0
Różnice w wierszach
Macierz kosztów jednostkowych
1 4 7 3
*
3 5 11 6
*
6 7 9 2
Różnice w kolumnach
- 1 2
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
22
Metoda VAM (3)
Metoda VAM (3)
Rozwiązanie początkowe Podaż
0
10 0 10 10
*
0
0 15 5 5
*
0
0 0 30 30
*
0 0 45 Zapotrzebowanie
0
Różnice w wierszach
Macierz kosztów jednostkowych
1 4 7 -
*
*
3 5 11 -
* *
6 7 9 -
*
Różnice w kolumnach
- - -
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
23
Algorytm metody potencjałów
Algorytm metody potencjałów
1. Znalez
ć pierwsze, dopuszczalne rozwiązanie bazowe.
1.
2. Ocenić, czy jest ono optymalne, czy też nie.
2.
3. Jeżeli nie jest optymalne, wyznaczyć nowe sąsiednie rozwiązanie
3.
bazowe. W tym celu należy:
- wybrać zmienną wchodzącą do bazy,
- wybrać zmienną usuwaną z bazy,
- znalez
ć rozwiązanie bazowe odpowiadające bazie
sÄ…siedniej
4. Jeżeli otrzymane rozwiązanie jest optymalne, zakończyć
4.
postępowanie.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
24
Wskaz
niki optymalności (1)
Wskaz
niki optymalności (1)
Konstrukcja układu równań
Konstrukcja układu równań
RozwiÄ…zanie poczÄ…tkowe
Podaż
(metoda minimalnego elementu)
10 * 10 * 0 0
0 5 15 0
* *
0 0 30 0
*
0 0 0 Zapotrzebowanie
Ponieważ x11 > 0, więc u1 + v1 + 1 = 0
Ponieważ x12 > 0, więc u1 + v2 + 4 = 0
u1 = a, v1 =  1 a
u2 =  1 + a, v2 =  4  a
Ponieważ x22 > 0, więc u2 + v2 + 5 = 0
u3 = 1 + a, v3 =  10  a
Ponieważ x23 > 0, więc u2 + v3 + 11 = 0
Ponieważ x33 > 0, więc u3 + v3 + 9 = 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
25
Wskaz
niki optymalności (2)
Wskaz
niki optymalności (2)
c ij = ui + vj + cij
u1 = a, v1 =  1 a
4 4 7
îÅ‚ Å‚Å‚
ïÅ‚ śł
u2 =  1 + a, v2 =  4  a
C = 3 5 11
ïÅ‚ śł
u3 = 1 + a, v3 =  10  a
ïÅ‚ śł
6 7 9
ðÅ‚ ûÅ‚
c 11 = u1 + v1 + 1 = a + ( 1  a) + 1 = 0
c 12 = u1 + v2 + 4 = a + ( 4  a) + 4 = 0
c 13 = u1 + v3 + 7 = a + ( 10  a) + 7 =  3
0 0 - 3
îÅ‚ Å‚Å‚
c 21 = u2 + v1 + 3 = ( 1 + a) + ( 1  a) + 3 = 1
ïÅ‚ śł
C' = 1 0 0
ïÅ‚ śł
c 22 = u2 + v2 + 5 = ( 1 + a) + ( 4  a) + 5 = 0
ïÅ‚ śł
6 4 0
ðÅ‚ ûÅ‚
c 23 = u2 + v3 + 11= ( 1 + a) + ( 10  a) + 11 = 0
c 31 = u3 + v1 + 6 = (1 + a) + ( 1  a) + 6 = 6
c 32 = u3 + v2 + 7 = (1 + a) + ( 4  a) + 7 = 4
c 33 = u3 + v3 + 9 = (1 + a) + ( 10  a) + 9 = 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
26
Kryterium optymalności
Kryterium optymalności
Jeżeli wartości wszystkich wskaz
ników optymalności są
dodatnie lub równe zeru, wtedy rozpatrywane rozwiązanie jest
optymalne. Jeżeli choć jeden ze wskaz
ników optymalności
jest ujemny, wtedy istnieje możliwość poprawy tego
rozwiÄ…zania.
0 0 - 3
îÅ‚ Å‚Å‚
Istnieje możliwość poprawy
ïÅ‚ śł
C' = 1 0 0
ïÅ‚ śł
rozwiÄ…zania poczÄ…tkowego.
ïÅ‚ śł
6 4 0
ðÅ‚ ûÅ‚
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
27
Kryterium wejścia
Kryterium wejścia
W macierzy wskaz
ników optymalności
znajdujemy element najmniejszy. OdpowiadajÄ…ca
mu zmiennÄ… wprowadzamy do nowej bazy.
0 0 - 3
îÅ‚ Å‚Å‚
Do bazy wprowadzamy
ïÅ‚ śł
C' = 1 0 0
ïÅ‚ śł
zmiennÄ… x13.
ïÅ‚ śł
6 4 0
ðÅ‚ ûÅ‚
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
28
Kryterium wyjścia
Kryterium wyjścia

10 10 0 10 9 1
+
0 5 15 0 6 14 
+
0 0 45 0 0 45
Półcykl dodatni: węzły (2, 2), (1, 3)
Półcykl ujemni: węzły (1, 2), (2, 3)
Bazę opuszcza ta zmienna należąca do półcyklu
ujemnego, dla której wielkość przewozu w
dotychczasowym rozwiÄ…zaniu jest minimalna.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
29
Przejście do rozwiązania bazowego sąsiedniego
Przejście do rozwiązania bazowego sąsiedniego
RozwiÄ…zanie poczÄ…tkowe
(metoda minimalnego elementu)
Wartość
funkcji celu
10 10 0+
10 0
0 5+ 15 510
5 15
510
0 0 30
Nowe rozwiÄ…zanie dopuszczalne
(iteracja 1)
Wartość
funkcji celu
10 0 10
* *
0 15 5 480
480
* *
*
*
0 0 30
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
30
Przebieg obliczeń (1)
Przebieg obliczeń (1)
Iteracja 2
Iteracja 2
Macierz wskaz
ników optymalności
0 0  3
* *
1 0 0
* *
6 4 0
*
Układ równań: Rozwiązanie:
u1 + v1 = 0
u1 = 0, v1 = 0,
u1 + v3  3 = 0
u2 =  3, v2 = 3,
u2 + v2 = 0
u3 =  3, v3 = 3.
u2 + v3 = 0
u3 + v3 = 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
31
Przebieg obliczeń (2)
Przebieg obliczeń (2)
Iteracja 2 (c.d.)
Iteracja 2 (c.d.)
Dotychczasowa macierz wskaz
ników
ui
optymalności
0 0  3 0
* *
1 0 0  3
* *
6 4 0  3
*
0 3 3 vj
Nowa macierz wskaz
ników optymalności
* *
0 3 0
 2 0 * 0 *
3 4 0
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
32
Przebieg obliczeń (3)
Przebieg obliczeń (3)
Iteracja 2 (c.d.)
Iteracja 2 (c.d.)
Rozwiązanie dopuszczalne Podaż
10 0 10+ 20
0+ 15 5 20
0 0 30 30
10 15 45 Popyt
Macierz wskaz
ników optymalności
* *
0 3 0
 2 0 * 0 *
3 4 0
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
33
Przebieg obliczeń (4)
Przebieg obliczeń (4)
Iteracja 2 (c.d.)
Iteracja 2 (c.d.)
Dotychczasowe
Podaż
rozwiÄ…zanie dopuszczalne
10 10+
10 0 10+ 20
0+ 15 5 20
0+ 5
0 0 30 30
10 15 45 Popyt
Nowe rozwiÄ…zanie dopuszczalne
Wartość funkcji
* *
5 0 15
celu (iteracja 2)
5 * 15 * 0
470
470
0 0 30
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
34
Przebieg obliczeń (5)
Przebieg obliczeń (5)
Iteracja 3
Iteracja 3
Macierz wskaz
ników optymalności
0 3 0
* *
 2* 0 * 0
3 4 0
*
Układ równań Rozwiązanie:
Układ równań Rozwiązanie:
u1 = 0, v1 = 0,
u1 + v1 = 0
u2 = 2, v2 =  2,
u1 + v3 = 0
u3 = 0, v3 = 0.
u2 + v1  2 = 0
u2 + v2 = 0
u3 + v3 = 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
35
Przebieg obliczeń (6)
Przebieg obliczeń (6)
Iteracja 3 (c.d.)
Iteracja 3 (c.d.)
Dotychczasowa macierz wskaz
ników
ui
optymalności
0 3 0 0
* *
 2 0 0 2
* *
3 4 0 0
*
0  2 0 vj
Nowa macierz wskaz
ników optymalności
* *
0 1 0
0 * 0 * 2
3 2 0
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
36
Bilansowanie zadania transportowego (1)
Bilansowanie zadania transportowego (1)
m n
"a > "b
i j
i=1 j=1
Przykład 3.2
Przykład 3.2
a1 = 25, a2 = 20, a3 = 30
b1 = 10, b2 = 15, b3 = 45
1 4 7
îÅ‚ Å‚Å‚
ïÅ‚3 5 11śł
C =
ïÅ‚ śł
ïÅ‚
ðÅ‚6 7 9 śł
ûÅ‚
b4 = (a1 + a2 + a3)  (b1 + b2 + b3) = (25 + 20 + 30)  (10 + 15 + 45) = 5
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
37
Bilansowanie zadania transportowego (2)
Bilansowanie zadania transportowego (2)
RozwiÄ…zanie poczÄ…tkowe
RozwiÄ…zanie poczÄ…tkowe
RozwiÄ…zanie poczÄ…tkowe
Podaż
(metoda minimalnego elementu)
10 * 10 * 0 5 25
*
0 5 15 0 20
* *
0 0 30 0 30
*
10 15 45 5 Zapotrzebowanie
Macierz kosztów jednostkowych
Wartość
1 4 7 0
funkcji celu
3 5 11 0
510
510
6 7 9 0
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x11 = 10 x12 = 0 x13 = 15 x14 = 0
x21 = 0 x22 = 15 x23 = 0 x24 = 5
x31 = 0 x32 = 0 x33 = 30 x34 = 0
Optymalna wartość funkcji celu jest równa 460.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
38
Bilansowanie zadania transportowego (3)
Bilansowanie zadania transportowego (3)
m n
"a < "b
i j
i=1 j=1
Przykład 3.3
Przykład 3.3
a1 = 20, a2 = 20, a3 = 30
b1 = 10, b2 = 15, b3 = 50
1 4 7
îÅ‚ Å‚Å‚
ïÅ‚3 5 11śł
C =
ïÅ‚ śł
ïÅ‚
ðÅ‚6 7 9 śł
ûÅ‚
a4 = (b1 + b2 + b3)  (a1 + a2 + a3) = (10 + 15 + 50)  (20 + 20 + 30) = 5
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
39
Bilansowanie zadania transportowego (4)
Bilansowanie zadania transportowego (4)
RozwiÄ…zanie poczÄ…tkowe
RozwiÄ…zanie poczÄ…tkowe
RozwiÄ…zanie poczÄ…tkowe
Podaż
(metoda VAM)
10 0 10
20
* *
0 15 * 5
20
*
0 0 30
30
*
0 0 5 5
*
10 15 50 vj
Nowa macierz wskaz
ników optymalności
1 4 7
3 5 11
6 7 9
0 0 0
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x11 = 10 x12 = 0 x13 = 10
x21 = 0 x22 = 15 x23 = 5
x31 = 0 x32 = 0 x33 = 30
x11 = 0 x12 = 0 x13 = 5
Optymalna wartość funkcji celu jest równa 470.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
40
Degeneracja z zadaniu transportowym (1)
Degeneracja z zadaniu transportowym (1)
Przykład 3.4
Przykład 3.4
7 4 4
îÅ‚ Å‚Å‚
a1=10, a2=20, a3=30
ïÅ‚ śł
C = 3 6 1
ïÅ‚ śł
b1=10, b2=20, b3=30
ïÅ‚ śł
2 3 5
ðÅ‚ ûÅ‚
RozwiÄ…zanie poczÄ…tkowe
Podaż
(metoda kąta północno-zachodniego)
10 0 0 10 0
* *
0
0 20 0 20
* *
0
0
0 0 30 30
*
10 0 20 30 Zapotrzebowanie
0
0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
41
Degeneracja z zadaniu transportowym (2)
Degeneracja z zadaniu transportowym (2)
Dalsze rozwiÄ…zania poczÄ…tkowe
Dalsze rozwiÄ…zania poczÄ…tkowe
10 0 * 0 10 0 0
* *
0 20 0 0 20 0
* * *
0 0 30 0 0 30
* * * *
10 0 0
*
0 20 0
* * *
0 0 30
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
42
Przebieg obliczeń (1)
Przebieg obliczeń (1)
Iteracja 1
Iteracja 1
u1 + v1 + 7 = 0
u1 + v2 + 4 = 0
u1 = 0, v1 =  7
u2 + v2 + 6 = 0
u2 =  2, v2 =  4
u2 + v3 + 1 = 0
u3 =  6, v3 = 1
u3 + v3 + 5 = 0
Macierz kosztów jednostkowych
ui
7 4 4
0
3 6 1
 2
2 3 5
 6
 7  4 1 vj
Macierz wskaz
ników optymalności
0 0 5
 6 0 0
 11  7 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
43
Przebieg obliczeń (2)
Przebieg obliczeń (2)
Iteracja 1 (c.d.)
Iteracja 1 (c.d.)
RozwiÄ…zanie poczÄ…tkowe
PoczÄ…tkowa
wartość funkcji
10 0+ 0
10 0+
celu
0 20 0+
20 0+
340
340
0+ 30
0+ 0 30
Nowe rozwiÄ…zanie dopuszczalne
Wartość funkcji
*
0 10 0
celu (iteracja 1)
0 10 * 10
*
230
230
10 0 20
*
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
44
Przebieg obliczeń (3)
Przebieg obliczeń (3)
Iteracja 2
Iteracja 2
Dotychczasowa macierz wskaz
ników
ui
optymalności
0 0 5 0
* *
 6 0 0 0
* *
 11  7 0 0
*
11 0 0 vj
Nowa macierz wskaz
ników optymalności
*
11 0 5
5 0 * 0 *
0  7 0
* *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
45
Przebieg obliczeń (4)
Przebieg obliczeń (4)
Iteracja 2 (c.d.)
Iteracja 2 (c.d.)
RozwiÄ…zanie poczÄ…tkowe
PoczÄ…tkowa
wartość funkcji
0 10 0
celu
0 10 10+
10 10+
230
230
10 0+ 20
0+ 20
Nowe rozwiÄ…zanie dopuszczalne
Wartość funkcji
*
0 10 0
celu (iteracja 2)
0 0 20
*
160
160
10 10 * 10
*
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
46
Przebieg obliczeń (5)
Przebieg obliczeń (5)
Iteracja 3
Iteracja 3
Dotychczasowa macierz wskaz
ników
ui
optymalności
11 0 5 0
5 0 0 7
0  7 0 7
 7 0  7 vj
Nowa macierz wskaz
ników optymalności
*
4 0  2
5 7 0 *
0 0 0
* * *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
47
Przebieg obliczeń (6)
Przebieg obliczeń (6)
Iteracja 3 (c.d.)
Iteracja 3 (c.d.)
RozwiÄ…zanie poczÄ…tkowe
PoczÄ…tkowa
wartość funkcji
0 10 0+
10 0+
celu
0 0 20
160
160
10 10+ 10
10+ 10
Nowe rozwiÄ…zanie dopuszczalne
Wartość funkcji
*
0 0 20
celu (iteracja 3)
0 0 20
*
140
140
10 20 * 0
*
*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
48
Przebieg obliczeń (7)
Przebieg obliczeń (7)
Iteracja 4
Iteracja 4
Dotychczasowa macierz wskaz
ników
ui
optymalności
4 0  2 0
*
*
5 7 0  2
* * *
0 0 0  2
2 2 2 vj
Nowa macierz wskaz
ników optymalności
*
6 2 0
5 7 0 *
0 0 0
* * *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
49
Minimalizacja pustych przebiegów (1)
Minimalizacja pustych przebiegów (1)
Przykład 3.5
Przykład 3.5
Odległości między miastami:
1 2 3 4 5 6 7 8
1 0 315 250 190 320 80 380 345
2 0 130 400 305 320 170 440
3 0 240 245 295 315 385
4 0 165 270 520 155
5 0 400 480 140
6 0 315 480
7 0 615
8 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
50
Minimalizacja pustych przebiegów (2)
Minimalizacja pustych przebiegów (2)
Przykład 3.5 (c.d.)
Przykład 3.5 (c.d.)
Wywóz z miasta i
pi
1 2 3 4 5 6 7 8
1 0 21 18 19 16 17 10 9 110
2 14 0 12 15 9 11 6 4 71
3 18 9 0 13 11 12 5 6 74
4 13 8 9 0 7 14 3 7 61
5 16 18 10 8 0 6 2 8 68
6 18 19 6 11 9 0 6 2 71
7 8 7 6 4 3 9 0 2 39
8 4 3 6 10 3 4 2 0 32
wi 91 85 67 80 58 73 34 38
Znalez
ć plan przewozów minimalizujących puste przebiegi.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
51
Przywóz do miasta
i
Minimalizacja pustych przebiegów (3)
Minimalizacja pustych przebiegów (3)
Nadwyżka/niedobór samochodów w kolejnych miastach
Nadwyżka/niedobór samochodów w kolejnych miastach
pi 110 71 74 61 68 71 39 32
wi 91 85 67 80 58 73 34 38
wi 19  14 7  19 10  2 5  6
a1  nadwyżka samochodów w mieście 1 (dostawca pierwszy),
a2  nadwyżka samochodów w mieście 3 (dostawca drugi),
a3  nadwyżka samochodów w mieście 5, (dostawca trzeci),
a4  nadwyżka samochodów w mieście 7 (dostawca czwarty),
b1  niedobór samochodów w mieście 2 (odbiorca pierwszy),
b2  niedobór samochodów w mieście 4 (odbiorca drugi),
b3  niedobór samochodów w mieście 6 (odbiorca trzeci),
b4  niedobór samochodów w mieście 8 (odbiorca czwarty).
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
52
Minimalizacja pustych przebiegów (4)
Minimalizacja pustych przebiegów (4)
Podaż i popyt na puste samochody
Podaż i popyt na puste samochody
odbiorca
dostawca
b1 b2 b3 b4
a1 315 190 80 345
a2 130 240 295 385
a3 305 165 400 140
a4 170 520 315 615
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
53
Minimalizacja pustych przebiegów (5)
Minimalizacja pustych przebiegów (5)
Cel
Cel
określenie takiego planu przewozów, który minimalizuje łączną liczbę
samochodo kilometrówpustych przebiegów.
Zmienne decyzyjne
Zmienne decyzyjne
Liczba pustych przebiegów:
x11  z miasta 1 do miasta 2, x31  z miasta 3 do miasta 2,
x12  z miasta 1 do miasta 4, x32  z miasta 3 do miasta 4,
x13  z miasta 1 do miasta 6, x33  z miasta 3 do miasta 6,
x14  z miasta 1 do miasta 8, x34  z miasta 3 do miasta 8,
x21  z miasta 2 do miasta 2, x41  z miasta 4 do miasta 2,
x22  z miasta 2 do miasta 4, x42  z miasta 4 do miasta 4,
x23  z miasta 2 do miasta 6, x43  z miasta 4 do miasta 6,
x24  z miasta 2 do miasta 8, x44  z miasta 4 do miasta 8.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
54
Minimalizacja pustych przebiegów (6)
Minimalizacja pustych przebiegów (6)
Funkcja celu
Funkcja celu
f(x11, x12, x13 , x14, x21, x22, x23 , x24, x31, x32, x33 , x34, x41, x42, x43, x44 )=
= 315x11 + 190x12 + 80x13 + 345x14 +
+ 130x21 + 240x22 + 295x23 + 385x24 +
+ 305x31 + 165x32 + 400x33 + 140x34 +
+ 170x41 + 520x42 + 315x43 615x44 min
Ograniczenia
Ograniczenia
odbiorca 1 - x11 + x21 + x31 + x41 = 14
dostawca 1 - x11 + x12 + x13 + x14 = 19
dostawca 2 - x21 + x22 + x23 + x24 = 7 odbiorca 2 - x12 + x22 + x32 + x42 = 19
dostawca 3 - x31 + x32 + x33 + x34 = 10 odbiorca 3 - x13 + x23 + x33 + x43 = 2
dostawca 4 - x41 + x42 + x43 + x44 = 5 odbiorca 4 - x14 + x24 + x34 + x44 = 6
Warunki nieujemności
Warunki nieujemności
x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33,x34, x41, x42, x43, x44 e" 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
55
Minimalizacja pustych przebiegów (7)
Minimalizacja pustych przebiegów (7)
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x11 = 2 x12 = 15 x13 = 2 x14 =0
x21 = 7 x22 = 0 x23 = 0 x24 = 0
x31 = 0 x32 = 4 x33 = 0 x34 = 6
x41 = 5 x42 = 0 x43 = 0 x44 = 0
Optymalna wartość funkcji celu :
Optymalna wartość funkcji celu :
6900
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
56
Zadanie transportowo-produkcyjne (1)
Zadanie transportowo-produkcyjne (1)
Przykład 3.6
Przykład 3.6
Zdolności produkcyjne zakładów: 40, 50, 30
Zapotrzebowanie odbiorców: 45, 10, 30, 35
Jednostkowe koszty produkcji: 4, 3, 1
Jednostkowe koszty
Jednostkowe koszty transportu
produkcji i transportu
4 3 2 1
îÅ‚ Å‚Å‚
8 7 6 5
îÅ‚ Å‚Å‚
ïÅ‚ śł
ïÅ‚3 2 7 9śł
C =
J = 6 5 10 12śł
ïÅ‚
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
9 4 6 5
ðÅ‚ ûÅ‚
ðÅ‚8 3 5 4ûÅ‚
Znalez
ć taki plan produkcji, by zminimalizować łączne koszty produkcji i
transportu.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
57
Zadanie transportowo-produkcyjne (2)
Zadanie transportowo-produkcyjne (2)
Cel
Cel
Minimalizacja łącznych kosztów produkcji i transportu.
Zmienne decyzyjne
Zmienne decyzyjne
Ilość produktu wytworzona:
x11 - przez zakład 1 dla odbiorcy 1
x12 - przez zakład 1 dla odbiorcy 2
x13 - przez zakład 1 dla odbiorcy 3
x31 - przez zakład 3 dla odbiorcy 1
x14 - przez zakład 1 dla odbiorcy 4
x32 - przez zakład 3 dla odbiorcy 2
x33 - przez zakład 3 dla odbiorcy 3
x21 - przez zakład 2 dla odbiorcy 1
x34 - przez zakład 3 dla odbiorcy 4
x22 - przez zakład 2 dla odbiorcy 2
x23 - przez zakład 2 dla odbiorcy 3
x24 - przez zakład 2 dla odbiorcy 4
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
58
Zadanie transportowo-produkcyjne (3)
Zadanie transportowo-produkcyjne (3)
Funkcja celu
Funkcja celu
f(x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34) =
= 8x11 + 7x12 + 6x13 + 5x14 +
+ 6x21 + 4x22 + 10x23 + 12x24 +
+ 9x31 + 4x32 + 10x33 + 12x34 min
Ograniczenia
Ograniczenia
odbiorca 1 - x11 + x21 + x31 + x41 = 45
zakład 1 - x11 + x12 + x13 + x14 = 40
zakład 2 - x21 + x22 + x23 + x24 = 50 odbiorca 2 - x12 + x22 + x32 + x42 = 10
zakład 3 - x31 + x32 + x33 + x34 = 30 odbiorca 3 - x13 + x23 + x33 + x43 = 30
odbiorca 4 - x14 + x24 + x34 + x44 = 35
Warunki nieujemności
Warunki nieujemności
x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33,x34, x41, x42, x43, x44 e" 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
59
Zadanie transportowo-produkcyjne (4)
Zadanie transportowo-produkcyjne (4)
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x11 = 0 x12 = 0 x13 = 30 x14 = 10
x21 = 45 x22 = 5 x23 = 0 x24 = 0
x31 = 0 x32 = 5 x33 = 0 x34 = 25
Optymalna wartość funkcji celu jest równa
Optymalna wartość funkcji celu jest równa
665
Plan przewozów
Produkcja
odbiorca 1 odbiorca 2 odbiorca 3 odbiorca 4
0 0 30 10 zakład 1 40
45 5 0 0 zakład 2 50
0 5 0 25 zakład 3 30
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
60
Zadanie przydziału (1)
Zadanie przydziału (1)
Przykład 3.7
Przykład 3.7
Czas pracy doradców firmy consultingowej :
X - 140 godz., Y - 140 godz., Z - 120 godz.
Wymagania czasowe nowych kontraktów:
Klient Liczba godzin
A 165
B 50
C 80
D 70
Stawki godzinowe:
Doradca Klient A Klient B Klient C Klient D
X 9 11,5 12 10
Y 11 13 11,5 12
Z 15 14,5 14 13
W jaki sposób przydzielić doradcom kontrakty tak, by łączny koszt ich realizacji
był najmniejszy?
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
61
Zadanie przydziału (2)
Zadanie przydziału (2)
Cel
Cel
Minimalizacja kosztów wynagrodzenia doradców.
Zmienne decyzyjne
Zmienne decyzyjne
Liczba godzin pracy:
x11 - doradcy X dla klienta A,
x12 - doradcy X dla klienta B,
x13 - doradcy X dla klienta C,
x31 - doradcy Z dla klienta A,
x14 - doradcy X dla klienta D,
x32 - doradcy Z dla klienta B,
x33 - doradcy Z dla klienta C,
x34 - doradcy Z dla klienta D.
x21 - doradcy Y dla klienta A,
x22 - doradcy Y dla klienta B,
x23 - doradcy Y dla klienta C,
x24 - doradcy Y dla klienta D,
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
62
Zadanie przydziału (3)
Zadanie przydziału (3)
Funkcja celu
Funkcja celu
f(x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34) =
= 90x11 + 115x12 + 120x13 + 100x14 +
+ 110x21 + 130x22 + 115x23 + 120x24 +
+ 150x31 + 145x32 + 140x33 + 130x34 min
Ograniczenia
Ograniczenia
dla klienta A - x11 + x21 + x31 = 165
dla doradcy X - x11 + x12 + x13 + x14 d" 140
dla klienta B - x12 + x22 + x32 = 50
dla doradcy Y - x21 + x22 + x23 + x24 d" 140
dla klienta C - x13 + x23 + x33 = 80
dla doradcy Z - x31 + x32 + x33 + x34 d" 120
dla klienta D - x14 + x24 + x34 = 70
Warunki nieujemności dla zmiennych decyzyjnych
Warunki nieujemności dla zmiennych decyzyjnych
x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33,x34 e" 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
63
Zadanie przydziału (4)
Zadanie przydziału (4)
Fikcyjny klient (odbiorca E)
Fikcyjny klient (odbiorca E)
Dodatkowe zmienne decyzyjne
Dodatkowe zmienne decyzyjne
x15 - liczba godzin pracy doradcy X dla klienta E,
x25 - liczba godzin pracy doradcy Y dla klienta E,
x35 - liczba godzin pracy doradcy X dla klienta E,
Dodatkowe ograniczenie dla klienta E
Dodatkowe ograniczenie dla klienta E
x15 + x25 + x35 = 35
Dodatkowe warunki nieujemności:
Dodatkowe warunki nieujemności:
x15, x25, x35 e" 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
64
Zadanie przydziału (5)
Zadanie przydziału (5)
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x11 = 140 x12 = 0 x13 = 0 x14 =0 x15 = 0
x21 = 25 x22 = 35 x23 = 80 x24 = 0 x25 = 0
x31 = 0 x32 = 15 x33 = 0 x34 = 70 x35 = 35
Optymalna wartość funkcji celu jest równa 40 375
Optymalna wartość funkcji celu jest równa
Doradca Klient A Klient B Klient C Klient D
X 140 0 0 0
Y 25 35 80 0
Z 0 15 0 70
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/
65
Podsumowanie
Podsumowanie
SÅ‚owa kluczowe
Zbilansowane zadanie transportowe
RozwiÄ…zanie poczÄ…tkowe
Metoda minimalnego elementu macierzy
Metoda VAM
Metoda kąta północno-zachodniego
Metoda potencjałów
Bilansowanie zadania niezbilansowanego
Sztuczny dostawca
Sztuczny odbiorca
Degeneracja w zadaniu transportowym
Pora na relaks
Pora na relaks
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3/ 66