Разрешимость транспортной задачи

Проанализируем разрешимость построенной модели. Из теории линейного программирования известно [3], что такая задача может не иметь решений в одном из двух случаев: если у нее отсутствуют допустимые планы (система ограничений несовместна) или ее целевая функция не ограничена (стоимость перевозок можно уменьшать до бесконечности).

Возможен ли первый случай? Сложив почленно все ограничения, связанные с запасами продукции у поставщиков (это первые n ограничений в формуле (1)), можно получить, что суммарные поставки (сумма всех переменных) не превышают общий объем запасов:

Аналогично из ограничений, связанных с потребностями (в формуле (1) это ограничения с (n+1)-го по (n+m)-ое, т.е. следующие m ограничений), следует, что эта сумма должна быть не менее общего объема потребностей:

Итак, . Отсюда необходимое и достаточное условие существования допустимого плана транспортной задачи состоит в следующем:

(общий объем потребностей не превышает общего объема запасов).

Возможно ли, чтобы целевая функция транспортной задачи была не ограничена на минимум? Нет. Она не может быть, например, меньше нуля, поскольку представляет собой сумму неотрицательных слагаемых.

Следовательно, формула (4) представляет собой и критерий разрешимости транспортной задачи. Выполнение этого условия необходимо и достаточно для того, чтобы транспортная задача имела решение.