3848093739

16

Rozdział 1. Zagadnienie transportowe

1.2.1. Przykład

Firma turystyczna dysponuje czterema autobusami o różnych kosztach eksploatacji. Firma podpisała umowy na wynajęcie autobusów czterem różnym klientom na długi weekend. Koszty realizacji poszczególnych zleceń dla każdego autobusu zamieszczono w tablicy 1.10.

Tablica 1.10. Koszty realizacji zleceń [zł]

---Autobus Zlecenie ——___	Al	A2	A3	A4
Kołobrzeg	3000	1500	3900	2100
Międzyzdroje	4700	2500	5500	3500
Szklarska Poręba	5600	3000	7200	4200
Zielona Góra	6200	3700	8200	4700

1.2.2. Analiza sytuacji decyzyjnej

Każdy z autobusów będzie zajęty przez cały weekend, a zatem każdemu autobusowi można przydzielić co najwyżej jedno zlecenie. Każde zlecenie może być obsłużone przez jeden autobus. Oznaczmy zatem przez Xij, i, j = 1,... ,n zmienną decyzyjną, która przyjmie wartość jeden, gdy autobus j zostanie przydzielony do zlecenia i, oraz zero w przeciwnym razie. W rozwiązaniu optymalnym cztery zmienne przyjmą wartość jeden, a pozostałe wartość zero. Niech Cij oznacza koszt realizacji zlecenia i autobusem j. Sumaryczny koszt realizacji zleceń wyniesie zatem CijXij.

1.2.3. Model matematyczny

Jak wspomniano we wstępie, model matematyczny problemu przydziału jest szczególnym przypadkiem zadania transportowego i ma postać:

zminimalizować

n n

yi y °ij^xij    (i •

i=lj=l

przy ograniczeniach

S II •»> II H	(1.14)
X{j = 1, i = 1,..., n	(1.15)
3=i
'<ij € {0,1}, i,j = l, ...,n	(1.16)

W sytuacji, gdy m ^ n postępujemy podobnie, jak z niezbilansowanym zadaniem transportowym, czyli dodajemy fikcyjne zadanie albo wykonawcę. Koszty realizacji fikcyjnego zadania są zerowe, podobnie jak koszty realizacji zadań przez fikcyjnego wykonawcę.

1.2.4. Algorytm węgierski

Problem przydziału można oczywiście rozwiązać zarówno za pomocą algorytmu sympleks, jak i algorytmu transportowego, ale ze względu na jego