116 117

I 16 Programowanie liniowe całkowitoliczbowe

Iteracja 5

Porządkujemy lisię zadań. Na liście mamy: zadanie 4, zadanie 6, zadanie 8 i zadanie 9. Usuwamy zadanie 6, gdyż zostało już podzielone. Usuwamy zadanie 9, które jest sprzeczne. Usuwamy również zadanie 4; rozwiązanie tego zadania spełnia co prawda warunki całkowitoliczbowości, ale wartość funkcji celu dla tego zadania równa 13 jest gorsza od wartości funkcji celu dla optymalnego rozwiązania zadania 8 równej 13,5. Rozwiązanie optymalne zadania 8 jest jednocześnie rozwiązaniem optymalnym zadania wyjściowego rozpatrywanego przykładu 2.2.

Kolejne zadania, otrzymane w wyniku dokonywanych podziałów, zestawiono w' tablicy 2.1.

Tablica 2.1

Numer zadania	Zakresy zmienności		Rozwiązanie optymalne			Optymalna wartość funkcji celu	Generowane zadania
	Si	*3	JC,	*2
1	[0, 5]	ro, 5j	2,667	2.667	0	16,000	2, 3
2	[0, 2]	[0, 51	2	2	0,286	15,714	4, 5
3	[3, 5]	to, 5]	zadanie sprzeczne			—
4	10. 2]	[0, 0]	2,333	2	0	13,000
5	10, 21	U. 51	0,333	0,333	1	15,000	' 6, 7
6	[0, 0]	II. 5,|	0	0	1,143	14,857	8, 9
7	U, 21	[1. 5]	zadanie sprzeczne			—
8	[0, 01	[l. U	0.167	0	1	13,500
9	[0, 0]	[2. 5]	zadanie sprzeczne			—

2.2.3. Reguły postępowania

w metodzie podziału i ograniczeń

Podsumowując dotychczasowe rozważania dotyczące metody podziału i ograniczeń, w przypadku maksymalizacji możemy sformułować reguły postępowania w przedstawionej wersji metody. W każdej iteracji wykonujemy następujące czynności:

/. Porządkowanie listy zadań zrelaksowanych.

Usuwamy z listy:

•    zadania, które zostały już podzielone,

•    zadania sprzeczne,

•    zadania niespełniające warunków całkowitoliczebności, dla których wartość funkcji celu jest mniejsza lub równa największej wartości funkcji celu zadań spełniających warunki całkowitoliczbowości.

Zadania, które pozostają na liście, nazywamy zadaniami aktywnymi.

2.    Sprawdzenie kryterium optymalności.

Rozwiązanie optymalne zadania zrelaksowanego jest jednocześnie rozwiązaniem wyjściowego zadania programowania całkowitoliczbowego. jeżeli spełnione są wszystkie warunki całkowitoliczbowości oraz na liście zadań nie ma już żadnego innego zadania aktywnego lub wszystkie pozostałe na liście zadania aktywne mają tę samą wartość funkcji celu i spełniają warunki całkowitoliczbowości.

3.    Wybór zadania do podziału.

Do podziału wybieramy to zadanie aktywne, które ma najlepszą wartość funkcji celu.

4.    Wybór zmiennej, względem której dokonujemy podziału.

Wybrane zadanie dzielimy względem dowolnej zmiennej, na którą nałożony został warunek całkowitoliczbowości i która w rozpatrywanym rozwiązaniu wybranego do podziału zadania nie spełnia tego warunku.

5.    Podział zadania wzglądem wybranej zmiennej.

Nowo otrzymane zadania różnią się od zadania wybranego do podziału (i wzajemnie między sobą) ograniczeniem dotyczącym zmiennej, względem której dokonano podziału. Przypuśćmy, że dokonano podziału względem zmiennej x, i w zadaniu wyjściowym ograniczenie na tę zmienną ma postać:

a < Xj < b.

Przypuśćmy dalej, że wartość zmiennej x, w rozwiązaniu dzielonego zadania ma wartość (niecałkowitą) c. Oznaczymy symbolem [c] największą liczbę całkowitą nie przekraczającą wartości c. Ponieważ c jest niecałkowite, zachodzi związek:

|c] < c < [c| + 1.

W pierwszym z dzielonych zadań ograniczenie dotyczące wartości xj przyjmuje postać:

a ^xj < [c], a w drugim: lc] + 1 < Xj b.

2.2.4. Zaokrąglanie rozwiązań

Można zapytać, czy dosyć skomplikowane postępowanie, jakie proponuje metoda podziału i ograniczeń jest niezbędne i czy nie byłaby wystarczająca metoda polegająca na zaokręgleniu zrelaksowanego zadania programowania liniowego do najbliższych liczb całkowitych. Na przykładzie prostego zadania, w którym występuje jeden warunek ograniczający, pokażemy, że postępowanie takie może prowadzić do błędnych wniosków.