Транспортная задача по критерию времени
Переменными(неизвестными) транспортной задачи являются (i=1,…,m;i=1,2,…,n)- объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в матрице перевозок
Математическая модель транспортной задачи в общем случае имеет вид
i=1,2,…,m,
j=1,2,…,n,
i=1,2,…,m; j=1,2,…,n.
Целевая функция задачи выражает требования обеспечить минимум суммарных затрат на перевозку всех грузов. Первая группа из т уравнений описывает тот факт, что запасы всех т поставщиков вывозятся полностью. Вторая группа из n уравнений выражает требования полностью удовлетворить запросы всех n потребителей. Неравенства являются условиями неотрицательности всех переменных задачи.
Таким образом, математическая формулировка транспортной задачи состоит в следующем: найти переменные задачи
i=1,2,…,m; j=1,2,…,n,
удовлетворяющее системе ограничений условиям неотрицательности и обеспечивающее минимум целевой функции.
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.
.
Такая задача называется задачей с правильным балансом, а ее модель- закрытой. Если же это неравенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель- открытой.
Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т.е. задача должна быть с правильным балансом.
Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.
Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы Х, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы Х - запасам второго поставщика:
Это означает, что запасы поставщиков вывозятся полностью.
Суммы перевозок, стоящих в каждом столбце матрицы Ч, должны быть равны запросам соответствующих потребителей:
Это означает, что запросы потребителей удовлетворяются полностью.
Необходимо также учитывать, что перевозки не могут быть отрицательными:
Ответ: математическая модель задачи формулируется следующим образом: найти переменные задачи, обеспечивающие минимум функции
и удовлетворяющие системе ограничений и условиям неотрицательности.
АЛГОРИТМ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
СБАЛАНСИРОВАННОСТЬ ТРАНСПОРТНОЙ ЗАДАЧИ