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

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

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

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

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

Многокутник ровз'язків задачі лінійного програмування

Якщо до даного розв'язку застосувати умову цілочисельності, то в результаті розв'язком для задачі цілочисельного програмування буде многокутник KLMNPO, в якому цілі числа позначено точками:

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

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

Зауваження: округленням лінійного розв'язку неможливо отримати цілочисельне рішення.

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

Для розв'язку задач такого типу існує декілька методів, які можна поділити на дві групи:

  1. Метод відсічень (відсікаючих прлощин; метод Гоморі).
  2. Комбінаторні методи (метод гілок та меж; аддитивний метод з бінарними змінними).

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар