Решение задачи методом потенциалов

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

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

Для транспортной задачи (ТЗ), как и для любой ЗЛП, существует двойственная к ней задача.

Исходная задача:

, j=

Двойственная задача:

План Х=(хij) транспортной задачи будет являться оптимальным, если существует система m+n чисел α _i, β _j, называемых потенциалами, удовлетворяющих условиям:

max ( α _i +β _j)*x_ij

α _i + β _j = c_ij для занятых клеток, где x_ij> 0, i=1, m

α _i + β _j ≤ c_ij для незанятых клеток, где x_ij = 0. j=1, n

Потенциалы α _i и β _j являются переменными двойственной транспортной задачи и обозначают оплату за перевозку единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу α _i + β _j = c_ij.

Введем обозначение оценки свободной клетки таблицы

∆ _ij = α _i+ β _j – c_ij.

Если среди оценок ∆ _ij нет положительных (задача поставлена на минимум), то опорный план является минимальным.

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

· Построение первого опорного плана.

· Проверка вырожденности плана. Потенциалы α _i и β _j могут быть рассчитаны только для невырожденного плана.

· Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем производимого груза по всем занятым клеткам таблицы

· Определяем потенциалы α _i и β _j. Для каждой занятой клетки таблицы записываем уравнение α _i+β _j=c_ij(i=1, m; j=1, n). Получим систему (m+n-1) уравнений с (m+n) переменными.

Так как число переменных больше числа уравнений (m+n> m+n-1), то система является неопределенной и имеет бесконечное число решений. Поэтому одному из неизвестных потенциалов α i, β j задают произвольное значение, например, для одного из столбцов (отправителей)принимают потенциал α i равный нулю. При этом целесообразно нулю приравнивать потенциал того столбца, в котором имеется загруженная клетка с наибольшим тарифом. Остальные потенциалы определяют по загруженным клеткам.

· Определяем оценки свободных клеток ∆ _ij.

