Приклад

Розв’язати методом потенціалів транспортну задачу, умова якої надається таблицею 8.6.

Таблиця 8.6

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1
A2
A3
Потреби

Розв’язання

Початковий опорний план ТЗ, який отримано методом північно-західного кута, наведено в таблиці 8.7.

Таблиця 8.7

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1
A2
A3
Потреби

Для визначення потенціалів u_i, v_j сформуємо відповідну систему рівнянь:

u₁ + v₁ = 2,

u₁ + v₂ = 5,

u₂ + v₂ = 4,

u₂ + v₃ = 5,

u₃ + v₃ = 3,

u₃ + v₄ = 4.

Покладемо в системі u₁ = 0, й отримаємо потенціали початкового опорного плану ТЗ. Вони рівні:

v₁ = 2, v₂ = 5, v₃ = 6, v₄ = 7, u₂ = -1, u₃ = -3.

Занесемо отримані потенціали в таблицю 8.8.

Таблиця 8.8

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1						u1 = 0
A2						u2 = -1
A3						u3 = -3
Потреби
	v1 = 2	v2 = 5	v3 = 6	v4 = 7

 

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

u₁ + v₃ = 6 3 –?

u₁ + v₄ = 7 1–?

u₂ + v₁ = 1 3,

u₂ + v₄ = 6 2 –?

u₃ + v₁ = -1 4,

u₃ + v₂ = 2 5.

З наведених нерівностей випливає, що умова оптимальності не виконується для клітинок (1.3), (1.4) і (2.4). Тому необхідно перейти до нового опорного плану.

Оберемо клітинку, для якої необхідно здійснити цикл перерахування. Для її вибору обчислимо

₁₃ = (u₁ + v₃) – с ₁₃ = 0 + 6 – 3 = 3,

₁₄ = (u₁ + v₄) – с ₁₄ = 0 + 7 – 1 = 6,

₂₄ = (u₂ + v₄) – с ₂₄ = –1 + 7 – 2 = 4.

max _ij = 6.

Отже, цикл перерахування слід здійснити для клітинки (1.4). Виконання перерозподілу продукції в межах циклу можна оцінити з таблиці 8.9.

Таблиця 8.9

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1		70 –		1 +
A2		4 80 +	70 –
A3			3 100 +	100 –
Потреби

При цьому в клітинки (1.4), (2.2) і (3.2) переноситься 70 одиниць продукції, а з клітинок (1.2), (2.3) і (3.4) така ж кількість продукції вилучається. З урахуванням цього новий план ТЗ матиме вигляд (табл. 8.10). Він є виродженим.

Таблиця 8.10

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1
A2
A3
Потреби

Оскільки план з таблиці 8.10 виявився виродженим здійснимо цикл перерахування для клітинки (2.4). Виконання перерозподілу продукції в межах циклу можна оцінити з наступної таблиці (табл. 8.11).

Таблиця 8.11

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1
A2			70 –	2 +
A3			100 +	100 –
Потреби

При цьому в клітинки (2.4) і (3.3) переноситься 70 одиниць продукції, а з клітинок (2.3) і (3.4) така ж кількість продукції вилучається. З урахуванням цього новий план ТЗ матиме вигляд (табл. 8.12).

Таблиця 8.12

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1						u1 = 0
A2						u2 = -1
A3						u3 = 1
Потреби
	v1 = 2	v2 = 5	v3 = 2	v4 = 3

 

Для визначення потенціалів u_i, v_j нового невиродженого плану сформуємо відповідну систему рівнянь:

u₁ + v₁ = 2,

u₁ + v₂ =5,

u₂ + v₂ = 4,

u₂ + v₄ = 2,

u₃ + v₃ = 3,

u₃ + v₄ = 4.

Покладемо в системі u₁ = 0, й отримаємо потенціали початкового опорного плану ТЗ. Вони рівні:

v₁ = 2, v₂ = 5, v₃ = 2, v₄ = 3, u₂ = -1, u₃ = 1.

Занесемо отримані потенціали в таблицю 8.12. Перевіримо виконання умов оптимальності для незаповнених клітинок таблиці 8.12.

u₁ + v₃ = 2 3,

u₁ + v₄ = 3 1–?

u₂ + v₁ = 1 3,

u₂ + v₃ = 1 5,

u₃ + v₁ = 3 4,

u₃ + v₂ = 6 5–?

