22

22) Метод потенциалов. Теорема о достаточном условии оптимальности опорного решения транспортной задачи.

Пусть исходное опорное решение записано в транспортной таблице, тогда в базисных клетках стоят неотрицательные числа, а свободные незаполнены (соответственно =0)

Сопоставим каждому поставщику число α_i a_i→α_i, а для каждого потребителя число βj v b_j→β_j и потребуем, чтобы для каждой базисной клетки (k,l) выполнялось условие α_i+β_j=c_kl c_kl – тариф

Получаем систему из m+n-1 уравнений и m+n неизвестных. Эта линейная система относительно неизвестных α_k и β_l всегда совместна. Чтобы найти какое-либо одно решение, нужно 1 неизвестное задать, а значения остальных неизвестных найти из системы. Всякое решение такой системы уравнений будем называть потенциалами данного опорного решения.

Теорема.

Пусть Х₀ – опорное решение системы ограничений (1) и (2) α_i i=1,m β_j j=1,n – потенциалы опорного решения Х_0.

Тогда, если для каждой свободной клетки транспортной таблицы выполняется условие α_i + β_j ≤ c_kl (*), то Х₀-оптимальное, следовательно, Х ₀→min

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

Доказать, Х-произвольное опорное решение (план) систем (1) и (2) , то стоимость перевозок(значение целевой функции) f(X) ≥f(X₀) X₀=(x⁰₁₁, x⁰₁₂,…,x⁰_mn)

F(X) = ≥

= +

=

= f(X₀)

Для базисных неизвестных (α_i+ β_j)x⁰_ij=c_ij x⁰_ij , т к мы находим потенциалы, а для свободных клеток (α_i+ β_j)x⁰_ij=c_ij x⁰_ij также выполняется , т к по условию теоремы значение x⁰_ij =0 для свободной клетки.

Если найдется хотя бы 1 клетка, для которой условие (*) не выполняется, то есть α_i + β_j c_kl, то опорное решение Х₀ не является оптимальным, необходимо перейти к новому опорному решению Х₁, на котором значение целевой функции меньше или равно значению на опорном решении Х_0. F(X₁₎₀)