Читайте также:
|
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
Лабораторна робота №6
з дисципліни “ Математичні методи дослідження операцій ”
на тему
«Метод Гоморі»
Виконав:
студент групи КН-22
Муха Богдан
Прийняв:
старший викладач
Балич Б. І.
Львів – 2012
Мета роботи: вивчення методу Гоморідля знаходження розв’язку цілочисельних задач лінійного програмування.
План
1. Короткі теоретичні відомості.
2. Постановка задачі
2.1 Графічне вирішення задачі.
2.2 Метод Гоморі розв’язаний за допомогою симлекс таблиць.
3. Розв’язання за допомогою пакету програм MS Exel
4. Розв’язання за допомогою власної програми.
Хід роботи
1. Короткі теоретичні відомості
Під завданням цілочисельного програмування (ЦП) розуміється завдання, в якому всі або деякі змінні повинні приймати цілі значення. У тому випадку,
коли обмеження і цільова функція задачі є лінійної залежності, завдання називають целочисельним завданням лінійного програмування. В іншому випадку, коли хоча б одна залежність буде нелінійною, це буде целочисленним завданням нелінійного програмування.
Особливий інтерес до завдань ЦП викликаний тим, що в багатьох практичних задачах необхідно знаходити цілочисельне рішення зважаючи дискретність ряду значень шуканих змінних.
Цілочисельне програмування виникло в 50-60-і роки нашого століття з потреб практики - головним чином в роботах американських математиків Дж.Данціга і Р.Гоморі. Спочатку цілочисельне програмування розвивалося незалежно від геометрії чисел на основі теорії і методів математичної оптимізації, перш за все лінійного програмування. Однак, в останні час
дослідження в цьому напрямку все частіше проводяться засобами математики цілих чисел.
Завдання такого типу дуже актуальні, оскільки до їх вирішення зводиться аналіз різноманітних ситуацій, що виникають в економіці, техніці, військовій справі і інших областях. З появою ЕОМ, зростанням їх продуктивності підвищився інтерес до завдань такого типу і до математики в цілому.
Цілочисловим (іноді його називають також дискретним) програмуванням
називається розділ математичного програмування, який вивчає екстремальні
завдання, в яких на шукані змінні накладається умова
цілочисельності, а область допустимих рішень яких кінцева. Величезна кількість економічних завдань носить дискретний, найчастіше цілочисельний характер, що пов'язано, як правило з фізичною неподільністю багатьох елементів розрахунку: наприклад, не можна побудувати два з половиною заводи, купити півтора автомобіля і т.д. У ряді випадків такі завдання вирішуються звичайними методами, наприклад, симплексним методом, з наступним округленням до цілих чисел. Однак такий підхід виправданий, коли окрема одиниця становить дуже малу частину всього
обсягу (наприклад, товарних запасів); в іншому випадку він може внести
значні спотворення в дійсно оптимальне рішення. Тому розроблені спеціальні методи вирішення цілочислових задач.
Рекомендації по формулюванню і рішенням ЦП:
Кількість цілочисельних змінних зменшувати настільки, наскільки можливо. Наприклад, цілочисельні змінні, значення яких повинно бути не менше 20, можна розглядати як безперервні.
На відміну від загальних задач ЛП, додавання нових обмежень особливо включають цілочисельні змінні, звичайно зменшують час розв'язання завдань ЦП.
Якщо немає гострої необхідності в знаходженні точного оптимального цілочисельного рішення, що відрізняється від безперервного рішення, наприклад, 3%. Тоді реалізацію методу гілок і меж для задачі максимізації можна закінчувати, якщо відношення різниці між верхньою і нижньою границями до верхньої межі менше 0,03.
Метод гілок і меж можна застосовувати для вирішення задач нелінійного
програмування.
2. Постановка задачі
Розв’язати задачу лінійного програмування симплекс методом (номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100)
Варіант 48
F(x1,x2) = 3x1 + 6x2 
max;
x 1 + x 2 
8,
3x 1 + 7 x 2 
21,
x 1 + 2 x 2 6,
0 x 1 7, 0 x 2 7.
2.1 Розв’язання без використання пакетів програм.
Графічне вирішення задачі
Знайдемо геометрично найбільше значення лінійної функції
F(x1,x2) = 3x1 + 6x2 max в області, заданої системою нерівностей.
x 1 + x 2 8,
3x 1 + 7 x 2 21,
x 1 + 2 x 2 6,
0 x 1 7, 0 x 2 7.
Малюємо графік враховуючи нерівності за рівності і відповідно визначаємо область допустимих значень.
Будую градієнт функції F і переміщаю пряму перпендикулярну йому, поки вона не доторкнеться області допустимих значень.
Якщо переміщатимемо поки вона не пройде всю область допустимих значень, то знайдемо точку максимуму.
|
|
|
Всі цілочисельні рішення, що належать області G, виділені жирними крапками. Найбільше значення L(x1,x2) в області G дорівнює (0, 8).
При цьому L(0,8)=48 - найбільше значення цільової функції в області G.
Метод Гоморі.
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексної таблиці.
Визначимо максимальне значення цільової функції F(x1,x2) = 3x1 + 6x2 max за таких умов-обмежень.
x1 + x2 ≤ 8
3x1 + 7x2 ≥ 21
x1 + 2x2 ≥ 6
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
В 1-й нерівності (≤) вводимо базисну змінну x3. В 2-й нерівності (≥) вводимо базисну змінну x4 зі знаком мінус. В 3-й нерівності (≥) вводимо базисну змінну x5 зі знаком мінус.
1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 8
3x1 + 7x2 + 0x3-1x4 + 0x5 = 21
1x1 + 2x2 + 0x3 + 0x4-1x5 = 6
Введемо штучні змінні x: в 2-у рівність вводимо змінну x6; в 3-у рівність вводимо змінну x7;
1x1 + 1x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 8
3x1 + 7x2 + 0x3-1x4 + 0x5 + 1x6 + 0x7 = 21
1x1 + 2x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 6
Для постановки завдання на максимум цільову функцію запишемо так:
F(X) = 3x1+6x2 - Mx6 - Mx7 => max
За використання штучних змінних, що вводяться в цільову функцію, накладається так званий штраф величиною М, дуже велике позитивне число, яке зазвичай не задається.
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.
З рівнянь знаходимо значення штучних змінних:
x6 = 21-3x1-7x2+x4
x7 = 6-x1-2x2+x5
які підставимо в цільову функцію:
F(X) = 3x1 + 6x2 - M(21-3x1-7x2+x4) - M(6-x1-2x2+x5) => max
або
F(X) = (3+4M)x1+(6+9M)x2+(-1M)x4+(-1M)x5+(-27M) => max
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
| -1 | ||||||
| -1 |
Базисні змінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3, x6, x7,
Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план: X1 = (0,0,8,0,0,21,6)
Базисне рішення називається допустимим, якщо воно невід'ємне.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x3 | ||||||||
| x6 | -1 | |||||||
| x7 | -1 | |||||||
| F(X0) | -27M | -3-4M | -6-9M | 1M | 1M |
Переходимо до основного алгоритму симплекс-методу.
Ітерація №1.
1. Перевірка критерію оптимальності.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
2. Визначення нової базисної змінної.
В якості ведучого виберемо стовпець, відповідний змінній x1, так як це найбільший коефіцієнт по модулю.
3. Визначення нової вільної змінної.
Обчислимо значення Di по рядках як частка від ділення: bi / ai1
і з них виберемо найменше:
min (8: 1, 21: 3, 6: 1) = 6
Отже, 3-ий рядок є провідним.
Розв’язуючий елемент дорівнює (1) і стоїть на перетині ведучого стовпця і вивідного рядка.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| x3 | |||||||||
| x6 | -1 | ||||||||
| x7 | -1 | ||||||||
| F(X1) | -27M | -3-4M | -6-9M | 1M | 1M |
4. Перерахунок симплекс-таблиці.
Формуємо наступну частину симплексного таблиці.
Замість змінної x в план 1 увійде змінна x1 .
Рядок, який відповідає змінній x1 в плані T1, отриманий в результаті поділу всіх елементів рядка x7 плану 0 на розв’язуючий елемент РЕ=1. На місці розв’язуючий елемента в плані Т1 отримуємо 1. В інших клітинах стовпця x1 плану Т1 записуємо нулі.
Таким чином, у новому плані Т1 вже маємо заповнені рядок x1 і стовпець x1.
Всі інші елементи нового плану Т1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають розв’язуючий елемент РЕ.
НЕ = СЕ - (А * В) / РЕ
СТЕ - елемент старого плану, РЕ - розв’язуючий елемент (1), А і В - елементи старого плану, що утворюють прямокутник з елементами СТЕ і РЕ.
Уявімо розрахунок кожного елемента у вигляді таблиці:
| B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 |
| 8-(6 • 1):1 | 1-(1 • 1):1 | 1-(2 • 1):1 | 1-(0 • 1):1 | 0-(0 • 1):1 | 0-(-1 • 1):1 | 0-(0 • 1):1 | 0-(1 • 1):1 |
| 21-(6 • 3):1 | 3-(1 • 3):1 | 7-(2 • 3):1 | 0-(0 • 3):1 | -1-(0 • 3):1 | 0-(-1 • 3):1 | 1-(0 • 3):1 | 0-(1 • 3):1 |
| 6: 1 | 1: 1 | 2: 1 | 0: 1 | 0: 1 | -1: 1 | 0: 1 | 1: 1 |
| (0)-(6 • (-3-4M)):1 | (-3-4M)-(1 • (-3-4M)):1 | (-6-9M)-(2 • (-3-4M)):1 | (0)-(0 • (-3-4M)):1 | (1M)-(0 • (-3-4M)):1 | (1M)-(-1 • (-3-4M)):1 | (0)-(0 • (-3-4M)):1 | (0)-(1 • (-3-4M)):1 |
Отримуємо нову симплекс-таблицю:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x3 | -1 | -1 | ||||||
| x6 | -1 | -3 | ||||||
| x1 | -1 | |||||||
| F(X1) | 18-3M | -1M | 1M | -3-3M | 3+4M |
Ітерація №2.
1. Перевірка критерію оптимальності.
Поточний опорний план неоптимальним, тому що в індексному рядку знаходяться негативні коефіцієнти.
2. Визначення нової базисної змінної.
В якості ведучого виберемо стовпець, відповідний змінній x2, так як це найбільший коефіцієнт по модулю.
3. Визначення нової вільної змінної.
Обчислимо значення Di по рядках як частка від ділення: bi / ai2
і з них виберемо найменше: min (-, 3: 1, 6: 2) = 3
Отже, 2-ий рядок є провідним.
Розв’язуючий елемент дорівнює (1) і стоїть на ведучого стовпця і вивідного рядка.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| x3 | -1 | -1 | - | ||||||
| x6 | -1 | -3 | |||||||
| x1 | -1 | ||||||||
| F(X2) | 18-3M | -1M | 1M | -3-3M | 3+4M |
4. Перерахунок симплекс-таблиці.
Формуємо наступну частину симплексного таблиці. Замість змінної x в план Т2 увійде змінна x2 . Рядок, який відповідає змінній x2 в плані Т2, отриманий в результаті поділу всіх елементів рядка x6 плану 1 на розв’язувальний елемент РЕ=1.
На місці розв’язувального елементу в плані Т2 отримуємо 1. В інших клітинках стовпця x2 плануТ 2 записуємо нулі.
Таким чином, у новому плані Т2 заповнені стають рядок x2 і стовпець x2.
Всі інші елементи нового плану Т2, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Уявімо розрахунок кожного елемента у вигляді таблиці:
| B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 |
| 2-(3 • -1):1 | 0-(0 • -1):1 | -1-(1 • -1):1 | 1-(0 • -1):1 | 0-(-1 • -1):1 | 1-(3 • -1):1 | 0-(1 • -1):1 | -1-(-3 • -1):1 |
| 3: 1 | 0: 1 | 1: 1 | 0: 1 | -1: 1 | 3: 1 | 1: 1 | -3: 1 |
| 6-(3 • 2):1 | 1-(0 • 2):1 | 2-(1 • 2):1 | 0-(0 • 2):1 | 0-(-1 • 2):1 | -1-(3 • 2):1 | 0-(1 • 2):1 | 1-(-3 • 2):1 |
| (3+4M)-(3 • (-1M)):1 | (0)-(0 • (-1M)):1 | (-1M)-(1 • (-1M)):1 | (0)-(0 • (-1M)):1 | (1M)-(-1 • (-1M)):1 | (-3-3M)-(3 • (-1M)):1 | (0)-(1 • (-1M)):1 | (3+4M)-(-3 • (-1M)):1 |
Отримуємо нову симплекс-таблицю:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x3 | -1 | -4 | ||||||
| x2 | -1 | -3 | ||||||
| x1 | -7 | -2 | ||||||
| F(X2) | -3 | 1M | 3+1M |
Ітерація №3.
1. Перевірка критерію оптимальності.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
2. Визначення нової базисної змінної.
В якості ведучого виберемо стовпець, відповідний змінній x5, так як це найбільший коефіцієнт по модулю.
3. Визначення нової вільної змінної.
Обчислимо значення Di по рядках як частка від ділення: bi / ai5 і з них виберемо найменше:
min (5: 4, 3: 3, -) = 1
Отже, 2-ий рядок є провідним.
Розв’язувальний елемент дорівнює (3) і стоїть на ведучого стовпця і вивідного рядка.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| x3 | -1 | -4 | 11/4 | ||||||
| x2 | -1 | -3 | |||||||
| x1 | -7 | -2 | - | ||||||
| F(X3) | -3 | 1M | 3+1M |
4. Перерахунок симплекс-таблиці.
Формуємо наступну частину симплексного таблиці. Замість змінної x в план Т3 увійде змінна x5 . Рядок, відповідний змінній x5 в плані Т3, отриманий в результаті поділу всіх елементів рядка x2 плані Т2 на розв’язувальний елемент РЕ=3.На місці розв’язувального елемента в плані Т3 отримуємо 1.В інших клітинках стовпця x5 плану 3 записуємо нулі.
Таким чином, у новому плані 3 заповнені рядок x5 і стовпець x5.
Всі інші елементи нового плану 3, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Уявімо розрахунок кожного елемента у вигляді таблиці:
| B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 |
| 5-(3 • 4):3 | 0-(0 • 4):3 | 0-(1 • 4):3 | 1-(0 • 4):3 | -1-(-1 • 4):3 | 4-(3 • 4):3 | 1-(1 • 4):3 | -4-(-3 • 4):3 |
| 3: 3 | 0: 3 | 1: 3 | 0: 3 | -1: 3 | 3: 3 | 1: 3 | -3: 3 |
| 0-(3 • -7):3 | 1-(0 • -7):3 | 0-(1 • -7):3 | 0-(0 • -7):3 | 2-(-1 • -7):3 | -7-(3 • -7):3 | -2-(1 • -7):3 | 7-(-3 • -7):3 |
| (3+1M)-(3 • (-3)):3 | (0)-(0 • (-3)):3 | (0)-(1 • (-3)):3 | (0)-(0 • (-3)):3 | (0)-(-1 • (-3)):3 | (-3)-(3 • (-3)):3 | (1M)-(1 • (-3)):3 | (3+1M)-(-3 • (-3)):3 |
Отримуємо нову симплекс-таблицю:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x3 | -11/3 | 1/3 | -1/3 | |||||
| x5 | 1/3 | -1/3 | 1/3 | -1 | ||||
| x1 | 21/3 | -1/3 | 1/3 | |||||
| F(X3) | -1 | 1+1M | 1M |
Ітерація №4.
Виконую наступні кроки по відомому алгоритму
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| x3 | -11/3 | 1/3 | -1/3 | ||||||
| x5 | 1/3 | -1/3 | 1/3 | -1 | - | ||||
| x1 | 21/3 | -1/3 | 1/3 | - | |||||
| F(X4) | -1 | 1+1M | 1M |
Перерахунок симплекс-таблиці.
| B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 |
| 1: 1/3 | 0: 1/3 | -11/3: 1/3 | 1: 1/3 | 1/3: 1/3 | 0: 1/3 | -1/3: 1/3 | 0: 1/3 |
| 1-(1 • -1/3):1/3 | 0-(0 • -1/3):1/3 | 1/3-(-11/3 • -1/3):1/3 | 0-(1 • -1/3):1/3 | -1/3-(1/3 • -1/3):1/3 | 1-(0 • -1/3):1/3 | 1/3-(-1/3 • -1/3):1/3 | -1-(0 • -1/3):1/3 |
| 7-(1 • -1/3):1/3 | 1-(0 • -1/3):1/3 | 21/3-(-11/3 • -1/3):1/3 | 0-(1 • -1/3):1/3 | -1/3-(1/3 • -1/3):1/3 | 0-(0 • -1/3):1/3 | 1/3-(-1/3 • -1/3):1/3 | 0-(0 • -1/3):1/3 |
| (1M)-(1 • (-1)):1/3 | (0)-(0 • (-1)):1/3 | (1)-(-11/3 • (-1)):1/3 | (0)-(1 • (-1)):1/3 | (-1)-(1/3 • (-1)):1/3 | (0)-(0 • (-1)):1/3 | (1+1M)-(-1/3 • (-1)):1/3 | (1M)-(0 • (-1)):1/3 |
Отримуємо нову симплекс-таблицю:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x4 | -4 | -1 | ||||||
| x5 | -1 | -1 | ||||||
| x1 | ||||||||
| F(X4) | -3 | 1M | 1M |
Ітерація №5.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| x4 | -4 | -1 | - | ||||||
| x5 | -1 | -1 | - | ||||||
| x1 | |||||||||
| F(X5) | -3 | 1M | 1M |
Перерахунок симплекс-таблиці.
| B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 |
| 3-(8 • -4):1 | 0-(1 • -4):1 | -4-(1 • -4):1 | 3-(1 • -4):1 | 1-(0 • -4):1 | 0-(0 • -4):1 | -1-(0 • -4):1 | 0-(0 • -4):1 |
| 2-(8 • -1):1 | 0-(1 • -1):1 | -1-(1 • -1):1 | 1-(1 • -1):1 | 0-(0 • -1):1 | 1-(0 • -1):1 | 0-(0 • -1):1 | -1-(0 • -1):1 |
| 8: 1 | 1: 1 | 1: 1 | 1: 1 | 0: 1 | 0: 1 | 0: 1 | 0: 1 |
| (1M)-(8 • (-3)):1 | (0)-(1 • (-3)):1 | (-3)-(1 • (-3)):1 | (3)-(1 • (-3)):1 | (0)-(0 • (-3)):1 | (0)-(0 • (-3)):1 | (1M)-(0 • (-3)):1 | (1M)-(0 • (-3)):1 |
Отримуємо нову симплекс-таблицю:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x4 | -1 | |||||||
| x5 | -1 | |||||||
| x2 | ||||||||
| F(X5) | 1M | 1M |
Ітерація №6.
1. Перевірка критерію оптимальності.
Серед значень індексного рядка немає негативних. Тому ця таблиця визначає оптимальний план завдання.
Остаточний варіант симплекс-таблиці:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x4 | -1 | |||||||
| x5 | -1 | |||||||
| x2 | ||||||||
| F(X6) | 1M | 1M |
Оптимальний план можна записати так:
x4 = 35
x5 = 10
x2 = 8
F(X) = 6•8 = 48
Рішення вийшло цілочисловим. Немає необхідності застосовувати метод Гоморі.
Оптимальний цілочисельний план можна записати так:
x4 = 35
x5 = 10
x2 = 8
F(X) = 48
3. Розв’язання з допомогою пакету програм MS Exel
4. Розв’язання за допомогою власної програми.
Програма написана мовою Delphi
Вхідними даними програми є цільова функція, максимум чи мінімум якої потрібно знайти і система лінійних обмежень. Для введення коефіцієнтів використовується редактор завдання, що дозволяє додавати функцію та обмеження, змінювати і видаляти їх. Вікно параметрів задачі містить дві вкладки: вкладка «Функція», що служить для зміни цільової функції і вкладка «Обмеження» для редагування лінійних обмежень. Для зручності в програмі не потрібно кодування вхідних даних. Обробка і машинне подання вхідних даних проводиться автоматично.
Вихідними даними є оптимальний базис і значення цільової функції при знайдених значеннях змінних, які можна вивести як на екран, так і на принтер.
Існує можливість зберегти на диску як вхідні дані, так і вихідні для подальшого зчитування. Ці операції виконуються командами «Відкрити...», «Зберегти» і «Зберегти як..." головного меню програми. Діалогові вікна збереження і завантаження даних мають стандартний вигляд і дозволяють здійснювати файлові операції.
Дата добавления: 2015-11-16; просмотров: 91 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Интервью с Дмитрием Борисенковым - 28.05.09 | | | БЮЛЛЕТЕНЬ № 8 |