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
O2 O3 O4
O1
podaż
Dostawca  i
210 90 0 0 300
D1
0 80 70 0 150
D2
0 0 290 140 430
D3
880
popyt
210 170 360 140
Sprawdzenie optymalności planu dostaw polega na wyznaczeniu wskaz
ników
optymalności "ij dla każdej z tras (i, j) odpowiadających zmiennym niebazowym xij i
ustaleniu, czy wszystkie wskaz
niki mają wartości dodatnie. Wskaz
niki te wyznaczamy jako
różnice
~
"ij = cij - cij ,
~
gdzie cij 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:
6 3 8 6
�ł łł
a) Z macierzy kosztów C=�ł4 3 2 5śł wpisujemy do tablicy te wartości kosztów
�ł śł
�ł śł
�ł6 5 3 1�ł
jednostkowych cij , które odpowiadają zmiennym bazowym ( xij >0).
O2 O3 O4
O1
ui
6 3
D1
3 2
D2
3 1
D3
v
j
b) Obliczamy wartości ui i v wybierając dowolne rozwiązanie szczególne nieoznaczonego
j
układu (m+n-1) równań postaci: ui + v = cij (dla przepisanych do tablicy cij ).
j
Dla tego przykładu otrzymujemy następujący układ równań:
u1 + v1 = 6
ńł
�łu + v2 = 3
1
�ł
�ł
u2 + v2 = 3
�ł
�ł
u2 + v3 = 2
�ł
�ł
u3 + v3 = 3
�ł
�ł u3 + v4 = 1
ół
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. u1 = 0 . Otrzymamy wówczas:
v1 = 6 v2 = 3 u2 = 0 v3 = 2 u3 = 1 v4 = 0
, , , , , .
O2 O3 O4
O1
ui
6 3 0*
D1
3 2 0
D2
3 1 1
D3
6 3 2 0
v
j
c) Po wyznaczeniu wszystkich ui i v obliczamy koszty pośrednie jako sumy
j
~
cij = ui + v .
j
~
cij
Liczby te wpisujemy do podzielonych na pół pustych kratek w tablicy
"ij
sprawdzającej. Wskaz
niki optymalności wyznaczamy jako różnice:
~
"ij = cij - cij ; które wpisujemy do dolnych części podzielonych kratek
Ostatecznie otrzymamy następującą tablicę, zawierającą wskaz
niki optymalności
(zaznaczone kolorem czerwonym) dla badanego planu dostaw:
O2 O3 O4
O1
ui
2 0 0*
D1
6 3
+6 +6
6 0 0
D2
3 2
+2 +5
7 4 1
D3
3 1
-1 +1
6 3 2 0
v
j
Na trasie (3,1) otrzymaliśmy "31 = -1, 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.