Формулировка транспортной задачи
Исходные данные транспортной задачи обычно записываются в таблице (таб1.1).
В =() и матрицы стоимостей .
Переменными (неизвестными) транспортной задачи являются 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, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1). Математическая модель транспортной задачи может быть записана в векторном виде.. Тогда математическая модель транспортной задачи запишется следующим образом: , (7) = , (8) , i=1,2,,…,m, j=1,2,…,n (9)
|