Теоретичні відомості

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

1. Якщо з деякого пункту перевезення не можуть бути здійснені в певні пункти призначення.

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

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

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

3. Необхідно знайти такий розв’язок при якому з пункту А_i в пункт B_j повинно бути перевезено не менш заданої кількості вантажу .

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

4. Потрібно знайти такий розв’язок при якому з пункту А_i в пункт B_j повинно бути перевезено не більше заданої кількості вантажу

.

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

Отримати розв’язок Т-задачі з обмеженнями на пропускні спроможності можна декількома способами.

Спосіб 1. Для кожного такого обмеження передбачається додатковий стовпець, так як на малюнку 1:

		Сij		M
Потребности

Рис. 1. Перетворення умови Т-задачі

з обмеженнями на пропускні спроможності

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

Спосіб 2. Будують опорний план по методу мінімального елемента, враховуючи накладені обмеження на пропускні спроможності. Якщо внаслідок такого розподілу залишився залишок d, то вводять додатковий пункт споживання і відправлення з потребами і запасами рівними d. В кутовій клітці тариф вважають рівним нулю, у всіх інших клітках рівний М. Полученную задачу вирішують методом потенціалів. При цьому умова оптимальності виглядає таким чином:

Приклад. Знайти розв’язок транспортної задачі початкові дані якої приведені в таблиці 14 при додаткових умовах: з А₁ в В₂ повинно бути перевезено не менше за 50 од. вантажу, з А₃ в В₅ - не менше за 60 од. вантажу, а з А₂ в В₄ - не більше за 40 од. вантажу. З А₁ в В₅ перевезення не можуть бути здійснені.

Таблиця 14

Пункти відправлення	Пункти призначення					Запаси
	В1	В2	В3	В4	В5
А1	5	3	2	4	8	160
А2	7	6	5	3	1	90
А3	8	9	4	5	2	140
Потреби	90	60	80	70	90

Розв’язок. Оскільки з пункту А₁ в пункт В₅ перевезення не можуть бути здійснені, то в клітці А₁В₅ тариф перевезення будемо вважати рівним деякому скіль завгодно великому числу М.

Так як з А₁ і А₃ відповідно в В₂ і В₅ необхідно завезти не менше за 50 і 60 од. вантажу, то запаси цих пунктів відправлення і потреби пунктів призначення вважаємо меншими відповідно на 50 і 60 од.

Крім того, оскільки з А₂ в В₄ необхідно завезти не більше за 40 од. вантажу, то розглянемо додатковий пункт призначення з потребами, що дорівнюють 70-40 = 30 од., а потреби пункту В₄ вважаємо рівними 40 од. У стовпці записуємо тарифи, вміщені в клітках стовпця В₄, за винятком клітки А₂ . У цій клітці тариф вважаємо рівним деякому скіль завгодно великому числу М. В результаті отримуємо транспортну задачу, початкові дані якої записані в таблиці 15

Таблиця 15

Пункти відправлення	Пункти призначення						Запаси
	В1	В2	В3	В4	В5
А1	5	3	2	4	М	4	110
А2	7	6	5	3	1	М	90
А3	8	9	4	5	2	5	80
Потреби	40	60	80	40	30	30

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

При такому плані перевезень загальна вартість перевезень

грош. од.

Контрольне завдання: Вирішити транспортну задачу, враховуючи всі додаткові умови.

На складах зберігається мука, яку необхідно завезти до хлібопекарен. Номери складів і номера хлебопекарен вибираються відповідно до варіантів таблиці 16 . Тарифи перевезення муки [крб./т], щомісячні запаси муки [т/міс.] на складах і потребі хлебопекарен в муці [т/міс.] вказані в таблиці 17 .

При цьому необхідно враховувати, що через ремонтні роботи тимчасово немає можливості перевозити муку з деяких складів до деяких хлібопекарен. У таблиці 16 це показане в графі "Заборона перевезення" в форматі № складу х № хлібопекарні. Наприклад, «2x3» означає, що не можна перевозити муку зі складу №2 в хлібопекарню №3.

Крім того, необхідно врахувати, що деякі хлібопекарні мають договори на гарантоване постачання муки з певних складів. У таблиці 16 це показане в графі "Гарантоване постачання" в форматі № складу х № хлебопекарни = обсяг постачання. Наприклад, «1x4=40» означає, що між складом №1 і магазином №4 укладений договір на обов'язкове постачання 40 т муки.

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

Примітка. Враховуючи умову, що мука зберігається і транспортується в мішках вагою по 50 кг необхідно перетворити початкові дані, перевівши значення [т/міс.] в значення [меш./міс.]. При цьому необхідно врахувати, що кількість мішків повинна бути цілою.

Варіанти завдань:

Таблиця 16

Номери складів, хлібопекарен, заборонені і гарантовані постачання

№ Варианта	№ Складів	№ Хлібопекарен	Заборони перевезень	Гарантовані постачання, т/міс.
1	1, 2, 3	1, 2, 3, 4	2x2, 3x4	3x3=50
2	2, 3, 4, 5	1, 2, 5	2x2, 3x5	3x2=40
3	1, 2, 4	1, 2, 3, 5	1x5, 2x3	4x3=45
4	1, 2, 3, 4	3, 4, 5	3x3, 4x5	3x5=40
5	1, 2, 5	2, 3, 4, 5	1x4, 5x3	1x5=60
6	1, 2, 3, 5	2, 3, 5	5x5, 2x2	3x5=30
7	2, 3, 4	2, 3, 4, 5	3x3, 2x5	4x3=45

Таблиця 17

Запаси, потреби і тарифи перевезень

Склади	Хлібопекарні
	1	2	3	4	5	Запас, т/міс.
1	400	600	800	200	200	80
2	300	100	500	600	500	70
3	500	200	100	600	300	60
4	300	700	200	400	900	55
5	200	500	800	200	400	65
Попит, т/міс.	77,86	56,78	58,88	62,44	73,92

Питання для самоконтроля:

1. Які ускладнення можуть бути присутніми в постановці транспортної задачі?

2. Які прийоми використовуються для розв’язання транспортних задач з додатковими обмеженнями типу ?

3. Які прийоми використовуються для розв’язання транспортних задач з додатковими обмеженнями типу ?

4. Чи завжди ТЗ з обмеженнями на пропускні спроможності має розв’язок? Поясніть чому?