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

Для определения номера переменной, вводимой в базис на очередной итерации необходимо:

- рассчитать новые значения коэффициентов целевой функции при небазисных переменных;

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

В методе потенциалов, который впервые был предложен Канторовичем и Габуриным, вычисление новых значений коэффициентов целевой функции основано на соотношениях двойственности. Определим вид этих соотношений для транспортной задачи.

Для этого запишем транспортную задачу в аналитической форме:

Представим двойственную переменную в виде для первых n ограничений прямой задачи и для последних m ограничений. Тогда целевая функция двойственной задачи задается соотношением: _,а ограничения - соотношениями: .

С учетом последнего неравенства соотношения двойственности преобразуются к виду

где - исходные коэффициенты целевой функции прямой задачи. Из предыдущего известно, что новые коэффициенты при всех базисных переменных, количество которых равно n+m-1, должны быть равны нулю. Отсюда получим систему из уравнений

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

Общее количество неизвестных потенциалов равно n+m. Для того, чтобы решить систему из n+m-1 уравнений, с n+m неизвестными, одной из неизвестных необходимо задать произвольное значение. Обычно полагают .

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

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

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

Тогда , что и требовалось доказать.

Так как принято значение , то можно найти Если известен потенциал , то можно найти .

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

Определим методом потенциалов номер переменной, вводимой в базис, для задачи из примера 1. В качестве опорного плана, возьмем план, полученный способом северо-западного угла, табл. Рассчитаем потенциалы. Получим систему линейных уравнений: Зададим . Тогда из этой системы получим: .

Оценки для небазисных переменных рассчитаем по формуле:

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

№ склада	№ города

1
2	- 9	- 10

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

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

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

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

Анализ таблицы показывает, что из базиса должна быть выведена переменная . Тогда значение переменной оказывается равным 2, а переменные, находящиеся на изломах цикла, корректируются, в результате чего новый базис оказывается равным (4, 6, 0, 2, 0, 0, 7, 1).

№ склада	№ города

			- 1
	- 8	- 9

Значение целевой функции на новом базисе оказывается равным 225, что на 24 единицы меньше чем при начальном базисе.

Оптимальность нового базисного решения проверяется с помощью уже рассмотренного метода потенциалов. Составим систему уравнений:

Присвоим потенциалу значение равное нулю. Тогда остальные потенциалы будут равны соответственно:

Теперь можно рассчитать и новые значения коэффициентов при небазисных переменных:

Отрицательные значения всех при небазисных переменных свидетельствует об оптимальности полученного плана.

Таким образом, оптимальный по критерию стоимости план рассредоточения кораблей рекомендует: из первого пункта базирования направить четыре корабля в первую точку рассредоточения, шесть – во вторую и два в четвертую, из второго пункта базирования - семь кораблей в третью точку рассредоточения и один – в четвертую. При таком плане стоимость рассредоточения составит 225 условных единиц.

⇐ Предыдущая 1 2 3 456 7 Следующая ⇒