112 113

Programowanie liniowe całkowitoliczbowe

Rysunek 2.6    Rysunek 2.7

112

Przykład 2.2

Należy rozwiązać zadanie:

3*1+ 3jt₂+ 13*3 —> max,

-3*,+ 6*,+ 7*j <8,

6*| -3*2+ 7*3 < 8,

*i >0,

0 ^*2 < 5,

0<*,<5,

*2. *3 — całkowite.

Tworzymy zadanie zrelaksowane. Ma ono postać:

Zadanie 1

3*| +3*2+13*3 —» max, - 3*! + 6*2 + 7*3 < 8,

6*i - 3*2 + 7*3 ^ 8,

*, >0,

0s$*₂ ^5,

0<*3 <5.

Rozwiązanie optymalne, które możemy uzyskać za pomocą prymalnej metody simpleks, jest następujące: *, = 2,667, *2 = 2,667, *, = 0.

Optymalna wartość funkcji celu wynosi 16.

Pokażemy przebieg kolejnych iteracji dla rozpatrywanego zadania.

i

Iteracja 1

Na liście rozpatrywanych zadań znajduje się zadanie 1. Nie spełnia ono wymaganych w rozwiązywanym przykładzie warunków całkowitoliczbowości, ponieważ wartość zmiennej x₂ w rozwiązaniu optymalnym nie jest całkowita. Jest to jedyne rozwiązanie znajdujące się na liście zadań, stąd wybieramy je jako zadanie przeznaczone do podziału i dokonujemy go względem zmiennej x₂ (rys. 2.8).

Rysunek 2.8

i.

-i-

2,667

Otrzymujemy w ten sposób następujące zadania:

3*i + 3*2 +	13*
-3*, + 6*2 +	7*,
+ fN 3 1 £	7*3
>0,
0sSjc2sS2,
Os:*,<5.

• max,

Zadanie 3

3*1 + 3*2 +	13*
— 3*i + 6*2 +	7*3
6*| -3*2 +	7*3
*i >o,
3 <*2<5,

max,

0 ^*3 <5.

Znajdujemy rozwiązania powyższych zadań. W zadaniu 2 mamy: jc, = 2, x₂-2, *₃ = 0,286.

Optymalna wartość funkcji celu wynosi 15,714. Z kolei stwierdzamy, że zadanie 3 jest sprzeczne.

Iteracja 2

Na liście rozpatrywanych zadań znajduje się zadanie I, zadanie 2 i zadanie 3. Porządkujemy listę zadań. Ponieważ zadanie 1 zostało już podzielone, usuwamy je z listy, usuwamy również zadanie 3, ponieważ jest sprzeczne, stąd nie mamy możliwości dokonywania jego dalszego podziału. Jedynym pozostałym na liście zadaniem jest zadanie 2. Nie spełnia ono wszystkieh warunków całkowitoliczbowości, nie możemy więc zakończyć procesu rozwiązywania i dlatego dokonamy jego podziału. Zmienna *₃ w rozwiązaniu zadania 2 nie spełnia warunków całkowitoliczbowości, dokonamy więc podziału tego zadania ze względu na tę zmienną (rys. 2.9).

Rysunek 2.9

X

X

- i 1

0 0,286