- •Завдання 1.1. Прогнозування за допомогою ковзного середнього
- •Завдання 1.2. Прогнозування за допомогою лінії тренду
- •Завдання 1.3. Лінійний прогноз (регресія)
- •Власне, це і є лінійна регресійна модель, яка для вихідних даних, використовуваних у прикладі, виглядає саме так. Розрахункові значення моделі і прогноз
- •Завдання №2 вирішення оптимізаційних задач
- •Завдання 2.1. Оптимізація плану виробництва
- •Завдання 2.2. Транспортна задача
- •Завдання 2.3. Управління запасами
- •Задача 2.5. Призначення на посаду
- •Завдання 2.4. Розподіл однорідних ресурсів
- •Завдання 2.7. Ефективний портфель по Марковіцу
- •Задача 2.8.Вирішення економічних задач за допомогою теорії ігор.
- •49600, М. Дніпропетровськ, просп. К. Маркса, 19.
Завдання 2.4. Розподіл однорідних ресурсів
Виконати постановку і рішення економіко-математичної моделі розподілу однорідних ресурсів. Записати цільову функцію та обмеження. Описати економічну постановку задачі.
Приклад.
Постановка завдання (рис. 2.12).
Рис. 2.12. Вхідні дані для вирішення моделі
Знайти оптимальний розподіл 3-х машин по 4-х роботах, щоб за умови виконання заданих обсягів загальна вартість всіх вироблених робіт була б мінімальною.
Початкові дані: матриця собівартості робіт; ресурси машин (час); продуктивність машин; обсяг робіт.
Економіко-математична модель.
Знайти таку матрицю розподілу ресурсів, щоб
Загальні витрати = Матриця_собівартості * Матриця_розподілу min
При обмеженнях: Зроблено = Обсяг;
використані ресурси <= Ресурси; Матриця_розподілу > = 0.
Реалізація в Excel.
Створюємо таблицю з формулами, які пов'язують план, обмеження і цільову функцію (Вартість) (рис. 2.13):
Рис. 2.13. Вирішення моделі в Excel
стовпець Всього заповнюємо формулою суми по рядках Матриця_розподілу;
стовпець Резерв заповнюємо формулою: Ресурс-Всього;
рядок Зроблено заповнюємо формулою: = СУММПРОИЗВ (Продуктивність; Работа_n);
в цільову комірку вводимо формулу: = СУММПРОИЗВ (Матриця_собівартості; Матриця_розподілу).
Рис. 2.14. Налаштування надбудови Пошук рішення для вирішення моделі
Запускаємо програму Пошук рішень (рис. 2.14) командою Дані /Аналіз /Пошук рішення (В Excel 2007/2010) Сервіс / Пошук рішення (В Excel 2003 і нижче). В полях Встановити цільову комірку, Змінюючи осередки, Обмеження вводимо відповідні адреси осередків. Так як це лінійна модель, то не забуваємо фіксувати в вікні Параметри пошуку рішень перемикач на позицію Лінійна модель і невід'ємні значення. Натискаємо кнопку Виконати і у вікні Результати пошуку рішення.
Рис. 2.15.Результати обчислення моделі
Аналіз результатів.
При оптимальному плані (рис. 2.15) загальні витрати становлять 379,67 д. Од., При чому 1-я машина не завантажена повністю, її резерв становить 23,3.
Тіньові ціни повністю використаних ресурсів показують, що із збільшенням їх ресурсу загальні витрати зменшаться. Тіньові ціни обсягів робіт показують, як будуть збільшуватися загальні витрати при збільшенні обсягів робіт.
Нормовані вартості вказують на скільки збільшитися загальна вартість робіт, якщо ми примусово поставимо машину на «невигідну роботу».
Задача 2.5. Призначення на посаду
Виконати розрахунок оптимального призначення на посаду в досліджуваній компанії.
Записати цільову функцію, обмеження, описати економічну постановку задачі.
(Посади в прикладі позначені як Посада 1,2 .... - Розписати посади для своєї компанії).
Приклад.
Постановка завдання.
Назва і завдання відповідної моделі про призначення (assignment problem) - безпосередньо виходити від практичної кадрової ситуації, коли претендентів потрібно призначити на вакантні посади найкращим чином.
Критерій максимізації загального афекту використовується тоді, коли відомі про кожного претендента задані оцінки здатності виконання певної функції (чим вище, тим краще), мінімізації - коли, скажімо, для кожного претендента задана величина витрат на його підготовку для певної діяльності (чим вище, тим гірше ).
Приклад. Підприємство оголосило набір працівників для нового цеху - вказало назви семи посад і кількість вакансій по кожній з них. Кадрова служба зібрала від 18 претендентів на ці посади, провела тестування з кожної з них і за результатами визначила 5 груп з однаковими оцінками і можливостями, отримали відповідно таблицю середніх оцінок їх умінь і знань.
Потрібно призначити на вакантні посади претендентів таким чином, що б загальна ефективність виконання ними відповідних обов'язків була максимальною.
Особливість - наявність високої оцінки ще не гарантує успіх, оскільки метою оптимізації про призначення є максимальний загальний ефект. Економіко-математична модель.
Знайти таку матрицю призначень, щоб
Загальний ефект = Матриця_оцінок * Матриця_призначень мах
При обмеженнях: Призначено <= Встого_претендентів;
Зайнято = Всього_вакансій.
Матриця_призначень> = 0.
Реалізація в Excel.
Створюємо таблицю з формулами (рис. 2.16), які пов'язують план, обмеження і цільову функцію (Заг_ефект):
Рис. 2.16. Реалізація моделі в Excel
в стовпець Призначено вводимо формулу суми по термінах матриці призначено;
в стовпець Залишилося вводимо формулу Всього претендентів-Призначено;
в рядок Зайнято вводимо формулу суми по стовпцях матриці призначено;
цільову комірку заповнюємо формулою: = СУММПРОИЗВ (Матриця_оцінок; Матриця_призначень).
Рис. 2.17. Налаштування надбудови Пошук рішень для вирішення моделі
Запускаємо програму Пошук рішень (Рис. 2.17) командою Дані / Аналіз / Пошук рішення (В Excel 2007) Сервіс / Пошук рішення (В Excel 2003 і нижче). В полях Встановити цільову комірку, Змінюючи осередки, Обмеження вводимо відповідні адреси осередків. Так як це лінійна модель, то не забуваємо фіксувати в вікні Параметри пошуку рішень перемикач на позицію Лінійна модель і невід'ємні значення. Натискаємо кнопку Виконати і у вікні Результати пошуку рішення (Рис. 2.18).
Рис. 2.18. Результати вирішення моделі
Аналіз результатів.
Оптимальний план призначень (дивись таблицю) забезпечує загальну ефективність 63.
Тіньові ціни для претендентів показують на скільки зміниться цільова функція при збільшенні даного претендента на 1 од. Тіньові ціни для вакансій показують «цінність» відповідних посад.
Нормовані вартості для нульових призначень означають:
на скільки потрібно збільшити оцінку, щоб можна було претендувати на призначення;
на скільки зменшитися загальна ефективність, якщо на посаду буде призначений цей «невигідний» претендент.
Задача 2.6. Обґрунтування інвестиційних вкладень в розвиток підприємств методом динамічного програмування
Порядок виконання роботи:
1. Вивчити приклад виконання роботи.
2. Вирішити задачу динамічного програмування для свого підприємства
3. Зробити висновки.
Методичні вказівки до виконання завдання.
Розглянемо застосування методу динамічного програмування на прикладі розподілу капіталовкладень між 4-ма підприємствами. Нехай загальна сума коштів, що інвестуються в розвиток складає не більше 5-ти мільйонів гривень. На основі техніко-економічних розрахунків встановлено, що в результаті реконструкції в залежності від кількості витрачених коштів підприємства будуть мати продуктивність, приведену в табл. 2.1. Необхідно визначити оптимальний розподіл коштів між підприємствами, що забезпечує максимальне збільшення продуктивності підприємств. Таким чином, в цій оптимізаційній задачі використовується критерій - сумарна продуктивність підприємств.
Таблиця 2.1.
|
Кошти, що вкладаються в розвиток (млн. грн.) |
|||||
№ підприємства |
0 |
1 |
2 |
3 |
4 |
5 |
|
Продуктивність в результаті розвитку (тис. т.) |
|||||
1 |
400 |
500 |
550 |
700 |
750 |
1000 |
2 |
4000 |
4200 |
4300 |
4500 |
4600 |
4700 |
3 |
0 |
100 |
400 |
800 |
850 |
900 |
4 |
600 |
750 |
900 |
950 |
1100 |
1200 |
Нехай х1, х2, х3, х4 - капіталовкладення в розвиток відповідно першого, другого, третього і четвертого підприємства, 0≤ хi ≤ 5, i = 1,4. Позначимо f1 (x), f2 (x), f3 (x), f4 (x) - функції зміни продуктивності першого, другого, третього і четвертого підприємства при вкладенні в їх розвиток х млн. грн. Цим функціям відповідають рядки 1, 2, 3, 4 в табл.1. Визначимо максимум функції цілі:
F (х1, х2, х3, х4) = f1 (x) + f2 (x) + f3 (x) + f4 (x).
При цьому на капіталовкладення х1, х2, х3, х4 накладені обмеження
х1 + х2 + х3 + х4 = А, млн. грн.
В основі методу динамічного програмування, використаного для вирішення поставленого завдання, лежить принцип оптимальності.
Згідно з цим принципом, вибравши деякий початковий розподіл ресурсів, виконуємо багатокрокову оптимізацію, причому на найближчому кроці вибираємо такий розподіл ресурсів, щоб він у сукупності з оптимальним розподілом на всіх наступних кроках приводив до максимального виграшу на всіх наступнихкроках, включаючи даний.
Виділимо в нашій задачі 3 кроки:
- А млн. грн. вкладаються в перше, друге підприємства одночасно;
- А млн. грн. вкладаються в перше, друге, третє підприємства разом;
- А млн. грн. вкладаються в чотири підприємства одночасно.
Позначимо: F1,2 (А), F1,2,3 (А), F1,2,3,4 (А) - відповідно оптимальні розподіли коштів для першого, другого і третього кроків.
Алгоритм методу динамічного програмування складається з двох етапів. На першому етапі виконується умовна оптимізація, яка полягає в тому, що для кожного з трьох кроків знаходять умовний оптимальний виграш для F1,2 (А), F1,2,3 (А), F1,2,3,4 (А). На другому етапі виконується безумовна оптимізація. Використовуючи результати першого етапу, знаходять величини капіталовкладень в розвиток підприємств х1, х2, х3, х4, що забезпечують максимальну продуктивність групи підприємств.
Перший етап включає наступні кроки:
1) Обчислення максимуму критерію оптимізації для різних значень капіталовкладень х = 0, 1, 2, 3, 4, 5, які використовуються тільки для підприємств 1 і 2 Розрахунок ведеться за формулою:
F1,2 (А) = max [f1 (x) + f2 (A - x)];
0 ≤ x ≤ 5;
0 ≤ A ≤ 5.
Результати розрахунку представлені в табл.2.2.
Таблиця 2.2.
|
|
х2 = А - х |
|||||
х1 |
f1( x) |
0 |
1 |
2 |
3 |
4 |
5 |
|
|
f2( А - x ) |
|||||
|
|
4000 |
4200 |
4300 |
4500 |
4650 |
4700 |
0 |
400 |
4400 |
4600 |
4700 |
4900 |
5050 |
5100 |
1 |
500 |
4500 |
4700 |
4800 |
5000 |
5150 |
|
2 |
550 |
4550 |
4750 |
4850 |
5050 |
|
|
3 |
700 |
4700 |
4900 |
5000 |
|
|
|
4 |
750 |
4750 |
4950 |
|
|
|
|
5 |
1000 |
5000 |
|
|
|
|
|
Наприклад, для того, щоб визначити F1,2 (2), треба обчислити
f1 (2) + f2 (0) = 550 + 4000 = 4550;
f1 (1) + f2 (1) = 500 + 4200 = 4700;
f1 (0) + f2 (2) = 400 + 4300 = 4700.
Найбільше з отриманих значень буде F1,2 (2). Решта F1,2 (х) виходять як найбільше значення кожної діагоналі в таблиці (ці значення в таблиці підкреслені:
F2 (0) = 4400; F2 (1) = max (4600, 4500) = 4600;
F2 (2) = max (4550, 4700, 4700) = 4700;
F2 (3) = max (4700, 4750, 4800, 4900) = 4900;
F2 (4) = max (4750, 4900, 4850, 5000, 5050) = 5050;
F2 (5) = max (5000, 4950, 5000, 5050, 5100, 5100) = 5150.
2) Обчислення максимуму критерію оптимізації для різних значень капіталовкладень х = 0, 1, 2, 3, 4, 5, які використовуються тільки для підприємств 1,2 і 3.
Розрахунок ведеться за формулою
F1,2,3 (А) = max [F1,2 (A) + f3 (A - x)];
0 ≤ x ≤ 5;
0 ≤ A ≤ 5.
Результати розрахунків занесемо в табл.2.3, яка аналогічна табл.2.2, тільки замість f1 (x) в ній вказані значення F2 (А), а f2 (A - x) замінена на f3 (A - x).
Таблиця 2.3.
|
|
х3 = А - х |
|||||
A |
F1,2(A) |
0 |
1 |
2 |
3 |
4 |
5 |
|
|
f3( А - x ) |
|||||
|
|
0 |
100 |
400 |
800 |
850 |
900 |
0 |
4400 |
4400 |
4500 |
4800 |
5200 |
5250 |
5300 |
1 |
4600 |
4600 |
4700 |
5000 |
5400 |
5450 |
|
2 |
4700 |
4700 |
4800 |
5100 |
5500 |
|
|
3 |
4900 |
4900 |
5000 |
5300 |
|
|
|
4 |
5050 |
5050 |
5150 |
|
|
|
|
5 |
5150 |
5150 |
|
|
|
|
|
Значення F1,2,3 (A) будуть наступними:
F1,2,3 (0) = 4400; F1,2,3 (1) = 4600; F1,2,3 (2) = 4800;
F1,2,3 (3) = 5200; F1,2,3 (4) = 5400; F1,2,3 (5) = 5500.
3) Обчислення максимуму критерію оптимізації для різних значень капіталовкладень х = 0, 1, 2, 3, 4, 5, які використовуються для всіх підприємств.
Розрахунок ведеться за формулою
F1,2,3,4 (А) = max [F1,2,3 (A) + f4 (A - x)];
0 ≤ x ≤ 5;
0 ≤ A ≤ 5.
Результати розрахунків заносимо в табл.2.4.
Таблиця 2.4.
|
|
х4 = А – х |
|||||
A |
F1,2,3(А) |
0 |
1 |
2 |
3 |
4 |
5 |
|
|
f4( А - x ) |
|||||
|
|
600 |
750 |
900 |
950 |
1100 |
1200 |
0 |
4400 |
5000 |
5150 |
5300 |
5350 |
5500 |
5600 |
1 |
4600 |
5200 |
5350 |
5500 |
5550 |
5700 |
|
2 |
4800 |
5400 |
5550 |
5700 |
5750 |
|
|
3 |
5200 |
5800 |
5950 |
6100 |
|
|
|
4 |
5400 |
6000 |
6150 |
|
|
|
|
5 |
5500 |
6100 |
|
|
|
|
|
Значення F1,2,3,4 (А) в результаті розрахунку будуть наступними:
F1,2,3,4 (0) = 5000; F1,2,3,4 (1) = 5200;
F1,2,3,4 (2) = 5400; F1,2,3,4 (3) = 5800;
F1,2,3,4 (4) = 6000; F1,2,3,4 (5) = 6150.
На цьому перший етап розв'язання задачі динамічного програмування закінчується.
Перейдемо до другого етапу розв'язання задачі динамічного програмування - безумовної оптимізації. На цьому етапі використовуються табл.2.4,2.3,2.2. Визначимо оптимальні капіталовкладення в розвиток підприємств для А = 0, 1, 2, 3, 4, 5 Для цього виконаємо наступні розрахунки.
1) Нехай обсяг капіталовкладень, виділений на розвиток підприємств, складає А = 5 млн. грн.
Визначимо обсяг капіталовкладень на розвиток четвертого підприємства. Для цього використовуємо табл.2.4. Виберемо на ній діагональ, відповідну А = 5 - це значення 6100, 6150, 6100, 5750, 5700, 5600. З цих чисел візьмемо максимальне F1,2,3,4 (5) = 6100 тис. т. Відзначаємо стовпець, в якому стоїть ця величина. Далі визначаємо у відзначеному стовпчику обсяг капіталовкладень в четверте підприємство х4 = 1.
На розвиток першого, другого і третього підприємств залишається
А = 5 - х4 = 4 млн. Грн.
2) Визначимо обсяг капіталовкладень, виділений на розвиток третього підприємства.
Для цього використовуємо табл.3. Виберемо в цій таблиці діагональ, відповідну А = 4 - це значення 5050, 5000, 5100, 5400, 5250. Відзначаємо стовпець, в якому стоїть максимальна (підкреслена) величина продуктивності F1,2,3,4 (4) = 5400 тис.т. Визначаємо значення х3 = 3 млн. грн. у відзначеному стовпчику.
3) На розвиток першого і другого підприємства залишається сума
А = 5 - х4 - х3 = 1 млн. грн.
Визначимо обсяг капіталовкладень на розвиток другого підприємства. Використовуємо для цього табл.2.2. Виберемо в таблиці діагональ, відповідну А = 1 - це значення 4500, 4600, 4300. Відзначаємо стовпець з максимальною величиною продуктивності F1,2 (1) = 4600 тис.т. Тоді в цьому стовпці х2 = 1 млн. грн .
4) Визначимо обсяг капіталовкладень на розвиток першого підприємства. Так як виділені капіталовкладення вичерпані х2 + х3 + 1+ х4 = 5, то на розвиток першого підприємства кошти не виділяються.
Таким чином, для капіталовкладень обсягом А = 5 млн. Грн. оптимальним є вкладення в розвиток другого підприємства 1 млн. грн., третього 3 млн. грн., четвертого - 1 млн. грн., в розвиток першого підприємства кошти не виділяються. При цьому сумарна продуктивність чотирьох підприємств складе 5750 тис.т.
