Признаки оптимальности опорного решения

Достаточный признак достижения целевой функцией минимума на данном ОР. Если все оценки свободных переменных неположительны, ≤ 0, то минимум целевой функции равен числу (все свободные переменные равны нулю).

Достаточный признак достижения целевой функцией максимума на данном ОР. Если все оценки свободных переменных неотрицательны, ≥ 0, то максимум целевой функции равен числу (все свободные переменные равны нулю).

Соответствующие ОР являются оптимальными.

Объединив оба случая, можно сформулировать признак оптимальности опорного решения: Опорное решение ЗЛП на максимум (минимум) является оптимальным, если для любого вектора условий оценка разложения по базису ОР неотрицательная (неположительная), т.е.

· в задаче на максимум ≥ 0 ;

· в задаче на минимум ≤ 0 .

При этом экстремальное значение целевой функции равно числу .

Признак единственности оптимального решения. Оптимальное решение ЗЛП является единственным, если для любого вектора условий, не входящего в базис, оценка не равна нулю, т.е. (здесь предполагается, что в базис оптимального решения входят первые m векторов).

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

Из признака оптимальности следует, что в примере 6 оптимальным будет ОР (11/7, 0, 0, 12/7). Оценки всех свободных переменных положительны (последняя строка в табл. 13), поэтому целевую функцию больше увеличивать нельзя. . Из признака единственности оптимального решения следует, что найденное оптимальное решение (11/7, 0, 0, 12/7) единственно.

Date: 2015-09-20; view: 1534; Нарушение авторских прав