Необходимое и достаточное условия разрешимости транспортной задачи

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

, т.е. задача должна быть с правильным балансом.

Доказательство. Необходимость. Пусть задача имеет допустимое решение , i=1,2,,…,m, j=1,2,…,n. Докажем, что . Подставим в уравнения системы ограничений (2), (3), получим , i=1,2,,…,m, , j=1,2,…,n. Просуммируем первую и вторую группы тождеств по отдельности: и . Отсюда следует, что задача имеет правильный баланс .

Достаточность. Пусть задача имеет правильный баланс =М. Докажем, что в этом случае задача имеет оптимальное решение. Сначала убедимся в том, что область допустимых решений задачи – непустое множество. Проверим, что = , i=1,2,,…,m, j=1,2,…,n является допустимым решением. Подставим в левые части уравнений системы ограничений (2), (3), получим = = М= , i=1,2,,…,m;

= = М= , j=1,2,…,n, т.е. уравнения обращаются в тождества. Очевидно, что удовлетворяет и условиям неотрицательности.

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

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