Проверка найденного решения на оптимальность

Метод потенциалов

Определение 1: Если при решении транспортной задачи число заполненных клеток транспортной таблицы равно m + n – 1, где m – где число производителей, а n – число потребителей, то план перевозок невырожденный.

Определение 2: Если число заполненных клеток транспортной таблицы меньше  m + n – 1, где m – где число производителей, а n – число потребителей, то план перевозок вырожденный.

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

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

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

Рассмотрим получение оптимального плана перевозок с использованием метода потенциалов.

1 шаг: Получение начального плана перевозок. (методом «минимального элемента» или другим методом).

2 шаг: Проверка плана на невырожденность

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

3 шаг: Проверка плана на оптимальность

3.1  Определение потенциалов производителей и потребителей. Составляют систему уравнений для заполненных клеток транспортной таблицы: U_i +V_J = C_ij,

где i, j – номера строк и столбцов, на пересечении которых стоят заполненные клетки, U_i потенциал i – го поставщика V_j – потенциал j –го потребителя C_ij - тариф на перевозку из пункта i в пункт j. Для решения данной системы одно из неизвестных выбирают произвольно. Обычно полагают U_i = 0. Решая систему уравнений, находят значения потенциалов U_i и V_j, i =1,m, j = 1,n.

3.2. Определение суммы потенциалов (косвенных тарифов) для свободных клеток: C1_qp = U_q + V_p, где q p – номера строк и столбцов, на пересечении которых стоит свободная клетка, U_q  - потенциал q-го поставщика, V_p- потенциал p-го потребителя, C1_qp – косвенные тарифы.

3.3 Проверка на оптимальность.

Для каждой свободной клетки таблицы составляется разность между C1_qp и C_qp (косвенным и реальным тарифами) . Если все , то полученный план оптимален. Если хотя бы для одной свободной клетки , то план может быть улучшен.

4 шаг. Улучшение плана

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

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

4.2 Выбор переменной выводимой из списка базисных переменных.

Заполнение клетки, выбранной на шаге 4.1, происходит следующим образом. Строят цикл, начинающийся и оканчивающийся в выбранной свободной клетке, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков. При этом в каждой клетке таблицы, являющейся вершиной цикла, соединяют обязательно горизонтальный и вертикальный отрезки. В свободной клетке условно ставят знак «+», а в остальных вершинах цикла, чередуясь ставят «-» и «+».Затем происходит перераспределение продукции по циклу. Для этого выбирают клетку со знаком «-», которой соответствует наименьшее число единиц продукции. Это значение прибавляют к значениям, стоящим в клетках со знаком «+» и отнимают от значений, стоящих со знаком «-». При таком распределении общий баланс не изменяется. Свободная клетка заполняется. А клетка со знаком «-», которой соответствует наименьшее количество продукции, становится свободной.

Для нового плана повторяют все действия. (т.е переходят к шагу 2).

Пример 1.  

Найти оптимальный план перевозок для транспортной задачи.

1) Получим начальный план решения методом минимального элемента.

№	1	2	3	4	Предложение
1	^7	^8	160 – ^1	+^2	160
2	120  ^4	^5	^9	20 ^8	140
3	^9	50 ^2	30 +  ^3	90 –^6	170
Спрос	120	50	190	110

2) Проверим число заполненных клеток m+n-1= 4+3-1=6, т.е. данный план невырожденный. Определим потенциалы производителей и потребителей, составив уравнения  U_i +V_J = C_ij, для заполненных клеток и занесем их в таблицу:

2.1 U₁+V₃=1,                   U₁=0,              V₁=0,

U₂+V₁=4,                         U₂=4,              V₂=0,

U₂+V₄=8,                         U₃=2.              V₃=1,

U₃+V₂=2,                                                     V₄=4.

U₃+V₃=3,

U₃+V₄=6.

2.2 Составим разности для свободных клеток:

Получена положительная разность . Заполним клетку первой строки и четвертого столбца. Строим цикл, начинающийся и заканчивающийся в этой клетке. Вершинами цикла являются клетки: (3,4), (3,3), (1,3). В клетке (1,4) ставим «+», в клетке (3,4) – «-», в клетке (3,3) «+», в клетке (1,3) ставим «-». Перераспределяем продукцию по циклу. Минимальное значение для клеток со знаком «-» находится в клетке (3,4) х₃₄=90. Отнимаем 90 от значений, стоящих в клетках со знаком «-», и прибавляем к значениям, стоящим в клетках со знаком «+». Получаем новый план перевозок, представленный в следующей транспортной таблице:

№	1	2	3	4	Предложение
1	^7	^8	70 ^– ^1	90   ^+ ^2	160
2	120^4	+^5	^9	20 – ^8	140
3	^9	50 – ^2	120 + ^3	^6	170
Спрос	120	50	190	110

 

3) Проверим число заполненных клеток: m+n-1=4+3-1= 6 - план невырожденный.

4) Проверим на оптимальность.

4.1 U₁+V₃=1,                   U₁=0,             V₁=-2,

U₁+V₄=2,                         U₂=6,              V₂=0,

U₂+V₁=4,                         U₃=2.              V₃=1,

U₂+V₄=8,                                                     V₄=2.

U₃+V₂=2,

U₃+V₃=3.

4.2 Составим разности для свободных клеток:

4.3 Получена положительная разность  . Заполним клетку (2,2). Цикл будет содержать клетки (2,2), (3,2), (3,3), (1,3), (1,4), (2,4), (2,2).       

Для того, чтобы не загромождать таблицу цикл можно вынести отдельно:

		70			90
			–	+
				–
	+				20
	–	+
50			120

Минимальное значение х₂₄=20 для клеток со знаком «-». Перераспределив продукцию по циклу, получим новый план перевозок, представленный в таблице:

№	1	2	3	4	Предложение
1	^7	^8	50^1	110^2	160
2	120^4	20^5	^9	^8	140
3	^9	30^2	140^3	^6	170
Спрос	120	50	190	110

 

5) Полученный план невырожденный. Проверим на оптимальность.

5.1 U₁+V₃=1,                   U₁=0,             V₁=-1,

U₁+V₄=2,                     U₂=5,              V₂=0,

U₂+V₁=4,                    U₃=2.              V₃=1,

U₂+V₂=2,                                                V₄=2.

U₃+V₂=2,

U₃+V₃=3.

5.2 Составим разности для свободных клеток:

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

Стоимость перевозки: L_min=50·1+110·2+120·4+20·5+30·2+140·3=1330 у.е.

Пример 2.  

Три торговых склада могут поставлять некоторое изделие в количестве 9,4 и 8 тонн. Величины спроса трех магазинов розничной торговли на это изделие равны 3, 5 и 6 т.

Какова минимальная стоимость транспортировки от поставщиков к потребителям, если матрица стоимостей имеет вид ?

Решение: Запасы складов потребности магазинов:  - задача открытая. Введем фиктивный магазин со спросом  и тарифом 20 у.е. и решим задачу методом минимального элемента.

№	1	2	3	4ф	Предложение	ui
1	^10	1^20	6^5	2^20	9	0
2	^2	4^10	^8	^20	4	-10
3	3^1	^20	^7	5^20	8	0
Спрос	3	5	6	7
vj	1	20	5	20

Оптимизируем полученное решение:

1) Найдем потенциалы заполненных клеток. (см. таблицу);

2) Оценим свободные клетки: .

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

.

Минимальная стоимость транспортных расходов L_опт=93 у.е.