ZADANIE TRANSPORTOWE I PROBLEM KOMIWOJAŻERA Tadeusz Trzaskalik Wprowadzenie do badań operacyjnych z komputerem 3.Zadanietransportoweiproblemkomiwojaże...
8 downloads
34 Views
510KB Size
ZADANIE TRANSPORTOWE I PROBLEM KOMIWOJAŻERA
Tadeusz Trzaskalik Wprowadzenie do badań operacyjnych z komputerem
3. Zadanie transportowe i problem komiwojażera
3.1. Wprowadzenie
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 Problem komiwojażera Algorytm genetyczny T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
2
3. Zadanie transportowe i problem komiwojażera
3.1. Wprowadzenie
Zadanie transportowe
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 znaleźć taki plan przewozów, który minimalizuje łączny ich koszt
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3
3. Zadanie transportowe i problem komiwojażera
3.1. Wprowadzenie
Problem komiwojażera
Mamy n miast, które należy odwiedzić w dowolnej kolejności, rozpoczynając podróż z miasta o numerze 1 i wracając do niego, przy czym każde z miast można odwiedzić dokładnie jeden raz. Znając wszystkie odległości miedzy miastami należy znaleźć trasę przejazdu o minimalnej długości.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
4
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.1. Zadanie transportowe w ujęciu programowania liniowego (1/3) Przykład 3.1
Miejscowość
O1
O2
O3
D1
1
4
7
D2
3
5
11
D3
6
7
9
1
20
D1 3
20
D2
5
11 6
30
4 7
D3 9
O1
10
O2
15
O3
45
7
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
5
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.1. Zadanie transportowe w ujęciu programowania liniowego (2/3) Model matematyczny
Cel Określenie planu przewozów, który minimalizuje łączny koszt. 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
6
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.1. Zadanie transportowe w ujęciu programowania liniowego (3/3) Model matematyczny (c.d.)
Funkcja celu f (x11, x12, x13, x21, x22, x23, x31,x32, x33) = x11 +4x12 +7x13 + +3x21 +5x22 +11x23 +6x31 +7x32 +9x33 ® min
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 ³ 0
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
7
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.2. Zadanie dualne do zadania transportowego (1/7) Postać macierzowa zadania prymalnego c - wektor funkcji celu,
cx ® min Ax = b x³0
A - macierz współczynników, b - wektor warunków ograniczających,
cx ® max Ax = b Þ x³0 przy czym c = -c
x - wektor zmiennych. c = [1 4 7 3 5 11 6 7 9] é1 ê0 ê ê0 A= ê 1 ê ê0 ê0 ë
1 0 0 0
1 0 0 0
0 1 0 1
0 1 0 0
0 1 0 0
0 0 1 1
0 0 1 0
0ù 0ú ú 1ú 0ú ú 1 0 0 1 0 0 1 0ú 0 1 0 0 1 0 0 1úû
é20ù ê20ú ê ú ê30ú b=ê ú 10 ê ú ê15 ú ê 45ú ë û
é x11 ù êx ú ê 12 ú ê x13 ú êx ú ê 21 ú x = ê x22 ú êx ú ê 23 ú ê x31 ú ê ú ê x32 ú êë x33 úû
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
8
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.2. Zadanie dualne do zadania transportowego (2/7) Zasady tworzenia zadania dualnego
Zadanie prymalne (ZP)
Zadanie dualne (ZD)
c x ® max Ax = b x³0
yb ® min yA ³ c 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 u 2
u3 ]
y = [u1 u2
v = [v1 v2 u3
v1
v2
v3 ]
v3 ]
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
9
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.2. Zadanie dualne do zadania transportowego (3/7) Postać zadania dualnego
yb = [u1
v3 ]
é20ù = 20u1 + 20u2 + 30u3 + 10v1 + 15v2 + 45v3 ® min ê20ú ê30ú ê10 ú ê15 ú êë45ûú é - 1ù ê - 4ú [ ] = u u u v v v 1 1 1 0 0 0 0 0 0 ù yA 1 2 3 1 2 3 é ê - 7ú ê0 0 0 1 1 1 0 0 0ú ê - 3ú 0 0 0 0 0 0 1 1 1 ê ú ³ ê - 5ú =c ê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úû u2
u3
v1 v2
u1 + v1 ³ -1
u1 + v2 ³ -4
u1 + v3 ³ -7
u2 + v1 ³ -3
u2 + v2 ³ -5
u2 + v3 ³ -11
u3 + v1 ³ -6
u3 + v2 ³ -7
u3 + v3 ³ -9
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
10
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.2. Zadanie dualne do zadania transportowego (4/7) Zadanie prymalne i dualne – zestawienie
Zadanie prymalne –x11 – 4x12 –7x13 –3x21 –5x22 –11x23 –6x31 –7x32 –9x33 ® max 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 ³ 0
Zadanie dualne 20u1 + 20u2 + 30u3 + 10v1 + 15v2 + 45v3 ® min u1 + v1 + 1 ³ 0 u2 + v1 + 3 ³ 0 u3 + v1 + 6 ³ 0
u1 + v2 + 4 ³ 0 u2 + v2 + 5 ³ 0 u3 + v2 + 7 ³ 0 u1, u2, u3, v1, v2, v3 - dowolne
u1 + v3 + 7 ³ 0 u2 + v3 + 11 ³ 0 u3 + v3 + 9 ³ 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
11
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.2. Zadanie dualne do zadania transportowego (5/7) Zależności między zmiennymi i warunkami ograniczającymi
x11 odpowiada warunkowi u1 + v1 + 1 ³ 0 x12 odpowiada warunkowi u1 + v2 + 4 ³ 0 x13 odpowiada warunkowi u1 + v3 + 7 ³ 0 x21 odpowiada warunkowi u2 + v1 + 3 ³ 0 x22 odpowiada warunkowi u2 + v2 + 5 ³ 0 x23 odpowiada warunkowi u2 + v3 + 11 ³ 0 x31 odpowiada warunkowi u3 + v1 + 6 ³ 0 x32 odpowiada warunkowi u3 + v2 + 7 ³ 0 x33 odpowiada warunkowi u3 + v3 + 9 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
12
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.2. Zadanie dualne do zadania transportowego (6/7) Twierdzenie o komplementarności
(yA - c) = 0 czyli:
([u, v] A - c) x = 0 stąd: (u1 + v1 + 1) x11 = 0 (u2 + v1 + 3) x21 = 0 (u3 + v1 + 6) x31 = 0
(u1 + v2 + 4) x12 = 0 (u2 + v2 + 5) x22 = 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
13
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.2. Zadanie dualne do zadania transportowego (7/7) 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
14
3.2. Zadanie transportowe i jego własności
3. Zadanie transportowe i problem komiwojażera
3.2.3. Sformułowanie zadania transportowego (1/1) Zbilansowane zadanie transportowe
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 =1
i
j =1
j
Sformułowanie zadania m
n
åå c x i =1 j =1
n
ij ij
® min
åx
ij
= ai
dla i = 1,...,m
åx
ij
= bj
dla j = 1,...,n
j =1 m
i =1
xij ³ 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
15
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.1. Metoda minimalnego elementu macierzy kosztów (1/7) Definicje
Macierz przewozów
é_ X = êê _ êë _
_ _ _
Macierz kosztów
_ù _ úú _ úû
é1 C = êê 3 êë 6
4 5 7
7ù 11 úú 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
Wielkość przewozu
xij = min (ai ,bj)
Podaż i popyt po modyfikacji a’i = ai – xij b’j = bj – xij T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
16
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.1. Metoda minimalnego elementu macierzy kosztów (2/7) Przebieg obliczeń
Rozwiązanie początkowe
Podaż
10 *
20 10
0
20
0 10 0
30 15
45
Zapotrzebowanie
Macierz kosztów jednostkowych 1*
4
7
3
5
11
6
7
9
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
17
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.1. Metoda minimalnego elementu macierzy kosztów (3/7) Przebieg obliczeń (c.d.)
Rozwiązanie początkowe 10 *
10
Podaż 0
0 0
10
0
20 30 15 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
18
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.1. Metoda minimalnego elementu macierzy kosztów (4/7) Przebieg obliczeń (c.d.)
Rozwiązanie początkowe
Podaż
10
10
0
0
5*
20 15
0
0
30
0
5 0
45
0
Zapotrzebowanie
Macierz kosztów jednostkowych 1*
4*
7
3
5*
11
6
7
9
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
19
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.1. Metoda minimalnego elementu macierzy kosztów (5/7) Przebieg obliczeń (c.d.)
Rozwiązanie początkowe
Podaż
10
10
0
0
5
0
0
30 *
0
0
45 15
0 15 30 0 Zapotrzebowanie
Macierz kosztów jednostkowych 1*
4*
7
3
5*
11
6
7
9*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
20
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.1. Metoda minimalnego elementu macierzy kosztów (6/7) Przebieg obliczeń (c.d.)
Rozwiązanie początkowe
Podaż
10
10
0
0
0
5
15 *
15 0
0
0
30
0
0
0
15 0
Zapotrzebowanie
Macierz kosztów jednostkowych 1*
4*
7
3
5*
11 *
6
7
9*
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
21
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.1. Metoda minimalnego elementu macierzy kosztów (7/7) Przebieg obliczeń (c.d.)
Rozwiązanie początkowe 10 * 0
10 * 5 *
0 0
Podaż 0
0 0
0
15 * 30 *
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
22
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.2. Metoda VAM (1/3) Przebieg obliczeń
Rozwiązanie początkowe
Podaż
10 * 0
20 10 20
0
30
10 0
15
45
Macierz kosztów jednostkowych
Zapotrzebowanie Różnice w wierszach
1 *
4
7
3
3
5
11
2
6
7
9
1
2
1
2
Różnice w kolumnach
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
23
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.2. Metoda VAM (2/3) Przebieg obliczeń (c.d.)
Rozwiązanie początkowe
Podaż
10
0
10
0
20
0
15 * 0
0
15 0
5
30 45
Macierz kosztów jednostkowych
Zapotrzebowanie Różnice w wierszach
1 *
4
7
3
3
5 *
11
6
6
7
9
2
-
1
2
Różnice w kolumnach
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
24
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.2. Metoda VAM (3/3) Przebieg obliczeń (c.d.)
Rozwiązanie początkowe
Podaż
10
0
10 *
0
15
0
0
5* 30 *
0
0
45 0
Macierz kosztów jednostkowych 1 *
4
3
5 *
6
7
-
-
10 0 5 0 30 0 Zapotrzebowanie Różnice w wierszach
7 * 11 *
-
9 * -
-
Różnice w kolumnach
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
25
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3. Zadanie transportowe i problem komiwojażera
3.3.3. Metoda kąta północno-zachodniego (1/1) Przebieg obliczeń
Rozwiązanie początkowe (metoda kąta północno-zachodniego) 10 * 10 * 0
Podaż 0
0
5 *
15 *
0
0
0
30 *
0
0
0
0
Zapotrzebowanie
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
26
3. Zadanie transportowe i problem komiwojażera
3.4. Metoda potencjałów
Szkic algorytmu
1. Znaleźć pierwsze, dopuszczalne rozwiązanie bazowe. 2. Ocenić, czy jest ono optymalne, czy też nie. 3. Jeżeli nie jest optymalne, wyznaczyć nowe sąsiednie rozwiązanie bazowe. W tym celu należy: - wybrać zmienną wchodzącą do bazy, - wybrać zmienną usuwaną z bazy, - znaleźć rozwiązanie bazowe odpowiadające bazie sąsiedniej 4. Jeżeli otrzymane rozwiązanie jest optymalne, zakończyć postępowanie. T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
27
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.1. Badanie optymalności rozwiązania (1/3) Konstrukcja układu równań Rozwiązanie początkowe (metoda minimalnego elementu) 10 * 10 * 0
Podaż 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 Ponieważ x22 > 0, więc u2 + v2 + 5 = 0 Ponieważ x23 > 0, więc u2 + v3 + 11 = 0
u1 = a, v1 = –1– a u2 = –1 + a, v2 = –4 – a u3 = 1 + a, v3 = –10 – a
Ponieważ x33 > 0, więc u3 + v3 + 9 = 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
28
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.1. Badanie optymalności rozwiązania (2/3) Wskaźniki optymalności
c’ij = ui + vj + cij é4 C = êê 3 êë 6
4 5 7
7 ù 11 úú 9 úû
u1 = a, v1 = –1– a u2 = –1 + a, v2 = –4 – a u3 = 1 + a, v3 = –10 – a
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 c’21 = u2 + v1 + 3 = (–1 + a) + (–1 – a) + 3 = 1 c’22 = u2 + v2 + 5 = (–1 + a) + (–4 – a) + 5 = 0 c’23 = u2 + v3 + 11= (–1 + a) + (–10 – a) + 11 = 0
é0 C' = êê 1 êë 6
0 0 4
- 3ù 0 úú 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
29
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.1. Badanie optymalności rozwiązania (3/3) Kryterium optymalności
Jeżeli wartości wszystkich wskaźników optymalności są dodatnie lub równe zeru, wtedy rozpatrywane rozwiązanie jest optymalne. Jeżeli choć jeden ze wskaźników optymalności jest ujemny, wtedy istnieje możliwość poprawy tego rozwiązania.
é0 C' = êê 1 êë 6
0 0 4
- 3ù 0 úú 0 úû
Istnieje możliwość poprawy rozwiązania początkowego.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
30
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.2. Wybór zmiennej wprowadzanej do bazy (1/1) Kryterium wejścia
W macierzy wskaźników optymalności znajdujemy element najmniejszy. Odpowiadająca mu zmienną wprowadzamy do nowej bazy.
é0 C' = êê 1 êë 6
0 0 4
- 3ù 0 úú 0 úû
Do bazy wprowadzamy zmienną x13.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
31
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.3. Wybór zmiennej opuszczającej bazę (1/1) Kryterium wyjścia 9
0
– 6 +
+ 14 –
0
0
45
10
10
0
10
0
5
15
0
0
45
Półcykl dodatni:
węzły (2, 2), (1, 3)
Półcykl ujemny:
węzły (1, 2), (2, 3)
1
Bazę Bazęopuszcza opuszczatatazmienna zmiennanależąca należącado dopółcyklu półcyklu ujemnego, ujemnego,dla dlaktórej którejwielkość wielkośćprzewozu przewozuww dotychczasowym dotychczasowymrozwiązaniu rozwiązaniujest jestminimalna. minimalna.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
32
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.4. Przejście do rozwiązania bazowego sąsiedniego (1/1) Wyznaczenie cyklu
Rozwiązanie początkowe (metoda minimalnego elementu) 10
10 10–
00+
Wartość funkcji celu
0
55+
15 15–
510
0
0
30
Nowe rozwiązanie dopuszczalne (iteracja 1) 10 * 0 0
0 15 * 0
10 * 5 *
Wartość funkcji celu 480
30 * *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
33
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.5. Kolejne iteracje (1/6) Iteracja 2
Macierz wskaźników optymalności 0* 0 –3 * 1 0 * 0 * 6 4 0 * Układ równań: u 1 + v1 = 0 u 1 + v3 – 3 = 0 u 2 + v2 = 0 u 2 + v3 = 0 u 3 + v3 = 0
Rozwiązanie: u1 = 0, v1 = 0, u2 = – 3, v2 = 3, u3 = –3, v3 = 3.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
34
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.5. Kolejne iteracje (2/6) Iteracja 2 (c.d.)
Dotychczasowa macierz wskaźników optymalności
ui
0 *
0 *
–3
0
1
0 *
0 *
–3
6
4
–3
0
3
0 * 3
vj
Nowa macierz wskaźników optymalności 0 *
3
0 *
–2
0 *
0 *
3
4
0 *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
35
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.5. Kolejne iteracje (3/6) 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 wskaźników optymalności 0 *
3
0 *
–2
0 *
0 *
3
4
0 *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
36
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.5. Kolejne iteracje (4/6) Iteracja 2 (c.d.)
Dotychczasowe rozwiązanie dopuszczalne
Podaż
10–
0
10+
20
0+
15
5–
20
0
0
30
30
10
15
45
Popyt
Nowe rozwiązanie dopuszczalne 5 *
0
15 *
5 *
15 *
0
0
0
30 *
Wartość funkcji celu (iteracja 2) 470
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
37
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.5. Kolejne iteracje (5/6) Iteracja 3
Macierz wskaźników optymalności 0* –2 *
3 0 *
0 * 0
3
4
0 *
Układ równań u1 + v1 = 0 u1 + v3 = 0 u2 + v1 – 2 = 0 u2 + v2 = 0 u3 + v3 = 0
Rozwiązanie: u1 = 0, u2 = 2, u3 = 0,
v1 = 0, v2 = –2, v3 = 0.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
38
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.5. Kolejne iteracje (6/6) Iteracja 3 (c.d.)
Dotychczasowa macierz wskaźników optymalności
ui
0 *
3
0 *
0
–2
0 *
0 *
2
3
4
0
0
–2
0 * 0
vj
Nowa macierz wskaźników optymalności 0 *
1
0 *
0 *
0 *
2
3
2
0 *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
39
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (1/9) Przykład 3.2
a1=10, a2=20, a3=30 b1=10, b2=20, b3=30
é7 C = êê 3 êë 2
Rozwiązanie początkowe (metoda kąta północno-zachodniego)
4 6 3
4ù 1 úú 5 úû Podaż
10 *
0 *
0
10 0
0
20 *
0 *
20 0
0
0
30 *
30 0
10 0
20 0
30 0
Zapotrzebowanie
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
40
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (2/9) 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
41
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (3/9) Iteracja 1
u 1 + v1 + 7 = 0 u 1 + v2 + 4 = 0 u 2 + v2 + 6 = 0 u 2 + v3 + 1 = 0 u 3 + v3 + 5 = 0
u1 = 0, v1 = –7 u2 = –2, v2 = –4 u3 = –6, v3 = 1
Macierz kosztów jednostkowych
ui
7 4 4 3 6 1 2 3 5 –7 –4 1 Macierz wskaźników optymalności 0 0 5 –6 0 0 –11 –7 0
0 –2 –6 vj
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
42
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (4/9) Iteracja 1 (c.d.)
Rozwiązanie początkowe 10–
0+
0
0
20–
0+
0+
0
30–
Nowe rozwiązanie dopuszczalne 0
10 *
0
0
10 *
10 *
10 *
0
20 *
Początkowa wartość funkcji celu 340
Wartość funkcji celu (iteracja 1) 230
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
43
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (5/9) Iteracja 2
Dotychczasowa macierz wskaźników optymalności
ui
0 *
0 *
5
0
–6
0 *
0 *
0
–11
–7
0
11
0
0 * 0
vj
Nowa macierz wskaźników optymalności 11
0 *
5
5
0 *
0 *
0 *
–7
0 *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
44
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (6/9) Iteracja 2 (c.d.)
Rozwiązanie początkowe 0
10
0
0
10–
10+
10
0+
20–
Nowe rozwiązanie dopuszczalne 0
10 *
0
0
0
20 *
10 *
10 *
10 *
Początkowa wartość funkcji celu 230
Wartość funkcji celu (iteracja 2) 160
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
45
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (7/9) Iteracja 3
Dotychczasowa macierz wskaźników optymalności
ui
11
0
5
0
5
0
0
7
0
–7
0
7
–7
0
–7
vj
Nowa macierz wskaźników optymalności 4
0 *
–2
5
7
0 *
0 *
0 *
0 *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
46
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (8/9) Iteracja 3 (c.d.)
Rozwiązanie początkowe 0
10–
0+
0
0
20
10
10+
10–
Nowe rozwiązanie dopuszczalne 0
0
20 *
0
0
20 *
10 *
20 *
0 *
Początkowa wartość funkcji celu 160
Wartość funkcji celu (iteracja 3) 140
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
47
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.6. Degeneracja w zadaniu transportowym (9/9) Iteracja 4
Dotychczasowa macierz wskaźników optymalności
ui
4
0 *
–2
0
5
7
0 *
–2
0 *
0 *
0 *
–2
2
2
2
vj
Nowa macierz wskaźników optymalności 6
2
0 *
5
7
0 *
0 *
0 *
0 *
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
48
3.4. Metoda potencjałów
3. Zadanie transportowe i problem komiwojażera
3.4.7. Reguły postępowania w rozwiązywaniu zadania transportowego (1/1) Algorytm
1. 2. 3. 4. 5. 6. 7.
Uzyskanie pierwszego rozwiązania bazowego Wyznaczenie wskaźników optymalności Badanie optymalności rozwiązania Wybór zmiennej wprowadzanej do bazy Konstrukcja cyklu Wybór zmiennej opuszczającej bazę Przejście do rozwiązania bazowego sąsiedniego
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
49
3.5. Bilansowanie zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.5.1. Podaż przewyższa popyt (1/2) Fikcyjny odbiorca m
n
åa > åb i =1
i
j =1
j
a1 = 25, a2 = 20, a3 = 30 b1 = 10, b2 = 15, b3 = 45
é1 4 7 ù C = êê3 5 11úú êë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
50
3.5. Bilansowanie zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.5.1. Podaż przewyższa popyt (2/2) Fikcyjny odbiorca (c.d.) Rozwiązanie początkowe (metoda minimalnego elementu) 10 * 0 0 10 1 3 6
10 * 0 5 * 15 * 0 30 * 15 45 Macierz kosztów jednostkowych 4 7 5 11 7 9
5 * 0 0 5
Podaż 25 20 30 Zapotrzebowanie
0 0 0
Wartość funkcji celu 510
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
51
3.5. Bilansowanie zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.5.2. Popyt przewyższa podaż (1/2) Fikcyjny dostawca m
n
åa < åb i =1
i
j =1
j
a1 = 20, a2 = 20, a3 = 30 b1 = 10, b2 = 15, b3 = 50
é1 4 7 ù C = êê3 5 11úú êë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
52
3.5. Bilansowanie zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.5.2. Popyt przewyższa podaż (2/2) Fikcyjny dostawca (c.d.)
Rozwiązanie początkowe Rozwiązanie początkowe (metoda VAM)
Podaż
10 * 0 10 * 0 15 * 5 * 0 0 30 * 0 0 5 * 10 15 50 Nowa macierz wskaźników optymalności 1 4 7 3 5 11 6 7 9 0 0 0
20 20 30 5 vj
Rozwiązanie optymalne x11 = 10 x21 = 0 x31 = 0 x11 = 0
x12 = 0 x22 = 15 x32 = 0 x12 = 0
x13 = 10 x23 = 5 x33 = 30 x13 = 5
Optymalna wartość funkcji celu jest równa 470. T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
53
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.1. Problem komiwojażera a zagadnienie transportowe (1/4) Przykład 3.5
Komiwojażer wyjeżdża z miasta 1 i ma odwiedzić miasta o numerach 2, 3, 4 i 5, Do każdego z nich przyjeżdża dokładnie jeden raz, po czym wraca do miasta 1. Szukamy trasy najkrótszej. Miasto
1
2
3
4
5
1
0
10
12
15
11
2
10
0
19
10
11
3
12
19
0
10
12
4
15
10
10
0
20
5
11
11
12
20
0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
54
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.1. Problem komiwojażera a zagadnienie transportowe (2/4) Modelowanie trasy przejazdu
xij =
1 gdy planowany jest przejazd na trasie od i do j 0 w przeciwnym przypadku
Trasa przejazdu 1-2-3-4-5-1 x12 = 1, x23 = 1, x34 = 1, x45 = 1, x51 = 1, pozostałe xij= 0 Miasto
1
2
3
4
5
1
-
1
0
0
0
2
0
-
1
0
0
3
0
0
-
1
0
4
0
0
0
-
1
5
1
0
0
0
-
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
55
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.1. Problem komiwojażera a zagadnienie transportowe (3/4) Model transportowy
Zadanie o 5 dostawcach i 5 odbiorcach Miasto
1
2
3
4
5
Podaż
1
100
10
12
15
11
1
2
10
100
19
10
11
1
3
12
19
100
10
12
1
4
15
10
10
100
20
1
5
11
11
12
20
100
1
1
1
1
1
1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
Popyt
56
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.1. Problem komiwojażera a zagadnienie transportowe (4/4) Model transportowy (c.d.)
Rozwiązanie: x12 = 1, x25 = 1, x34 = 1, x43 = 1, x51 = 1; pozostałe zmienne są równe 0. Optymalna wartość funkcji celu wynosi 52. 2 1
3
5
4
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
57
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.2. Zadanie komiwojażera jako zadanie programowania całkowitoliczbowego (1/5)
Model matematyczny
Funkcja celu: f(x12,x13,x14,x15,x21,x23,x24,x25,x31,x32,x34,x35,x41,x42,x43,x45,x51,x52,x53,x54) = = 10x12 + 12x13 + 15x14 + 11x15 + 10x21 + 19x23 + 10x24 + 11x25 + 12x31 + 19x32 + + 10x34 + 12x35 + 15x41 + 10x42 + 10x43 + 20x45 + 11x51 + 11x52 + 12x53 + 20x54 → min Warunki ograniczające jednokrotny wyjazd z każdego miasta (3.11) – (3-15) jednokrotny wjazd do każdego miasta (3.16) – (3.20) eliminacja cyklów między miastami (3.21) – (3.30) wszystkie zmienne xij są zmiennymi binarnymi xij Î {0;1} dla i,j = 1, ... ,5.
(3.31)
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
58
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.2. Zadanie komiwojażera jako zadanie programowania całkowitoliczbowego (2/5)
Jednokrotny wyjazd z miasta i
Miasto 1 x12 + x13 + x14 + x15 = 1
(3.11)
Miasto 2 x21 + x23 + x24 + x25 = 1
(3.12)
Miasto 3 x31 + x32 + x34 + x35 = 1
(3.13)
Miasto 4 x41 + x42 + x43 + x45 = 1
(3.14)
Miasto 5 x51 + x52 +x53 + x54 = 1
(3.15)
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
59
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.2. Zadanie komiwojażera jako zadanie programowania całkowitoliczbowego (3/5)
Jednokrotny wjazd do miasta i
Miasto 1 x21 + x31 + x41 + x51 = 1
(3.16)
Miasto 2 x12 + x32 + x42 + x52 = 1
(3.17)
Miasto 3 x13 + x23 + x43 + x53 = 1
(3.18)
Miasto 4 x14 + x24 + x34 + x54 = 1
(3.19)
Miasto 5 x15 + x25 + x35 + x45 = 1
(3.20)
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
60
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.2. Zadanie komiwojażera jako zadanie programowania całkowitoliczbowego (4/5)
Eliminacja cyklów pomiędzy miastami
Miasta 1 i 2:
x12 + x21 £ 1
(3.21)
Miasta 1 i 3:
x13 + x31 £ 1
(3.22)
Miasta 1 i 4:
x14 + x41 £ 1
(3.23)
Miasta 1 i 5:
x15 + x51 £ 1
(3.24)
Miasta 2 i 3:
x23 + x32 £ 1
(3.25)
Miasta 2 i 4
x24 + x42 £ 1
(3.26)
Miasta 2 i 5
x25 + x52 £ 1
(3.27)
Miasta 3 i 4
x34 + x43 £ 1
(3.28)
Miasta 3 i 5
x35 + x53 £ 1
(3.29)
Miasta 4 i 5
x45 + x43 £ 1
(3.30)
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
61
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.2. Zadanie komiwojażera jako zadanie programowania całkowitoliczbowego (5/5)
Rozwiązanie optymalne
x15 = 1, x21 = 1, x34 = 1, x42 = 1, x53 = 1, pozostałe zmiennych xij = 0. Optymalna wartość funkcji celu jest równa 53.
Zapis tabelaryczny x12
x13
x14
x15
x21
x23
x24
x25
x31
x32
x34
x35
x41
x42
x43
x45
x51
x52
x53
x54
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
62
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.3. Mechanizmy działania algorytmu genetycznego (1/1) Podstawowe pojęcia
populacja populacja początkowa chromosom gen funkcja przystosowania selekcja krzyżowanie mutacja warunek końca algorytmu T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
63
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (1/9) Populacja początkowa
Chromox12 x13 x14 x15 x21 x23 x24 x25 x31 x32 x34 x35 x41 x42 x43 x45 x51 x52 x53 x54 som C11
0
1
0
0
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
0
C12
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
C13
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
C14
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
C15
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
1
0
0
1
C16
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
64
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (2/9) Populacja początkowa (c.d.) 2
2
1
3
5
2
1
3
5
4
1
3
5
4
4
C11
C12
C13
2
2
2
1
3
5
4
C14
1
3
5
4
C15
1
3
5
4
C16
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
65
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (3/9) Wartości funkcji przystosowania Chromosom
Numery naruszonych ograniczeń
Długość Odcinków
Kara
Wartość funkcji przystosowania
C11
(3.12), (3.13), (3.14), (3.17), (3.18), (3.19), (3.20), (3.25), (3.27)
C12
(3.14), (3.20)
50
200
250
C13
(3.16), (3.17)
69
200
269
C14
(3.13), (3.16), (3.18), (3.19), (3.26)
51
500
551
C15
(3.13), (3.14), (3.15), (3.16), (3.17), (3.20), (3.24)
85
700
785
C16
(3.13), (3.16), (3.19), (3.20)
64
400
464
Suma
3428
109 1000
1109
Średnia wartość funkcji przystosowania wynosi 3428 : 6=571,33 Najlepsza wartość funkcji przystosowania w tej populacji wynosi 250 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
66
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (4/9) Prawdopodobieństwo selekcji
Chromosom
Wartość funkcji przystosowania
Odwrotność wartości funkcji przystosowania
Suma odwrotności funkcji przystosowania
Prawdopodobieństwo selekcji
0,0138631
0,065044 » 7%
C11
1109
0,0009017
C12
250
0,0040000
0,288536 » 29%
C13
269
0,0037175
0,268156 » 27%
C14
551
0,0018149
0,130915 » 13%
C15
785
0,0012739
0,091890 » 9%
C16
464
0,0021552
0,155461 » 15%
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
67
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (5/9) Selekcja i krzyżowanie
Chromosom x12 x13 x14 x15 x21 x23 x24 x25 x31 x32 x34 x35 x41 x42 x43 x45 x51 x52 x53 x54 PK C15
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
1
0
0
1
C16
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
C12
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
C12
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
C14
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
C13
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
11 3 17
68
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (6/9) Mutacja
Prawdopodobieństwo mutacji = 1/100. Chromosom x12 x13 x14 x15 x21 x23 x24 x25 x31 x32 x34 x35 x41 x42 x43 x45 x51 x52 x53 x54 C24
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
C24’
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
69
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (7/9) Populacja początkowa dla następnej iteracji
Chromosom x12 x13 x14 x15 x21 x23 x24 x25 x31 x32 x34 x35 x41 x42 x43 x45 x51 x52 x53 x54 C21
0
0
0
1
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
C22
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
1
C23
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
C24’
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
C25
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
C26
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
70
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (8/9) Populacja początkowa dla następnej iteracji (c.d.) 2
2
1
3
5
1
3
5
4
C21
4
3
5
3
4
2
1
3
5
4
C23
2
1
C24’
1
C22
2
5
2
4
1
3
5
C25 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
4
C26 71
3.6. Problem komiwojażera
3. Zadanie transportowe i problem komiwojażera
3.6.4. Symulacja działania algorytmu genetycznego (9/9) Wartości funkcji przystosowania
Chromosom
Numery naruszonych ograniczeń
C21
Długość trasy
Kara
Wartość funkcji przystosowania
72
0
72
C22
(3.14), (3.15), (3.17), (3.19)
77
400
477
C23
(3.14), (3.20)
50
200
250
C24’
(3.12), (3.14), (3.18), (3.20)
31
400
431
C25
(3.13), (3.16), (3.26)
43
300
343
C26
(3.16), (3.17), (3.18), (3.19), (3.30)
77
500
577
Suma
2150
Średnia wartość funkcji przystosowania wynosi 358,33 Najlepsza wartość funkcji przystosowania w tej populacji wynosi 72 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
72
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.1. Minimalizacja pustych przebiegów (1/7) Przykład 3.6
Odległości między miastami:
1 2 3 4 5 6 7
1
2
3
4
5
6
7
8
0
315
250
190
320
80
380
345
0
130
400
305
320
170
440
0
240
245
295
315
385
0
165
270
520
155
0
400
480
140
0
315
480
0
615
8
0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
73
3.7. Przykłady wykorzystania zadania transportowego
Przykład 3.6 (c.d.)
1 2 3 4 5 6 7 8
Przywóz do miasta i
3. Zadanie transportowe i problem komiwojażera
3.7.1. Minimalizacja pustych przebiegów (2/7)
wi
1 0 14 18 13 16 18 8 4 91
2 21 0 9 8 18 19 7 3 85
3 18 12 0 9 10 6 6 6 67
Wywóz z miasta i 4 5 19 16 15 9 13 11 0 7 8 0 11 9 4 3 10 3 80 58
6 17 11 12 14 6 0 9 4 73
7 10 6 5 3 2 6 0 2 34
8 9 4 6 7 8 2 2 0 38
pi 110 71 74 61 68 71 39 32
Znaleźć plan przewozów minimalizujących puste przebiegi.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
74
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.1. Minimalizacja pustych przebiegów (3/7) Nadwyżka/niedobór samochodów w kolejnych miastach
pi wi
110 91
71 85
74 67
61 80
68 58
71 73
39 34
32 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
75
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.1. Minimalizacja pustych przebiegów (4/7) Podaż i popyt na puste samochody
dostawca
odbiorca b1
b2
b3
b4
a1
315
190
80
345
a2
240
295
385
a3
130 305
165
400
140
a4
170
520
315
615
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
76
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.1. Minimalizacja pustych przebiegów (5/7) Model matematyczny
Cel określenie takiego planu przewozów, który minimalizuje łączną liczbę kilometrów pustych przebiegów.
Zmienne decyzyjne Liczba pustych przebiegów: x11 – z miasta 1 do miasta 2, x12 – z miasta 1 do miasta 4, x13 – z miasta 1 do miasta 6, x14 – z miasta 1 do miasta 8,
x31 – z miasta 3 do miasta 2, x32 – z miasta 3 do miasta 4, x33 – z miasta 3 do miasta 6, x34 – z miasta 3 do miasta 8,
x21 – z miasta 2 do miasta 2, x22 – z miasta 2 do miasta 4, x23 – z miasta 2 do miasta 6, x24 – z miasta 2 do miasta 8,
x41 – z miasta 4 do miasta 2, x42 – z miasta 4 do miasta 4, x43 – z miasta 4 do miasta 6, x44 – z miasta 4 do miasta 8.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
77
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.1. Minimalizacja pustych przebiegów (6/7) Model matematyczny (c.d.)
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 dostawca 1: x11 + x12 + x13 + x14 = 19 odbiorca 1: x11 + x21 + x31 + x41 = 14 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 x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33,x34, x41, x42, x43, x44 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
78
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.1. Minimalizacja pustych przebiegów (7/7) 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 :
6900
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
79
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.2. Zagadnienie transportowo-produkcyjne (1/4) Przykład 3.7
Zdolności produkcyjne zakładów: 40, 50, 30 Zapotrzebowanie odbiorców: 45, 10, 30, 35 Jednostkowe koszty produkcji: 4, 3, 1 Jednostkowe koszty transportu
é4 3 2 1ù C = êê3 2 7 9úú êë8 3 5 4úû
Jednostkowe koszty produkcji i transportu é8 ê J = ê6 ê ë9
7 6 5ù ú 5 10 12ú ú 4 6 5û
Znaleźć taki plan produkcji, by zminimalizować łączne koszty produkcji i transportu. T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
80
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.2. Zagadnienie transportowo-produkcyjne (2/4) Model matematyczny
Cel Minimalizacja łącznych kosztów produkcji i transportu.
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 x14 - przez zakład 1 dla odbiorcy 4 x21 - przez zakład 2 dla odbiorcy 1 x22 - przez zakład 2 dla odbiorcy 2 x23 - przez zakład 2 dla odbiorcy 3 x24 - przez zakład 2 dla odbiorcy 4
x31 - przez zakład 3 dla odbiorcy 1 x32 - przez zakład 3 dla odbiorcy 2 x33 - przez zakład 3 dla odbiorcy 3 x34 - przez zakład 3 dla odbiorcy 4
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
81
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.2. Zagadnienie transportowo-produkcyjne (3/4) Model matematyczny (c.d.)
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 zakład 1: x11 + x12 + x13 + x14 = 40
odbiorca 1: x11 + x21 + x31 + x41 = 45
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 x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33,x34, x41, x42, x43, x44 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
82
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.2. Zagadnienie transportowo-produkcyjne (4/4) Rozwiązanie optymalne
x11 = 0 x21 = 45 x31 = 0
x12 = 0 x22 = 5 x32 = 5
x13 = 30 x23 = 0 x33 = 0
x14 = 10 x24 = 0 x34 = 25
Optymalna wartość funkcji celu jest równa Plan przewozów odbiorca 1 odbiorca 2 odbiorca 3 odbiorca 4
665 Produkcja
0
0
30
10
zakład 1
40
45
5
0
0
0
5
0
25
zakład 2 zakład 3
50 30
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
83
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.3. Zagadnienie przydziału (1/5) Przykład 3.8
Czas pracy doradców firmy consultingowej : X - 140 godz., Y - 140 godz., Wymagania czasowe nowych kontraktów:
Klient A B C D
Z - 120 godz.
Liczba godzin 165 50 80 70
Stawki godzinowe:
Doradca X Y Z
Klient A 9 11 15
Klient B 11,5 13 14,5
Klient C 12 11,5 14
Klient D 10 12 13
W jaki sposób przydzielić doradcom kontrakty tak, by łączny koszt ich realizacji był najmniejszy? T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
84
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.3. Zagadnienie przydziału (2/5) Model matematyczny
Cel Minimalizacja kosztów wynagrodzenia doradców.
Zmienne decyzyjne Liczba godzin pracy: x11 - doradcy X dla klienta A, x12 - doradcy X dla klienta B, x13 - doradcy X dla klienta C, x14 - doradcy X 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,
x31 - doradcy Z dla klienta A, x32 - doradcy Z dla klienta B, x33 - doradcy Z dla klienta C, x34 - doradcy Z dla klienta D.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
85
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.3. Zagadnienie przydziału (3/5) Model matematyczny (c.d.)
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 dla doradcy X: x11 + x12 + x13 + x14 £ 140 dla klienta A: x11 + x21 + x31 = 165 dla doradcy Y: x21 + x22 + x23 + x24 £ 140 dla klienta B: x12 + x22 + x32 = 50 dla doradcy Z: x31 + x32 + x33 + x34 £ 120 dla klienta C: x13 + x23 + x33 = 80 dla klienta D: x14 + x24 + x34 = 70 Warunki nieujemności dla zmiennych decyzyjnych x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33,x34 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
86
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.3. Zagadnienie przydziału (4/5) Model matematyczny (c.d.)
Fikcyjny klient (odbiorca E) 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 x15 + x25 + x35 = 35
Dodatkowe warunki nieujemności: x15, x25, x35 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
87
3.7. Przykłady wykorzystania zadania transportowego
3. Zadanie transportowe i problem komiwojażera
3.7.3. Zagadnienie przydziału (5/5) Rozwiązanie optymalne
x11 = 140 x21 = 25 x31 = 0
x12 = 0 x22 = 35 x32 = 15
x13 = 0 x23 = 80 x33 = 0
x14 =0 x24 = 0 x34 = 70
x15 = 0 x25 = 0 x35 = 35
Optymalna wartość funkcji celu jest równa 40 375 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
88
3. Zadanie transportowe i problem komiwojażera
Pora na relaks
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
89
