Решение транспортной задачи методом потенциалов.

1.Взять любой опорный план перевозок, в котором отмечены

m + n - 1 базисных клеток (остальные клетки свободные).

2.Определить для этого плана платежи (αi и βj ) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю.

3.Подсчитать псевдостоимости c

i,j = αi + βj для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.

4.Если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путём переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости).

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

Блок-схема алгоритма метода потенциалов для задачи транспортного типа приведена в приложении А.

Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом:

F0 = 723, F1 = 709, F2 = Fmin = 703.

Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же Fmin = 703.

Транспортная задача с неправильным балансом

В предыдущих случаях мы рассматривали только такую задачу о перевозках, в которой сумма запасов ровна сумме заявок:

∑аш =∑ ио ( где ш=1бюююбь ж о=1бюююбт ) (4)

Это классическая транспортная задача, иначе называемая, транспортной задачей с правильным балансом. Встречаются такие варианты транспортной задачи где условие (4) нарушено. В этих случаях говорят о транспортной задаче с неправильным балансом.

Баланс транспортной задачи может нарушаться в 2-ух направлениях:

. Сумма запасов в пунктах отправления превышает сумму поданных заявок

∑ аш Ю ∑ ио ( где ш=1бюююбь ж о=1бюююбт )ж

. Сумма поданных заявок превышает наличные запасы

∑ аш Б ∑ ио ( где ш=1бюююбь ж о=1бюююбт )ж

Условимся первый случай называть “Транспортной задачей с избытком запасов“, а второй - “Транспортной задачей с избытком заявок”.

Рассмотрим последовательно эти два случая:

) Транспортная задача с избытком запасов.

В пунктах A1, A2, . , Am имеются запасы груза a1, a2, . , am; пункты B1, B2, . , Bn подали заявки b1, b2, . , bn, причём

∑ аш Ю ∑ ио ( где ш=1ююь ж о=1юют )ю

Требуется найти такой план перевозок (X), при котором все заявки будут выполнены, а общая стоимость перевозок минимальна. Очевидно при этой постановке задачи некоторые условия-равенства транспортной задачи превращаются в условия-неравенства, а некоторые - остаются равенствами.

n

∑ Xi,j ? ai (i=1, . , m);

j=1

m

∑ Xi,j = bj (j=1, . , n).

i=1

Мы умеем решать задачу линейного программирования, в какой бы форме - равенств или неравенств ни были бы заданы её условия. Поставленная задача может бать решена, например, обычным симплекс-методом. Однако, задачу можно решить проще, если искусственным приёмом свести её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения В1, B2, . , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками