Решение задач транспортного типа методом потенциалов (стр. 3 из 4)

Распределительный метод решения транспортной задачи, с которым мы познакомились, обладает одним недостатком: нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой трудоёмкой работы нас избавляет специальный метод решения транспортной задачи, который называется методом потенциалов.

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

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.

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

Стоимость перевозки единицы груза из A_i в B_j равна C _ij ; таблица стоимостей задана. Требуется найти план перевозок x_ij, который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна.

Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления A_i вносит за перевозку единицы груза (всё равно куда) какую-то сумму a_i ; в свою очередь каждый из пунктов назначения B_j также вносит за перевозку груза (куда угодно) сумму b_j . Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим a_i + b_j = č_ij ( i=1..m ;j=1..n) и будем называть величину č_ij “псевдостоимостью” перевозки единицы груза из A_i в B_j. Заметим, что платежи a_i и b_j не обязательно должны быть положительными; не исключено, что “перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (a_i и b_j ) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи (a_i и b_j) и псевдостоимости č_ij с истинными стоимостями перевозок C _ij. Теперь мы установим между ними связь. Предположим, что план x_ij невырожденный (число базисных клеток в таблице перевозок ровно m + n -1). Для всех этих клеток x_ij >0. Определим платежи (a_i и b_j) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:

č_ij = a_i + b_j = с_ij , при x_ij >0.

Что касается свободных клеток (где x_ij = 0), то в них соотношение между псевдостоимостями и стоимостями может быть, какое угодно.

Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана x_ij > 0,

a_i + b_j = č_ij= с_ij ,

а для всех свободных клеток x_ij =0,

a_i + b_j = č_ij≤ с_ij ,

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

č_ij= с_ij (для всех базисных клеток ) (1)

č_ij≤ с_ij ( для всех свободных клеток ) (2)

называется потенциальным планом, а соответствующие ему платежи (a_i и b_j ) — потенциалами пунктов A_i и B_j ( i=1,...,m ; j=1,...,n ). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так:

Всякий потенциальный план является оптимальным.

Итак, для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (a_i и b_j ) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке : g_i,j= с_i,j - č_i,j.

Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.

Процедура построения потенциального (оптимального) плана состоит в следующем.

В качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане m + n - 1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи (a_i и b_j ), так, чтобы в каждой базисной клетке выполнялось условие :

a_i + b_j = с_ij (3)

Уравнений (3) всего m + n - 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений (3) можно найти остальные платежи a_i, b_j, а по ним вычислить псевдостоимости, č_i,j= a_i + b_j для каждой свободной клетки.

Таблица №5

ПН ПО	В1	В2	В3	В4	В5	ai
А1	10 č = 7	8 č = 6	5 42	6 6	9 č = 6	a1= 0
А2	6 4	7 č = 5	8 č = 4	6 č = 5	5 26	a2= -1
А3	8 č = 8	7 27	10 č = 6	8 č = 7	7 0	a3= 1
А4	7 14	5 č = 6	4 č = 5	6 6	8 č = 6	a4= 0
bj	b1= 7	b2= 6	b3= 5	b4= 6	b5= 6

a₄ = 0, ®

b₄ = 6, так как a₄ + b₄ = С₄₄ = 6, ®

a₁= 0, так как a₁ + b₄ = С₁₄ = 6, ®

b₃ = 5, так как a₁ + b₃ = С₁₃ = 5, ®