3848093745

Rozdział 1

Zagadnienie transportowe

Istnieje duża grupa wyspecjalizowanych zagadnień programowania liniowego, które są sformułowane jako zagadnienia sieciowe. Należą do nich takie zagadnienia, jak zagadnienie transportowe i jego uogólnienia, zagadnienie przydziału, zagadnienie lokalizacji i zagadnienie przepływu wielotowarowe-go.

1.1. Zagadnienie transportowe

Zagadnienie transportowe należy do najciekawszych wariantów zadania programowania liniowego. Zadanie transportowe charakteryzuje się szczególną postacią ograniczeń, co pozwala je rozwiązać za pomocą algorytmów sprawniejszych obliczeniowo niż algorytm sympleks. W tym rozdziale omówimy algorytm transportowy, tzw. metodę potencjałów oraz algorytm węgierski, który rozwiązuje zadania przydziału.

1.1.1. Przykład

Firma produkująca nawozy sztuczne ma trzy zakłady produkcyjne zlokalizowane w Kluczborku, Białymstoku i Pile. Kwartalna produkcja poszczególnych zakładów wynosi odpowiednio: 5000 kg, 6000 kg, i 2500 kg. Firma ma cztery centra dystrybucji, zlokalizowane w Lublinie, Elblągu, Łodzi i Opolu. Na podstawie przewidywanego popytu na nawozy poszczególne centra dystrybucji złożyły zamówienia odpowiednio na: 6000 kg, 4000 kg, 2000 kg oraz 1500 kg nawozów. Jednostkowe koszty transportu (w zł/kg) z każdego zakładu do poszczególnych centrów dystrybucji podano w tablicy 1.1.

Tablica 1.1. Jednostkowe koszty transportu [zł/kg]

Dostawcy		Odbiorcy			Zapas [kg]
	Lublin	Elbląg	Łódź	Opole
Kluczbork	3	2	7	6	5000
Białystok	7	5	2	3	6000
Piła	2	5	4	5	2500
Zamówienie [kg]	6000	4000	2000	1500

Znaleźć plan przewozów minimalizujący łączne koszty transportu.