《管理运筹学》(第二版)课后习题参考答案解析

《管理运筹学》(第二版)课后习题参考答案

第1章线性规划(复习思考题)

1.什么是线性规划？线性规划的三要素是什么？

答：线性规划(LinearProgramming,LP)是运筹学中最成熟的一个分支，并且是

应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化

工具，能够解决有限资源的最佳分配问题。

建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决

策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条

件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的

线性函数表达式，有的目标要实现极大值，有的则要求极小值。

2.求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？

答：(1)唯一最优解：只有一个最优点：

(2)多重最优解：无穷多个最优解；

(3)无界解：可行域无界，目标值无限增大；

(4)没有可行解：线性规划问题的可行域是空集。

当无界解和没有可行解时，可能是建模时有错。

3.什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？

答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项&NO,

决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业

来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“2”型约

束的左边取值大于右边规划值，出现剩余量。

4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。

答：可行解：满足约豪条件4X=。，XNO的解，称为可行解。

基可行解：满足非负性约束的基解，称为基可行解。

可行基：对应于基可行解的基，称为可行基。

最优解：使目标函数最优的可行解，称为最优解。

最优基：最优解对应的基矩阵，称为最优基。

它们的相互关系如右图所示：

基可行解

5.用表格单纯形法求解如下线性规划。

maxZ=4X|+工2+2x3

8X]+3X2+x3<2

S.t.<6%]+x2+x3<8

再，-2，％3NO

解：标准化maxZ=4xt+x2+2x3

82+3X2++X4=2

卜匕

s.t.«6X]+x2+x3=8

用，12，当，匕，占>0

列出单纯形表

Cj41200

cBXBb再五2工3%%

0匕2[8]31102/8

08611018/6

J41200

41/413/8[1/8]1/80(1/4)/(1/8)

0%13/26—5/41/4-3/41(13/2)/(1/4)

0-1/23/2-1/20

2X3283110

0XS6-2-20-11

%-12—50-20

故最优解为X*=（00,2,0,6）"即k=0,々=。,超=2,此时最优值为Z（X*）=4.

6.表1—15中给出了求极大化问题的单纯形表，问表中q,外，G，C2，d为何值及变

量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）

下一步迭代将以再代替基变量与；(4)该线性规划问题具有无界解；(5)该线性规划问

题无可行解。

表1—15某极大化问题的单纯形表

cic*2o00

A

0r

CBXRb再X2XyX4X5

0X3d4100

0“42-1-5010

0当3ci2-3001

%c2000

解：(1)d>(),<?!<(),c2<0;

(2)d<0,c2<0(q,C2中至少有一个为零)；

(3)c.>0,t7,>0,—>—;

■4出

(4)c2>(),«,<0;

(5)为为人工变量，且c［为也含的的大于零的数，—;或者为人工变量,

4%

且c2为包含"的大于零的数，r/,>0,6/>0.

7.用大加法求解如下线性规划。

maxZ=5』+3x2+6JT3

X1+2X2+x3<18

2Xj+厂+3X<16

s.t.-3

X1+x2+A3=10

和々，工3N()

解：加入人工变量，进行人造基后的数学模型如下：

maxZ=53+3x2+6x3+0x4+0x5-

8.A,B,C三个城市早年需分别供应电力320,250和350单位，由I,II两个电

站提供，它们的最大可供电量分别为400单位和450单位，单位费用如表1—16所示。

由于需要量大于可供量，决定城市A的供应量可减少0〜30单位，城市B的供应量不变,

城市C的供应量不能少于270单位。试建立线性规划模型，求将可供电量用完的最低总

费用分配方案。

表1—16单位电力输电费(单位：元)

ABC

1151822

//212516

解：设.%为“第/电站向第/城市分配的电量”"=1,2；户1,2,3),建立模型如下:

maxZ=15XN+18xl2+22x13+21x2l+25x22+16x23

人11十百2十人13=400

x21+x22+x23=450

