Відмінності між версіями «Двохетапна транспортна задача.»
| Рядок 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> одиниць продукції, яку необхідно перевезти до <math>l</math> посередницьких фірм <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_ik</math> та від посередників до споживачів — <math>c_kj</math> . Потрібно визначити оптимальну схему перевезень продукції з мінімальни-ми сумарними витратами. Якщо обсяг продукції, що перевозить-ся від i-го постачальника до k-ої фірми, позначити через <math>x_ik</math> , а об-сяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через <math>x_kj</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_ik x_ik + \sum_{k=1}^l \sum_{j=1}^n c_kj x_kj </math> <br /> |
за умов: | за умов: | ||
<br /> | <br /> | ||
| − | <math>\sum_{k=1}^l | + | <math>\sum_{k=1}^l x_ik = 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 /> | ||
<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>x_ik >=0</math>, <math>x_kj >=0</math>, <math>i=1..m</math>; <math>i=j..n</math>; <math>k=1..l</math>. | + | <math>x_ik >=0</math>, <math>x_kj >=0</math>, <math>i=1..m</math>; <math>i=j..n</math>; <math>k=1..l</math>. <br /> |
| − | Зазначимо, що коли загальний обсяг вантажу | + | Зазначимо, що коли загальний обсяг вантажу <math>\sum_{i=1}^m a_i</math> дорівнює місткості всіх складів і баз <math>\sum_{k=1}^l d_k</math> , а також сумарній потребі всіх споживачів <math>\sum_{j=1}^n b_j</math> , тобто <math>\sum_{i=1}^m a_i = \sum_{k=1}^l d_k = \sum_{i=1}^m a_i</math>, то така двохетапна транспортна задача може бути розв’язана як дві одноетапні. В іншому разі окремі оптимальні плани двох задач не збігатимуться з оптимальним планом загальної задачі. |
| − | Метод розв’язування двохетапної транспортної задачі, | + | Метод розв’язування двохетапної транспортної задачі, розроблений Орденом-Маршем, полягає у врахуванні місткостей посередників двічі — як постачальників і як споживачів. |
| − | Умови задачі подаються у вигляді таблиці, в рядках якої | + | Умови задачі подаються у вигляді таблиці, в рядках якої записують дані про постачальників, а також про посередницькі фірми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять ну-льові величини затрат. Решту клітин таблиці блокують, тобто ва-ртості перевезень прирівнюють до деякого досить великого числа М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам дво-хетапної транспортної задачі. |
Поточна версія на 06:44, 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_ik та від посередників до споживачів — Неможливо розібрати вираз (невідома помилка): c_kj . Потрібно визначити оптимальну схему перевезень продукції з мінімальни-ми сумарними витратами. Якщо обсяг продукції, що перевозить-ся від i-го постачальника до k-ої фірми, позначити через Неможливо розібрати вираз (невідома помилка): x_ik , а об-сяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через Неможливо розібрати вираз (невідома помилка): x_kj , то математична модель задачі матиме вигляд:
Неможливо розібрати вираз (невідома помилка): min Z = \sum_{i=1}^m \sum_{k=1}^l c_ik x_ik + \sum_{k=1}^l \sum_{j=1}^n c_kj x_kj
за умов:
Неможливо розібрати вираз (невідома помилка): \sum_{k=1}^l x_ik = 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
.
Зазначимо, що коли загальний обсяг вантажу Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m a_i
дорівнює місткості всіх складів і баз Неможливо розібрати вираз (невідома помилка): \sum_{k=1}^l d_k
, а також сумарній потребі всіх споживачів Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n b_j
, тобто Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m a_i = \sum_{k=1}^l d_k = \sum_{i=1}^m a_i
, то така двохетапна транспортна задача може бути розв’язана як дві одноетапні. В іншому разі окремі оптимальні плани двох задач не збігатимуться з оптимальним планом загальної задачі.
Метод розв’язування двохетапної транспортної задачі, розроблений Орденом-Маршем, полягає у врахуванні місткостей посередників двічі — як постачальників і як споживачів. Умови задачі подаються у вигляді таблиці, в рядках якої записують дані про постачальників, а також про посередницькі фірми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять ну-льові величини затрат. Решту клітин таблиці блокують, тобто ва-ртості перевезень прирівнюють до деякого досить великого числа М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам дво-хетапної транспортної задачі.
