Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 167 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

Составители: 

Рубрика: 

167
4.2. Метод потенциалов
Основной алгоритм распределительного метода, рассмотренный нами в 4.1
является далеко не лучшим методом решения транспортных задач, так как на каждой
итерации для проверки опорного плана на оптимальность приходилось строить [тп—
(т+п—1)] циклов пересчета, что при больших размерах матрицы оказывается очень
громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации
надо строить 81 цикл, а по матрице 20x20—361 цикл.
Оценки (или характеристики) свободных клеток можно вычислить и иным, менее трудоемким путем, без
составления циклов пересчета. Для этого существуют два способа, отличающихся друг от друга
несущественной деталью.
В 1940 г. советским ученым Л. В. Канторовичем был разработан метод решения
транспортной задачи, и в первой публикации (1942 г.) содержались основные идеи метода.
Впоследствии (в 1949 г.) в совместной статье Л. В. Канторовичем и.М. К. Гаву-риным был
изложен сам метод (в сетевой постановке), названный методом потенциалов.
Позднее (в 1951 г.) американским ученым Дж. Б. Данцигом был разработан
аналогичный метод, получивший название модифицированного распределительного
метода, который в иностранной и некоторой советской литературе сокращенно именуют
методом МОДИ.
Поскольку разница между этими способами чрезвычайно незначительна, в
дальнейшем не будем их разграничивать и станем именовать общим названием—
методом потенциалов.
В самом начале рассмотрения метода потенциалов следует обратить внимание
читателя на то, что этот метод имеет не только различия с распределительным методом, а
в некоторой части схож с ним (недаром Дж. Б. Данциг назвал его модифицированным
распределительным методом). Метод потенциалов и распределительный метод похожи
между собой тем, что исходный опорный план и переход от не оптимального плана к
лучшему как в одном, так и в другом методе осуществляются с помощью одинаковых
приемов. Разница этих двух методов заключается в методике проверки опорного плана
задачи на оптимальность. Так, в распределительном методе она производится с помощью
оценок свободных клеток, вычисленных по циклам пересчета. В методе потенциалов, как
это будет видно из дальнейшего изложения, — с помощью характеристик свободных
клеток, довольно легко вычисляемых посредством специальных чисел, называемых
потенциалами.
Сущность потенциалов и способ вычисления их в ряде литературных источников
рассматриваются на некоторых логических рассуждениях. Мы же здесь изберем иной
путь. Выведем потенциалы и зависимость их посредством использования основ теории
двойственности, которые были изложены в 3.3.
Для этого составим условие двойственной задачи по отношению прямой
транспортной задачи (4.1)—(4.4), в которой требовалось отыскать не отрицательные
значения переменных x
ij
, минимизирующие целевую функцию
∑∑
= =
=
m
i
n
j
ijij
xcF
1 1
(4.13)
при условиях:
∑
=
==
n
j
iij
miax
1
;,...,2,1
(4.14)

Страницы