Математическая модель транспортной задачи

 

Математическая модель транспортной задачи в общем виде имеет вид:

 

Целевая функция задачи Z(X) выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Вторая группа из уравнений ограничений записанных в общем виде, выражает требование, что запасы всех m, поставщиков вывозятся полностью, а также полностью должны удовлетворятся запросы всех n потребителей. Последнее неравенство является условием неотрицательности всех переменных.

В рассмотренной математической модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.

такая задача называется сбалансированной, а её модель закрытой. Если же это равенство не выполняется, то задача называется несбалансированной (с неправильным балансом), а её модель – открытой.

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

Математическая модель двойственной задачи:

если целевая функция Z’ стремится к минимуму то в системе ограничении меняется знак: экономический смысл перемененных двойственной задачи:

U_i – условная оценка i-го поставщика (условная плата поставщика перевозчику);

V_j – условная оценка j-го потребителя (условная плата потребителя перевозчику).

U_i, V_j – называются потенциалами.

 

Определения:

1) Если задача открыта, то необходимо добавить фиктивного поставщика или потребителя с недостающим объемом поставки и нулевой стоимостью перевозки. Распределение поставки фиктивному потребителю (поставщику), идет в последнюю очередь.

2) Клетка в плане перевозок называется базисной (закрытой), если в нее ставится перевозка.

3) Количество базисных клеток определяется соотношением r=m+n-1. опорное решение не может иметь базисных клеток больше, чем r.

4) План называется вырожденным, если количество базисных клеток меньше r, т.е. базисных клеток не хватает при выполненном условии, что объем поставок поставщиков распределен полностью и спрос потребителей также удовлетворен. В этом случае необходимо добавить нулевую перевозку.

5) Если в задаче указана не только стоимость перевозки, но и стоимость производства товара, тогда необходимо сложить эти стоимости с учетом перевозки товара от i-го поставщика j-му потребителю. Кроме того, математическая модель составляется с учетом этой суммарной стоимости.