Тема: Математичне програмування

1. Двоїсті оцінки, їх економічний сенс на прикладі задачі про використання та оцінку ресурсів.

2. Економічні задачі, які зводяться до транспортної.

 

 

Приклади економічних задач, що зводяться до транспортних моделей

Транспортна задача часто використовується для розв’язання економічних задач, які за умовою не мають нічого спільного з транспортуваннями вантажів, і величини можуть залежно від конкретної задачі означати відстань, час, продуктивність тощо. Наведемо постановку найтиповіших економічних задач, що зводяться до транспортної моделі.

Оптимальний розподіл обладнання. Домовимося для спрощення, що розглядається модель закритої транспортної задачі (будь-яка відкрита задача зводиться до закритої перетвореннями, розглянутими в § 5.5).

Обладнання m різних видів необхідно розподілити між n виробничими дільницями. Продуктивність одиниці обладнання i -го виду на j -ій виробничій дільниці дорівнює , . Відомі потреби кожної j -ої дільниці в обладнанні, що становлять , а також запаси обладнання кожного i -го виду — . Необхідно знайти оптимальний розподіл обладнання за виробничими дільницями, за якого сумарна продуктивність виробництва буде максимальною.

Ця задача зводиться до транспортної за умови, що продуктивність лінійно залежить від кількості застосовуваного обладнання. «Постачальниками» в задачі є види обладнання, а «споживачами» — виробничі дільниці. Запаси постачальників — це наявна кількість обладнання кожного виду, а потреби споживачів — вимоги на необхідну кількість обладнання для кожної виробничої дільниці.

Нехай — кількість одиниць обладнання i -го виду, яку буде виділено j -ій виробничій дільниці . Сумарна продуктивність виробництва визначатиметься за формулою: . Оскільки запаси кожного типу обладнання обмежені, то маємо: , . З другого боку, потреби кожної дільниці в обладнанні є також фіксованими, тому: , . Отже, загалом ми маємо таку математичну модель транспортної задачі:

max

У даній задачі необхідно максимізувати значення цільової функції F. Для переходу до стандартної моделі транспортної задачі слід замінити функцію F на протилежну функцію , яку необхідно мінімізувати:

.

Розв’язуючи цю задачу, будемо використовувати взяті з протилежними знаками значення продуктивностей . Розв’язок можна відшукати одним з відомих методів.

Розглянемо приклад задачі про оптимальний розподіл обладнання.

Машинно-тракторний парк, який обслуговує кілька фермерських господарств, налічує 23 трактори, з них:

«Бєларусь», МТЗ-80 — 8 одиниць,

ЮМЗ-6АЛК — 10 одиниць,

MEZZO 6100 — 5 одиниць.

Одночасно надійшли замовлення від трьох фермерських господарств з такими потребами: 10, 5 і 5 одиниць техніки. Залежно від виконуваних технологічних операцій та особливостей ґрунтів господарств продуктивність виконання робіт зазначеними тракторами в кожному з господарств є різною і подається в табл. 5.33.

Таблиця

Трактор	Продуктивність трактора в господарстві, еталонних гектарів на добу
І господарство	ІІ господарство	ІІІ господарство
«Бєларусь», МТЗ-80
ЮМЗ-6АЛК
MEZZO 6100

Визначити оптимальний розподіл техніки по господарствах.

Для розв’язування задачі скористаємось методом потенціалів. Задача належить до відкритого типу транспортних задач, бо кількість наявної техніки дорівнює 23 одиницям, а потреби — 20 одиницям, тому необхідно ввести фіктивного споживача (четверте господарство) з потребою, що дорівнює 3 одиницям техніки.

Всі значення продуктивностей техніки з наведеної таблиці використовуватимемо, розв’язуючи задачу, з протилежним знаком.

Застосовуючи метод потенціалів, отримаємо оптимальний план розподілу техніки, що наведений у табл. 5.34.

Таблиця

Трактор	Продуктивність трактора в господарстві, етал. га на добу
І господарство (10 один.)	ІІ господарство (5 один.)	ІІІ господарство (5 один.)	ІV господарство (фіктивне) (3 один.)
«Бєларусь», МТЗ-80 (8 один.)	–50	–63	–59
ЮМЗ-6АЛК (10 один.)	–49	–56	–50
MEZZO 6100 (5 один.)	–61	–58	–62

За оптимальним планом кожне господарство отримує потрібну кількість тракторів. Однак, оскільки задача належить до відкритого типу, значення відповідає фіктивно введеному споживачеві. Це означає, що трактори ЮМЗ-6АЛК будуть розподілені не повністю. З десяти їх одиниць розподілено тільки 7.

Загальне значення продуктивності тракторів становить 1146 еталонних гектарів на добу.

Задача про призначення. Потрібно виконати n видів робіт, на які претендують n кандидатів. Витрати на оплату праці i -го кандидата за виконання j -ої роботи дорівнюють . Кожен кандидат може бути призначений лише на одну роботу, і кожна робота має виконуватися лише одним кандидатом. Потрібно знайти оптимальне призначення кандидатів на виконання робіт, за якого сумарні витрати на виконання всіх робіт будуть мінімальними.

Нехай дорівнює одиниці, якщо i -ий кандидат виконує j -ту роботу, та дорівнює нулю в протилежному разі. Тоді умову, що кожен кандидат має виконувати лише одну роботу, запишемо у вигляді: . Умова виконання кожної роботи лише одним кандидатом має вигляд: . Цільова функція має такий вираз: . Отже, маємо математичну модель транспортної задачі:

min

Найзручнішим методом розв’язання задачі про призначення є угорський метод.

Розглянемо приклад економічної постановки задачі про призначення.

Науково-дослідний інститут отримав замовлення на виконання чотирьох дослідних проектів. Кінцеві результати першого проекту є початковими даними для другого проекту, а кінцеві результати другого проекту — початковими для третього і, нарешті, результати третього проекту є початковими значеннями для четвертого. Виконавцями проектів можуть бути чотири відділи інституту. Кожен відділ визначив кількість часу, яка необхідна для виконання ним науково-дослідних робіт. Матриця витрат часу має вигляд:

.

Кожен елемент аij матриці Т означає тривалість виконання i -им відділом j -го проекту. Витрати часу наведені в тижнях. Необхідно так вибрати відділи, які будуть працювати над проектами, щоб тривалість виконання всіх проектів була мінімальною.

Для розв’язування задачі вводимо змінні: , якщо i -ий відділ призначено для виконання j -го проекту; та в протилежному разі.

Розв’язуючи задачу угорським методом, матимемо два альтернативні оптимальні плани. Перший оптимальний план:

,

тобто перший відділ слід призначити для виконання першого проекту

другий відділ — для виконання другого проекту

третій відділ — для виконання третього проекту

а четвертий відділ — для виконання четвертого проекту

За такого розподілу виконавців загальна тривалість виконання чотирьох проектів дорівнюватиме:

.

Другий оптимальний план: .

В такому разі тривалість виконання всіх проектів також дорівнюватиме 17 тижням: