§ 28. Линейное программирование

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

f(x₁, …, x_n) =

n

∑

k=1

 c_kx_k (1)

в некоторой области G n-мерного пространства R_n = {-∞ < x < ∞, i = 1, ..., n}, где с_k - постоянные числа, не все равные нулю.

Ясно, что если G = R_n, то линейная функция (1) не имеет наибольшего и наименьшего значений: supf = +∞, inff = -∞.

Однако если мы будем рассматривать ограниченную замкнутую область G, то линейная функция f (непрерывная на R_n, a следовательно, и на G) достигает своих максимальных и минимальных значений на G. Так как

∂f

∂xi

  = c_i (i = 1, …, n ≡ 1, n)

и c_i одновременно не равны нулю, то линейная функция f не имеет стационарных точек. Поэтому наибольшее и наименьшее значения эта функция достигает только на границе ∂G.

Так как maxf = -min(-f), то в дальнейшем мы будем говорить только о минимуме линейной функции f на G.

28.2. Транспортная задача. Характерной задачей, приводящей к указанной выше проблеме (нахождения минимума или максимума линейной функции),

241

является транспортная задача. Требуется наиболее экономно, в смысле транспортных затрат, перевезти потребителям заказанную ими на данных предприятиях продукцию. Характер продукции в данном случае не имеет значения. Важно, что речь идет об однотипной продукции.

Итак, пусть имеются предприятия (производители) B₁, ..., В_s, выпустившие продукцию в количестве соответственно b₁, ..., b_s тонн. Эту продукцию надо доставить потребителям А₁, ..., A_s в количествах а₁, ..., a_s тонн соответственно, т. е. а_ρ - количество продукции, заказанное потребителем А_ρ.

Таким образом, надо считать, что

s

∑

q=1

 b_q =

t

∑

p=1

 a_p,

т. е. вся произведенная продукция распределена между предприятиями. Стоимость перевозки тонны продукции от B_q к А_р обозначим через с_qp. Пусть количество продукции, доставленной из B_q в А_p , будет х_qp. Тогда стоимость перевозки продукции будет

S =

s

∑

q=1

 b_q =

t

∑

p=1

 a_p

Требуется так составить план перевозок, чтобы сумма транспортных расходов S была минимальной.

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

Дана линейная функция

S =

s

∑

q=1

 

t

∑

p=1

 c_qpx_qp (2)

Требуется найти ее минимум при ограничениях

(3)

т. е. сумма продукции, полученной потребителями А₁, ..., A_t от производителя В_q , равна продукции b_q

242

выработанной этим предприятием, а сумма продукции, полученной потребителем А_p от всех производителей В₁, ..., B_s, равна потребности а_р этого потребителя.

По характеру задачи также ясно, что х_qp ≥ 0.

Таким образом, среди неотрицательных решений {х_qp} системы (3) необходимо выбрать такое, при котором S достигает наименьшего значения (минимизируется).

28.3. Общая задача линейного программирования. В общем случае задачу линейного программирования можно сформулировать следующим образом: даны система линейных уравнений

n

∑

k=1

 a_jkx_k + b_j = 0 (j = 1, …, m ≡ 1, m) (4)

(где можно считать, что b_j ≥ 0, изменяя, если нужно, знак в соответствующем уравнении (4)) и линейная функция

f =

n

∑

k=1

 c_kx_k. (1)

Требуется среди неотрицательных решений системы (4) х = (x₁, ..., x_n), х_j ≥ 0, найти такое решение, для которого линейная функция f принимает наименьшее значение.

Уравнения (4) обычно называют ограничениями данной задачи. Конечно, требование, чтобы х_j ≥ 0 (j = 1, n), тоже является ограничением, но оно присутствует во всех задачах подобного типа и его не принято называть ограничением. Любое неотрицательное решение системы (4) будем называть допустимым, а решение, реализующее минимум, - оптимальным.

Отметим, что уравнения системы (4) с геометрической точки зрения представляют плоскости в R_n. Чтобы задача о минимуме f была содержательной, необходимо, чтобы число т ограничений типа равенств было меньше п.

Например, при п = 2 наличие двух ограничений означает, что неотрицательное решение системы должно быть точкой (x₀, y₀) пересечения прямых, представляющих уравнения системы. Тогда задача о нахождении min/ сводится к вычислению f в этой точке. Если прямые параллельны, то задача теряет смысл. Если ограничений больше двух,

243

то система или несовместна, или же все прямые принадлежат одному пучку:

А(х - x₀) + В(у - у₀) = 0.

В этом случае минимум f также равен f(x₀, y₀). В ряде практических задач (например, в задаче о диете) ограничения носят вид неравенств

b_j +

n

∑

k=1

 a_jkx_k ≥ 0 (j = 1, m, x_k ≥ 0, k = 1, n). (5)

Однако от одного типа ограничений легко перейти к другому. В самом деле, если ограничения носят характер неравенств (5), то вводим новые добавочные неизвестные x_n+1, ..., x_n+m с помощью уравнений

x_n+j = b_j +

n

∑

k=1

 a_jkx_k (j = 1, m)

Тогда неравенства (5) равносильны условию x_n+j ≥ 0 (j = 1, m ), x_k ≥ 0 (k = 1, п ), и мы пришли к ограничениям типа равенств (4), хотя и с большим числом переменных. Обратно, пусть имеют место ограничения типа равенств (4). Тогда, решая эту систему (например, методом исключения неизвестных), мы после некоторого числа шагов или убедимся, что система несовместна, или же разрешим систему (4) относительно некоторых неизвестных:

x₁ = α_1,r+1x_r+1 + … + α_1,nx_n + β₁,
..................
x_r = α_r,r+1x_r+1 + … + α_r,nx_n + βr, (6)

Здесь r - ранг матрицы коэффициентов системы (4).

Подставляя эти выражения x₁, ..., х_r в функцию f, получаем

f = c

’

0

+ c

’

r+1

x_r+1 + … + c

’

n

x_n.

После этого исходная задача может быть сформулирована следующим образом. Даны система

244

α_1,r+1x_r+1 + … + α_1,nx_n + β₁ ≥ 0,
..........
α_r,r+1x_r+1 + … + α_r,nx_n + β_r ≥ 0 (7)

r линейных неравенств с п = r неизвестными х₁, ... х_п и линейная функция

f= с

’

0

+ с

’

r+1

+ ... + c

’

n

x_n. (8)

Требуется среди всех неотрицательных решений системы (7) найти такое, которое минимизирует f.

