3. Методи розв’язання транспортної задачі

ЗАВДАННЯ 3. У трьох пунктах виробництва А₁, А₂, А₃ зосереджений однорідний вантаж у кількостях відповідно рівних а₁, а₂, а₃ тонн. Даний вантаж споживається в чотирьох пунктах В1, В₂, В₃, В₄, а потреби в ньому в цих пунктах складають b₁, b₂, b₃, b₄, тонн відповідно. Відома матриця тарифів по перевезенню 1 тони вантажу з i^го пункту виробництва до j^го пункту споживання:

.

Скласти план перевезень:

,

при якому сумарні транспортні витрати будуть мінімальними.

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

3.1 методом потенціалів,

3.2 за допомогою інструмента «Поиск решения».

3.1 Математична модель транспортної задачі

Розглянемо поставлену задачу для таких вихідних даних:

30т, 20т, 40т,

20т, 30т, 20т, 30т,

.

Запишемо їх у вигляді таблиці.

Таблиця 3.1

Пункти виробництва	Пункти споживання				Запаси
	3	1	4	2	30
	1	4	3	3	20
	2	2	4	4	40
Потреби	20	30	20	30	90 100

До нижнього правого куту цієї таблиці занесемо значення сумарних потреб і сумарних витрат:

т, т.

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

Збалансуємо дану задачу, уводячи фіктивний пункт виробництва з запасом вантажу =100-90=10(т). При цьому вартість перевезень із цього пункту в кожний із пунктів споживання дорівнює 0 (див. табл. 3.2).

Таблиця 3.2

Пункти виробництва	Пункти споживання				Запаси
	3	1	4	2	30
	1	4	3	3	20
	2	2	4	4	40
	0	0	0	0	10
Потреби	20	30	20	30	90 100

Складемо математичну модель даної задачі.

1. Змінні задачі: – планований обсяг перевезення (у тоннах) з ^го пункту виробництва в ^й пункт споживання ( , ). Сукупність змінних утворить матрицю

.

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

.

3. Обмеження задачі: на вивіз вантажу

, (9)

на задоволення потреб у вантажі

, (10)

невід’ємність змінних:

( , ). (11)

Сукупність змінних , що задовольняють обмеженням (9)-(11), утворюють припустимий опорний план. Матриця системи (9) ‑ (10) має ранг на 1 менший кількості рядків цієї системи, тобто на 1 менший від суми кількостей пунктів виробництва і пунктів споживання, у даному випадку це – 7. Це означає, що кількість базисних змінних повинна дорівнювати 7.