Транспортная задача с запретами (в транспортной задаче запрещены некоторые маршруты перевозок)
Довольно часто в транспортных задачах может оказаться, что между некоторыми поставщиками и потребителями отсутствуют коммуникации.
Обозначим через 
– множество номеров потребителей, которые связаны коммуникациями с 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)
где 
.