Название: Цілочислове програмування
Вид работы: реферат
Рубрика: Математика
Размер файла: 25.13 Kb
Скачать файл: referat.me-218838.docx
Краткое описание работы: Постановка задачі Існує доволі широкий клас задач математичного програмування, в економіко – математичних моделях яких одна або кілька змінних мають набувати цілих значень, наприклад, коли йдеться про кількість верстатів у цеху, тобто коли така вимога випливає з особливостей технології виробництва.
Цілочислове програмування
Постановка задачі
Існує доволі широкий клас задач математичного програмування, в економіко – математичних моделях яких одна або кілька змінних мають набувати цілих значень, наприклад, коли йдеться про кількість верстатів у цеху, тобто коли така вимога випливає з особливостей технології виробництва. До цілочислового програмування належать також задачі оптимізації, в яких змінні набувають лише двох значень – 0 або 1 (бульові, або бінарні, змінні).
До цілочислового програмування відносять задачі про призначення, найкоротший шлях і т. ін. У реальних задачах часто цілочислових значень набувають не всі, а одна чи кілька змінних. Такі задачі називають частково цілочисловими.
Задача цілочислового програмування записується так :
, (1)
за умов
; (2)
(3)
(4).
Для знаходження оптимального розв'язку цілочислових задач застосовують спеціальні методи. Найпростішим методом розв'язування цілочислової задачі є знаходження її оптимального роз в'язку як задачі, що має лише неперервні змінні, з подальші округленням останніх. Такий підхід часто є виправданим.
Для знаходження оптимальних планів задач цілочислової програмування застосовують дві основні групи методів:
— методи відтинання;
— комбінаторні методи.
Основою методів відтинання є ідея поступового «звуження» області допустимих розв'язків розглядуваної задачі. Пошук цілочислового оптимуму починається з розв'язування задачі з так званими послабленими обмеженнями, тобто без урахування вимог цілочисловості змінних. Далі введенням у модель спеціальних додаткових обмежень, що враховують цілочисловість змінних, многокутник допустимих розв'язків послабленої задачі поступово зменшуємо доти, доки змінні оптимального розв'язку не набудуть цілочислових значень. До цієї групи належать:
-методи розв'язування повністю цілочислових задач (дробовий
алгоритм Гоморі);
-методи розв'язування частково цілочислових задач (другий
алгоритм Гоморі, або змішаний алгоритм цілочислового програ
мування).
Комбінаторні методи цілочислової оптимізації базуються на повному переборі всіх допустимих цілочислових розв'язків, тобто вони реалізують процедуру цілеспрямованого перебору, під час якої розглядається лише частина розв'язків (досить невелика), а решта враховується одним зі спеціальних методів.
Найпоширенішим у цій групі методів є метод віток і меж.
Починаючи з розв'язування послабленої задачі, він передбачає розбиття початкової задачі на дві підзадачі виключенням областей, що не мають цілочислових розв'язків, і дослідженням кожної окремої частини многокутника допустимих розв'язків.
Для розв'язування задач із бульовими змінними застосовують комбіновані методи, причому оскільки змінні є бульовими, то методи пошуку оптимуму значно спрощуються.
Метод Гоморі
Нехай маємо задачу цілочислового програмування (1) – (4). Для її розв'язування можна скористатися ітеративним методом Гоморі. Суть його полягає ось у чому:
1.Знаходять розв'язок послабленої, тобто задачі без вимог ці-
лочисловості змінних — (1) - (3).
Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей план є оптимальним планом задачі цілочислового програмування (1) - (4).
2.Коли в умовно-оптимальному плані є дробові значення, то
вибирається змінна, яка має найбільшу дробову частину. На базі
цієї змінної (елементів відповідного рядка останньої симплексної
таблиці, в якому вона міститься) будується додаткове обмеження Гоморі:
де символ {} позначає дробову частину числа.
Для визначення дробової частини будь-якого числа від цього числа віднімають цілу його частину — найбільше ціле число, що неперевищує даного Цілу частину числа позначають символом [] .
Наприклад :
[1,3] = 1; [-1,3] =-2;
{1,3} = 1,3 - 1 = 03; {-1,3} = -1,3 - (-2) =2 - 1,3 = 0,7.
3. Додаткове обмеження після зведення його до канонічного вигляду і введення базисного елемента приєднується до останньої симплексної таблиці, яка містить умовно-оптимальний план. Здобуту розширену задачу розв'язують, а далі перевіряють її розв'язок на цілочисювість. Якщо він не цілочисловий, то процедуру повторюють повертаючись до пункту 2.
Так діють доти, доки не буде знайдено цілочислового розв'язку або доведено, що задача не має допустимих розв'язків у множині цілих чисел.
Досвід показує, що процес розв'язування задач великої розмірності методом Гоморі повільно збіжний. Істотними є також похибки округлення, які можуть призвести до того, що отриманий цілочисловий план не буде оптимальним .
Похожие работы
-
Будування математичної моделі економічної задачі і розвязання її за допомогою графічного метода
Практичне завдання з математичного програмування Будування математичної моделі економічної задачі і розв'язання її за допомогою графічного метода, методів Жордана-Гаусса, потенціалу та симплекс-метода
-
Побудова математичної моделі задачі лінійного програмування
КОНТРОЛЬНА РОБОТА з дисципліни „Математичне програмування” Завдання 1 1) Побудувати математичну модель задачі лінійного програмування. 2) Звести дану задачу до канонічного вигляду.
-
Математичне програмування в економіці
Математичне програмування Тема 1. Предмет, особливості та сфери застосування математичного програмування в економіці. Класифікація задач Математичне програмування
-
Знаходження оберненої матриці за формулою
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ЗАКАРПАТСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ФАКУЛЬТЕТ ІНФОРМАТИКИ Кафедра програмного забезпечення автоматизованих систем та фізико-математичних дисциплін
-
Загальні властивості неперервних функцій
Загальні властивості неперервних функцій однакові як для функцій однієї змінної, так і для функцій багатьох змінних. Теорема 3. (Вейєрштрасса). Функція
-
Розв'язок задачі лінійного програмування
Послідовність графічного розв'язання задачі лінійного програмування. Сумісна система лінійних нерівностей, умови невід'ємності, визначення півплощини з граничними прямими. Графічний метод для визначення оптимального плану задачі лінійного програмування.
-
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
-
Теореми Ролля Лагранжа Коші Правило Лопіталя Формула Тейлора для функції однієї та двох змін
Пошукова робота на тему: Теореми Ролля, Лагранжа, Коші. Правило Лопіталя. Формула Тейлора для функції однієї та двох змінних. План Основні теореми диференціального числення
-
Властивості визначеного інтеграла
1. Властивості визначеного інтеграла 10 Величина визначеного інтеграла не залежить від позначення змінної інтегрування: тощо. Інтегральна сума, а отже, і її границя не залежать від того, якою буквою позначено аргумент функції f. Це й означає, що визначений інтеграл не залежить від позначення змінної інтегрування.
-
Критерій Байєса-Лапласа при експоненційно розподілених даних для множини оптимальних рішень
Прийняття рішень як основний компонент систем управління проектами. Методика розробки програми для знаходження множини оптимальних рішень за критерієм Байєса-Лапласа з формуванням матриці ймовірностей реалізації умов за експоненційним законом розподілу.