2024年4月2日发(作者：铎天媛)
第二章 线性规划
P
73
4. 将下面的线性规划问题化成标准形式
⎧
max
x
1
−
x
2
+
2
x
3
⎪
s
..
tx
1
−
2
x
2
+
3
x
3
≥
6
⎪
⎪
2
x
1
+x
2
−x
3
≤
3
⎨
⎪
0
≤
x
1
≤
3
⎪
⎪
−1≤
x
2
≤6
⎩
解：将max 化为 min， x
3
用x
4
−x
5
代替，则
⎧
min
⎪
s..
⎪
t
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
⎧
min
⎪
s..x
1
−2x
2
+3(x
4
−x
5
)≥6
⎪
t
⎪
2x
1
+x
2
−(x
4
−x
5
)≤3
⎪
′
令x
2
=x
2
+1，则
⎨
0
≤
x
1
≤
3
⎪
⎪
−
1
≤
x
2
≤
6
⎪
x
4
,x
5
≥
0
⎪
⎩
−x
1
+x
2
−2(x
4
−x
5
)
′
−1−2(x
4
−x
5
)−x
1
+x
2
′
−1)+3(x
4
−x
5
)≥6x
1
−2(x
2
′
−1)−(x
4
−x
5
)≤32x
1
+(x
2
0
≤
x
1
≤
3
′
≤
70
≤
x
2
x
4
,x
5
≥
0
将线性不等式化成线性等式，则可得原问题的标准形式
⎧
min
⎪
s
..
⎪
t
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
′
−
2
x
4
+
2
x
5
−
1
−
x
1
+
x
2
′
+
3
x
4
−
3
x
5
−
x
6
=
4
x
1
−
2
x
2
′
−
x
4
+
x
5
+
x
7
=
42
x
1
+
x
2
x
1
+x
8
=
3
′
+x
9
=
7
x
2
′
,
x
4
,
x
5
,
x
6
,
x
7
,
x
8
,
x
9
≥
0
x
1
,
x
2
P
73
5
、用图解法求解下列线性规划问题：
⎧
min
x
1
+
3
x
2
⎪
s
..
⎪
tx
1
+
x
2
≥
20
(1)
⎨
≤≤
x
612
1
⎪
⎪
x
2
≥
2
⎩
解：图
2.1
的阴影部分为此问题的可行区域
.
将
X
1
法线方向
等值线
8
目标函数的等值线
x
1
+3x
2
=c(
c
为常数
)
沿它的
负法线方向
(
−1，−3
)
移动到可行区域的边界上.
T
o
12 20
图2.1
X
2
（12，8）
就是该问题的最优解，于是交点其最优
值为36.
P
75
16. 用单纯形法求解下列线性规划问题：
T
运筹学作业参考解答 第1页（共14页）
⎧
min
⎪
t
⎪
s
..
⎪
(1)
⎨
⎪
⎪
⎪
⎩
z
=−
2
x
1
−
x
2
+
x
3
3
x
1
+
x
2
+
x
3
≤60
x
1
−
x
2
+
2
x
3
≤
10
x
1
+
x
2
−
x
3
≤20
x
j
≥
0,
j
=
1,2,3
注（零行元素的获得）：先将目标函
数化成求最小值的形式，再把所有变
量移到等式左边，常数移到等式右
边。则变量前的系数为零行对应的元
素.
解：将此问题化成标准形式
⎧
⎪
min
z
=−
2
x
1
−
x
2
+
x
3
⎪
⎪
s
..
t
3
x
1
+
x
2
+
x
3
+
x
4
=60
⎨
x
+
x
⎪
1
−
x
2
+
2
x
35
=
10
⎪
x
1
+
x
2
−
x
3
+
x
6
=20
⎪
⎩
x
j
≥
0,
j
=
1,2,3,4,5,6
以
x
4
,
x
5
,
x
6
为基变量，可得第一张单纯形表为
x
1
x
2
x
3
x
4
x
5
x
6
RHS
z
21 -1 0 000
x
4
31 1 1 0060
x
5
1-1 2 0 1010
x
6
11 -1 0 0120
以
x
1
为进基变量，
x
5
为离基变量旋转得
x
1
x
4
x
5
x
6
RHS
x
2
x
3
z
0
3 -5 0 -20-20
x
4
04 -5 1 -3030
x
1
1-1 2 0 1010
x
6
02 -3 0 -1110
以
x
2
为进基变量，
x
6
为离基变量旋转得
运筹学作业参考解答
1 注意单纯形表的格式！
2 要用记号把转轴元标出来
3 要记住在单纯形表的左边，用
进基变量代替离基变量
第2页（共14页）
2024年4月2日发(作者：铎天媛)
第二章 线性规划
P
73
4. 将下面的线性规划问题化成标准形式
⎧
max
x
1
−
x
2
+
2
x
3
⎪
s
..
tx
1
−
2
x
2
+
3
x
3
≥
6
⎪
⎪
2
x
1
+x
2
−x
3
≤
3
⎨
⎪
0
≤
x
1
≤
3
⎪
⎪
−1≤
x
2
≤6
⎩
解：将max 化为 min， x
3
用x
4
−x
5
代替，则
⎧
min
⎪
s..
⎪
t
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
⎧
min
⎪
s..x
1
−2x
2
+3(x
4
−x
5
)≥6
⎪
t
⎪
2x
1
+x
2
−(x
4
−x
5
)≤3
⎪
′
令x
2
=x
2
+1，则
⎨
0
≤
x
1
≤
3
⎪
⎪
−
1
≤
x
2
≤
6
⎪
x
4
,x
5
≥
0
⎪
⎩
−x
1
+x
2
−2(x
4
−x
5
)
′
−1−2(x
4
−x
5
)−x
1
+x
2
′
−1)+3(x
4
−x
5
)≥6x
1
−2(x
2
′
−1)−(x
4
−x
5
)≤32x
1
+(x
2
0
≤
x
1
≤
3
′
≤
70
≤
x
2
x
4
,x
5
≥
0
将线性不等式化成线性等式，则可得原问题的标准形式
⎧
min
⎪
s
..
⎪
t
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
′
−
2
x
4
+
2
x
5
−
1
−
x
1
+
x
2
′
+
3
x
4
−
3
x
5
−
x
6
=
4
x
1
−
2
x
2
′
−
x
4
+
x
5
+
x
7
=
42
x
1
+
x
2
x
1
+x
8
=
3
′
+x
9
=
7
x
2
′
,
x
4
,
x
5
,
x
6
,
x
7
,
x
8
,
x
9
≥
0
x
1
,
x
2
P
73
5
、用图解法求解下列线性规划问题：
⎧
min
x
1
+
3
x
2
⎪
s
..
⎪
tx
1
+
x
2
≥
20
(1)
⎨
≤≤
x
612
1
⎪
⎪
x
2
≥
2
⎩
解：图
2.1
的阴影部分为此问题的可行区域
.
将
X
1
法线方向
等值线
8
目标函数的等值线
x
1
+3x
2
=c(
c
为常数
)
沿它的
负法线方向
(
−1，−3
)
移动到可行区域的边界上.
T
o
12 20
图2.1
X
2
（12，8）
就是该问题的最优解，于是交点其最优
值为36.
P
75
16. 用单纯形法求解下列线性规划问题：
T
运筹学作业参考解答 第1页（共14页）
⎧
min
⎪
t
⎪
s
..
⎪
(1)
⎨
⎪
⎪
⎪
⎩
z
=−
2
x
1
−
x
2
+
x
3
3
x
1
+
x
2
+
x
3
≤60
x
1
−
x
2
+
2
x
3
≤
10
x
1
+
x
2
−
x
3
≤20
x
j
≥
0,
j
=
1,2,3
注（零行元素的获得）：先将目标函
数化成求最小值的形式，再把所有变
量移到等式左边，常数移到等式右
边。则变量前的系数为零行对应的元
素.
解：将此问题化成标准形式
⎧
⎪
min
z
=−
2
x
1
−
x
2
+
x
3
⎪
⎪
s
..
t
3
x
1
+
x
2
+
x
3
+
x
4
=60
⎨
x
+
x
⎪
1
−
x
2
+
2
x
35
=
10
⎪
x
1
+
x
2
−
x
3
+
x
6
=20
⎪
⎩
x
j
≥
0,
j
=
1,2,3,4,5,6
以
x
4
,
x
5
,
x
6
为基变量，可得第一张单纯形表为
x
1
x
2
x
3
x
4
x
5
x
6
RHS
z
21 -1 0 000
x
4
31 1 1 0060
x
5
1-1 2 0 1010
x
6
11 -1 0 0120
以
x
1
为进基变量，
x
5
为离基变量旋转得
x
1
x
4
x
5
x
6
RHS
x
2
x
3
z
0
3 -5 0 -20-20
x
4
04 -5 1 -3030
x
1
1-1 2 0 1010
x
6
02 -3 0 -1110
以
x
2
为进基变量，
x
6
为离基变量旋转得
运筹学作业参考解答
1 注意单纯形表的格式！
2 要用记号把转轴元标出来
3 要记住在单纯形表的左边，用
进基变量代替离基变量
第2页（共14页）