106 107 2

106 Programowanie liniowe całkowitoliczbowe

leks, a także metodę geometryczną, moż.na wykorzystać do rozwiązania zadań programowania calkowitoliczbowego. Każde takie zadanie można rozpatrzyć jako zwykłe zadania programowania liniowego, pomijając warunki całkowito! iczbowo-ści. Mówimy wówczas, że dokonujemy relaksacji zadania, czyli uwalniamy je od warunków całkowitoliczbowości. Takie zadanie zrelaksowane (czyli zadanie, w którym dokonano relaksacji) możemy rozwiązać metodą simpleks (lub metodą geometryczną, jeżeli jest to możliwe).

Jeżeli otrzymane rozwiązanie optymalne nie spełnia warunków całkowitoliczbowości, to można byłoby próbować zaokrąglić wartości zmiennych niecałkowitych do najbliższych liczb całkowitych. Postępowanie takie —jak pokażemy — nie ma uzasadnienia i prowadzi niejednokrotnie do błędnych wniosków. Po pierwsze, zaokrąglone rozwiązanie może nie spełniać warunków ograniczających (czyli może nie być dopuszczalne). Po drugie, wartość funkcji celu dla tego zaokrąglonego rozwiązania może nawet znacznie różnić się od wartości dla rozwiązania optymalnego, które może znajdować się w zupełnie innej części zbioru dopuszczalnego niż rozwiązanie zaokrąglone.

Zagadnienie programowania całkowitoliczbowego ze względu na swoje praktyczne zastosowania było rozwiązywane na różne sposoby. Zajmiemy się dwoma z nich. Pierwszy, zwany metodą podziału i ograniczeń, można stosować zarówno do mieszanych, jak i czystych problemów programowania całkowitoliczbowego. Drugi, zwany metodą cięć, przedstawimy w wersji pozwalającej otrzymać rozwiązanie dla zadania czystego. W obu tych metodach rozwiązujemy zrelaksowane zadanie programowania liniowego, a następnie, korzystając z otrzymanych rozwiązań, konstruujemy w odpowiedni dla danej metody sposób następne zadania liniowe. Postępowanie to powtarzamy tak długo, aż otrzymamy rozwiązanie spełniające wszystkie warunki całkowitoliczbowości i przekonamy się, że jest ono rozwiązaniem optymalnym zadania wyjściowego.

Istotne znaczenie praktyczne mają zadania, w których wszystkie zmienne (lub ich część) przyjmują wartości zero lub jeden. Zmienne takie nazywamy zmiennymi binarnymi. Można je zastosować m.in. w zadaniach dotyczących porównywania i wyboru wariantu działania. Rozpatrzymy przykład takiego zadania, które opisuje możliwość zwiększenia mocy produkcyjnych w zależności od wyboru wariantu inwestycyjnego. Zmienna opisująca akceptację (lub jej brak) dla danego wariantu inwestycyjnego przyjmie wartość jeden (gdy wariant ten ma być wybrany) lub zero (w przeciwnym przypadku).

Wśród wielu zastosowań programowania liniowego całkowitoliczbowcgo-można wymienić zadania planowania różnego typu, np. zwiększenie mocy produkcyjnych, sporządzenie planu wydawniczego, dokonanie lokalizacji komisariatów policji, sporządzenie harmonogramu zatrudnienia pracowników, zadanie minimalizacji odpadów czy ustalenie programu zawodów sportowych. Niektóre z nich omówimy w końcowej części rozdziału i rozwiążemy, wykorzystując programy SIMP 1NT.EXE i CIEC1A.EXE.

2.2. Metoda podziału i ograniczeń

Ideę metody podziału i ograniczeń pokażemy najpierw na przykładach, kolejno dla zadania czystego, a następnie mieszanego, po czym sformułujemy ogólne reguły postępowania.

2.2.1. Zadania czyste

Zajmiemy się najpierw prostym przykładem zadania programowania całkowitoliczbowego, w którym występują dwie zmienne decyzyjne i dwa warunki ograniczające, i rozwiążemy je geometrycznie.

Przykład 2.1¹

Należy rozwiązać zadanie:

Xi +x₂ —» max, jc, + 2x₂ ^ 32,

1 8jc, + 3*2 < 224,

X|, -r₂ >0,

x_h x₂ — całkowite.

Formułujemy zrelaksowane zadanie programowania liniowego następująco:

Zadanie 1

jc, +x₂ —» max, jc, +2x₂ < 32,

18x, + 3x₂ < 224,

X|, x₂ > 0.

Rozwiążemy to zadanie metodą geometryczną. Rozwiązanie zostało przedstawione na rys. 2.1.

Rozwiązaniem optymalnym jest punkt /t(10²/₃, 10²/₃). Warunki całkowitoliczbowości nie są spełnione zarówno przez pierwszą, jak i drugą zmienną. Należy więc dokonać podziału zbioru punktów dopuszczalnych, wykorzystując do tego celu dowolnie wybraną zmienną, która w tym rozwiązaniu przyjmuje wartość niecałkowitą. W rozpatrywanym przez nas przypadku podział może być dokonany zarówno ze względu na zmienną jc,, jak i zmienną x₂. Dla zilustrowania podobieństw i różnic przedstawimy dalej obydwie możliwości.

Sformułowanie przykładu zaczerpnięto z książki W. Grabowskiego, Programowanie matematyczne PWE, Warszawa 1980.