Особливості методу

1. Безпосередньо з алгоритму необхідно, щоб метод гілок і границь застосовувався як для задач повністю цілочисельного програмування, так і для задач частково цілочисельного програмування.

2. Для даного методу несуттєва проблема помилок округлення.

3. Геометрична інтерпретація методу: гіперплощина, що визначається функцією мети задачі, переміщається в середину області припустимих рішень до зустрічі з найбільш близьким цілочисельним планом (див. мал.).

4. Нові обмеження виду , відіграють роль розсічень ОПР.

5. Коли вводять нові обмеження зазначеного типу, то немає необхідності розв’язувати ЗЛП заново, а можна скористатися попередньою ітерацією, уводячи нові обмеження. Розглянемо приклад.

Приклад. Вирішити ЦЗЛП методом гілок і границь.

Зобразимо ОПР задачі.

Визначимо координати точки А.

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

D = –9; D₁ = –39; D₂ = –24;

Таким чином, F(А) = F (13/3, 8/3) = 7.

Визначимо координати точки В.

Таким чином, F(В) = F (40/9, 23/9) = 7.

Процедура розгалуження здійснюється відповідно до співвідношень

Вихідна задача розпадається на дві:

Дата добавления: 2014-11-25