Свойства задач ЛП

Теорема 5.2. Множество всех допустимых решений системы ограничений задачи ЛП является выпуклым многогранником.

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

Точка Х называется выпуклой линейной комбинацией точек X₁, X₂, …, X_n, если выполняются условия:

, (5.14)

Теорема 5.4. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений и, наоборот, каждой угловой точке многогранника решений соответствует базисное решение.

Любые m переменных системы ограничений ЗЛП (5.6), состоящей из m линейно независимых уравнений с n переменными (m < n), называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n – m переменных называются неосновными (или свободными).

Базисным называют решение ЗЛП, при котором все свободные переменные равны нулю.

Дата добавления: 2014-01-04