Постановка транспортної задачі та її види

ТРАНСПОРТНА ЗАДАЧА

План

1. Постановка транспортної задачі та її види.

2. Методи побудови початкового опорного плану транспортної задачі.

3. Метод потенціалів.

4. Перехід від одного опорного плану до іншого.

5. Навчальні завдання.

 

Література:

1. Бугір М.К. Математика для економістів. Лінійна алгебра, лінійні моделі. – К.: ВЦ. „Академія”, 1998. – С. 214-234.

2. Бугір М.К. Математика для економістів: Посібник Київ.: ВЦ „Академія”, 2003 р. – С. 436-458.

3. Наконечний С.І., Савіна С.С. Математичне програмування. Навчальний посібник – К.:КНЕУ, 2003 р. – С. 184-252.

4. Гетманцев В.Д. Лінійна алгебра і лінійне програмування: навч. Посібник. – К.: Либідь, 2001. – С. 202-227.

 

Ключові слова: транспортна задача (ТЗ), закрита (збалансована) ТЗ, відкрита (незбалансована) ТЗ, матриця перевезень, методи пошуку початкового опорного плану ТЗ: північно-західного кута, найменшої вартості (мінімального елемента), подвійної переваги; вироджений та невироджений опорний план, метод потенціалів; квадрат у матриці перевезень (правильний, неправильний, нейтральний); цикл, сусідні вершини циклу, означений цикл, цикл перерахунку, зсув по циклу перерахунку.

Постановка транспортної задачі та її види

Транспортна задача — це специфічна задача лінійного програмування, застосовувана для визначення найекономічнішого плану перевезення однорідної продукції від постачальників до споживачів.

Математична модель транспортної задачі має такий вигляд:

(1)

за обмежень

; (2)

; (3)

, (4)

де х_ij — кількість продукції, що перевозиться від і -го постачальника до j -го споживача; с_ij — вартість перевезення одиниці продукції від і -го постачальника до j -го споживача; а_i — запаси продукції і -го постачальника; b_j — попит на продукцію j -го спо­живача.

Якщо в транспортній задачі загальна кількість продукції постачальників дорівнює загальному попиту всіх споживачів, тобто

, (5)

то таку транспорту задачу називають збалансованою, або закритою. Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою.

Планом транспортної задачі називають будь-який невід’єм­ний розв’язок системи обмежень (2)—(4) транспортної задачі, який позначають матрицею .

Оптимальним планом транспортної задачі називають матрицю , яка задовольняє умови задачі і для якої цільова функція (1) набуває найменшого значення.

Теорема (умова існування розв’язку транспортної задачі). Необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість, тобто .

 

2. Методи побудови початкового опорного плану транспортної задачі

Для побудови початкового опорного плану транспортної задачі існує кілька методів: північно-західного кута, мінімальної вартості, подвійної переваги, апроксимації Фогеля. Побудову опорного плану зручно подавати у вигляді таблиці, в якій постачальники продукції є рядками, а споживачі — стовпчиками.

Побудову першого плану за методом північно-західного кута починають із заповнення лівої верхньої клітинки таблиці (х ₁₁), в яку записують менше з двох чисел а ₁ та b ₁. Далі переходять до наступної клітинки в рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнювати таблицю у правій нижній клітинці.

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

Метод подвійної переваги. Перед початком заповнення таблиці необхідно позначити клітинки, які мають найменшу вартість у рядках і стовпчиках. Таблицю починають заповнювати з клітинок, позначених двічі (як мінімальні і в рядку, і в стовпчику). Далі заповнюють клітинки, позначені один раз (як мінімальні або в рядку, або в стовпчику), а вже потім — за методом мінімальної вартості.

 

Метод потенціалів

Транспортна задача є задачею лінійного програмування, яку можна розв’язати симплекс-методом. Але специфічна структура транспортної задачі дає змогу використовувати для її розв’я­зування ефективніший метод, який повторює, по суті, кроки симплекс-алгоритму. Таким є метод потенціалів.

Алгоритм методу потенціалів складається з наступних кроків.

1. Визначення типу транспортної задачі (відкрита чи закрита).

2. Побудова першого опорного плану транспортної задачі.

