[运筹学教程]第二章习题答案

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

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

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

4X 1+2X2+X5=9 X 1,X 2,X 4,X 5≥0

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

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

4X 1+2X2+X5=9

X 1,X 2, X3′，X 3〞，X 4,X 5 ≥0

(2)解：引入松弛变量x 5≥0, 剩余变量X 6≥0，化不等式为等式为：

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

X 2-2X 4-X 6=9 X 1,X 2，X 4,X 5 ，X 6≥0

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

X 2-2X 4-X 6=9

X 1,X 2, X3′，X 3〞，X 4,X 5 , X6≥0

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

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

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

X 2-2X 4-X 6=9

X 1,X 2, X3′，X 3〞，X 4,X 5 , X6≥0

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

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

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

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

m ax z =2x 1+x 2-x 3⎫

⎪

s . t . x 1+x 2+2x 3≤6⎪

（1）⎬

x 1+4x 2-x 3≤4⎪

⎪x 1, x 2, x 3≥0⎭

解：将上式化成标准形式，如下：

m in p =-2x 1-x 2+x 3⎫⎪

s . t . x 1+x 2+2x 3+x 4=6⎪

⎬

x 1+4x 2-x 3+x 5=4⎪

⎪x 1, x 2, x 3, x 4, x 5≥0⎭

从上式中可以得出系数矩阵为A =[P 1

P 2P 3P 4

⎡1

P 5]=⎢

⎣1

14

2-1

10

0⎤⎥， 1⎦

取基础变量为x 4, x 5，令非基变量x 1, x 2, x 3=0，解方程组得基础可行解x (1)=(0,0, 0, 6, 4) T

x 1+x 2+2x 3+x 4=6x 1+4x 2-x 3+x 5=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 ，

x x

(5)

=(0,1,0, 5, 0)

T

，x (6) =(0,，x (9) =(

3

1420T

, , 0, 0) 99, -23, 0, 0, 0)

T

，x (7) =(6,0, 0, 0, -2) T ，

(10) x =(，

(8)

=(4,0, 0, 2, 0)

T

20143

, 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) 99

23

，x (8) =(4,0, 0, 2, 0) T ，x (10) =(

26323

143

, 0,

23

, 0, 0)

T

。

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

Z 1=0，Z 3=-3，Z 5=1，Z 6=-

，Z 8=8，Z 10=

143

。

, 0, 0)

T

其中Z 10=

263

