Свойства задач ЛП
Выше в лекции по ЛП было показано, что любая задача ЛП м.б. представлена в виде общей, канонической или стандартной задачи. Причем, от одной задачи можно перейти к другой. Будем рассматривать каноническую задачу, в которой система ограничений – система уравнений. Теорема 4. Множество всех допустимых решений системы ограничений ЗЛП (задачи линейного программирования)является выпуклым, т.е. является выпуклым многогранником (или выпуклой многогранной областью). Будем называть в дальнейшем – многогранником решений. Теорема 5. Если задача ЛП имеет оптимальное решение, то линейная функция принимает макс (мин) значение в одной из угловых точек многогранника решений. Эта теорема является фундаментальной, т.к. она указывает принципиальный путь решения ЗЛП. Действительно, согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них искомого оптимального решения необходимо исследовать лишь конечное число угловых точек многогранника решений. Теорема 6. Каждому допустимому базисному решению ЗЛП соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение. Из теорем 5 и 6 вытекает следствие: если ЗЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений. Итак, оптимум линейной функции ЗЛП следует искать среди конечного числа ее допустимых базисных решений.
|