3. Перевірка плану транспортної задачі на оптимальність.

4. Якщо умова оптимальності виконується, то маємо оптимальний розв’язок

транспортної задачі. Якщо ж умова оптимальності не виконується, необхідно

перейти до наступного опорного плану.

5. Новий план знову перевіряють на оптимальність, тобто повторюють дії п. 3, і

т. д.

Розглянемо детально кожний крок цього алгоритму.

1. Якщо під час перевірки збалансованості (5) виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. Це виконується введенням фіктивного умовного постачальника у разі перевищення загального попиту над за­­пасами із запасом . Якщо ж загаль­ні запаси постачальників перевищують попит споживачів , то до закритого типу задача зводиться введенням фіктивного умовного споживача з потребою .

Вартість перевезення одиниці продукції для фіктивного постачальника або фіктивного споживача вважається такою, що дорівнює нулю.

2. Після побудови першого опорного плану одним із розглянутих методів у таблиці має бути заповнено (m + n – 1) клітинок, де m — кількість постачальників; n — кількість споживачів у задачі, у тому числі фіктивних. Такий план називають невиродженим. Якщо кількість заповнених клітинок перевищує (n + m – 1), то початковий план побудовано неправильно і він є неопорним. Ознакою опорності плану транспортної задачі є його ациклічність, тобто неможливість побудови циклу. Циклом у транспортній задачі називають замкнену ламану лінію, вершини якої розміщуються в заповнених клітинках таблиці, а сторони проходять уздовж рядків і стовпчиків таблиці.

Якщо заповнених клітинок у таблиці менш як (m + n – 1), то опорний план називають виродженим. У такому разі необхідно заповнити відповідну кількість порожніх клітинок, записуючи в них «нульове перевезення», але так, щоб при цьому не порушилася ациклічність плану.

3. Опорний план перевіряють на оптимальність за допомогою потенціалів u_i та v_j відповідно постачальників та споживачів.

Теорема (умова оптимальності опорного плану транспортної задачі). Якщо для деякого опорного плану Х ^* = (x_ij ^*) існують числа u_i та v_j, для яких виконується умова

u_i + v_j = c_ij, x_ij > 0,

u_i + v_j £ c_ij, x_ij = 0

для всіх та , то він є оптимальним планом транспортної задачі.

Потенціали опорного плану визначаються із системи рівнянь
u_i + v_j = c_ij, які записують для всіх заповнених клітинок транспорт­ної таблиці.

4. За допомогою розрахованих потенціалів перевіряють умову оптимальності u_i + v_j £ c_ij для порожніх клітинок таблиці. Якщо хоча б для однієї клітинки ця умова не виконується, тобто u_i + v_j > c_ij, то поточний план є неоптимальним і від нього необхідно перейти до нового опорного плану.

 

4. Перехід від одного опорного плану до іншого

Перехід від одного опорного плану до іншого виконують заповненням клітинки, для якої порушено умову оптимальності. Якщо таких клітинок кілька, то для заповнення вибирають таку, що має найбільше порушення, тобто . Для вибраної порожньої клітинки будують цикл перерахування та виконують перерозподіл продукції в межах цього циклу за такими правилами:

1) кожній вершині циклу приписують певний знак, причому вільній клітинці — знак «+», а всім іншим по черзі — знаки «–» та «+»;

2) у порожню клітинку переносять менше з чисел x_ij, що стоять у клітинках зі знаком «–». Одночасно це число додають до відповідних чисел, які розміщуються в клітинках зі знаком «+».

Отже, клітинка, що була вільною, стає заповненою, а відповід­на клітинка з мінімальним числом x_ij вважається порожньою. У результаті такого перерозподілу продукції дістанемо новий опор­ний план транспортної задачі.

5. Новий опорний план перевіряють на оптимальність згідно з п. 3 розглянутого алгоритму.

Розглянемо застосування методу потенціалів для розв’язуван­ня транспортних задач, наведених далі.

Навчальні завдання

