2.4. Транспортная задача с усложнениями

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

1. Запрет перевозок от i-го поставщика к j-му потребителю.

Для определения оптимальных планов таких задач предполагают, что тариф перевозки единицы груза из пункта А_i в пункт В_j является столь угодно большой величиной M, и при этом условии известными методами находят решение новой транспортной задачи. При таком предположении исключается возможность при оптимальном плане ТЗ перевозить грузы из А_i в В_j. Такой подход к нахождению решения ТЗ называется запрещением перевозок или блокированием соответствующей клетки таблицы данных задачи.

2. Фиксированная поставка.

В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из пункта А_i в пункт В_j требуется обязательно перевезти α_ij ед.груза. Тогда в ячейку таблицы данных ТЗ, находящуюся на пересечении строки А_i и столбца В_j, записывают указанное число α_ij и в дальнейшем эту ячейку считают свободной со сколь угодно большим тарифом перевозок М. Для полученной таким образом новой ТЗ находят оптимальный план, который определяет оптимальный план исходной задачи.

3. Нижние границы на поставки.

Иногда требуется найти решение ТЗ, при котором из пункта А_i в пункт В_j должно быть завезено не менее заданного количества груза α_ij. Для определения оптимального плана какой задачи считают, что запасы пункта А_i и потребности пункта В_j меньше фактических на α_ij ед. Далее находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи. После этого к значению переменной х_ij добавляют α_ij.

4. Верхние границы на поставки.

В некоторых ТЗ требуется найти оптимальный план перевозки при условии, что из пункта отправления А_i в пункт В_j перевозится не более чем α_ij единиц груза, т.е. x_ij≤α_ij. Для сведения условия задачи к разрешимому типу поставщика А_i или потребителя В_j (либо того, либо другого) делят на две части, как бы на два самостоятельных поставщика (или потребителя). При этом мощности этих условно самостоятельных поставщиков будут равны: А′_i=α_ij и А′′_i=А_i-α_ij. Затраты на поставку продукции от пос-

или

.

тавщика А′i к Вj и другим потребителям принимаются равными затратам, заданным в матрице C=(сij)mxn. Затраты с′′ij на постав-

ку продукции от поставщика А′′_i к В_j принимаются равными с′′_ij=М, где М – сколь угодно большое число. Затраты на поставку от А′′_i к другим потребителям (помимо В_j) принимаются равными заданным в матрице C=(с_ij)_mxn. Подобный прием обеспечивает положение, при котором переменная в решении задачи непременно будет равна нулю, в то время как переменная может принимать любое значение от нуля до a_ij, 0≤x_ij ≤α_ij. После получения оптимального решения соответствующие переменные поставщиков А′_i и А′′_i (или потребителей В′_i и В′′_i) складываются.

Пример 4. Найдем решение ТЗ, исходные дан-ные которой приведены в табл.10 с учетом того, что из пункта А1 в пункт В1 перевозки не могут быть осуществлены, а из пункта А3 в пункт В1 будет завезено 10 ед. груза.	Таблица 10
	Вj Аi 50 80 30 60 65 3 5 4 1 85 4 5 6 2 70 5 1 3 3

Так как из А₁ в В₁ перевозки не могут быть осуществлены, то в ячейке (1,1) тариф считаем равными некоторому сколь угодно большому числу М. Полагаем равным этому же числу и тариф для ячейки (3,1). Одновременно в эту клетку помещаем число 10, так как по условию из А₃ в В₁ нужно завезти 10 единиц груза. В дальнейшем ячейку (3,1) считаем свободной со сколь угодно большим тарифом М. Находим опорный план методом наименьшей стоимости и проверяем его на оптимальность.

Итерация 0 Вj Аi 50 80 30 60 ui 65 М 2-М 5 -2  4 5 ⊖1 60 0 85 4 40 5 20 ⊖6 25 2 1 2 70 М 10 -М 1 60 3 -1 3 -4 -2 vj 2 3 4 1

Итерация 1 Вj Аi 50 80 30 60 ui 65 М 3-М 5 -1 4 30 1 35 0 85 4 40 5 20 6 -1 2 25 1 70 М 10 -М 1 60 3 -4 3 -5 -3 vj 3 4 4 1

Он не оптимален, так как одна оценка является положительной (1). Строим новый план (итерация 1). Он является оптимальным. Следовательно, исходная ТЗ имеет оптимальный план .

При этом общая стоимость перевозок

z*=430+135+440+520+225+510+160=575 ден. ед. является минимальной.

Пример 5. Найдем решение ТЗ, исходные данные которой приведены в табл.11 с учетом того, что из пункта А2 в пункт В4 завезти не менее 5 ед. груза, а из А2 в В1 – не более 30 ед. груза.	Таблица 11
	Вj Аi 50 80 30 60 65 3 5 5 1 85 4 5 6 2 70 5 1 3 3

Так как из А₂ в В₄ необходимо завезти не менее 5 ед.груза, то запасы этих пунктов отправления и назначения считаем меньшими на 5 ед.

Итерация 0								Итерация1
Вj Аi	30	80	30	55	20	ui		Вj Аi	30	80	30	55	20	ui
65	3 10 ⊖	5 -1	5 0	1 55	3 М-4	0		65	3 4-М	5 3-М	5 4-М	⊖ 1 55	 3 10	0
80	 4 20	5 10	6 30	2 0	М 20 ⊖	1		80	4 30	5 10	6 30	 2 М-4	⊖ М 10	М-3
70	5 -5	1 70	3 --1	3 --5	5 М-9	-3		70	5 -5	1 70	3 -1	3 М-9	5 М-9	М-7
vj	3	4	5	1	М-1			vj	7-М	8-М	9-М	1	3

Кроме того, поскольку из А₂ в В₁ необходимо завезти не более 30 ед. груза, то пункт назначения В₁ разобьём на два пункта: потребности В₁ теперь считаем равными 30 ед. и рассмотрим дополнительный

Итерация 2								пункт В′′1 с потребностями, равными 50-30=20 ед. В столбце В′′1 записываем тарифы, помещённые в ячейках столбца В1, за исключением ячейки (2,1′′). В этой ячейке тариф полагаем равным некоторому сколь угодно большому числу М. Решение задачи методом потенциалов приведено в таблицах итер. 0–2.
Вj Аi	30	80	30	55	20	ui
65	3 0	5 -1	5 0	1 45	3 20	0
80	4 30	5 10	6 30	2 10	М 4-М	1
70	5 -5	1 70	3 --1	3 --1	5 -5	-3
vj	3	4	5	1	3

Как видно из таблицы итер. 3, исходная ТЗ имеет оптимальный план

.

Мы сложили соответствующие переменные столбцов В₁ и В′′₁ и добавили 5 ед. груза в ячейку (2,4) исходя из дополнительных условий задачи. При этом общая стоимость перевозок является минимальной.

z*=320+145+430+510+630+215+170=555 ден. ед.