164 165

164 Zadanie transportowe i problem komiwojażera

Przykład 3.4

Popyt w centrum dystrybucji 0₂ z przykładu 3.1 zwiększył się i wynosi 50 jednostek, podaż jest taka sama jak w przykładzie 3.1. Należy przekształcić powstałe w ten sposób zagadnienie nięzbilansowane, w którym popyt przewyższa podaż do postaci zbilansowanej i rozwiązać otrzymane zadanie zbilansowane.

Wprowadzamy fikcyjnego dostawcę., którego podaż jest równa całkowitemu popytowi pomniejszonemu o wielkość całkowitej podaży. Ponieważ popyt jest równy b\ = 10, b₂ = 15, b,= 50, a podaż, odpowiednio, <z, =20, a₃ = 20, a₃ = 30, podaż fikcyjnego dostawcy wynosi:

a₄=(b_[+b₂ + b_i)-(a_l+a₂ + a_s) = (\Q + 15+ 50)-(20 + 20 +30) = 5.

Oznaczymy przez x_4J ilość towaru przekazaną od fikcyjnego dostawcy do j-tego odbiorcy.

Rozwiązanie początkowe otrzymane metodą VAM wraz z dołączoną macierzą kosztów przedstawiono w tablicy 3.34.

Tablica 3.34

Rozwiązanie początkowe (metoda VAM)			Podaż
10*	0	10*	20
0	15*	5*	20
0	0	30*	30
0	0	5*	5
to	15	50	Popyt
Macierz kosztów jednostkowych			Wartość funkcji celu 480
i	4	7
3	5	11
6	7	9
0	0	0

Stosując metodę potencjałów, otrzymujemy rozwiązanie optymalne w drugiej iteracji. Ma ono postać:

= 5,	*12= 0,	*13= 15,
= 5,	*22=15,	*23 = 5,
= 0,	*32 =	*33 = 30,
= 0,	O II pą *	*43= 5.

Optymalna wartość funkcji celu jest równa 470.

Łatwo sprawdzić, że i tym razem metoda VAM daje najlepsze rozwiązanie początkowe. Jeżeli posłużymy się metodą kąta północno-zachodniego, to rozwiązanie optymalne otrzymamy w trzeciej iteracji. Wykorzystując w fazie początkowej metodę minimalnego elementu, rozwiązanie optymalne otrzymamy w czwartej iteracji.

3.6. Problem komiwojażera

3.6.1. Problem komiwojażera

a zagadnienie transportowe

Zastanowimy się teraz, czy problem komiwojażera, sformułowany w podrozdziale 3.1, może być przedstawiony jako zadanie transportowe.

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 i. Odległości między miastami przedstawia tablica 3.35. Szukamy trasy najkrótszej.

Tablica 3.35

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

Podobnie jak w zadaniu transportowym, wprowadzimy zmienne x_:J o wartościach 0 i 1. Zmienna a„ przyjmuje wartość 1, jeżeli w konstruowanej trasie planowany jest przejazd na trasie od miasta i do miasta j, w przeciwnym przypadku zmienna ta przyjmuje wartość 0.

Rozpatrzymy przykładową trasę przejazdu komiwojażera, prowadzącą kolejno przez z miasta 1 przez miasta 2, 3, 4 i 5, a następnie z powrotem do miasta 1. W rozwiązaniu tym mamy x_l2=\, x₂i=l, x_M = I, a₄₅ = 1, a_5i = 1, pozostałe zmienne x_}J są równe zeru. Rozwiązanie to możemy zapisać tabelarycznie. Ponieważ na pewno nie będziemy planowali przejazdów z miasta i do miasta i, więc