Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки

• Название: Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
• Анкор: Езу9у
• Дата: 03.11.2022
• Размер: 5.85 Mb.
• Имя файла: 978‑5‑7996-2956-4_2020.pdf
• Тип: Учебное пособие; #769125
• страница: 14 из 21

Шаг 1. Методом Гаусса — Жордана получаем нули в М-строке в столбцах с номерами n + 1, …, n + m. Для этого последовательно выбираем в качестве разрешающих элементов коэффициенты при x
n+1
, …, x
n+m
(единицы) и далее прибавляем к элементам М-строки элементы всех строк, умноженные на (−M).
При этом вся таблица, кроме верхней строки, не меняется, т. е. пересчиты- вается только М-строка.
Шаг 2. M — достаточно большое число, поэтому значение оценок зависит от M. Следовательно, в первую очередь, с помощью жордановых преобразо- ваний добиваемся того, чтобы в строке целевой функции все элементы были неотрицательными. По мере выведения неизвестных x
n+1
, …, x
n+m
из базисных, соответствующие столбцы с искусственными переменными вычеркиваем. После

118
выведения из базиса всех искусственных переменных М-строку, состоящую из нулей, также вычеркиваем.
Шаг 3. Решаем оставшуюся задачу симплекс-методом.
Замечание 1.В предыдущей табл. 4.24 коэффициенты при неизвестных целевой функции занесены в две строки. Это сделано для удобства и просто- ты вычислений. Можно аналогично для целевой функции использовать одну строку (табл. 4.25).
Таблица 4.25
БП
0
x
x
1
x
2
…
x
n
x
n+1
x
n+2
…
x
n+m
b
i
0
Z x
=
 
1
–c
1
–c
2
…
–c
n
M
M
…
M
0
x
n+1 0
a
11
a
12
…
a
1n
1 0
…
0
b
1
x
n+2 0
a
21
a
22
…
a
2n
0 1
…
0
b
2
…
…
…
…
…
…
…
…
…
…
…
x
n+m
0
a
m1
a
m2
…
a
mn
0 0
…
1
b
m
Замечание 2. Иногда необязательно вводить все m искусственных перемен- ных. Например, в следующем примере вводим четыре дополнительных и две искусственных переменных.
Пример 4.6. Решить методом искусственного базиса задачу линейного программирования:
1 2
( )
3
min,
Z X
x
x
= − +
→
1 2
1 2
1 2
1 2
3 6,
2 1,
5,
3 6;
x
x
x
x
x
x
x
x
+
≥

 − +
≤


+
≤


−
≥

1 2
0,
0.
x
x
≥
≥
Решение. Введем дополнительные (Д) и искусственные (И) переменные:
Д
И
1 2
3 7
1 2
4 1
2 5
1 2
6 8
3 6,
2 1,
5,
3 6;
x
x
x
x
x
x
x
x
x
x
x
x
x
x
+
≥
−
+

− +
≤
+


+
≤
+


−
≥
−
+

1 2
0,
0.
x
x
≥
≥

119
Составим расширенную задачу. Так как рассматриваемая задача на мини- мум, неизвестные x
7
и x
8
вводятся в целевую функцию с коэффициентом +M.
Имеем:
1 2
7 8
( )
3
min,
Z X
x
x M x M x
= − +
+
+
→
 
1 2
3 7
1 2
4 1
2 5
1 2
6 8
3 6,
2 1,
5,
3 6;
x
x x
x
x
x
x
x
x
x
x
x
x
x
+
−
+
=

− +
+
=


+
+
=


−
−
+
=

(
)
0 1, 8 .
j
x
j
≥
=
Введем новую переменную
0 1
2 7
8 3
x
x
x Mx Mx
= − +
+
+

и перепишем это уравнение в виде
0 1
2 7
8 3
0.
x x
x Mx Mx
+ −
−
−
=

Рассмотрим новую систему уравнений:
0 1
2 7
8 1
2 3
7 1
2 4
1 2
5 1
2 6
8 3
0,
3 6,
2 1,
5,
3 6;
x x
x
Mx Mx
x
x x
x
x
x
x
x
x
x
x
x
x
x
 + −
−
−
=

+
−
+
=

− +
+
=


