Дельта-метод

Рассмотрим алгоритм дельта-метода в общем виде:

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

нулевым приращением

не рассматриваются.

1. Заполнение проводится по столбцам, содержащим одно нулевое приращение, в клетки, содержащие его, записываются потребности, без учета величины запасов на складах. Затем уже с учетом произведенных постановок просматриваем столбцы, содержащие два нулевых и более приращений, и заполняем их, до тех пор, пока все объемы потребностей не будут закреплены за поставщиками.
2. Подсчитываются для строк разницы между фактическими запасами и полученными для опорного “фиктивного” плана. Критерием оптимальности плана является нулевая разница по всем запасам и “фиктивным” планом. В случае положительной разницы строки называют недостаточными, в случае отрицательной разницы - избыточными, нулевыми строки называют в случае 0-разницы.
3. Отмечаются столбцы, с занятыми клетками в избыточных строках. Для каждой недостаточной и нулевой строки просматриваются приращения , стоящие в отмеченных столбцах, выбирается наименьшее в строке. Эти значения показывают, какое приращение стоимости будет получено на данном шаге, если единицу потребности перезакрепить от одного поставщика к другим (избыточные и недостаточные строки). Сравнивая со значениями нулевой строки, получим два случая:

а) для каждой нулевой строки минимальное значение меньше либо равно по отношению к приращениям нулевой строки.

б) минимальное приращение больше приращений нулевой строки;

В случае а) производится непосредственное перераспределение потребности из избыточной строки в недостаточную в клетку отмеченного столбца, которой соответствует минимальное

В случае б) составляются цепочки.

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

Составляем для каждой цепочки алгебраическую сумму приращения, считая их отрицательными, если они стоят в клетке, отмеченной знаком “-”, и положительными, если клетка отмечена знаком “+”. Если сумма больше минимального , то производится непосредственное распределение, если меньше, то распределение производится по цепочке.

5. Исключаем из рассмотрения отмеченные столбцы. Если занятая клетка избыточной строка стала незанятой или избыточной, то начинаем п.4. В противном случае продолжаем процесс до тех пор, пока все строки не превратятся в нулевые.

4.5. Алгоритм улучшения плана

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

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

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

Введение в базис вектора означает, что мы должны запланировать какую-то перевозку из третьего склада в первый пункт потребления. Пусть величина этой перевозки равна q. Поставим ее в клетку, соответствующую i =3, j =1. Тогда мы получим следующий план перевозок:

	3.1
	3.9	4.2
q		2.8	6.3

Но теперь у нас нарушился баланс запасов и потребностей - получилось, что из третьего склада вывозится , а в первый пункт потребления поступает .

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

Теперь для восстановления баланса запасов и потребностей можно поступить очень просто: при движении по столбцу от имеющихся компонентов плана надо отнимать q, а при движении по строке - наоборот, прибавлять q. В результате получится следующий план перевозок, уже сохраняющий баланс запасов и потребностей:

2-q	3.1+q
	3.9-q	4.2+q
q		2.8-q	6.3

С балансом всё в порядке, но теперь у нас стало компонент плана, а должно быть . Поэтому надо выбрать q так, чтобы одна из бывших компонент обратилась в нуль, но все остальные компоненты остались положительными. Легко догадаться, что для этого q надо взять равным минимальному из тех чисел, из которых q вычитается. В нашем случае q вычитается из чисел 2; 3.9; 2.8. Минимальное из них есть 2 и поэтому надо взять q =2.

В результате получится новый опорный план следующего вида

	5.1
	1.9	6.2
		0.8	6.3

в котором снова будет положенные ему компонент.

Вычисляя транспортные расходы для этого плана, мы получим , откуда видно, что по сравнению с исходным планом транспортные расходы уменьшились на 2 единицы.

Опишем этот процесс в общем виде.

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

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

- такой цикл всегда может быть построен;

- такой цикл единственный.

Итак, пусть этот цикл имеет вид

Установим новый план перевозок вида

Все остальные компоненты плана перевозок, не входящие в цикл, остаются неизменными.

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

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

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

Для нового плана перевозок мы имеем

В выражении, стоящем в квадратных скобках, большинство слагаемых сокращается и окончательно получаем

так как мы вводим перевозку, для которой .

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

Закончим наш учебный пример. Одну итерацию мы уже проделали.