Эта задача эквивалентна исходной. В самом деле, если мы нашли решение задачи (7), (8) x

0

n+1

, ..., х

0

n

, то, находя по формулам (6) неотрицательные значения х

0

1

, ..., х

0

r

, мы получим систему чисел

x

0

1

, …, x

0

r

, x

0

r+1

, …, x

0

n

,

которая служит решением задачи (1), (4).

Таким образом, задачу линейного программирования можно ставить с ограничениями типа неравенств. Из такой постановки видно, что область G, в которой мы ищем минимум f, представляет собой "многогранник" в неотрицательном угле R_n (т. е. когда x_k ≥ 0, k = 1, n), а ее граница ∂G состоит из "плоских граней", находящихся в плоскостях пространства R_n:

n

∑

k=1

  a_jkx_k + b_j = 0. (9)

Множество G ⊂ R_n называется выпуклым, если ∀ x, у ∈ G αх + βу ∈ G, α + β = 1, α, β ≥ 0.

Из системы неравенств (7) ясно, что "многогранник" G выпуклый и G находится по одну сторону от любой из своих граней.

Слово "многогранник" мы пишем в кавычках, так как могут быть случаи, когда этот "многогранник" будет неограниченной частью неотрицательного угла R_n.

Например, при п = 2 и при тех ограничениях типа неравенств "многоугольник" G может быть неограниченным в первой четверти R₂. На рис. 54 G - заштрихованная часть.

245

В дальнейшем кавычки у слова "многогранник" мы будем опускать.

При нахождении минимума линейной функции f на замкнутой области G = G_n мы последовательно будем переходить на плоские грани G_n меньшей размерности. Отметим, что граница ∂G_n n-мерного многогранника состоит из нескольких (п - 1)-мерных многогранников. Если G_n - ограниченный замкнутый многогранник, то линейная функция f достигает минимума в некоторой точке границы ∂G_n. При рассмотрении линейной функции f на этом новом многограннике меньшего числа измерений она снова будет линейной функцией, но от меньшего числа переменных и, следовательно, будет достигать минимума на границе ∂G_n-1 которая состоит из (п - 2)-мерных многогранников. Продолжая этот процесс, мы придем к случаю, когда линейная функция рассматривается на одномерной грани (ребре G_n), границей которой являются точки (вершины многогранника G_n).

Таким образом ясно, что если G_n - ограниченный замкнутый многогранник, то линейная функция достигает минимума в некоторой вершине G_n.

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

246

Замечание 1. Если функция f =

n

∑

k=1

 c_kx_k + В, где В - постоянное число, то мы исследуем сначала линейную форму φ = f - В, и если min φ = φ₀, то min f = φ₀ + В.

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

Рассмотрим плоскости уровня функции f:

C =

n

∑

k=1

 c_kx_k (-∞ < C < ∞). (10)

Уравнение (10) при различных С в пространстве R_n изображает семейство параллельных плоскостей (см. § 27). Будем непрерывно и монотонно изменять С от -∞ до +∞. Тогда плоскость (10) будет передвигаться в R_n в направлении вектора (с₁, ..., с_п), который, как мы знаем, перпендикулярен плоскости (10). Очевидно, что если с_п > 0, то плоскость (10) поднимается вверх относительно оси х_п при изменении С от -∞ до +∞; если же с_п < 0, то плоскость (10) опускается вниз относительно оси х_п. При с_n = 0 плоскость (10) движется вправо или влево относительно оси х_n-1 в зависимости от знака числа с_n-1 (с_n-1 ≠ 0). Если с_п > 0 и при всех С < С*, где С* - некоторое действительное число, плоскость (10) пересекает область G, то inff = -∞.

Если же этого нет, то при некотором С = С₀ плоскость (10), двигаясь в направлении вектора (с₁, ..., с_п), впервые встретит замкнутую область G в некоторой точке (х

0

1

, …, х

0

n

). Тогда в этой точке встречи функция f и достигает минимума.

На рис. 54 при п = 2 прямая уровня при возрастании С поднимается и при С = С₀ впервые встречает замкнутый многоугольник G в точке (х

0

1

, х

0

2

). Значит, min f= f(x

0

1

, x

0

2

).

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

Этот геометрический метод решения поставленной задачи эффективен лишь при п = 2, т. е. когда плоскости

247

(10) - прямые и G - многоугольник, ограниченный или нет. При п = 3 взаимное расположение плоскостей и многоугольника G трудноуловимо, а при п = 4 мы просто не можем прибегнуть к наглядным графическим изображениям.

Пример 1. Найти минимум функции f(x, у)=3 - х - у (х ≥ 0, у ≥ 0) при ограничениях (рис. 55)

Ясно, что область G есть треугольник с вершинами в точках М = (2, 0), N = (1, 2), Р = (0, 1). Прямая уровня функции f:

3 - х - у = С,

при возрастании С от -∞ до +∞ опускается относительно оси у (коэффициент при у отрицателен); ее первая точка встречи с G есть вершина N. Значение функции f в этой точке равно нулю (С = С₀ = 0). Итак, решение задачи есть х = 1, у = 2, f = 0.

В данном случае можно было бы просто вычислить значение f в точках М, N, Р и взять наименьшее: f(М) = f(2, 0) = 1, f(N) = f(1, 2) = 0, f(P) = f(0, 1) = 2, т. е. min f = f(N) = 0.

248

Пример 2. Найти минимум функции f = 3 - х + 2у при тех же ограничениях, что и в примере 1.

В данном случае прямая уровня функции

3 - х + 2у = С

при возрастании С от -∞ до +∞ поднимается (рис. 56) вверх относительно оси у (с₂ = 2 > 0) и ее первая точка встречи с областью G есть вершина М = (2, 0). Значение функции f в этой точке равно 1 (С = С₀ = 1). Здесь тоже проще всего взять наименьшее среди чисел f(M) = 1, f(N) = 6, f(Р) = 5.

Пример 3. Найти минимум функции f = -х при ограничениях

Ясно, что последнее ограничение несущественно, оно перекрывается условием х ≥ 0, у ≥ 0.

Область G неограничена и представляет собой полосу (рис. 57) между прямыми х - у + 1 = 0, -х + у + 1 = 0 и правее прямой х + у - 3 = 0, которая пересекает эти прямые в точках N = (1, 2), М = (2, 1).

При х → +∞ функция f(x, у) = -х → -∞, (х, у) ∈ G. Поэтому линейная функция f не имеет наименьшего значения (inff = -∞).

