Условие разрешимости транспортной задачи, Особенности ограничений транспортной задачи - Транспортная задача и ее решение методом потенциалов

Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие:

(1.5)

Доказательство:

Необходимость. Пусть транспортная задача разрешима, т. е. система ограничений (1.1) - (1.2) задачи совместна, тогда существуют значения xij (; ), удовлетворяющие этим условиям. Необходимо доказать, что

.

Просуммировав условия (1.2а) по i, а условия (1.2б) - по j, получим:

И.

Т. к. левые стороны этих выражений равны, то равны и правые, т. е. , что и требовалось доказать.

Достаточность. Пусть. Необходимо доказать, что существуют значения xij (; ), удовлетворяющие условиям (1.1) - (1.2). Положим

, ;

И покажем, что является планом T. З.

Действительно,

;

Очевидно также, что

> 0.

Таким образом, условия (1.1) - (1.2) удовлетворяются. Достаточность условий (1.5) доказана.

Особенности ограничений транспортной задачи

T. З. является задачей линейного программирования, и ее можно решить симплексным методом. Однако специфика ограничений T. З. позволяет применять для ее решения методы значительно менее громоздкие, чем симплексный метод. Один из них - метод потенциалов.

Особенности ограничений T. З. следующие:

    А) ограничения заданы в виде уравнений; Б) каждая переменная xij встречается только в двух уравнениях; В) коэффициенты при неизвестных, входящих в уравнение, равны единице (или нулю, если переменные не входят в уравнение).

Рассмотрим систему уравнений (1.2). Она содержит (m + n) уравнений с m - n неизвестными. Сложив почленно уравнения отдельно системы (1.2а) и отдельно - системы (1.2б), мы получим два одинаковых уравнения:

> 0;

> 0.

Это говорит о том, что система уравнений (1.2) Т. З. линейно зависима и, по крайней мере, одно из уравнений лишнее. Следовательно, максимальное число линейно независимых уравнений системы (1.2), т. е. ранг r системы, не более, чем (m + n - 1).

Можно показать, что ранг r в точности равен (m + n - 1), т. е. система ограничений T. З. содержит ровно (m + n - 1) линейно независимых уравнений. Это означает, что если систему уравнений (1.2) решить методом Жордана-Гаусса, то число базисных переменных будет равно (m + n - 1).

Одним из методов решения T. З., который учитывает специфику ее ограничений, является метод потенциалов. По существу, его можно рассматривать, как результат реализации симплексного метода в условиях транспортной задачи (1.1)-(1.3).

Метод потенциалов состоит из трех шагов.

Первый шаг - отыскание исходного опорного плана перевозок T. З..

Второй шаг - проверка найденного плана на оптимальность. Если условия оптимальности плана перевозок выполнены - задача решена.

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

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

Похожие статьи




Условие разрешимости транспортной задачи, Особенности ограничений транспортной задачи - Транспортная задача и ее решение методом потенциалов

Предыдущая | Следующая