Реферат: Решение задач транспортного типа методом потенциалов

Существует несколько вариантов цикла:

1.) 2.) 3.)

Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком + те вершины цикла, в которых перевозки необходимо увеличить, а знаком - , те вершины , в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть означенным. Перенести какое-то количество единиц груза по означенному циклу, это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце - заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно, цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком + , а в отрицательных со знаком - . Обозначим цену цикла через g . При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину g . При перемещении по нему k единиц груза стоимость перевозок увеличиться на k g . Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение, стоимость плана уменьшается на соответствующую величину k g . Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.

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

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

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

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

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	a i
А 1	10 č = 7	8 č = 6	5 42	6 6	9 č = 6	a 1 = 0
А2	6 4	7 č = 5	8 č = 4	6 č = 5	5 26	a 2 = -1
А3	8 č = 8	7 27	10 č = 6	8 č = 7	7 0	a 3 = 1
А4	7 14	5 č = 6	4 č = 5	6 6	8 č = 6	a 4 = 0
b j	b 1 = 7	b 2 = 6	b 3 = 5	b 4 = 6	b 5 = 6

a ₄ = 0, ®

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

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

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

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