+
+
=

−
−
+
=


(
)
0 1, 8 .
j
x
j
≥
=
Наша цель: найти неотрицательное базисное решение этой системы так, чтобы коэффициенты целевой функции при x
7
и x
8
обратились в ноль, кроме того, преобразования должны обеспечить минимум целевой функции. Рас- смотрим табл. 4.26.
Таблица 4.26
БП
0
x
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
b
i
М-строка
0 0
0 0
0 0
0
–M
–M
0 0
Z x
=
 
1 1
–3 0
0 0
0 0
0 0
0 1
3
–1 0
0 0
1 0
6
x
4 0
–1 2
0 1
0 0
0 0
1
x
5 0
1 1
0 0
1 0
0 0
5 0
3
–1 0
0 0
–1 0
1 6

120
Прибавим к элементам М-строки элементы первой и четвертой строк ог- раничений, умноженные на M (табл. 4.27).
Таблица 4.27
БП
0
x
x
1
↓
x
2
x
3
x
4
x
5
x
6
x
7
x
8
b
i
θ
1
М-строка
0 4M
2M
–M
0 0
–M
0 0
12M
0
x
1 1
–3 0
0 0
0 0
0 0
x
7 0
1 3
–1 0
0 0
1 0
6 6
x
4 0
–1 2
0 1
0 0
0 0
1
—
x
5 0
1 1
0 0
1 0
0 0
5 5
← x
8 0
3
–1 0
0 0
–1 0
1 6
2
Теперь таблица готова к применению симплекс-метода с использованием условий оптимальности и неотрицательности переменных. Первое допустимое решение X
1
= (0, 0, 0, 1, 5, 0, 6, 6) с базисом (A
7
, A
4
, A
5
, А
8
) и значением целевой функции Z(X
1
) = 12М не является оптимальным, так как в М-строке имеются положительные коэффициенты. Наибольший коэффициент 4M соответствует переменной x
1
, которая и будет разрешающей. Находим θ
01
= min{6, 5, 2} = 2.
Разрешающий элемент выделяем рамкой (табл. 4.27). Новую симплекс-табли- цу получаем с помощью жордановых преобразований. Вектор A
8
, выводимый из базиса (вводится A
1
), исключаем из рассмотрения (вычеркиваем). Получим новое решение X
2
= (2, 0, 0, 3, 3, 0, 4, 0) с базисом (A
7
, A
4
, A
5
, А
1
) и значением целевой функции
1 2
3
( )
( 6 12 )
Z X
M
= − +
(табл. 4.28). Это решение, так же как и предыдущее, не является оптимальным. Выбираем наибольший положитель- ный коэффициент М-строки 10M при x
2
и находим θ
02
= min{6/5, 9/5, 9/4} = 6/5.
Таблица 4.28
БП
x
0
x
1
x
2
↓
x
3
x
4
x
5
x
6
x
7
x
8
b
i
θ
2
М-строка
0 0
10M
–3M
0 0
M
0
—
12M
x
0 3
0
–8 0
0 0
1 0
—
–6
← x
7 0
0
10
–3 0
0 1
3
—
12
6/5
x
4 0
0 5
0 3
0
–1 0
—
9 9/5
x
5 0
0 4
0 0
3 1
0
—
9 9/4
x
1 0
3
–1 0
0 0
–1 0
—
6
—
Новый разрешающий элемент число 10. В базис вводится A
2
, выводится A
7
, поэтому столбец при x
7
исключаем из рассмотрения (вычеркиваем). Также исключаем из рассмотрения целевой функции М-строку. С помощью преобра- зований Гаусса — Жордана получаем табл. 4.29.

121
Таблица 4.29
БП
x
0
x
1
x
2
x
3
x
4
x
5
x
6
↓
x
7
b
i
θ
6
Z = x
0 5
0 0
–4 0
0 3
—
6
x
2 0
0 10
–3 0
0 1
—
12 12
x
4 0
0 0
5 10 0
–5
—
10
—
← x
5 0
0 0
2 0
5
1
—
7
7
x
1 0
10 0
–1 0
0
–3
—
24
—
Получено решение
3 12 6 7
, , 0,1, , 0, 0, 0 5 5 5
X


