Меню
Головна
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

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

Цілочисельним (іноді його називають також дискретним) називається програмуванням розділ математичного програмування, що вивчає екстремальні задачі, в яких на шукані змінні накладається умова целочисленности, а область допустимих рішень скінченна. Вивчення цього розділу в курсі "Економіко-математичні методи і прикладні моделі" викликається тим, що величезна кількість економічних завдань носить дискретний, найчастіше цілочисельний характер, що пов'язано, як правило, з фізичної неделимостью багатьох елементів розрахунку: наприклад, не можна побудувати два з половиною заводу, купити півтора автомобіля і т. д. В ряді випадків такі завдання вирішуються звичайними методами, наприклад симплексним методом, з послідуючим округленням до цілих чисел. Однак такий підхід виправданий, коли окрема одиниця складає дуже малу частину всього обсягу (наприклад, товарних запасів); в іншому випадку він може внести значні спотворення в дійсно оптимальне рішення. Тому розроблені спеціальні методи розв'язування цілочислових задач, серед яких можна виділити два напрямки: методи відсікання (відсікаючих площин) і комбінаторні методи.

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

Розглянемо більш детально один з методів відсікаючих площин, відомий як метод Гоморі. Метод Гоморі для лінійних задач цілочислового програмування заснований на понятті конгруентності дійсних чисел. Будь-яке дійсне число можна представити у вигляді суми цілої і дробової частин: х = [x] + {x} де квадратні дужки означають цілу частину, а фігурні - дробову. Наприклад, 7,5 = [7,5] + {7,5} = 7 + 0,5. Невід'ємні числа (для простоти ми будемо розглядати тільки їх) називаються конгруэнтными, якщо рівні їх дробові частини. Якщо позначати конгруентність чисел символом " ≡", то, наприклад, 7,5 ≡ 0,5; 6,3 ≡ 2,3; зокрема, всі цілі числа конгруентний нулю, тому умова целочисленности змінної х можна записати: хi = 0.

За методом Гоморі перший етап розв'язування цілочислових задач не відрізняється від звичайного розрахунку по симплексному алгоритмом. Якщо серед значень змінних в оптимальному плані є дробові, то складається додаткове обмеження, що відтинає дробову частину рішення, але залишає в силі всі інші умови, яким повинен задовольняти оптимальний план. Це додаткове обмеження приєднується до вихідних обмежень завдання, і знову застосовується процедура симплексного методу. Алгоритм Гоморі дозволяє прийти до оптимального целочисленному рішенням за кінцеве число кроків.

Приклад 3.6. Нехай для придбання обладнання, що розміщується на виробничій площі 38 м2, фірма виділяє 20 млн руб. Є одиниці обладнання двох типів: типу А вартістю 5 млн руб., що вимагає виробничу площу 8 м2 і має продуктивність 7 тис. од. продукції за зміну, і типу Б - вартістю 2 млн руб., займає площу 4 м2 і дає за зміну 3 тис. од. продукції. Потрібно розрахувати оптимальний варіант придбання устаткування, що забезпечує максимум продуктивності ділянки.

Рішення. Сформулюємо економіко-математичну модель задачі. Нехай х1, х2 - кількість придбаних машин типу А та типу Б відповідно. Тоді цільова функція задачі матиме вигляд

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

Сформульована задача лінійного цілочислового програмування.

Введемо додаткові змінні х4, з допомогою яких вихідні нерівності перетворюються в рівності:

з яких випливає, що змінні х1, х2 можуть приймати тільки невід'ємні цілочисельні значення. Фрагмент симплексного таблиці на останній ітерації (без урахування целочисленности) наведено в табл. 3.15.

Таблиця 3.15

Базисні

змінні

План

x1

x2

x3

x4

x1

1

1

0

1

-0,5

x2

7,5

0

1

-2

1,26

29,5

0

0

1

0,25

Звідси видно, що в оптимальному плані х1, = 1; х2 = 7,5 і максимум цільової функції дорівнює

Для нецелочисленной змінної х2 складаємо з наведеної симплексним табл. 3.15 рівняння:

звідки

