- •Навчальне видання Вітлінський Вальдемар Володимирович Наконечний Степан Ількович терещенко Тетяна Опанасівна математичне програмування
- •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. Основні терміни та поняття
Задача 6.10.
Побудувати модель задачі
розподілу капіталовкладень, які можуть
спрямовуватися на втілення чотирьох
проектів протягом трьох послідовних
років.
Очікувані розміри прибутку від реалізації кожного проекту та розподіл необхідних капіталовкладень, млн грн., за роками відбиває таблиця:
Проект |
Розподіл капіталовкладень за роками |
Прибуток |
||
1-м |
2-м |
3-м |
||
1 |
6 |
2 |
8 |
40 |
2 |
5 |
7 |
6 |
50 |
3 |
4 |
6 |
9 |
45 |
4 |
8 |
3 |
7 |
52 |
Максимальний обсяг капіталовкладень |
20 |
25 |
18 |
— |
Передбачається, що кожний затверджений проект має бути реалізовано за трирічний період. Вибрати сукупність проектів, яка забезпечить отримання максимального сумарного прибутку.
● Вказівка. Для побудови моделі задачі користуватися бульовими змінними.
Задача 6.11.
Побудувати модель задачі
планування виробничої лінії, що охоплює
виконання шести операцій для виготовлення
двох різних виробів на одному верстаті.
Послідовність і тривалість операцій
відбиває рисунок. Строки виготовлення
виробів А і В становлять відповідно 58
і 46 днів.
● Зауваження. У кожний момент часу на верстаті може виконуватися лише одна операція.
Задача 6.11.
Побудувати модель задачі
цілочислового програмування для вибору
варіанта розміщення чотирьох різних
видів технологічного устаткування на
двох виробничих дільницях цеху. Витрати
на підготовку та встановлення устаткування
відбиває таблиця:
Дільниця |
Витрати на встановлення устаткування |
Витрати на підготовку |
|||
1 |
2 |
3 |
4 |
||
1 |
4 |
2 |
7 |
9 |
10 |
2 |
6 |
5 |
3 |
6 |
14 |
Визначити такий порядок розміщення устаткування на дільницях, за якого сумарні витрати на його встановлення та підготовку є мінімальними.
Задача 6.11.
Розв’язати задачу оптимального
розкрою двох заготівок завдовжки 15 і
12 м на деталі трьох типів завдовжки
3, 4 і 2 м. Відомо, що запас заготівок
становить відповідно 100 і 80 одиниць, а
попит на деталі — 30, 20, 15 одиниць.
Знайти план оптимального розкрою заготівок за двома варіантами:
1) мінімізації відходів від розкрою;
2) Максимізації комплектів, до яких деталі входять відповідно 6.2. Дробово-лінійне програмування
6.2.1. Постановка задачі та алгоритм розв’язування
Розв’язуючи економічні задачі, часто за критерій оптимальності беруть показники рентабельності, продуктивності праці тощо, які математично подаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так:
за умов
,
.
Припускають, що знаменник цільової функції в області допустимих розв’язків системи обмежень не дорівнює нулю.
Алгоритм розв’язування задачі дробово-лінійного програмування передбачає зведення її до задачі лінійного програмування. Щоб виконати таке зведення, позначимо
,
зробимо заміну змінних
.
і запишемо економіко-математичну модель:
за умов
,
,
.
Дістали задачу лінійного програмування, яку можна розв’язати симплексним методом. Нехай оптимальний план
Оптимальні значення x0j знайдемо за формулою
.