32 33 теортя. 32. Теоремы об эквивалентности множества крайних точек допустимого множества и множества допустимых базисных решений
 Скачать 12.7 Kb.
|
|
32. Теоремы об эквивалентности множества крайних точек допустимого множества и множества допустимых базисных решений. 1) Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым. Ограничениями любой задачи линейного программирования являются либо система линейных уравнений, либо система линейных неравенств. Совокупность решений таких систем при условии их совместности, образует выпуклые множества с конечным числом угловых точек. В частном случае, когда в систему ограничений - неравенств входят только две переменные x1 и x2 это множество можно изобразить на плоскости. 2) Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений. 33. Теорема о достижимости оптимального значения в одной из крайних точек Теорема: если задача линейного программирования имеет оптимальное решение, то линейная функция принимает оптимальное значение в одной из угловых точек многоугольника решений. Если линейная функция принимает оптимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек. |