На основании В = (Р Р2) имеем Х, = (х х/ и Св = (1,4). Вычисляем обратную матрицу В 1:

Находим текущее базисное решение

3 -1

х.=Г I = в ь =

5 5 3 2 v5 5J

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

(±0(2 1 2 Л) (1 0 0 2 В (Р Р,.Р Р4)= < 5

1 3 4 1 -МЗ -1 -2 6 [0 1 2 0

Теперь находим коэффициенты г-строки симплекс-таблицы:

Св[В-,(Р1.Р2,Рз,Р4)]-С = (1,4) ° ° -(1,4,7,5) = (0.0.1.-3). Наконец, вычисляем значение целевой функции:

г = СйВ-,Ь = СвХв=(1,4)

= 19 ,

Таким образом, получаем значения следующей симплекс-таблицы.

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

УПРАЖНЕНИЯ 7.1.3

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

2. Дана следующая задача ЛП.

Максимизировать г = 5xt + 12х2 + 4х3

при ограничениях

х, + 2х2 + х3 + х4 = 10,

3* 4 ~

Определите, какие из следующих наборов векторов образуют базис: (Р Р2),

(р2, р3), (р3, р4).

3. Дана следующая задача ЛП.

Минимизировать г = 2хх + х2

при ограничениях

Зяг, -(- х2 - х3 3, 4л:, + Зл;2 - х4 = 6, х, + 2лг2 + хь = 3, х х2, ят3, х4, я:5 > 0.

Вычислите симплекс-таблицу, соответствующую Хв = (xv х2, хь)Г, и определите, будет ли это решение допустимым и оптимальным.

4. Дана следующая симплекс-таблица с оптимальным решением задачи ЛП.

Здесь переменные ха, xt и хь являются дополнительными (остаточными). С помощью матричных вычислений реконструируйте исходную задачу ЛП, затем вычислите оптимальное значение целевой функции.

5. В стандартной задаче ЛП разобьем вектор X на два - X = (X Х )т. Здесь вектор Х соответствует начальному базисному решению, состоящему из дополнительных и искусственных переменных (так что В = I). Тогда матрицу А можно представить как А = (D, I). Вектор С также разделим на два вектора С, и С в соответствии с векторами X, и Х . Покажите, что в этом случае симплекс-таблицу можно записать в следующем виде, который в точности соответствует виду симплекс-таблицы из главы 3.

7.2. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

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

Модифицированный симплекс-метод предусматривает выполнение точно таких же этапов, как и обычный табличный симплекс-метод, описанный в главе 3. Основное отличие между ними заключается в том, что в обычном симплекс-методе при переходе от одного базиса к другому используется процедура преобразования строк симплекс-таблицы с помощью метода Гаусса-Жордана, тогда как

в модифицированном симплекс-методе эти преобразования осуществляются путем вычисления обратной матрицы В-1, и основные действия связаны именно с вычислением этой матрицы.

7.2.1. Условия оптимальности и допустимости

Рассмотрим стандартную задачу ЛП.

Максимизировать или минимизировать г = СХ при ограничениях PjX, =b, х.>

0,j= 1, 2, га.

Для данного базисного вектора Хв и соответствующих базиса В и вектора коэффициентов целевой функции Св на каждой итерации вычисления значений симплекс-таблицы выполняются по следующим формулам (см. раздел 7.1.2).

г + £ц-су)*;=св в-ь

(XB)i+X(B-PJ),x;=(B-1b)l,

где Zj - с\ = СВВ~!Р; - с\. Здесь запись (V), используется для обозначения t-ro элемента вектора V.

Условие оптимальности симплекс-метода. Из уравнения для значений z-строки, приведенного выше, следует, что увеличение значения небазисной переменной xf приводит к возрастанию (убыванию) значения целевой функции z выше текущего значения СВВ 1Ь только в том случае, если разность zj - с\ строго отрицательна в задаче максимизации или строго положительна в задаче минимизации. В противном случае переменная не может улучшить текущее решение и должна остаться небазисной с нулевым значением. Таким образом, любая небазисная переменная, удовлетворяющая этому условию, может быть включена в базис, что, возможно, улучшит значение целевой функции. В симплекс-методе действует эмпирическое правило, которое гласит, что в качестве вводимой в базис переменной выбирается переменная, которой соответствует наибольший (по модулю) отрицательный коэффициент г - с\ в z-строке в задаче максимизации или наибольший положительный аналогичный коэффициент в задаче минимизации.

Условие допустимости симплекс-метода. Определение исключаемого из базиса вектора основано на проверке ограничения, представленного в виде равенства, соответствующего i-й базисной переменной. Это равенство имеет следующий вид.

(ХД.+В-РДхВ-Ь),.

Обозначим через Рк вводимый вектор, определенный из условия оптимальности, а через хк - вводимую в базис переменную, принимающую положительное значение. Поскольку все остальные небазисные переменные сохраняют нулевые значения, равенство ограничения, соответствующее базисной переменной (Хв) можно записать следующим образом.

(Хв), = (В-1Ь),-(В-1РДх4 Это уравнение показывает, что при (В~РД > 0 возрастание переменной хк не приведет к отрицательному значению базисной переменной (Хв)( только в том случае, если будет выполняться неравенство

(B b), - (В 1РД хк > 0 для всех L