Лабораторна робота № 6.

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

Мета роботи: пошук оптимального плану в задачах цілочисельного програмування (ЗЦП).

Теоретична частина.

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

(6.1)

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

Для ЗЦП не існує такого універсального ефективного методу вирішення, яким є симплекс-метод для ЗЛП. З точних методів вирішення відзначимо геометричний метод і комбінований метод гілок та меж.

Метод гілок і меж

Цей метод точного вирішення ЗЦП найчастіше використовується на практиці. Він полягає в наступному.

Спочатку вирішується ослаблена задача. Якщо отримане оптимальне рішення цілочислове, то ЗЦП вирішена. Якщо ж оптимальне рішення ЗЛП не є цілочисловим, то робимо "розгалуження" у такий спосіб. Нехай змінна х_s прийняла в оптимальному рішенні значення q_s, що не є цілим. Тоді розглядаємо дві ЗЦП. Перша виходить додаванням обмеження х_s<=[q_s], друга – додаванням обмеження х_s>=[q_s] + 1, де [q_s] - ціла частина числа q_s .

Кожна із цих двох задач аналогічним способом може розбитися ще на дві задачі і т.д.

Якщо в результаті вирішення якої-небудь із задач виходить цілочисловий оптимальний план, то значення А цільової функції при цьому плані відіграє роль "межі": якщо в результаті вирішення чергової ЗЛП з'ясується, що оптимальне значення цільової функції "гірше" А, тоді така задача "не гілкується".

Практична частина

Вирішити наступні ЗЦП геометрично:

Задача1 Задача2