249

В данном примере прямая уровня -х = С при возрастании С от -∞ до +∞ движется влево (с₁ = -1 < 0) и при всяком С < -1 пересекает G, значит, inf_f = -∞.

Пример 4. Найти минимум функции f = 4 - x + y - 2z при ограничениях

где а₁ а₂, а₃ - положительные числа.

Ясно, что область G (рис. 58) есть часть пространства R₃, находящаяся в первом октанте (х ≥ 0, у ≥ 0, z ≥ 0) между плоскостями

x

a1

  +

y

a2

  +

z

a3

  = 1,

x

2a1

  +

y

2a2

  +

z

2a3

  = 1.

В данном случае многогранник G имеет шесть известных вершин

(а₁, 0, 0), (2a₁, 0, 0), (0, а₂, 0), (0, 2а₂, 0),
(0, 0, а₃), (0, 0, 2а₃).

Поэтому, вычисляя функцию f в этих точках, легко находим ее минимум и максимум:

28.4. Векторно-матричная форма задачи линейного программирования. Задачу линейного программирования можно сформулировать также в векторно-матричной форме. Пусть с = (с₁, ..., с_n), х = (х₁, ..., х_п), 0 = (0, ..., 0) - векторы пространства R_n; b = (b₁, ..., b_m) - вектор из пространства R_m;

250

- матрица размера п × т, составленная из коэффициентов системы ограничений (4). Линейная функция f(x) =

n

∑

k=1

 c_kx_k = сх есть скалярное произведение векторов с и х.

Поэтому общую задачу линейного программирования можно записать в следующем виде: требуется минимизировать скалярное произведение сх при условии х ≥ 0 и Ах + b = 0.

Примем столбцы матрицы А за векторы из R_m:

P₁ = (а₁₁, а₁₂, ..., a_m1), ..., Р_п = (a_1n, а_2n, ..., а_тп).

Тогда легко получаем, что

Ах = (а₁₁х₁ + ... + a_1nx_n, ..., a_m1x₁ + ... + а_тпх_п) =
= (а₁₁х₁, a₂₁x₁, ..., a_m1X₁) + ... + (a1_nx_n, ..., а_тпх_п) =
= Р₁x₁ + Р₂х₂ + ... + Р_nx_n.

Поэтому систему ограничений можно записать в виде

n

∑

j=1

 P_jx_j = -b.

Если ранг А = m, то среди векторов Р₁, ..., Р_п имеется т линейно независимых, которые можно принять за базис в пространстве R_m (см. § 16). Следовательно, любой вектор (-b) ∈ R_n может быть разложен по элементам этого базиса. Нам необходимо выбрать такой базис, чтобы вектор (-b) разлагался по векторам этого базиса с неотрицательными коэффициентами x₁, x₂, ..., х_п.

Различных m-мерных базисов (m < n) из векторов Р₁ ..., Р_n конечное число. Среди них могут быть базисы, по элементам которых вектор (-b) разлагается с неотрицательными коэффициентами. Тогда минимум скалярного произведения (линейной функции) достигается на

251

конечном множестве точек x = (x₁, ..., х_п) ∈ R_n, где х_j - коэффициенты разложения вектора (-b) по элементам некоторых базисов.

Если базисов указанного типа нет (вектор (-b) не разлагается по элементам базисов с неотрицательными коэффициентами), то задача линейного программирования не имеет решения (неразрешима).

Таким образом, задача состоит в том, как найти базис

(P_k, …, P_km)

так, чтобы

-b =

m

∑

j=1

 x_kjP_km, x_kj ≥ 0,

и

minf =

min

xj≥0

  cx =

m

∑

j=1

 c_kjx_kj.

28.5. Симплекс-метод. Реальные задачи линейного программирования содержат, как правило, большое число ограничений и неизвестных. Поэтому естественно, что решение таких задач связано с большим объемом вычислений. Это затруднение преодолевается с помощью быстродействующих электронно-вычислительных машин (ЭВМ). Для каждой задачи разрабатываются алгоритм и программа, и затем ЭВМ в короткий срок дает решение поставленной задачи.

Существуют и другие общие методы, позволяющие найти решение любой задачи линейного программирования в обозримое число шагов.

Таким является симплекс-метод. Опишем идею этого метода.

Пусть надо найти минимум линейной функции

f(x) = c

’

0

+

n

∑

j=1

 c

’

j

x_j (11)

среди значений x_j ≥ 0 (j = 1, ..., п), удовлетворяющих равенствам

252

n

∑

j=1

 a

’

kj

x_j + b

’

k

= 0 (k = 1, …, m; m < n). (4)

Неотрицательные решения системы (4) x_j ≥ 0 (j = 1, n) мы условимся называть допустимыми, а точку x = (x₁, ..., x_n) - допустимой точкой. Покажем, как эту задачу можно решить, применяя симплекс-метод.

Пусть ранг матрицы А' = (а

’

