Дерево розв’язків

Третій крок

Другий крок

Перший крок

1 задача 2 задача

Ця задача несумісна

Розгалуження здійснюємо по змінній х₂.

1 задача 2 задача

Отриманий план не є цілочисельним

Розгалуження здійснюємо в першій задачі по змінній х₁.

Четвертий крок

Розгалуження здійснюємо по змінній х₁ задачі другого кроку.

1 задача 2 задача

Ця задача несумісна.

3. ДРОБово - ЛІНІЙНЕ ПРОГРАМУВАННЯ (ДЛП)

Загальна постановка задач дробово-лінійного програмування (ЗДЛП)

Постановка ЗДЛП складається у визначенні оптимального значення функції:

(3.1)

при обмеженнях виду:

. (3.2)

Крім того, на змінні накладаються умови невід’ємності

. (3.3)

Очевидно, що в області невід’ємних значень змінних х.

Як і у випадку ЗЗЛП цільова функція (3.1) досягає свого оптимального значення в одній з вершин гіперопуклого багатогранного тіла. ОПР у цілому ЗДЛП визначається обмеженнями виду (3.2)-(3.3).

Очевидно, що якщо задача (3.1)–(3.3) має одну або дві змінні, то її можна розв’язувати в площині Х₁0Х₂ графічно.