- •Оптимізаційні методи і моделі
- •0305 “ Економіка та підприємництво ”
- •Зм 1. Предмет математичного програмування.Лінійне програмування
- •Зміст виконання завдання
- •Критерій оптимальності – мінімум затрат праці - запишемо як
- •Зміст виконання завдання
- •Зм 2. Двоїстість у лінійному програмуванні
- •Зм 3.Транспортна задача
- •Скласти план вантажних перевезень з мінімальним вантажообігом.
- •Втрати живої ваги при перевезенні худоби, кг на 1 т
- •Площі попередників озимої пшениці, га
- •Площа сортів озимої пшениці, га
- •Середня урожайність озимої пшениці за попередниками, ц з 1 га
- •Зміст виконання завдання
- •Зм 4. Цілочислове програмування
- •4.1. Алгоритм методу відтинання Гоморі
- •4.2. Алгоритм методу гілок і меж
- •4.1. Метод відтинання Гоморі
- •4.2. Метод гілок і меж
- •Модуль2. Дослідження операцій
- •5.1.Моделювання виробничих систем в тваринництві
- •Зміст виконання завдання
- •5.2. Моделювання виробничих систем в тваринництві
- •Зміст виконання завдання
- •5.3. Моделювання виробництва і реалізації продукції
- •Зміст виконання завдання
- •Зм 6. Аналіз та управління ризиком в економіці
- •Платіжна матриця
- •Платіжна матриця
- •Матриця ризиків
- •Платіжна матриця
- •Зміст виконання завдання
- •Зм 7. Оптимізаційні задачі управління запасами
- •Статична однономенклатурна детермінована модель управління запасами без дефіциту
- •Стохастична модель управління запасами за умови, що попит характеризується нормальним законом розподілу
- •Стохастична модель управління запасами за умови штрафу за дефіцит
- •Зм 8. Задачі та моделі заміни
- •Отже, рекурентне співвідношення для періоду т буде мати вигляд:
- •Якщо обладнання після списання реалізується, то рекурентне свіввідношення має вигляд
- •Зм 9. Багатокритеріальні задачі
- •Додаток а Приклад використання надбудови SimplexWin для розв’язування задач лінійного програмування в симплексних таблицях
- •Додаток б Приклад використання Excel для розв" язання симплексних задач лінійного програмування за допомогою надбудови "Поиск решения"
- •Додаток в Приклад використання Excel для розв’язання транспортних задач лінійного програмування (тзлп) за програмою "Поиск решения"
- •Список рекомендованої літератури Підручники та навчальні посібники
- •Електронні ресурси
- •Марченко Володимир Петрович Оптимізаційні методи і моделі
- •0305 “ Економіка та підприємництво ”
4.1. Метод відтинання Гоморі
Розв'язання. Для побудови економіко-математичної моделі позначимо:
х1 - кількість машино-змін агрегату марки А, шт.;
х2 - кількість машино-змін агрегату марки В, шт.;
W – орендна плата, грн.
Тоді, умова задачі в математичній формі буде записана так:
1. Умова виконання механізованих робіт: 12х1 + 16х2 = 60
2. Умова витрат палива: 40 х1 + 60 х2 ≤ 230
3. Умова невід"ємності змінних :х1 ≥ 0; х2≥ 0
4. Змінні х1 та х2 - цілі числа.
Критерій оптимальності - мінімум орендної плати
Wmin = 70 х1 + 80 х2
Для запису задачі в канонічній формі введемо додаткову невідому S1 та штучну невідому А1, де S1- невикористана кількість палива, кг.
В результаті отримаємо: знайти Wmin = 0 - ( - 70 х1 - 80 х2)
при обмеженнях:
1) 12х1 + 16х2 + А1 = 60
2) 40х1 + 60х2 + S1 = 230
Розв’яжемо отриману М-задачу в симплексних таблицях.
Симплексна таблиця 4.1
Базисні невідомі |
Значення базисних невідомих |
х1 |
х2 |
S1 |
А1 |
α |
А1 |
60 |
12 |
16 |
0 |
1 |
33/4 |
Ѕ1 |
230 |
40 |
60 |
1 |
0 |
35/6 |
Wmin |
0 |
-70 |
-80 |
0 |
0 |
- |
Fmin |
60 |
12 |
16 |
0 |
1 |
- |
Симплексна таблиця 4.2
Базисні невідомі |
Значення базисних невідомих |
х1 |
х2 |
S1 |
х2 |
3 3/4 |
3/4 |
1 |
0 |
Ѕ1 |
5 |
-5 |
0 |
1 |
Wmin |
300 |
-10 |
0 |
0 |
Отримуємо оптимальний розв’язок задачі: Wmin = 300, х1 = 0 , х2 = 3 3/4,
Ѕ1 = 5. Розв’язок не цілочисловий, тому вводимо обмеження-відтинання. Визначаємо рядок, який містить max f{bi}, де bі – дробова частина базисної невідомої (х2). Для цього рядка запишемо рівняння, виділивши цілі і дробові частини коефіцієнтів:
(3 + 3/4) = (0 + 3/4)х1 +(1+0)* х2 + (0+0)* Ѕ1
Використовуючи формулу Ui = - f{bi}, запишемо рядок-відтинання U1
- 3/4= 3/4х1 + 0*х2 + 0*S1,
який приймається за розв’язуючий. Розв’язуючий стовпчик вибирається за максимальним значенням (за модулем) серед коефіцієнтів розв’язуючого рядка.
Симплексна таблиця 4.3
Базисні невідомі |
Значення базисних невідомих |
х1 |
х2 |
S1 |
х2 |
3 3/4 |
3/4 |
1 |
0 |
Ѕ1 |
5 |
-5 |
0 |
1 |
U1 |
-3/4 |
-3/4 |
0 |
0 |
Zmin |
300 |
-10 |
0 |
0 |
Симплексна таблиця 4.4
Базисні невідомі |
Значення базисних невідомих |
х1 |
х2 |
S2 |
х2 |
3 |
0 |
1 |
0 |
Ѕ1 |
10 |
0 |
0 |
1 |
Х1 |
1 |
1 |
0 |
0 |
Zmin |
310 |
0 |
0 |
0 |
Цілочисловий оптимальний розв’язок дорівнює: Wmin = 310 , х1 = 1, х2 = 3, S2 = 10.