124 125

124 Programowanie liniowe całkowitoliczbowe

Interpretację geometryczną metody cięć przedstawiono na rys. 2.14. Dołączone do zbioru warunków ograniczających zadania zrelaksowanego równanie cięcia odcina z tego zbioru dotychczasowe rozwiązanie optymalne, czyli wierzchołek B, lecz pozostawia w tym zbiorze wszystkie punkty o współrzędnych całkowitych.

Rysunek 2.14

Dołączony warunek ograniczający odcina dotychczasowe rozwiązanie optymalne w punkcie B, generując jednocześnie dwa nowe wierzchołki zbioru rozwiązań dopuszczalnych: C₂ i C,. Funkcja celu w obu tych punktach przyjmuje taką samą wartość. Rozwiązaniem optymalnym jest punkt C₂(10, 11) o współrzęd- g nych całkowitych.

2.3.2. Reguły postępowania w metodzie cięć

Poniżej sformułujemy reguły postępowania stosowane w metodzie cięć.

1.    Rozwiązanie zadanie zrelaksowanego.

Stosując pryrnalną łub dualną metodę simpleks, rozwiązujemy zadanie zrelaksowane. Jeżeli otrzymane rozwiązanie nie jest całkowitoliczbowe, przechodzimy do kroku 2, w przeciwnym przypadku kończymy postępowanie.

2.    Wybór równania wykorzystywanego do konstrukcji równania cięcia. Wybieramy to równanie, dla którego część ułamkowa elementu prawej strony warunków ograniczających jest największa. W przypadku niejednoznaczności wybieramy równanie związane ze zmienną bazową o najniższym numerze.

3.    Konstrukcja równania ciącia.

Wykorzystujemy wzór:

X - a₀)Xij + jc„₊i = [b,] - b„

j

gdzie sumowanie przebiega po zmiennych niebazowych, a /'jest numerem wybranego do cięcia warunku ograniczającego, to współczynniki przy zmiennych niebazowych w ostatniej postaci bazowej zadania, b, — /-ta składowa wyrazu wolnego, a x„_+l — wprowadzona dodatkowo zmienna bilansująca. Utworzone w powyższy sposób równanie cięcia dołączamy do zbioru warunków ograniczających.

4.    Przejście do nowej bazy dopuszczalnej.

Uzyskane w punkcie 3 zadanie jest w postaci bazowej. Otrzymana baza jest optymalna, lecz niedopuszczalna, dlatego też w dalszym postępowaniu do otrzymania bazy dopuszczalnej wykorzystamy dualną metodę simpleks.

5.    Zakończenie postępowaniu.

Jeżeli uzyskane w kroku 4 rozwiązanie jest całkowitoliczbowe, kończymy postępowanie. W przeciwnym przypadku wracamy do kroku 2.

2.4. Przykłady wykorzystania programowania liniowego całkowitoliczbowego

Pokażemy dalej trzy przykłady zastosowania programowania całkowitoliczbowego. We wszystkich przykładach w znacznym stopniu będziemy wykorzystywać zmienne binarne, mogące przyjąć wartości zero lub jeden. Przykład 2.5 dotyczy problemu wyboru wariantów modernizacji maszyn, co pozwoli na zwiększenie produkcji i maksymalizację zysku. Przykład 2.6 opisuje problem