4. Вычисление оценок (значений критерия оптимальности плана).
После заполнения указанных столбцов
симплекс-таблицы необходимо определить,
является ли начальный опорный план
оптимальным.
Критерий оптимальности опорного плана
Опорный план
задачи линейного программирования
является оптимальным
,
если для всех векторов
системы ограничений выполняется условие
(для задачи максимизации),
(26)
или
(для задачи минимизации),
(27)
.
(28)
Если хотя бы для одного из векторов
критерий оптимальности (26) или
(27) не выполняется, то опорный
план
не является оптимальным.
Здесь
- число, равное значению целевой функции,
если в качестве переменных подставить
значения коэффициентов разложения
вектора
по векторам базиса;
- оценка разложения вектора
по векторам базиса. Для ее вычисления
необходимо из скалярного произведения
векторов-столбцов
и
вычесть соответствующий коэффициент
целевой функции.
Критерий единственности опорного плана
Оптимальный план
является единственным,
если для любого вектора условий
,
не входящего в базис
,
оценка
не равна нулю:
,
для
.
(29)
В противном случае задача имеет альтернативные оптимальные планы.
В последнюю строку «Оценка»
симплекс-таблицы в столбцах
заносят результаты вычисления
оценок для каждого из векторов
:
.
В столбце «План
»
оценочного ряда заносится значение
целевой функции
для начального плана
.
Так как оценки
и
отрицательны, то план
не является оптимальным и необходимо
перейти к другому опорному плану.
5. Симплекс-критерии перехода к новому опорному плану.
Переход к новому опорному плану
осуществляется путем замены базиса и
перехода к новым базисным переменным.
Из текущего базиса
необходимо исключить один из базисных
векторов
или
(одну из базисных переменных
или
)
и включить вместо него один из небазисных
векторов
или
и соответствующую свободную переменную.
Получим новый базис
с соответствующими новыми базисными
переменными.
Симплекс-критерий I включения вектора в базис
Если для задачи максимизации
в строке оценок есть отрицательные
оценки
(для задачи минимизации - положительные
оценки
),
соответствующие небазисным переменным,
то в новый базис войдет вектор условий
с номером
,
соответствующий максимальной по
абсолютной величине отрицательной
(положительной) оценке
для
(30)
Если таких максимальных оценок
несколько, то в базис вводится вектор,
соответствующий максимальному
коэффициенту
целевой функци.
Направляющим столбцом
называется столбец симплекс-таблицы
(столбец матрицы ограничений с номером
),
в котором находится включаемый в базис
вектор
.
Если в направляющем столбце симплекс-таблицы нет положительных элементов
,
(31)
то целевая функция неограниченна и оптимальный план не существует.
В новом базисе целевая функция получит максимально возможное положительное (отрицательное) приращение и приблизится к максимальному (минимальному) оптимальному значению.
В рассматриваемой задаче максимизации
отрицательными являются оценки
и
.
Максимальная по абсолютной величине
оценка
равна
и находится во втором столбце
.
Поэтому в новый базис будет включен
вектор
,
соответствующий новой базисной переменной
.
Направляющий второй столбец выделен
цветом в симплекс-таблице.
Для определения базисного вектора и переменной, которые необходимо исключить из текущего базиса, используется второй симплекс-критерий, обеспечивающий неотрицательность правых частей системы уравнений ограничений.