《运筹学教程》第二章习题答案

1、（1）解：引入松弛变量x4≥0,x5≥0,化不等式为等式为： minz=2X1 +3X2+4X3

s.t. X1+3X2+2X3+X4=7

4X1+2X2+X5=9 X1,X2,X4,X5≥0

化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ： minz=2X1 +3X2+4X3′-4X3〞

s.t. X1+3X2+2 X3′-2 X3〞+X4=7

4X1+2X2+X5=9

X1,X2, X3′，X3〞，X4,X5 ≥0

(2)解：引入松弛变量x5≥0,剩余变量X6≥0，化不等式为等式为：

maxz=X1 -5X2+4X3- X4 s.t. X1+2X3+X5=7

X2-2X4-X6=9 X1,X2，X4,X5 ，X6≥0

化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ： maxz=X1 -5X2+4X3′-4X3〞- X4 s.t. X1+2 X3′-2 X3〞+X5=7

X2-2X4-X6=9

X1,X2, X3′，X3〞，X4,X5 , X6≥0

化极大的目标函数为极小的目标函数：

minz=-X1+5X2-4X3′+4X3〞+X4

s.t. X1+2 X3′-2 X3〞+X5=7

X2-2X4-X6=9

X1,X2, X3′，X3〞，X4,X5 , X6≥0

2、(1)是 不等式表示下图阴影区域，过阴影部分任意两点的直线仍在该区域内。

(2)不是 不等式表示下图阴影区域，过阴影部分且通过曲线上部的直线上的点不完全在该区域内。

(3)不是 不等式表示下图阴影区域，过阴影部分且通过圆内部的直线上的点不完全在该区域内。

3、在以下问题中，指出一组基础变量，求出所有基础可行解以及最优解。

maxz2x1x2x3s.t.x1x22x36（1）

x14x2x34x1,x2,x30解：将上式化成标准形式，如下：

minp2x1x2x3s.t.x1x22x3x46

x14x2x3x54x1,x2,x3,x4,x50从上式中可以得出系数矩阵为AP1P2P3P41P511421100， 1取基础变量为x4,x5，令非基变量x1,x2,x3=0，解方程组得基础可行解x(1)(0,0,0,6,4)T

x1x22x3x46x14x2x3x54

同理得基础解：x(2)(0,6,0,0,20)T，x(3)(0,0,3,0,7)T，x(4)(0,0,4,24,0)T，

xx(5)(0,1,0,5,0)T，x(6)(0,，x(9)(31420T,,0,0)99,23,0,0,0)T，x(7)(6,0,0,0,2)T，

(10)x(，

(8)(4,0,0,2,0)T20143,0,23,0,0)T。

其中基础可行解为：x(1)(0,0,0,6,4)T，x(3)(0,0,3,0,7)T，x(5)(0,1,0,5,0)T，

x(6)(0,1420T,,0,0)9923，x(8)(4,0,0,2,0)T，x(10)(26323143,0,23,0,0)T。

将上解逐一带入原目标函数，得

Z1=0，Z3=-3，Z5=1，Z6=，Z8=8，Z10=

143。

,0,0)T其中Z10=

