- •Навчальне видання Вітлінський Вальдемар Володимирович Наконечний Степан Ількович терещенко Тетяна Опанасівна математичне програмування
- •03680, М. Київ, просп. Перемоги, 54/1
- •Рекомендована література 245
- •1.1. Предмет курсу «математичне програмування»
- •Тема 1. Предмет, особливості та сфери застосування математичного програмування в економіці. Класифікація задач
- •Тема 9. Задачі динамічного програмування
- •Розділ 2
- •2.1. Загальна математична модель лінійного програмування
- •Приклад 2.1.
- •2.2. Форми запису задач лп
- •2.3. Геометрична інтерпретація злп
- •2.5. Графічний метод розв’язування задач лінійного програмування
- •Задача 2.1.
- •Задача 2.2.
- •Задача 2.3.
- •Задача 2.4.
- •2.5.3. Приклади та завдання для самостійної роботи
- •Задача 2.5.
- •Задача 2.6.
- •Задача 2.7.
- •Задача 2.8.
- •Задача 2.9.
- •Задача 2.35.
- •Задача 2.36.
- •§ 2.6. Симплексний метод розв’язування задач лп
- •Задача 2.41.
- •Задача 2.42.
- •Задача 2.43.
- •Задача 2.44.
- •2.6.3. Приклади та завдання для самостійної роботи
- •Задача 2.45.
- •Задача 2.46.
- •Задача 2.47.
- •Задача 2.48.
- •Задача 2.49.
- •2 .8. Контрольні запитання
- •2.9. Теми рефератів
- •2 .10. Основні терміни та поняття
- •Тема 10. Моделі та методи стохастичного програмування
- •Тема 11. Елементи теорії ігор
- •Розділ 3 двоїстість у лінійному програмуванні
- •3.2. Теореми двоїстості
- •3.3. Навчальні завдання
- •Задача 3.1.
- •Задача 3.2.
- •Задача 3.3.
- •3 .6. Контрольні запитання
- •3 .7. Теми рефератів
- •4.1. Економічна інтерпретація двоїстої задачі
- •4.2. Навчальні завдання
- •Задача 4.1.
- •Задача 4.2.
- •Задача 4.3.
- •Задача 4.4.
- •Задача 4.5.
- •Задача 4.6.
- •Задача 4.7.
- •Задача 4.8.
- •Задача 4.9.
- •Задача 4.10.
- •Задача 4.11.
- •Задача 4.12.
- •Задача 4.13.
- •Задача 4.20.
- •Задача 4.21.
- •4.4. Заключні зауваження
- •5.2. Метод потенціалів
- •5.3. Навчальні завдання
- •Задача 5.1.
- •Задача 5.2.
- •Задача 5.3.
- •Задача 5.4.
- •Задача 5.37.
- •Задача 5.38.
- •Задача 5.39.
- •Задача 5.40.
- •5.5. Заключні зауваження
- •5.6. Контрольні запитання
- •5 .7. Теми рефератів
- •5 .8. Основні терміни та поняття
- •4.5. Контрольні запитання
- •4 .6. Теми рефератів
- •4 .7. Основні терміни та поняття
- •Розділ 6
- •6.1. Цілочислове програмування
- •6.1.1. Постановка задачі
- •6.1.2. Метод Гоморі
- •Задача 6.1.
- •6.1.3. Метод «віток і меж»
- •6.1.4. Приклади цілочислових економічних задач
- •Задача 6.2.
- •Задача 6.3.
- •Задача 6.4.
- •Задача 6.5.
- •Задача 6.6.
- •6.1.5. Приклади та завдання для самостійної роботи
- •Задача 6.7.
- •Задача 6.8.
- •Задача 6.9.
- •Задача 6.10.
- •Задача 6.11.
- •Задача 6.11.
- •Задача 6.11.
- •2) Максимізації комплектів, до яких деталі входять відповідно 6.2. Дробово-лінійне програмування
- •6.2.1. Постановка задачі та алгоритм розв’язування
- •6.2.2. Приклади дробово-лінійних задач
- •Задача 6.14.
- •Задача 6.15.
- •Задача 6.16.
- •6.2.3. Приклади та завдання для самостійної роботи
- •Задача 6.17.
- •Задача 6.18.
- •6.3. Нелінійне програмування
- •6.3.1. Постановка задачі
- •6.3.2. Труднощі розв’язування задач нелінійного програмування
- •6.3.3. Метод множників Лагранжа
- •Задача 6.19.
- •6.3.4. Приклади задач нелінійного програмування
- •Задача 6.20.
- •6.3.5. Приклади та завдання для самостійної роботи
- •Задача 6.21.
- •Задача 6.22.
- •6.4. Динамічне програмування
- •6.4.2. Методика розв’язування динамічних задач
- •6.4.3. Приклади розв’язування динамічних задач
- •Задача 6.23.
- •Задача 6.24.
- •6.4.4. Приклади та завдання для самостійної роботи
- •Задача 6.25.
- •Задача 6.26.
- •Задача 6.27.
- •Задача 6.28.
- •Задача 6.29.
- •Задача 6.30.
- •Задача 6.31.
- •Задача 6.32.
- •Задача 6.33.
- •6.5 Теорія ігор
- •6.5.1. Основні поняття теорії ігор
- •Задача 6.34.
- •Задача 6.35.
- •6.5.3. Приклади та завдання для самостійної роботи
- •Задача 6.36.
- •6.6. Стохастичне програмування
- •6.6.1 Постановка задач і методи розв’язування
- •6.6.2. Приклади стохастичних економічних задач
- •Задача 6.37.
- •Задача 6.38.
- •Задача 6.39.
- •Задача 6.40.
- •Задача 6.41.
- •Задача 6.42.
- •Задача 6.43.
- •6.6.3. Приклади та завдання для самостійної роботи
- •Задача 6.44.
- •Задача 6.45.
- •Задача 6.46.
- •Задача 6.45.
- •Задача 6.46.
- •6.7. Заключні зауваження
- •6.8. Контрольні запитання
- •6 .9. Теми рефератів
- •6 .10. Основні терміни та поняття
Задача 4.21.
Фірма виготовляє
продукцію трьох видів А, В і С, використовуючи
для цього верстати видів 1, 2 та 3. Для
виробництва продукції А використовують
усі три верстати, для виробництва
продукції В — лише 1 та 3, а для продукції
С — лише 1 та 2. Тривалість обробки одиниці
продукції кожного виду наведено в
таблиці:
Ресурс |
Норма витрат на одиницю продукції за видами |
||
А |
В |
С |
|
1 |
1 |
2 |
1 |
2 |
3 |
— |
2 |
3 |
1 |
4 |
— |
Час роботи верстата 1 для виробництва продукції становить 430 ум. од., верстата 2 — 460 ум. од. і верстата 3 — 450 ум. од. Ціна одиниці продукції А, В і С становить відповідно 4, 2 та 5 ум. од. Керівництво фірми має намір визначити оптимальний план виробництва продукції, який дасть найбільший дохід.
Остання симплекс-таблиця має такий вигляд:
Базис |
Сбаз |
План |
4 |
2 |
5 |
0 |
0 |
0 |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
|||
х2 |
2 |
100 |
–1/4 |
1 |
0 |
1/2 |
–1/4 |
0 |
х3 |
5 |
230 |
3/2 |
0 |
1 |
0 |
1/2 |
0 |
х6 |
0 |
50 |
2 |
0 |
0 |
–2 |
1 |
1 |
Zj – Cj ≥ 0 |
1350 |
3 |
0 |
0 |
1 |
2 |
0 |
Розглянути та проаналізувати наведені далі ситуації.
1. Загострення конкуренції на ринку збуту призвело до зниження цін на продукцію А та С відповідно до 3 та 2 ум. од. Визначити новий оптимальний план і максимальний дохід фірми від виробництва своєї продукції.
2. Припустимо, що при додаткових витратах 500 ум. од. можна збільшити час роботи верстатів 1 та 2 на 200 ум. од. кожного. Чи вигідно це? Відповідь пояснити. Визначити оптимальний план та дохід фірми в такій ситуації.
3. Перед фірмою постає потреба обмежити виробництво продукції В величиною 80 ум. од. Як необхідно скоректувати оптимальний план виробництва продукції відповідно до цієї вимоги?
4. Керівництво фірми цікавить, чи має сенс налагоджувати виробництво нової продукції вартістю 5 ум. од. за одиницю, якщо для її виробництва потрібні верстати 2 і 3, час обробки на яких становить відповідно 2 та 3 ум. од. Якщо відповідь ствердна, то якими мають бути новий оптимальний план виробництва продукції та дохід фірми?
4.4. Заключні зауваження
Теорія двоїстості є потужним математичним апаратом обґрунтування структури виробництва в передплановому періоді. Вона дає змогу насамперед визначити статус ресурсів та інтервали стійкості двоїстих оцінок відносно зміни запасів дефіцитних ресурсів. В умовах ринкової економіки ціни на ресурси можуть змінюватися в доволі широких межах. Крім цього, постачальники не за своєю волею можуть не виконати попередніх домовленостей. Тому аналіз ринку ресурсів у передплановому періоді має суттєве значення. Важливою є проблема заміни даного дефіцитного ресурсу іншим, більш дорогим.
Використання двоїстих оцінок дає можливість визначити рентабельність кожного виду продукції, яка виробляється підприємством. При цьому можна оцінити інтервали можливої зміни цін одиниці кожного виду продукції, що дуже важливо в умовах ринку.
Отже, аналіз лінійної економіко-математичної моделі на чутливість дає широкий спектр динамічної інформації про визначений оптимальний план і змогу дослідити вплив можливих змін на результати господарської діяльності.
Розроблена економіко-математична модель може бути використана для машинної імітації процесу виробництва. Це дає можливість перевірити:
1) за яких умов оптимальний план є стійким;
2) чи є вигідним додаткове залучення ресурсів;
3) як зміниться ефективність виробництва в разі загострення конкуренції на ринку збуту (оцінити виправданість у цій ситуації зниження цін на продукцію);
4) доцільність виробництва нової продукції;
5) як вплине на ефективність діяльності підприємства порушення споживачами продукції попередніх угод — відмова від часРозділ 5
ТРАНСПОРТНА ЗАДАЧА
5.1. ПОСТАНОВКА ТРАНСПОРТНОЇ ЗАДАЧІ
Транспортна задача — це специфічна задача лінійного програмування, застосовувана для визначення найекономічнішого плану перевезення однорідної продукції від постачальників до споживачів.
Математична модель транспортної задачі має такий вигляд:
(5.1)
за обмежень
; (5.2)
; (5.3)
, (5.4)
де хij — кількість продукції, що перевозиться від і-го постачальника до j-го споживача; сij — вартість перевезення одиниці продукції від і-го постачальника до j-го споживача; аi — запаси продукції і-го постачальника; bj — попит на продукцію j-го споживача.
Якщо в транспортній задачі загальна кількість продукції постачальників дорівнює загальному попиту всіх споживачів, тобто
, (5.5)
то таку транспорту задачу називають збалансованою, або закритою. Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою.
Планом транспортної задачі називають будь-який невід’ємний розв’язок системи обмежень (5.2)—(5.4) транспортної задачі, який позначають матрицею .
Оптимальним планом транспортної задачі називають матрицю , яка задовольняє умови задачі і для якої цільова функція (5.1) набуває найменшого значення.
Т еорема (умова існування розв’язку транспортної задачі). Необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість, тобто .