Вторая итерация

Этап 1

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

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

			7
-3	-1
-1

Затем определяются потенциалы. Обычно это легко сделать в уме, двигаясь по строкам и столбцам.

Затем оставшиеся клетки заполняются суммами соответствующих потенциалов, то есть величинами .

Наконец, производится сравнение получившейся таблицы с таблицей величин и определяются те клетки, где .

Этап 2

Из тех пар индексов, где , находится та пара, где разность максимальна (в нашем случае это пара i =1, j =3). Строится цикл, определяется q и строится новый опорный план.

В нашем случае эти преобразования имеют следующий вид:

	5.1-q	q					5.1
	1.9+q	6.2-q		Þ			1.1
		0.8	6.3				0.8	6.3

В нашем случае , так что новый опорный план нарисован в таблице справа. Значение транспортных расходов уменьшилось на величину

,

то есть на 15.3 единицы.

Следующая итерация дается без пояснений.

Третья итерация
Этап 1

	-1
	-1
	-1

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

Для этого плана перевозок значение транспортных расходов

.

По сравнению с исходным планом, полученным методом северо-западного угла, транспортные расходы уменьшились на 17.3 единицы, то есть на 21%.

Теперь мы в состоянии доказать одну интересную теорему

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

Доказательство

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

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

Задачи

Решить следующие транспортные задачи методом потенциалов.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

6. Снятие вырожденности

6.1. Эпсилон-прием

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

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

с некоторым e >0. Можно взять e конкретным, но достаточно малым числом, а можно просто оставить в алгебраическом виде как букву. Затем транспортная задача решается обычным путем, а в ответе просто полагается e =0, (или полученный результат округляется, если e было взято конкретным малым числом).

Проиллюстрируем этот прием на конкретном примере.

Пример

Пусть матрица стоимостей перевозок имеет вид:

Запасы складов равны . Потребности пунктов потребления равны .

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

Чтобы снять намечающееся вырождение, будем решать задачу с теми же самыми , но с

Дальнейшее дается с минимальными пояснениями.

Построение исходного опорного плана.

Используя метод северо-западного угла, получим следующий исходный опорный план

	2+e
	4-e	4+2e
		4-2e	6+3e

Для этого плана значение функции потерь равно

Первая итерация

Этап 1
Определение потенциалов и проверка оптимальности плана.

	2	3

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

Этап 2

Строим цикл, находим q и переходим к новому опорному плану.

4-q	2+e +q				2e	6-e
	4-e -q	4+2e +q				e
q		4-2e -q	6+3e		4-2e			6+3e

В данном случае . Обратите внимание на то, что если бы было e =0, то построенный план имел бы всего 4 положительных компоненты, то есть он был бы вырожденным.

Вторая итерация

Этап 1

Находим потенциалы и проверяем оптимальность плана.

				2

Полученный план снова не является оптимальным. Условие нарушается на элементе с i =2, j =4.

Цикл нарисован заранее.

Этап 2

2e -q	6-e +q				e
	e -q		q					e
4-2e +q			6+3e -q		4-e			6+2e

В данном случае . Опять-таки, если бы было e =0, то план был бы вырожденным.

Третья итерация

Этап 1

Нахождение потенциалов и проверка на оптимальность.

Соответствующая таблица приведена ниже.

В данном случае для всех клеток таблицы выполнено условие , так что построенный план является оптимальным.

Чтобы получить решение исходной задачи, надо положить e =0. Тогда мы получим:

e
			e
4-e			6+2e

Найденный оптимальный план имеет всего 4 компоненты, то есть он является вырожденным. Для него значение транспортных потерь равно

то есть значение транспортных издержек уменьшилось по сравнению с планом, построенным по методу северо-западного угла, на 4 единицы. или на 9.5%.

Задачи

Снять вырождение и найти оптимальный план методом потенциалов.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

6.2. 0-подстановка

Еще один прием для снятия вырожденности – 0-подстановка.

Рассмотрим задачу

План, составленный методом северо-западного угла имеет вид:

План является вырожденным.

Рассмотрим таблицу, в которой указаны цены на перевозки, за исключением базисных компонент.

Удалим из рассмотрения клетки, при постановке в которые некоторых единиц возникает цикл.

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

Выберем минимальную стоимость и поставим нулевую перевозку .

Теперь план приобретет вид.

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

План примет вид