Задача 1. Компанія контролює три фабрики А ₁, А ₂, А ₃, здатні виготовляти 150, 60 та 80 тис. од. продукції щотижня. Компанія уклала договір із чотирма замовниками В ₁, В ₂, В ₃, В ₄, яким потрібно щотижня відповідно 110, 40, 60 та 80 тис. од. продукції. Вартість виробництва та транспортування 1000 од. продукції замовникам з кожної фабрики наведено в таблиці.

Фабрика	Вартість виробництва і транспортування 1000 од. продукції за замовниками
В 1	В 2	В 3	В 4
А 1
А 2
А 3

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

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

Економічний зміст записаних обмежень полягає ось у чому: уся вироблена на фабриках продукція має вивозитися до замовників повністю.

Аналогічні обмеження можна записати відносно замовників: продукція, що надходить до споживача, має повністю задовольняти його попит. Математично це записується так:

Загальні витрати, пов’язані з виробництвом і транспортуванням продукції, складаються як добуток обсягу перевезеної продукції та питомої вартості перевезень за відповідним маршрутом і за умовою задачі мають бути мінімальними. Тому

Z = 4 × x ₁₁ + 4 × x ₁₂ + 2 × x ₁₃ + 5 × x ₁₄ + 5 × x ₂₁ + 3 × x ₂₂ + x ₂₃ +
+ 2 × x ₂₄ + 2 × x ₃₁ + x ₃₂ +4 × x ₃₃ +2 × x ₃₄ ® min.

У цілому математичну модель поставленої задачі можна записати так:

Z = 4 x ₁₁ + 4 x ₁₂ + 2 x ₁₃ + 5 x ₁₄ + 5 x ₂₁ + 3 x ₂₂ + x ₂₃ + 2 x ₂₄ + 2 x ₃₁ + x ₃₂ +4 x ₃₃ +2 x ₃₄ ® min

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

Aj	Bj	ui
B 1= 110	B 2= 40	B 3= 60	B 4= 80
A 1= 150			2 +	40–	u 1= 5
A 2= 60			–60	0+	u 2= 2
A 3= 80					u 3= 2
vj	v 1= –1	v 2= –1	v 3= –1	v 4= 0

 

Тому Z = 4 × 110 + 5 × 40 + 1 × 60 + 1 × 40 + 2 × 40 = 820 ум. од.

Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п’яти, а (m + n – 1) = 3 + 4 – 1 = 6. Для подальшого розв’язування задачі необхідно в одну з порожніх клітинок записати «нульове перевезення» так, щоб не порушити опорності плану, тобто можна зай­няти будь-яку вільну клітинку, яка не утворює замкненого циклу. Наприклад, заповнимо клітинку А ₂ В ₄. Тепер перший план транспортної задачі є невиродженим, і його можна перевірити на оптимальність за допомогою методу потенціалів.

На основі першої умови оптимальності u_i + v_j = c_ij складемо систему рівнянь для визначення потенціалів плану:

Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, якщо, наприклад, v ₄ = 0. Тоді всі інші потенціали однозначно визначаються: u ₁ = 5, u ₂ = 2, u ₃ = 2, v ₁ = –1, v ₂ = –1, v ₃ = –1.

Далі згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності u_i + v_j ≤ c_ij (для порожніх клітинок таблиці):

А ₁ B ₂: u ₁ + v ₂ = 5 + (–1) = 4 = 4;

А ₁ B ₃: u ₁ + v ₃ = 5 + (–1) = 4 > 2;

А ₂ B ₁: u ₂ + v ₁ = 2 + (–1) = 1 < 5;

А ₂ B ₂: u ₂ + v ₂ = 2 + (–1) = 1 < 3;

А ₃ B ₁: u ₃ + v ₁ = 2 + (–1) = 1 < 2;

А ₃ B ₃: u ₃ + v ₃ = 2 + (–1) = 1 < 4.

Умова оптимальності не виконується для клітинки А ₁ B ₃. Порушення D₁₃ = (u ₁ + v ₃) – c ₁₃ = 4 – 2 = 2 записуємо в лівому нижньому кутку відповідної клітинки.

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

Потрібно заповнити клітинку А ₁ B ₃, в якій є єдине порушення умови оптимальності. Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А ₁ B ₃, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у вільну клітинку А ₁ B ₃ переносимо менше з чисел х_ij, які розміщуються в клітинках зі знаком «–». Одночасно це саме число х_ij додаємо до відповідних чисел, що розміщуються в клітинках зі знаком «+», та віднімаємо від чисел, що розміщуються в клітинках, позначених знаком «–».

