Przykład AT-2.
Sprawdzić optymalność planu dostaw z przykładu AT-1 wyznaczonego metodą kąta północno
- zachodniego.

Rozwiązanie:

Wyznaczony 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

Sprawdzenie optymalności planu dostaw polega na wyznaczeniu wskaźników

optymalności

ij

∆

dla każdej z tras

)

,

( j

i

odpowiadających zmiennym niebazowym

ij

x

i

ustaleniu, czy wszystkie wskaźniki mają wartości dodatnie. Wskaźniki te wyznaczamy jako
różnice

ij

ij

ij

c

c

~

−

=

∆

,

gdzie

ij

c~

są tzw. kosztami pośrednimi. Zatem należy najpierw wyznaczyć koszty pośrednie.

Wyniki obliczeń wpisujemy do tablicy analogicznej jak plan dostaw, Postępujemy
następująco:

a) Z macierzy kosztów





















1

3

5

6

5

2

3

4

6

8

3

6

=

C

wpisujemy do tablicy te wartości kosztów

jednostkowych

ij

c

, które odpowiadają zmiennym bazowym (

ij

x

>0).

1

O

2

O

3

O

4

O

i

u

1

D

6

3

2

D

3

2

3

D

3

1

j

v

b) Obliczamy wartości

i

u i

j

v

wybierając dowolne rozwiązanie szczególne nieoznaczonego

układu (

m+n-1) równań postaci:

ij

j

i

c

v

u

=

+

(dla przepisanych do tablicy

ij

c

).

Dla tego przykładu otrzymujemy następujący układ równań:





















=

+

=

+

=

+

=

+

=

+

=

+

1

3

2

3

3

6

4

3

3

3

3

2

2

2

2

1

1

1

v

u

v

u

v

u

v

u

v

u

v

u

Układ ten jest nieoznaczonym układem równań (którego rozwiązanie ogólne zależy od

jednego parametru) i poszukujemy dowolnego jego rozwiązania szczególnego. Za jedną z

niewiadomych podstawiamy dowolną liczbę rzeczywistą, np.

0

1

=

u

. Otrzymamy wówczas:

6

1

=

v

,

3

2

=

v

,

0

2

=

u

,

2

3

=

v

,

1

3

=

u

,

0

4

=

v

.

1

O

2

O

3

O

4

O

i

u

1

D

6

3

0*

2

D

3

2

0

3

D

3

1

1

j

v

6

3

2

0

c) Po wyznaczeniu wszystkich

i

u i

j

v

obliczamy koszty pośrednie jako sumy

j

i

ij

v

u

c

+

=

~

.

Liczby te wpisujemy do podzielonych na pół pustych kratek w tablicy

sprawdzającej. Wskaźniki optymalności wyznaczamy jako różnice:

ij

ij

ij

c

c

~

−

=

∆

; które wpisujemy do dolnych części podzielonych kratek

Ostatecznie otrzymamy następującą tablicę, zawierającą wskaźniki optymalności

(zaznaczone kolorem czerwonym) dla badanego planu dostaw:

ij

c~

ij

∆

Na trasie

)

1

,

3

(

otrzymaliśmy

1

31

−

=

∆

, oznacza to zgodnie kryterium optymalności, że ten

plan dostaw nie jest optymalny (można zmniejszyć łączne koszty transportu). Konstrukcję
nowego poprawionego planu dostaw omówimy w przykładzie AT-3.

1

O

2

O

3

O

4

O

i

u

1

D

6

3

2

+6

0

+6

0*

2

D

6

+2

3

2

0

+5

0

3

D

7

-1

4

+1

3

1

1

j

v

6

3

2

0