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

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

Замечание. В задаче на минимум все
0.
m j
c
+
≤

Итак, справедлива теорема 4.4.
Теорема 4.4 (правило оптимальности решения). Допустимое базисное ре- шение
0
X
= (β
1
, β
2
, …, β
m
, 0, …, 0) является оптимальным в том и только в том случае, когда среди элементов Z-строки нет отрицательных в задаче на макси- мум (нет положительных в задаче на минимум). При этом x
0
= β
0
— оптимальное значение целевой функции.
Если коэффициенты целевой функции имеют разные знаки, то соответст- вующее неотрицательное базисное решение не является оптимальным.
Пусть существует
0,
j
c <

например, j = m + 1, т. е.
1 0.
m
c
+
<

Есть возможность увеличения x
0
за счет увеличения x
m+1
, но при этом остальные базисные переменные x
1
, …, x
m
должны быть неотрицательными:
1 1
1 1 1
, 1 1
0 0.
m
m
m
m
m m
m
x
x
,
x
x
+
+
+
+

= β − α
≥



= β − α
≥


(4.21)
Рассмотрим случаи:
1. Пусть все
,
1 0,
i m+
α
≤
тогда ввести в базис x
m+1
нельзя: это приводит к не- допустимому решению (x
m+1
можно брать сколь угодно большим, что приводит к неограниченности целевой функции).
2. Пусть существует коэффициент
,
1 0
i m+
α
>
при неизвестной x
m+1
> 0, тогда
, 1
max
1
:
0
,
1
min
i m
i
m
i a
i m
x
+
+
>
+
β
=
α
Пусть i = k, где реализуется этот минимум. В системе (4.21) для переменной x
k
выполняется равенство: max
,
1 1
0
,
k
k
k m
m
x
x
+
+
=
= β − α
т. е. x
k
стано- вится свободной переменной, а x
m+1
— базисной. Далее за разрешающий элемент

102
берем α
k, m+1
и пересчитываем симплекс-таблицу, используя преобразования
Гаусса — Жордана.
Справедливы теоремы 4.5–4.6.
Теорема 4.5 (правило неограниченности целевой функции). Если среди элементов Z-строки найдется неположительное число
0
j
c ≤

и при этом все ко- эффициенты α
ij
≤ 0 при переменной x
j
в задаче на максимум, то max Z(X) = + ∞, аналогично, если существует
0
j
c ≥

и
1,
i
m
∀ =
α
ij
≤ 0 (в задаче на минимум), то min Z(X) = −∞.
Теорема 4.6 (правило перехода к новому допустимому базисному решению).
Если существует j∉J:
0
j
c <

(существует j∉J:
0)
j
c >

и среди коэффициентов при переменной x
j
существуют α
ij
> 0, то можно найти новое базисное решение, на котором значение целевой функции будет больше в задаче на максимум и меньше — в задаче на минимум.
Чтобы обеспечить наибольшее изменение целевой функции при переходе от одного допустимого базисного решения к другому, векторы, выводимый из базиса и вводимый в базис решения, полезно выбирать из условий:
• в задаче на максимум min { ,
};
j
c j J
∉

(4.22)
• в задаче на минимум max { ,
}.
j
c j J
∉

(4.23)
Замечание. Приведенные теоремы 4.4–4.6 слово в слово повторяют теоремы
4.1–4.3. В самом деле, в Z-строке табл. 4.6
(
)
1 1 2 2 1
1, ,
m
j
j
j
m mj
j
i ij
j
i
c c
c
c
c
c
c j m
n
=
= α + α + + α − =
α −
= +
∑


(4.24)
0 1 1 2 2 1
m
m m
j j
j
c
c
c
c
=
β = β + β + + β =
β
∑

(4.25)
Сравнивая правые части формул (4.24)–(4.25) и (4.6)–(4.7), заключаем, что
(
)
0 0
1, ,
j
j
c
j m
n
= ∆
= +
β = ∆


В дальнейшем коэффициенты преобразованной целевой функции
j
c
(j = m + 1, …, n) будем также называть оценками разложения вектора A
j
по ба- зису допустимого решения (или оценками свободных переменных x
j
), а Z-стро- ку — оценочной.
Пример 4.2. Рассмотримпример планирования для предприятия, выпуска- ющего два вида продукции и расходующего при этом три вида сырья. Составим