Так як х2 - ціле число, то цілою повинна бути і права частина останнього рівняння ("=" - символ конгруентності):

звідси можна отримати, що

тобто вираз 0,25х4 може дорівнювати 0,5, або 1,5 або 2,5 і т. д. Отже, з'являється додаткове обмеження: 0,25х4 > 0,5, яке шляхом введення додаткової негативної цілочисельної змінної х5 перетворюється в рівність, так що система обмежень вихідної задачі в канонічному вигляді містить три рівняння:

Повторивши процес вирішення симплексним методом для даної розширеної системи обмежень, отримаємо новий оптимальний план, в якому змінні, що входять в базис, приймають цілі значення: х1 = 2; х2 = 5; х 4 = 2. Таким чином, придбання двох машин типу А і п'яти машин типу Б забезпечує максимум продуктивності ділянки, рівний 29 тис. од. продукції в зміну. Зауважимо, що якщо б в якості плану був обраний варіант, що отримується в результаті округлення початкового рішення задачі симплексним методом (x1 = 1; x2 = 7), то сумарна продуктивність була б дорівнює лише 28 тис. од. продукції.

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

Математично такі задачі відносяться до того самого типу розподільчих завдань, що і розглянута в параграфі 3.2 транспортна задача, з тією особливістю, що в них обсяги готівки та необхідних ресурсів для виконання кожної роботи дорівнюють одиниці (ai = bj = 1), а всі змінні xij: або рівні одиниці, якщо i-й працівник призначений на j-ту роботу, або дорівнюють нулю в інших випадках. Вихідні дані задачі про призначення групуються в таблиці, яка називається матрицею оцінок, а результати - у матриці призначень.

Задача про призначення в загальному вигляді може бути сформульована наступним чином. Є п працівників, які можуть виконувати п робіт, причому використання г-го працівника j-ї роботи, наприклад, приносить дохід зij. Потрібно доручити кожному з працівників виконання однієї цілком визначеної роботи, щоб максимізувати у даному випадку сумарний дохід.

Введемо змінні:

Завдання полягає в тому, щоб знайти розподіл X = (Xjj) працівників з робіт (тобто знайти матрицю призначень), яке максимізує цільову функцію

(3.22)

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

(3.23)

(3.24)

причому xij дорівнює або 0, або 1 (так звані булеві змінні) для всіх i,j = i,n.

Обмеження (3.23) відбивають умову того, що за кожним працівником може бути закріплена лише одна робота, а обмеження (3.24) означають, що для виконання кожної роботи може бути виділений тільки один працівник.

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

Інший завданням подібного роду є задача про комівояжера, яка може бути сформульована наступним чином. Є п міст, пронумерованих числами від 1 до п. Комівояжер, виїжджаючи з міста 1, повинен побувати в кожному місті рівно один раз і повернутися у вихідний пункт. Нехай відомі відстані зij між містами (i,j = 1,n; i j). Потрібно знайти найкоротший маршрут.

Введемо змінні:

Вимога одноразового в'їзду до міста і виїзду з них запишеться у вигляді наступних обмежень:

(3.25)

Однак обмеження (3.25) повністю не визначають припустимі маршрути, так як не виключають можливості розриву шляху, тобто появи декількох не пов'язаних між собою подмаршрутов для частини міст. Тому слід ввести додатково п змінних іi (іi (i = 1, п), приймають тільки цілі невід'ємні значення, і записати для них спеціальні обмеження:

(3.26)

Загальне число таких обмежень одно (п - 1) · (n - 2), і вони, не виключаючи допустимий маршрут, виключають можливість існування подмаршрутов.

Таким чином, задача про комівояжера полягає в мінімізації цільової функції:

(3.27)

при умовах (3.25), (3.26)де змінні Ху, і, приймають тільки невід'ємні цілі значення.

До задач цілочислового програмування призводять також багато оптимальні задачі теорії розкладів, в якій розглядаються методи оптимізації оперативно-календарного планування. В якості прикладу таких завдань можна привести задачу визначення оптимальної черговості обробки виробів на різних верстатах чи інших робочих місцях, завдання складання програми "диспетчер" для управління роботою ЕОМ в мультипрограммном режимі та ін.