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

 

Обозначим x_ij - величина груза, перевозимого с базы A_i потребителю B_j .

Так как стоимости перевозок (тарифы) известны, запишем функцию общих затрат на перевозку:

. (2.10)

Величина перевозимых грузов не может быть отрицательна:

. (2.11)

Если задача с выполненным балансом, т.е. выполняется условие (2.9), то количество вывозимого с i-ой базы груза должно совпадать с запасами на этой базе:

, (2.12)

количество привозимого j-ому потребителю груза должно совпадать с его потребностями

. (2.13)

Математическая модель задачи: требуется минимизировать функцию затрат (функцию цели) Z:

(2.14)

При наличии ограничений:

(2.15)

Отметим следующие особенности транспортной задачи:

1. Все коэффициенты в системе ограничений равны единице.

2. Не все m + n уравнений являются независимыми. В силу условия одно из ограничений можно исключить и тогда для общего числа m´n переменных будет m + n - 1 ограничений. То есть опорный план должен содержать не более m + n - 1 компонент. В этом случае план называется невырожденным. В случае вырожденного опорного плана число компонент будет меньше, чем m + n - 1. Если план оказывается вырожденным, то в клетку следует ввести пустую поставку (груз, равный 0) и считать ее заполненной.

При решении транспортной задачи выделяются следующие шаги.

1. Составление начального плана перевозок.

2. Проверка плана на оптимальность и его пошаговое уточнение.