Zagadnienia

11.1 Zagadnienia całkowitoliczbowe

11. Zagadnienia całkowitoliczbowe

11.1. Zagadnienia całkowitoliczbowe

Definicja 11.1

Zagadnieniem całkowitoliczbowym nazyawć będziemy zadanie optymalizacji liniowej w którym od zmiennych lub części zmiennych wymagamy by były liczbami całkowitymi. Na przykład zadanie typu: $Max\ \{\, x_{0}=x\bullet c\ |\ x\in W\subset\mathbb{R}^{n},\,\forall _{{1\leq i\leq t}}\ x_{i}\in\mathbb{Z}\}$ .

Idea rozwiązania.

Skupmy się na zadaniu w którym wszystkie zmienne mają być całkowite a wielościan $W$ jest ograniczony. Jako $W_{1}$ bierzemy uwypuklenie zbioru wszystkich punktów z wielościanu $W$ o współrzędnych całkowitych. Zbiór $W_{1}$ jest rozpięty na skończonej liczbie punktów. Na mocy twierdzenia strukturalnego $W_{1}$ jest wielościanem i to takim, którego wszystkie wierzchołki mają współrzędne całkowite. Zatem zadania $P:\ Max\ \{\, x_{0}=x\bullet c\ |\ x\in W,\,\forall _{{1\leq i\leq t}}\ x_{i}\in\mathbb{Z}\}$ i $P_{1}:\ Max\ \{\, x_{0}=x\bullet c\ |\ x\in W_{1}\subset\mathbb{R}^{n}\}$ mają te same wierzchołki optymalne. Metoda rozwiązania polega na przecinaniu wielościanu $W$ takimi półprzestrzeniami by uzyskać wielościan $W_{1}$ .

Rozpoczniemy od prezentacji metody zwanej ”Odcięciem Gomoryego” [7], [8], [9]. Metoda opiera się na relaksacji problemu i jej kolejnych zacieśnianiach zwanych odcięciami Gomoryego.

Definicja 11.2

Relaksacją problemu $P$ nazywamy problem

$RP$ : $Max\ \{\, f(x)\ |\ x\in Q(RP)\}$ ,

gdzie obszar dopuszczalny $Q(RP)$ jest większy niż $Q(P)$ .

Zwykle relaksacja jest opuszczeniem najmniej wygodnych warunków opisujących obszar dopuszczalny, np. że współrzędne są całkowite.

Definicja 11.3

Zacieśnieniem relaksacji $RP$ problemu $P$ nazywamy taką relaksację problemu $P$ której obszar dopuszczalny jest mniejszy niż obszar $Q(RP)$ .

Odcięciem nazywamy zacieśnienie relaksacji w którym nowy obszar dopuszczalny jest przecięciem półprzestrzeni i $Q(RP)$ .

Odcięcie Gomoryego wykorzystuje proste własności części całkowitej liczby:

$\lfloor a+b\rfloor\geq\lfloor a\rfloor+\lfloor b\rfloor$

i jeżeli $x$ jest liczbą naturalną to $\lfloor xa\rfloor\geq x\lfloor a\rfloor$

Stąd jeżeli obszar dopuszczalny jest ( między innymi ) opisany równaniem $\sum _{{i=1}}^{n}a_{i}x_{i}=b$ to każdy punkt tego obszaru o współrzędnych całkowitych spełnia też nierówność

$\lfloor b\rfloor=\lfloor\sum _{{i=1}}^{n}a_{i}x_{i}\rfloor\geq\sum _{{i=1}}^{n}\lfloor a_{i}\rfloor x_{i}$ .

Odcięciem Gomoryego nazywamy więc ograniczenie obszaru dopuszczalnego półprzestrzenią $H=\{ x\in\mathbb{R}^{n}\,|\,\sum _{{i=1}}^{n}\lfloor a_{i}\rfloor x_{i}\leq\lfloor b\rfloor\}$ .

Algorytm rozwiązywania zadań całkowitoliczbowych metodą odcięć Gomoryego:

0) Dane zagadnienie $P:\ \ Max\ \{\, x_{0}=x\bullet c\ |\ Ax^{T}=b,\,\forall _{{1\leq i\leq n}}\ x_{i}\geq 0,\ \forall _{{1\leq i\leq n}}\ x_{i}\in\mathbb{Z}\}$ .

1) Rozwiązujemy relaksację $RP:\ \ Max\ \{\, x_{0}=x\bullet c\ |\ Ax^{T}=b,\,\forall _{{1\leq i\leq n}}\ x_{i}\geq 0\}$ polegającą na pominięciu warunków $\forall _{{1\leq i\leq t}}\ x_{i}\in\mathbb{Z}$ i znajdujemy tablicę sympleks $TS$ pierwotnie i dualnie dopuszczalną.