xl}+x2l>290

+x21<32()

x]2+x22=250

x13+x23>270

尤]3+423<350

/NO,i=1,2;/=123

9.某公司在3年的计划期内，有4个建设项目可以投资：项目I从第一且到第三

年年初都可以投资。预计每年年初投资，年末可收回本利120%,每年又可以重新将所获

本利纳入投资计划；项目II需要在第一年初投资，经过两年可收回本利150席,又可以

重新将所获本利纳入投资计划，但用于该项目的最大投资不得超过20万元；项目III

需要在第二年年初投资，经过两年可收回本利160乐但用于该项目的最大投资不得超过

15万元；项目IV需要在第三年年初投资，年末可收回本利140%,但用于该项目的最大

投资不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问

怎样的投资方案，才能使该公司在这个计划期获得最大利泗？

解：设王⑴表示第一次投资项目/,设兀⑵表示第二次投资项目/,设王⑶表示第三

次投资项目/,(7=1,2,3,4),则建立的线性规划模型为

maxZ=1.2X；3>+1.6^0+1.4工;

西⑴+省<3（）

不⑵+引）41.2x9+30-王⑴一引）

短）+引）=1.2幸+1.5对）+1.2M⑴+30-染-引）-率_档）

<20

<15

<10

引）力2）,姬皿=1,2,3,4

通过LINGO软件计算得：邸）=10，E"=20,"）=0,6，=12,靖）二利.

10.某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、

上漆几道重要工序。每种家具的每道工序所用的时间、每道工序的可用时间、每种家具

的利洞由表1一17给出。问工厂应如何安排生产，使总利洞最大？

表1—17家具生产工艺耗时和利润表

所需时间（小时）每道工序可用

生产工序

12345时间（小时）

成型346233600

打磨435643950

上漆233432800

利润（百元）2.734.52.53

解：设%表示第/种规格的家具的生产量（/=1,2,…,5）,则

maxZ=2.7.V,+3x2+4.5,q+2.5x4+3x5

XX

3X]+42+6与+24+3X5<3600

