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