118 119

I 18 Programowanie liniowe całkowitoliczbowe

Przykład 2.3

Należy rozwiązać zadanie:

/(jc,, jc₂) = 21 jc, + 1 ]x₂ —» max,

7jc, + 4x₂ < 13,

*1, jc₂ ^ 0, jC], x₂ — całkowite.

Po dokonaniu relaksacji zadania otrzymujemy następujący problem:

21x, + 1 1jc₂ —» max. : j

7jc, +4x₂ ^ 13,

x,, jc₂ ^ 0.

Rozwiązanie zadania zrelaksowanego uzyskane metodą geometryczną przedstawiono na rys. 2.12. Rozwiązaniem optymalnym jest wierzchołek /4(^l3/₇, 0). Nie jest to rozwiązanie całkowitoliczbowe. Najbliższym rozwiązaniem o współrzędnych całkowitych jest punkt C(2, 0), który jednak, jak widać na rys. 2.13 (na którym przedstawiono rozwiązania dopuszczalne zadania wyjściowego), nie jest rozwiązaniem dopuszczalnym rozpatrywanego zadania.

Zaokrąglenie współrzędnej x, rozpatrywanego rozwiązania w dól daje punkt D(l, 0). Porównując wartości funkcji celu w punktach A oraz D, otrzymujemy:

f(A) = 39, /(D) = 21,

Rysunek 2.12 Rysunek 2.13

▲ A

X₂ *2

C₄ (0,3)1h

c₃( 0.2)0- \

C₂(0,1)O- C,(1,1)»\

>• 0(0.0)

—A-x—A—

0(1.0) \ C(2,0)

widzimy zatem, że wartość funkcji celu po dokonaniu zaokrąglenia zmiennej x, spadla prawie o połowę w porównaniu z wartością w rozwiązaniu optymalnym zadania zrelaksowanego.

Rozpatrzymy teraz kolejno rozwiązania dopuszczalne zadania wyjściowego. Są to punkty o współrzędnych całkowitych przedstawione na rys. 2.13. Obliczając wartości funkcji celu w tych punktach, otrzymujemy:

/(0,0) = 0, /(0.1)= 11, /(O, 2) = 22, /(O, 3) = 33, /(1, 0)=21, /(1, 1) = 32.

Po porównaniu otrzymanych wartości widzimy, że najlepszą, czyli największą, wartość, która wynosi 33, funkcja celu osiąga w punkcie (0, 3). Wartość ta jest więc o ponad połowę lepsza od wartości funkcji celu w punkcie (1.0) otrzymanym w wyniku zaokrąglenia rozwiązania zadania zrelaksowanego. Na rys. 2.13 pokazano ponadto, że rozwiązanie optymalne zadania całkowitoliczbowego znajduje się w rzeczywistości w innej części obszaru dopuszczalnego niż ta, którą byliśmy skłonni rozpatrywać, dokonując zaokrągleń.

Powróćmy ponownie do przykładu 2.2 i przyjrzyjmy się skutkom zaokrąglania rozwiązań w stosunku do rozwiązania zadania 1, które jest następujące:

= 2,667, x₂ = 2,667, x₃ = 0.

Zaokrąglenia wymaga jedynie zmienna x₂. Zaokrąglając zmienną x₂ zarówno w górę do wartości 3, jak i w dół do wartości 2, otrzymujemy wartości funkcji celu równe, odpowiednio, 17 i 14, a więc lepsze od wartości otrzymanej jako rozwiązanie zadania 8. Zauważmy jednak, że rozwiązania te leżą poza zbiorem rozwiązań dopuszczalnych, gdyż w pierwszym przypadku nie jest spełnione ograniczenie:

- 3ri + 6x₂ + 7x, sC 8,

a w drugim — ograniczenie:

6x, - 3x₂ + lx₃ < 8.

Widać zatem, że metoda zaokrąglenia nie pozwala wygenerować w tym przypadku żadnego rozwiązania dopuszczalnego.

2.3. Metoda cięć

Do znalezienia rozwiązania optymalnego wyjściowego czystego zadania programowania całkowitoliczbowego można wykorzystać rozwiązanie niecałkowi-toliczbowe zadania zrelaksowanego w sposób odmienny od opisanego w metodzie podziału i ograniczeń. W tablicy simpleksowej identyfikujemy ograniczenie,