Приклади розв’язування навчальних завдань

Приклад 5.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 додаємо до відповідних чисел, що розміщуються в клітинках зі знаком «+», та віднімаємо від чисел, що розміщуються в клітинках, позначених знаком «–».

У даному випадку , тобто . Виконавши перерозподіл продукції згідно із записаними правилами, дістанемо такі нові значення: клітинка А ₁ B ₃ — 40 од. продукції, А ₂ B ₃ – (60 – 40) = 20 од., А ₂ B ₄ – (0 + 40) = 40 од. Клітинка А ₁ B ₄, звільняється і в новій таблиці буде порожньою. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписують у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості, тобто дорівнювати (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 ум. од.

Приклад 5.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 ум. од. і також будуть найменшими.

 

 

Приклад 5.3.

Три нафтопереробних заводи А ₁, А ₂, А ₃, із максимальною щоденною продуктивністю відповідно 30, 20, 15 тис. т бензину забезпечують чотири бензосховища B ₁, B ₂, B ₃, B ₄, потреба яких становить відповідно 10, 20, 25 та 20 тис. т. бензину. Бензин транспортується до бензосховищ за допомогою трубопроводів. Вартість перекачування 1000 т бензину від заводів до сховищ (в умовних одиницях) наведено в таблиці.

Завод	Вартість, ум. од., перекачування 1000 т бензину до сховищ
	В 1	В 2	В 3	В 4
А 1
А 2
А 3

 

Cформулювати та розв’язати відповідну транспорту задачу з неодмінним виконанням таких умов:

1) повністю задовольнити попит бензосховища B ₄;

2) недопостачання бензину до сховища B ₂ штрафується 5 ум. од. вартості за кожні 1000 т бензину;

3) у зв’язку з виконанням ремонтних робіт на трубопроводі постачання бензину із заводу А ₁ до сховища B ₁ тимчасово неможливе.

Розв’язування. Визначимо, до якого типу належить транспортна задача:

, .

За умовою транспортна задача є відкритою, незбалансованою. Зведення її до закритого типу потребує введення додаткового фіктивного постачальника А ₄ з продуктивністю а ₄ = 75 – 65 = 10 (тисяч тон). Кількість бензину, що «відправляється» фіктивним заводом до бензосховищ, в оптимальному плані означатиме обсяг незадоволеного попиту в цьому пункті призначення. Тому для виконання першої додаткової вимоги задачі необхідно блокувати клітинку фіктивного постачальника А ₄ та споживача B ₄, записавши в ній досить високу вартість М. Тоді в оптимальному плані транспортної задачі ця клітинка обов’язково буде незаповненою.

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

Оскільки неможливо транспортувати бензин від заводу А ₁ до сховища B ₁, необхідно також блокувати маршрут А ₁ B ₁. Для цього в зазначеній клітинці замість с ₁₁ = 4 записуємо величину М.

З огляду на викладене таблиця для першого плану транспортної задачі має такий вигляд (початковий опорний план побудовано методом апроксимації Фогеля).

 

Aj	Bj	ui	Різниці для рядків
B 1= 10	B 2= 20	B 3= 25	B 4= 20
A 1= 30	М	–15		10+	u 1= 0	2 2 2
A 2= 20					u 2= –1	3 3 3
A 3= 15	–10	5+			u 3= –2	2 5
A 4= 10	М – 4	М – 7	М – 4	М 10–	u 4= М –7
vj	v 1= 3	v 2= 5	v 3= 3	v 4= 7
Різниці для стовпчиків		2 2 1	1 1 1	2 2 2

 

Отже, перший опорний план задачі неоптимальний. Найбільше порушення умови оптимальності відповідає порожнім клітинкам А ₄ B ₁ та А ₃ B ₃ таблиці. Оскільки обидві вони мають однаковий коефіцієнт с ₄₁ = с ₄₃ = 0, то для заповнення можна вибрати будь-яку з них, наприклад А ₄ B ₁. Перехід до другого плану виконується за таким циклом:

При цьому заблокована клітинка А ₄ B ₄ звільняється. Подальше розв’язування задачі подано у вигляді таблиць.

 

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

 

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

 

В останній таблиці маємо оптимальний план транспортної задачі. Тому

,

Z _min = 5 × 5 + 5 × 25 + 5 × 20 + 3 × 15 = 245 ум. од.

 

Через незбалансованість поставленої транспортної задачі спостерігатиметься недопостачання бензину до першого бензосховища в кількості 10000 т. Загальні витрати на транспортування в цьому разі будуть найменшими і становитимуть 245 ум. од.

Альтернативний оптимальний план дістанемо, заповнивши клітинку А ₄ В ₃ (для неї u ₄ + v ₃ = c ₄₃) згідно з таким циклом:

Тоді можна записати:

,

Z _min = 5 × 15 + 3 × 15 + 5 × 20 + 1 × 10 + 3 × 15 = 245 ум. од.

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

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

 

 

