Особенности решения транспортных задач с неправильным балансом

Может случиться, что в рассматриваемых пунктах запасы не равны потребностям: или запасы превосходят потребности, или же запасы не обеспечивают потребностей.

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

Первый случай. . В математическую модель транспортной задачи введем фиктивный (l +l) - й пункт назначения. Для этого в матрице задачи предусмотрим один столбец, для которого потребность будет равна излишку груза:

, все тарифы на доставку груза в этот пункт будем считать равными нулю. Получим новую задачу, причем для старой и новой задачи функционал будет один и тот же, так как цены на дополнительные перевозки равны нулю: min.

Фиктивный потребитель обеспечивает совместность ограничений, не внося искажений в решение.

Второй случай. Если запасов не хватает для удовлетворения потребностей, т.е. , то вводим фиктивный (k +1) - й пункт отправления, которому приписываем запас груза, равный , тарифы на доставку грузов из этого фиктивного склада опять, полагаем нулевыми. В матрице добавится одна строка. На функционале это не отразится, а система ограничений задачи станет совместной, т.е. станет возможным отыскание оптимального плана на минимум стоимости перевозок.