Условие оптимальности ДБР

Определение. Вектор-строка, на которую умножается слева x_N в уравнении для ЦФ (13), называется век­тором относительных оценок, т.к. он указывает, в какую сторону и насколько изменится ЦФ при изменении x_N.

Обозначим этот вектор через d_N. Его j-ый элемент определяется так:

Если относительная оценка (d_N)_j, то небазисной переменной (x_N)_j положительна или равна нулю, но значение ЦФ не увеличивается при увеличении (x_N)_j, начиная с нуля [11].

Теорема (условие оптимальности).Для ДБР x⁰ операция замещения, при которой (x_N)_p вводится в базис, изменяет значение ЦФ на величину

где

Если d_N≥0, то x⁰ оптимально.

ЗЛП будем называть невырожденной, если все ее ДБР не вырождены. Справедлива теорема, обратная последней теореме.

Теорема. Пусть ЗЛП является невырожденной, а x⁰ – ДБР, являющееся ее решением. Тогда d_N≥0.

В том случае, если ЗЛП не является невырожденной, предыдущая теорема приобретает вид:

Теорема. Для того, чтобы ДБР x⁰ являлось решением исходной ЗЛП, необходимо и достаточно су­ществование такого базиса для x⁰, для которого d_N≥0.

Теорема. Если некоторому ДБР исходной задачи соответствует задача, для которой существует не­базисная переменная (x_N)_p такая, что (d_N)_p<0 и (a_N)_*p≤0, то целевая функция исходной задачи не ограни­чена на множестве допустимых решений (θ не ограничено сверху и можно сколько угодно увеличивать целевую функцию).

 

Пример 7.1

Дана ЗЛП

.

Знайти всі компоненти перетвореної задачі для ДБР, який відповідає базису . Чи є оптимальним цей ДБР?

Розв’язок

Базисні, небазисні змінні та відповідні їм векторикоєфіцієнтів ЦФ:

.

Небазисна матриця та вектор правих частин обмежень:

.

Базисна матриця та матриця, обернена до неї:

.

Значення базисних змінних та ЦФ:

Вектор відносних оцінок небазисних змінних:

Оскільки вектор відносних оцінок небазисних змінних містить додатні компоненти, а задача на максимум, то поточний базисний розв'язок не є оптимальним.