134 135

134 Programowanie liniowe calkowitoliczbowe

Rozwiązanie optymalne

Zadanie rozwiązujemy za pomocą programu CIECIA.EXE. Otrzymujemy następujące rozwiązanie:

*1	*2	X,	*4	X*	Xft	*7
0	1	0	0	i	0	0

Optymalna wartość funkcji celu wynosi 2.

Interpretacja rozwiązania

Najmniejsza liczba zrelokalizowanych komisariatów wynosi 2. Komisariaty powinny być zlokalizowane w miejscach B i E.

2£E^r 3* Zadacie trampeftmre i prMem k®ntiw@|aźsra

3.1. Wprowadzenie

Zadanie transportowe przedstawiane jest jako problem opracowania planu przewozu jednorodnego produktu z różnych źródeł zaopatrzenia do punktów, które zgłaszają zapotrzebowanie na ten produkt.

Mamy zatem ustaloną liczbę dostawców i odbiorców jednorodnego produktu. Znamy podaż każdego dostawcy i zapotrzebowanie każdego odbiorcy w określonym czasie oraz koszty jednostkowe transportu między poszczególnymi dostawcami i odbiorcami proporcjonalne do ilości przewiezionego towaru. Należy znaleźć taki plan przewozów, który minimalizuje łączny ich koszt.

Zadanie transportowe jest przykładem modelu liniowego i może być rozwiązywane za pomocą metody simpleks. Okazuje się jednak, że nie jest to zbyt wygodne. Wykorzystując pewne specyficzne cechy tego zadania oraz teorię dualności, opracowana została bardzo efektywna metoda jego rozwiązania, zwana metodą potencjałów. W porównaniu do metody simpleks pozwala ona skrócić i uprościć obliczenia. Ma przy tym charakter iteracyjny, a czynności wykonywane w kolejnych iteracjach są zbliżone do tych, które wykonujemy w prymalnej metodzie simpleks. Sprawdzamy mianowicie najpierw, czy rozpatrywane w danej iteracji dopuszczalne rozwiązanie bazowe jest optymalne, a jeżeli nie jest, to poprawiamy je, wyznaczając najpierw zmienną, którą wprowadzimy do bazy, następnie zmienną, którą usuniemy z bazy, i wykonujemy przekształcenia doprowadzające dotychczasowe rozwiązanie do nowej postaci bazowej.

Chcąc rozpocząć obliczenia za pomocą metody potencjałów, wykorzystujemy (podobnie jak w prymalnej metodzie simpleks) pierwsze dopuszczalne rozwiązanie bazowe. To rozwiązanie początkowe możemy uzyskać na kilka sposobów. Najprostszym z nich jest metoda kąta północno-zachodniego. Stosując ją, nie wykorzystujemy jednak w żaden sposób wiedzy o jednostkowych kosztach transportu między dostawcami i odbiorcami, dlatego też uzyskane rozwiązania początkowe są zazwyczaj bardziej odległe od rozwiązania optymalnego niż otrzymane wówczas, gdy takie informacje są brane pod uwagę. Powoduje to konieczność wykonania