Цілочисленне програмування
Розділ математичного програмування, вивчає екстремальні завдання, у яких шукані змінні накладається умова цілісності, а область допустимих рішень кінцева. Метод Гоморі та його застосування. Циклічний алгоритм програмування.
Надіслати свою гарну роботу до бази знань просто. Використовуйте форму нижче
Студенти, аспіранти, молоді вчені, які використовують базу знань у своєму навчанні та роботі, будуть вам дуже вдячні.
Розміщено наhttp://www.allbest.ru/
Федеральна державна освітня бюджетна установа вищої освіти
при Уряді України
Кафедра "Математика та інформатика"
Напрямок: Державне та муніципальне управління
Викладач: ст. пр. Рязанцева Є.А.
Студент: Кирина Валерія Андріївна
При розгляді цілого ряду завдань фінансового менеджменту та бізнесу необхідно враховувати вимогу цілісної кількості змінних, що використовуються. Такі завдання називаються завданнями цілісного програмування.
Під завданням цілісного програмування (ЦП) розуміється завдання, у якій всі або деякі змінні повинні набувати цілих значень. У тому випадку, коли обмеження і цільова функція задачі є лінійними залежностями, завдання називають цілою задачею лінійного програмування. В іншому випадку, коли хоча б одна залежність буде нелінійною, це буде цілою задачею нелінійного програмування. Особливий інтерес до завдань ЦП викликаний тим, що у багатьох практичних завданнях необхідно знаходити цілечисленне рішення через дискретність низки значень змінних, що шукаються.
Цілочисленне програмування виникло в 50-60-ті роки ХХ століття з потреб практики - головнимчином у роботах американських математиків Дж. Данцига та Р. Гоморі. Спочатку цілісне програмування розвивалося незалежно від геометрії чисел на основі теорії та методів математичної оптимізації, насамперед лінійного програмування. Проте, останнім часом дослідження у цьому напрямі дедалі частіше проводяться засобами математики цілих чисел.
Завдання такого типу дуже актуальні, оскільки до їх вирішення зводиться аналіз різноманітних ситуацій, що виникають в економіці, техніці, військовій справі та інших сферах. З появою ЕОМ (електронна обчислювальна машина), зростанням їхньої продуктивності підвищився інтерес до завдань такого типу і до математики в цілому.
Цілочисленне програмування. Основні поняття.
При розгляді цілого ряду завдань фінансового менеджменту та бізнесу необхідно враховувати вимогу цілісної кількості змінних, що використовуються. Такі завдання називаються задачами цілісного програмування.
Цілочисленним (іноді його називають також дискретним) програмуванням називається розділ математичного програмування, вивчає екстремальні завдання, у яких шукані змінні накладається умова цілісності, а область допустимих рішень кінцева. Величезна кількість економічних завдань носить дискретний, найчастіше цілий характер, що пов'язано, як правило, з фізичною неподільністю багатьох елементів розрахунку: наприклад, не можна побудувати два з половиною заводи, купити півтора автомобіля і т.д. У ряді випадків такі завдання вирішуються звичайними методами, наприклад, симплексним методом, з наступним заокругленням до цілих чисел. Однак такий підхід виправданий, коли окрема одиниця становить дуже малу частину всього обсягу (наприклад, товарних запасів); в іншому випадку він може внести значніспотворення дійсно оптимальне рішення. Тому розроблено спеціальні методи вирішення цілих завдань.
Рекомендації з формулювання та рішення ЦП:
1.Кількість цілих змінних зменшувати наскільки можливо. Наприклад, цілі перемінні, значення яких має бути не менше 20, можна розглядати як безперервні;
2.На відміну від загальних завдань ЛП, додавання нових обмежень, що особливо включають цілочисленні змінні, зазвичай зменшують час вирішення завдань ЦП;
3.Якщо немає гострої необхідності знаходження точного оптимального цілочисельного рішення, що відрізняється від безперервного рішення, наприклад, 3%. Тоді реалізацію методу гілок та кордонів для завдання максимізації можна закінчувати, якщо відношення різниці між верхньою та нижньою межами до верхньої межі менше 0,03.
Метод гілок та кордонів можна застосовувати для вирішення задач нелінійного програмування.
Одним із методів вирішення завдань лінійного цілісного програмування є метод Гоморі. Сутність методу полягає у побудові обмежень, що відсікають нецілочисленні рішення задачі лінійного програмування, але не відсікають жодного цілочисельного плану.
Розглянемо алгоритм розв'язання задачі лінійного цілісного програмування цим методом.
1. Вирішуємо задачу симплексним методом без урахування умови цілісності. Якщо всі компоненти оптимального плану цілі, він є оптимальним й у завдання целочисленного програмування. Якщо виявляється нерозв'язність задачі, то й нерозв'язна задача цілого програмування.
2. Якщо серед компонент оптимального рішення є нецілі, то до обмежень завдання додаємо нове обмеження, яке має такі властивості:
- воно має бути лінійним;
- повинно відсікати знайдений оптимальний нецілочисленний план;
-не повинно відсікати жодного цілісного плану.
Для побудови обмеження вибираємо компонент оптимального плануз найбільшою дробовою частиноюі за відповідним цим компонентним рядком симплексної таблиці записуємо обмеження Гоморі.
найближче ціле не перевищує xj і zj відповідно.
3. Складене обмеження додаємо до наявних у симплексної таблиці, тим самим отримуємо розширене завдання. Щоб отримати опорний план цього завдання, необхідно ввести в базис той вектор, для якого мінімальна величина. І якщо для цього вектора величина = min, то виходить по додатковому рядку, якщо zkj 0, то в наступній симплексної таблиці буде отриманий опорний план. Якщо ж величина і не відповідає додатковому рядку, необхідно переходити до М-задачі (вводити штучну змінну в обмеження Гоморі).
4. Вирішуємо за допомогою звичайних симплексних перетворень отримане завдання. Якщо розв'язання цього завдання призводить до цілісного оптимального плану, то завдання, що шукається, вирішено. Якщо ми отримали нецілочисленне рішення, то знову додаємо одне додаткове обмеження і процес обчислень повторюється. Виконавши кінцеве число ітерацій, або отримуємо оптимальний план завдання цілісного програмування, або встановлюємо її нерозв'язність.
Метод гілок та кордонів
Вперше метод гілок і кордонів був запропонований Ландом і Дойгом в 1960 для вирішення загальної задачі цілісного лінійного програмування (Land A.H., Doig A.G.).
Алгоритм методу гілок та кордонівє ефективну процедуру перебору всіх цілих допустимих рішень.
Вирішується вихідне завдання ЛП за умови безперервності змінних.
Якщо всі коріння рішення нецілочисленні (у протилежному випадку - оптимальне цілочислове рішення знайдено), робимо розгалуження задачі на дві, для кожної із завдань вводимо додаткові обмеження по одній зі змінних xiai, xibi, де ai - найбільше ціле, що не перевищує xi, а bi - найменше ціле, більше xi, наприклад, при корені вихідної задачі x2=2.3 дод. обмеження в одній галузі буде x22, а по іншій - x23.
Знову вирішуються завдання в обох гілках з накладенням наступних обмежень за іншими змінними. На кожному кроці перевіряється цілісність коренів.
Гілку вважають тупиковою, якщо:
а) допустиме рішення чергового завдання ЛП відсутнє;
б) поточне рішення (значення цільової функції) гірше вже знайденого цілого рішення; математичний програмування алгоритм
в) поточне завдання ЛП є підзавданням раніше розрахованого завдання.
Циклічний алгоритм цілісного програмування
Розглянемо таку задачу лінійного програмування:
Зауважимо, що xn+1., хn+m – слабкі змінні, a x1…., хn – вихідні змінні завдання (2). Якщо поруч із обмеженнями (2) вимагати, щоб усі хj, (j'=1,…, т) були цілими, то завдання буде називатися завданням цілого програмування. Існує велика кількість завдань, особливо комбінаторних, які можна сформулювати як завдання цілісного програмування.
Саме алгоритми цілісного програмування, які будуть описані нижче, реалізують методи систематичного запровадження додаткових обмежень з метою зведення вихідної допустимої області до опуклоїоболонці її допустимих цілих точок.
Як тільки це буде зроблено, можна вирішувати модифіковане завдання лінійного програмування будь-яким звичайним методом, і отримане оптимальне базове рішення автоматично буде цілочисловим.
Наведений нижче цілий алгоритм має такі властивості:
1) всі додаткові обмеження зберігають допустимі точки вихідної цілісної задачі;
2) за кінцеве число кроків створюється достатня кількість додаткових обмежень для того, щоб оптимальне розв'язання модифікованого завдання було цілим;
3) додаткові обмеження (гіперплощини) проходять принаймні через одну цілу точку, хоча і не обов'язково знаходиться всередині опуклої оболонки;
4) кожне нове обмеження скорочує область допустимих рішень вихідного завдання цілісного програмування.
Слід наголосити, що оптимальне рішення вихідної задачі може бути отримане перш, ніж допустима область скоротиться до розмірів опуклої оболонки. До того ж, оскільки оптимальне ціле рішення визначається перетином п гіперплощин, таких гіперплощин існує не більше, ніж це необхідно; деякі з них можуть бути обмеженнями вихідного завдання.
Зазвичай в обмеження задачі (2) включаються в тривіальні співвідношення xj = - (-Xj) (j' = 1, ..., n), а завдання в матричній формі набуває вигляду: х = А (-хn), (3)
де х - вектор-стовпець з компонентами Х 0, x1, ..., xn, xn + 1, ..., xn + m А - відповідна матриця розміру (п + т + 1) * (n + 1) і (-хn) - вектор з компонентами (1, - x1, - x2, ..., - xn), що являють собою небазисні змінні вихідної таблиці. Завдання цілого програмування також можна записати у вигляді таблиці.
Причиниуявлення змінних як (-x1), (-x2,……, (-xn)) - суто історичні, але це стало звичайною практикою в цілісному програмуванні. Будемо використовувати бj(j = 0, 1, ..., п) для позначення j-го стовпця поточної таблиці та aij (i = 0, 1, ..., п + т; j = 0, 1, ..., n) для позначення елемента 1-го рядка та 7-го стовпця таблиці. Передбачається, що це a, ij у вихідній таблиці цілі. Отже, усі слабкі змінні xn+1,…, Хn+m повинні бути також невід'ємними цілими числами.
При викладанні алгоритму для вирішення цілих завдань будемо слідувати роботі Гоморі. Спочатку завдання цілісного програмування розглядається як лінійна програма і алгоритм вирішує її за допомогою прямого або двоїстого симплекс-метода. Наприкінці роботи алгоритму аij?0 (i = 1, ..., п + т) і a0j? 0 (j' = 1, ..., n). (Для отримання вихідного двоїстого допустимого рішення введемо додаткове обмеження xn+m+1 == М - X1 - x2 - … - xn? 0, де M - досить велика константа, і проробимо одну ітерацію з цим рядком і лексикографічно мінімальним стовпцем як ведучий .) Якщо аi0? 0 та цілі для всіх i, то отримано оптимальне рішення цілісної задачі. У цьому випадку рішення виходить одразу, без використання обмежень цілісності. Якщо аi0? 0, але не всі цілі, додамо до обмежень ще одне. Нове обмеження записується внизу таблиці те щоб вона перестала бути прямо допустимої, тобто. аi0