103
план выпуска продукции, обеспечивающий максимальный доход. Исходные данные задачи таковы (табл. 4.7).
Таблица 4.7
Виды сырья
Запасы сырья (ресурсы)
Расход сырья на единицу продукции
P
1
P
2
А
120 3
2
В
120 2
3
С
44 1
1
Цена единицы продукции, ден. ед.
40 30
Кроме того, известно, что суточный спрос на продукцию P
1
превышает суточный спрос на продукцию P
2
не более чем на 30 ед.
Обозначим через x
1
и x
2
количество единиц продукции P
1
и P
2
соответственно.
Составим математическую модель задачи:
1 2
1 2
1 2
1 2
1 2
1 2
( ) 40 30
max,
3 2
120,
2 3
120,
44,
30;
0,
0.
Z X
x
x
x
x
x
x
x
x
x
x
x
x
=
+
→
+
≤


+
≤


+
≤


≤
+

≥
≥
Решение. Приведем задачу линейного программирования к каноническому виду. Для этого сначала последнее ограничение перепишем в виде
1 2
30.
x x
−
≤
Далее вводим дополнительные (Д) неизвестные x
3
, x
4
, x
5
и x
6
для преобра- зования неравенств в равенства:
Д
1 2
3 1
2 4
1 2
5 1
2 6
3 2
120,
2 3
120,
44,
30;
0,
1, 6.
j
x
x
x
x
x
x
x
x
x
x
x
x
x
j
+
≤
+


+
≤
+


+
≤
+


−
≤
+

≥
=

104
Итак, исходная задача принимает вид:
( )
1 2
1 2
3 1
2 4
1 2
5 1
2 40 30
max,
3 2
120,
2 3
120,
44,
30;
0,
1, 6.
j
Z X
x
x
x
x x
x
x
x
x
x
x
x
x
x
x
j
=
+
→
+
+
=


+
+
=


+
+
=


−
+
=

≥
=
6
Введем новую переменную x
0
= 40x
1
+ 30x
2
и рассмотрим систему линейных уравнений:
0 1
2 1
2 3
1 2
4 1
2 5
1 2
6 40 30 0,
3 2
120,
2 3
120,
44,
30;
x
x
x
x
x x
x
x
x
x
x
x
x
x
x
−
−
=


+
+
=

+
+
=


+
+
=

−
+
=

(4.26)
0,
1,6.
j
x
j
≥
=
Далее представим условия задачи в виде симплекс-таблицы, составленной аналогично табл. 4.5. Коэффициенты первого уравнения системы (4.26) запи- сываются отдельной строкой. Они образуют Z-строку (или оценочную строку).
Коэффициенты каждого из остальных уравнений (ограничений) записываем в отдельную строку. Значения правых частей этих уравнений записаны в столб- це «В» (табл. 4.8).
Таблица 4.8
БП
x
0
x
1
↓
x
2
x
3
x
4
x
5
x
6
B
θ
1
Z = x
0
→max
1
–40
–30 0
0 0
0
0
x
3 0
3 2
1 0
0 0
120 40
x
4 0
2 3
0 1
0 0
120 60
x
5 0
1 1
0 0
1 0
44 44
← x
6 0
1
–1 0
0 0
1 30
30
Заметим, что столбцы коэффициентов при неизвестных x
0
, x
3
, x
4
, x
5
и x
6
образуют единичный базис и система уравнений (4.26) является разрешенной.
Неизвестные x
1
и x
2
являются свободными и равны нулю, а базисные равны правым частям ограничений (4.26). Первое базисное решение X
1
= (0, 0, 120, 120,

105 44, 30). Это решение говорит о том, что предприятие ничего не производит, а все ресурсы остаются неизрасходованными. Значение целевой функции Z(X
1
) = 0 не является оптимальным. Неизвестные x
1
и x
2
равны нулю, возрастание этих неизвестных хотя бы на единицу приводит к увеличению целевой функции
Z = x
0
= 40x
1
+ 30x
2
на 40 ед. (при увеличении x
1
) или 30 ед. (при увеличении x
2
).
Поскольку коэффициент целевой функции при x
1
больше, чем при x
2
, пере- менную x
1
вводят в число базисных. Если обратиться к табл. 4.8, то вводимая в базис неизвестная имеет в строке целевой функции наибольший по модулю отрицательный коэффициент, в нашем случае это (−40). Итак, наращиваем значение переменной x
1
= t. В этом случае значение целевой функции увеличи- вается на 40t. Увеличение продукта на t уменьшает соответствующий ресурс тоже на t. Для сохранения строчных балансов следует изменить значения ба- зисных неизвестных:
( ) ( ,0,120 3 ,120 2 ,44 ,30 ).
X t
t
t
t
t
t
=
−
−
−
−
Заметим, что при t = 30 переменная x
6
= 30 − t обращается в ноль, в то время как остальные неизвестные остаются положительными или не изменяются.
То есть значение t = 30 является наименьшим значением, при котором неиз- вестные остаются неотрицательными. Так как переменная x
6
= 30 − t при t > 30 становится отрицательной, то лучше ее вывести из базисных (в табл. 4.8 указано стрелкой). Итак, за разрешающий элемент примем число 1 в последней строке и в столбце переменной x
1
. При этом x
1
переходит в базисные, а x
6
— в сво- бодные. Таким образом мы пришли к пониманию условия, обеспечивающего неотрицательность правых частей уравнений системы:
0
:
0
min
il
i
k
l
i
a
il
kl
b
b
a
a
∀ >
 
