Показник
|
№
|
|
|
1
|
Q
|
0.6
|
Ф
|
60
|
ф1
|
150
|
X0
|
70
|
Р
|
10
|
C1
|
850
|
C2
|
Потреба
підприємства в робочу часі:
|
|
січень
|
10000
|
лютий
|
8000
|
березень
|
10000
|
квітень
|
12000
|
травень
|
9000
|
червень
|
12000
|
1.
Розробка математичної моделі та аналіз методів
Математична модель
Математична модель складається з:
. Цільової функції
де - к січні, лютому, березні, квітні, травні та червні відповідно.
2. Обчислення:
81
Методи вирішення:
Гоморі-2, метод розгалужень та обмежень.
Даний курсовий проект запропоновано розв'язати
двома методами цілочисленого ділення: метод Гоморі 2, який реалізується
програмно та метод розгалуджень та обмежень, розрахунок яким відбувається
вручну.
Методи цілочислового ділення основані на введені
в задачу додаткових обмежень, що дозволяють врахувати вимоги цілочисленності.
Основна ідея методів відсікання полягає в тому, що на отримане оптимальне не
цілочислового рішення накладається додаткове обмеження, котре робить це рішення
недопустимим, але і не відсікає ні одного цілочислового рішення от області допустимих
рішень.
Суть методу Гоморі полягає у наступному:
· отримання першого
опорного рішення з використанням звичайної симплекс таблиці або двоїстого
симплекс методу;
· на основі максимальної
дробної змінної формується нове обмеження, щоб відсікати дробну частину;
· Рішення нової системи
розмірністю m+1, n+1 відбувається за допомогою двоїстого симплекс метода;
· Повтор другого та
третього пункту відбувається до тих пір всі значення не будуть цілими або
рішення не буде відсутнє.
Формування обмеження: - {yi}=
Перерахунок нової модель відбувається за такими формулами:
{bi}, якщо j=0
, якщо Xj - ціле та {aij} >={b0}
{aij}, якщо {aij} <{b0}, якщо Xj - не
ціле та {aij} >{b0}
, якщо {aij} <{b0}
Гоморі 2, на відміну від Гоморі, майже завжди дає відповідь
та відрізняється тим, що не на всі змінні накладаються обмеження.
Метод розгалужень та обмежень - один із комбінаторних
методів. Його зміст полягає у впорядкованому переборі варіантів та перегляді
лише тих які виявляються по певним ознакам перспективними, і відкиданні безперспективних
варіантів.
Цей метод полягає в наступному: множина
допустимих рішень (планів) деяким способом розбивається на підмножини, кожна з
яких тим же способом розбивається на підмножини. Процес продовжується доти доки
не буде отримане оптимальне цілочисельне рішення
Зміст методу полягає в наступному:
. Знаходимо рішення задачі лінійного
програмування без обліку цілочисельних змінних.
. Складаємо додаткові обмеження на дробову
компоненту плану.
. Знаходимо рішення двох задач з обмеженнями на
компоненту.
. Будуємо в разі потреби додаткові обмеження,
відповідно до
можливих чотирьох випадків одержуємо
цілочисельний план, або
встановлюємо нерозв’язаність системи.
Метод оснований на припущенні, що наш оптимальний
нецілочисельний план дає значення функції, більше ніж усякий наступний план
переходу.
. Розв’язок задачі за допомогою методу Гоморі 2
Алгоритм
програми
Для початку розрахунку задачі за допомогою методу Гоморі 2,
користувач має вручну розрахувати псевдо-план. В свою чергу псевдоплан - це
нова модель, яка вміщує одиничний спряжений (знайдений одиничний) базис та
недопустиме опорне рішення.
Для цього потрібно привести цільову функцію до max (Якщо вона
спрямована на мінімізацію, то знак цільової функції змінюється на «-»), а
обмеження до рівнянь. В цілюву функцію ніякі змінні не додаються. Всі знаки
замінюються на знак « =», враховуючи відповідні правила переведення моделей від
звичайної моделі до її канонічного вигляду (вони відмінні від правил переводу
до канонічного моделі при симплекс методі). Правила переводу є наступними: якщо
обмеження має знак «<» то при переведенні до канонічного вигляду, то
додається одну змінна; якщо - «>» то віднімається одна змінна; якщо знак «=»
то ніякі змінні не додаються.
Наступним етапом буде записана двоїста задача, на
основі якої будуть сформовані незалежні вектори за допомогою введення А0…Аn.
Після чого вибираємо спряжений базис розмірності m:
· Вибираємо m-рівнянь
· Вирішуємо систему
· Підставляємо рішення в
інші обмеження (якщо рішення інших обмежень задовольняє рівняння, то базис
знайдено, в іншому випадку шукаємо далі).
Після формування та розрахунку симплекс таблиці
переписуємо з таблиці нову модель, данні якої передаються далі на розрахунок за
допомогою двоїстого симплекс метода. Якщо рішення після розрахунку за допомогою
двоїстого симплекс-метода не буде цілочислене формуємо певні обмеження:
· Від max А0 відсікається
дробна частина та створюється нова змінна (таким чином розмірність задачі
збільшується).
· Розрахунок всіх останніх
елементів рядка відбувається за допомогою вище перечислених правил.
Процес буде повторюватись до того часу поки не
буде знайдене цілочислене рішення, або рішення не буде відсутнє.
Розв’язок за допомогою Гоморі 2
(c) Koziy Alena…PNK-41zadachi:
6x12
x1-850x2->max
x1+1x7=-6850
x1-1x2-1x3+1x9=-9790
x1-1x2-1x3-1x4+1x10=-13260
x1-1x2-1x3-1x4-1x5+1x11=-11730
x1-1x2-1x3-1x4-1x5-1x6+1x12=-16200cilochusesnosti:
0 0 0 0 0 0 0 0 0 0 0
Z=-214245
X=(47.57 14344.79 0 0 0 0 0 13875.83 9406.88
4937.92 5468.96 0)
. Розрахунок задачі методом «Розгалуджень та
обмежень».
Даний алгоритм має такий опис.
Перша частина складає окремий модуль (simpl). В
цьому модулі реалізовані такі процедури, як:
· зчитування з текстового
файлу;
· переведення до канонічного
виду;
· розрахунок симплекс -
методу.
Процедура зчитування з файлу реалізується
наступним чином - дані умови задачі потрібно внести у текстовий файл.
Вказується розмірність задачі. Модель задачі у текстовий файл вводиться в не
канонічному вигляді. Після приведення до канонічного вигляду відбувається
розрахунок симплекс-методом.
Формується симплекс - таблиця, що має свою
відповідну структуру та розрахунок за відповідними правилами. В результаті
отримання значення цільової функції, та вектору X.
Наступною дією є перевірка умови цілочисельності.
Якщо умова виконується і всі значення X є цілочисельними то одразу отримуємо
оптимальне рішення. Якщо умова цілочисельності не виконується то необхідно
вибрати значення X з найбільшою дробною частиною і сформувати два нових
обмеження відносно відповідного значення х. Обмеження формуються по типу «менше
меншого» та «більше більшого». Потім ці обмеження по черзі додаються в
початковий файл і формується наступний рівень дерева (формується дві нові
моделі.). Першим рівнем дерева є файл отриманий при першому виконанні програми.
Після цього застосовується розроблений модуль (simpl). Отримані результати
перевіряються. Коли буде отримане перше цілочисельне рішення, то воно
запам’ятовується, як максимальне. Процес формування дерева буде завершений
тоді, коли всі вузли одного рівня будуть або не мати рішення, або рішення
нецілочисельне буде гірше отриманого цілочисельного.
Дерево формується наступним чином. Наявні
відповідні рівні, кожен наступний формується при знаходженні нецілочисельного
значення X. Кількість рівнів відповідно становить N. Кількість вузлів
відповідно збільшується на кожному рівні вдвічі. Результати кожного з них на
одному рівні перевіряються. Після чого при наявності ознаки кращого
нецілочисельного рішення формується наступний рівень. Якщо рішення відсутнє або
гірше, процес побудови завершується.
Ітерація розв’язку
Начальный файл forvetv.txt
Размерность задачи: 6x14
Канонический вид:
-405X1-850X2-4050X4-4050X6-4050X8-4050X10-4050X12-4050X14->
max
X1 -1X3+ 1X4=6850
X1+ 1X2 -1X5+ 1X6=6320
X1+ 1X2+ 1X3+ 1X4 -1X7+ 1X8=9790
X1+ 1X2+ 1X3+ 1X4 -1X9+ 1X10=13260
X1+ 1X2+ 1X3+ 1X4+ 1X5 -1X11+ 1X12=11730
39X1+ 1X2+ 1X3+ 1X4+ 1X5+ 1X6 -1X13+ 1X14=1620
Итерация №1
Решение найдено
Задача 1
Задача-передующая 0=(89.378 0 6020.400 0 4673.467 0 5346.933
0 0 0 4326.533 0 12559.600 0)=-36198.000
Итерация №53
Размерность задачи ЦЛП - 11 x 22
-405X1-850X2-4050X4-4050X6-4050X8-4050X10-4050X12-4050X14-40500X15-40500X18-40500X21
-> max
X1 -1X3+ 1X4 = 6850
X1+ 1X2 -1X5+ 1X6 = 6320
X1+ 1X2+ 1X3+ 1X4 -1X7+ 1X8 = 9790
X1+ 1X2+ 1X3+ 1X4 -1X9+ 1X10 = 13260
X1+ 1X2+ 1X3+ 1X4+ 1X5 -1X11+ 1X12 = 11730
X1+ 1X2+ 1X3+ 1X4+ 1X5+ 1X6 -1X13+ 1X14 = 1620
X2+ 1X15 -1X16 = 3
X3+ 1X17 = 6019
X2+ 1X18 -1X19 = 1
X3+ 1X20 = 6020
X3+ 1X21 -1X22 = 6021
Решение найдено
Задача 53
Задача-передующая 26
Ограничение X2>=3=(89.364 3 6018.480 0 4674.827 0 5346.653
0 0 0 1.520 0 12561.520 0.188 0 11.500 1.187 1 2 0.520 1.187 1)=-38742.601
Конечное решение(1)= 89(2)= 0(3)=6007(4)=
41(5)=4627.000=-214245
Результати цільової функції співпадають.
За допомогою програми було обчислено системи рівнянь.
Ітерації, подані вище, свідчать про виконання роботи в цій програмі. Отже,
можна зробити висновок, що програма, яка була створена для обчислення цих
рівнянь методом розгалужень та обмежен працює вірно, результати співпадають.
. Дослідження на чутливість
Приклад 1:
(c) Koziy Alena…PNK-41
Размерность задачи: 2x6
.00x1-0.00x2-25x3-25x5->max
x1+3x2+1x3-1x4=6000
x1+1x2+1x5-1x6=4000
Условие целочисленности:
1 1 1 1 1=-250000=(0 0 6000 0 4000 0)
Приклад 2:
(c) Koziy Alena…PNK-41
Размерность задачи: 5x11
x1-20x2-22x3-25x4-28x5-30x6->max
x1-4x3-6x5+1x7=-10
x2-4x4-5x6+1x8=-6
x1+1x2+1x9=5
+1x3+1x4+1x10=15
+1x5+1x6+1x11=15
1 1 1 1 1 1 1 1 1 1=-106.00=(3.33 1.67 0 0 0 0.53 0 0 0 15
14.47)
Размерность задачи: 6x12
-17x1-20x2-22x3-25x4-28x5-30x6->max
x1+1.33x3+2x5-0.33x7=3.33
+1x2-1.33x3-2x5+0.33x7+1x9=1.67
+0.53x3+0.80x4+0.80x5+1x6-0.13x7-0.20x8-0.40x9=0.53
+1x3+1x4+1x10=15
.53x3-0.80x4+0.20x5+0.13x7+0.20x8+0.40x9+1x11=14.47
.47x3-0.20x4-0.20x5-0.13x7-0.20x8-0.40x9+1x12=-0.47
Условие целочисленности:
1 1 1 1 1 1 1 1 1 1 0=-106.67=(0 3.00 0 0 1.67 0 0 0 2.00 15
13.33 0.67)
Размерность задачи: 7x13
x1-20x2-22x3-25x4-28x5-30x6->max
x1+0.00x3-2x4-2.50x6-0.00x7+0.50x8+1x9=2.00
+1x2-0.00x3+2x4+2.50x6+0.00x7-0.50x8=3.00
.50x1-0.33x3-1x4-1x6-0.17x7+1x12=0.67
+1x3+1x4+1x10=15
.50x1-0.67x3+1x6+0.17x7+1x11=13.33
.50x1+0.67x3+1x5-0.17x7=1.67
.50x1-0.33x3-0.17x7+1x13=-0.33
Условие целочисленности:
1 1 1 1 1 1 1 1 1 1 0 0
=-116.00=(0 3 0 0 2.00 0 2.00 0 2.00 15 13 1.00 0)
Висновок
В створену програму, яка обраховує симплекс методом було
введено наведену нижче математичну модель та було отримано відповідні
результати.
Математична модель:
15
50 37 45 56 50 35 23 25 54 33 34 53 12 67 max
4 2 1 3 1 1 2 3 4 2 3 4 2 4 <600
2 1 3 1 1 1 2 3 4 3 4 3 2 4 <590
1 2 2 1 1 2 2 3 4 5 3 2 2 1 <760
1 2 2 2 3 1 2 3 4 2 1 3 2 1 <670
2 1 2 3 3 1 3 4 2 1 2 3 4 3 <500
3 4 5 2 4 4 3 2 1 2 3 2 3 4 <760
3 4 2 3 2 3 5 2 3 4 5 6 4 3 <560
2 4 3 5 4 3 4 5 3 4 5 6 4 3 <680
3 1 2 3 2 3 2 1 2 3 3 2 3 2 <690
1 2 3 3 4 5 5 4 3 2 3 4 4 5 >560
1 1 1 1 1 1 1 1 1 1 1 1 1 1= (10 10 60 10 10 0 0 0 0 50 0 0 0
0 0 0 0 0 10 0 0 45 0 0 0 0)= 16030
Отже, зробимо висновок, що програма спрацьовує на великій
розмірності.
Список використаної літератури
1. Тах Х.А. Введение в исследование операций.
6-ое издание. М. 2010.
2. Бабич В.І. Конспект лекцій з дисципліни
«Математичні методи дослідження операцій» 2012.
. Зайченко Ю.П. Курс лекцій з дослідження
операцій. Веб-сайт факультету «ІПСА» - http://iasa.org.ua