Переменными(неизвестными)
транспортной задачи являются (i=1,…,m;i=1,2,…,n)- объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в матрице перевозок
Математическая
модель транспортной задачи в общем случае имеет вид
(1.1)
i=1,2,…,m, (1.2)
j=1,2,…,n, (1.3)
i=1,2,…,m; j=1,2,…,n. (1.4)
Целевая функция
задачи (1.1) выражает требования обеспечить минимум суммарных затрат на
перевозку всех грузов. Первая группа из т уравнений (1.2) описывает тот
факт, что запасы всех т поставщиков вывозятся полностью. Вторая группа
из n уравнений (1.3) выражает
требования полностью удовлетворить запросы всех n потребителей. Неравенства (1.4) являются условиями
неотрицательности всех переменных задачи.
Таким образом,
математическая формулировка транспортной задачи состоит в следующем: найти
переменные задачи
i=1,2,…,m; j=1,2,…,n,
удовлетворяющее
системе ограничений (1.2), (1.3), условиям неотрицательности (1.4) и обеспечивающее
минимум целевой функции (1.1).
В рассмотренной
модели транспортной задачи предполагается, что суммарные запасы поставщиков
равны суммарным запросам потребителей, т.е.
.
Такая задача
называется задачей с правильным балансом, а ее модель- закрытой. Если же это
неравенство не выполняется, то задача называется задачей с неправильным балансом,
а ее модель- открытой.
Для того чтобы
транспортная задача линейного программирования имела решение, необходимо и
достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам
потребителей, т.е. задача должна быть с правильным балансом.
Пример 1:
Составить
математическую модель транспортной задачи перевоза груза из двух складов в 3
магазина:
Целевая функция
задачи равна сумме произведений всех соответствующих элементов матриц С и Х:
Данная функция,
определяющая суммарные затраты на все перевозки, должна достигать минимального
значения.
Составим систему
ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы Х,
должна равняться запасам первого поставщика, а сумма перевозок во второй строке
матрицы Х – запасам второго поставщика:
Это означает, что
запасы поставщиков вывозятся полностью.
Суммы перевозок,
стоящих в каждом столбце матрицы Ч, должны быть равны запросам соответствующих
потребителей:
Это означает, что
запросы потребителей удовлетворяются полностью.