Зі схеми бачимо, що на перший склад надходить лише 300 + 300 + 700 = 1300 од. продукції, тобто його місткість використовується не повністю (D ₁ D ₁ = 1200 од.). Це виникає внаслідок прямих поставок продукції за маршрутом А ₁ В ₂ у кількості 700 од. і А ₃ В ₄ — у кількості 500 од.

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

Поряд із розглянутою у транспортних задачах із проміжними пунктами можуть зустрічатися також такі ситуації:

1. Незбалансованість транспортної задачі (). У цьому разі необхідно ввести або фіктивного постачальника, або фіктивного споживача, звівши задачу до закритого типу.

2. Місткість проміжних пунктів не відповідає загальному обсягу продукції постачальників: а) коли (у цьому разі потрібно або ввести фіктивний проміжний пункт, і кількість продукції, що «перевозитиметься» до нього, має означати невивезену частину продукції відповідного постачальника, або дозволити транзитні перевозки за обсягом не менш як (од.)); б) коли (у цьому разі немає потреби вводити фіктивного постачальника і заздалегідь зрозуміло, що місткість проміжних пунктів повністю не використовуватиметься).

3. Місткість проміжних пунктів не відповідає загальній потребі споживачів: а) (у цьому разі потрібно або ввести фіктивний проміжний пункт, і кількість продукції, що «перевозитиметься» від нього до споживача В, має означати незадоволений попит відповідного споживача, або дозволити пряме перевезення продукції від постачальників до споживачів за обсягом не менш як (од.)); б) (аналогічно п. 2б).

 

5.2. Приклади та завдання для самостійної роботи

Розв’язати наведені далі транспортні задачі

	5.1	ai = (8; 10; 5); bj = (5; 5; 10);	.
5.2	ai = (8; 7; 6); bj = (7; 10; 6);	.
5.3	ai = (15; 10; 5; 20); bj = (10; 20; 15);	.
	5.4	ai = (10; 20; 40); bj = (30; 10; 60);	.
	5.5	ai = (30; 35; 60); bj = (25; 25; 40; 30);	.
	5.6	ai = (160; 80; 60); bj = (60; 20; 40; 20; 100);	.
	5.7	ai = (5; 20; 10); bj = (10; 25; 15);	.
	5.8	ai = (30; 40; 20); bj = (40; 30; 20; 40);	.
	5.9	ai = (30; 40; 50); bj = (35; 30; 60);	.
	5.10	ai = (10; 20; 80; 50); bj = (30; 10; 60; 50);	.
	5.11	ai = (40; 20; 50; 20); bj = (20; 45; 35; 40);	.

5.12 Передбачено штрафи за недопостачання одиниці продукції до споживачів В ₁, В ₂, В ₃ у розмірі відповідно 5, 3 та 2 ум. од. Визначити оптимальний план такої транспортної задачі:

ai = (10; 80; 15); bj = (75; 20; 50);

.

5.13 Розв’язати транспортну задачу:

ai = (80; 40; 60; 40); bj = (70; 60; 80);

,

якщо вартість зберігання одиниці невивезеної продукції у постачальників А ₁, А ₂, А ₃, А ₄ дорівнює відповідно 5, 4, 2 та 3 ум. од.

 

5.14 Розв’язати транспортну задачу:

ai = (75; 40; 35; 40); bj = (20; 60; 140);

,

якщо штрафи за недопостачання продукції споживачам В ₁, В ₂, В ₃ становлять відповідно 6, 4 та 8 ум. од.

 

 

5.15 Розв’язати транспортну задачу за умови, що вартість зберігання невивезеної продукції в постачальників А ₁, А ₂, А ₃ дорівнює відповідно 8, 7 та 5 ум. од. за одиницю продукції:

ai = (60; 90; 50); bj = (30; 80; 20; 40);

.

 

5.16 У транспортній задачі загальний обсяг виробництва продукції перевищує загальний попит. Припустимо, що вартість зберігання одиниці продукції, яка не вивозиться від постачальників А ₁, А ₂, А ₃, А ₄, дорівнює відповідно 7, 3, 4 та 8 ум. од. Визначити оптимальний план задачі:

ai = (30; 80; 20; 40); bj = (60; 80; 20);

.

 

5.17 У незбалансованій транспортній задачі загальний попит перевищує загальний обсяг виробництва на 10 ум. од. продукції. За недопостачання продукції споживачам умовою задачі передбачаються штрафи в розмірі 6 та 4 ум. од. за кожну одиницю продукції відповідно для першого та другого постачальників. Визначити оптимальний план такої транспортної задачі:

ai = (10; 10; 30; 20); bj = (20; 30; 20; 10);

.

 

