120 121

120 Programowanie liniowe całkowito liczbowe

odpowiadające zmiennej bazowej o wartości niecałkowitej. Na podstawie tego ograniczenia konstruujemy dodatkowy warunek ograniczający, nazywany równaniem dęcia. Nazwa bierze się stąd, żc ten dodatkowy warunek odcina ze zbioru rozwiązań dopuszczalnych niecałkowite rozwiązanie optymalne zadania zrelaksowanego (oraz dodatkowo pewne inne rozwiązania tego zadania), jednak wśród tych odrzuconych punktów nie ma żadnego rozwiązania dopuszczalnego wyjściowego zadania programowania całkowitoliczbowego.

Zaproponowany dalej sposób konstrukcji równania cięcia generuje, po dołączeniu tego równania do zbioru pozostałych warunków ograniczających rozpatrywanego zadania, rozwiązanie bazowe optymalne, lecz niedopuszczalne. Chcąc przejść do kolejnego rozwiązania dopuszczalnego (i optymalnego), stosujemy dualną metodę simpleks. Konstruujemy kolejne równania cięcia tak długo, aż otrzymamy rozwiązanie całkowitoliczbowe zadania zrelaksowanego z dołączonymi dodatkowo kolejnymi równaniami cięć. Otrzymane w ten sposób rozwiązanie jest rozwiązaniem optymalnym wyjściowego zadania programowania całkowitoliczbowego.

2.3.1. Konstrukcja równania cięcia

Sposób konstrukcji równania cięcia i wykorzystania go w obliczeniach zilustrujemy za pomocą przykładu.

Przykład 2.4

Pokażemy zastosowanie naszkicowanego powyżej postępowania na przykładzie zadania sformułowanego w przykładzie 2.1. Przypomnijmy to zadanie:

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

18*1 + 3,r₂ ^ 224,

ją, x₂ > 0,

ją, x₂ — całkowite.

Rozpatrzymy zadanie z pominięciem warunków całkowitoliczbowości. Wprowadzając zmienne bilansujące, sprowadzamy zadanie do postaci standardowej, która jest jednocześnie postacią bazową. Otrzymujemy:

ją + x₂ —» max,

ją+2x₂+.K:i    = 32,

I 8jc, + 3jc₂ +j.'₄=224, ją, x₂, ją, x_A ^ 0.

Zadanie możemy rozwiązać, stosując prymalną metodę simpleks. Ostatnią tablicę simpleksową przedstawiono w postaci tablicy 2.2.

Tablica 2.2

cx —>	max	1	1	0	0	b
Baza	C»	*1	*2		Xą
*2	1	0	1	0,5455	-0,0303	10,6667
**l	1	1	0	-0,0909	0,0606	10,6667
^cr	-Z/	0	0	-0,4545	-0,0303	21,3333

Uzyskane rozwiązanie zadania liniowego nie daje nam rozwiązania w liczbach całkowitych, przystąpimy więc do konstrukcji równania cięcia, które dołączymy do rozpatrywanego przez nas zadania. Wykorzystamy do tego celu ten wiersz tablicy simpleksowej, w którym odpowiadająca mu zmienna bazowa przyjmuje wartość niecałkowitą i jej część ułamkowa jest największa. W otrzymanym rozwiązaniu mamy *, =*₂ = 10,6667, stąd części ułamkowe są takie same i mamy [10,66671 = 10 (przypomnijmy, że symbol [a] oznacza największą liczbę całkowitą nie przekraczającą a). W celu utworzenia równania cięcia wybieramy równanie odpowiadające zmiennej *,. Ma ono postać:

z, - 0,0909*, + 0,0606*, = 10.6667.    (2.1)

Zauważmy, że ponieważ dla współczynników przy zmiennych niebazowych zachodzą związki:

[-0,0909] <-0,0909

oraz

[0,0606] 0,0606, tak więc:

[-0,0909]*,0,0909*, oraz

[0,0606] *₄ < 0,0606*₄.

Dodając stronami dwie powyższe nierówności, otrzymujemy:

[-0,0909]*, + [0,0606]*4 ^ -0.0909*, + 0,0606*₄.

Jeżeli do obu stron ostatniej nierówności dodamy zmienną *,, to otrzymamy:

*, + [- 0,0909]*, +10,0606] *4 <*,-0,0909*, + 0,0606*4 = 10,6667.

Końcowa równość jest powtórzeniem rozpatrywanego przez nas równania. Z powyższego związku wynika, że:

+ [- 0,0909]*, + [0,0606]*4 < 10,6667.