4.5. Транспортные задачи, имеющие усложнения в постановке

Транспортная задача с запретами (в транспортной задаче запрещены некоторые маршруты перевозок)

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

Обозначим через множество номеров потребителей, которые связаны коммуникациями с i-м поставщиком со стоимостью перевозок , а через – множество номеров поставщиков, которые связаны коммуникациями с j-м потребителем со стоимостью перевозок , тогда математическая модель примет вид

,

,

,

.

Заметим, что в этом случае, даже при выполнении условия баланса, задача может оказаться несовместной.

Такая задача после некоторых преобразований сводится к обычной транспортной задаче.

Полагаем (М – большое число), где и , полученная задача решается методом потенциалов

Если в оптимальном решении , там где , то исходная задача несовместна.

Если при всех все , то найдено решение исходной задачи.

Несбалансированные транспортные задачи

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

Так как условие баланса является необходимым и достаточным для существования решения транспортной задачи, то несбалансированную задачу необходимо свести к сбалансированной.

Рассмотрим оба случая:

а) Пусть , то есть предложение превышает спрос.

В этом случае, очевидно, не вся продукция от поставщиков будет отправлена потребителям, поэтому математическая модель примет вид

,

,

,

.

б) Пусть , то есть спрос превышает предложение.

Математическая модель:

,

,

,

.

Рассмотрим способ сведения несбалансированных задач а) и б) к сбалансированным.

Для случая а) введём дополнительную переменную – количество продукции, которая осталась на складе i-го поставщика, то есть не вывезенная к потребителям продукция. Получим

,

,

,

или

,

,

.

Таким образом, к таблице исходных данных надо добавить -й столбец с целевыми коэффициентами, равными нулю, и

.

Для случая б) введём дополнительную переменную – количество продукции, которое недодали j-му потребителю.

,

,

,

или

,

,

.

К таблице исходных данных добавляется строка с целевыми коэффициентами, равными нулю, и .

Далее решается сбалансированная транспортная задача с помощью метода потенциалов. После решения добавленный столбец или строка отбрасываются.

Пример 4.2. Пусть задана следующая транспортная задача (рис. 4.16):

.
	5	4	3	1	2	20
	3	6	2	4	3	8
	2	4	5	3	1	7
	1	2	3	4	5	10
Bj	12	9	8	5	6

Рис. 4.16

Задача несбалансированна, так как . Поэтому необходимо добавить столбец с целевыми коэффициентами, равными нулю, и (рис. 4.17).

	5	4	3	1	2	0	20
	3	6	2	4	3	0	8
	2	4	5	3	1	0	7
	1	2	3	4	5	0	10
Bj	12	9	8	5	6	5

Рис. 4.17

Задача решается методом потенциалов (рис. 4.18).

Vj Ui	3	4	3	1	2	0
0	-2	9	0	5	1	5
-1	-1	-3	8	-4	-2	-1
-1	2	-1	-3	-3	5	-1
-2	10	0	-2	-5	-5	-2

Рис. 4.18

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

		9	0	5	1	20
			8			8
	2			5		7
	10					10
Bj	12	9	8	5	6

Рис. 4.19

Из рис. 4.19 видим, что у первого поставщика осталось пять единиц не- вывезенной продукции.

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

.

Пример 4.5.2. Имеем несбалансированную транспортную задачу (рис. 4.20).

	5	4	3	1	2	20
	3	6	2	4	3	8
	2	4	5	3	1	7
	1	2	3	4	5	10
Bj	12	15	10	8	5

Рис. 4.20

Задача несбалансированна, так как . Добавляем строку с целевыми коэффициентами, равными нулю, и . Получаем следующую задачу (рис. 4.21):

	5	4	3	1	2	20
	3	6	2	4	3	8
	2	4	5	3	1	7
	1	2	3	4	5	10
	0	0	0	0	0	5
Bj	12	15	10	8	5

Рис. 4.21

Задача решается методом потенциалов (рис. 4.22).

Vj Ui	3	4	3	1	2
0	-	10	2	8	0
-1	-	-	8	-	-
-1	2	-	-	-	5
-2	10	0	-	-	-
-3	0	5	0	-	-

Рис. 4.22

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

		10	2	8	0	20
			8			8
	2				5	7
	10					10
Bj	12	15	10	8	5

Рис. 4.23

Потребность второго потребителя не удовлетворена на пять единиц. Оптимальное значение целевой функции

.