Комбінаторні методи. Метод гілок та меж

В основі комбінаторних методів є перебір можливих варіантів розв’язків поставленої задачі. Для розв’язування задач цілочис-лового програмування ефективнішим за метод Гоморі є метод гілок і меж. Спочатку, як і в разі методу Гоморі, симплексним методом розв’язується послаблена (без умов цілочисловості) за-дача. Потім вводиться правило перебору.

Нехай потрібно знайти Неможливо розібрати вираз (невідома помилка): x_j

— цілочислову змінну, значення якої Неможливо розібрати вираз (невідома помилка): x_j= x'_j
в оптимальному плані послабленої задачі є дробовим. Очевидно, що в деякому околі даної точки також не існує цілочислових значень, тому відповідний проміжок можна виключити з множини допустимих планів задачі в подальшому розгляді. Та-ким проміжком є інтервал між найближчими до Неможливо розібрати вираз (невідома помилка): x'_j
цілочисловими значеннями. Можна стверджувати, що на інтервалі Неможливо розібрати вираз (невідома помилка):  \left [ \left [ x'_j \right ] ; \left [ x'_j \right ] + 1 \right ] 

цілих значень немає.

Наприклад, якщо Неможливо розібрати вираз (невідома помилка): x'_j = 2,7

дістаємо інтервал \left [ 2;3 \right ] , де, очевидно, немає Неможливо розібрати вираз (невідома помилка): x_j
, яке набуває цілого значення і оптимальний розв’язок буде знаходитися або в інтервалі Неможливо розібрати вираз (невідома помилка): x_j \le 2

, або Неможливо розібрати вираз (невідома помилка): x_j \ge 3

Виключення проміжку \left [ 2;3 \right ] з множини допустимих планів здійснюється введенням до системи обмежень початкової задачі додаткових нерів¬ностей. Тобто допустиме ціле значення Неможливо розібрати вираз (невідома помилка): x_j
має задовольняти одну з нерівностей виду:

Неможливо розібрати вираз (невідома помилка): x_j \le \left [ x'_j \right ]

або Неможливо розібрати вираз (невідома помилка): x_j \ge \left [ x'_j \right ] +1

Дописавши кожну з цих умов до задачі з послабленими обме-женнями, дістанемо дві, не пов’язані між собою, задачі. Тобто, початкову задачу цілочислового програмування поділимо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими. Це означає, що симплекс-методом розв’язуватимемо дві такі задачі:

перша задача:

Неможливо розібрати вираз (невідома помилка): \max \,(\min )\,\,F=\sum\limits_{j=1}^n {c_{j} x_{j} }

за умов:

Неможливо розібрати вираз (невідома помилка): \sum\limits_{j=1}^n {a_{ij} x_{j} } \left\{ {\begin{array}{l} \le \\ = \\ \ge \\ \end{array}} \right\}b_{i} \quad \left( {i=\overline {1,m} } \right);

Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0 \quad \left( {j=\overline {1,n} } \right);

Неможливо розібрати вираз (невідома помилка): \ \quad x_{j}

- цілі числа  Неможливо розібрати вираз (невідома помилка): \left( {j=\overline {1,n} } \right);

Неможливо розібрати вираз (невідома помилка): x_j \le \left [ x'_j \right ]

друга задача:

Неможливо розібрати вираз (невідома помилка): \max \,(\min )\,\,F=\sum\limits_{j=1}^n {c_{j} x_{j} }

за умов:

Неможливо розібрати вираз (невідома помилка): \sum\limits_{j=1}^n {a_{ij} x_{j} } \left\{ {\begin{array}{l} \le \\ = \\ \ge \\ \end{array}} \right\}b_{i} \quad \left( {i=\overline {1,m} } \right);

Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0 \quad \left( {j=\overline {1,n} } \right);

Неможливо розібрати вираз (невідома помилка): \ \quad x_{j}

- цілі числа  Неможливо розібрати вираз (невідома помилка): \left( {j=\overline {1,n} } \right);

Неможливо розібрати вираз (невідома помилка): x_j \ge \left [ x'_j \right ]