Транспортні тарифи, гривень з розрахунку на 1 тис. цеглин
| Цегельний завод | Будівельний майданчик | ||||||
| М-1 | М-2 | М-3 | М-4 | М-5 | М-6 | М-7 | |
| З-1 | |||||||
| З-2 | |||||||
| З-3 | |||||||
| З-4 | |||||||
| З-5 |
Потрібно:
1. Визначити оптимальний за критерієм мінімізації загальних транспортних витрат план постачання цеглою будівельних майданчиків.
2. Чи є сенс змінити знайдений план постачання на інший, якщо додатково враховувати витрати на придбання цегли? Відомо, що заводські ціни на цеглу, з розрахунку на 1 тис. цеглин, наступні: З1, З4 – по 500, З2 – 480, З3, З5 – по 520 гривень.
3. Як зміняться закупівельна та транспортна складові оптимальних загальних витрат (дивись завдання 2), якщо на будівельному майданчику М4 відмовляться від цегли, яку виготовляє завод З2?
З метою опрацювання наведених питань пропонуємо:
1). Скласти економіко–математичну модель транспортної задачі. Знайти оптимальний план перевезень на ПК.
2). Скласти економіко–математичну модель виробничо–транспортної задачі, обчислити на ПК оптимальний план закупівель та перевезення цегли за критерієм мінімізації загальних витрат на закупівлю та перевезення. Порівняти знайдений план перевезень з попереднім.
3). Ввести до умов виробничо–транспортної задачі заборону на перевезення за маршрутом З2 ® М4. Знайти новий оптимальний план та порівняти результати з результатами розрахунків у п. 2.
4). Навести інші приклади аналогічних оптимізаційних задач в економічній та управлінській діяльності.
РОЗДІЛ 3. ОПТИМІЗАЦІЯ ПЛАНУ ПОСТАВОК ПРОДУКЦІЇ
ДО СПОЖИВАЧІВ З УРАХУВАННЯМ ВІДПУСКНОЇ ЦІНИ НА ПРОДУКЦІЮ У РІЗНИХ ПОСТАЧАЛЬНИКІВ
(ВИРОБНИЧО–ТРАНСПОРТНА ЗАДАЧА)
З виробничо–транспортною задачею, в якій план забезпечення продукцією споживачів визначається не лише транспортними тарифами, а також відпускними цінами на продукцію у різних споживачів, Ви познайомились, якщо уважно виконували завдання з попереднього розділу. Зараз ми зупинимося на питанні про виробничо–транспортну задачу докладніше.
3.1. Постановка виробничо–транспортної задачі
3.2. Економіко–математична модель та умова існування розв’язку задачі
3.3. Розв’язування задачі про оптимізацію плану поставок продукції до споживачів з урахуванням відпускної ціни на продукцію у різних постачальників за методом потенціалів шляхом зведення виробничо–транспортної задачі до транспортної
3.4. Розв’язування виробничо–транспортної задачі з використанням інструменту “Поиск решения” Excel
3.5. Завдання для самостійного опрацювання
3.1. Постановка виробничо–транспортної задачі
Виробничо–транспортна задача полягає у тому, щоб з якнайменшими загальними витратами забезпечити попит споживачів. Окрім інформації про розміри попиту до уваги беруться не лише транспортні тарифи на перевезення одиниці продукції від постачальників до споживачів і виробничі потужності постачальників, а також відпускні ціни на продукцію у кожного з постачальників.
Вихідна інформація до задачі:
– кількість підприємств – виробників продукції (постачальників);
– номер окремого постачальника (
);
– виробнича потужність -го виробника;
– відпускна ціна одиниці продукції у -го постачальника;
– кількість споживачів;
– номер окремого споживача (
);
– попит на продукцію з боку -го споживача;
– витрати на перевезення одиниці продукції за маршрутом 
(
, ).
Невідомі:
– обсяг перевезень за маршрутом (, );
– обсяг виготовленої на -му підприємстві та відправленої споживачам продукції ();
– загальні витрати на закупівлю продукції у постачальників і перевезення цієї продукції до споживачів.
3.2. Економіко–математична модель
та умова існування розв’язку задачі
Економіко–математична модель виробничо–транспортної задачі, з урахуванням обраних позначень для відомих і невідомих величин, набирає вигляду:
(3.1)
Цільова функція задачі відбиває вимогу мінімізувати загальні витрати на закупівлю продукції та її перевезення до споживачів. Обмеження задачі враховують вимогу забезпечення попиту кожного із споживачів, умову про відповідність обсягів закупівлі рівням виробничих потужностей кожного із постачальників та балансові рівняння про розподіл виготовленої кожним із підприємств–постачальників продукції між споживачами. Враховуються також вимоги про невід’ємність обсягів виробництва та перевезень продукції.
Математично модель (3.1) являє собою задачу лінійного програмування транспортного типу. Її можна розв’язувати симплекс–методом. Можна також цю задачу звести до транспортної та розв’язувати за методом потенціалів. Але спочатку слід перевірити, чи виконується умова існування розв’язку цієї задачі.
Виробничо–транспортна задача (3.1) розв’язувана тоді і тільки тоді, коли загальні виробничі потужності усіх виробників відповідають сукупному попиту на продукцію з боку всіх споживачів:
(3.2)
В реальних ситуаціях у співвідношенні між обсягами загальних виробничих потужностей та сукупного попиту можуть мати місце такі три різних випадки:
1). Загальні виробничі потужності усіх виробників збігаються із сукупним попитом споживачів:
(3.3)
Таку задачу будемо називати закритою. Закрита задача є розв’язуваною. Особливість закритої задачі полягає у тому, що обсяги виробництва продукції кожним із виробників збігатимуться з його виробничими потужностями. З іншого боку, кожному споживачу буде надіслано продукцію саме у кількості, яка збігається з його попитом.
2). Загальні виробничі потужності виробників перевищують сукупний попит усіх споживачів:
(3.4)
Така виробничо–транспортна задача теж є розв’язуваною. Причому оптимальний план не вимагатиме повного використання загального виробничого потенціалу виробників через економічну недоцільність надсилання споживачам продукції у обсягах, що перевищуватимуть їхній попит. Резерв виробничих потужностей складе величину:
(3.5)
Залучимо до розгляду фіктивного 
-го споживача з рівнем попиту 
. Тоді задача перетвориться на закриту. Причому перевезення за фіктивними маршрутами – визначаються змінними 
– не вимагатимуть ані транспортних витрат, ані витрат на придбання цієї продукції. Вони показують резерв виробничих потужностей -го підприємства (), що лишається через брак сукупного попиту на продукцію.
3). Загальні виробничі потужності усіх виробників менші від сукупного попиту споживачів:
(3.6)
Така виробничо–транспортна задача не є розв’язуваною через наявність дефіциту виробничих потужностей у кількості:
(3.7)
Зараз може виникнути нова задача: як оптимальним чином, нехай і з дефіцитом, максимально забезпечити потреби споживачів? Цю нову задачу можна звести до закритої уведенням фіктивного 
-го виробника з виробничою потужністю 
одиниць продукції. Виготовлена ним продукція та обсяги перевезень продукції від нього споживачам не вимагатимуть аніяких витрат, причому змінні 
, , означатимуть обсяги недопостачання продукції споживачам внаслідок дефіциту виробничих потужностей.
3.3. Розв’язування задачі про оптимізацію плану поставок продукції до споживачів з урахуванням відпускної ціни на продукцію у різних постачальників за методом потенціалів шляхом зведення
виробничо–транспортної задачі до транспортної
Виробничо–транспортну задачу можна звести до класичної транспортної задачі. Для цього слід вилучити змінні , використовуючи балансові рівняння:
, (3.8)
Виконавши необхідні перетворення, отримаємо таку транспортну задачу:
(3.9)
Відмінність задачі (3.9) від класичної транспортної задачі полягає у тому, що коефіцієнти при змінних у цільовій функції задачі (3.9) відбивають не лише питомі витрати на перевезення продукції, а також і витрати, пов’язані із придбанням цієї продукції у відповідного виробника (постачальника).
Задачу (3.9) можна розв’язувати за методом потенціалів (звівши її, у разі необхідності, до закритої). Після цього оптимальні обсяги виробництва обчислюватимуться за даними про оптимальні обсяги перевезень за балансовими рівняннями (3.8).
Розглянемо конкретний числовий приклад. Припустимо, що задача характеризується наступними даними:
1). Інформація про виробників – постачальників продукції (
):
|
| ||||
|
| ||||
|
| 6,0 | 5,5 | 5,0 | 4,8 |
2). Інформація про споживачів (
):
|
| |||
|
|
3) Транспортні тарифи (
):
|
|
| ||
| 0,1 | 0,2 | 0,1 | |
| 0,3 | 0,4 | 0,2 | |
| 0,4 | 0,1 | 0,3 | |
| 0,2 | 0,1 | 0,3 |
Наведена задача є закритою (загальні виробничі потужності усіх виробників збігаються із сукупним попитом споживачів; вони дорівнюють 690 одиниць продукції).
Обчислимо питомі виробничо–транспортні витрати (за формулою: 
, , ):
|
|
| ||
| 6,1 | 6,2 | 6,1 | |
| 5,8 | 5,9 | 5,7 | |
| 5,4 | 5,1 | 5,3 | |
| 5,0 | 4,9 | 5,1 |
Тепер можна скористатися методом потенціалів.
1–й крок.
|
|
|  =690
| |||||||
| 6,1 | 6,0 | 6,2 | 6,1 | ||||||
| 5,7 | 5,8 | 5,6 | 5,9 | 5,7 | -0.4 | ||||
| 5,3 | 5,4 | 5,2 | > | 5,1 | 5,3 | -0.8 | |||
| * | |||||||||
| 5,0 | 4,9 | 5,0 | 5,1 | -1.1 | |||||
| =690
| 6.1 | 6.0 | 6.1 | 
| |||||
| |||||||||
План не є оптимальним, оскільки за маршрутом 
сума потенціалів (-0,8+6,0=5,2 – показана у верхньому лівому куті клітинки) перевищує тариф (5,1 – показаний у верхньому правому куті клітинки).
Корекцією поточного неоптимального опорного плану перевезень переходимо до другого кроку.
2–й крок.
|
|
| =690
| |||||
| 6,0 | 6,1 | 5,9 | 6,2 | 6,1 | |||
| 5,6 | 5,8 | 5,5 | 5,9 | 5,7 | -0.4 | ||
| 5,2 | 5,4 | 5,1 | 5,3 | -0.8 | |||
| 5,0 | 4,9 | 5,1 | 5,1 | -1.0 | |||
| =690
| 6.0 | 5.9 | 6.1 |
| |||
|
| |||||||
Ознака оптимальності виконується: за кожним із маршрутів сума потенціалів не перевищує відповідного тарифу. Фіксуємо знайдений план як оптимальний та обчислюємо загальні мінімально можливі виробничо–транспортні витрати:
=120*6,1+160*5,7+110*5,1+70*5,3+140*5,0+90*4,9=3717,0 (грош.од.).
Задачу за методом потенціалів розв’язано.
3.4. Розв’язування виробничо–транспортної задачі з використанням інструменту “Поиск решения” Excel
Розпочнемо роботу зі створення файлу “VTZ.xls” та звернемося до першого аркушу цієї книги “Лист 1”.
Підготовка робочого аркуша Excel. Виконаємо такі дії.
1. Об’єднаємо клітинки A1:E1 та внесемо туди назву задачі: “Виробничо–транспортна задача”.
2. В масив клітинок A3:D3, які об’єднаємо, внесемо назву першого інформаційного блоку: “1). Інформація про виробників–постачальників”, під якою в масиві клітинок A4:C8 створимо таблицю з даними про потужності та відпускну ціну одиниці продукції у кожного з постачальників:
| Номер | Потужність | Ціна за од. |
| 6,0 | ||
| 5,5 | ||
| 5,0 | ||
| 4,8 |
3. Об’єднаємо клітинки A10:D10 та зафіксуємо у них назву другого інформаційного блоку: “2). Інформація про споживачів”. Далі в клітинках A11:D12 наведемо дані про попит кожного із споживачів:
| Номер | |||
| Попит |
4. В масив клітинок A14:D20 занесемо інформаційний блок про транспортні тарифи:
| 3). Транспортні тарифи | |||
| Виробник | Споживач | ||
| 0,1 | 0,2 | 0,1 | |
| 0,3 | 0,4 | 0,2 | |
| 0,4 | 0,1 | 0,3 | |
| 0,2 | 0,1 | 0,3 |
5. В клітинках A22:E22 побудуємо інформаційний блок про загальні витрати на закупівлю продукції у виробників та її перевезення до постачальників. Для цього клітинки A22:D22 об’єднаємо та впишемо слова: “4). Загальні виробничо–транспортні витрати”, а клітинку E22 оберемо за цільову. Згодом в цю клітинку внесемо формулу для обчислення загальних виробничо–транспортних витрат.
6. Масив клітинок A24:B29 відведемо для п’ятого інформаційного блоку – про план виробництва (закупівлі) продукції у кожного з постачальників; масив клітинок A31:D33 – для шостого інформаційного блоку – про обсяги постачання продукції кожному із споживачів; нарешті, масив клітинок A35:D41 – для сьомого інформаційного блоку про план перевезень продукції. Ось як виглядатимуть зараз ці інформаційні блоки:
| 5). План виробництва | |
| Виробник | Обсяг |
| 6). Обсяги постачання | |||
| Споживач | |||
| Обсяг |
| 7). План перевезень | |||
| Виробник | Споживач | ||
7. Уведемо в цільову клітинку E22 формулу для обчислення загальних виробничо–транспортних витрат:
=СУММПРОИЗВ(B26:B29;C5:C8)+СУММПРОИЗВ(B17:D20;B38:D41)
8. Внесемо формули обчислення необхідних обсягів виробництва продукції, яка надсилатиметься усім споживачам:
у клітинку B26 – формулу: =СУММ(B38:D38)
у клітинку B27 – формулу: =СУММ(B39:D39)
у клітинку B28 – формулу: =СУММ(B40:D40)
у клітинку B29 – формулу: =СУММ(B41:D41)
/Формулу з клітинки B26 потрібно просто “протягнути” через клітинки B27, B28 та B29./
9. У клітинки B33:D33 введемо формули для обчислення обсягів продукції, що ввозитиметься кожному споживачу:
у клітинку B34: =СУММ(B38:B41)
у клітинку C34: =СУММ(C38: C41)
у клітинку D34: =СУММ(D38: D41)
/Можна “протягнути” формулу з клітинки B34 на клітинки C34 та D34./
Підготовку робочого аркушу закінчено.
Пошук розв’язку.
1. Оберемо команду “Поиск решения” в меню “Сервис”.
2. У діалоговому вікні “Поиск решения”, яке з’явиться на екрані, в полі “Установить целевую ячейку” вкажемо на адресу цільової клітинки: E22.
3. Перемикач вибору оптимізаційного спрямування цільової функції увімкнемо у положення “минимальному значению”.
4. У полі “Изменяя ячейки” вкажемо на адреси клітинок з основними незалежними змінними, які відповідають шуканим обсягам перевезень продукції за кожним з маршрутів: B38:D41.
5. У поле “Ограничения” введемо обмеження задачі. Для цього натиснемо кнопку “Добавить” та введемо обмеження щодо виробничих потужностей постачальників:
| $B$26:$B$29 | <= | $B$5:$B$8 |
та щодо попиту на продукцію з боку споживачів:
| $B$33:$D$33 | >= | $B$12:$D$12 |
6. Введемо параметри пошуку рішення: “Линейная модель” та “Неотрицательные переменные”.
7. Натиснемо на кнопку “Выполнить”.
8. У вікні “Результаты поиска решения”, яке через мить з’явиться на екрані, увімкнемо перемикач “Сохранить найденное решение” та натиснемо ОК.
9. Прочитаємо на робочому аркуші Excel знайдений розв’язок (рис. 3.1). Оптимальному плану закупівлі та перевезень продукції відповідають загальні витрати у сумі 3717 грошових одиниць.
| A | B | C | D | E | |
| Виробничо–транспортна задача | |||||
| 1). Інформація про виробників–постачальників | |||||
| Номер | Потужність | Ціна за од. | |||
| 6,0 | |||||
| 5,5 | |||||
| 5,0 | |||||
| 4,8 | |||||
| 2). Інформація про споживачів | |||||
| Номер | |||||
| Попит | |||||
| 4). Транспортні тарифи | |||||
| Виробник | Споживач | ||||
| 0,1 | 0,2 | 0,1 | |||
| 0,3 | 0,4 | 0,2 | |||
| 0,4 | 0,1 | 0,3 | |||
| 0,2 | 0,1 | 0,3 | |||
| 5). Загальні виробничо–транспортні витрати | |||||
| 6). План виробництва | |||||
| Виробник | Обсяг | ||||
| 7). Обсяги постачання | |||||
| Споживач | |||||
| Обсяг | |||||
| 8). План перевезень | |||||
| Виробник | Споживач | ||||
Рис. 3.1. Робочий лист з умовами та розв’язком задачі
про оптимізацію плану закупівлі та перевезень продукції до споживачів
3.5. Завдання для самостійного опрацювання
1. Проаналізуйте знайдений за методом потенціалів розв’язок задачі про оптимізацію плану закупівлі та перевезень продукції до споживачів (підрозділ 3.3) щодо існування альтернативних оптимальних планів та спробуйте описати всю множину оптимальних планів.
2. Порівняти розв’язки задачі, отримані за методом потенціалів (підрозділ 3.3) та на ПК (підрозділ 3.4).
3. Як змінитися розв’язок задачі про оптимізацію плану закупівлі та перевезень продукції до споживачів, якщо третій виробник збільшить відпускні ціни на продукцію на 30 %, а за маршрутами та 
буде введено заборону на перевезення продукції?
РОЗДІЛ 4. ОПТИМІЗАЦІЯ ПЛАНУ РОЗПОДІЛУ ЗАМОВЛЕНЬ
НА ПЕРЕВЕЗЕННЯ МІЖ ПЕРЕВІЗНИКАМИ
(ЗАДАЧА ПРО ПРИЗНАЧЕННЯ)
4.1. Постановка та особливості задачі про призначення; використання логічних змінних з метою відбиття її умов
4.2. Оптимізація плану розподілу замовлень на перевезення за критерієм мінімізації загальних витрат
4.3. Оптимізація плану розподілу замовлень на перевезення за критерієм мінімізації часу виконання всіх робіт
4.4. Завдання для самостійного опрацювання
4.1. Постановка та особливості задачі про призначення;
використання логічних змінних з метою відбиття її умов
Задача про призначення у контексті логістики полягає у визначенні якнайкращого плану розподілу замовлень на перевезення між різними виконавцями (перевізниками).
Особливість задачі полягає у тому, що коли кількість замовлень дорівнює , кількість виконавців – теж , причому кожному виконавцю слід доручити одне і тільки одне замовлення, загальна кількість альтернативних планів розподілу замовлень між виконавцями є дуже великою (
). Наприклад, вже при 
матимемо 10!=3628800 різних планів призначень, попарно порівняти які між собою без використання спеціальних засобів практично неможливо.
Отже, для вибору оптимального плану призначень є сенс скористатися спеціальними економіко–математичними методами моделювання та оптимізації.
Позначимо кількість замовлень на перевезення через , а кількість можливих перевізників через . Нехай – номер окремого замовлення (), а – номер окремого перевізника ().
Уведемо логічні змінні , які значеннями 1 або 0 відбиватимуть факт доручення або відмови від доручення -го замовлення -му перевізнику (; ):
Тоді кількість перевізників, яким буде доручено виконати -те замовлення, дорівнюватиме сумі:
(4.1)
а кількість замовлень, які доручатимуться окремому -му виконавцю, – сумі:
(4.2)
У випадку, коли кількість замовлень на перевезення збігається з кількістю виконавців (
), причому потрібно виконати всі замовлення за умов, що кожному перевізнику доручатиметься одне й тільки одне замовлення, довільний допустимий план 
розподілу замовлень між виконавцями має задовольняти обмеження:
(4.3)
(4.4)
(4.5)
Наведені формули означають:
(4.3) – кожне замовлення слід доручити одному і тільки одному перевізнику;
(4.4) – кожному перевізнику слід доручити одне і тільки одне замовлення;
(4.5) – кожна із логічних змінних, за її визначенням, може набирати лише одне із двох значень: або 1, або 0.
Припустимо, що кожний з виконавців виконує замовлення на перевезення за індивідуальними (власними) тарифами. Нехай 
– вартість виконання -го замовлення -м перевізником, причому матриця тарифів 
є відомою. Тоді можна обчислити загальні витрати , пов’язані із реалізацією плану 
розподілу замовлень між перевізниками:
(4.6)