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

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

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

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

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

Таблица 5.3.1

bj ai

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

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

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

Таблица 5.3.2

bj ai
				M

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

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

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

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

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

С=

2 4 6

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

Таблица 5.3.3

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

bj ai
		-	-
	-	-	-	+
	5 +		-	M -
		-	+	-

u₁=0

u₂=1

u₃=7

u₄ = -1

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

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

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

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

u₁=0;

v₁=1-u=1-0=1;

u₂=2-v₁=2-1=1;

v₄=2-u₂=2-1=1;

u₄=0-v₄=0-1=-1;

v₃=0-u₄=0-(-1)=1;

u₃=8-v₃=8-1=7;

v₃=7-u₃=7-7=0.

Находим оценки для свободных клеток таблицы:

Δ₁₂=0+0-5= -5 <0; Δ₁₃=0+1-6= -5<0; Δ₁₄=0+1-1=0;

Δ₂₂=1+0-6= -5<0; Δ₂₃=1+1-7= -5<0; Δ₃₁=7+1-3=5>0;

Δ₃₄=7+1-M<0; Δ₄₁=-1+1-0=0; Δ₄₂=-1+0-0= -1<0.

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

Таблица 5.3.4

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

bj ai
				M -
	-	-		-

u₁=0

u₂=1

u₃=2

u₄= -6

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

Получим

X*= •

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

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

Ответ: min Z(X)=4400 при X*= •

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