080 081 2

80

C_t A

f-O .

•)O../, (' ■ ■' •••

Programowanie liniowe

Przykład 1.20

Rozwiążemy ponownie zadania z przykładu 1.5, wykorzystując dualną metodę simpleks.

Pierwsze bazowe rozwiązanie optymalne otrzymamy po usunięciu z bazy zmiennej bilansującej sztucznego ograniczenia i wprowadzeniu na to miejsce zmiennej xa- Przyjmujemy wartość prawej strony sztucznego ograniczenia równą 1600. Uzyskane w ten sposób rozwiązanie bazowe jest również rozwiązaniem dopuszczalnym (tablica 1.32).

Tablica 1.32

cx —>	max	2	3	0	0	0	5
Baza	CH		*i	Xy	*4	Jt,
Xy	0	4	0	i	0	0	t6
x2	3	2	1	0	0	1	1 603
*4	0	1	0	0	1	l	1 600
^cr	-2;	-4	0	0	0	-3	4 809

Wśród zmiennych bazowych nie ma jednak zmiennej x_s, która została właśnie usunięta z bazy. Zgodnie ze wcześniejszymi uwagami oznacza to, że funkcja celu rozpatrywanego zadania jest nieograniczona od góry.

1.7.5. Reguły postępowania

w dualnej metodzie simpleks

1.    Uzyskanie pierwszego rozwiązania bazowego

Rozwiązanie to uzyskujemy często poprzez przekształcenie zadania wyjściowego do postaci standardowej i wprowadzenie zmiennych bilansujących. Jeżeli okaże się to niewystarczające, stosujemy metodę sztucznego ograniczenia.

2.    Badanie dopuszczalności rozwiązania

Służy do tego kryterium dopuszczalności, wykorzystywane na początku każdej iteracji.

3.    Badanie nieograniczoności funkcji celu

Jeżeli do zadania wyjściowego wprowadzone zostało sztuczne ograniczenie, wtedy sprawdzamy, czy w otrzymanym na końcu postępowania rozwiązaniu dopuszczalnym wśród zmiennych bazowych znajduje się zmienna bilansująca sztucznego ograniczenia. Jeżeli nie, oznacza to, że w wyjściowym zadaniu funkcja celu jest nieograniczona od góry.

7.

8.

Parametryczne programowanie liniowe

•7

81

Identyfikacja rozwiązań alternatywnych    O )    _

Rozwiązania alternatywne istnieją wtedy, gdy przynajmniej jeden współ-czynnik optymalności dla zmiennej niebazowej przyjmuje wartość zero. Możemy zidentyfikować wszystkie rozwiązania alternatywne, wprowadzając kolejno te zmienne do bazy i przechodząc do kolejnych rozwiązań bazowych zgodnie z regułami, opisanymi w dalszych krokach.

Wybór zmiennej usuwanej z bazy Służy do tego kryterium wyjścia.

Badanie niesprz.eczności zadania

Sprawdzamy, czy w wierszu, odpowiadającym wybranej zmiennej, którą zamierzamy usunąć z bazy, jest przynajmniej jedna liczba ujemna. Jeżeli nie, oznacza to, że zadanie jest sprzeczne.

Wybór zmiennej wprowadzanej do bazy Służy do tego kryterium wyjścia.

Sprowadzenie warunków ograniczających do postaci bazowej wzglądem nowej bazy

Wykorzystujemy w tym celu przekształcenia elementarne.

1.8. Parametryczne

programowanie liniowe

W dotychczas omawianych zadaniach zarówno współczynniki funkcji celu, wyrazów wolnych, jak i macierzy warunków ograniczających były jednoznacznie określone. Może się zdarzyć, że wartości te będą funkcjami pewnych parametrów. Przedstawimy dalej dwie najprostsze sytuacje tego rodzaju. W pierwszym z rozpatrywanych przypadków od parametru zależne będą współczynniki wektora funkcji celu, w drugim zaś wartość parametru będzie kształtowała współczynniki wektora wyrazów wolnych. Rozważane zadania są zadaniami jednoparametrycznymi, co oznacza, że na wszystkie składowe rozpatrywanych wektorów ma wpływ ten sam parametr. Rozpatrywane przez nas zależności będą miały charakter liniowy.

1.8.1. Funkcja celu

zależna od parametru

Przedstawimy dalej sposób analizy zależności rozwiązania optymalnego od wartości parametru w przypadku, gdy parametr pojawia się w funkcji celu. Będziemy dążyli do tego, aby zbiór możliwych do zrealizowania wartości parametru (może to być zbiór wszystkich liczb rzeczywistych lub pewien jego podzbiór) podzielić na takie przedziały, by wszystkim wartościom ustalonego przedziału odpowiadało to samo rozwiązanie optymalne. Rozpoczniemy od dowolnie wybranej początkowej wartości parametru (często wartość tę przyjmujemy jako /₀ = 0).