Математическая модель транспортной задачи
Переменными (неизвестными) транспортной задачи являются 
, i = 1, 2, ..., m; j = 1, 2, ..., n - объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок
.
Так как произведение 
определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны 
. По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция задачи имеет вид
.
Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид
, i = 1, 2, ..., m.
Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид
, j = 1, 2, ..., n.
Учитывая условие неотрицательности объемов перевозок математическую модель задачи можно записать
, (6.1)
, i = 1, 2, ..., m, (6.2)
, j = 1, 2, ..., n, (6.3)
, i = 1, 2, ..., m; j = 1, 2, ..., n. (6.4)
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т. е.
. (6.5)
Такая задача называется задачей с правильным балансом, а модель задачи - закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а модель задачи - открытой.
Математическая формулировка транспортной задачи такова: найти переменные задачи
, i = 1, 2, ..., m; j = 1, 2, ..., n,
удовлетворяющие системе ограничений (6.2), (6.3), условиям неотрицательности (6.4) и обеспечивающие минимум целевой функции (6.1).
Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи (6.2), (6.3):
. (6.6)
Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной , является вектором-условий задачи и обозначается через 
. Каждый вектор имеет всего m + n координат и только две из них, отличные от нуля, равны 1. Первая единица вектора стоит на i-м месте, а вторая единица на (m + j)-м месте, т. е.
номер
координаты
.
Обозначим через 
вектор-ограничений (правых частей уравнений (6.2), (6.3)), и систему ограничений задачи представим в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:
, (6.7)
, (6.8)
, i = 1, 2, ..., m; j = 1, 2, ..., n. (6.9)
Пример 6.1. Составить математическую модель транспортной задачи, исходные данные которой приведены в табл. 6.2.
Т а б л и ц а 6.2
| bj aj | |||
Решение. Вводим переменные задачи (матрицу перевозок)
.
Запишем матрицу стоимостей
.
Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X
.
Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.
Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X – запасам второго поставщика:
Это означает, что запасы поставщиков вывозятся полностью.
Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей. Это означает, что запросы потребителей удовлетворяются полностью:
Необходимо также учитывать, что перевозки не могут быть отрицательными
, i = 1, 2, ..., m; j = 1, 2, ..., n.
Таким образом, математическая модель рассматриваемой задачи записывается следующим образом.
Найти переменные задачи, обеспечивающие минимум функции
и удовлетворяющие системе ограничений
и условиям неотрицательности
, i = 1, 2, ..., m; j = 1, 2, ..., n.
Необходимое и достаточное условие разрешимости
транспортной задачи
Теорема 6.1. Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей
,
т. е. задача должна быть с правильным балансом.
Доказательство. Необходимость. Пусть задача имеет допустимое решение
, 
, i = 1, 2, ..., m; j = 1, 2, ..., n.
Докажем, что 
. Подставим 
в уравнения системы ограничений (6.2) и (6.3), получим
, i = 1, 2, ..., m, 
, j = 1, 2, ..., n .
Просуммируем первую и вторую группы тождеств по отдельности
и 
.
Отсюда следует, что задача имеет правильный баланс 
.
Достаточность. Пусть задача имеет правильный баланс
= М.
Докажем, что в этом случае задача имеет оптимальное решение.
Сначала убедимся в том, что область допустимых решений задачи является не пустым множеством. Проверим, что 
, i = 1, 2, ..., m; j = 1, 2, .., n является допустимым решением. Подставим 
в левые части уравнений системы ограничений (6.2), (6.3), получим
, i = 1, 2, ..., m,
, j = 1, 2, ..., n,
т. е. уравнения обращаются в тождества. Очевидно, что 
удовлетворяет и условиям неотрицательности.
Далее покажем, что существует оптимальное решение. Учитывая, что стоимости перевозок единиц груза ограничены сверху и снизу 
, где C и D – конечные постоянные, можно записать
.
Следовательно, целевая функция ограничена на множестве допустимых решений и, как всякая непрерывная функция достигает своего наименьшего (а также и наибольшего) значения.