2) Jeżeli znaleziony punkt optymalny $p=(p_{1},p_{2},...,p_{n})$ ma współrzędne całkowite to STOP znaleźliśmy rozwiązanie.

3) Wybieramy niecałkowitą współrzędną $p_{j}$ . Odpowiadające jej równanie ( wiersz macierzy sympleks ) ma postać $\sum _{{i=1}}^{n}a_{i}x_{i}=p_{j}$ , gdzie $x_{j}$ jest zmienną bazową więc $a_{j}=1$ .

Dodajemy nierówność $\sum _{{i=1}}^{n}\lfloor a_{i}\rfloor x_{i}\leq\lfloor p_{j}\rfloor$ .

4) Budujemy nową tablicę sympleks z dodatkową kolumną na nową zmienną ( tu $x_{{n+1}}$ ) i dodatkowym wierszem opisującym równanie $\sum _{{i=1}}^{n}\lfloor a_{i}\rfloor x_{i}+x_{{n+1}}-\sum _{{i=1}}^{n}a_{i}x_{i}=\lfloor p_{j}\rfloor-p_{j}$ . Musimy odjąć wyjściowe równanie by zmienna $x_{j}$ pozostała bazową.

5) Rozwiązujemy relaksację zadaną tą tablicą i GOTO 2.

Prześledźmy algorytm na przykładzie:

Przykład 11.1

Rozwiązujemy zadanie P.

Max $x_{0}=-3x_{1}-x_{2}$ , gdy

$\frac{1}{2}x_{1}+2x_{2}+x_{3}+\frac{3}{2}x_{5}=\frac{7}{2}$

$\frac{1}{2}x_{1}+\frac{1}{2}x_{2}+x_{4}+3x_{5}=\frac{9}{2}$

$x_{1}\geq 0$ , $x_{2}\geq 0$ , $x_{3}\geq 0$ , $x_{4}\geq 0,x_{5}\geq 0$ , $x_{i}\in Z$ .

Zaczynamy od budowy tablicy sympleks pierwszej relaksacji. Jest nią:

$\left[\begin{array}[]{ccccc|c}3&1&0&0&0&0\\ \hline\frac{1}{2}&2&1&0&\frac{3}{2}&\frac{7}{2}\\ \frac{1}{2}&\frac{1}{2}&0&1&3&\frac{9}{2}\end{array}\right]$

Otrzymaliśmy tablicę sympleks pierwotnie i dualnie dopuszczalną opisującą wierzchołek optymalny $p_{1}=(0,0,\frac{7}{2},\frac{9}{2},0)$ . Ponieważ punkt nie ma współrzędnych całkowitych wybieramy zmienną $x_{3}$ . Odpowiada jej pierwszy wiersz pod kreską i równanie $\frac{1}{2}x_{1}+2x_{2}+x+3+\frac{3}{2}x_{5}=\frac{7}{2}$ . Półprzestrzeń odcinająca opisana jest nierównością $(\ \lfloor\frac{1}{2}\rfloor x_{1}+2x_{2}+x+3+\lfloor\frac{3}{2}\rfloor x_{5}\leq\lfloor\frac{7}{2}\rfloor\ )$ czyli $2x_{2}+x+3+x_{5}\leq 3$ . Teraz od równania $2x_{2}+x+3+x_{5}+x_{6}=3$ odejmujemy wyjściowe $\frac{1}{2}x_{1}+2x_{2}+x+3+\frac{3}{2}x_{5}=\frac{7}{2}$ i otrzymane równanie $-\frac{1}{2}x_{1}-\frac{1}{2}x_{5}+x_{6}=-\frac{1}{2}$ dopisujemy do tablicy sympleks. Otrzymujemy dualnie dopuszczalną tablicę sympleks:

$\left[\begin{array}[]{cccccc|c}3&1&0&0&0&0&0\\ \hline\frac{1}{2}&2&1&0&\frac{3}{2}&0&\frac{7}{2}\\ \frac{1}{2}&\frac{1}{2}&0&1&3&0&\frac{9}{2}\\ -\frac{1}{2}&0&0&0&(-\frac{1}{2})&1&-\frac{1}{2}\end{array}\right]$

Stosujemy teraz dualną metodę sympleks. Wybieramy wiersz 3-ci i element centralny w piątej kolumnie. $(\ 0/\frac{1}{2}<3\frac{1}{2}\ )$ . Po redukcji Gaussa - Jordana otrzymujemy:

