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: M⁢a⁢x⁢⁢⁢x0=x∙c⁢|⁢x∈W⊂Rn,⁢∀1≤i≤t⁢xi∈Z.

Idea rozwiązania.

Skupmy się na zadaniu w którym wszystkie zmienne mają być całkowite a wielościan W jest ograniczony. Jako W1 bierzemy uwypuklenie zbioru wszystkich punktów z wielościanu W o współrzędnych całkowitych. Zbiór W1 jest rozpięty na skończonej liczbie punktów. Na mocy twierdzenia strukturalnego W1 jest wielościanem i to takim, którego wszystkie wierzchołki mają współrzędne całkowite. Zatem zadania P:⁢M⁢a⁢x⁢⁢⁢x0=x∙c⁢|⁢x∈W,⁢∀1≤i≤t⁢xi∈Z i P1:⁢M⁢a⁢x⁢⁢⁢x0=x∙c⁢|⁢x∈W1⊂Rn mają te same wierzchołki optymalne. Metoda rozwiązania polega na przecinaniu wielościanu W takimi półprzestrzeniami by uzyskać wielościan W1.

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

R⁢P: M⁢a⁢x⁢⁢⁢f⁢x⁢|⁢x∈Q⁢R⁢P,

gdzie obszar dopuszczalny Q⁢R⁢P 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 R⁢P problemu P nazywamy taką relaksację problemu P której obszar dopuszczalny jest mniejszy niż obszar Q⁢R⁢P.

Odcięciem nazywamy zacieśnienie relaksacji w którym nowy obszar dopuszczalny jest przecięciem półprzestrzeni i Q⁢R⁢P.

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

a+b≥a+b

i jeżeli x jest liczbą naturalną to x⁢a≥x⁢a

Stąd jeżeli obszar dopuszczalny jest ( między innymi ) opisany równaniem ∑i=1nai⁢xi=b to każdy punkt tego obszaru o współrzędnych całkowitych spełnia też nierówność

b=∑i=1nai⁢xi≥∑i=1nai⁢xi.

Odcięciem Gomoryego nazywamy więc ograniczenie obszaru dopuszczalnego półprzestrzenią H=x∈Rn⁢|⁢∑i=1nai⁢xi≤b.

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

0) Dane zagadnienie P:⁢⁢M⁢a⁢x⁢⁢⁢x0=x∙c⁢|⁢A⁢xT=b,⁢∀1≤i≤n⁢xi≥0,⁢∀1≤i≤n⁢xi∈Z.

1) Rozwiązujemy relaksację R⁢P:⁢⁢M⁢a⁢x⁢⁢⁢x0=x∙c⁢|⁢A⁢xT=b,⁢∀1≤i≤n⁢xi≥0 polegającą na pominięciu warunków ∀1≤i≤t⁢xi∈Z i znajdujemy tablicę sympleks T⁢S pierwotnie i dualnie dopuszczalną.

2) Jeżeli znaleziony punkt optymalny p=p1,p2,…,pn ma współrzędne całkowite to STOP znaleźliśmy rozwiązanie.

3) Wybieramy niecałkowitą współrzędną pj. Odpowiadające jej równanie ( wiersz macierzy sympleks ) ma postać ∑i=1nai⁢xi=pj, gdzie xj jest zmienną bazową więc aj=1.

Dodajemy nierówność ∑i=1nai⁢xi≤pj.

4) Budujemy nową tablicę sympleks z dodatkową kolumną na nową zmienną ( tu xn+1 ) i dodatkowym wierszem opisującym równanie ∑i=1nai⁢xi+xn+1-∑i=1nai⁢xi=pj-pj. Musimy odjąć wyjściowe równanie by zmienna xj 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 x0=-3⁢x1-x2 , gdy

12⁢x1+2⁢x2+x3+32⁢x5=72

12⁢x1+12⁢x2+x4+3⁢x5=92

x1≥0, x2≥0, x3≥0, x4≥0,x5≥0, xi∈Z.

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

310000122103272121201392

Otrzymaliśmy tablicę sympleks pierwotnie i dualnie dopuszczalną opisującą wierzchołek optymalny p1=0,0,72,92,0. Ponieważ punkt nie ma współrzędnych całkowitych wybieramy zmienną x3. Odpowiada jej pierwszy wiersz pod kreską i równanie 12⁢x1+2⁢x2+x+3+32⁢x5=72. Półprzestrzeń odcinająca opisana jest nierównością ⁢12⁢x1+2⁢x2+x+3+32⁢x5≤72⁢ czyli 2⁢x2+x+3+x5≤3. Teraz od równania 2⁢x2+x+3+x5+x6=3 odejmujemy wyjściowe 12⁢x1+2⁢x2+x+3+32⁢x5=72 i otrzymane równanie -12⁢x1-12⁢x5+x6=-12 dopisujemy do tablicy sympleks. Otrzymujemy dualnie dopuszczalną tablicę sympleks:

310000012210320721212013092-12000-121-12

Stosujemy teraz dualną metodę sympleks. Wybieramy wiersz 3-ci i element centralny w piątej kolumnie. 0/12<3⁢12⁢. Po redukcji Gaussa - Jordana otrzymujemy:

3100000-1210032-521201063210001-21

Teraz wierzchołkiem optymalnym jest p2=(0,0,2,32,1|0). Poprawiamy zmienną x4. Do tablicy dopisujemy różnicę równań -52⁢x1+12⁢x2+x4+6⁢x6+x7=32 i -52⁢x1+12⁢x2+x4+6⁢x6+x7=32. Otrzymujemy:

31000000-12100305-5212010603210001-201-12-1200001-12

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

2000002-1-30100343-3001061110001-201110000-21

Wyznaczony przez tę tablicę punkt p3=(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=p1,p2,…,pn ma niecałkowitą współrzędną pj i odpowiadające jej równanie ma postać ∑i=1nai⁢xi=pj to aj=1 i xj jest zmienną bazową zaś dla i≠j⁢⁢⁢ai=0 lub pi=0. Zatem ∑i=1nai⁢pi=pj>pj. Więc p nie spełnia nierówności ∑i=1nai⁢xi≤pj.

Uwaga 11.2

Dodawane zmienne są całkowitoliczbowe gdyż xn+1=pj-∑i=1nai⁢xi∈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 x0=x2 , gdy

x1-x2=72

x1≥0, x2≥0,xi∈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 x0=x2 , gdy

x1+a⁢x2=a

x1≥0, x2≥0,xi∈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:

M⁢i⁢n⁢⁢x0=2⁢x3+3⁢x4+6⁢x5x1+2⁢x3+x4+3⁢x5=35⁢x2+2⁢x3-3⁢x4-x5=12

∀1≤i≤5⁢x1≥0,xi∈Z

Ćwiczenie 11.2

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

Min x0=4⁢x1+3⁢x2+5⁢x3 , gdy

3⁢x1-x3≤9

3⁢x1+x2≥2

x1+3⁢x3≤8

x1≥0, x2≥0, x3≥0, xi∈Z.

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

Optymalizacja I