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

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

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

,

,

,

.

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

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

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

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

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

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

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

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

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

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

,

,

,

.

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

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

,

,

,

.

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

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

,

,

,

или

,

,

.

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

.

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

,

,

,

или

,

,

.

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

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

Пример 4.5.2.1.

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

Bj

Рис.16.

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

Bj

Рис. 17.

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

Vj Ui
	-2
-1	-1	-3		-4	-2	-1
-1		-1	-3	-3		-1
-2			-2	-5	-5	-2

Рис. 18.

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

Bj

Рис. 18.

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

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

.

Пример 4.5.2.2.

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

Bj

Рис.20.

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

Bj

Рис. 21.

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

Vj Ui
	-
-1	-	-		-	-
-1		-	-	-
-2			-	-	-
-3				-	-

Рис. 22.

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

Bj

Рис. 23.

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

.

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

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

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

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

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

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

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

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

Введем

(1)

, если i-е требование обслуживается j-м прибором;

, если i-е требование не обслуживается.

Ограничения:

, (2)

каждое требование обслуживается ровно одним прибором.

, (3)

каждый прибор обслуживает ровно одно требование.

Целевая функция имеет вид

.

Замечание. Так как коэффициент не влияет на положение оптимальной точки, то целевую функцию можно заменить на функцию

, (4)

где .