= 



с базисом (A
2
, A
4
, A
5
, А
1
) и зна- чением целевой функции
3 6
( )
1,2.
5
Z X = =
Далее вводим в базис вектор A
6
, выводим из базиса A
5
. С помощью элемен- тарных преобразований над строками получим решение
4 9 1 9
, , 0, , 0, 7 2 2 2
X


= 



с базисом (A
2
, A
4
, A
6
, А
1
) и значением целевой функции Z(X
4
) = −3 (табл. 4.30).
Полученное решение является оптимальным решением расширенной задачи, так как все оценки небазисных переменных отрицательные, что соответствует целевой функции
0 3
5
( )
2 3
3.
Z X
x
x
x
≡
=
+
−
 

В силу неотрицательности неизвест- ных
0 3.
x ≥ −

Исходная задача также имеет оптимальное решение, которое получается из оптимального решения расширенной задачи отбрасыванием нулевых искусственных и дополнительных переменных, то есть min min
9 1
,
,
3.
2 2
X
X
Z
∗


=
=
= −




Таблица 4.30
БП
x
0
x
1
x
2
x
3
x
4
x
5
x
6
b
i
Z = x
0 1
0 0
–2 0
–3 0
–3
x
2 0
0 2
–1 0
–1 0
1
x
4 0
0 0
3 2
5 0
9
x
6 0
0 0
2 0
5 1
7
x
1 0
2 0
1 0
3 0
9
Пример 4.7. Решить методом искусственного базиса задачу линейного программирования:
1 2
3
( )
2 2
min,
Z X
x
x
x
= +
+
→

122 1
2 3
1 2
3 1
2 3
4 1,
2 2
2,
2 2
6;
x
x
x
x
x
x
x
x
x
 +
−
≥
 − + =

 +
−
≤

0,
1, 3.
j
x
j
≥
=
Решение. Введем дополнительные (Д) и искусственные (И) переменные:
Д
И
1 2
3 4
6 1
2 3
7 1
2 3
5 4
1,
2 2
2,
2 2
6;
x
x
x
x
x
x
x
x
x
x
x
x
x
 +
−
≥
−
+
 − + =
+

 +
−
≤
+

0,
1, 7.
j
x
j
≥
=
Составим расширенную задачу. Так как рассматривается задача на мини- мум, то неизвестные x
6
и x
7
вводятся в целевую функцию с коэффициентом +M.
Имеем:
( )
1 2
3 6
7 2
2
min,
Z X
x
x
x M x M x
= +
+
+
+
→
 
1 2
3 4
6 1
2 3
7 1
2 3
5 4
1,
2 2
2,
2 2
6;
õ
x
x x
x
x
x
x
x
x
x
x
x

+
−
−
+
=
 − +
+
=

 +
−
+
=

0,
1, 7
j
x
j
≥
=
Введем
0 1
2 3
6 7
2 2
x
x
x
x Mx Mx
= +
+
+
+

и аналогично предыдущему рассмот- рим симплексные преобразования без введения дополнительной М-строки
(табл. 4.31).
Таблица 4.31
БП
0
x
x
1
x
2
x
3
x
4
x
5
x
6
x
7
b
i
0
Z x
=
 
1
–1
–2
–2 0
0
–M
–M
0 0
1 1
–4
–1 0
1 0
1 0
1
–2 2
0 0
0 1
2
x
5 0
1 2
–2 0
1 0
0 6
Прибавим к строке целевой функции первую и вторую строки, умноженные на M (табл. 4.32).

123
Таблица 4.32
БП
0
x
x
1
↓
x
2
x
3
x
4
x
5
x
6
x
7
b
i
θ
1 0
Z x
=
 
1
−1 + 2M −2 − M −2 − 2M −M
0 0
0 3M
← x
6 0
1
1
−4
−1 0
1 0
1
1
x
7 0
1
−2 2
0 0
0 1
2 2
x
5 0
1 2
−2 0
1 0
0 6
6
Таблица готова к применению симплекс-метода. Разрешающий элемент на пересечении первой строки и столбца x
1
. С помощью элементарных пре- образований над строками получаем табл. 4.33.
Таблица 4.33
БП
0
x
x
1
x
2
x
3
↓
x
4
x
5
x
6
x
7
b
i
θ
3 0
Z x
=
 