$\left[\begin{array}[]{cccccc|c}3&1&0&0&0&0&0\\ \hline-1&2&1&0&0&3&2\\ -\frac{5}{2}&\frac{1}{2}&0&1&0&6&\frac{3}{2}\\ 1&0&0&0&1&-2&1\end{array}\right]$

Teraz wierzchołkiem optymalnym jest $p_{2}=(0,0,2,\frac{3}{2},1|0)$ . Poprawiamy zmienną $x_{4}$ . Do tablicy dopisujemy różnicę równań $\lfloor-\frac{5}{2}\rfloor x_{1}+\lfloor\frac{1}{2}\rfloor x_{2}+x_{4}+6x_{6}+x_{7}=\lfloor\frac{3}{2}\rfloor$ i $-\frac{5}{2}x_{1}+\frac{1}{2}x_{2}+x_{4}+6x_{6}+x_{7}=\frac{3}{2}$ . Otrzymujemy:

$\left[\begin{array}[]{ccccccc|c}3&1&0&0&0&0&0&0\\ \hline-1&2&1&0&0&3&0&5\\ -\frac{5}{2}&\frac{1}{2}&0&1&0&6&0&\frac{3}{2}\\ 1&0&0&0&1&-2&0&1\\ -\frac{1}{2}&(-\frac{1}{2})&0&0&0&0&1&-\frac{1}{2}\end{array}\right]$

Teraz element centralny wybieramy w 4-tym wierszu i 2-giej kolumnie. Po redukcji Gaussa - Jordana otrzymujemy:

$\left[\begin{array}[]{ccccccc|c}2&0&0&0&0&0&2&-1\\ \hline-3&0&1&0&0&3&4&3\\ -3&0&0&1&0&6&1&1\\ 1&0&0&0&1&-2&0&1\\ 1&1&0&0&0&0&-2&1\end{array}\right]$

Wyznaczony przez tę tablicę punkt $p_{3}=(0,1,3,1,1,|0,0)$ ma współrzędne całkowite więc jest rozwiązaniem zadania.

Uwaga 11.1

Odcięcie Gomoryego zawsze wyrzuca badany punkt po za obszar dopuszczalny nowej relaksacji. Rzeczywiście, jeżeli punkt $p=(p_{1},p_{2},...,p_{n})$ ma niecałkowitą współrzędną $p_{j}$ i odpowiadające jej równanie ma postać $\sum _{{i=1}}^{n}a_{i}x_{i}=p_{j}$ to $a_{j}=1$ i $x_{j}$ jest zmienną bazową zaś dla $i\neq j\ \ a_{i}=0$ lub $p_{i}=0$ . Zatem $\sum _{{i=1}}^{n}\lfloor a_{i}\rfloor p_{i}=p_{j}>\lfloor p_{j}\rfloor$ . Więc $p$ nie spełnia nierówności $\sum _{{i=1}}^{n}\lfloor a_{i}\rfloor x_{i}\leq\lfloor p_{j}\rfloor$ .

Uwaga 11.2

Dodawane zmienne są całkowitoliczbowe gdyż $x_{{n+1}}=\lfloor p_{j}\rfloor-\sum _{{i=1}}^{n}\lfloor a_{i}\rfloor x_{i}\in\mathbb{Z}$ .

Uwaga 11.3

W przypadku gdy obszar dopuszczalny jest niepusty i ograniczony lub niepusty i współczynniki wyjściowej tablicy sympleks są wymierne to algorytm odcięcia Gomoryego kończy się po skończonej liczbie kroków, zależnej od liczby zmiennych, ograniczenia i postaci współczynników. Niestety jest to algorytm zużywający dużo czasu i pamięci. Patrz [12] Twierdzenie 23.2.

Uwaga 11.4

Jeżeli obszar dopuszczalny jest zbiorem pustym algorytm odcięcia Gomoryego może nie działać.

Przykład 11.2

Badamy zadanie P.

Max $x_{0}=x_{2}$ , gdy

$x_{1}-x_{2}=\frac{7}{2}$

$x_{1}\geq 0$ , $x_{2}\geq 0$ , $x_{i}\in Z$ .

Obszar dopuszczalny jest zbiorem pustym zaś algorytm urywa się na pierwszym kroku gdyż relaksacja jest zadaniem nieograniczonym.

Przykład 11.3

Badamy zadanie P.

Max $x_{0}=x_{2}$ , gdy

$x_{1}+ax_{2}=a$

$x_{1}\geq 0$ , $x_{2}\geq 0$ , $x_{i}\in Z$ .

Jeżeli $a$ i $b$ są liczbami algebraicznie niezależnymi $>1$ to obszar dopuszczalny jest zbiorem pustym zaś algorytm nigdy się nie kończy mimo, że obszar dopuszczalny relaksacji jest ograniczony.