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

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

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

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

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

Цілочисельне програмування — це розділ математичного програмування, який використовує змінні лише у цілочисельному вигляді. З математичної точки зору, задачі такого типу можуть бути лінійними або нелінійними. Розглянемо лінійну задачу цілочисельного програмування, для якого запишемо наступну математичну модуль:

Цілочисельне програмування

де Цілочисельне програмування — цілі числа. Виходячи з (1) бачимо, що зовнішній вигляд задачі лінійного цілочисельного програмування практично не відрізняється від задачі лінійного програмування, за вийнятком того, що на розв'язок задачі лінійного програмування накладається додаткове обмеження: визначення лише цілих значень змінних. Припустимо, що ми розв'язали деяку задачу лінійного програмування, не враховуючи вимогу цілочисельності, і отримали наступний многокутник розв'язків ABCDО.

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