Проверка опорного плана на оптимальность

Запишем исходную модель КТЗ в векторной форме:

(5)

(6)

(7)

Здесь - вектор условия,

G= - вектор ресурсов.

Известно, что каждой ЗЛП соответствует двойственная задача. В двойственной задаче столько же переменных, сколько ограничений в исходной, и столько же ограничений, сколько в исходной задаче переменных.

Пусть - двойственная переменная, соответствующая i-тым ограничениям (2) (потенциал пункта А_i), - двойственная переменная, соответствующая j-тому ограничению (3) (потенциал пункта В_j). Тогда вектор двойственных переменных будет иметь вид: , а сама двойственная задача запишется в виде:

(8)

(9)

В скалярной форме эта задача запишется:

(10)

(11)

Существует теорема (без доказательства):

Для оптимальности опорного плана КТЗ (1)-(4) необходимо и достаточно существование вектора двойственных переменных, компоненты которого удовлетворяют условию:

(12)

Причем , если - базисная переменная, и , если - небазисная переменная.

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

Т.о., для проверки опорного плана на оптимальность необходимо определить потенциалы , всех пунктов А_i и В_j. Для этого используют условие (12) для базисных переменных:

(13)

Для отыскания потенциалов , необходимо решить данную систему линейных уравнений. Уравнений в системе (13) будет (m+n-1), а кол-во неизвестных (m+n). Поэтому любой одной переменной можно придать любое значение, в том числе и нулевое. На распределительной таблице построение потенциалов производится следующим образом: полагаем для какой-либо строки i₁, содержащей базисные переменные, потенциал =0. Просматривается эта строка, и находятся базисные клетки . Для всех таких клеток из (13) можно определить потенциалы столбцов В_j:. Далее по известным потенциалам столбцов можно определить потенциалы некоторых строк. Пусть потенциал известен. Тогда просматривается столбец с номером и находятся клетки (), содержащие базисные переменные. Для всех этих клеток из (13) можно найти потенциалы строк А_i: . Продолжая этот процесс, найдутся потенциалы строк всех пунктов производства и потенциалы столбцов всех пунктов потребления.

Далее для всех клеток (i,j) содержащих небазисные переменные, вычисляются оценки . Если все , то рассматриваемый план КТЗ является оптимальным. Если хотя бы для одной клетки (k,l) справедливо , то опорный план неоптимален и необходимо перейти к лучшему опорному плану.

Дата добавления: 2014-01-05