logo search
Глава 3

3.1 Векторная запись задачи линейного программирования. Опорный план

Система ограничений задачи линейного программирования, приведенной к канонической или стандартной форме, может быть записана в векторной формеследующим образом:

(13)

,

где Аj =- векторные коэффициенты; B=, X=,R{;;=}.

Будем считать, что система ограничений задачи в канонической форме представляет собой линейно независимую систему уравнений (в противном случае часть уравнений можно просто вычеркнуть).

Опорным планомзадачи линейного программирования в канонической форме называется такой допустимый план, совокупность векторных коэффициентов при ненулевых компонентах которого представляет собой систему линейно независимых векторов*.

Например, представим систему ограничений задачи, записанной в канонической форме, в векторной форме:

2х1+ 3х2- х3 + х4 = 5

4х1+ 6х2+ 2х3 + х5 = 10

х1-50

А1=, А2=, А3=, А4=, А5=, В =, Х =;

.

Рассмотрим план Х(1) = (0; 0; 0; 5; 10). Этот план является допустимым, в чем легко убедиться, подставив его в систему ограничений:

2*0 + 3*0 - 0 + 5 = 5

4*0 + 6*0 + 2*0 + 10 = 10

0 0

5 0

10 0

Отличными от нуля являются переменные х4 и х5. Векторные коэффициенты при этих переменных А4=и А5=являются линейно независимыми. В самом деле,. Следовательно, план Х(1) является опорным.

Убедимся в том, что отнюдь не любой допустимый план является опорным. Для этого рассмотрим другой план Х(2) = (1; 1; 0; 0; 0). Здесь ненулевыми компонентами плана являются переменные х1 и х2. Этот план тоже является допустимым:

2*1 + 3*1 - 0 + 0 = 5

4*1 + 6*1 + 2*0 + 0 = 10

1 0

0 0

Однако этот план не является опорным, так как можно подобрать отличные от нуля числа d1и d2, при которых d1А1+ d2А2 = d1+d2=. Таких чисел бесконечно много, например, d1= 3, d2= -2.

Можно доказать [6], что каждой вершине ОДП задачи линейного программирования соответствует опорный план. Поэтому, чтобы найти оптимальный план в одной из вершин, симплекс-метод перебирает именно опорные планы задачи линейного программирования.

Очевидно, что ненулевых компонент в опорном плане может быть не больше, чем ограничений в задаче (в рассмотренном примере невозможно построить три двумерных линейно независимых вектора, поэтому ненулевых компонент не может быть больше двух). Для реализации симплекс-метода необходимо, чтобы в опорном плане присутствовало ровно mлинейно независимых векторов, т.е. базисm–мерного пространства. В случае, если ненулевых компонент в опорном плане меньше, чемm, один или несколько из этих векторов могут соответствовать и нулевым переменным.Переменные, столбцы коэффициентов при которых образуют полную систему (m) единичных независимых столбцов, будем называтьбазисными(хБ), а остальные переменные -небазисными.Столбцы (вектора), соответствующие базисным переменным, также будем называтьбазисными. Совокупность этих переменных (или этих векторов) будем называтьбазисом. Если среди базисных переменных есть нулевые, базис называютвырожденным.

Например, в плане Х(1)в базис входили переменные х4 и х5, и базис был невырожденным.