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

Метод гілок і меж — один з комбінаторних методів. На відміну від методу Гоморі застосовується як до повністю, так і частково цілочисельних задач. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються за певними ознаками корисними для знаходження оптимального рішення.

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

Читати повністю