Линейное программирование

Дана задача линейного программирования

[pic 1]

1. Найти все базисные решения системы, используя теорему о замене базисного вектора.
2. Определить все угловые точки допустимого множества данной задачи. Пронумеровать найденные угловые точки. Предполагая, что данная задача имеет решение, найти ее оптимальные решения (maxf и minf) методом полного перебора

[pic 2]

Запишем расширенную матрицу системы

[pic 3]

Рассмотрим столбцы , данной системы и составим из них все наборы, содержащие по три столбца. Получим список из десяти наборов:[pic 4]

[pic 5]

[pic 6]

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

Теорема «о замене базисного вектора». Пусть векторы  образуют базис в . Заменим в этом базисе какой-либо из векторов (например ) на любой вектор [pic 7][pic 8][pic 9][pic 10]

[pic 11]

Тогда полученная система векторов будет базисом этого пространства тогда и только тогда, когда в разложении вектора  по исходному базису коэффициента  при рассматриваемом векторе отличен от 0:[pic 12][pic 13]

[pic 14]

Убедимся что (1) является базисным:

Методом Жордана-Гаусса перейдем от расширенной матрицы данной системы к расширенной матрице равносильной системы с единичным базисом.

[pic 15]

В ходе вычислений столбцы , преобразовались в единичные столбцы.[pic 16]

Следовательно, набор столбцов линейно независим и образует базис некоторого опорного решения (текущий базис).[pic 17]

[pic 18]

Используя теорему о замене базисного вектора получим следующий базис

[pic 19]

Следовательно, набор столбцов линейно независим и образует базис некоторого опорного решения (текущий базис)[pic 20]

[pic 21]

Получим следующий базис:

[pic 22]

Следовательно, набор столбцов линейно независим и образует базис некоторого опорного решения (текущий базис).[pic 23]

[pic 24]

Т.к. в разложении для второй строки коэффициент при векторе , следовательно система векторов  не является базисом[pic 25][pic 26]

Получим следующий базис: