140 141

140 Zadanie transportowe i problem komiwojażera

reguły tworzenia zadania dualnego opisane w podrozdziale 1.6.1 i przenosząc na lewą stronę wyrazy wolne, otrzymujemy następujące zadanie:

20w, + 20«₂ + 30n₃ + 10v,+ 15v₂ + 45v₃ —» min,

m, + w, + 1 >0, « i + v₂ + 4>0, n, + v, + 7>0,

n₂ + + 3 ^ 0, m₂ + v₂ + 5 > 0, n₂ + v₃ + 11 ^ 0, (3.7)

u₃ + Vt + 6^0, «j + v₂ + 7>0, u₃+v₃ + 9X).

Ponieważ w zadaniu prymalnym ograniczenia są w postaci równości, więc zmienne w zadaniu dualnym nie są ograniczone co do znaku.

Zmienne w zadaniu prymalnym i ograniczenia w zadaniu dualnym połączone są przez twierdzenie o kompiementarności następującym układem warunków:

*!,(«, + v, + 1) = 0, x \ ₂ (u! + v₂+4) ⁼ 0, JC,,(£/, + v₃ + 7) = 0,

x₂,(m₂ + ^v, + 3) = 0, .v₂₂(n₂+r₂ + 5) = 0, x₂₃(n₂ +v,+11) = 0, (3.8)

X₃|(«₃ + +6) = 0, x₃₂(n, + v₂ + 7) = 0, x₃₃(n₃ + v₃ + 9) = 0.

Zależności te wykorzystamy w dalszej części tego rozdziału.

3.2.3. Sformułowanie zadania transportowego

Przedstawimy teraz ogólny sposób zapisu zadania transportowego. Przyjmiemy następujące oznaczenia:

m — liczba dostawców,

n — liczba odbiorców,

a, — podaż /-tego dostawcy (i=l, ..., ni),

bj — popyt y-tego odbiorcy (/'= 1, ..., n),

_XiJ — ilość towaru przewieziona od /-tego dostawcy do j-tego odbiorcy,

C/j — koszt przewozu jednostki towaru od /-tego dostawcy do j-tego odbiorcy.

Podamy postać zbilansowanego zadania transportowego, w którym łączna podaż wszystkich dostawców jest równa łącznemu zapotrzebowaniu wszystkich odbiorców, czyli spełniony jest warunek:

m n

Ź a, = £ bj.

>=i ;=i

Model matematyczny zadania transportowego możemy wówczas zapisać następująco:

m n

£ £ c_ux,j -> min, i-U-l

(3.9)

£xij = <z, dla /=1, .... m,

/='

£x-,j = bj dla 7=1, n, (3.10)

i= I

xij> 0.

Każde ograniczenie z grupy (3.9) interpretujemy w taki sposób, że łączna ilość towaru wysłanego przez i-tego dostawcę do wszystkich odbiorców jest równa całkowitej podaży tego dostawcy. Każde ograniczenie z grupy (3.10) odczytujemy z kolei tak, że łączna ilość towaru otrzymanego przez j-tego odbiorcę od wszystkich dostawców jest równa łącznemu popytowi tego dostawcy. Egz.emplifikacją ograniczeń grupy (3.9) w przykładzie 3.1 są związki (3.1)—(3.3), natomiast grupy (3.10) — związki (3.4)-(3.6).

Warto zwrócić uwagę na pewne interesujące własności zadania transportowego, wyróżniające je spośród zadań programowania liniowego. Zawsze istnieje jego rozwiązanie optymalne i jest ono skończone, czyli nie może zaistnieć żaden z pozostałych dwóch przypadków omówionych w rozdziale 1 (zadanie sprzeczne, nieograniczoność funkcji celu). W każdym zadaniu transportowym mamy m + n warunków ograniczających, przy czym macierz współczynników składa się z zer i jedynek. Każdy z tych warunków można przedstawić jako kombinację liniową pozostałych, które są liniowo niezależne. Wynika stąd, że liczba zmiennych bazowych w każdym rozwiązaniu bazowym wynosi m + n- 1.

3.3. Pierwsze dopuszczalne rozwiązanie bazowe

Mamy dane zbilansowane zadanie transportowe i chcemy je rozwiązać. W tym celu należy znaleźć jego pierwsze rozwiązanie bazowe.

Rozpatrując zadanie transportowe, wygodnie jest posługiwać się ujęciem macierzowo-tabelarycznym. Z zadaniem transportowym zwiążemy dwie macierze o m wierszach i n kolumnach — macierz przewozów' (zwaną również planem przewozów) i macierz kosztów. W macierzy przewozów zapisujemy wartości aktualnie rozpatrywanego rozwiązania, w macierzy kosztów zapisujemy jednostkowe koszty transportu między poszczególnymi dostawcami i odbiorcami. Parę liczb (/, j) z zakresu 1 oraz 1 ^n opisującą położenie aktualnie

rozpatrywanego elementu macierzy (przewozów lub kosztów) nazywamy węzłem. Macierz przewozów X oraz macierz kosztów C dla przykładu 3.1 mają postać:

	~ 0	0	20		1	4	i'
X =	0	0	20	, c =	3	5	11
	10	15	5		6	7	9