Приклад 6.3. Методом віток і меж розв'язати задачу лінійного цілочислового програмування

Приклад 6.3. Методом віток і меж розв'язати задачу лінійного цілочислового програмування

Розв'язування. Множину планів задачі позначимо через . Процес розв'язування задачі проілюструємо геометрично.

Рисунок 6.1

Рисунок 6.2

Рисунок 6.3

Рисунок 6.4

Розв'язуючи послаблену задачу до задачі на площині (рис.6.1), одержуємо оптимальний план (0;7/2). Верхня оцінка

Оскільки змінна х2 = 7/2— дробова, то у цілочисловому розв'язку її слід зменшити до [7/2] = 3, або збільшити до [7/2] +1 = 4.

початкова множина планів розбивається на дві підмножини

,

.

Знайдемо розв'язок таких двох задач лінійного програмування:

(6.11) (6.12)

Цільова функція задачі (6.11) досягає максимального значення в точці (1/2;3), а задача ЛП (6.12) розв'язку немає (рис. 6.2). Оцінками множин , та , є відповідно , та . Для продовження процесу розв'язування задачі розіб'ємо множину на дві підмножини , та (рис. 6.3), де

,

Тепер розв'яжемо такі дві задачі лінійного програмування:

(6.13) (6.14)

Як бачимо з рис. 6.3, оптимальним планом задачі (3.13) є (0;3), а оптимальним планом задачі (6.;5/2). Оцінкинки множин , та відповідно дорівнюють: , та . Оскільки змінна х2 - дробова, то розбиваємо на дві підмножини (рис. 6.4). Цим підмножинам відповідають такі дві задачі лінійного програмування:

(6.15) (6.16)

Як бачимо з рис. 6.4, множина планів задачі (6.16) є порожньою, .і оптимальним планом задачі (6.15) є Х3 =(3/2;2), і оцінкою 11/2.

Оскільки 11/26 то на цьому розв'язування цілочислової задачі лінійної и програмування припиняється й робимо висновок, що

Х*=(0;3),Lmax=6

оптимальний цілочисловий план задачі. Процес розгалуження показано на рис.6.5.

Рисунок 6.5