θ =
=
 
 
Напомним, что здесь l — номер вектора A
l
, вводимого в базис, а k — номер вектора A
k
, выводимого из базиса (номер строки матрицы системы, в которой следует выбирать разрешающий элемент для жорданова преобразования). Име- ем: θ
01
= min {40, 60, 44, 30} = 30. Выбираем в качестве разрешающего элемента указанное выше число 1. В результате из базиса выведем столбец A
6
. Отметим число 1 рамкой. С помощью линейных преобразований над строками на месте остальных элементов этого столбца получим нули (табл. 4.9).
Мы получили новое допустимое базисное решение X
2
= (30, 0, 30, 60, 14, 0), которому отвечает большее значение целевой функции Z(X
2
) = 1 200 = 40 · 30 +
+ 30 · 0. На рис. 4.1 решение из начала координат переместилось в точку
А(30, 0).

106
Таблица 4.9
БП
x
0
x
1
x
2
↓
x
3
x
4
x
5
x
6
b
i
θ
2
Z = x
0 1
0
–70 0
0 0
40
1 200
← x
3 0
0
5
1 0
0
–3 30
30/5 = 6
x
4 0
0 5
0 1
0
–2 60 60/5 = 12
x
5 0
0 2
0 0
1
–1 14 14/2 = 7
x
1 0
1
–1 0
0 0
1 30
—
Будем наращивать теперь переменную x
2
= t. Строка целевой функции эквивалентна уравнению Z = x
0
= 70x
2
− 40x
6
+ 1 200. Поэтому значение целевой функции увеличится на 70t. Находим θ
02
= min{6, 12, 7} = 6. Разрешающий эле- мент выбираем в первой строке ограничений: число 5 (табл. 4.9). Используя жордановы преобразования, получим новую таблицу (табл. 4.10).
Таблица 4.10
max
x
0
x
1
x
2
x
3
x
4
x
5
x
6
↓
b
i
θ
6
Z = x
0 1
0 0
14 0
0
–2
1 620
x
2 0
0 5
1 0
0
–3 30
—
x
4 0
0 0
–1 1
0 1
30 30
← x
5 0
0 0
–2 0
5
1
10
10
x
1 0
5 0
1 0
0 2
180 90
Следующее базисное решение X
3
= (36, 6, 0, 30, 2, 0), которому отвечает значение целевой функции Z(X
3
) = 1 620 = 40 · 36 + 30 · 6. На рис. 4.1 из точки
А(30; 0) осуществлен переход в точку В(36; 6). Аналогично предыдущему вво- дим в базис А
6
и выводим А
5
. С помощью элементарных преобразований над строками получим табл. 4.11.
Таблица 4.11
БП
x
0
x
1
x
2
x
3
x
4
x
5
x
6
b
i
Z = x
0 1
0 0
14 0
10 0
1 640
x
2 0
0 1
–1 0
3 0
12
x
4 0
0 0
1 1
0 0
20
x
6 0
0 0
0 0
–5 1
10
x
1 0
1 0
1 0
–2 0
32
Теперь наша таблица отвечает системе уравнений (4.26), разрешенной от- носительно базисных переменных x
0
, x
1
, x
2
, x
4
, x
6
. Итак, мы получили базисное

