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

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

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 при Х ^*= .

Транспортная задача с ограничениями на пропускную способность

Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов: 1) х_lk ≥ а; 2) х_lk ≤ b, где а и b — постоянные величины.

1. Если х_lk ≥ а, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l -го поставщика и запросы k -гопотребителя на величину а (зарезервировать перевозку х_lk = а). После решения задачи в оптимальном решении следует увеличить объем перевозки х_lk на величину а.

2. Если х_lk ≤ b, то необходимо вместо k -гопотребителя с запросами b_k, ввести двух других потребителей. Один из них с номером k должен иметь запросы b'_k = b, а другой с номером п + 1 - запросы b_{n+ 1} = b_k- b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости с_{l ( n +1)}, которая принимается равной сколь угодно большому числу М (М>> 1). После получения оптимального решения величины грузов, перевозимых к (п +1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как с_{l ( n +1)}= М -самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l,n +1) останется пустой, х_{l ( n +1)} = 0 и объем перевозки х_lk не превзойдет b.

Пример. Решить транспортную задачу, исходные данные которой приведены в таблице, при дополнительных условиях: объем перевозки груза от 1-го поставщика 2-му потребителю должен быть не менее 100 единиц (х ₁₂ ≥100), а от 3-го 1-му не более 200 единиц (х ₃₁ ≤ 200).

bj ai

Решение. Для того чтобы в оптимальном решении объем перевозки х ₁₂был не менее 100 единиц, при решении задачи будем предполагать, что запасы 1-го поставщика а ₁и запросы 2-го потребителя b ₂меньше фактических на 100 единиц. После получения оптимального решения объем перевозки х ₁₂увеличим на 100 единиц.

Для того чтобы удовлетворить требованию х ₃₁≤ 200, вместо 1-го потребителя введем двух других. Один из них под прежним первым номером имеет запросы b ₁ = 200 единиц и прежние стоимости перевозок единиц груза. Другому присвоим четвертый номер. Его запросы равны b ₄ = 500 — 200 = 300 единиц и стоимости перевозок единиц груза те же, что и у 1-го потребителя, за исключением с ₃₄, которую примем равной сколь угодно большому числу М, т.е. с ₃₄= М. После нахождения оптимального решения задачи объемы перевозок для 4-го потребителя необходимо прибавить к соответствующим объемам перевозок для 1-го потребителя.

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

bj ai
				М

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

а ₁ + а ₂ + а ₃ = 100 + 300 + 500 = 900;

b ₁ + b ₂ + b ₃ + b ₄ = 200 + 300 + 300 + 300 = 1100.

Задача с неправильным балансом. Вводим фиктивного поставщика с запасами а ₄= 1100 - 900 = 200.

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

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

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

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

Полученное решение X ₁имеет т + n — 1=4 + 4— 1 = 7 базисных переменных. Вычисляем значение целевой функции на этом опорном решении:

F (X ₁) = 100·1+100·2+200·2+300·7+200·8+100·0+100·0=4400.

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

Система состоит, из семи уравнений и имеет восемь переменных. Так как число неизвестных на единицу больше числа уравнений, то одному из потенциалов можно задать значение произвольно: пусть и ₁=0. Остальные потенциалы однозначно находятся из системы уравнений:

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

Опорное решение неоптимальное, так как имеется положительная оценка Δ₃₁ = 5 для клетки (3, 1). Отмечаем эту клетку знаком «+». Находим цикл для улучшения опорного решения. Определяем величину груза для перераспределения по циклу θ= {100, 200, 100} = 100. Осуществляем сдвиг по циклу на величину θ=100. Получаем второе опорное решение Х ₂.

v ₁=1 v ₂=5 v ₃=6 v ₄=1

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

В таблице также записаны потенциалы и оценки для свободных клеток. Решение Х ₂оптимальное, так как все оценки неположительные. Запишем оптимальное решение исходной задачи. Для этого увеличим объем перевозки х ₁₂ на 100 единиц и объединим объемы перевозок 4-го потребителя, с объемами перевозок 1-го потребителя.

Получим Х ^*= .

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