Если ∆ _ij ≤ 0 (задача решается на минимум целевой функции) либо все ∆ _ij ≥ 0 (задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки ∆ _ij> 0(задача поставлена на минимум) или ∆ _i< 0 (задача поставлена на максимум), план не является оптимальным, его можно улучшить, осуществив перераспределение груза.

· Построение нового опорного плана. Из всех положительных оценок свободных клеток выбираем наибольшую (если задача построена на минимум), из отрицательных – наибольшую по отрицательной величине (если задача построена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т.е. направить груз и изменить объемы поставок, построив в так называемый цикл или контур.

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

Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки «+» и «-».

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

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

Примечания.

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

2. Если в оптимальном плане транспортной задачи оценка свободной клетки равна нулю (∆ _ij=0), то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь такое же значение целевой функции.

3. Значение целевой функции на каждой итерации можно рассчитать следующим образом:

F(X_k) = F(X_k_-1) - γ ∆ _ij (задача поставлена на минимум)

F(X_k) = F(X_k_-1) + γ ∆ _ij (задача поставлена на максимум)

Где γ – величина перемещаемого по циклу груза;

∆ ij - оценка свободной клетки, в которую направляется груз при переходе к новому плану;

F(X_k) – значений целевой функции на k-й итерации;

F(X_k_-1) – значение целевой функции на предыдущей итерации.

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


30⁴
40³	120¹	30²
		120³	130⁷

План не вырожденный; F(x)=1690

Проверяем полученный план на оптимальность и находим оценки свободных клеток (согласно алгоритму)

Составляем уравнения для определения потенциалов (для каждой загруженной клетки).

α ₁+ β ₁ =4; α ₂+ β ₁ =3; α ₂+ β ₂ =1; α ₂+ β ₃ =2; α ₃+ β ₃ =3; α ₃+ β ₄ =7.

Полагая, что α ₃=0, то получаем: β ₄ =7; β ₃ =3; α ₂=-1; β ₂ =2; β ₁ =4; α ₁=0.

Получаем следующую таблицу.

b_j a_i					α _i
	30⁴				α ₁=0
	40³	120¹	30²		α ₂=-1
			120³	130⁷	α ₃=0
β _j	β ₁ =4	β ₂ =2	β ₃ =3	β ₄ =7

Далее вычисляем оценки свободных клеток и выполнения условия ∆ _ij< α _i + β _j – c_ij

Для клетки (1, 2): 0 + 2 - 7 = -5

Для клетки (1, 3): 0 + 3 - 2 = 1

Для клетки (1, 4): 0 + 7 - 3 = 4

Для клетки (2, 4): -1 + 7 - 4 = 2

Для клетки (1, 2): 0 + 4 - 5 = -1

Для клетки (1, 2): 0 + 2 - 6 = -4

Наличие положительных оценок свидетельствует о том, что план не оптимален и его можно улучшить.

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

b_j a_i			α i
	30	+4 3
			-1

β j

Нарисуем этот цикл. Для каждой клетки указаны её индексы и объем поставок

(1.1) (1.4)

(2.3)

(3.4)

(2.1)

(3.3)

Стартовой клетке (1, 4) припишем знак «+». Двигаясь по циклу, чередуем знаки. Среди поставок со знаком «-» (это клетки (1, 1), (2, 3), (3, 4)) найдем минимальную: min(30, 30, 130) =30. После этого в клетках со знаком «-» уменьшим поставки на этот минимум, а в клетках со знаком «+» увеличим на этот минимум. Клетка (1, 4) становится отмеченной (загруженной).

Если получена одна клетка с нулевой поставкой, то она становится пустой. У нас таких клеток две – (1, 1), (2, 3). Поэтому пустой объявим только одну из них с наибольшим тарифом– клетку (1, 1). В клетку (2, 3) будет сделана нулевая поставка, и она останется отмеченной. Это делается для выполнения соотношения: число отмеченных клеток = число столбцов + число строк – 1. Получаем новый план поставок.

b_j a_i		Α _i
		-4
	+2 4	-1

Β _j

Для нового плана находим оценки строк и столбцов. Затем получим матрицу оценок клеток:.

План является неоптимальным, так как оценка клетки (2, 4) больше нуля. Строим для нее цикл пересчета: (2, 4) – (3, 4) – (3, 3) – (2, 3) – (2, 4) и получаем новый план:

B_j A_i		a_i
		-4
	70	-3
	+1 5
b_j

Для нового плана находим оценки строк и столбцов. Затем получаем матрицу оценок клеток:.

План является неоптимальным, так как оценка клетки (3, 1) больше нуля. Строим для нее цикл пересчета: (3, 1) - (2, 1) - (2, 4) - (3, 4) - (3, 1).

(2.1)

(2.4)

(3.4)

(3.1)

min (70, 100) = 70. В клетках с «+» поставки увеличиваются на 70, а в клетках с «-» поставки уменьшаются на 70. Клетка (2, 1) становится пустой. Новый план поставок:

B_j A_i					a_i
					-4
					-3

b_j

Находим оценки срок и столбцов. Получаем матрицу оценок:

Матрица оценок не содержит положительных чисел. Получен оптимальный план поставок. Суммарные затраты на перевозку груза равны: 3*30+1*120+4*70+5*70+3*150+7*30=1500.

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

Поставщик А1 должен поставить 30 единиц груза потребителю В4. Поставщик А2 должен поставить 120 единиц груза потребителю В2 и 70 единиц груза

потребителю В₄.. Поставщик А₃ должен поставить 70 единиц груза потребителю В₁, 150 единиц груза потребителю В₃, 30 единиц груза потребителю В₄.

⇐ Предыдущая 8 9 10 11 121314 15 16 17 Следующая ⇒

Последнее изменение этой страницы: 2017-04-13; Просмотров: 615; Нарушение авторского права страницы