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

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

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

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

3. Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений

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

при > 0, если известен потенциал , и

при > 0, если известен потенциал .

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

5. Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка . Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину θ=. Клетка со знаком «-», в которой достигается , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным т+ п —1. Возвращаются к пункту 3.

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

bj ai

Решение. 1. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и запросы потребителей:

= 100 + 200 + 300 = 600, = 100 + 100 + 300 + 300 = 800.

Задача с неправильным балансом. Вводим четвертого, фиктивного поставщика с запасами а ₄ = 800 — 600 = 200 и нулевыми стоимостями перевозки единиц груза.

2. Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей С:

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

bj ai

Полученное решение Х ₁ имеет т + п — 1=4 + 4— 1 = 7 базисных переменных. Опорное решение является вырожденным, так как одна из его координат равна нулю. Вычислим значение целевой функции на этом опорном решении F (X ₁)=100·1+0·2+100·3+100·4+200·7+100·12+200·0=3400.

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

Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть и ₂ = 0. Остальные потенциалы находятся однозначно:

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

v ₁=2 v ₂=3 v ₃=4 v ₄=9

	bj ai
u 1=-1
u 2=0
u 3=3
u 4=-9		-	-	-

4. Проверяем опорное решение Х ₁ на оптимальность. С этой целью вычисляем оценки для всех незаполненных клеток таблицы (для всех занятых клеток =0):

Положительные оценки записываем в левые нижние углы соответствующих клеток таблицы, вместо отрицательных ставим знак «—». Начальное опорное решение не является оптимальным, так как имеются положительные оценки.

5. Переходим к новому опорному решению. Находим клетку таблицы, которой соответствует наибольшая положительная оценка: =max{7,3,2,2}=7 для клетки (1,4). Для этой клетки строим цикл. Ставим в нее знак «+», присоединяем ее к занятым клеткам и применяем метод вычеркивания. После проведения вычеркиваний в таблице остаются только образующие цикл клетки. Цикл изображен в таблице. В угловых точках цикла расставляем поочередно знаки «+» и «-», начиная с «+» в клетке (1, 4). В клетки, отмеченные знаком «+», прибавляется груз θ, а из клеток, отмеченных знаком «-», вычитается такой же по величине груз. Определяем величину груза θ, перераспределяемого по циклу. Она равна значению наименьшей из перевозок в клетках цикла, отмеченных знаком «-», θ={100,100,100}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем второе опорное решение Х ₂:

v ₁=2 v ₂=3 v ₃=4 v ₄=9

	bj ai
u 1=-1
u 2=0			100 -	-	-
u 3=3					-
u 4=-9

В данном случае минимум перевозок в клетках, отмеченных знаком «-», достигался сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно т+п —1=7, в клетки с номерами (1, 1) и (2, 3) поставлены нулевые базисные перевозки. Следует освобождать клетку с большей стоимостью перевозки, т.е. клетку (3, 4). Вычисляем значение целевой функции на втором опорном решении: F (X)=0·1+100·1+100·2+100·3+0·4+300·7+200·0=2700.

6. Проверяем второе опорное решение Х ₂ на оптимальность. Находим потенциалы и оценки. Решение не является оптимальным, так как имеются положительные оценки Δ₃₁=2, Δ₃₂=2, Δ₄₂=1 и Δ₄₃=2. Наибольшая из них равна 2 одновременно для трех клеток (3, 1), (3, 2) и (4, 3). В одну из них, пусть в клетку (3, 2), ставим знак «+». Для этой клетки строим цикл и находим величину груза по циклу: θ={100,300}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем третье опорное решение Х ₃.

v ₁=1 v ₂=0 v ₃=3 v ₄=1

	bj ai
u 1=0			-
u 2=1	200		-		-
u 3=4					-
u 4=-1			-

Вычисляем значение целевой функции на третьем опорном решении:

F(X ₃ )= 0·1 + 100·1 + 100·2 + 100·4 + 100·4 + 200·7 + 200·0 =2500.

7. Решение не является оптимальным, так как имеются положительные оценки Δ₃₁=2 и Δ₄₃=2. Ставим знак «+» пусть в клетку (3, 1), Для этой клетки строим цикл и находим величину груза для перераспределения по циклу: θ={100,200}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем четвертое опорное решение Х ₄:

v ₁=1 v ₂=0 v ₃=3 v ₄=1

	bj ai
u 1=-2	100
u 2=-3			-		-
u 3=0					-
u 4=-3

Вычисляем значение целевой функции на четвертом опорном решении: F (Х ₄) = 0·l + 100·1 +200·4+ 100·3 + 100·4+ 100·7 + 200·0 =2300.

8. Проверяем решение Х ₄ на оптимальность. Находим потенциалы и оценки. Они приведены в таблице. Положительными являются оценки Δ₁₃=2, Δ₄₂=1 и Δ₄₃=4. Для клетки (4, 3), которой соответствует наибольшая оценка, строим цикл и находим величину груза для перераспределения по циклу: θ={200,0,100}=0. Осуществляем сдвиг по циклу на величину θ=0. Получаем пятое опорное решение Х ₅:

v ₁=3 v ₂=4 v ₃=7 v ₄=3

	bj ai
u 1=-6		-	-	-
u 2=-3		-	-		-
u 3=0					-
u 4=-7		-	-	-

Решение Х ₅ является оптимальным, так как все оценки отрицательные. Значение целевой функции F (X ₅) = F (X ₄) = 2300.

Ответ: min F (Х)=2300 при Х ^*=.

Дата добавления: 2014-01-04