6. Прямой алгоритм с искусственными переменными

1. Рассмотрим теперь прямой алгоритм симплексно­го метода для случая, когда каноническая форма полу­чается путем введения в уравнения системы искусствен­ных переменных. Предварительно исходную систему уравнений преобразуем так, чтобы все свободные члены b_j были неотрицательны. Пусть дана задача линейного программирования в стандартной форме:

найти

x_j0 (j=1,2, … , n) (6.1)

при условиях

(6.2)

c₁x₁ + c₂x₂ + ··· c_nx_n = z  min (6.3)

Введем в уравнение системы (6.2) базисное множество искусственных переменных x_n+i≥0 (i = 1, 2, … ,m). Кро­ме того, в целевой функции перенесем z в левую часть со знаком минус и, таким образом, приравняем (6.3) нулю; получим расширенную систему уравнений;

(6.4)

и

x_j0 (j=1,2, … , n, n+1, … , n+m) (6.5)

Сумму искусственных переменных (обозначим ее че­рез u)

x_n+1 + x_n+2 + ··· + x_n+m = u (6.6)

будем называть, искусственной линейной формой (или u-уравнением).

Исключим переменные x_n+1, x_n+2, … , x_n+m из u-уравнения, вычитая из него сумму первых m уравнений рас­ширенной системы (иначе говоря, находим значения искусственных переменных из уравнений расширенной системы и подставляем их в искусственную форму). Тогда коэффициенты при x₁, x₂, … ,x_n будут соответст­венно равны: d₁= –(a₁₁+a₁₂+…+a_m1), d₂= –(a₁₂+a₂₂+…+a_m2), … , d_j= –(a_1j+a_2j+…+a_mj), … , d_n= –(a_1n+a_2n+…+a_mn). Перенесем u в левую часть (со знаком минус), а свободный член — в правую часть с обратным знаком; будем иметь:

d₁x₁+d₂x₂+···+d_nx_n+u₀=u, где

u₀=b₁+b₂+···b_m,

или d₁x₁+d₂x₂+···+d_nx_n+(-u)=u₀ (6.7)

Добавив к расширенной системе уравнений (6.4) пре­образованное u-уравнение (искусственную форму), по­лучим следующую каноническую форму:

(6.8)

Используем алгоритм, описанный в пп. 1, 2, 3 описания прямого симплекс-метода, для получения решения системы (6.4)–(6.5), которое дает минимальное значение u.

Составим начальную таблицу 2 по аналогии с ра­нее составлявшейся таблице с той лишь разницей, что дополняем, её еще одной стро­кой, в клетки которой вписываем коэффициенты d_j u-уравнения (6.7). Таким образом, первоначальную табли­цу 2 заполняем соответствующими коэффициентами канонической формы (6.8), при этом в клетках, относя­щихся к базисным переменным, нули писать не будем.

2. Пусть дана стандартная форма задачи линейного программирования (в сокращенной записи):

найти

x_j0 (j=1,2, … , n) (6.9)

при условиях

(i=1,2, … , m), (6.10)

дающих

, (6.11)

при этом

b_i0 (i=1, 2, … , m). (6.12)

Введем искусственные переменные х_n+j, связанные с x₁, x₂, … , x_n; получим расширенную систему:

(i=1, 2, … , m), (6.13)

, (6.14)

x_j0 (j=1,2, … , n, n+1, … , n+m). (6.15)

Как было принято, искусственная линейная форма (сумма искусственных переменных) есть

x_n+1+ x_n+2+…+ x_n+m=u (6.16)

Теперь задача состоит в том, чтобы найти минималь­ное значение u. Для этого используем алгоритм, описан­ный в описании прямого симплекс-метода, чтобы получить решение системы (6.13)—(6.15), которое дает минимальное значение искусственной линейной формы u. При условии x_n+1=0, x_n+2=0, … , x_n+m=0 очевидно, решение системы (13) эквивалентно системе (10).