107
решение системы (4.24). Обратим внимание на то, что в оценочной строке нет отрицательных элементов! Это означает, что решение
4
(32,12, 0, 20, 0,10)
X =
и значение Z(X
4
) = 1 640 = 40 · 32 + 30 · 12 являются оптимальными.
Действительно, строка целевой функции эквивалентна уравнению Z = x
0
≡
≡ −14x
3
− 10x
5
+ 1 640. В силу неотрицательности неизвестных верно неравенство
0 3
5 1640 14 10 1640.
x
x
x
≡
−
−
≤
Следовательно, max max
(32,12, 0, 20, 0,10),
1640.
X
X
Z
∗
=
=
=
С экономической точки зрения получено перераспределение продукции и ресурсов так, что введенные новые продукты x
3
, х
4
, x
5
и x
6
имеют или от- рицательные или нулевые цены и поэтому выпускаться не должны. Следует производить 32 ед. продукции P
1
и 12 ед. — P
2
. Ежедневный доход составляет
1 640 (ден. ед.).
Замечание. В процессе жордановых преобразований строку целевой функ- ции (Z-строку) не следует выбирать разрешающей, но преобразовывать ее нужно по правилам преобразования остальных строк. В результате каждого шага целевая функция, как и базисные переменные, окажется выраженной через свободные переменные.
Рис. 4.1. Геометрическая иллюстрация примера 4.2 60 20 40 20 60
А
x
2 40
О
В
D
ν
x
1

108
Покажем на рис. 4.1 путь по вершинам многоугольника исходной задачи, начиная с первой (начало координат) и кончая оптимальной (вершина D) (весь путь: вершины O→A→B→D). Заметим еще раз, что значение целевой функции при переходе к каждой следующей вершине увеличивалось.
Пример 4.3 (бесконечное множество решений). Решить симплексным ме- тодом следующую задачу линейного программирования:
1 2
( ) 5 10
max,
Z X
x
x
=
+
→
1 2
1 2
1 2
2 10,
2 6,
4;
x
x
x
x
x
x
+
≤

 − + ≤


−
≤

1 2
0,
0.
x
x
≥
≥
Решение. Запишем задачу в канонической форме. Для этого введем допол- нительные переменные x
3
, х
4
, x
5
:
1 2
3 1
2 4
1 2
5 2
10,
2 6,
4;
x
x
x
x
x
x
x
x
x

+
+
=
− +
+
=


−
+
=

0,
1, 5.
j
x
j
≥
=
Обратим внимание на прямую 5x
1
+ 10x
2
= α, представляющую целевую функцию, параллельную прямой, соответствующей неравенству x
1
+ 2x
2
≤ 10
(которое в точке максимума выполняется как точное равенство). В этом случае целевая функция принимает одно и то же оптимальное значение на некотором множестве точек границы области допустимых решений. Эти решения назы- вают оптимальными альтернативными решениями.
На рис. 4.2 каждая точка отрезка BC соответствует оптимальному решению со значением целевой функции Z(X) = 50.
Построим таблицу Гаусса — Жордана (табл. 4.12). Для сохранения неотри- цательности правых частей уравнений вводим параметр θ
l
. Получим первое базисное решение X
1
= (0, 0, 10, 6, 4) с базисом (A
3
, A
4
, A
5
) и значением целевой функции Z(X
1
) = 0. На рис. 4.2 это соответствует началу координат.
Будем наращивать x
2
. Находим θ
2
= min (5, 3) = 3. Разрешающий элемент выбираем в столбце переменной x
2
и во второй строке: число 2 (выделено рамкой). Используя жордановы преобразования, получим новую таблицу
(табл. 4.13).

109
Таблица 4.12
БП
x
0
x
1
x
2
↓
x
3
x
4
x
5
b
i
θ
2
Z = x
0
→ max
1
–5
–10 0
0 0