Этому плану согласно (8:24) соотвествует значение целевой ф-и f(X) = f(X(0)) (fj cj) (8:25)

Так как по условию теоремы fj cj > 0 и > 0, то

f(X) < f(X(0))

Следствие. Если в задаче на минимум для некоторого плана X(0) разложение всех векторов Aj j = 1; :::; n в данном базисе удовлетворяют условию

fj cj 6 0 (8:26)

то план x(0) является оптимальным. Разности fj cj называются оценками плана.

Для задачи на максимум ф-и f cправедлива аналогичная предыдущей теорема:

Теорема 8.2. Если в задаче на максимум для некоторого вектора Aj выполняется условие fj cj < 0, то план X(0) не является оптимальным и можно построить такой план X, для которого выполняется условие f(X) > f(X(0))

Следствие. Если в задаче на максимум для некоторого плана X(0) разложение всех векторов Aj j = 1; 2; :::; n в данном базисе удовлетворяют условию fj cj > 0 (8:27), то план X(0)является оптимальным.

27.3Алгоритм симплексного метода. Симплексная таблица

Пусть как и раньше задача (8:6) (8:8) на отыскание минимума целевой ф-и f первоначальнвй опорный план

X(0) = (x1 = b1; x2 = b2; :::; xm = bm; xm+1 = 0; :::; xn = 0)

описывается системой m-мерных единичных векторов A1; A2; :::; Am. Для исследования этого опорного плана на оптимальность необходимо все векторы Aj j = 1; 2; :::; m системы (8:7) разложить по векторам базиса и подсчитать значения оценок

fj cj

Так как данный базис был единичным, то компоненты вектора Aj равны

xij = aij i = 1; 2; :::; m j = 1; 2; :::; n

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

27.3.1Правила заполнения таблицы

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

2.В столбце A0 записывается первоначальный опорный план X(0). В этом же столбце в результате вычислений получают оптимальный план

3.В столбцах Aj j = 1; 2; :::; n записывают коэффициенты разложения j-отого вектора по базису

4.В яйчейке на пересечении m + 1 строки и столбца A0 записывают значения целевой ф-и f(X), которые она принимает при найденном опорном плане. А в яйчейках стоящих на пересечении m + 1 строки и столбцов Aj записывают значения оценок fj cj

55

Если положительных оценок несколько, то в базис должен быть включен вектор, которому соответствует величина

max[ 0j(fj cj)]

j

максимум берется по тем индексам j для которых

fj cj > 0

и величина 0j определяется для каждого такого индекса j.

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

27.3.3Переход к новому опорному плану

Пусть

max[ 0j(fj cj)] = 0k(fk ck)

j

тогда в базис включается вектор Ak и исключается вектор, соотвествующий минимуму

0k = min xi

i xik

Допустим что минимум достигается для вектора базиса, стоящего в строке с номером l. Тогда вектор Al исключается из базиса.

Элемент xlk называется разрешающим. Столбец и строка в которых он находится, называются направляющими.

Новому опорному плану будет соотвествовать базис

A1; A2; :::; Al 1; Ak; Al+1; :::; Am

Рассмотрим вопрос о вычислении нового опорного базиса. Первоначальный базис был единичным A1; A2; :::; Am. Поэтому

A0 = x1A1 + ::: + xlAl + ::: + xmAm (8:28)

Ak = x1kA1 + ::: + xlkAl + ::: + xmkAm (8:29)

и произвольный вектор Aj разлагается так

Aj = x1jA1 + ::: + xljAl + ::: + xmjAm(8:30)

Из (8:29) получим

Al = x1 (Ak x1kA1 ::: xl 1;kAl 1 xl+1;kAl+1 ::: xmkAm) (8:31)

lk

Подставляя полученные значения Al в (8:28) получим

A0 = x1A1+:::+xl 1Al 1+xl x1 (Ak x1kA1 ::: xl 1;kAl 1 xl+1;kAl+1 ::: xmkAm)+xl+1Al+1+:::+xmAm

lk

Поэтому новый опорный план, равный

X0 = (x01; x02; :::; x0k; :::; x0m)

вычисляется по формулам

По аналогии выводятся формулы для коэффициентов разложения всех векторов по векторам нового базиса. Эти формулы имеют вид

56