Условие (ХД < (UB), эквивалентно неравенству

(в-ьх-св-рджид,

которое будет выполняться, если

(B-b),-(U,),

х <8, = тЫ - 1 (В-РД.

(В~РД. <0

Наконец, третье условие будет выполнено, если выполняется неравенство х < иг Все три неравенства относительно х. можно обобщить в виде следующего условия.

лгу = тт{в1( 92, и).

Базис, формируемый для следующей итерации, зависит от того, какое значение (в 02 или цу) примет переменная дс.. Предполагая, что (Хв)г- исключаемая переменная, получаем следующие правила формирования базиса.

1. Если х. = Gj, то переменная (Хв)г исключается из базиса и принимает нулевое значение. Новый базис формируется точно так же, как в обычном симплекс-методе с вводимой переменной дг и исключаемой (Хв)г.

2. Если Xj = 62, переменная (Хв)г исключается из базиса и принимает значение своей верхней границы. Новый базис формируется точно так же, как в обычном симплекс-методе, но с учетом того, что переменная (Хв)г равна верхней границе. Поскольку значения 0j и 62 получены при условии, что все небазисные переменные равны нулю, необходимо выполнить преобразование новой небазисной переменной (Хв)г, чтобы она также приняла нулевое значение.

Это достигается с помощью подстановки (XB)r= (UB)r- (Х )г, где (Хй)>0.

Не имеет особого значения, когда выполняется эта подстановка: до или после вычисления нового базиса.

3. Если Xj = ujt то базисный вектор Хв остается неизменным, поскольку в данном случае никакая из текущих базисных переменных не принимает ни нулевого значения, ни значения своей верхней границы. Таким образом, переменная х} остается небазисной, но со значением своего верхнего предела. После подстановки дс = ы; - xj выполняется следующая итерация симплекс-метода.

В случае равенства значений 0 02 и uf выбор правила, в соответствии с которым переходим к следующей итерации симплекс-метода, произволен. Вместе с тем предпочтительнее использовать третье правило (деу = так как в этом случае требуется выполнить меньший объем вычислений.

Подстановка дсу = uj - xt изменяет исходные значения с\, Ру и b на cj = -cjt PJ = -Pj

и b = b - u Py. Это означает, что при выполнении модифицированного симплекс-метода на каждой итерации все вычисления (таких величин, как В 1, Хв и zy-cv) должны основываться на измененных значениях С, А и b (более подробно этот вопрос рассмотрен в упражнении 7.3.1.5).

Пример 7.3.1

Решим следующую задачу ЛП вышеописанным методом решения задач с ограниченными переменными.

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

х,+у + 2x3<14,

2 л:, + 4у + 3х3<43,

О < х, < 4, 7 < у < 10, 0 < х3 < 3.

Поскольку переменная у ограничена положительной константой не только сверху, но и снизу, производим замену у = х2 + 7, где 0 < х2 < 10 - 7 = 3.

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

Итерация 0

Базис Xi хг хз Х4 х5 Решение

z -3 -5 -2 0 0 35

xt 112 10 7

хъ 2 4 3 0 1 15

Имеем В = В 1 = I и Хв = (л:4, л:5)г = B~b = (7,15). Принимая переменную х2 в качестве вводимой в базис переменной (z2 -с2 = -5), получаем B~lP2 = (1, 4). Отсюда следует

02 = °° (поскольку В 1Р2 > 0).

Так как по условию л:2 < 3, получаем значение, принимаемое переменной х2.

х2 = min{3,75, ее, 3} = 3 = иг.

Поскольку л:2 = и2, базис остается неизменным; переменная х2 в базис не вводится (остается небазисной), но принимает значение своей верхней границы. После подстановки х2 = 3 - х\ получаем новую симплекс-таблицу.

Выполненная подстановка изменяет исходный вектор правых частей ограничений с Ь = (7, 15)г на Ь = (4, 3)г. Эти изменения должны учитываться в последующих вычислениях.

Максимизировать z = Зл:, + 5у + 2х.

8, = ггагн-, - > = 3,75 , что соответствует переменной хй,

Итерация 1. Определяем вводимую в базис переменную де,. Базисный вектор Хв и обратная матрица В 1 (= I) такие же, как на предыдущей итерации. Вычисляем

в-р.-а.г).

Отсюда следует

6, = rran j у, - > = 1,5 , что соответствует переменной де5,

92 = оо (поскольку В-1Р, > 0).

Так как по условию задачи де, < 4, получаем значение, принимаемое переменной де,.

jeI-min{l,5,oo, 4} = 1,5 (=9,).

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

Итерация 2. Имеем новую обратную матрицу.

В =

Значения базисных переменных определяются так:

Хв = (*4> xj = В1 V = (5/2, 3/2)т,

где Ь = (4, 3)г- значения правых частей ограничений, вычисленные в конце нулевой итерации.

Определяем хг как вводимую в базис переменную. Учитывая, что К = -Р2, получаем

Далее вычисляем

5 2 1

Вр; =(1,-2)г

= 2,5 , что соответствует базисной переменной дс4,

= 1,25 , что соответствует базисной переменной хг.

Так как по условию хг < 3, получаем значение, принимаемое переменной х\.

х2 = min{2,5,1,25, 3} = 1,25 (= 82).