最大，所以，最优解为x (10) =(

, 0,

，最优值为Z 10=

263

。

m in z =3x 1-4x 2-x 3⎫

⎪

s . t .3x 1+4x 2+x 3≤9

⎪⎪

（2）5x 1+2x 2+x 4=8⎬

⎪x 1-2x 2-x 3≤-1

⎪⎪x 1, x 2, x 3, x 4≥0⎭

解：将上式化成标准形式，如下： ⎫⎪

s . t .3x 1+4x 2+x 3+x 5=9

⎪⎪

5x 1+2x 2+x 4=8⎬ -x 1+2x 2+x 3-x 6=1⎪

⎪⎪x 1, x 2, x 3, x 4, x 5, x 6≥0⎭m in z =3x 1-4x 2-x 3

从上式中可以得出系数矩阵为

A =[P 1

P 2

P 3

P 4

P 5

⎡3

⎢P 6]=5

⎢⎢⎣-1

422

101

010

100

0⎤

⎥0， ⎥-1⎥⎦

3x 1+4x 2+x 3+x 5=9

取基础变量为x 4, x 5, x 6，令非基变量x 1, x 2, x 3=0，解方程组5x 1+2x 2+x 4=8

-x 1+2x 2+x 3-x 6=1

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

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

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

x x

(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 ，

2

1

x x

(9)

=(0,4, -7, 0, 0, 0)

T

，x (10) =(0,4, -7, 0, 0, 0) T ，x (11)=(, 0, 0, 0,

5

T

8215

, -

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 ，

x x

(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 ，

2

3

(18)

，x (19) =(, , 0, , 0, 0) T ，x (20) =(0,4, -7, 0, 0, 0) T 。

55

5

9

7

7

767

其中基础可行解为：

x x (3)

=(0,0, 9, 8, 0, 8) =(0,1T

，x (4) =(0,0,1, 8, 8, 0) T ，x (6) =(0,, 0, , 0, ) T ，

4

2

2

T

(7)

, 0, 7, 7, 0) ，x (14)=(8/5,0,21/5,0,0,8/5)T x

(15)

8138T =(, 0, , 0, , 0) ，

2555

x

(17) =(1,

3T

2

, 0, 0, 0,1)

，x (18) =(7,

13612, 0, 0,

76, 0)

T

。

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

Z =-

1，Z 1153=-9，Z 4=-1，Z 6=-9，Z 72

14=3/5 , Z 15=5

，Z 17=-3，Z 18=-

6

。

其中Z 3=Z 6=-9最小，所以，最优解为x (3)=(0,0, 9, 8, 0, 8) T x

(6)

=(0,

94

, 0,

72

, 0,

72

)

T

，，最优值为Z 3=Z 6=-9。

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

m ax z =4x 1+x 2（1）

⎧x 1+3x 2≤7

s . t . ⎪

4x 9 ⎨1+2x 2≤⎪⎩x 1, x 2

≥0解：解法（一）如图可知最优解为(x *

*

9

*1, x 2) =(4

, 0) ，最优值为z =9。

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

，

m in p =-4x 1-x 2

⎧x 1+3x 2+x 3=7

⎪

s . t . ⎨4x 1+2x 2+x 4=9⎪x , x , x , x ≥0⎩1234

不难发现，这个标准形式已经是一个正规定价方程组了，它给出了一个初始基础可行解为

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

T

' '

=-4

' ' '

可求下一个基础可行解。选x 1作进基变量，计算b i /a i 1(a i 1>0, i =1, 2) 后得，p =

94

，定a 21

'

' '

作旋转项，出基变量为x 4，作一次旋转运算后得第二表，此时c 1, c 2≥0，第二表对应的基

础可行解为(, 0,

4

9194

, 0) ，目标值p =-9。因此原LP 问题的最优解为(x 1, x 2) =(

T

' **

94

, 0) ，

最优值为z *=9。

m in z =2x 1+3x 2

⎧x 1+x 2≥350⎪

（2） ⎪x 1≥125

s . t . ⎨

⎪2x 1+x 2≤600⎪x , x ≥0⎩12

**

解法（一）由图可知该线性规划的最优解为(x 1, x 2) =(250,100)，它与可行域的顶点相对

应，最优目标值z =800。

*

解法（二）将线性规划问题化成标准形式 m in z =2x 1+3x 2

⎧x 1+x 2-x 3=350⎪

⎪x 1-x 4=125

s . t . ⎨

⎪2x 1+x 2+x 5=600⎪x , x , x , x , x ≥0⎩12345

该线性规划问题没有基础可行解，故先增设非负人工变量x 6, x 7, x 8，构造新的线性规划问题：

(LP 1) m in w =x 6+x 7+x 8

⎧x 1+x 2-x 3+x 6=350⎪

列出(LP 1) 的单纯形表如下： ⎪x 1-x 4+x 7=125

s . t . ⎨

⎪2x 1+x 2+x 5+x 8=600⎪x ≥0(i =1, 2 8) ⎩i

由基础表的最后一行判别数不难发现，基础变量x 6, x 7, x 8的判别数不是零，这是不允许的，必须把它们冲零后，才可用非基础变量的判别数的正负来判定现行基础可行解是否最优，把表1、2、3行分别乘以-1后加到第四行上，得第二表。根据第二表有多个负判别数，取最

' ' '

小者-4所在列的x 1作进基变量，比值b i /a i 1(a i 1>0) 最小者的p =125，用1作旋转项进行

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

（250，100，0，125，0，0，0，0），最优值w =0。

优解为

T

*

舍去第五表的人工变量部分，加上原目标函数系数于最后一行得原LP 问题的单纯形表，该

T

LP 问题的初始可行解为（250，100，0，125，0），目标值为z 0=0。

把基础变量列的判别系数冲零，得到第二表，所有判别式非负，此时的基础可行解即是最优

***

（250，100）解(x 1, x 2) =，最优目标值z =800。

m in z =6x 1+4x 2

⎧2x 1+x 2≥1

（3） ⎪

s . t . ⎨3x 1+4x 2≥1.5⎪x , x ≥0⎩12

*

解法（一）由图可知该线性规划的最优解为(x 1*, x 2，它与可行域的顶点对应，) =（，0）

1

2

最优目标值z *=3。

解法（二）构造新的线性规划(LP 1) ： (LP 1) m in w =x 5+x 6

⎧2x 1+x 2-x 3+x 5=1⎪

3 ⎪

s . t . ⎨3x 1+4x 2-x 4+x 6=

2⎪

⎪⎩x i ≥0(i =1, 2 6)

将初始表中基础变量x 5, x 6的判别数冲零，变为第二表，迭代后得到第四表，第四表即为

（(LP 1) 的最优解表，最优解为

1

，0，0，0，0，0），目标值w =0。

T

*

舍去第四表的人工变量部分，加上目标函数系数于最后一行得原LP 问题的单纯形表。将基础变量系数冲零得到第二表，判别数均为非负。此时的基础可行解是最

优解

(x 1, x 2) =（

*

*

1，目标值z =3。 ，0）

*

m ax z =4x 1+8x 2

⎧2x 1+2x 2≤10

（4） ⎪

s . t . ⎨-x 1+x 2≥8⎪x , x ≥0⎩12

解：作图法知该线性规划问题无可行域，因此无最优解。

m ax z =3x 1+9x 2

⎧x 1+3x 2≤22⎪

-x 1+x 2≤4⎪（5） ⎪

s . t . ⎨x 2≤6

⎪2x -5x ≤0

2

⎪1⎪⎩x 1, x 2≥0

解法（一）由图可知该线性规划的目标函数等值线与其中一条边界平行，因此该线性规划问题有无穷多个最优解，最优目标值z *=66。

解法（二）将原线性规划问题化为标准形式 m in p =-3x 1-9x 2⎧x 1+3x 2+x 3=22⎪

-x +x 2+x 4=4⎪1

⎪

s . t . ⎨x 2+x 5=6

⎪2x -5x +x =0

26

⎪1⎪⎩x i ≥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。 (x 1, x 2) =（4，6）

***

5、某工厂生产过程中需要长度为3.2m 、2.4m 和1.6m 的同种棒料毛坯分别为200根、100根和300根。现有的原料为9m 长棒材，问如何下料可使废料最少？ 解：由题意可得出如下的下料方案表：

现考虑九种下料方案的可行性。九种方案产生的废料有1m 和0.2m 两种区分，而本题从废料最少的角度出发，所以废料为0.2m 的方案严格优于废料为1m 的方案，理性的厂商会选择废料为0.2m 的方案，故可行的下料方案表如下：

设四种下料方案所用的原料棒材根数分别为X 1、X 2、X 3、X 4，根据题意及上表可以得出线性规划模型：

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

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

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

Max P=－0.2 X1－0.2X 2－0.2X 3－0.2X 4 s.t. －2 X1－X 2 + X5 =200

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

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

所以：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所示。根据上述条件，建立一个线性规划的数学模型，使得仓库租借费用最小（不求解）。

解：设在i 月租j 个月的仓库的面积为X ij ，由题意得：

租用时长

决 策

时

点

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

Min Z=20（X 11+ X21+ X31+ X41）+36（X 12+ X22+ X32）+50（X 13+ X23）+62 X14

s.t. X 11 +X12 +X13 +X14=1500

X 12 +X13 +X14 +X21 +X22 +X23=2000 X 13 +X14+X22 +X23+ X31 +X32=2200 X 14 +X23+ X32+ X41=1500 X ij ≥0（i ，j=1,2,3,4）

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

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

x 1, x 2, x 3, x 4, x 5(x i ≥0, i =1, 2 5) ，构造线性规划如下：

m ax z =50x 1+80x 2+30x 3+40x 4+15x 5

⎧500x 1+1000x 2+100x 3+300x 4+80x 5≤20000⎪

x +x 2≥8⎪1

⎪500x 1+1000x 2≤12000⎪

⎪x 3+x 4≥15⎪x ≤16 ⎪1s . t . ⎨

⎪x 2≤10⎪x ≤243⎪

⎪x 4≤4⎪x ≤25⎪5⎪⎩x i ≥0(i =1, 2 5)

将原线性规划分为两个子线性规划：

m ax p =50x 1+80x 2⎧x 1+x 2≥8⎪

⎪x 1+2x 2≤24s . t . ⎨

⎪0≤x 1≤16⎪0≤x ≤10⎩2

m ax w =30x 3+40x 4

和

⎧x 3+x 4≥15

⎪

s . t . ⎨0≤x 3≤24⎪0≤x ≤4

4⎩

*

) =（16，4），用图解法解这两个子线性规划，由图知最优解分别为：(x 1*, x 2

(x 3, x 4) =（24，4），500x 1+1000x 2+100x 3+300x 4+80*25

*****

（16,4，24，4，25）原规划的最优解为：(x 1, x 2, x 3, x 4, x 5) =，最优值为z *=2375。

*******

8.

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

设公司下月在航空商场经销x 1台，在铁路商场经销x 2台，在水上商场经销x 3台，可以得到：

m ax Z =50x 1+80x 2+70x 3⎧x 1+x 2+x 3≤1000⎪

12x 1+7x 2+8x 3≤8000⎪⎪⎪2x 1+3x 2+4x 3≤2500s . t . ⎨

⎪100≤x 1≤200⎪x ≥3002⎪⎪⎩x 3≥200

解得：

X =(100,500, 200) max Z =59000