У даному випадку , тобто . Виконавши перерозподіл продукції згідно із записаними правилами, дістанемо нові значення. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписують у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості, тобто дорівнювати (n + m – 1).

Отже, другий опорний план транспортної задачі матиме такий вигляд:

Aj	Bj	ui
B 1= 110	B 2= 40	B 3= 60	B 4= 80
A 1= 150	–110		40+		u 1= 0
A 2= 60			–20	40+	u 2= –1
A 3= 80	1 +			40–	u 3= –1
vj	v 1= 4	v 2= –2	v 3= 2	v 4= 3

Тому Z ₂ = 4 × 110 + 2 × 40 + 1 × 20 + 2 × 40 + 1 × 40 + 2 × 40 =
740 ум. од.

Новий план знову перевіряємо на оптимальність, тобто повторюємо описані раніше дії. Другий план транспортної задачі також неоптимальний (порушення для клітинки А ₃ B ₁). За допомогою побудованого циклу виконаємо перехід до третього опор­ного плану транспортної задачі і дістанемо таку таблицю:

Aj	Bj	ui
B 1= 110	B 2= 40	B 3= 60	B 4= 80
A 1= 150					u 1= 2
A 2= 60					u 2= 0
A 3= 80					u 3= 0
vj	v 1= 2	v 2= 1	v 3= 0	v 4= 2

Тому Z ₃ = 4 × 90 + 2 × 60 + 2 × 60 + 2 × 20 + 1 × 40 + 2 × 20 = 720 ум. од.

Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний. Тому

.

За оптимальним планом перевезень перший замовник отримує 90 тис. од. продукції з першої фабрики та 20 тис. од. — з третьої. Другий споживач задовольняє свій попит за рахунок виробництва та перевезення 40 тис. од. продукції з третьої фабрики і т. д. При цьому загальна вартість виробництва та перевезення всієї продукції є найменшою і становить 720 ум. од.

Задача 2. Районне агропромислове об’єднання складається з трьох господарств А ₁, А ₂, А ₃, що спеціалізуються на вирощуванні ранніх овочів. Кожне господарство щотижня збирає відповідно 50, 30 та 20 т овочів, які необхідно відправляти в чотири магазини B ₁, B ₂, B ₃, B ₄. Магазини бажають отримувати ранні овочі в кількості відповідно 30, 30, 10 та 20 т. Вартість перевезення 1 т овочів від господарства до магазинів наведено в таблиці.

Господарство	Вартість перевезення 1 т овочів у магазини
В 1	В 2	В 3	В 4
А 1
А 2
А 3

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

Побудова математичної моделі. Нехай х_ij — кількість тон овочів, які перевозять з і -го господарства j -го магазину (; ). Тоді економіко-математична модель поставленої задачі має такий вигляд:

Z = 2 x ₁₁ + 3 x ₁₂ + 4 x ₁₃ + 2 x ₁₄ + 5 x ₂₁ + 7 x ₂₂ + x ₂₃ +
+ 4 x ₂₄ + 9 x ₃₁ + 4 x ₃₂ +3 x ₃₃ +2 x ₃₄ ® min,

за обмежень

Знак «≤» у перших трьох обмеженнях задачі пояснюється тим, що за умовою транспортна задача є відкритою:

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

Розв’язування. Щоб визначити оптимальний план поставленої задачі, її необхідно збалансувати, тобто звести до закритого типу. Це виконується шляхом уведення додаткового, умовного споживача B ₅ із попитом B ₅ = 100 – 90 = 10 т. Вартість перевезення одиниці продукції до умовного споживача дорівнює нулю.

Перший опорний план транспортної задачі побудуємо методом подвійної переваги.

 

Aj	Bj	ui
B 1 = 30	B 2= 30	B 3= 10	B 4= 20	B 5= 10
A 1= 50						u 1= –4
A 2= 30		–10		0+		u 2= 0
A 3= 20		1 +		20–		u 3= –2
vj	v 1= 6	v 2= 7	v 3= 1	v 4= 0	v 5= 0

 