4X[+3K2+5X3+6匕+4X5<3950

XXX

2X1+3X2+33+44+35<2800

X：N0,i=l,2,…,5

通过LINGO软件计算得：.v,=0,x2=38,X3=254,X4=0,X5=642,Z=3181.

11.某厂生产甲、乙、丙三种产品，分别经过A,B,C三种设备加工。已知生产单

位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表2—10所示。

表1—18产品生产工艺消耗系数

甲乙丙设备能力

A（小时）111100

B（小时）1045600

c(小时)226300

单位产品利泗(元)1064

(1)建立线性规划模型，求该厂获利最大的生产计划。

(2)产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加

到6,求最优生产计划。

(3)产品甲的利润在多大范围内变化时，原最优计划保持不变？

设备A的能力如为100+10g,确定保持原最优基不变的q的变化范围。

(5)如合同规定该厂至少生产10件产品丙，试确定最优计划的变化。

解：(1)设内,々，当分别表示甲、乙、丙产品的生产量，建立线性规划模型

maxZ=1()X[+6x2+4x3

X14-x2+x3<100

Jl()$+4X2+5X3<600

2X1+2X2+6X3<300

xrx2,x3>0

标准化得

maxZ=10.+6X2+4x3+0x4+Ox5+0x6

xI-I-x2+x3+x4=100

10x(+4X+5X+x=600

s.t.235

2X]+2X2+6X3+x6=300

列出单纯形表

1064000

仇

CBXBb£当%%

0匕100111100100

0公600[10]4501060

0工6300226001150

1064000

0400[3/5]1/210200/3

1/10

106012/51/201/100150

018006/550—1/51150

Oj02-10-10

6%200/3015/65/3—1/60

10再100/3101/6-2/31/60

046100004-201

%00-10/3-2/30

8/3

故最优解为F=100/3,%=200/3,当二0,又由于七,占，工3取整数，故四舍五人可得

最优解为项=33,为=67,再=°，2max=732.

(2)产品丙的利润q变化的单纯形法迭代表如下：

106Q000

%

b阳工2/%/

6x2200/3015/65/3—1/60

10占100/3101/6-2/31/60

0%100004-201

6一

%00-10/3-2/30

20/3

要使原最优计划保持不变，只要。3=。3一手《0,即。3«6；=6.67.故当产品丙每

件的利润增加到大于6.67时，才值得安排生产。

如产品丙每件的利泗增加到6时，此时6<6.67,故原最优计划不变。

(3)由最末单纯形表计算出

I21

/=-1——G00,巴=-10+—G<0,6=1——q<0,

636

解得<15,即当产品甲的利润q在［6,15］范围内变化时，原最优计划保持不变。

‘5/3-1/60、

(4)由最末单纯形表找出最优基的逆为=-2/31/60,新的最优解为

「201,

'5/3-1/60、。()0十1(靖(200+50(7、

X；=B/=-2/31/606001100-204>0

-3

「20*<300,3(100—200

解得-4«q«5,故要保持原最优基不变的g的变化范围为[-4,5].

(5)如合同规定该厂至少生产10件产品丙，则线性规划模型变成

maxZ=10芭+6x2+4x3

X[+x2+x3<100

1+4JT2+5犬3<600

<2x}4-2X2+6X3<300

x3>10

xpx2,x3>0

通过LINGO软件计算得到：再=32,巧=58，i=1°，Z=708.

第2章对偶规划(复习思考题)

1.对偶问题和对偶向量(即影子价值)的经济意义是什么？

答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来

考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利涧是产品

生产带来的，同时又是资源消耗带来的。

对偶变量的值X表示第，种资源的边际价值，称为影子价值。可以把对偶问题的解

Y定义为每增加一个单位的资源引起的目标函数值的增量。

2.什么是资源的影子价格？它与相应的市场价格有什么区别？

答：若以产值为目标，则)"是增加单位资源/对产值的贡献，称为资源的影子价格

(ShadowPrice)o即有“影子价格=资源成本+影子利润”。因为它并不是资源的实际价

格，而是企业内部资源的配比价格，是由企业内部资源的配黄状况来决定的，并不是由

市场来决定，所以叫影子价格。可以将资源的市场价格与影子价格进行比较，当市场价

格小于影子价格时，企业可以购进相应资源，储备或者投入生产；当市场价格大于影子

价格时，企业可以考虑暂不购进资源，减少不必要的损失。

3.如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检

脸数之间的关系？

答：(1)最优性定理：设元F分别为原问题和对偶问题的可行解，且c又=

则RF分别为各自的最优解。

(2)对偶性定理：若原问题有最优解，那么对偶问题也有最优解，而且两者的目

标函数值相等。

(3)互补松弛性：原问题和对偶问题的松弛变量为x$和八，它们的可行解x",y"

a

为最优解的充分必要条件是Lx、=o,rs.x=o.

(4)对偶问题的最优解对应于原问题最优单纯形表中，初始基变量的检验数的负

值。若-匕对应于原问题决策变量〉的检脸数，则-y对应于原问题松弛变量看的检脸

数。

4.已知线性规划问题

maxZ=4X[+x2+2匕

8巧+3X2+x5<2(第一'种资源)

s.t.<6X]+x2+<8(第二种资源)

x,,x2,x3>0

(1)求出该问题产值最大的最优解和最优值。

(2)求出该问题的对偶问题的最优解和最优值c

(3)给出两种资源的影子价格，并说明其经济含义；第一种资源限量由2变为4,

最优解是否改变？

(4)代加工产品丁，每单位产品需消耗第一种资源2单位，消耗第二种资源3单

位，应该如何定价？

解：(1)标准化，并列出初始单纯形表

Cj41200<9,

b

xB修々%%与

0之42[8]31102/8

08611018/6

41200

4%1/413/8[1/8]1/802

013/26—5/41/4-3/4126

%0-1/23/2-1/20

2283110

0%6-2-20-11

-12-50-20

由最末单纯性表可知，该问题的最优解为：X*=(0,0,2。6)/，即玉=0,x2=0,x3=2,

最优值为Z=4.

(2)由原问题的最末单纯形表可知，对偶问题的最优解和最优值为：

必=2,%=0,卬=4♦

(3)两种资源的影子价格分别为2、0,表示对产值贡献的大小；第一种资源限量

由2变为4,最优解不会改变。

(4)代加工产品丁的价格不低于2x2+0x3=4.

5.某厂生产A,B,C,D4种产品，有关资料如表2—6所示。

表2—6

源消耗产品资源供应量原料成本

资源ABCD(公斤)(元/公斤)

甲23128002.0

乙543412001.0

丙345310001.5

华住产品售价(.元)14.52115.516.5

(1)请构造使该厂获利润最大的线性规划模型，并用单纯形法求解该问题(不计

加工成本)。

(2)该厂若出租资源给另一个工厂，构成原问题的对偶问题，列出对偶问题的数

学模型，资源甲、乙、丙的影子价格是多少？若工厂可在市场上买到原料丙，工厂是否

应该购进该原料以扩大生产？

(3)原料丙可利用量在多大范围内变化，原最优生产方案中生产产品的品种不变

(即最优基不变)？

(4)若产品B的价格下降了0.5元，生产计划是否需要调整？

解：(1)设网,々，工3，大4分别表示甲、乙、丙产品的生产量，建立线性规划模型

maxZ=+5xz+3x4+4JV4

2X14-3X2+/+2X4<800

5X[+4X2+3xy+4X4<1200

3X1+4X2+5X3+3X4<1000

x；NO"=1,2,3,4

初始单纯形表

%1534000

%A

gX"b%x2/马

0%8002312100800/3

0工6120054340101200/4

010003[4]530011000/4

%1534000

最末单纯形表

1534000

%A

CBXBb匹工3相丸4匕

01001/40-13/4011/4-1

420020-2101-1

5x2100-3/4111/400-3/41

%-13/40-11/400-1/4-1

解得最优解为：X*=(0,100,0,200,100)r,最优值Z=1300.

(2)原问题的对偶问题的数学模型为

min卬=800%+1200%+1000%

2M+5%+3%21

3必+4%+4)，3之5

s.t.<M+3乂+5)4-1

2凹+4h+3"4

.)22，3心。

解得影子价格分别为2,1.25、2.5。对比市场价格和影子价格，当市场价低于影子

价格时购进。

(3)原料丙可利用量在［900,1100］范围内变化，原最优生产方案中生产产品的品

种不变(即最优基不变)。

(4)若产品B的价格下降了0.5元，生产计划不需要调整。

6.某企业生产甲、乙两种产品，产品生产的工艺路线如图2—1所示，试统计单位

产品的设备工时消耗，填入表2—7。又已知材料、设备C和设备D等资源的单位成本和

拥有量如表2—7所示。

表2—7资源消耗与资源成本表

产品资源消耗资源成本

资源拥有量

资源甲乙元/单住资源

材料(公斤)60502004200

设备C(小时)3040103000

设备D(小时)6050204500

据市场分析，甲、乙产品销售价格分别为13700元和11640元，试确定获利最大的

产品生产计划。

(1)设产品甲的计划生产量为用，产品乙的计划生产量为它,试建立其线性规划

的数学模型；若将材料约束加上松弛变量与，设备c约束加上松弛变量乙，设备D约束

加上松弛变量与，试化成标准型。

(2)利用LINDO软件求得：最优目标函数值为18400,变量的最优取值分别为

Xl=20,x2=60,x3=0,x4=0,x5=300,则产品的最优生产计划方案是什么？并解释

巧=0,x4=0,x5=300的经济意义。

(3)利用LINDO软件对价值系数进行敏感性分析，结果如下：

ObjCoefficientRanges

CurrentAlIowabIe

VariabIeAllowableDecrease

CoefIncrease

再2008820

x224026.6773.33

试问如果生产计划执行过程中，甲产品售价上升到13800元，或者乙产品售价降低

60元，所制定的生产计划是否需要进行调整？

(4)利用LINDO软件对资源向量进行敏感性分析，结果如下：

RighthandSideRanges

AIIowabIeAIIowabIe

ResourceCurrentRhs

IncreaseDecrease

材料4200300450

设备C3000360900

设备D4500Infinity300

试问非紧缺资源最多可以减少到多少，而紧缺资源最多可以增加到多少？

解：(1)建立的线性规划模型为

maxZ=200x,+240x2

60A：1I50X2V4200

30x.+40占<3000

s.t.

60xj+50X2<4500

XpX,>0

将其标准化

maxZ=200x,+240x2

60a+50X2+x?=4200

30x,+40X2+X4=3000

60X1+50X2+X5=4500

xi>0J=1,2,…,5

(2)甲生产20件，乙生产60件，材料和设备C充分利用，设备D剩余600单位。

(3)甲上升到13800需要调整，乙下降60不用调整。

(4)非紧缺资源设备D最多可以减少到300,而紧缺资源一材料最多可以增加到

300,紧缺资源一设备C最多可以增加到360。

第3章整数规划(复习思考题)

1.整数规划的类型有哪些？

答：纯整数规划、07规划和混合整数规划。

2.试述整数规划分枝定界法的思路。

答：(1)首先不考虑整数条件，求解整数规划相应的线性规划问题。若相应的线性

规划问题没有可行解，停止计算，这时原整数规划也没有可行解。

(2)定界过程。对于极大化的整数规划问题，当前所有未分枝子问题中最大的目

标函数值为整数规划问题上界；在满足整数约束的子问题的解中，最大的目标函数值为

整数规划问题的下界。当上下界相同时，则已得最优解；否则，转入剪枝过程C

(3)剪枝过程。在下述情况下剪除这些分枝：①若某一子问题相应的线性规划问

题无可行解；②在分枝过程中，求解某一线性规划所得到的目标函数值Z不优于现有下

界。

(4)分枝过程。当有多个待求分枝时，应先选取目标函数值最优的分枝继续进行

分枝。选取一个不符合整数条件的变量看作为分枝变量，若毛的值是〃：，构造两个新的

约束条件：>[/?；]+1,分别并入相应的数学模型中，构成两个子问题。对

任一个子问题，转步骤(1).

3.试用分枝定界法求如下线性规划:

maxZ=40+90x2

9玉+7X2<56

七7x1+20x2<70

xpx2>0

XpX,取整数

解：

最优整数解为：八=4,"胡二弘0.上界:

理>2=1生,=355型_0“I

4.有4名职工妁龈不属说蠢个人做$演工器所用的时间不同，所花

甲15182124

乙19232218

丙26171619

丁19212317

问指派哪个人去完成哪项工作，可使总的消耗时间最少？

1,任务，由人员;完成

解：设马=%为个人/.对于任务/的时间耗费矩阵,

0,任务i不由人员;完成

则建立整数规划模型为:

minZ=

i=lJ=l

力“1

r=l

,ixu=1

j=i

勺=0或山=123,4

解得：x12=l,x21=1,J33=l,x44=h其余均为零，Z=7(),即任务A由乙完成，任

务B由甲完成，任务C由丙完成，任务D由丁完成。

5.某部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人，周五

至少需要80人，周六周日每天至少需要90人，先规定应聘者需连续工作5天，试确定

聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。

解：设x,表示在第7天应聘的展员人数(/=1,2,3,4,5,6,7)。数学模型为

niinZ=X)+x2++x4+x5+x6+x7

