海量资源，欢迎共阅 《管理运筹学》（第二版）课后习题参考答案 第1章线性规划（复习思考题） 1．什么是线性规划？线性规划的三要素是什么？ 答：线性规划（LinearProgramming，LP）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？ 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？ 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0ib，

决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 海量资源，欢迎共阅 2 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0XbAX，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5．用表格单纯形法求解如下线性规划。

s.t.0,,86238321321321xxxxxxxxx

解：标准化32124maxxxxZ

s.t.0,,,,862385432153214321xxxxxxxxxxxxx

列出单纯形表 jc 4 1 2 0 0 i

BC BX b 1x 2x 3x 4x

5x

0 4x 2 [8] 3 1 1 0 2/8

0 5x 8 6 1 1 0 1 8/6

j 4 1 2 0 0 4 1x 1/4 1 3/8 [1/8] 1/8 0 (1/4)/(1/8)

0 5x 13/2 6 －5/4 1/4 －3/4 1 (13/2)/(1/4)

j 0 －1/2 3/2 -1/2 0 2 3x 2 8 3 1 1 0 海量资源，欢迎共阅 0 5x 6 －2 －2 0 －1 1

j －12 －5 0 －2 0 故最优解为TX)6,0,2,0,0(*，即2,0,0321xxx，此时最优值为4*)(XZ．

6．表1—15中给出了求极大化问题的单纯形表，问表中dccaa,,,,2121为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以1x代替基变量5x；（4）该线性规划问题具有无界解；（5）该线性规划问

题无可行解。 表1—15某极大化问题的单纯形表

jc 1c

2c

0 0 0

i

BC BX b 1x 2x 3x 4x

5x

0 3x d

4 1a 1 0 0

0 4x 2 －1 －5 0 1 0

0 5x 3 2a －3 0 0 1

j 1c

2c

0 0 0

解：（1）0,0,0

21ccd；

（2）中至少有一个为零）（

2121,0,0,0ccccd；

（3）221

34,0,0ad

ac；

（4）0,012ac；

（5）1x为人工变量，且1c为包含M的大于零的数，234ad；或者2x为人工变量，

且2c为包含M的大于零的数，0,01da．

7．用大M法求解如下线性规划。 海量资源，欢迎共阅 4 s.t.0,,101632182321321321321xxxxxxxxxxxx

解：加入人工变量，进行人造基后的数学模型如下： s.t.)6,,2,1(0101632182632153214321ixxxxxxxxxxxxxi

列出单纯形表 jc 5 3 6 0 0 －M i

BC BX b 1x 2x 3x 4x

5x

6x

0 4x 18 1 2 1 1 0 0 18/1

0 5x 16 2 1 [3] 0 1 0 16/3

－M 6x 10 1 1 1 0 0 1 10/1

j 5+M 3+M 6+M 0 0 0 0 4x 38/3 1/3 5/3 0 1 －1/3 0 38/5

6 3x 16/3 2/3 1/3 1 0 1/3 0 16

－M 6x 14/3 1/3 [2/3] 0 0 －1/3 1 14/2

j M311 M321 0 0 M312 0

0 4x 1 －1/2 0 0 1 1/2 －5/2 －

6 3x 3 [1/2] 0 1 0 1/2 －1/2 6

3 2x 7 1/2 1 0 0 －1/2 3/2 14

j 1/2 0 0 0 －3/2 M23 0 4x 4 0 0 1 1 1 －3

5 1x 6 1 0 2 0 1 －1 海量资源，欢迎共阅 3 2x 4 0 1 －1 0 －1 2

j 0 0 －1 0 －2 －1－M 故最优解为TX)0,0,4,0,4,6(*，即0,4,6321xxx，此时最优值为42*)(XZ．

8．A，B，C三个城市每年需分别供应电力320，250和350单位，由I，II两个电站提供，它们的最大可供电量分别为400单位和450单位，单位费用如表1—16所示。由于需要量大于可供量，决定城市A的供应量可减少0～30单位，城市B的供应量不变，城市C的供应量不能少于270单位。试建立线性规划模型，求将可供电量用完的最低总费用分配方案。 表1—16单位电力输电费（单位：元） 电站城市 A B C

I 15 18 22 II 21 25 16 解：设ijx为“第i电站向第j城市分配的电量”（i=1,2;j=1,2,3），建立模型如下：

s.t.3,2,1;2,1,035027025032029045040023132313221221112111232221131211jixxxxxxxxxxxxxxxxxij

9．某公司在3年的计划期内，有4个建设项目可以投资：项目I从第一年到第三年年初都可以投资。预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目II需要在第一年初投资，经过两年可收回本利150%，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资不得超过20万元；项目III需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资不得超海量资源，欢迎共阅 6 过15万元；项目IV需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 解：设)1(

ix表示第一次投资项目i，设)2(ix表示第二次投资项目i，设)3(ix表示第三次

投资项目i，（i=1,2,3,4），则建立的线性规划模型为

s.t.4,3,2,1,0,,101520302.15.12.1302.130)3()2()1()1(4)1(3)1(2)1(3)2(1)1(2)1(1)1(1)1(2)2(1)1(4)3(1)1(2)1(1)1(1)1(3)2(1)1(2)1(1ixxxxxxxxxxxxxxxxxxxxxxiii

通过LINGO软件计算得：44,12,0,20,10

)2(1)2(1)1(3)1(2)1(

1xxxxx．

10．某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、上漆几道重要工序。每种家具的每道工序所用的时间、每道工序的可用时间、每种家具的利润由表1—17给出。问工厂应如何安排生产，使总利润最大？ 表1—17家具生产工艺耗时和利润表

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

时间（小时） 1 2 3 4 5

成型 3 4 6 2 3 3600 打磨 4 3 5 6 4 3950 上漆 2 3 3 4 3 2800 利润（百元） 2.7 3 4.5 2.5 3 解：设ix表示第i种规格的家具的生产量（i=1,2,…,5），则