F (X*)=100·1+100·5+300·2+100·3+300·7+100·8=4400.

Ответ: min F (X) = 4400 при X* = .

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

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

Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется т поставщиков с запасами однородного груза в количестве а ₁, а ₂, …, а_т и п потребителей, которым этот груз должен быть доставлен в объеме b ₁, b ₂, ..., b_n. Известно t_ij, i = 1, 2,..., m, j = 1, 2,..., n — время, за которое груз доставляется от каждого i -го поставщика каждому j -му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех грузов является минимальным.

Составим математическую модель этой задачи. Обозначим х_ij — объем перевозимого груза от i -го поставщика j -му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи. Пусть X = (x_ij), i = 1, 2,..., т, j = 1, 2,..., п — некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т (Х)наибольшее значение элементов матрицы Т= (t_ij), i = 1,2,..., m, j = 1, 2,..., п,соответствующих клеткам таблицы, занятым опорным решением: Т (Х)= . Таким образом, за время Т (Х)план перевозок будет выполнен полностью. Математическая модель имеет вид

Т (Х)= → min,

, i =1,2,..., т,

, j= 1, 2,..., п.

х_ij ≥ 0, i =1,2,..., т, j= 1, 2,..., п.

Задача решается в следующем порядке. Находится начальное опорное решение Х _1.Определяется значение целевой функции Т (Х ₁) = = . Все свободные клетки, которым соответствуют значения t_ij > Т (Х ₁),исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l₁, k ₁),в которой t_ij достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l₁, k ₁), расставляются поочередно знаки «—» и «+» и осуществляется сдвиг на величину θ= { х_ij }. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х ₂, на котором значение целевой функции меньше, чем на Х ₁.Далее снова пытаются разгрузить клетку, соответствующую Т (Х ₂) = = = . Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.

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

bj ai
		6
	2
	15

Решение. Составим начальное опорное решение Х ₁по методу северо-западного угла (см. табл.). Базисные нули не записываем. Максимум целевой функции Т (Х ₁) = {10, 8, 5, 12, 4} = 12 достигается в клетке (3, 4). Перечеркнем клетку (4, 1), в которой время доставки груза t ₄₁= 15 больше Т (Х ₁) = 12.

Для улучшения решения разгрузим клетку (3, 4) с помощью цикла (3, 4), (2, 4), (2, 2), (3, 2). Означим цикл, найдем θ= {10, 30} = 10. Осуществив сдвиг по циклу, получим второе опорное решение Х ₂:

bj ai	20

Максимум целевой функции на этом опорном решении Т (Х ₂) = {10,8,4,5,4}=10 достигается в клетке (1, 1). Перечеркнем клетку (3, 4), так как время t ₃₄=12 больше, чем Т (Х ₂)=10. Разгрузим клетку (1, 1) с помощью цикла (1, 1), (1, 2), (2, 2), (2, 1). Означим цикл, найдем θ= {20,20}=20. Осуществив сдвиг по циклу, получим третье опорное решение Х ₃. Максимум целевой функции на этом опорном решении Т (Х ₃) = {6,5,4,4,5,4}=6 и достигается в клетке (1, 2). Перечеркнем клетки (1,1), (2,2), (2,3) и (4,3): в них время t ₁₁ = 10, t ₂₂ = 8, t ₂₃=7 и t ₄₃=9 больше, чем Т (Х ₃)=6. Разгрузим клетку (1, 2) с помощью цикла (1, 2), (1, 3), (3, 3), (3, 2). Означим цикл, найдем θ= {20, 20}=20.

bj ai

Осуществив сдвиг по циклу, получим четвёртое опорное решение Х ₄. Максимум целевой функции на этом опорном решении Т (Х ₄) = {5,4,4,5,4}=5 и достигается в клетках (2, 1) и (3, 3). Перечеркнем клетки (1, 2), и (4, 2), в которых время перевозок не менее t ₂₁ = 5. С помощью оставшихся невычеркнутых клеток разгрузить клетки (2, 1) и (3, 3) не удаётся, поэтому Х ₄ является оптимальным решением.

bj ai

Ответ: min Т (X) = 5 при X* = .