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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

или

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

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

или

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

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

Пример 4.5.2.1.

Пусть задана следующая транспортная задача.






B _j

Рис.16.

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






B _j

Рис. 17.

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

V _j U _i
	-2
-1	-1	-3		-4	-2	-1
-1		-1	-3	-3		-1
-2			-2	-5	-5	-2

Рис. 18.

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






B _j

Рис. 18.

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

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

Пример 4.5.2.2.

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






B _j

Рис.20.

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







B _j

Рис. 21.

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

V _j U _i
	-
-1	-	-		-	-
-1		-	-	-
-2			-	-	-
-3				-	-

Рис. 22.

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






B _j

Рис. 23.

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

44. Задача о назначениях. Постановка. Модель. Способ задания. Основные свойства матрицы C.

§2 Задача о назначениях

2.1 Постановка задачи

Вербальная модель

Пусть имеется n – приборов (станков) и n – требований (деталей). Каждое требование может обслуживаться (каждая деталь может обрабатываться) на любом из приборов.

– длительность обслуживания i -го требования на приборе j.

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

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

Введем

(1)