168 169

168

już zostały wyeliminowane). Zajmiemy się więc cyklami dwu- i trzyelementowymi *'• '

Zadanie transportowe i problem komiwojażera '•*

jako kombinacjami, odpowiednio, dwu- i trzyclcmcntowymi, zbioru pięcioelemen- |§j

towego. Ponieważ każdemu cyklowi trzyelementowemu odpowiada cykl dwuele- •

mentowy, przy eliminacji rozwiązań zawierających cykle wystarczy ograniczyć się do cyklów dwuelementowych, uzupełniając dotychczas uwzględnione warunki zależnościami x_{j + x_y, < 1 dla / = 1,    5 oraz j= 1, ..., 5, i^j- Ich spełnienie

gwarantuje, że w żadnym rozwiązaniu dopuszczalnym nie zaplanujemy jednocześnie przejazdu od miasta i do j oraz z powrotem. Model matematyczny rozpatrywanego zadania zapiszemy następująco:

Funkcja celu

m ■-

'■•SśS ■

aft

Problem komiwojażera

jednokrotny wjazd do miasta 5:

JCj5 + *25 + *35 + *45    1 ,

eliminacja cyklu pomiędzy miastami 1 i 2: *12 + *21 < 1,

eliminacja cyklu pomiędzy miastami 1 i 3:

*13 + zc.n ^ 11

eliminacja cyklu pomiędzy miastami 1 i 4:

*14 + *41 ^ 1"

169

eliminacja cyklu pomiędzy miastami 1 i 5:

-*15 + *₅| ^ 1,

eliminacja cyklu pomiędzy miastami 2 i 3:

(3.21)

(3.22)

(3.23)

(3.24)

(3.25)

/(*I2> *13, *14, *15, *2I> *23, *24, *25, *31, *32, *34, *35, *41, *42, *43, *45, *51, *52, *53, *54) ⁼ = 10*i2 + 12*13 + I5*|₄ + 1 1*,₅ + 10*2| + 19*23 + 10*₂₄ + I 1*25 + 12*₃, +

+ 19*32 "b 10*34 "b 12*35 "b 15*4| + 10*42 b 10*4₃ "b 20*45 *b 1 1*5| "b 1 1*52 +

+ 12*53 + 20*54 —3 min.

Warunki ograniczające jednokrotny wyjazd z miasta 1: *12 +*„ + *,4 +*,5= 1,	(3.12)
jednokrotny wyjazd z miasta 2: *21 + *23 + *24 + *25 = 1 -	(3.13)
jednokrotny wyjazd z miasta 3: *31 + *32 + *34 + *35 = 1 ,	(3.14)
jednokrotny wyjazd z miasta 4: *41 + *42 + *43 + *45 = 1 >	(3.15)
jednokrotny wyjazd z miasta 5: *51 + *52 + *53 + *54 = 1,	(3.16)
jednokrotny wjazd do miasta 1: *21 +*31 +*41 +*51 = 1,	(3.17)
jednokrotny wjazd do miasta 2: X\2 X-yi + Xą2 ~ł“ X$2 ~ ^ i	(3.18)
jednokrotny wjazd do miasta 3: *13 + *23 + *43 + *S3 = 1,	(3.19)
jednokrotny wjazd do miasta 4: *14 + *24 + *34 + *54 = 1,	(3.20)

*23 + *32 ^ 1 ,	(3.26)
eliminacja cyklu pomiędzy miastami 2 i 4: *24 + *42 < 1 ,	(3.27)
eliminacja cyklu pomiędzy miastami 2 i 5: *25 + *52 ^ 1 >	(3.28)
eliminacja cyklu pomiędzy miastami 3 i 4: *34 +*43 < 1,	(3.29)
eliminacja cyklu pomiędzy miastami 3 i 5: *35 + *53 ^ 1,	(3.30)
eliminacja cyklu pomiędzy miastami 4 i 5: *45 + *54 11	(3.31)
wszystkie zmienne xtJ są zmiennymi binarnymi: *ąe (0; 1}, dla /, j = 1.....5.	(3.32)

Rozwiązując zadanie za pomocą programu SIMP INT.EXE, otrzymujemy: *15=1, *21 = 1, *34=1, *42=1, *53=1; wartości pozostałych zmiennych x_tJ są równe 0. Optymalna wartość funkcji celu jest równa 53. Zauważmy, że optymalna wartość funkcji celu jest niewiele większa od przybliżenia (wynoszącego 52), otrzymanego za pomocą algorytmu transportowego.

Otrzymane rozwiązanie można zapisać tabelarycznie lub też w postaci zer i jedynek (tablica 3.38).