+X44-X5+X6+X7>50

阳+x2+x5+x6+x7>50

X]+/+戈3+工6+X7>50

*+七+13+Z+X7>5()

S.t.,>80

x2+x3+x4+x5+x6>90

x3+x4+x5+x6+x7>90

巧N0,i=l,2，…,7

再取整数,i=1,2,…,7

解得：X]=0,x2-4,X3=32,七=10,x5=34,x6=10,x7=4,Z=94.

第4章目标规划（复习思考题）

1.某计算机公司生产A,B,C三种型号的笔记本电脑。这三种笔记本电脑需要在

复杂的装配线上生产，生产一台A,B,C型号的笔记本电脑分别需要5小时、8小时、

12小时。公司装配线正常的生产时间是每月1700小时，公司营业部门估计A,B,C三

种笔记本电脑每台的利润分别是1000元、1440元、2520元，而且公司预测这个月生产

的笔记本电脑能够全部售出。公司经理考虑以下目标：

第一目标：充分利用正常的生产能力，避免开工不足；

第二目标：优先满足老客服的需求，A,B,C三种型号的电脑各为50台、50台、

80台，同时根据三种电脑三种电,脑的纯利润分配不同的加权系数；

第三目标：限制装配线加班时间，最好不超过200小时；

第四目标：满足各种型号电脑的销售目标，A,B,C三种型号分别为100台、120

