122 123

122 Programowanie liniowe całkowitoliczbowe

Ponieważ zmienne *,, *,, x₄ mogą przyjmować jedynie wartości całkowite, lewa strona otrzymanej nierówności może przyjąć jedynie wartość całkowitą jako suma wyrażeń całkowitych. Wynika stąd, że wystarczające jest zapisanie po prawej stronie rozpatrywanej nierówności części całkowitej występującej tam liczby, stąd otrzymujemy:

x, + [-0,0909]*, + [0,0606]*, =$[10,6667],

Możemy wprowadzić zmienną bilansującą x₅. Wtedy:

*, + [-0,09091 *, + | 0,0606] *₄ + *₅ = | 10,6667],    (2.2)

Odejmujemy stronami (2.1) od (2.2):

([-0,0909] + 0,0909)*, + ([0,0606] - 0,0606)*,+*₅ = 110,6667] - 10,6667.

Po wykonaniu powyższych działań otrzymujemy związek:

— 0,9091*₃—0,0606*4 + *₅ = — 0,6667.    (2.3)

Uzyskane równanie nazywamy równaniem cięcia i dołączamy do rozpatrywanego zadania. Tablica simpleksowa z dołączonym równaniem cięcia przyjmuje następującą postać:

Tablica 2.3

cx	max	i	1	0	0	0	b
Baza	Cii	*\	*2	X\	XA	Xi
*2	i	0	1	0,5455	-0,0303	0	10,6667
*i	i	i	0	-0,0909	0,0606	0	10,6667
^x5	0	0	0	0,9091	-0,0606	1	-0,6667
<v		0	0	-0,4545	-0,0303	0	21,3333

Baza, w skład której wchodzą zmienne *_t, *₂ i *₅, jest bazą optymalną, lecz niedopuszczalną. W takiej sytuacji stosujemy dualną metodę simpleks. Zgodnie z kryterium wyjścia zmienną opuszczającą bazę jest *₅, natomiast zmienną wchodzącą do bazy jest *,. Po wykonaniu przekształceń elementarnych otrzymujemy tablicę 2.4.

Uzyskane rozwiązanie *,= 10, x₂~ 11 spełnia warunki całkowitoliczbowości, jest więc jednocześnie rozwiązaniem zadania sformułowanego w rozpatrywanym przykładzie 2.1 zadania programowania całkowitoliczbowego. Rozwiązanie optymalne otrzymaliśmy więc po wykonaniu jednej pełnej iteracji metody cięć.

Zauważmy, że przed przystąpieniem do konstrukcji równania cięcia mieliśmy możliwość wyboru równania wykorzystywanego do tworzenia równania cięcia.

Tablica 2.4

cx —	max	I	1	0	0	0	|)
Baza		X,	•*2	X)	<4	•*s
Xl	1	0	1	1	0	-0,5	1 1
X\	1	1	0	-1	0	1	10
XA	0	0	0	15	1	-16	11
cr		0	0	0	0	-0,5	21

Wybraliśmy równanie odpowiadające zmiennej bazowej jc,. Okazuje się, że wybierając do tworzenia równania cięcia wiersz tablicy simpleksowej odpowiadający zmiennej x₂ i stosując dalej rekomendowaną zasadę wyboru do kolejnego cięcia tego równania, w którym część ułamkowa wyrazu wolnego jest największa, otrzymalibyśmy rozwiązanie optymalne dopiero po wykonaniu jedenastu iteracji².

Zinterpretujemy geometrycznie postępowanie zaproponowane w metodzie cięć. Równanie cięcia, zapisane wzorem (2.3), wygodnie będzie wykorzystywać w postaci ułamkowej. Jest ona następująca:

— '°/| i *3 ~ ²/j3 *4 +*5 = ~ %■

Pomijając zmienną bilansującą, uzyskujemy nierówność:

~¹ °/||-Tt^-~"^3-    (2.4)

Ponieważ mamy: x₃ = 32 — JT|-2x₂ oraz

x₄ = 224 - 1 8jc i — 3jc₂,

uwzględniając powyższe związki w nierówności (2.4), otrzymujemy:

-“7,,(32—jc, — 2jc₂)-²/33(224 — I8jc, — 3a*₂) ^ -²/₃.

Po dokonaniu przekształceń stwierdzamy, że na płaszczyźnie Ox,x₂ do warunków ograniczających zadania wyjściowego z przykładu 2.1 dołączamy nierówność:

*,+*2 <21.

³ W trybie automatycznym i rozwiązania końcowego programu CIECIA.EXB wykorzystano w takim przypadku pewne dodatkowe możliwości, pozwalające na przyspieszenie obliczeń.