Теоретическая часть, Математическая постановка задачи - Анализ транспортной задачи по критерию времени

Математическая постановка задачи

Транспортная задача - Однородный груз сосредоточен у поставщиков. Данный груз необходимо доставить потребителям.

Известны (i=1,2,...,m; j=1,2,...,n) - стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны.

Переменными(неизвестными) транспортной задачи являются (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, удовлетворяющее системе ограничений условиям неотрицательности и обеспечивающее минимум целевой функции. В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей.

Такая задача называется задачей с правильным балансом, а ее модель - закрытой. Если же это неравенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель - открытой. Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т. е. задача должна быть с правильным балансом. Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения. Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы Х, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы Х - запасам второго поставщика. Это означает, что запасы поставщиков вывозятся полностью. Суммы перевозок, стоящих в каждом столбце матрицы Ч, должны быть равны запросам соответствующих потребителей. Это означает, что запросы потребителей удовлетворяются полностью. Необходимо также учитывать, что перевозки не могут быть отрицательными: Ответ: математическая модель задачи формулируется следующим образом: найти переменные задачи, обеспечивающие минимум функции и удовлетворяющие системе ограничений и условиям неотрицательности.

Похожие статьи




Теоретическая часть, Математическая постановка задачи - Анализ транспортной задачи по критерию времени

Предыдущая | Следующая