Przykład AT-3.
Wyznaczyć poprawiony (o mniejszych kosztach całkowitych) plan dostaw dla rozwiązania
startowego z przykładu AT-2.

Rozwiązanie:

Wyznaczony w przykładu AT-2 startowy, bazowy plan dostaw był następujący:

Odbiorca „j”

Dostawca „i”

1

O

2

O

3

O

4

O

podaż

1

D

210

90

0

0

300

2

D

0

80

70

0

150

3

D

0

0

290

140

430

popyt

210

170

360

140

880

Na trasie

)

1

,

3

(

otrzymaliśmy

1

31

−

=

∆

- oznacza to, że kierując jednostkową dostawę

na trasę

)

1

,

3

(

obniżamy całkowite koszty transportu o 1 jednostkę. Zatem, jeśli w nowym

planie dostaw zmienna

31

x

będzie zmienną bazową to

31

31

x

KC

⋅

∆

=

∆

.

Należy teraz ustalić, która z poprzednich zmiennych bazowych zostanie z bazy

usunięta oraz wartość dla nowej zmiennej bazowej

31

x

. Odpowiednia procedura polega

znalezienia cyklu, który tworzy pole

)

1

,

3

(

z pozostałymi polami odpowiadającymi

niewiadomym bazowym. W tablicy zaznaczamy pola (zacieniowane), którym odpowiadają
niewiadome bazowe oraz znakiem „+” pole na które kierujemy dostawę.

1

O

2

O

3

O

4

O

1

D

-

+

2

D

-

+

3

D

+

-

Przenosząc dostawę na trasę

)

1

,

3

(

musimy: zmniejszyć dostawę na trasie

)

1

,

1

(

(co

zaznaczamy znakiem „.

-

”) oraz zwiększyć dostawę na trasie

)

2

,

1

(

(co zaznaczamy znakiem

„.+

”), następnie zmniejszyć dostawę na trasie

)

2

,

2

(

oraz zwiększyć dostawę na trasie

)

3

,

2

(

i konsekwentnie zmniejszyć dostawę na trasie

)

3

,

3

(

. Ponieważ liczba znaków „.+

” i „.

-

” jest

w każdym wierszu i w każdej kolumnie taka sama to szukany cykl został znaleziony.

Aby ustalić wartość dostawy

31

x

, korzystamy z warunku

0

≥

ij

x

: dla pól oznaczonych

znakiem „

-

” wielkości dostaw nie mogą być ujemne stąd:

80

}

290

,

80

,

210

min{

}

,

,

{

min

33

22

11

31

=

=

=

x

x

x

x

Aby otrzymać poprawiony plan dostaw musimy dodać po 80 do wielkości dostaw na polach
oznaczonych znakiem „ +

” oraz odjąć po 80 od wielkości dostaw na polach oznaczonych

znakiem „

-

”.

Nowy (poprawiony) plan przewozów jest zatem następujący

Odbiorca „j”

Dostawca „i”

1

O

2

O

3

O

4

O

podaż

1

D

130

170

0

0

300

2

D

0

0

150

0

150

3

D

80

0

210

140

430

popyt

210

170

360

140

880

Dla

nowego

poprawionego

planu

dostaw

2840

80

)

1

(

2920

=

⋅

−

+

=

∆

+

KC

KC

.

Dociekliwa Osoba zauważy, że to rozwiązanie otrzymaliśmy metodą minimalnego elementu
macierzy kosztów (był to oczywiście przypadek a nie reguła).

Sprawdzając optymalność nowego rozwiązania otrzymamy:

Na trasie

)

1

,

2

(

otrzymaliśmy ujemną wartość wskaźnika optymalności

1

21

−

=

∆

co oznacza,

ż

e wyznaczone rozwiązanie nie jest optymalne. Wyznaczenie nowego planu przewozów (po

skierowaniu dostawy na trasę

)

1

,

2

(

) pozostawiamy Osobie studiującej.

1

O

2

O

3

O

4

O

i

u

1

D

6

3

3

+5

1

+5

0*

2

D

5

-1

2

+1

2

0

+5

-1

3

D

6

3

+2

3

1

0

j

v

6

3

3

1