1 0
–1–3M –6 + 6M –1 + M
0
—
0 1 + M
x
1 0
1 1
–4
–1 0
—
0 1
← x
7 0
0
–3
6
1 0
—
1 1
1/6
x
5 0
0 1
2 2
1
—
0 5
5/2
Первое допустимое решение X
1
= (1, 0, 0, 0, 5, 0, 1) с базисом (A
1
, A
7
, A
5
) и значением целевой функции Z(X
1
) = 1 + М не является оптимальным, так как в строке целевой функции имеются положительные оценки. Наибольший коэффициент −6 + 6M соответствует переменной x
3
, которая и будет разреша- ющей. Находим θ
03
= min{1/6, 5/2} = 1/6. Разрешающий элемент выделяем рам- кой. Новую симплекс-таблицу (табл. 4.34) получаем с помощью жордановых преобразований.
Таблица 4.34
БП
0
x
x
1
x
2
x
3
x
4
↓
x
5
x
7
b
i
θ
4 0
Z x
=
 
3 0
–24 0
0 0
—
6
x
1 0
3
–3 0
–1 0
—
5
← x
3 0
0
–3 6
1
0
—
1
1
x
5 0
0 6
0 5
3
—
14 14/5
Следующее решение
2 5
1 14
, 0, , 0, , 0, 0 3
6 3
X


= 



с базисом (A
1
, A
3
, A
5
) и значе- нием целевой функции Z(X
2
) = 2 является оптимальным (среди элементов
Z-cтроки нет положительных). Далее замечаем, что коэффициент целевой функции при x
4
(небазисная переменная) равен нулю. Это означает, что мы

124
можем ввести разрешающий элемент в столбце x
4
, при этом значение целевой функции не изменится (табл. 4.35).
Таблица 4.35
БП
0
x
x
1
x
2
x
3
x
4
x
5
b
i
0
Z x
=
 
1 0
–8 0
0 0
2
x
1 0
1
–2 2
0 0
2
x
4 0
0
–3 6
1 0
1
x
5 0
0 7
–10 0
1 3
Итак, получено еще одно оптимальное решение X
3
= (2, 0, 0, 1, 3, 0, 0) с тем же значением целевой функции Z(X
3
) = 2.
Таким образом, задача имеет бесконечное множество решений. Каждое из них представляет собой выпуклую линейную комбинацию решений
2 5
1
, 0,
3 6
X


= 



и X
3
= (2, 0, 0); записываем это в виде
(
)
min
2 3
min
1
, 0 1,
2.
X
X
X
Z
= α
+ − α
≤ α ≤
=
Замечание. В ответе отброшены дополнительные и искусственные пере- менные.
4.6.2. Вырожденность
При решении задач симплекс-методом проверка условия неотрицательно- сти может привести к неоднозначному выбору исключаемой переменной. В этом случае на следующем шаге одна или более базисных переменных принимает нулевое значение. То есть новое решение будет вырожденным. С практической точки зрения вырожденность объясняется тем, что в исходной задаче в системе ограничений имеется, по крайней мере, одно или несколько «избыточных» ограничений (см. далее пример 4.8). Существуют примеры, показывающие, что при определенном выборе номеров строк и столбцов симплекс-метод может привести к циклическому перебору базисов одной и той же вершины. В таком случае говорят, что происходит зацикливание симплекс-процедуры. Существуют правила, предотвращающие зацикливание, однако, замедляющие вычисли- тельный процесс. Простейшее правило (правило Блэнда
*
)в задаче вычисле- ния максимального (минимального) значения целевой функции используется
*
Роберт Гэри Блэнд (род. 25 февраля 1948 г.) — американский математик, профессор в области исследования операций в Корнеллском университете. Правило Блэнда разработано им в Центре исследования операций и эконометрики в Бельгии.

125
во время итерации симплекс-метода для определения, какой вектор вводится в базис (т. е. вводимое неизвестное) и какая строка (исключаемое неизвестное) выводится из базиса.
Напомним: J — множество индексов (номеров) базисных неизвестных. Для определенности сформулируем теорему для задачи на максимум.