Правило нахождения оценок

Оценка для х_j равна сумме произведений элементов данного столбца на соответствующие элементы первого столбца (С_j-базисные) минус С_j данного столбца (коэффициент над х_j).

Например, в первой части таблицы оценка при х₂ равна:

,

в третьей части таблицы оценка при х₃ равна:

.

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

.

При решении задачи на максимум опорный план будет оптимальным, если все оценки будут неотрицательными. Исходный опорный план не будет оптимальным, т.к. оценки при х₁ и х₂ – отрицательные.

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

Разрешающую строку определяем по наименьшему θ, равному отношению свободных членов () к соответствующим положительным элементам разрешающего столбца. В разрешающем столбце х₂ два положительных элемента. Находим отношения:

Наименьшим отношением является отношение , следовательно, =1 – разрешающий элемент. Неизвестное х₂ входит в базис вместо х₅. Т.о. посредством преобразования однократного замещения мы перешли к лучшему опорному плану , при котором . Но этот план также не является оптимальным, т.к. при х₃ оценка отрицательная. В третьей части таблицы получен оптимальный план (нет отрицательных оценок):

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

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

Замечание 3. Если требуется найти минимум функции

,

то можно перейти к задаче максимизации функции

Замечание 4. Признаком альтернативного оптимума задачи является наличие нулевой оценки при свободном неизвестном оптимальной таблицы. В задаче с альтернативным оптимумом необходимо найти

опорные оптимальные планы и записать оптимальное решение в виде выпуклой линейной комбинации этих планов: