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

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

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

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

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