Замечания. Теорема 6. Если - угловая точка области допустимых значений решений задачи линейного программирования (4)

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

Теорема 5. Если известно, что система векторов-столбцов линейно независима и такова, что, где все, то точка является угловой точкой выпуклого множества решений задачи линейного программирования (4).

Пример 4. Пусть дана задача линейного программирования в координатной канонической форме:

Исходные данные задачи:

					–5 –9
		–3	–5	–1

Столбцы матрицы ограничений имеют вид:

Столбцы и - базисные столбцы, переменные - базисные.

Тогда ограничения 2) запишутся в векторной форме виде:

или в матричной форме:

или

Поскольку количество ограничений =2, то число линейно независимых столбцов не может быть больше 2.

1.В дальнейшем совокупность линейно-независимых столбцов порядка матрицы условий задачи (4), которым соответствуют положительные компоненты угловой точки множества допустимых решений, будем называть базисом задачи (4). Все остальные столбцы и соответствующие им переменные будут называться небазисными. При этом некоторые базисные переменные могут принимать нулевые значения (такие решения называют вырожденные).

2.Задача линейного программирования может иметь базисы, в которых могут быть отрицательные компоненты решения. Такие базисы будем называть посторонними.

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