Перший опорний план є виродженим, і тому в клітинку, наприклад A ₂ B ₄, поставимо нуль і вважатимемо її заповненою.

Перевірка плану за допомогою потенціалів показує, що він є неоптимальним. Перехід до другого опорного плану виконується шляхом заповнення клітинки A ₃ B ₂ згідно із побудованим циклом. Зазначену клітинку включено до циклу тому, що в разі кількох однакових найбільших порушень (D₂₁ = D₃₂ = 1) заповнюють таку клітинку таблиці, яка має меншу вартість перевезення одиниці продукції (с ₃₂ < c ₂₁).

Другий план транспортної задачі наведемо у вигляді таблиці:

Aj	Bj	ui
B 1= 30	B 2= 30	B 3= 10	B 4= 20	B 5= 10
A 1= 50						u 1= –3
A 2= 30						u 2= 0
A 3= 20						u 3= –2
vj	v 1= 5	v 2= 6	v 3= 1	v 4= 4	v 5= 0

Умова оптимальності для цього опорного плану виконується, і тому можна записати:

;

Z _min = 2 × 30 + 3 × 20 + 1 × 10 + 4 × 10 + 4 × 10 + 2 × 10 = 320 ум. од.

Згідно з оптимальним планом потреба магазинів у ранніх овочах задовольняється завдяки повному вивезенню продукції з першого та третього господарств і лише частково — з другого (залишок дорівнює 10 т). У цьому разі загальна вартість усіх перевезень буде найменшою і становитиме 230 ум. од.

Але виявляється, що розглянута транспортна задача має ще один альтернативний оптимальний план. Ознакою цього є виконання умови оптимальності для порожньої клітинки: u_i + v_j = c_ij. В останній таблиці це справджується для порожньої клітинки A ₂ B ₁: u ₁ + v ₁ = 0 + 5 = с ₂₁ = 5.

Щоб отримати альтернативний оптимальний план, достатньо заповнити зазначену клітинку таблиці, виконавши перерозподіл продукції за таким циклом:

Наведемо транспортну таблицю, що відповідає другому оптимальному плану задачі.

 

Aj	Bj	ui
B 1 = 30	B 2 = 30	B 3 = 10	B 4 = 20	B 5 = 10
А 1 = 50						u 1 = –3
A 2 = 30						u 2 = 0
A 3 = 20						u 3 = –2
vj	v 1 = 5	v 2 = 6	v 3 = 1	v 4 = 4	v 5 = 0

 

Тому

;

Z _min = 2 × 20 + 3 × 30 + 5 × 10 + 1 × 10 + 2 × 20 = 230 ум. од.

Другий оптимальний план задачі формулюється так. Перевезти з першого господарства 20 т овочів до першого магазину та 30 т — до другого; з другого господарства — 10 т до першого магазину та 10 т овочів до третього, залишаючи невивезеними 10 т, а також з третього господарства до четвертого магазину — 20 т овочів. У цьому разі загальні транспортні витрати становитимуть 230 ум. од. і також будуть найменшими.

 

Контрольні запитання:

1. Опишіть економічну та математичну постановку класичної транспортної задачі.

2. Чим відрізняється транспортна задача від загальної задачі лінійного програмування?

3. Сформулюйте критерій оптимальності за методом потенціалів.

4. Чим відрізняється відкрита ТЗ від закритої?

5. Які методи побудови початкового опорного плану ТЗ Вам відомі? Яка їх суть?

6. Як обчислюють потенціали?

7. Які Ви знаєте методи переходу від одного опорного плану ТЗ до іншого?

8. У чому суть методу квадратів?

9. Як будують цикл у матриці перевезень та здійснюють його перерахунок?

 

Питання, що виносяться на самостійне опрацювання [література]:

1. Метод осеред­нених коефіцієнтів побудови початкового опорного плану ТЗ. [1,2]

2. Методи розв’язування розподільчих задач. [1-4]

3. Угорський метод розв’язування ТЗ. [3]

4. Двохетапна ТЗ. [3]

5. Транспортна задача за критерієм часу. [3]

6. Розв’язування ТЗ на мережі. [3]