Zagadnienia

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.

Ćwiczenie 11.1

Rozwiąż w liczbach całkowitych zadanie:

\begin{array}[]{c}Min\; x_{0}=2x_{3}+3x_{4}+6x_{5}\\
x_{1}+2x_{3}+x_{4}+3x_{5}=3\\
5x_{2}+2x_{3}-3x_{4}-x_{5}=12\end{array}

\forall _{{1\leq i\leq 5}}\; x_{1}\geq 0,x_{i}\in\mathbb{Z}

Ćwiczenie 11.2

Stosując odcięcie Gomory'ego rozwiąż w liczbach całkowitych zadanie:

Min x_{0}=4x_{1}+3x_{2}+5x_{3} , gdy

3x_{1}-x_{3}\leq 9

3x_{1}+x_{2}\geq 2

x_{1}+3x_{3}\leq 8

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

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.