Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
12. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ МЕТОДОМ ПОТЕНЦИАЛОВРаспределительный метод решения ТЗ, с которым мы познакомились в предыдущем параграфе, обладает одним недостатком: нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой трудоемкой работы нас избавляет специальный метод решения ТЗ, который называется методом потенциалов. Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями
причем
Стоимость перевозки единицы груза из Требуется найти план перевозок
Идея метода потенциалов для решения ТЗ сводится к следующему. Представим себе, что каждый из пунктов отправления Обозначим
и будем называть величину Заметим, что платежи Обозначим для краткости всю совокупность платежей Для заданной совокупности платежей
при любом допустимом плане перевозок
В этой формуле величина С зависит только от совокупности платежей Докажем это положение. Имеем:
Преобразуем первую из двойных сумм в выражении (12.5). Вынесем
Но план
откуда
Аналогичным образом преобразуем второе слагаемое в (12.5):
Подставляя (12.6) и (12.7) в (12.5), получим:
В формуле (12.8) правая часть не зависит от плана перевозок Таким образом, мы доказали, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах До сих пор мы никак не связывали платежи Предположим, что план
что касается свободных клеток (где
Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным, или же он может быть улучшен. Докажем следующую теорему. Теорема. Если для всех базисных клеток плана
а для всех свободных клеток
то план является оптимальным и никакими способами улучшен быть не может. Доказательство. Обозначим (
В сумме (12.9) отличны от нуля только слагаемые, соответствующие базисным клеткам, в них стоимости равны псевдостоимостям. Поэтому
На основании ранее доказанного, эта сумма (при данной системе платежей) равна некоторой константе С (см. (12.4)):
Теперь попробуем изменить план
где
Поэтому сумма (12.12) не может быть меньше, чем сумма (12.11) (она же 12.9):
Мы видим, что никаким изменением плана Нетрудно показать, что эта теорема справедлива также для вырожденного плана, в котором некоторые из базисных переменных равны нулю. Действительно, то, что в базисных клетках перевозки строго положительны, для доказательства несущественно: достаточно, чтобы они были неотрицательными. Таким образом, доказано, что признаком оптимальности плана
План, обладающий таким свойством, называется потенциальным, а соответствующие ему платежи Пользуясь этой терминологией, доказанную выше теорему можно сформулировать так: Всякий потенциальный план является оптимальным. Итак, для решения транспортной задачи нам нужно одно — построить потенциальный план. Оказывается, его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (12.14 а). При этом в каждой базисной клетке получается сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план, следует одновременно менять систему платежей так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: Какова бы ни была система платежей
Таблица 12.1
Действительно, рассмотрим какую-то транспортную таблицу, например Не будеи проставлять в этой таблице ни запасов, ни заявок, ни перевозок (они не будут нам нужны), просто отметим (обведем жирной линией) базисные клетки. Возьмем любую свободную клетку, например (1.5), и построим соответствующий ей цикл пересчета, положительная вершина которого лежит в этой свободной клетке, а все остальные — в базисных. Определим цену этого цикла. Она равна
Но для всех базисных клеток стоимости равны псевдостоимостям, поэтому
т. е. цена цикла, начинающегося в свободной клетке (1, 5) равна разности стоимости Очевидно, то же будет справедливо и для любой свободной клетки. Таким образом, при пользовании методом потенциалов для решения ТЗ отпадает наиболее трудоемкий элемент распределительного метода: поиски циклов с отрицательной ценой. Процедура построения потенциального (оптимального) плана состоит в следующем. В качестве первого приближения к оптимальному плану берется любой допустимый план (хотя бы построенный способом северо-западного угла). В этом плане
Уравнений (12.16) всего
для каждой свободной клетки. Если оказалось, что все эти псевдостоимости не превосходят стоимостей
то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости
то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла равна разности между стоимостью и псевдостоимостью в этой свободной клетке. Итак, мы приходим к следующему правилу (алгоритму) решения транспортной задачи методом потенциалов. 1. Взять любой опорный план перевозок, в котором отмечены 2. Определить для этого плана платежи
Один из платежей можно назначить произвольно, например, положить равным нулю. 3. Подсчитать псевдостоимости 4. Если бы хотя в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путем переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости). 5. После этого заново подсчитываются платежи и псевдостоимости, и, если план все еще не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план. Таблица 12.2
Понятиям «платежей» и и «псевдостоимостей» можно дать наглядную экономическую интерпретацию. Представим себе, что Продемонстрируем применение метода потенциалов для решения ТЗ на конкретном примере. Пример 1. Решить методом потенциалов ТЗ, заданную в табл. 12.2, где проставлен первый опорный план, составленный по способу северо-западного угла. Решение. Приписываем к табл 12 2 снизу добавочную строку для платежей Полагая
а из условия
Таблица 12.3
Продолжая эту процедуру, находим:
Так как не все псевдостоимости в свободных клетках табл. 12.3 удовлетворяют условию (12.17), план, приведенный в табл. 12.3, не является оптимальным Попробуем улучшить его, переводя в базисные одну из свободных клеток, для которых например, клетку (2, 1) Строим соответствующий этой клетке цикл (показан в табл. 12.3). Цена этого цикла Вычисляем для плана табл. 12.4 новые значения платежей, по-прежнему полагая Таблица 12.4
Таблица 12.5
Таблица 12.6
Таблица 12.7
Таблица 12.8
Таблица 12.9
Таблица 12.10
Таблица 12.11
Таблица 12.12
Этот плаи все еще не оптимальный. Перенося по циклу, соответствующему свободной клетке (4, 3), В табл. 12.6 уже все псевдостоимости не превосходят соответствующих стоимостей, значит, этот план оптимален Потенциалы пунктов найдены и равны соответственно:
При анализе этих значений нельзя забывать, что одно из них (в нашем случае с) назначено произвольно Пример 2. Решить методом потенциалов ТЗ, условия которой даны в табл. 12.7. Решение. Применяя способ ceвepo-западного угла, получаем вырожденный план. Вводя
Заметим, что эта стоимость такая же, как стоимость плана, показанного в табл. 12.10 при
|
1 |
Оглавление
|