263最大，所以，最优解为x(10)(,0,，最优值为Z10=

263。

minz3x14x2x3s.t.3x14x2x39（2）5x12x2x48

x12x2x31x1,x2,x3,x40解：将上式化成标准形式，如下： s.t.3x14x2x3x595x12x2x48 x12x2x3x61x1,x2,x3,x4,x5,x60minz3x14x2x3从上式中可以得出系数矩阵为

AP1P2P3P4P53P65142210101010000， 13x14x2x3x59取基础变量为x4,x5,x6，令非基变量x1,x2,x3=0，解方程组5x12x2x48x12x2x3x61

得基础可行解x(1)(0,0,0,8,9,1)T。

当基变量为x3,x5,x6时，子矩阵为奇异矩阵，x(2)不是该题的基，其他的都为非奇异矩阵，共有19个基。

类似上述，得其他基础解：

xx(3)(0,0,9,8,0,8)(0,94,0,72,0,T，x(4)(0,0,1,8,8,0)T，x(5)(0,4,0,0,7,7)T，

)T(6)72，x(7)(0,,0,7,7,0)T，x(8)(0,4,7,0,0,0)T，

21xx(9)(0,4,7,0,0,0)T，x(10)(0,4,7,0,0,0)T，x(11)(,0,0,0,5T8215,135)T，

(12)(3,0,0,7,0,4)，x(13)(1,0,0,13,12,0)T，x(14)=(8/5,0,21/5,0,0,8/5)T，

xx(15)8138T(,0,,0,,0)555(7137T,,0,0,,0)6126，x(16)(2,0,3,12,0,0)T，x(17)(1,,0,0,0,1)T，

23(18)，x(19)(,,0,,0,0)T，x(20)(0,4,7,0,0,0)T。

555977767其中基础可行解为：

xx(3)(0,0,9,8,0,8)(0,1T，x(4)(0,0,1,8,8,0)T，x(6)(0,,0,,0,)T，

422T(7),0,7,7,0)，x(14)=(8/5,0,21/5,0,0,8/5)Tx(15)8138T(,0,,0,,0)，

2555x(17)(1,3T2,0,0,0,1)，x(18)(7,13612,0,0,76,0)T。

将上解逐一带入原目标函数，得

Z=1，Z1153=-9，Z4=-1，Z6=-9，Z7214=3/5 , Z155，Z17=-3，Z186。

其中Z3=Z6=9最小，所以，最优解为x(3)(0,0,9,8,0,8)Tx(6)(0,94,0,72,0,72)T，，最优值为Z3=Z6=9。

4.用图解法和单纯形法求如下线性规划问题的最优解

maxz4x1x2（1）

x13x27s.t.4x9 12x2x1,x20解：解法（一）如图可知最优解为(x**9*1,x2)(4,0)，最优值为z9。

4x12x29 x13x27

解法（二）将原线性规划问题化成标准形式：

，

minp4x1x2

x13x2x37 s.t.4x12x2x49x,x,x,x01234不难发现，这个标准形式已经是一个正规定价方程组了，它给出了一个初始基础可行解为

x(0,0,7,9),目标值为p00，列出单纯形初始表如下：

0T 基础变量 x1 x3 x4 -p x3 x1 -p 1 4 -4 0 1 0 x2 3 2 -1 5/2 1/2 1 x3 1 0 0 1 0 0 x4 0 1 0 -1/4 1/4 1 常数项 7 9 0 19/4 9/4 9 ''40,c210,且负判别数对应列元素均有元素大于零者，故从初始表可以看出，c1'''可求下一个基础可行解。选x1作进基变量，计算bi/ai1(ai10,i1,2)后得，p94，定a21'''作旋转项，出基变量为x4，作一次旋转运算后得第二表，此时c1,c20，第二表对应的基

础可行解为(,0,49194,0)，目标值p9。因此原LP问题的最优解为(x1,x2)(T'**94,0)，

最优值为z*9。

minz2x13x2x1x2350（2） x1125s.t.2x1x2600x,x012**解法（一）由图可知该线性规划的最优解为(x1,x2)(250,100)，它与可行域的顶点相对

应，最优目标值z800。

*

x1x2350 2x1x2600 x1125 解法（二）将线性规划问题化成标准形式 minz2x13x2x1x2x3350 x1x4125s.t.2x1x2x5600x,x,x,x,x012345该线性规划问题没有基础可行解，故先增设非负人工变量x6,x7,x8，构造新的线性规划问题：

(LP1)minwx6x7x8x1x2x3x6350列出(LP1)的单纯形表如下： x1x4x7125s.t.2x1x2x5x8600x0(i1,28)i由基础表的最后一行判别数不难发现，基础变量x6,x7,x8的判别数不是零，这是不允许的，必须把它们冲零后，才可用非基础变量的判别数的正负来判定现行基础可行解是否最优，把表1、2、3行分别乘以-1后加到第四行上，得第二表。根据第二表有多个负判别数，取最

'''小者-4所在列的x1作进基变量，比值bi/ai1(ai10)最小者的p125，用1作旋转项进行

旋转运算。如此迭代下去，直至所有判别式非负，得第五表。即为(LP1)的最优解表，其最

（250，100，0，125，0，0，0，0），最优值w0。 优解为

T*基础变量 原有变量 人工变量 常数项 x1 x6 x7 x8 -w x6 x7 x8 -w x6 x1 x8 -w x6 x1 x4 -w x2 x1 x4 1 1 2 0 1 1 2 -4 0 1 0 0 0 1 0 0 0 1 0 x2 1 0 1 0 1 0 1 -2 1 0 1 -2 1/2 1/2 1/2 -1/2 1 0 0 x3 -1 0 0 0 -1 0 0 1 -1 0 0 1 -1 0 0 1 -2 1 1 x4 0 -1 0 0 0 -1 0 1 1 -1 2 -3 0 0 1 0 0 0 1 x5 0 0 1 0 0 0 1 -1 0 0 1 -1 -1/2 1/2 1/2 1/2 -1 1 1 x6 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 2 -1 -1 x7 0 1 0 1 0 1 0 0 -1 1 -2 4 0 0 -1 1 0 0 -1 x8 0 0 1 1 0 0 1 0 0 0 1 0 -1/2 1/2 1/2 3/2 -1 1 1 350 125 600 0 350 125 600 -1075 225 125 350 -575 50 300 175 -50 100 250 125 -w 0 0 0 0 0 1 1 1 0 舍去第五表的人工变量部分，加上原目标函数系数于最后一行得原LP问题的单纯形表，该

TLP问题的初始可行解为（250，100，0，125，0），目标值为z00。

基础变量 x2 x1 x4 -z x2 x1 x4 -z x1 0 1 0 2 0 1 0 0 x2 1 0 0 3 1 0 0 0 x3 -2 1 1 0 -2 1 1 4 x4 0 0 1 0 0 0 1 0 x5 -1 1 1 0 -1 1 1 1 常数项 100 250 125 0 100 250 125 -800 把基础变量列的判别系数冲零，得到第二表，所有判别式非负，此时的基础可行解即是最优

***（250，100）解(x1,x2)，最优目标值z800。

minz6x14x22x1x21（3） s.t.3x14x21.5x,x012*解法（一）由图可知该线性规划的最优解为(x1*,x2，它与可行域的顶点对应，)（，0）12最优目标值z*3。

2x1x21 3x14x21.5

解法（二）构造新的线性规划(LP1)： (LP1)minwx5x62x1x2x3x513 s.t.3x14x2x4x62xi0(i1,26)将初始表中基础变量x5,x6的判别数冲零，变为第二表，迭代后得到第四表，第四表即为

（(LP1)的最优解表，最优解为

12，0，0，0，0，0），目标值w0。

T*基础变量 x5 x6 -w x5 原有变量 x1 2 3 0 2 x2 1 4 0 1 x3 -1 0 0 -1 x4 0 -1 0 0 人工变量 x5 1 0 1 1 x6 0 1 1 0 常数项 1 3/2 0 1 x6 -w x1 x6 -w x1 x2 -w 3 -5 1 0 0 1 0 0 4 -5 1/2 5/2 -5/2 0 1 0 0 1 -1/2 3/2 -3/2 -4/5 3/5 0 -1 1 0 -1 1 1/5 -2/5 0 0 0 1/2 -3/2 5/2 4/5 -3/5 1 1 0 0 1 0 -1/5 2/5 1 3/2 -5/2 1/2 0 0 1/2 0 0 舍去第四表的人工变量部分，加上目标函数系数于最后一行得原LP问题的单纯形表。将基础变量系数冲零得到第二表，判别数均为非负。此时的基础可行解是最优解

(x1,x2)（**12，目标值z3。 ，0）x1 1 0 6 1 0 0 x2 0 1 4 1 1 0 x3 -4/5 3/5 0 -4/5 3/5 12/5 x4 1/5 -2/5 0 1/5 -2/5 2/5 常数项 1/2 0 0 1/2 0 -3 *基础变量 x1 x2 -z x2 x1 -z

maxz4x18x22x12x210（4） s.t.x1x28x,x012解：作图法知该线性规划问题无可行域，因此无最优解。

x1x28 2x12x210

maxz3x19x2x13x222x1x24（5） s.t.x262x5x021x1,x20解法（一）由图可知该线性规划的目标函数等值线与其中一条边界平行，因此该线性规划问题有无穷多个最优解，最优目标值z*66。

x1x24 x13x222 x26

解法（二）将原线性规划问题化为标准形式 minp3x19x2x13x2x322xx2x441 s.t.x2x562x5xx0261xi0(i1,26)T基础可行解为（0，0，22，4，6，0），目标值为0，经过迭代，得到一组最优解

（4，6，0，2，0，22），目标值为p66。原LP问题的一组最优解为

T*，最优目标值z66。 (x1,x2)（4，6）***5、某工厂生产过程中需要长度为3.2m、2.4m和1.6m的同种棒料毛坯分别为200根、100根和300根。现有的原料为9m长棒材，问如何下料可使废料最少？ 解：由题意可得出如下的下料方案表：

单位：根 方案1 方案2 方案3 方案4 方案5 方案6 方案7 方案8 方案9 3.2m 0 0 0 0 1 1 1 2 2 2.4m 0 3 1 2 0 1 2 0 1 1.6m 5 1 4 2 3 2 0 1 0 废料 1m 0.2m 0.2m 1m 1m 0.2m 1m 1m 0.2m 现考虑九种下料方案的可行性。九种方案产生的废料有1m和0.2m两种区分，而本题从废料最少的角度出发，所以废料为0.2m的方案严格优于废料为1m的方案，理性的厂商会选择废料为0.2m的方案，故可行的下料方案表如下：

单位：根 方案1 方案2 方案3 方案4 3.2m 2 1 0 0 2.4m 1 1 3 1 1.6m 0 2 1 4 废料 0.2m 0.2m 0.2m 0.2m 设四种下料方案所用的原料棒材根数分别为X1、X2、X3、X4，根据题意及上表可以得出线性规划模型：

Min Z=0.2 X1+0.2X2+0.2X3+0.2X4 s.t. 2 X1+ X2 ≥200

X1+ X2+3 X3+ X4 ≥100 2 X2+ X3+4 X4 ≥300 Xi≥0（i=1,2,3,4）

运用对偶单纯形法求解上述数学模型： 先将此问题化为下列形式：

Max P=－0.2 X1－0.2X2－0.2X3－0.2X4 s.t. －2 X1－X2 + X5 =200

－X1－X2－3 X3－X4 + X6 =100 －2 X2－X3－4 X4+ X7=300 Xi≥0（i=1,2,3,…,7）

建立此问题的初始单纯形表并进行运算如下：

Cj -0.2 -0.2 -0.2 -0.2 0 X5 1 0 0 0 0 X6 0 1 0 0 0 X7 0 0 1 0 CB 0 0 0 XB X5 X6 X7 b X1 X2 -1 -1 -2 X3 0 -3 -1 X4 0 -1 -4 -200 -2 -100 -1 -300 0 

Cj j-0.2 -0.2 -0.2 -0.2 0.1 0.2 0.05  -0.2 -0.2 -0.2 -0.2 0 X5 1 0 0 0 0 X6 0 1 0 0 0 X7 0 -1/4 -1/4 -0.05 CB 0 0 -0.2 XB X5 X6 X4 b X1 X2 -1 X3 0 X4 0 0 1 0 -200 -2 -25 75 -1 -1/2 -11/4 0 1/2 1/4 

j -0.2 -0.1 -0.15 0.1 0.1  Cj -0.2 -0.2 -0.2 -0.2 0 X5 -1/2 -1/2 0 X6 0 1 0 X7 0 -1/4 CB -0.2 0 XB X1 X6 b 100 75 X1 1 0 X2 1/2 0 X3 0 -11/4 X4 0 0 -0.2 X4 75 0 0 1/2 0 1/4 -0.15 1 0 0 -0.1 0 0 -1/4 -0.05 j

所以：X* = (100，0，0，75)T Z* = 100×（-0.2）+75×（-0.2）=35

即：按照方案1下料100根，按照方案4下料75根，可使废料最少，为35m 。

6、某贸易公司需要4个月的销售旺季租用仓库，各个月所需仓库面积如表2-16所示，仓库租借合同月初可以办理，租借费用随租借时间和面积的不同而不同，同样的面积，连续租用时间越长，费用折扣越大，具体价格如表2-17所示。根据上述条件，建立一个线性规划的数学模型，使得仓库租借费用最小（不求解）。

表2-16 月份 1 2 3 4 仓库面积/ m2 1500 2000 2200 1500 表2-17 合同租借期限 1个月 2个月 3个月 4个月 仓库面积/ m2 20 36 50 62 解：设在i月租j个月的仓库的面积为Xij，由题意得：

租用时长

1个月 2个月 3个月 4个月 决 1月 X11 X12 X13 X14 策

2月 X21 X22 X23 时

3月 X31 X32 点

4月 X41

根据上表可以建立如下线性规划模型：

Min Z=20（X11+ X21+ X31+ X41）+36（X12+ X22+ X32）+50（X13+ X23）+62 X14

s.t. X11 +X12 +X13 +X14=1500

X12 +X13 +X14 +X21 +X22 +X23=2000 X13 +X14+X22 +X23+ X31 +X32=2200 X14 +X23+ X32+ X41=1500 Xij≥0（i，j=1,2,3,4）

答案为：第1月租1500平方米，租期4个月； 第2月租500平方米，租期2个月；第3月租200平方米，租期1个月；租借费用最小，11500元。

7.解：设应采用的电视台（a）、电视台（b）、每日晨报、星期日报、广播电台的次数分别为

x1,x2,x3,x4,x5(xi0,i1,25)，构造线性规划如下：

maxz50x180x230x340x415x5500x11000x2100x3300x480x520000xx281500x11000x212000x3x415x16 1s.t.x210x243x44x255xi0(i1,25)将原线性规划分为两个子线性规划：

maxp50x180x2x1x28x12x224s.t.0x1160x102maxw30x340x4和

x3x415s.t.0x3240x44

x1x28 x12x224

x3x415 x44 x324

*)（16，4），用图解法解这两个子线性规划，由图知最优解分别为：(x1*,x2(x3,x4)（24，4），500x11000x2100x3300x480*2520000，因此取x525。

*****（16,4，24，4，25）原规划的最优解为：(x1,x2,x3,x4,x5)，最优值为z*2375。

*******8.

把推销人员最高可用公式改成2500h.

设公司下月在航空商场经销x1台，在铁路商场经销x2台，在水上商场经销x3台，可以得到：

maxZ50x180x270x3x1x2x3100012x17x28x380002x13x24x32500s.t.100x1200x3002x3200

解得：

X(100,500,200)maxZ59000