Переменными (неизвестными) транспортной задачи являются i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок
.
Так как произведение определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид .
Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью:
, i=1,2,…,m.
Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:
, j=1, 2, …, n.
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:
, (1)
, i=1,2,…,m, (2)
, j=1, 2, …, n, (3)
, i=1,2,,…,m, j=1,2,…,n (4)
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. .
|
|
Такая задача называется задачей с правильным балансом, а ее модель – закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель – открытой.
Математическая формулировка транспортной задачи такова: найти переменные задачи , i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).
Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи (2), (3):
.……………………………………………………
А = (6).
……………………………………………………
Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной , является вектором-условием задачи и обозначается через . Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая – на (m+j)-м месте, т.е.
Номер
корди-
наты
= ; = .
Обозначим через вектор ограничений (правых частей уравнений (2), (3)) и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:
, (7)
= , (8)
, i=1,2,,…,m, j=1,2,…,n (9)