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

Розділ математичного програмування, що вивчає задачі, в яких на значення всіх (або частини) змінних величин накладено вимогу цілочисловості, називається цілочисловим програмуванням. Серед задач цілочислового програмування найбільш вивчені задачі лінійного цілочислового програмування.

Математична модель ЗЦЛП формулюється так: знайти екстремум (мінімум або максимум) цільової функції

при умовах (i = 1,2,…..,m), x_j ≥0 (j=1,2,…,n), x_j – ціле (j=1,2,…,n_e ; n_e ≤n).

Якщо n_e < n, то задача називається частково цілочисловою; якщо n_e=n, то повністю цілочисловою.

При n=2 ЗЦЛП можна розв’язувати геометрично.

Наприклад,математична модель задачі має вигляд:

цілі числа.

Побудуємо чотирикутник ОАBD (рис.1) розв’язків задачі

Рис. 1. Геометричне розв'язування ЗЦЛП.

Пряма, перпендикулярна вектору = (с₁,с₂) = (3;1), виходить з даної області через точку В(5; ) (х₂ = – не ціле число). Щоб знайти цілочисловий розв’язок задачі, замість області ОАBD розглянемо заштрихований многокутник, вершини якого мають цілочислові координати і належать області OABD, знаходячись якнайближче до точок її границі АВ: М(1;3), N(2;3), Р(3;2), L(5;2). Цілочисловий оптимальний розв’язок дає точка L(5;2), яка є точкою «виходу» з області OAMNPLD прямої, перпендикулярної вектору .

При цьому значення цільової функції становитиме 3∙5+1∙2=17 (грошових одиниць).

При розв’язуванні ЗЦЛП користуються методом Гоморі – методом відтинань (вперше цей метод був запропонований у 1958 р.).

Розглянемо метод Гоморі для розв’язування повністю цілочислових задач лінійного програмування. Нехай задача розв’язана симплекс – методом, Х⁰ – її оптимальний план. Одержавши останню симплекс – таблицю, вибираємо максимальну дробову частину компоненти Х⁰ та складаємо по відповідному рядку додаткове обмеження. В це обмеження вводимо додаткову змінну х_n+1 (х_n+1 ≥0), множимо обмеження на (-1) та дописуємо його до симплекс – таблиці. Змінна х_n+1 буде базисною. Одержавши розширену таблицю, зауважуємо, що в стовпчику вільних членів є від’ємне число. Для розв’язування розширеної задачі виконуємо такі операції:

1) Переглядаємо рядок, що містить від’ємне число в стовпчику вільних членів, та вибираємо будь-яке від’ємне число в цьому рядку. Вибране число визначає ключовий стовпчик.

2) Для чисел з однаковими знаками складаємо симплексне відношення.

3) Найменше симплексне відношення визначає ключовий рядок. На перетині ключового рядка і ключового стовпчика стоїть генеральний елемент.

4) Виконуємо звичайні симплекс – перетворення.

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

Схематично розв’язок сформульованої вище задачі методом віток і меж показано на рис. 2.

Рис. 2. Розв’язок задачі методом віток і меж.