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

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

Транспортная таблица строится по правилу северо-западного угла, в соответствии с которым заполнение транспортной таблицы начинается с левой верхней клетки и состоит из однотипных шагов, на каждом из которых исключается один пункт потребления или один пункт производства в зависимости от соотношения остатка продукта в соответствующем пункте производства или остатка запроса в соответствующем пункте потребления

Следует иметь в виду, что по любой транспортной таблице можно восстановить предпочитаемый эквивалент системы уравнений 3) – 4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе 3) – 4) ровно (m + n – 1) линейно независимых уравнений, то в любой транспортной таблице должно быть m + n – 1 занятых клеток.

Решаем транспортную задачу методом потенциалов, в соответствии с которым каждому пункту производства ставится в соответствие потенциал pi, а каждому пункту потребления – потенциал qj.

Обозначим через μ (p1, p2, p3, q1, q2, q3, q4) вектор симплексных множителей или потенциалов.

Каждой клетке транспортной таблицы соответствует некоторая оценка:

_ij = p_i + q_j - c_ij i = 1, 2, 3; j = 1, 2, 3, 4

Один из потенциалов можно выбрать произвольно, так как в системе уравнений 3) – 4)одно уравнение линейно зависит от остальных.

Положим, что p1 = 0

Остальные потенциалы находим из условия, что для базисных клеток _ij = 0:

₁₁= 0,p₁+q₁-c₁₁= 0, 0 +q₁ - 3 = 0,q₁ = 3

₁₂= 0,p₁+q₂-c₁₂= 0, 0 +q₂-2 = 0,q₂ = 2

₂₂= 0,p₂+q₂-c₂₂= 0, р₂ + 2 - 3 = 0, р₂ = 1

₂₃ = 0, p₂ + q₃ – c₂₃ = 0, 1 + q₃ - 1 = 0, q₃ = 0

₂₄ = 0, p₂ + q₄ – c₂₄ = 0, 1 + q₄ - 4 = 0, q₄ = 3

₃₄ = 0, p₃ + q₄ – c₃₄ = 0, р₃ + 3 - 1 = 0, р₃ = - 2

₃₅= 0,p₃+q₅–c₃₅= 0, -2 +q₅ - 0 = 0,q₅ = 2

Вычисляем оценки всех свободных клеток вычисляем по формуле_ij = p_i + q_j - c_ij:

₁₃ = p₁ + q₃ - c₁₃ = 0 + 0 - 4 = - 4

₁₄ = p₁ + q₄ - c₁₄ = 0 + 3 - 3 = 0

₁₅ = p₁ + q₅ – c₁₅ = 0 + 2 - 0 = 2

₂₁ = p₂ + q₁ - c₂₁ = 1 + 3 - 5 = - 1

₂₅ = p₂ + q₅ - c₂₅ = 1 + 2 - 0 = 3

₃₁ = p₃ + q₁ – c₃₁ = - 2 + 3 - 4 = - 3

₃₂ = p₃ + q₂ – c₃₂ = - 2 + 2 - 3 = - 3

₃₃ = p₃ + q₃ – c₃₃ = - 2 + 0 - 6 = - 8

Находим наибольшую положительную оценку:

max() = 3 =

Для найденной свободной клетки 31 строим цикл пересчета – замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в найденной свободной клетке 25, а все остальные – в ближайших занятых клетках.

Это будет 25 – 24 – 34 – 35. Клетка 25 помечается знаком «плюс», далее соседние вершины цикла пересчета помечаются по очереди знаками «минус» и «плюс». Выбирается минимальная из поставок, отмеченных знаком «минус» ρ max, и к поставкам, отмеченным знаком «плюс» добавляется ρ max, а из поставок, отмеченных знаком «минус», вычитается ρ max

ρ max= 2 производим перераспределение поставок вдоль цикла пересчета

Получаем второе базисное допустимое решение и заполняем вторую транспортную таблицу

Находим новые потенциалы и оценки всех свободных клеток.

₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0 + q₁ - 3 = 0, q₁ = 3

₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0 + q₂ -2 = 0, q₂ = 2

₂₂ = 0, p₂ + q₂ - c₂₂ = 0, р₂ + 2 - 3 = 0, р₂ = 1

₂₃ = 0, p₂ + q₃ – c₂₃ = 0, 1 + q₃ - 1 = 0, q₃ = 0

₂₅= 0,p₂+q₅–c₂₅= 0, 1 +q₅ - 0 = 0,q₅ = - 1

₃₄ = 0, p₃ + q₄ – c₃₄ = 0, 1 + q₄ - 1 = 0, q₄ = 0

₃₅ = 0, p₃ + q₅ – c₃₅ = 0, p₃ - 1 - 0 = 0, р₃ = 1

₁₃ = p₁ + q₃ - c₁₃ = 0 + 0 - 4 = - 4 ₂₄ = p₂ + q₄ - c₂₄ = 1 + 0 - 4 = - 3

₁₄ = p₁ + q₄ - c₁₄ = 0 + 0 - 3 = - 3 ₃₁ = p₃ + q₁ – c₃₁ = 1 + 3 - 4 = 0

₁₅ = p₁ + q₅ – c₁₅ = 0 - 1 - 0 = - 1 ₃₂ = p₃ + q₂ – c₃₂ = 2 + 1 - 3 = 0

₂₁=p₂+q₁-c₂₁= 1 + 3 - 5 = - 1₃₃=p₃+q₃–c₃₃= 0 + 1 - 6 = - 5

Все _ij ≤ 0, следовательно, оптимальным базисным решением будет

Общая стоимость перевозок составит:

L (min) = 38*3 + 22*2 + 20*3 + 28*1 + 41*1 = 287 денежных единиц.

Экономический смысл потенциалов и оценок клеток транспортной таблицы.

Оценка свободной клетки _ij показывает, насколько уменьшатся суммарные расходы по перевозке груза, если поставить единицу от i-го производителя j-му потребителю (перераспределив основные поставки так, чтобы сохранился баланс по строкам и столбцам).

Потенциалы указывают на то, сколько каждый производитель уплачивает перевозчику (pi) за вывоз единицы груза; каждый потребитель уплачивает перевозчику (qj) за получение единицы груза. При это м необходимо выполнение условия, что сумма цен, взимаемых с пары «производитель – потребитель» не должна превосходить реальной стоимости перевозки груза между ними, что в итоге приводит к задаче, двойственной по отношению к транспортной, и интерпретации оценок клеток и потенциалов, основанной на теоремах двойственности.

В реальных условиях pi и qj – не цены, а надбавки к основному тарифу перевозчика, единому для всех производителей и потребителей.