3848093735

12

Rozdział 1. Zagadnienie transportowe

Tablica 1.4. Wyznaczenie rozwiązania początkowego metodą VAM [r*i]    [dj]    aij    wartości zmiennych

[1 3 2 2] ai2 = ram{2,5,5}

x\2 = 4000 X₂2 = 0

X32 — 0

[1-2 2] an = min{3, 7,6}

Zn — 1000 Xl3 = 0

£l4 — 0

2    [5 -2 2] a3i = min{7,2}

£31 = 2500

£33 = 0

£34 = o

023 - min{7, 2,3}    £23 = 2000

024 = min{7,3}    £24 — 1500

2

021

7

Graf rozwiązania

Rozwiązanie bazowe zadania transportowego będziemy przedstawiali w postaci grafu zbudowanego na macierzy przewozów, którego wierzchołkami są węzły (i,j) tej macierzy odpowiadające zmiennym bazowym, a łuki łączą sąsiednie wierzchołki w tym samym wierszu (i\ =12) lub kolumnie (ji = j‘2). Graf rozwiązania otrzymanego metodą VAM przedstawiono w tablicy 1.5.

Tablica 1.5. Graf rozwiązania początkowego wyznaczonego metodą VAM

Korzystając z własności, że liczba zmiennych bazowych w rozwiązaniu dopuszczalnym wynosi (m + n — 1) zauważmy, że graf rozwiązania ma dokładnie (m + n — 1) wierzchołków. Ponadto jest to graf spójny i bez cykli. Można wykazać, że warunki te są równoważne, czyli zachodzi własność 1.1.

Własność 1.1

Na to, aby graf rozwiązania zadania transportowego był grafem spójnym i bez cykli potrzeba i wystarcza, aby zawierał dokładnie (m + n-1) wierzchołków.