Лекция 5. Основные теоремы линейного программирования

Содержание лекционного занятия:

· Теорема об оптимальном решении в ограниченной области.

· Теорема об оптимальном решении в неограничен­ной области.

· Фундаментальная теорема.

· Теорема об альтернативном оптимуме.

· Геометрическая интерпретация симплекс-метода

Прежде чем перейти к рассмотрению основных теорем линейного программирования, вспомним понятия, рассматриваемые в курсе линейной алгебры.

Базисным (опорным) решением системы m линейных уравнений с п переменными называется решение, в кото­ром все (n-m) не основных переменных равны нулю.

Число базисных решений является конечным, так как оно равно числу групп основных переменных, не превосходящему C^m _n.

Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.

Теорема. Если задача линейного программирования имеет оптимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника решений. Если линейная функция принимает максимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся вы­пуклой линейной комбинацией этих точек.

Теорема. (Об оптимальном решении в ограниченной области.) Если область допустимых решений системы ограничена, то оптимальное решение существует и совпадает хотябы с одним из опорных решений системы.

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

Теорема. (Фундаментальная.) Если задача линейного программирования имеет оптимальное решение (в ограни­ченной области всегда, а в неограниченной области в зави­симости от ограниченности линейной функции), то оно совпадает, по крайней мере, с одним из опорных решений системы ограничительных уравнений.

Теорема. (Об альтернативном оптимуме.) Если мак­симум или минимум линейной функции достигается в не­скольких опорных решениях, то любое оптимальное решение есть выпуклая линейная комбинация оптимальных решений.