Відмінності між версіями «Двохетапна транспортна задача.»
| Рядок 1: | Рядок 1: | ||
На практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі. | На практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі. | ||
| − | Нехай в m пунктах постачання <math>A_1, A_2, …, A_m</math> є відповідно <math>a_1, a_2, ... a_m</math> одиниць продукції, яку необхідно перевезти до l посередницьких фірм <math>D_1, D_2, …, D_l</math>, місткості сховищ яких становлять <math>D_1, D_2, …, D_l</math> , а потім доставити її споживачам <math>B_1, B_2, …, B_m</math> , потреби яких становлять <math>b_1, b_2, …, b_n</math> . Відомі також витрати на перевезення одиниці продукції від кожного постачальника до посередницьких фірм — <math> | + | Нехай в m пунктах постачання <math>A_1, A_2, …, A_m</math> є відповідно <math>a_1, a_2, ... a_m</math> одиниць продукції, яку необхідно перевезти до l посередницьких фірм <math>D_1, D_2, …, D_l</math>, місткості сховищ яких становлять <math>D_1, D_2, …, D_l</math> , а потім доставити її споживачам <math>B_1, B_2, …, B_m</math> , потреби яких становлять <math>b_1, b_2, …, b_n</math> . Відомі також витрати на перевезення одиниці продукції від кожного постачальника до посередницьких фірм — <math>c_i_k</math> та від посередників до споживачів — <math>c_k_j</math> . Потрібно визначити оптимальну схему перевезень продукції з мінімальни-ми сумарними витратами. Якщо обсяг продукції, що перевозить-ся від i-го постачальника до k-ої фірми, позначити через <math>x_ik</math> , а об-сяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через <math>x_k_j</math> , то математична модель задачі матиме вигляд: <br /> |
| − | <math>min Z = \sum_{i=1}^m \sum_{k=1}^l | + | <math>min Z = \sum_{i=1}^m \sum_{k=1}^l c_i_k x_i_k + \sum_{k=1}^l \sum_{j=1}^n c_k_j x_k_j </math> <br /> |
за умов: | за умов: | ||
<br /> | <br /> | ||
| − | <math>\sum_{k=1}^l | + | <math>\sum_{k=1}^l x_i_k = a </math> ; <br /> |
<math>\sum_{j=1}^n c_jx_j \to \max </math> ; <br /> | <math>\sum_{j=1}^n c_jx_j \to \max </math> ; <br /> | ||
<math>\sum_{j=1}^n c_jx_j \to \max </math> ; <br /> | <math>\sum_{j=1}^n c_jx_j \to \max </math> ; <br /> | ||
Версія за 06:35, 14 травня 2012
На практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі. Нехай в m пунктах постачання Неможливо розібрати вираз (невідома помилка): A_1, A_2, …, A_m
є відповідно Неможливо розібрати вираз (невідома помилка): a_1, a_2, ... a_m одиниць продукції, яку необхідно перевезти до l посередницьких фірм Неможливо розібрати вираз (невідома помилка): D_1, D_2, …, D_l
, місткості сховищ яких становлять Неможливо розібрати вираз (невідома помилка): D_1, D_2, …, D_l
, а потім доставити її споживачам Неможливо розібрати вираз (невідома помилка): B_1, B_2, …, B_m , потреби яких становлять Неможливо розібрати вираз (невідома помилка): b_1, b_2, …, b_n . Відомі також витрати на перевезення одиниці продукції від кожного постачальника до посередницьких фірм — Неможливо розібрати вираз (невідома помилка): c_i_k та від посередників до споживачів — Неможливо розібрати вираз (невідома помилка): c_k_j . Потрібно визначити оптимальну схему перевезень продукції з мінімальни-ми сумарними витратами. Якщо обсяг продукції, що перевозить-ся від i-го постачальника до k-ої фірми, позначити через Неможливо розібрати вираз (невідома помилка): x_ik , а об-сяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через Неможливо розібрати вираз (невідома помилка): x_k_j , то математична модель задачі матиме вигляд:
Неможливо розібрати вираз (невідома помилка): min Z = \sum_{i=1}^m \sum_{k=1}^l c_i_k x_i_k + \sum_{k=1}^l \sum_{j=1}^n c_k_j x_k_j
за умов:
Неможливо розібрати вираз (невідома помилка): \sum_{k=1}^l x_i_k = a
;
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
;
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
;
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
;.
Неможливо розібрати вираз (невідома помилка): x_ik >=0 , Неможливо розібрати вираз (невідома помилка): x_kj >=0 , Неможливо розібрати вираз (невідома помилка): i=1..m
- Неможливо розібрати вираз (невідома помилка): i=j..n
- Неможливо розібрати вираз (невідома помилка): k=1..l
. Зазначимо, що коли загальний обсяг вантажу дорівнює місткості всіх складів і баз , а також сумарній потребі всіх споживачів , тобто = = , то така двохетапна транспортна задача може бути розв’язана як дві одноетапні. В іншому разі окремі оптимальні плани двох задач не збігати-муться з оптимальним планом загальної задачі.
Метод розв’язування двохетапної транспортної задачі, ро-зроб¬лений Орденом-Маршем, полягає у врахуванні місткос-тей посередників двічі — як постачальників і як споживачів. Умови задачі подаються у вигляді таблиці, в рядках якої запи-сують дані про постачальників, а також про посередницькі фір-ми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять ну-льові величини затрат. Решту клітин таблиці блокують, тобто ва-ртості перевезень прирівнюють до деякого досить великого чис-ла М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам дво-хетапної транспортної задачі.
