Российский экономический

Задача 6.1.
Решить следующую задачу целочисленного линейного про-
граммирования: 
max (7𝑥
1
+ 9𝑥
2
)
(6.4) 
−𝑥
1
+ 3𝑥
2
≤ 6
, 
7𝑥
1
+ 𝑥
2
≤ 35
, 
𝑥
1
, 𝑥
2
≥ 0
, 
𝑥
1
, 𝑥
2
∈ 𝑍
. 
Решение
. Область допустимых решений задачи с ослабленными ограни-
чениями (четырехугольник ABCD), получаемой путем отбрасывания требова-
ния целочисленности переменных, а также оптимальное решение этой задачи 
изображены на рис. 6.1. 
116

---

Рис. 6.1. 
Область допустимых решений и оптимальное решение задачи 
Добавляя в задаче с ослабленными ограничениями две новые неотрица-
тельные переменные, приведем задачу к стандартному виду: 
max (7𝑥
1
+ 9𝑥
2
)
(6.5) 
−𝑥
1
+ 3𝑥
2
+ 𝑥
3
≤ 6
, 
7𝑥
1
+ 𝑥
2
+ 𝑥
4
≤ 35
, 
𝑥
1
, 𝑥
2
, 𝑥
3
, 𝑥
4
≥ 0
. 
Применяя симплекс-метод (этап 1) для решения задачи, получим послед-
нюю симплексную таблицу, определяющую оптимальное решение, в следую-
щем виде (табл. 6.1). 
Таблица 6.1 
Симплексная таблица оптимального решения
 
х
1
х
2
х
3
х
4
Решение 
Z 
0 
0 
28/11 
15/11 
63 
x
2
0 
1 
7/22 
1/22 
7/2 
x
1
1 
0 
–1/22 
3/22 
9/2 
Оптимальное значение целевой функции равное 63 достигается в точке 
𝑥
∗
= (𝑥
1
∗
, 𝑥
2
∗
, 𝑥
3
∗
, 𝑥
4
∗
)
с координатами 
𝑥
1
∗
= 9/2
, 
𝑥
2
∗
= 7/2
, 
𝑥
3
∗
= 0
, 
𝑥
4
∗
= 0
. По-
скольку оптимальное решение задачи с ослабленными ограничениями не явля-
ется целочисленным, то необходимо переходить к этапу 2, т.е. строить пра-
вильное отсечение. Поскольку обе компоненты оптимального решения нецело-
численны и их дробные части равны, то выберем в качестве переменной, на ба-
зе которой строится отсечение, например, переменную 
𝑥
2
. Тогда, добавляя но-
вую неотрицательную переменную 
𝑥
5
, получаем согласно (6.3) дополнительное 
ограничение следующего вида:
− {
7
22
} 𝑥
3
− {
1
22
} 𝑥
4
+ 𝑥
5
= − {
7
2
}
, 
или
−
7
22
𝑥
3
−
1
22
𝑥
4
+ 𝑥
5
= −
1
2
. 
(6.6) 
117

---

Добавляя новое ограничение к ограничениям задачи, получаем модифи-
цированную задачу линейного программирования со следующей исходной 
симплекс-таблицей (табл. 6.2) 
Таблица 6.2