台、100台，再根据三种电脑的纯利润分配不同的加权系数；

第五目标：装配线加班时间尽可能少。

请列出相应的目标规划模型，并用LINGO软件求解。

解：建立目标约束。

(1)装配线正常生产

设生产A,B,C型号的电脑为七,它,马(台)，4-为装配线正常生产时间未利用数，

为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束为

min{"1}

5司+8々+12/+4--d：=1700

(2)销售目标

优先满足老客户的需求，并根据三种电脑的纯利泗分配不同的权因子，A,B,C三

种型号的电脑每小时的利润是幽，上曳，至2因此，老客户的销售目标约束为

5812

min{20W+18d；+21d；}

+d2-=50

x2+d；-d；=50

x3+d；-d；=80

再考虑一般销售。类似上面的讨论，得到

min{201/5+I8J6+2\dj}

M+〃；一百=1°0

x2+d~-d；=120

x3+d--若=100

（3）加班限制

首先是限制装配线加班时间，不允许超过200小时，因此得到

5为+8.¥2+12X3+-d；=1900

其次装配线的加班时间尽可能少，即

min{d；}

5x,+8々+12/+d「-d：=1700

写出目标规划的数学模型

minG=P、d:+R（20d£+18d；+21d；）+P.d；+P式20dg+18d[+2M；）+P§d：

5M+8々+12X3+d「-d；=1700

*+d；-d；=50

%-d；=50

+d4—d；-80

…工-4=120

Xyd-j-d；=100

5方+知+12X3+d「-d：=1900

x.>0,/=l,2

“,d；NO,/=1,2,…,8

经过LINGO软件计算，得到修=100,%=55,曰=80,装配线生产时间为1900小时，

满足装配线加班不超过200小时的要求。能够满足老客户的需求，但未能达到销售目标。

销售总利润为100X1000+55X1440+80X2520=380800（元）。

2.已知3个工厂生产的产品供应给4个客户，各工厂生产量、用户需求量及从各

工厂到用户的单位产品的运输费用如表4—3所示。由于总生产量小于总需求量，上级

部门经研究后，制定了调配方案的8个目标，并规定了重要性的次序。

表4—3工厂产量一用户需求量及运费单价（单位：元）

1234生产量

15267

23546

34523

需求量(单位)200100450250

第一目标：用户4为重要部门，需求量必须全部满足；

第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；

第三目标：每个用户的满足率不低于80%；

第四目标：应尽量满足各用户的需求；

第五目标：新方案的总运费不超过原运榆问题(线性规划模型)的调度方案的10%；

第六目标：因道路限制，工厂2到用户4的路线应尽量避免运输任务；

第七目标：用户1和用户3的