19. Основные понятия, связанные с симплекс методом. Обозначения плана. Опорный план

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

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

Система ограничений задачи линейного программирования в канонической форме имеет вид

, (1) где B = ( b 1 , ..., B M ) T , A J = ( A 1J , ..., A MJ ) T , ( j = 1, ..., n ) - известные векторы, T - знак транспонирование, а X = ( x 1 , ..., X N ) - вектор переменных. Решение X *является опорным планом тогда и только тогда, когда множество векторов A J , для которых X J * > 0, линейно независима.

Количество положительных компонент опорного плана не превышает m . Если количество этих компонент равна m , опорный план называется невырожденным, а множество соответствующих векторов A J образует базис . Множество A J 1 , ..., A J M является базисом задачи линейного программирования с ограничениями (1) тогда и только тогда, когда система имеет единственное решение, и X J и ≥ 0, i = 1, ..., m .

Разным опорным планам соответствуют разные базисы. Обратное утверждение верно лишь в случае невироджености всех опорных планов системы (1).

21. Общая характеристика симплекс метода

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.  Общая идея симплексного метода (ме­тода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит из: -умение находить начальный опорный план; -наличие признака оптимальности опорного пла­на; -умение переходить к нехудшему опорному плану.

22. Схема применеия симплекс метода для злп в канонической форме

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.

Данная формальная модель задачи линейного программирования обычно задается в форме, так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода

23. Метод искусственного базиса(М-метод) используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств.

Рассмотрим задачу:

max{F(x)=∑c_ix_i|∑a_jix_i=b_j, j=1,m; x_i≥0}.

В ограничения и в функцию цели вводят так называемые «искусственные переменные» R_j следующим образом: ∑a_jix+R_j=b_j, j=1,m;F(x)=∑c_ix_i-M∑R_j

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑c_ix_i, , а другая – для составляющей M ∑R_j