На головну сторінку
целочисленное програмування
В кінець сторінки
13. Цілочисельне програмування
Целочисленное програмування - один з наймолодших, перспективних і швидко розвиваються розділів математичного програмування. Можна перерахувати велику кількість різноманітних завдань планування економіки, організації виробництва, дослідження конфліктних ситуацій, синтезу схем автоматичного регулювання, які формально зводяться до вибору кращих, в деякому сенсі, значень параметрів з певною дискретної сукупності заданих величин. До них можна віднести і екстремальні комбінаторні задачі, що виникають в різних розділах дискретної математики.
Завдання і методи, що відносяться до перерахованого кола питань, в літературі називають по-різному. Найбільшого поширення набув термін «целочисленное програмування», однак зустрічаються і такі як «дискретне програмування», рідше «комбинаторное (або диофантово) програмування».
Найбільш вивченими завданнями цього класу є цілочисельні завдання лінійного програмування, в яких на всі змінні (або на їх частину) накладено додаткову вимогу целочисленности. Від них прийнято відрізняти так звані дискретні задачі лінійного програмування, в яких область допустимого зміни кожної змінної - не безлічі цілих невід'ємних чисел, а деякий заданий кінцевий безліч.
Цілочисельні завдання математичного програмування можуть виникати різними шляхами.
1. Існують завдання лінійного програмування, які формально до цілочисельним не належать, але при відповідних вихідних даних завжди мають цілочисельним планом. Приклади таких завдань - транспортна задача і її модифікації (задачі про призначення, про потоках в мережах).
2. Поштовхом до вивчення цілочисельних задач у власному розумінні слова стало розгляд завдань лінійного програмування, в яких змінні представляли фізично неподільні величини. Вони були названі завданнями з неделимостью. Такі, наприклад, завдання про оптимізацію комплексу засобів доставки вантажів, про знаходження мінімального порожнього пробігу автомобілів при виконанні заданого плану перевезень, про визначення оптимального машинного парку і його оптимального розподілу по вказаних робіт за умови мінімізації сумарної вартості (машинного парку і виконуваних робіт), про знаходженні мінімальної кількості судів для здійснення даного графіка перевезень і т. п.
3. Іншим важливим поштовхом до побудови теорії цілочислового програмування став новий підхід до деяких екстремальних комбінаторних задач. У них потрібно знайти екстремум целочисленной лінійної функції, заданої на кінцевому безлічі елементів. Такі завдання прийнято називати завданнями з альтернативними змінними. Як приклади можна назвати завдання комівояжера (бродячого торговця), про оптимальний призначення, теорії розкладу, або календарного планування, і завдання з додатковими логічними умовами (наприклад, типу «або - або», «якщо - то» і т. П.) .
Історично першим завданням целочисленного типу є опублікована в 1932 р угорським математиком Е. Егерварі завдання про призначення персоналу. У 1955 р на Другому симпозіумі по лінійному програмуванню була розглянута задача про бомбардувальнику, відома як завдання про ранці.
Наведемо приклади цілочисельних задач лінійного програмування.
Приклад. Завдання про ранці. Є m вектор обмежених ресурсів 
, Які можна використовувати для перевезення різних за своїми характеристиками вантажів. Кожен j -й вантаж 
має такі властивості: 1) неподільність; 2) корисністю 
; 3) витратою i -го ресурсу для перевезення одиниці j -го вантажу 
. Вибрати такий номер вантажу для перевезення, при якому максимізується загальна корисність рейсу (сумарна вартість перевезених за рейс вантажів).
Складемо математичну модель задачі. позначимо через 
кількість обраних для траспортування предметів. Вимогу неподільності відповідає умова
цілі, 
(13.1)
Зіставлення витрат ресурсів кожного типу для транспортування одиниці вантажу і їх наявності призводить до обмеження
(13.2)
Загальна корисність рейсу визначається значенням функції
. (13.3)
Окремим випадком завдання (13.1) - (13.2) є завдання про ранці, в якій будь-який із заданого набору предметів 
може бути обраний чи ні. Тоді математична модель прийме наступний вигляд:
максимізувати
за умов
Приклад. В області
знайти максимум функції 
.
Вирішимо задачу геометрично (рис. 13.1). Область пошуку екстремуму - багатокутник OABCD. Так як лінія рівня цільової функції паралельна стороні BC багатокутника, екстремум досягається у вершинах 
і 
, А також в будь-якій точці відрізка BC і дорівнює 7. Нас цікавлять лише точки з цілочисельними координатами, тому ні B, ні C не є допустимим рішенням задачі. Округливши значення координат точок B і C, отримаємо точку (4; 3), що не належить області пошуку. Легко показати, що цілочисельний оптимум досягається в точках M (2; 3) і N (3; 2) і дорівнює 5. Обидві точки знаходяться всередині області пошуку.
малюнок 13.1
Неспроможність округлення підкреслюється також такими міркуваннями. Незважаючи на те, що цілочисельні змінні звичайно виражають кількість неподільних предметів, можливі й інші типи специфікації цих змінних. Так в задачі про ранці рішення представляється булевої змінної 
(X = 0 або x = 1). У цьому випадку немає сенсу оперувати дробовими значеннями величини x і процедура округлення є логічно неприйнятною.
З наведеного прикладу видно, що для вирішення задач цілочисельного програмування необхідно розглянути особливі методи оптимізації. Крім того, оптимальне рішення задач цілочисельного програмування не обов'язково належить кордоні багатогранника (багатокутника) умов, що характерно для задач лінійного програмування.
назад На початок сторінки вперед
