4.4. Опорное решение задачи линейного программирования,

его взаимосвязь с угловыми точками.

Рассмотрим каноническую задачу ЛП в векторной записи (см.(2.1.2)):

, ,(4.4.1)

.

Определение 4.4.1.Опорным решением задачи ЛПназывается такое допустимое решение, для которого соответствующие положительным координатамвекторы,,…,в (4.4.1) линейно независимы.

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

Определение 4.4.2.Базисом опорного решения называется базис системы векторов условия задачи (4.4.1), в состав которого входят векторы, соответствующие отличным от нуля координатам опорного решения.

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

Теорема 4.4.1.Любое опорное решение является угловой точкой области допустимых решений.

Теорема 4.4.2.Любая угловая точка области допустимых решений является опорным решением.

Доказательства теорем 4.4.1 и 4.4.2 проводятся методом от противного (см. [3], с.537-539).