В системе (6.13) искусственные переменные x_n+i (i=l, 2, …, m) образуют базис. Путем преобразований указанной системы искусственные базисные переменные x_n+i будут переходить в число небазисных переменных, а последние вводятся в базис вместо искусственных переменных. Переход от одного базиса к другому на не­которой итерации приведет к тому, что базис не будет содержать ни одной искусственной переменной. Этот переход осуществляется путем применения указанного алгоритма; при этом решается задача о минимизации u.

Действительно, указанный алгоритм можно приме­нить, поскольку расширенная система представляет ка­ноническую форму с базисом (x_n+1, x_n+2, … , x_n+m). Чёрез некоторое число итераций соответствующее базисное решение даст min u. При этом минимальное значение целевой функции может быть или положительным, или равным нулю, так как u есть сумма неотрицательных переменных. В самом деле, так как u≥0, то и min u≥0.

В случае если окажется min u>0, то задача не име­ет допустимого решения. В самом деле, поскольку система (6.13)—(6.14) не имеет неотрицательных решений, для которых x_n+1=0, x_n+2=0, … , x_n+m=0 (тогда min u=0), то и исходная система также не имеет неотрицательных решений, и процесс решения на этом заканчивается.

Если min u=0, то для минимального значения u ре­шение будет (, , …, , , …, ), так как из условия ++…+=min u=0 следует =0, =0, … , =0. Следовательно, (, , …, ) есть неотрицательное решение исходной формы системы, при этом среди компонент , , …, не более m отличных от нуля. Решение начинаем следую­щим образом:

исключаем из дальнейшего рассмотрения все не базисные переменные, соответствующие u-строке табли­цы 2 положительным (не нулевым) коэффициентам d_j;

заменяем искусственную форму и линейной формой z, которая получается после исключения из u-строки всех базисных переменных.

Отметим, что искусственную переменную, исключен­ную из базиса в результате некоторой итерации, не сле­дует в дальнейшем вводить ни в один из последующих базисов; поэтому нет необходимости делать преобразо­вания последних m столбцов.

Таким образом, вычисления начинаем с расширенной задачи. После того как выяснится, что в u-строке таб­лицы достигнут min=0, приходим к решению исходной задачи.

Решение задачи линейного программирования пря­мым алгоритмом симплексного метода с введением в ее стандартную форму искусственных переменных нагляд­но показано в блок-схеме 2.

Блок-схема 2

Алгоритм прямого (с искусственными переменными) симплекс-метода.

Таблица 2

Симплекс-таблица (исходная).

Базисн. перем.

x1

x2

…

xj

…

xk

…

xn

xn+1

…

xn+i

…

xn+m

(-z)

(-u)

Свободн. члены

xn+1

a11

a12

…

a1j

…

a1k

…

a1n

1

…

…

b1

xn+2

a21

a22

…

a2j

…

a2k

…

a2n

…

…

b2

…

…

xn+i

a n+i,1

an+i,2

…

an+i,j

…

an+i,k

…

an+i,n

…

1

…

bi

…

…

xn+r

a n+r,1

an+r,2

…

an+r,j

…

an+r,k

…

an+r,n

…

…

br

…

…

xn+m

an+m,1

an+m,2

…

an+m,j

…

an+m,k

…

an+m,n

…

…

1

bm

(-z)

c1

c2

…

cj

…

ck

…

cn

…

…

1

0

(-u)

d1

d2

…

dj

…

dk

…

dn

…

…

1

(-u0)

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА.

1. Горстко А. Б. Познакомьтесь с математическим моделированием.

- М.: Знание , 1991. – 160 с.: ил.

2. Вершинин О. Е. Компьютер для менеджера: Уч. пособие.

- М.: Высш. школа , 1990. – 240 с.: ил.

3. Ромакин М. И. Математический аппарат оптимизационных задач.

- М.: Статистика, 1975.

4. Щедрин Н. И., Кархов А. Н. Математические методы программирования в экономике. – М.: Статистика, 1974.

5. Конторович Л. В., Горстко А. В. Оптимальные решения в экономике. - М.: Наука , 1972.