7. Свойства решения задач лп

Все методы решения задач предполагают перед началом решения следующие преобразования

1. Все ограничения в виде неравенств преобразовываются в равенства (те представляют ограничения в каноническом виде) путем

-добавляются неотрицат остаточные переменные в левую часть нер-ва <=

-вычитанием неотрицат избыточной переменной из левой части нер-ва вида >=

В отечественной лит-р в том и другом случае используется термин свободная переменная

2. Все правые части нер-в делаю неотриц-ми, умножая для этого ур-ие на (-1), если bi<0.

Как правило, учитывая большую размерность практических задач, наиболее удобной для задач ЛП является ее запись в матричном представлении. В этом случае задача выглядит следующим образом:

Максимизировать целквую ф-ию вида

Y=Cxmax при ограничениях Ax=b , x>=0

Компонентами в-ра Х явл управляемые переменные, которые в общем случае не только исходные, но и остаточные и избыточные переменные. Матрица А содержит также и коэф-ты при свободных членах. Очень часто при изложении решения задач ЛП используется понятие расширенной матрицы Ав, которая получается из исходной матрицы путем добавления столбца свободных членов.

Другой удобной формой записи задач ЛП является ее векторное представление

Обозначим матрицу А в следующем виде

A=(p1, p2,….pn)

P1-pn – столбцы матрицы А , которые обычно называются производственными векторами

Тогда задача ЛП запишется :

Y=Cjxjmax при ограничениях pj*xj=b xj>=0

Можно считать, что

- если в реальной задаче m>n – то в системе ограничений, по крайней мере (m-n) уравнений явл избыточными.

-если m=n и А- это матрица полного ранга (ранг матрицы – количество строк или столбцов линейнго независимы, r(A)=n – матрица полного ранга), то система имеет единственное решение.

-если m<n, то система Ax=b , имеет бесконечное мно-во решений

- если Ax=b несочместимая система, то задача вообще не имеет решений.

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

Теорема 1

Конечное оптимальное решение задач ЛП должно соот-ть допустимой экстремальной точке пространства решений.

Теорема 2

Базисным решением системы полностью определяют все ее экстремальные точки.

Базисное решение определяется базисомм, те m независимыми векторами pj. В общем случае все экстремальные точки мб найдены путем перебора всех допустимых базисных решений системы. В любой экстремальной точке переменная xj , соответствующая в-ру pj, не входящему в базис, равна 0. Такую переменную называют небазисной .

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

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

Нахождение экстремальных точек с помощью базисных решений системы Ax=b являются основой симплекс-метода.

В данном методе вместо простого перебора всех базисных решений, предполагается выбор допустимого базисного решения, на основе которого генерерируются новые допустимые базисные решения , каждое из которых отвечает условию x>=0 и дает значение целевой ф-ии, не меньшее, чем предыдущее.

То что оптимальное решение задачи ЛП, определяемое симплекс-методом, явл допустимым базисным решением – это особенность симплекс-метода, который определяет кол-во ненулевых переменных в решении. Если исходная система имела только одно ограничение, то в оптиальном решении, положительное значение может иметь только одна из переменных задач. Если добавляется еще одно ограничение, не явл избыточным, то положительное значение имеют не более 2 переменных и тд.