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

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

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

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

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

Двоїста задача лінійного програмування

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

120

при обмеженнях:

216

39

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

« Попередня сторінка