Найдено 90 решенных задач данной темы. Подробнее ...

---

Условие задачи
Решить транспортную задачу.

A = (60, 40, 100, 50)

B = (30, 80, 70, 35, 40)

$ C = \left( \begin{array}{rrrrr} 8&12&4&9&10\\ 7&5&15&3&6\\ 9&4&6&12&7\\ 5&3&2&6&4 \end{array} \right) $

Решение

Построим схему транспортной сети матричной задачи оптимизации.

Запишем условие задачи в экономическом виде на основании таблицы, где заданы пункты
отправления и назначения, запасы и потребности.

Пункты отправления	Пункты назначения					Запасы
	B1	B2	B3	B4	B5
A1	8	12	4	9	10	60
A2	7	5	15	3	6	40
A3	9	4	6	12	7	100
A4	5	3	2	6	4	50
Потребности	30	80	70	35	40	255\250

Поскольку запасы и потребности не совпадают, имеем задачу с неправильным балансом или
открытую, следовательно введем фиктивный пункт отправления с количеством 5 единиц груза.

Запишем общую математическую постановку транспортной задачи как задачи линейного программирование, которая заключается в определении минимального значения функции:

при условиях:

Следовательно, задача линейного программирования запишется так:

F = 8x₁₁ + 12x₁₂ + 4x₁₃ + 9x₁₄ + 10x₁₅ + 7x₂₁ + 5x₂₂ + 15x₂₃ + 3x₂₄ + 6x₂₅ + 9x₃₁ + 4x₃₂ + 6x₃₃ + 12x₃₄ + 7x₃₅ + 5x₄₁ + 3x₄₂ + 2x₄₃ + 6x₄₄ + 4x₄₅ → min

при условиях:

x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ = 60,
x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅ = 40,
x₃₁ + x₃₂ + x₃₃ + x₃₄ + x₃₅ = 100,
x₄₁ + x₄₂ + x₄₃ + x₄₄ + x₄₅ = 50,
x₅₁ + x₅₂ + x₅₃ + x₅₄ + x₅₅ = 5,
x₁₁ + x₂₁ + x₃₁ + x₄₁ + x₅₁ = 30,
x₁₂ + x₂₂ + x₃₂ + x₄₂ + x₅₂ = 80,
x₁₃ + x₂₃ + x₃₃ + x₄₃ + x₅₃ = 70,
x₁₄ + x₂₄ + x₃₄ + x₄₄ + x₅₄ = 35,
x₁₅ + x₂₅ + x₃₅ + x₄₅ + x₅₅ = 40,

x_ij > 0, x_ij є Z.

Найдем опорный план методом наименьшей стоимости.

Порядок заполнения клеток следующий: A₅B₁ (0) = 5, A₄B₃ (2) = 50, A₂B₄ (3) = 35, A₁B₃ (4) = 20, A₃B₂ (4) = 80, A₂B₅ (6) = 5, A₃B₅ (7) = 20, A₁B₁ (8) = 25, A₁B₅ (10) = 15.

B  A		1		2		3		4		5		a
		30		80		70		35		40
1	60	8		12		4		9		10		0
		25				20	+			15	–
2	40	7		5		15		3		6		-4
								35		5
3	100	9		4		6		12		7		-3
				80						20
4	50	5		3		2		6		4		-2
						50	–			0	+
5	5	0		0		0		0		0		-8
		5
b		8		7		4		7		10

Стоимость начального плана перевозки:

z₀ = 25 · 8 + 20 · 4 + 15 · 10 + 35 · 3 + 5 · 6 + 80 · 4 + 20 · 7 + 50 · 2 + 5 · 0 = 1125.

Для базисных клеток система потенциалов такая:

a₁ + b₁ = 8;  a₁ + b₃ = 4;  a₁ + b₅ = 10; 
a₂ + b₄ = 3;  a₂ + b₅ = 6; 
a₃ + b₂ = 4;  a₃ + b₅ = 7; 
a₄ + b₃ = 2; 
a₅ + b₁ = 0. 

Поскольку количество переменных меньше, чем уравнений, то положим a₁ = 0. Проверяем условие оптимальности для свободных клеток: a + b < c.

a₁ + b₂ = 0 + 7 = 7 < 12;  a₁ + b₄ = 0 + 7 = 7 < 9; 
a₂ + b₁ = -4 + 8 = 4 < 7;  a₂ + b₂ = -4 + 7 = 3 < 5;  a₂ + b₃ = -4 + 4 = 0 < 15; 
a₃ + b₁ = -3 + 8 = 5 < 9;  a₃ + b₃ = -3 + 4 = 1 < 6;  a₃ + b₄ = -3 + 7 = 4 < 12; 
a₄ + b₁ = -2 + 8 = 6 > 5 [1];  a₄ + b₂ = -2 + 7 = 5 > 3 [2];  a₄ + b₄ = -2 + 7 = 5 < 6;  a₄ + b₅ = -2 + 10 = 8 > 4 [4]; 
a₅ + b₂ = -8 + 7 = -1 < 0;  a₅ + b₃ = -8 + 4 = -4 < 0;  a₅ + b₄ = -8 + 7 = -1 < 0;  a₅ + b₅ = -8 + 10 = 2 > 0 [2]. 

Для клетки A₄B₅ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(15, 50) = 15.

Переходим к следующей итерации.

---

Зарегистрируйтесь и Вы сможете посмотреть задачу полностью!

---

Найдено 90 решенных задач данной темы. Подробнее ...