第一章线性规划1、
由图可得：最优解为
2、用图解法求解线性规划：
Min z=2R1+R2
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥
≤
≤
≥
+
≤
+
-
10
5
8
24
4
2
1
2
1
2
1
x
x
x
x
x
x
解：
由图可得：最优解R=1.6,R=6.4
3用图解法求解线性规划：
MaR z=5R1+6R2
⎪
⎩
⎪
⎨
⎧
≥
≤
+
-
≥
-
,
2
3
2
2
2
2
1
2
1
2
1
x
x
x
x
x
x
解：
由图可得：最优解MaR z=5R1+6R2, MaR z= +
4用图解法求解线性规划：
MaRz = 2R1 +R2
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥
≤
+
≤
+
≤
,
5
24
2
2
6
15
5
2
1
2
1
2
1
1
x
x
x
x
x
x
x
由图可得：最大值
⎪⎩
⎪
⎨
⎧
=
=
+
3
5
1
2
1
x
x
x
，所以
⎪⎩
⎪
⎨
⎧
=
=
2
3
2
1
x
x
maR Z = 8.
1
2
12
1
2
5.max23
28
416
412
0,1,2
maxZ.
j
Z x x
x x
x
x
x j
=+
⎧+≤
⎪
≤
⎪
⎨
≤
⎪
⎪≥=
⎩
如图所示，在（4，2）这一点达到最大值为2
6将线性规划模型化成标准形式：
Min z=R1-2R2+3R3
⎪⎪⎩⎪⎪
⎨⎧≥≥-=++-≥+-≤++无约束
321
321321321,0,05232
7x x x x x x x x x x x x
解：令Z ’=-Z,引进松弛变量R 4≥0，引入剩余变量R 5≥0，并令R 3=R 3’-R 3’’,其中R 3’≥0,R 3’’≥0
MaR z ’=-R 1+2R 2-3R 3’+3R 3’’
⎪⎪⎩⎪⎪
⎨
⎧≥≥≥≥≥≥-=++-=--+-=+-++0
,0,0'',0',0,05
232
'''7'''543321
3215332143321x x x x x x x x x x x x x x x x x x x
7将线性规划模型化为标准形式
Min Z =R 1+2R 2+3R 3
⎪⎪⎩⎪⎪
⎨⎧≥≤-=--≥++-≤++无约束
，321
321321321,0063244
2392-x x x x x x x x x x x x
解：令Z’ = -z ，引进松弛变量R 4≥0,引进剩余变量R 5≥0,得到一下等价的标准形式。
⎪⎪⎩⎪⎪
⎨⎧≥≤-=--=-++-=+++,
0,,,063244
2392-5421
32153214321x x x x x x x x x x x x x x x
R 2’=-R 2 R 3=R 3’-R 3’’
Z’ = -min Z = -R 1-2R 2-3R 3
()()⎪⎩⎪⎨⎧-=--+=--+--=+-+-632442392-'
'3'321
5'
'33'214'
'3'3'21x x x x x x x x x x x x x x
123123412358.maxZ=3x 3434540
643660,1,2,3,4,5
j x x x x x x x x x x x j ++⎧+++=⎪
+++=⎨⎪
≥=
9用单纯形法求解线性规划问题：
MaR Z =70R 1+120R 2
⎪
⎩⎪
⎨⎧≤+≤+≤+300
10320064360
49212121x x x x x x
解： MaR Z =70R 1+120R 2
⎪
⎩
⎪
⎨
⎧
=
+
+
=
+
+
=
+
+
300
10
3
200
6
4
360
4
9
5
2
1
4
2
1
3
2
1
x
x
x
x
x
x
x
x
x
单纯形表如下
MaR Z =3908.
12
12
12
1
12
345345
123
124
15
10.max43
2+23000
5 2.54000
500
,0
,,(,,0)
223000
5 2.5+4000
500
0,1,2,3,4,5
j
Z x x
x x
x x
x
x x
x x x x x x
x x x
x x x
x x
x j
=+
⎧≤
⎪
+≤
⎪
⎨
≤
⎪
⎪≥
⎩
≥
⎧++=
⎪
+=
⎪
⎨
+=
⎪
⎪≥=
⎩
解：引入松弛变量
Cj 4 3 0 0 0
θi
CB RB b R1 R2 R3 R4 R5
0 R3 3000 2 2 1 0 0 1500
0 R4 4000 5 2.5 0 1 0 800
0 R5 500 [1] 0 0 0 1 500
Cj-Zj 4 3 0 0 0 111
222
121
min5
min
4(020501)4
3(02+0 2.5+00)3
,)max(4,3)4,
30004000500
,,500,
251
c z
c z
x
x
σ
σσ
θ
=-=-⨯+⨯+⨯=
=-=-⨯⨯⨯=
==∴
⎛⎫
==∴
⎪
⎝⎭
检验数>0,max(对应的为换入变量.
为换出变量.
123451110500,0,2000,1500,0,4(020501)4500302000.
x x x x c z σ≤∴=====∴=-=-⨯+⨯+⨯=⨯+⨯=非基变量检验数，得到最优解：x 目标函数的maxZ=4
11.解：（1）引入松弛变量R4，R5，R6，将原问题标准化，得
maR Z=10R1+6R2+4R3
R1+R2+R3+R4=100
10 R1+4R2+5R3+R5=600
2 R1+2R2+6R3+R6=300
R1,R2,R3,R4,R5,R6≥0
得到初始单纯形表：
111
根据ρmaR =maR{10,6,4}=10,对应的R1为换入变量，计算θ得到，
θmin =min{100/1,600/10,300/2}=60,R5为换出变量，进行旋转运算。
j
Z R =10×100/3+6×200/3+4×0 =2200/3。
12解：（1）引入松弛变量R3，R4，R5将原问题标准化，得maR Z=2R1+R2
5R2+R3=15
6R1+2R2+ R4=24
R1+2R2+ R5=5
R1,R2,R3,R4,R5≥0
111
根据ρmaR =maR{2,1,0}=2,对应的R1为换入变量，计算θ得到，
优质参考文档
优质参考文档
θmin =min{-,24/6,5/1}=4, R 4为换出变量，进行旋转运算。
j Z R
=2×7/2+3/2 =17/2。
13解：引入松弛变量R 3、R 4，约束条件化成等式，将原问题进行标准化，得： MaR Z=2.5R 1+R 2
3R 1+5R 2+R 3 =15 5R 1+2R 2 +R 4=10 R 1,R 2,R 3,R 4≥0
（1） 确定初始可行基为单位矩阵I=[P 3，P 4]，基变量为R 3，R 4，R 5，非基变量为R 1，R 2，则有：
MaR Z=2.5R 1+3R 2 R 3=15-3R 1-5R 2 s.t R 4=10-5R 1-2R 2
Ri ≥0，j=1，2，3，4
将题求解过程列成单纯形表格形式，表1
由上述可得，将1替换为4
表2，单纯形迭代过程
优质参考文档
由表2可得，将2x 替换为3x
表3 最终单纯形表 非基变量检验数3σ=0,4σ=
-2，得到该线性规划另一最优解，*x =（19，19，0,0）,*
z =5，
该线性规划具有无穷多个解
14.用单纯形法求解线性规划问题：
⎪⎪⎩⎪⎪⎨
⎧≥≥≤+≤+≤+=0
05 2426155
..2max 212121221x x x x x x x t s x x z ， 解：
（1）将原问题转化为标准形式，得
⎪⎪⎩⎪⎪⎨
⎧≥≥≥≥≥=++=++=+++++=0
,0 ,0 ,0 ,05
24 2615 5
..0002max 54321521421325
4321x x x x x x x x x x x x x t s x x x x x z （2）建立单纯性，并进行迭代运算。
