Основы метода

Будем рассматривать каноническую форму задачи линейного программирования.

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

Тогда задача II запишется так:

Найти решение Х системы уравнений:

 

(1)

 

удовлетворяющее условиям неотрицательности

x₁ ≥ 0; x₂ ≥ 0; …, x_k ≥ 0; …, x_n ≥ 0; (2)

и максимизирующее линейную функцию

z — с₁х₁ — с₂х₂ — . . . — с_kх_k — . . . — с_nх_n =—с₀ (3)

Допустим, что в системе (1) все свободные члены неотрицательны, т. е. выполняется неравенство b_i ≥ 0, для i = 1, 2, ..., r. (4)

Тогда системе (1) соответствует исходное опорное решение

= (b₁, b₂ . . . b_i , 0, . . . 0). (5)

Подставляя это решение в равенство (3), вычислим соответствующее исходное значение функции z⁰ = z( ) = с₁а₁₀ + . . . + с_rа_r0. Преобразуем функцию z так, чтобы она зависела только от свободных переменных х_r+1, х_r+2, . . ., х_n.

Для этого умножим первое уравнение системы (1) на с₁, второе — на с₂ и т. д., r-е. уравнение — на с_r, и сложим с равенством (3).

В результате получим

Z + a_0r+1х_r+1 + а_0r+2+x_r+2 +... + а_0k x_k+ . . .a_0n x_n=а₀₀, (6)

где b_0k= - с_k (для k=r + 1, r + 2, . . .,n , 0). (7)

Будем называть равенство (6) приведенным (к свободным переменным) выражением для функции z, а коэффициенты а_0k- — оценками соответствующих свободных переменных х_k.

Способ образования приведенного выражения для функции Z остается в силе и в том случае, когда номер базисной переменной не совпадает с номером уравнения, т. е. когда, например, первое уравнение разрешено относительно х₃, второе — относительно х₈ и т. д. . Следует лишь в формуле (7) величины с_i рассматривать не как коэффициенты при i-й переменной, а как коэффициенты в равенстве (З) при базисной переменной, относительно которой разрешено i-е уравнение. Приведенное выражение (6) позволяет сразу без дополнительных расчетов определить значение z⁰, соответствующее опорному решению (5): z₀+z( )=a₀₀.

Равенство (6) формально не отличается от уравнений системы (1). Поэтому будем рассматривать его как «нулевое» уравнение, разрешенное относительно дополнительной базисной переменной z. Добавив его к системе (1), получим расширенную систему:

Заметим, что столбец свободных членов системы (8) содержит полную информацию на данном этапе расчета: первые r его членов определяют исходное опорное решение , а последний член — соответствующее значение целевой функции z⁰.

 

 

Выполним теперь одно симплексное преобразование этой системы при условии, чтобы последнее уравнение не выбиралось в качестве разрешающего (т. е. чтобы z все время оставалось в качестве базисной переменной). При выполнении этого преобразования разрешающий столбец выбирался произвольно, лишь бы он содержал хотя бы один положительный элемент а_ip, > 0. По причинам, которые выяснятся ниже, дополним алгоритм преобразований условием выбора разрешающего столбца по отрицательной оценке а_0p.

С этим дополнением алгоритм симплексных преобразований включает следующие основные пункты:

1. Выбирается разрешающий столбец а_p из условий: оценка а_0p < 0 и хотя бы один элемент аiр > 0. (9)

2. Выбирается разрешающая q-я строка из условия:

(10)

для a_ip>0

З. Производится пересчет элементов разрешающей строки по формуле

(11)

 

4. Вычисляются элементы всех остальных строк (при k ≠ p) по формуле

(12)

После выполнения одной итерации придем к новой системе уравнений, приведенной к новому единичному базису. Этот новый базис состоит, как и исходный, из единичных векторов и вместо вектора включает единичный вектор . Иными словами, новыми базисными переменными окажутся x₁,x₂,…,x_q-1,x_q+1,…,x_r и переменная x_p (заменившая переменную x_q ) Соответствующее преобразованной системе, новое опорное решение будет

 

(13)

и новое значение функции z:

 

(14)

 

Подставляя в (14) значение а0 из (12) и вычитая из нового значения функции исходное, получим изменение функции, достигнутое в результате данной итерации,

(15)

 

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

Будем полагать вначале, что ни один из свободных членов системы (1) и систем, получаемых после очередных итераций, не обращается в нуль.

Случай, когда какой-нибудь из свободных членов а_i0 = 0 приводит к так называемому вырожденному решению.

Подставляя значение в равенство (15) и разделив на получим

(16)

Таким образом, оценка а_0р свободной переменной x_р характеризует изменение целевой функции z, приходящееся на каждую единицу изменения значения переменной х_р. Этим и объясняется термин “оценка”.

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

Этим объясняется дополнительное условие выбора разрешающего столбца, включенное в п. 1 алгоритма. Если бы решалась задача минимизации функции z, то, очевидно, разрешающий столбец следовало бы выбирать по положительной оценке а_0р.