5.18 У незбалансованій транспортній задачі призначено плату за зберігання кожної одиниці невивезеної продукції від постачальників у розмірі відповідно 5, 4 та 3 ум. од.. Визначити оптимальний план задачі, якщо висунуто таку додаткову умову: уся продукція від другого постачальника має бути вивезена повністю для того, щоб звільнилося місце для нової продукції.

ai = (20; 40; 30); bj = (30; 20; 20);

.

 

5.19 Розв’язати транспортну задачу:

ai = (20; 25; 20; 10); bj = (20; 30; 40; 15);

.

Додаткова умова: попит третього споживача задовольнити повністю.

5.20 Розв’язати транспортну задачу:

ai = (20; 16; 14; 22); bj = (16; 18; 12; 15);

.

Додаткова умова: ресурси четвертого постачальника використати повністю.

5.21 Розв’язати транспортну задачу:

ai = (10; 8; 15; 12); bj = (15; 10; 5; 20);

.

Додаткова умова: попит першого та четвертого споживачів задовольнити повністю.

 

5.22 Розв’язати транспортну задачу:

ai = (75; 80; 70); bj = (30; 70; 70; 35);

.

Додаткова умова: ресурси першого та третього постачальників використати повністю.

5.23 У транспортній задачі визначити оптимальний план за умови повного задоволення потреб першого та другого споживачів:

ai = (100; 150; 180; 70); bj = (100; 200; 230; 80);

.

5.24 Розв’язати транспортну задачу:

ai = (40; 30; 20; 40); bj = (20; 40; 30);

.

5.25 Додаткова умова: ресурси першого та другого постачальників в оптимальному плані використати повністю.

5.26 Визначити оптимальний план транспортної задачі:

ai = (75; 40; 35; 40); bj = (20; 60; 180);

,

в якій потрібно повністю задовольнити попит третього споживача та неможливо виконувати перевезення за маршрутами А ₁ В ₂ та А ₃ В ₁.

 

5.27 Знайти оптимальний план транспортної задачі:

ai = (80; 40; 60; 40); bj = (45; 65; 20; 80);

.

Додаткові умови: повністю використати ресурси четвертого постачальника та не виконувати перевезення за маршрутами А ₂ В ₃ та А ₃ В ₄.

 

5.28 Розв’язати транспортну задачу:

ai = (5; 20; 10; 15); bj = (10; 25; 15; 5);

.

Додаткова умова: попит другого споживача задовольнити повністю та за маршрутом А ₂ В ₃ перевезти рівно 10 од. продукції.

 

5.29 Визначити оптимальний план транспортної задачі:

ai = (10; 20; 20; 30); bj = (20; 15; 25; 10);

,

якщо ресурси четвертого постачальника потрібно використати повністю і за маршрутом А ₄ В ₃ перевезти 20 од. продукції.

5.30 Розглянути транспортну задачу, в якій необхідно перевезти деяку продукцію від постачальників А ₁, А ₂, А ₃ до споживачів В ₁, В ₂, В ₃, В ₄ через проміжні пункти D ₁, D ₂, D ₃. Запаси продукції у постачальників, попит споживачів та місткість складів відповідно a_i = (200; 220; 380), b_j = (150; 50; 350; 250), d_{i (j)}= (350; 200; 400).

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

А	D
D 1	D 2	D 3
A 1
A 2
A 3

 

D	B
B 1	B 2	B 3	B 4
D 1
D 2
D 3

 

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

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

 

5.31 Розв’язати двохетапну транспортну задачу a_i = (400; 200; 300), b_j = (300; 200; 350; 50), d_{i (j)}= (250; 250; 500).

 

А	D
D 1	D 2	D 3
A 1
A 2
A 3

 

D	B
B 1	B 2	B 3	B 4
D 1
D 2
D 3

 

Неприпустиме перевезення продукції зі складу на склад.

5.32 Розглянути транспортну задачу з проміжними пунктами, в якій кількість складів менша за ресурси постачальників. У такій ситуації дозволене транзитне перевезення продукції безпосередньо від постачальників А ₁ та А ₂ до першого споживача. Вартість перевезення одиниці продукції за транзитними маршрутами А ₁ В ₁ та А ₂ В ₁ становить відповідно 6 та 5 ум. од.; a_i = (200; 300), b_j = (250; 100; 150), d_{i (j)}= (100; 150; 150).

 

А	D
D 1	D 2	D 3
A 1
A 2

 

D	B
B 1	B 2	B 3
D 1
D 2
D 3

 

Визначити оптимальний план поставленої задачі.

 

5.33 Розглянути двохетапну транспортну задачу, в якій дозволене пряме перевезення продукції від першого постачальника до споживачів В ₁, В ₂, В ₃, В ₄. Вартість перевезення одиниці продукції за транзитними маршрутами дорівнює відповідно 3, 4, 5, 3 ум. од.; a_i = (300; 200; 100), b_j = (150; 50; 200; 200), d_{i (j)}= (250; 250).

 

А	D
D 1	D 2