ij

) равен r ≤ т(r - ранг А')-Будем считать, что система (4) разрешима относительно

x_k = b_k -

n

∑

j=r+1

 a_kjx_j (k = 1, r) , (12)

и числа b_k неотрицательны (b_k ≥ 0, k = 1, r).

В этом случае говорят, что переменные х₁ ..., x_r образуют базис - базис В = {х₁, ..., х_r}. Остальные переменные называются свободными или небазисными. Следует обратить внимание, что здесь понятие базиса не совпадает с понятием базиса из § 16.

Вопрос о возможности перехода от системы (4) к системе (12) будет рассмотрен ниже в п. 28.8.

Системы (4) и (12) равносильны, поэтому допустимая точка x системы (4) есть допустимая точка системы (12), и обратно.

Очевидно, точка b = (b₁, ..., b_r, 0, ..., 0) допустимая, ее называют базисным решением, отвечающим базису В. Будем писать f(b) = f_B. В силу равенств (12) функцию f можно записать в виде линейной функции от переменных x_j (j = r + 1, ..., n):

f(x) = c₀ -

n

∑

j=r+1

 c_jx_j. (13)

Очевидно, что f_B = с₀ = с

’

0

+

r

∑

j=1

 c

’

j

b_j.

Первый этап симплекс-метода связан с рассмотрением функции f, определяемой равенством (13), и системы ограничений в виде равенств (12).

253

Рассмотрим четыре возможных случая I, II, III₊, III₀.

Случай I. Пусть c_j ≤ 0 для всех j = r + 1, ..., п. Тогда минимум f, определяемой равенством (13), относительно всех х_j > 0, j = 1, ..., n, будет равен с₀:

min

xj≥0,

  f(x) = с₀.

Этот минимум остается тем же для допустимых x₁, ..., х_п. Этим задача на минимум решена.

Случай II. Пусть для некоторого j₀ c_j0 > 0 и все коэффициенты a_kj0 матрицы А = (a_kj) неположительны:

a_kj0 ≤ 0 (k = 1, ..., r).

Тогда при любом x_j0 ≥ 0 (r + 1 ≤ j₀ ≤ п) точка

x⁰ = (х₁, ..., х_r, 0, ..., 0, x_j0 , 0, ..., 0). (14)

где x_k (k = 1, ..., r) вычисляются по формулам (12), будет допустимой, и если ее подставить в f, то получим f = с₀ - C_j0x_j0 → -∞ при x_j0 → +∞. Поэтому

inf

xj≥0

  f(x) = -∞,

и нашу задачу о минимуме можно считать решенной.

Случай III. Пусть для некоторого j₀ коэффициент с_j0 функции f положительный (c_j0 > 0) и имеются положительные коэффициенты a_kj0 в j₀-м столбце матрицы А:

a_kj0 > 0 (k ∈ е), (15)

где е - множество индексов k, для которых выполняется неравенство (15).

Пусть

min

k∈e

 

bk

akj0

  =

bk0

ak0j0

  = δ ≥ 0 (1 ≤ k₀ ≥ r, k₀ ∈ е). (16)

254

Элемент a_k0j0 называют разрешающим элементом.

Рассмотрим отдельно случаи δ > 0 и δ = 0, которые будем обозначать через III₊ и III₀ соответственно.

Случай III₊. Точка (14) для значений x_j0 , удовлетворяющих неравенствам 0 ≤ х_j0 ≤ δ (δ > 0), допустимая. В самом деле, в силу (12) при k ∈ e непосредственно видно, что

x_k = b_k - a_kj0x_j0 ≥ 0 (a_kj0 ≤ 0),

а при k ∈ e в силу соотношений (15), (16) имеем

x_k = b_k - a_kj0x_j0 ≥ b_k - a_kj0δ =
= b_k - a_kj0

min

k∈e

 

bk

akj0

  ≥ b_k - a_kj0

bk

akj0

  = b_k - b_k = 0.

Если x_j0 непрерывно возрастает от 0 до δ, то все x_k > 0 (k = 1, ..., r), a x_k0 = x_k0 - a_k0j0x_j0 к тому же непрерывно убывает от b_k0 до 0. При дальнейшем возрастании x_j0 переменная x_k0 становится отрицательной и точка (14) перестает быть допустимой.

Функция

f(x⁰) = c₀ - c_j0x_j0

при возрастании x_j0 от 0 до δ убывает от f(b) = с₀ до f(b¹)= с₀ - c_j0δ, где

b¹ = (b₁ - а_1j0 δ, ..., b_r - a_rj0 δ, 0, ..., 0, δ, 0, ..., 0) (17)

и δ стоит на j₀-м месте.

Таким образом,

c₀ = f(b) > f(b¹) = с₀ - с_j0δ.

Отметим, что координата х_k0 (k₀ ∈ е) в (17) равна нулю:

255

x_k0 = b_k0 - a_k0j₀δ = b_k0 - a_k0j0

bk0

ak0j0

  = 0.

Так как а_k0j0 > 0, то k₀-e уравнение системы (12) можно решить относительно x_j0:

x_j0 =

bk0

ak0j0

  -

xk0

ak0j0

  -

n

∑

j=r+1, j≠j0

 

ak0j

ak0j0

 x_j (18)

Мы выразили x_j0 через x_k0 и остальные переменные x_j (j ≠ j₀, j ≥ r + 1). Можно выразить через эти переменные также любую переменную x_k (k ≠ k₀, 1 ≤ k ≤ r), если подставить выражение (18) вместо x_j0 в равенства (12), соответствующие любым k ≠ k₀.

Итак, в случае III₊ удается решить систему (12) относительно переменных

x₁, …, x_k0-1, x_j0, x_k0+1, …, x_r. (19)

Условно запишем соответствующую систему равенств так:

x_k = b

1

k

-

n

∑

j=r+1

 a

1

kj

x_j (k = 1, …, r), (20)

хотя на самом деле в этих равенствах только переменные x₁ (i ≠ k₀, j₀) остались прежними, а остальные переменные х_k0 и x_j0 поменялись местами.

Покажем, что свободные члены

b

1

k

≥ 0 (k = 1, ..., r). (21)

В самом деле, если k ∈ е, то (a_kj0 > 0)

256

Если же k ∈ е (а_kj0 ≤ 0), то

b

1

k

= b_k -

akj0

ak0j0

 b_k0 = b_k +

|akj0|

ak0j0

 b_k0 = b_k + |a_kj0|δ ≥ 0

и неравенства (21) доказаны.

Итак, переменные x₁, ..., х_r в системе (20) образуют базис - базис В₁ (см. также (19)).

Для базисного решения b¹ = (b

1

1

, ..., b

1

r

, 0, ..., 0)

f_B1 = f(b¹) = с₀ - с_j0δ < с₀ = f(b) = f_B (c_j0 > 0).

Базис B₁ отличен от базиса B, и для него можно начать второй этап рассуждений (случай I, II, III). Таким образом, случай III₊ рассмотрен.

Случай III₀. Пусть с_j0 > 0, а_kj0 > 0 для k ∈ е, δ = 0. В этом случае b_k0 = 0 (см. (16)) и равенство с номером k₀ в (12) имеет вид

x_k0 = -

n

∑

j=r+1

 a_k0jx_j. (22)

Если в равенстве (22) все коэффициенты a_k0,r+1, ..., a_k0,n положительные, то система (12) имеет единственное допустимое решение х_j = 0, j = r + 1, ..., n; x_k = b_k ≥ 0 (k = 1, ..., r). Значение функции f на этом базисном решении будет: f = с₀. Задача на минимум функции f в этом случае решена.

Допустим, что в (22) имеются коэффициенты а_k0j ≤ 0 для некоторого значения j (j ≠ j₀). Тогда, как и в случае III₊, переходим к новому базису В₁ (вводим в базис переменную xj₀ и выводим из него х_k0, a_k0j0 - разрешающий элемент). Отметим, что в этом случае значение f_B= f_B1 (b_k0 = 0).

257

Итак, рассматривая базис В, мы либо решим нашу задачу на минимум, либо придем к новому базису В₁ (B₁ ≠ В). К базису В₁ снова применяем наш метод - это приведет к решению задачи либо к новому базису В₂ (В₂ ≠ B₁). Продолжая этот процесс, получим цепочку базисов

В₀, B₁, B₂, ... (В₀ = В). (23)

Если для некоторого s будет иметь место случай I или II, то цепочка на этом s оборвется и задача будет решена. Иначе от базиса В_s переходим к базису В_s+1.

Однако может случиться цикл. Он заключается в том, что хотя каждый последующий базис цепочки и отличается от предыдущего, но для некоторых s и l (l > 1) будет происходить совпадение базисов: В_s = B_s+1.

Разберемся, что здесь происходит. Для базиса В_s+l-1 произошел случай III₀, т. е. оказалось, что существует j₀ (r + 1 ≤ j₀ < п) и такое k₀ (1 ≤ k₀ ≤ r), что

C_j0 > 0, a_k0j0 > 0 b_k0 = 0 (δ = 0), (24)

и это привело к базису B_s (B_s+1 = B_s).

Но пара чисел (k₀, j₀), вообще говоря, неединственна, и какая-то другая пара (k

’

0

, j₀), для которой выполняются свойства (24), может привести к базису, отличному от базиса B_s. Это на самом деле и имеет место, как учит теория (см. ниже теорему 1 и замечания к ней).

Таким образом, если для некоторых s и l случится цикл, то его можно устранить. В этом случае для базиса В_s+l-1 надо перебрать всевозможные пары (k₀, j₀), обладающие свойствами (24). Каждая такая пара приводит к некоторому базису. Среди них есть отличный от базисов В₀, B₁, ..., B_s+l-1.

28.6. Устранение цикла. На практике циклы бывают очень редко. Все же объясним, как их можно "разорвать" (устранить).

Отметим теорему, доказательство которой будет намечено в п. 28.7.

258

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

Итак, пусть имеем цикл

B_s, B_S+1, …, B_s+1 (B_s+1 = B_s)

Тогда, очевидно,

f_Bs = f_Bs+1 = … = f_Bs+l

Пусть s₀ - наименьшее неотрицательное целое число, для которого

f_Bs0 = f_Bs+1 = … = f_Bs0+l

(f_Bs0-1 > f_Bs0, s₀ ≤ s, B_s0 = B_s0+l)

Очевидно, для базисов

B_s0, B_s0+1, …, B_s0+l (25)

имеет место случай III₀. Переход от любого из этих базисов B_s (s₀ ≤ s ≤ s₀ + l) к последующему совершается посредством разрешающего элемента а_k0j0 . Но базису B_s может соответствовать и другой разрешающий элемент, который переводит B_s в базис В

’

s+1

, отличный от B_s+l (В

'

s+1

≠ В_s+1).

Может случиться, что для любого s (s = s₀, ..., s₀ + l) базис B

’

s+1

содержится в цепочке (25). Тогда все базисы (25) решают задачу на минимум, т. е. f_Bs0 = f_Bs0+1 = ... = f_Bs0+l = minf. Ведь по теореме 1 существует путь, ведущий от B_s0 к минимуму. Но в данном случае все пути от В_s0 ведут к базисам цепочки (25).

Однако может случиться, что для некоторого s разрешающий элемент базиса B_s переводит В_s в базис B_s+1, не входящий в цепочку (25). Тогда мы получим новую цепочку

B_s0, B_s0+1, …, B_s, B

’

s+1

(26)

259

с новым последним базисом B

’

s+1

, который подлежит исследованию симплекс-методом.

Но указанных значений s может оказаться и много. Одна из цепочек может и не привести к нужному результату. Необходимо произвести перебор всех цепочек. Отметим, что сам перебор цепочек становится громоздким.

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

28.7. Выбор разрешающего элемента. Симплекс-таблицы. Условимся вектор Q = (q₀, q₁ ..., q_n) называть положительным (отрицательным) и писать Q > 0 = (0, ..., 0) (Q < 0), если его первая не равная нулю компонента положительная (отрицательная).

Будем говорить, что вектор Q меньше вектора D = (d₀, d₁, ..., d_n) или вектор D больше вектора Q, и писать Q < D или D > Q, если D - Q = (d₀ - q₀, ..., d_n - q_n) > 0.

Замечание 2. Целесообразность приведенных определений >, < для векторов Q можно подтвердить следующими соображениями.

Каждому вектору Q = (q₀, ..., q_n) поставим в соответствие многочлен от переменной t вида Q(t) = q₀ + q₁t + ... + q_ntⁿ, который является непрерывной функцией и Q(0) = q₀. Если q₀ > 0, то найдется окрестность нуля такая, что для всех t из этой окрестности Q(t) > 0. Если же q₀ = … = q_k = 0 и q_k+1 > 0, то

Q(t) = t^k+1[q_k+1 + q_k+2t + ... + q_nt^n-k+1].

Многочлен в квадратных скобках больше нуля (q_k+l > 0) в некоторой окрестности нуля. Далее t^k+l > 0 для t > 0. Значит, Q(t) > 0 для всех 0 < t < θ, где θ - некоторое положительное число.

Таким образом, если вектор Q > 0, то соответствующий многочлен Q(t) > 0 для 0 < t < θ при некотором θ > 0.

Вернемся теперь к системе ограничений (12), которую мы запишем в форме

260

Таблица 1

261

x_k +

n

∑

j=r+1

 a_kjx_j = b_k (b_k ≥ 0, k = 1, ..., r), (12)

а линейную функцию (13) запишем в виде

f +

n

∑

j=r+1

 c_jx_j = c₀. (13)

Здесь базис В = {х₁, ..., x_r}.

Оформим систему равенств (12) и (13) в виде таблицы 1 (матрицы).

Табл. 1 называется симплекс-таблицей. В табл. 1 мы приписали некоторую добавочную матрицу ||d_ij|| размера r × r и добавочную строку (d₁, ..., d_r). Введем в рассмотрение векторы

D = (с₀, d₁, ..., d_r), D_k = (b_k, d_k1, ..., d_kr), k = 1,2, ..., r.

Базис В называется положительным, если все векторы D_k(k = 1, ..., r) положительные (D_k > 0). Например, если матрица ||d_ij|| единичная , то базис В положительный, потому что для любого k = 1, ..., r либо b_k > 0, либо первый отличный от нуля элемент k-й строки матрицы ||d_ij|| равен 1 > 0.

Будем считать, что числа d_ij подобраны так, что базис В положительный и матрица ||d_ij|| невырожденная (т. е. определитель, порожденный матрицей, отличен от нуля). Вектор D выбираем произвольно. Можно считать, что D = (c₀, 0, ..., 0).

В дальнейшем при переходе от базиса В к другому базису В' записи систем ограничений (12) и линейной функции (13) будут изменяться, этому соответствует изменение табл. 1 с помощью некоторых элементарных преобразований (см. § 4.7), которые мы распространяем и на добавочную матрицу ||d_ij|| и добавочную строку (d₁, ..., d_r). В результате векторы D_k и D будут соответственно изменяться.

Напомним, что в случае III₀ существует j₀ (r + 1 ≤j₀≤ п) такое, что с_j0 > 0, и a_k0j0 > 0, k ∈ е, где е - непустое множество и, кроме того, b_k = 0 хотя бы для одного k ∈ е.

262

Индексов j₀, для которых имеет место III₀, может быть несколько. Не имеет значения, какой из них надо взять. Но, если мы остановились на некотором j₀, то индекс k₀ предлагается выбрать следующим образом:

1

ak0j0

 D_k0 =

min

k∈e

 

1

akj0

 D_k. (26)

Элемент а*0/0 разрешающий. В табл. 1 мы его поместили в рамку.

Минимум в (26) достигается для одного k₀, потому что если бы нашлось k₁ ∈ е, для которого

1

ak1j0

 D_k1 =

1

ak0j0

 D_k0,

то в матрице ||d_ij|| были бы две пропорциональные строки и она была бы вырожденной.

Замечание 3. Так как мы рассматриваем случай III₀, то среди k ∈ е имеются такие, для которых b_k = 0, поэтому

min

k∈e

 

1

akj0

 D_k =

min

k∈e bk=0

 

1

akj0

 D_k,

т. е. индекс k₀ находится среди таких k ∈ е, для которых b_k = 0.

В п. 28.5 мы брали в качестве k₀ одно из значений k ∈ е, для которых b_k = 0. Но таких значений может быть несколько. В данном способе среди них выбирается одно такое определенное значение, обращающее в минимум

1

akj0

 D_k.

Мы уже знаем, что в данном случае III₀ базис В = {x₁, ..., х_r} можно заменить на другой базис B’ = {x₁, ..., x_k0-1, x_j0, x_k0+1, …, x_r}, которому соответствует система ограничений, эквивалентная системе (12):

263

(27)

b

’

k

≥ 0 (k = 1, ..., k₀ - 1, j₀, k₀ + 1, ..., r), и линейная функция

f + c

’

r+1

x_r+1 + … + x

’

j0-1

x_j0-1 + c

’

k0

x_k0 + c

’

j0+1

x_j0+1 +
+ … + c

n

x_n = c

’

0

(28)

Системе равенств (27)-(28) соответствует таблица 2.

Табл. 2 получается из табл. 1 следующим образом. Делим k₀-ю строку табл. 1 на разрешающий элемент a_k0j0 (≠0).

Этим k₀-е уравнение системы (12) остается равносильным прежнему. Добиваемся теперь, чтобы в j₀-м столбце на остальных местах (k ≠ k₀) были нули. Для этого из k-й строки вычитаем измененную k₀-ю строку, умноженную на число a_kJ0. (Эту процедуру мы распространяем и на строки добавочной матрицы, в результате числа d_kj переходят в числа d

’

kj

).

Этот прием соответствует замене k-го уравнения разностью между ним и видоизмененным k₀-м уравнением, умноженным на число а_kj0 , что приводит к системе (27), равносильной системе (12).

Посмотрим, как видоизменяются векторы D_k, Так как базис B положительный и рассматривается случай III₀, то b_k0 = 0и

264

Таблица 2

265

D_k0 = (0, d_k01, …, d_k0r) > 0,

поэтому

для k ≠ k₀, k ∈ е (a_kj0 > 0)

в силу правила выбора k₀ ∈ е и его единственности (см. (26)); для k ≠ k₀, k ∈ е (a_kj0 ≤ 0), очевидно,

D

’

k

= D_k -

akj0

ak0j0

 D_k0 > 0.

Чтобы получить последнюю строку табл. 2, надо из последней строки табл. 1 вычесть видоизмененную k₀-ю строку, умноженную на c_j0 . Вектор D = (с₀, d₁, ..., d_r) переходит в вектор

D’ = D -

cj0

ak0j0

 D_k0.

Так как c_j0 > 0, а_k0j0 > 0, то

D' - D = -

cj0

ak0j0

 D_k0 < 0,

т. е. D' < D.

Новые коэффициенты линейной функции f имеют вид

c

’

k0

= -

1

ak0j0

 c_j0, c

’

j

= c_j -

ak0j

ak0j0

 c_j0
(j = r + 1, ..., j₀ - 1, j₀ + 1, ..., n).

Таким образом, мы пришли к положительному базису В’.

Чтобы табл. 2 была полностью аналогичной табл. 1, рекомендуем в табл. 2 переставить местами столбцы, отвечающие переменным x_j0 и x_k0 .

266

Если для базиса B’ снова будет иметь место случай III₀, то к нему можно опять применить описанный прием, который приводит к новому базису B", отличному не только от B', но и от В, потому что

D" < D' < D.

Замечание4. Если в процессе применения симплекс-метода мы пришли к циклу (см. (25)), то можно взять один из базисов цикла, например В = B_s0+l, и последовательно применять к нему описанный выше способ однозначного получения нового базиса на основании правила (26) выбора разрешающего элемента. Этим гарантируется получение каждый раз базиса, отличного от всех предшествующих. Так как количество возможных базисов конечно, то мы для некоторого базиса цепи обязательно придем к случаям I, II или III₊. В последнем случае возникает базис В', для которого f_B > f_B’. Базисы, возникшие после В', отличаются от базиса В и всех ему предшествующих базисов. Они могут создавать циклы, но состоящие из новых базисов, отличных от B и ему предшествующих.

Итак, вычисления по симплекс-методу производятся следующим образом:

• исследуются уравнения (12) с базисом Б и функция f; если будут иметь место случаи I или II, то задача на минимум f решена;
• если будет случай III₊, то переходим к новому базису на основании (16), составляя таблицы 1 и 2 без добавочной матрицы ||d_ij||;
• если же будет случай III₀, то можно продолжать наш процесс в надежде, что не случится цикла. Практика показывает, что циклы бывают очень редко;
• все же, если случится цикл, то придется, отправляясь, как правило, от базиса В_s0 , двигаться дальше, применив добавочную матрицу ||d_ij||; рассуждения станут более сложными, но они имеют то преимущество, что на каждом их этапе s будут получаться все новые и новые базисы, отличные от всех предыдущих базисов;
• для базиса B_s0 мы выбираем матрицу ||d_ij|| и вектор D = (c₀, d₁, ..., d_r) произвольно, как было указано выше;
• дальнейшие базисы, следуя методу, получаются определенным образом, а вместе с ними определенным образом преобразуются матрицы ||d_ij|| и вектор D;

267

• через конечное число шагов мы выясним, что inf f = = -∞, или же найдем конечный минимум f.

Проследим симплекс-метод на конкретном примере.

Пример 5. Найти минимум линейной функции

f = 0 - (

3

4

 x₁ - 150x₂ +

1

50

 x₃ - 6x₄)

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

Решение. Здесь базис В = {х₅, х₆, х₇}, и ограничения, и функция f записаны в форме (12)-(13). В данном случае c₁ =

3

4

  > 0 и в первом столбце матрицы ограничений имеются положительные элементы а₅₁ =

1

2

 , а₆₁ =

1

4

 . Отношения b₅BREAK/а₅₁ = 0, b₆BREAK/а₆₁ = 0. Поэтому

min

k∈e

 b_kBREAK/a₆₁ = δ = 0

и этот минимум достигается на двух элементах k = 5, k = 6.

Таким образом, мы имеем случай III₀ (j₀ = 1). Чтобы избежать образования цикла, используем описанный выше способ однозначного выбора разрешающего элемента (см. (26)). Для этой цели составим таблицу 1*.

Здесь D₁ = (0, 1, 0, 0), D₂ = (0, 0, 1, 0) и 2D₁ > 4D₂.

Поэтому разрешающим элементом будет а₆₁ =

1

4

  , стоящий на пересечении строки для х₆ и столбца для х₁. Эту строку и столбец мы выделяем стрелками, а разрешающий элемент обводим рамкой. Преобразуем эту таблицу в таблицу 2*.

268

Таблица Г

Разделим строку для х₆ на а₆₁ =

1

4

 , т. е. умножим строку для х₆ на 4 и перенесем ее в табл. 2*.

Затем умножим вторую строку (видоизмененную) на а₅₁ = - и вычтем из первой строки. Далее умножим вторую строку на c₁ =

3

4

  и вычтем из последней строки. Строку для х₇ переносим в табл. 2* без изменений (а_п = 0).

Кроме того, мы переставим местами столбцы для х₆ и х₁, тогда табл. 2* будет иметь вид:

Таблица 2*

269

Таким образом, базис В₁ = {x₅, x₁, х₇}. В табл. 2* коэффициент с₂ = 30 > 0 (штрих мы опускаем) и в столбце для x₂ имеется один элемент а₅₂ = 30 > 0, который и будет разрешающим элементом (в табл. 2* мы поместили его в рамку). Проводя преобразование табл. 2*, как и выше, мы перейдем к базису В₂ = {x₂, x₁, x₇}, т. е. из базиса В₁ мы выводим переменную х₅ и вводим переменную х₂.

Таблица 3* будет иметь следующий вид (после перестановки столбцов для х₂ и x₅):

Таблица 3'

В последней строке табл. 3* имеется только один положительный коэффициент c₃ =

2

25

  > 0. В столбце для х₃ все элементы также положительны. В данной таблице D₁ = (0,

1

30

  , -

1

15

 , 0), D₂ = (0, 8, -12, 0), D₃ = (1, 0, 0, 1). Сравнивая векторы 500D₁,

25

8

 D₂,D₃, находим, что минимальным будет вектор 500D₁ и, следовательно, разрешающим элементом будет а₂₃ =

1

500

  > 0. Минимум (16) равен нулю, т. е. мы опять имеем случай III₀. Преобразуя табл. 3*, получим таблицу 4*.

270

Таблица 4*

Таблица 5*

271

Здесь базис В₃ = (x₃, х₁, x₇}, с₆ =

5

3

  > 0 и в столбце для х₆ имеется только один положительный элемент а₇₆ =

100

3

  > 0, который и будет разрешающим элементом. Минимум (16) равен

3

100

  > 0, т. е. мы имеем случай III₊. Преобразуя табл. 4*, получим таблицу 5*.

В последней строке табл. 5* все коэффициенты c_j (j = 7, 5, 2, 4) отрицательные, следовательно, minf =

1

20

  (случай I).

Базис В₄ = (x₃, x₁, х₆}. Из табл. 5* видно, что базисное решение имеет вид х₃ = 1, x₁ =

1

25

 , х₆ =

3

100

 , х₇ = x₅ = x₂ = x₄ = 0.

Замечание 5. Если бы мы не следовали правилу однозначного выбора разрешающего элемента, то могли бы получить цикл, выбирая базисы в следующей последовательности:

В = {x₅, x₆, x₇} → B₁ = {x₁, x₆, x₇} → B₂ =
= {x₁, x₂, x₇} → B₃ = {x₃, x₂, x₇} → B₄ =
= {x₃, x₄, x₇} → B₅ = {x₅, x₄, x₇} → B₆ =
= {x₅, x₆, x₇} = B.

Замечание 6. Отметим, что на каждом этапе, начиная с первого, можно было бы изменять нумерацию переменных, приводя систему ограничений и функцию f к виду (12), (13).

28.8. Условия существования базиса. Поясним, как можно привести систему ограничений (4)

n

∑

j=1

 a_kjx_j = b_k (k = 1, ..., m) (4)

к системе вида (12)

272

x_k = β_k =

n

∑

j=r+1

 α_kjx_j (β_k ≥ 0, k = 1, ..., r), (12)

т. е. выясним, когда переменные x₁, ..., х_r образуют базис.

Как нам известно, система (4) разрешима (совместна) тогда и только тогда, когда ранг матрицы

равен рангу расширенной матрицы

Пусть r = ранг А = ранг В. Тогда можно указать r таких уравнений системы (4), что всякое решение системы, состоящей из этих r уравнений, есть решение системы (4). Будем считать, что для данной системы (4) r = т и, кроме того, т < п, потому что при т = п существует только одна точка n-мерного пространства, являющаяся решением системы (4).

Кроме того, всегда можно добиться путем перенумерации переменных того, чтобы

Теорема 2. Для того чтобы неизвестные x₁ ..., х_т из системы (4) образовывали базис, необходимо и достаточно, чтобы

Δ^k/Δ ≥ 0 ∀k = 1, т,

где Δ^k - определитель, получающийся из определителя Δ заменой k-го столбца столбцом свободных членов системы (4).

273

Доказательство. Пусть

Δk

Δ

  ≥ 0, k = 1, ..., т. Применяя правило Крамера (см. § 4.2), имеем (k - 1, ..., m)

Учитывая свойства определителей, получаем равенства вида (12)

x_k =

Δk

Δ

  -

n

∑

j=m+1

 α_kjx_j (k = 1, …, m),

где число α_kj равно определителю, который получается из определителя Δ заменой k-то столбца соответственно на j-й столбец матрицы A (j = m + 1, ..., п), деленному на Δ. Например,

Обратно, пусть система х₁, ..., х_т есть базис, т. е. выполняются соотношения (12). Для матрицы равенств (12)

Δ_* = 1, Δ

k

*

= β_k,

Δ k *

Δ*

  = β_k ≥ 0.

Допустимыми элементарными преобразованиями эта матрица переходит в матрицу равенств (4). При этом определители Δ_* и Δ

k

*

переходят в определители Δ и Δ^k пропорционально. Поэтому

Δk

Δ

  = β_k ≥ 0.

Пример 6. Найти базисные переменные в системе ограничений

274

где α - некоторое число.

Решение. Если α ≤ 0, то система ограничений несовместна в области x_j ≥ 0 (j = 1, ..., 5). Поэтому будем считать а > 0. Выясним, при каком а элементы x₁, х₂, х₃ будут базисом. Имеем

Далее,

Отсюда

Δ1

Δ

  =

2a - 5

1 - a

  ≥0, 1 < a ≤

5

2

 ;

Δ2

Δ

  =

3

a - 1

  > 0, a > 1;

Δ3

Δ

  = 11 > 0.

Таким образом, при 1<а<

5

2

  все отношения Δ4k/Δ ≥ 0 (k = 1, 2, 3) и {x₁, х₂, х₃} - базис.

Для того чтобы написать систему (12), нет необходимости вычислять все нужные определители. Надо просто преобразовывать матрицу 5, как мы это делали в § 4.7.

Пусть а = 2. Получим базис из элементов х₁, х₂, х₃, Для этой цели будем матрицу В преобразовывать так,

275

чтобы в первых трех столбцах по главной диагонали стояли 1, а на остальных местах - 0. Итак,

Последняя матрица определяет следующую систему уравнений:

x₁ - x₄ + x₅ = 1

x₂ -

2

3

 x₄ -

1

2

 x₅ = 3

x₃ -

9

2

 x₄ +

5

2

 x₅ = 11.

276

Аналогичным образом можно проверить, при каком а переменные х₁. х₂, х₅ образуют базис.

28.9. Задачи. Найти минимум функции f(x) = х₄ - х₅ при ограничениях:

Приведем решение первой задачи. Итак, необходимо найти минимум линейной формы f(x) = х₄ - х₅ при ограничениях

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

Так как в системе ограничений три уравнения, то в каждый базис входят какие-либо три переменные из x₁,, х₂, х₃, х₄, х₅ Всего из пяти элементов можно составить десять различных комбинаций по три элемента

277

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

Выясним, будут ли элементы x₁, x₂, х₃ образовывать базис. Определитель Δ, составленный из коэффициентов при этих неизвестных в системе ограничений, имеет вид

Далее,

Отношение

Δ2

Δ

  = -2 < 0, следовательно, согласно теореме 2 п. 28.8 элементы x₁, x₂, х₃ не образуют базиса. Проверим тройку x₁, х₃, х₄:

Отношение

Δ2

Δ

  = -4 < 0 и тройка x₁, x₃, х₄ также не образует базиса.

Исследуем тройку x₁, x₄, x₅:

278

Таким образом, в данном случае все отношения

Δk

Δ

  (k = 1, 2, 3) положительны и по теореме 2 п. 28.8 элементы x₁, x₄, х₅ образуют базис.

Чтобы написать систему ограничений вида (12), преобразуем матрицу В системы ограничений к необходимому виду. Предварительно переставим столбцы коэффициентов при х₄ и х₅ соответственно на второе и третье места.

Тогда

Последняя матрица определяет систему уравнений

(27)

279

Линейная форма f через свободные переменные х₂ и x₃ запишется следующим образом:

f(x) = x₄ - x₅ =

1

5

  -

2

5

 x₂ +

4

5

 x₃

или f +

2

5

 x₂ -

4

5

 x₃ =

1

5

 

Таким образом, теперь необходимо найти минимум линейной функции

f +

2

5

 x₂ -

4

5

 x₃ =

1

5

 

при ограничениях (27).

Здесь базис B₁ = {x₁, x₄, x₅}, ограничения и функция f записаны в форме (12), (13), и мы можем начать применение симплекс-метода.

В данном случае с₂ =

2

5

  > 0 и в первом столбце матрицы ограничений имеется положительный элемент a₁₂ =

1

5

  > 0.

Отношение

b1

a12

  = 8 > 0, т. е. мы имеем случай III₊ и а₁₂ - разрешающий элемент.

Составим первую симплекс-таблицу:

Таблица 6*

280

Здесь разрешающий элемент а₁₂. Преобразуем таблицу 6* в таблицу 7*. Строку для xl умножим на 5 и перенесем ее в табл. 7*. Строку для х₄ перенесем в табл. 7* без изменений (так как а₄₂ = 0).

Затем умножим первую строку на 2 и прибавим результат к последней строке. Далее умножим первую строку на 2 и вычтем из строки для формы f. Кроме того, переставим местами столбцы для x_l и х₂. В результате табл. 7* будет иметь следующий вид:

Таблица 7*

В табл. 7* коэффициенты формы f неположительны (с₁ = -2, с₃ = 0), поэтому при ограничениях (27)

min

xj≥0 j=1,…,5

  f = -3,

и задача решена.

Замечание 7. Можно было бы исследовать все десять троек из элементов x₁, х₂, х₃, х₄, х₅. Затем, найдя все базисы B_j(j = 1, 2, ..., j₀; j₀ < 10), мы можем найти минимум f при ограничениях (27) как минимальное значение среди f_B1 , ..., f_Bj0 .

281