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

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

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

причем

Стоимость перевозки единицы груза из равна с; таблица стоимостей задана.

Требуется найти план перевозок который удовлетворял бы балансовым условиям (12.1), и при этом стоимость всех перевозок была минимальна:

Идея метода потенциалов для решения ТЗ сводится к следующему. Представим себе, что каждый из пунктов отправления вносит за перевозку единицы груза (все равно, куда) какую-то сумму в свою очередь, каждый из пунктов назначения также вносит за перевозку единицы груза (куда угодно) сумму эти платежи передаются некоторому третьему лицу («перевозчику»).

Обозначим

и будем называть величину «псевдостоимостью» перевозки единицы груза из

Заметим, что платежи не обязательно должны быть Положительными: не исключено, что «перевозчик» сам платит тому или другому пункту какую-то премию за перевозку.

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

Для заданной совокупности платежей суммарная псевдостоимость перевозок

при любом допустимом плане перевозок сохраняет одно и то же значение

(12.4)

В этой формуле величина С зависит только от совокупности платежей но не зависит от того, каким именно допустимым планом мы пользуемся.

Докажем это положение. Имеем:

Преобразуем первую из двойных сумм в выражении (12.5). Вынесем из-под знака суммы по

Но план является допустимым, значит, для него выполняется балансовое условие:

откуда

Аналогичным образом преобразуем второе слагаемое в (12.5):

Подставляя (12.6) и (12.7) в (12.5), получим:

В формуле (12.8) правая часть не зависит от плана перевозок а зависит только от запасов заявок и платежей

Таким образом, мы доказали, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи и псевдостоимости с истинными стоимостями перевозок Теперь мы установим между ними связь.

Предположим, что план невырожденный (число базисных клеток в таблице перевозок равно). Для всех этих клеток Определим платежи так, чтобы во всех базисных клетках псевдостоимости были равны стоимостям:

что касается свободных клеток (где то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно:

Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным, или же он может быть улучшен.

Докажем следующую теорему.

Теорема.

Если для всех базисных клеток плана

а для всех свободных клеток

то план является оптимальным и никакими способами улучшен быть не может.

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

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

(12.10)

На основании ранее доказанного, эта сумма (при данной системе платежей) равна некоторой константе С (см. (12.4)):

(12.11)

Теперь попробуем изменить план заменив его каким-то другим планом Обозначим стоимость нового плана

(12.12)

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

Поэтому сумма (12.12) не может быть меньше, чем сумма (12.11) (она же 12.9):

Мы видим, что никаким изменением плана его стоимость не может быть уменьшена; значит, план является оптимальным и теорема доказана.

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

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

План, обладающий таким свойством, называется потенциальным, а соответствующие ему платежи — потенциалами пунктов.

Пользуясь этой терминологией, доказанную выше теорему можно сформулировать так:

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

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

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

При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей:

Какова бы ни была система платежей удовлетворяющая условию (12.14 а), для каждой свободной клетки цена цикла пересчета равна разности между стоимостью и псевдостоимостью в данной клетке;

(12.15)

Таблица 12.1

Действительно, рассмотрим какую-то транспортную таблицу, например (табл. 12.1).

Не будеи проставлять в этой таблице ни запасов, ни заявок, ни перевозок (они не будут нам нужны), просто отметим (обведем жирной линией) базисные клетки.

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

Но для всех базисных клеток стоимости равны псевдостоимостям, поэтому

т. е. цена цикла, начинающегося в свободной клетке (1, 5) равна разности стоимости и псевдостоимости в этой клетке.

Очевидно, то же будет справедливо и для любой свободной клетки.

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

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

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

(12.16)

Уравнений (12.16) всего, а число неизвестных равно. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из уравнений (12.16) можно найти остальные платежи а по ним вычислить псевдостоимости:

для каждой свободной клетки. Если оказалось, что все эти псевдостоимости не превосходят стоимостей

(12.17)

то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости

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

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

1. Взять любой опорный план перевозок, в котором отмечены базисных клеток (остальные клетки — свободные).

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

(12.18)

Один из платежей можно назначить произвольно, например, положить равным нулю.

3. Подсчитать псевдостоимости для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.

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

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

Таблица 12.2

Понятиям «платежей» и и «псевдостоимостей» можно дать наглядную экономическую интерпретацию.

Представим себе, что -реальные платежи, которые пункты платят за перевозку единицы груза какому-то третьему лицу («перевозчику»). Не будем противопоставлять интересов А и В — пусть они действуют как единая экономическая система. Перевозка единицы груза из пункта в пункт объективно стоит а стороны А и В вместе платят за эту перевозку «перевозчику» сумму. Оптимальным будет такой план перевозок, при котором пункты не переплачивают «перевозчику» ничего сверх объективной стоимости перевозок, т. е. такой план, любое отступление от которого невыгодно для компании А, В — оно заставит их платить за перевозки больше, чем если бы они возили грузы сами.

Продемонстрируем применение метода потенциалов для решения ТЗ на конкретном примере.

Пример 1. Решить методом потенциалов ТЗ, заданную в табл. 12.2, где проставлен первый опорный план, составленный по способу северо-западного угла.

Решение. Приписываем к табл 12 2 снизу добавочную строку для платежей справа — добавочный столбец для платежей а; (см табл. 12.3) Псевдостоимости записываем в левом верхнем углу каждой клетки, а стоимости — в правом верхнем углу. Один из платежей, например выбираем произвольно, полагая, скажем, Для каждой базисной клетки псевдостоимость должна быть равна стоимости

Полагая находим из условия

а из условия

Таблица 12.3

Продолжая эту процедуру, находим:

Так как не все псевдостоимости в свободных клетках табл. 12.3 удовлетворяют условию (12.17), план, приведенный в табл. 12.3, не является оптимальным Попробуем улучшить его, переводя в базисные одну из свободных клеток, для которых например, клетку (2, 1) Строим соответствующий этой клетке цикл (показан в табл. 12.3). Цена этого цикла Перенесем по этому циклу 13 единиц груза (больше нельзя, чтобы перевозки в клетке (2,2) не стали отрицательными), уменьшим стоимость плана на и перейдем к табл. 12.4.

Вычисляем для плана табл. 12.4 новые значения платежей, по-прежнему полагая Видим, что в табл. 12.4 все еще есть свободные клетки, для которых например (1, 4). Цикл для этой клетки показан в табл 12.4. Перенос четырех единиц по этому циклу приводит к плану, представленному (со своими платежами и псевдостоимостями) в табл. 12.5.

Таблица 12.4

Таблица 12.5

Таблица 12.6

Таблица 12.7

Таблица 12.8

Таблица 12.9

Таблица 12.10

Таблица 12.11

Таблица 12.12

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

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

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

Пример 2. Решить методом потенциалов ТЗ, условия которой даны в табл. 12.7.

Решение. Применяя способ ceвepo-западного угла, получаем вырожденный план. Вводя -изменения запасов, получаем опорный план с пятью базисными клетками. Подсчитывая платежи (табл. 12.8), видим, что план не оптимален. Улучшаем его циклическим переносом перевозок, и т. д. Процедура улучшения плана показана в табл. 12.8, 12.9, 12.10. 12.11; план, приведенный в последней таблице, оптимален. Полагая в нем получаем окончательный оптимальный план (табл. 12.12) со стоимостью

Заметим, что эта стоимость такая же, как стоимость плана, показанного в табл. 12.10 при это и естественно, так как табл. 12.11 получена из табл. 12.10 переносом по циклу фиктивных -перевозок; этот перенос не меняет стоимости плана, а нужен только для того, чтобы убедиться, что план оптимален.