Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
2.3.1. Критерий оптимальности
Каноническая форма позволяет не только сразу же найти допустимое базисное решение, но и определить будет ли оно оптимальным. Для этого исследуются коэффициенты целевого уравнения (2.5).
Определение 2.2 [13]. Коэффициенты целевого уравнения канонической формы называются относительными оценками, так как их значения будут зависеть от выбора базисного множества переменных.
Далее, для изложения симплекс-алгоритма в его оригинальном виде (разработанным его автором Джон Данцигом) рассмотрим задачу минимизации целевой функции.
Теорема 2.3 [13]. Базисное допустимое решение является минимальным допустимым решением с общими затратами f, если все относительные оценки неотрицательны
cj ≥ 0, j = 1, …, n.
Следствие. Базисное допустимое решение является единственным минимальным допустимым решением, если cj ≥ 0 для всех небазисных решений.