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

Умова:

	A1	A2	A3	A4	Vi
B1
B2
B1
B1
Uj

Перевіряємо - чи закрита задача, чи відкрита. Для цього порівнюємо суми запасів вантажу та потреби в ньому: Маємо рівність:

15 + 13 + 7 + 11 = 46

10 + 12 + 18 + 6 = 46

Наша задача закрита. Будуємо перший опорний план метод північно-західного кута. Він матиме такий вигляд:

	A1	A2	A3	A4	Vi
B1			5 -	+
B2			7 +	6 -		- 2
B1						- 1
B1
Uj				- 7

Вартість перевезень (цільова функція буде дорівнювати:

Z₂ = 2*10 + 5*5 +3*7 + 4*6 + 1*7 + 3*5 + 2*6 = 124

Знаходимо систему потенціалів по правилу:

С_ij = V_i + U_j для заповнених маршрутів (клітин).

Після цього знаходимо _ij = С_ij - V_i + U_j для незаповнених маршрутів (клітин)

₁₃ = 1 – (6+0) = - 5; ₁₄ = 9 - (7+0) = 2; ₂₁ = 7 - (-2+2) = 7; ₂₄ = 5 – (-2 –7) = 14; ₃₁ = 4 – (-1 + 2) =5; ₃₂ = 2 - (5 – 1) = -2; ₃₄ = 5 – (-7 -1) = 13; ₄₁ = 18 – (2 + 9) = 7; ₄₂ = 16 – (5 + 9) = 2.

Серед від ємних _ij обираємо таку, яка має найбільше значення модуля. Це буде _13. Будуємо цикл перебудови опорного плану транспортної задачі через клітинки (1,3) - (2,3) - (2,2) - (1,2). Помічаємо знаками “+” та “-”

значення об’єму перевезеного вантажу починаючи з клітинки (1,3), де ставимо “+”, в клітинці (2,2) “-”,в клітинці (2,3) “+”, в клітинці (2,3) “-”.

Дата добавления: 2014-01-07