Теоретические основы линейного программирования

Рассмотрим каноническую задачу линейного программирования (КЗЛП)

(2.22)

Будем в дальнейшем считать, что ранг матрицы А системы уравнений равен m, причем m< n.

Запишем КЗЛП в векторной форме:

(2.23)

(2.24)

(2.25)

где - j-й столбец матрицы А.

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

Согласно определению и предположению о том, что r(A)=m, всякому опорному плану задачи линейного программирования (как и всякому базисному решению системы линейных уравнений ) соответствует базисная подматрица В порядка m матрицы А и определенный набор m базисных переменных системы линейных уравнений .

Определение 2.15. m компонент базисного решения системы линейных уравнений , являющихся значениями соответствующих ему базисных переменных, будем называть базисными компонентами этого решения.

Отметим, что базисные компоненты опорного плана неотрицательны; остальные (n-m) его компонент равны нулю. Очевидно, что число опорных планов задачи линейного программирования конечно и не превышает . Число строго положительных компонент опорного плана не превышает m.

Определение 2.16. ОП ЗЛП, число строго положительных компонент которого равно m (), будем называть невырожденным ОП. В противном

случае ОП ЗЛП вырожденный.

Определение 2.17. Опорным планом ЗЛП будем называть такой план ,

что векторы , входящие в разложение

со строго положительными , линейно независимы.