Знайдено 55 розв'язаних задач даної теми. Детальніше ...

---

Умова задачі
Розв'язати транспортну задачу.

A = (60, 40, 100, 50)

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

Розв'язання

Побудуємо схему транспортної мережі матричної задачі оптимізації.

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

Пункти відправки	Пункти призначення					Запаси
	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.

Переходимо до наступної ітерації.

---

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

---

Знайдено 55 розв'язаних задач даної теми. Детальніше ...