第一章线性规划
习题1.1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？
表1—1
产品
单耗
资源
甲乙资源限制
A B C 1
2
1
1
1
300kg
400kg
250kg
单位产品利润（元/件）50100
解：设x1、x2分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。

依题意，问题可转换成求变量x1、x2的值，使总利润最大，即
ma x z=50x1+100x2
且称z=50x1+100x2为目标函数。

同时满足甲、乙两种产品所消耗的A、B、C三种资源的数量不能超过它们的限量，即可分别表示为
x1 + x2≤300
2x1 + x2≤400
x2≤250
且称上述三式为约束条件。

此外，一般实际问题都要满足非负条件，即
x1≥0、x2≥0。

这样有
ma x z=50x1+100x2
x1 + x2≤300
2x1 + x2≤400
x2≤250
x1、x2≥0
习题1.2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m 3，在两个工厂之间有一条流量为200万m 3的支流。

两化工厂每天排放某种有害物质的工业污水分别为2万m 3和1.4万m 3。

从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。

环保要求河流中工业污水含量不能大于0.2%。

两化工厂处理工业污水的成本分别为1000元/万m 3和800元/万m 3。

现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。

解：设x 1、x 2分别代表工厂1和工厂2处理污水的数量(万m 3)。

则问题的目标可描
述为
min z =1000x 1+800x 2约束条件有
第一段河流（工厂1——工厂2之间）环保要求 (2－x 1)/500 ≤0.2%第二段河流（工厂2以下河段）环保要求[0.8(2－x 1) +(1.4－x 2)]/700≤0.2%此外有
x 1≤2； x 2≤1.4化简得到
min z =1000x 1+800x 2
x 1 ≥10.8x 1 + x 2 ≥1.6x 1 ≤2x 2≤1.4x 1、x 2≥0
习题1.3
ma x z =50x 1+100x 2
x 1 + x 2≤3002x 1 + x 2≤400x 2≤250
图1—1
x 2
x 1、x 2≥0
用图解法求解。

解：如图1—2中的B 点，即问题的最优解为x 1*=50；x 2*=250，相应的最优值为z *=27500，且该问题有唯一最优解。

习题1.4
ma x z =2x 1+2x 2x 1－x 2 ≥ 1－x 1 + 2x 2≤ 0x 1、x 2≥ 0
用图解法求解。

解：图1—3中阴影部分就是该问题的可行域，显然该问题的可行域是无界的。

两条虚线为目标函数等值线，它们对应的目标值分别为2和4，可以看出，目标函
数等值线向右移动，问题的目标
值会增大。

但由于可行域无界，目标函数可以增大到无穷。

称这种情况为无界解或无最优解。

习题1.5 化下列线性规划为标准形 ma x z =2x 1+2x 2－4x 3x 1 + 3x 2－3x 3 ≥30x 1 + 2x 2－4x 3≤80x 1、x 2≥0，x 3无限制
解：按照上述方法处理，得该线性规划问题的标准形为 ma x z =2x 1+2x 2－4x 31+4x 32
x 1 + 3x 2－3x 31 + 3x 32－x 4 = 30x 1 + 2x 2－4x 31 + 4x 32 + x 5 = 80x 1、x 2，x 31，x 32，x 4，x 5 ≥0
例1.6 用单纯形法求解ma x z =50x 1+100x 2
x 1 + x 2≤3002x 1 + x 2≤400x 2≤250x 1、x 2≥0
解：首先将问题化为标准形式，然后将整个计算过程列在一个表中（表1—9）。

表1—9
C j50100000
C B X B x
1↓x2↓x3x4x5
b
0x311100300 0x421010400← 0x50[1]001250－z501000000← 0x31010-150 0x42001-1150 100x201001250
－z500
00-100
－2500
50x11010-150 0x400-21150 100x201001250
－z00
-500-50
－2750
由于σj≤0（j=1，…，5），故X*=（50，250，0，50，0）T，Z*=27500
例1.7 用单纯形法求解
ma x z=2x1+x2
－x1 + x2≤5
2x1－5x2≤10
x1、x2≥0
解：用单纯形表实现如表1—10
表1—10
C j2100
C B X B x
1↓x2x3x4
bθ
0x3-11105—← 0x4[2]-5011010/4(min)－z21000
0x30-3/211/210
2x11-5/201/25
－z060-1－10
σ2=6 > 0，且p2≤0，故该线性规划有无界解（无最优解）。

例1.8 用单纯形法（大M法）求解下列线性规划
ma x z=3x1－2x2－x3
x1－2x2 + x3≤ 11
－4x1 + x2 + 2x3 ≥ 3
－2x1+ x3= 1
x1、x2、x3≥0
解：化为标准形式
ma x z=3x1－2x2－x3
x1－2x2 + x3 + x4= 11
－4x1+ x2 +2x3 －x5 = 3
－2x1+x3= 1
x1、x2、x3、x4、x5≥0
显然上述标准形式的线性规划问题没有现成的初始可行基。

观察可知，需要在第二、三个约束方程中分别加入人工变量x6、x7，构造如下线性规划问题
ma x z=3x1－2x2－x3－M x6－M x7
x1－2x2 + x3 + x4= 11
－4x1+ x2 +2x3 －x5 + x6= 3
－2x1+x3+x7 = 1
x1、x2、x3、x4、x5、x6、x7≥0
用单纯形进行计算，计算过程见表1—11。

表1—11
C j3-1-100-M-M
C B X B x
1↓x2↓x3x4x5x6x7
b
0x41-21100011 -M x6-4120-1103 -M x7-20[1]00011
－z3-6M -1+M-
1+3M
0-M004M
0x43-20100-110 -M x60[1]00-11-21 -1x3-20100011
－z1-1+M0
0-M0
-
3M+1
M+1
0x4[3]001-22-512 -1x20100-11-21 -1x3-20100011－z1000-1-M+1-M-12 3x11001/3-2/32/3-5/34
-1x20100-1121 -1x30012/3-4/34/3-7/39
－z000
-1/3-1/3
-
M+1/
3
-
M+2/
3
－2
由于σj≤0（j=1，…，7），且基变量中不含人工变量，故X*=（4，1，9）T，z*=2
例1.9 用单纯形法（大M法）求解下列线性规划
ma x z=3x1+2x2
2x1+ x2 ≤ 2
3x1 +4 x2 ≥12
x1、x2≥0
解:化为标准形式后引入人工变量x5得到
ma x z=3x1+2x2－M x5
2x1+ x2 +x3= 2
3x1 +4 x2 －x4+x5 =12
x1、…、x5≥0
用单纯形法计算，过程列于表1—12中。

从表中可以看出，虽然检验数均小于或等于零，但基变量中含有非零的人工变量x5=4，所以原问题无可行解。

表1—12
C j3200-M
C B x B x1x2x3x4x5
b
0 -M x3
x5
2
3
[1]
4
1
-1
1
2
12 -z3+3M2+4M0-M012M
2 -M x2
x5
2
-5
1
1
-4
-1
1
2
4
-z-1-5M0-2-4M-M0-4+4M。