Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ММС_електронне видання.doc
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
3 Мб
Скачать
☆

Завдання 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 тис.т.