З наведених нерівностей випливає, що умова оптимальності не виконується для клітинок (1.4) і (3.2). Тому необхідно перейти до нового опорного плану.

Оберемо клітинку, для якої необхідно здійснити цикл перерахування. Для її вибору обчислимо

₁₄ = (u₁ + v₄) – с ₁₄ = 0 + 3 – 1 = 2,

₃₂ = (u₃ + v₂) – с ₃₂ = 1 + 5 – 5 = 1.

max _ij = 2.

Отже, цикл перерахування слід здійснити для клітинки (1.4), але при цьому знов отримаємо вироджений опорний план ТЗ. Тому, здійснимо цикл перерахування для клітинки (3.2) (табл. 8.13).

Таблиця 8.13

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1
A2		80 –		70 +
A3		5 +		30 –
Потреби

 

При цьому в клітинки (2.4) і (3.2) переноситься 30 одиниць продукції, а з клітинок (2.2) і (3.4) така ж кількість продукції вилучається. З урахуванням цього новий план ТЗ матиме вигляд (табл. 8.14).

Таблиця 8.14

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1						u1 = 0
A2						u2 = -1
A3						u3 = 0
Потреби
	v1 = 2	v2 = 5	v3 = 3	v4 = 3

 

Для визначення потенціалів u_i, v_j нового невиродженого плану сформуємо відповідну систему рівнянь:

u₁ + v₁ = 2,

u₁ + v₂ =5,

u₂ + v₂ = 4,

u₂ + v₄ = 2,

u₃ + v₂ = 5,

u₃ + v₃ = 3.

Покладемо в системі u₁ = 0, й отримаємо потенціали початкового опорного плану ТЗ. Вони рівні:

v₁ = 2, v₂ = 5, v₃ = 3, v₄ = 3, u₂ = -1, u₃ = 0..

Занесемо отримані потенціали в таблицю (табл. 8.14).

Перевіримо виконання умов оптимальності для незаповнених клітинок таблиці 8.14

u₁ + v₃ = 2 3,

u₁ + v₄ = 3 1–?

u₂ + v₁ = 1 3,

u₂ + v₃ = 2 5,

u₃ + v₁ = 2 4,

u₃ + v₄ = 3 4.

З наведених нерівностей випливає, що умова оптимальності не виконується для клітинки (1.4). Тому необхідно перейти до нового опорного плану.

Таблиця 8.15

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1		70 –		1 +
A2		4 50 +		100 –
A3
Потреби

 

При цьому в клітинки (1.4) і (2.2) переноситься 70 одиниць продукції, а з клітинок (1.2) і (3.4) така ж кількість продукції вилучається. З урахуванням цього новий план ТЗ матиме вигляд (табл. 8.16).

Таблиця 8.16

Пункти	Споживачі	Запаси
B1	B2	B3	B4
A1						u1 = 0
A2						u2 = 1
A3						u3 = 2
Потреби
	v1 = 2	v2 = 3	v3 = 3	v4 = 1

 

Для визначення потенціалів u_i, v_j нового невиродженого плану сформуємо відповідну систему рівнянь:

u₁ + v₁ = 2,

u₁ + v₄ =1,

u₂ + v₂ = 4,

u₂ + v₄ = 2,

u₃ + v₂ = 5,

u₃ + v₃ = 3.

Покладемо в системі u₁ = 0, й отримаємо потенціали початкового опорного плану ТЗ. Вони рівні:

v₁ = 2, v₂ = 3, v₃ = 3, v₄ = 1, u₂ = 1, u₃ = 2.

Занесемо отримані потенціали в таблицю 8.16.Перевіримо виконання умов оптимальності для незаповнених клітинок таблиці 8.16

u₁ + v₂ = 3 5,

u₁ + v₃ = 3 3,

u₂ + v₁ = 3 3,

u₂ + v₃ = 4 5,

u₃ + v₁ = 4 4,

u₃ + v₄ = 3 4.

З наведених нерівностей випливає, що умова оптимальності виконується для клітинки всіх перевірених клітин. Отже, опорний план є оптимальним.

Таким чином,

Х^* = (х ₁₁ = 180; х ₁₄ = 70; х ₂₂ = 120; х ₂₄ = 30; х ₃₂ = 30; х ₃₃ = 170).

При цьому

F_min = 180*2 + 70*1 + 120*4 + 30*2 + 30*5 + 170*3 = 1630 одиниць вартості.