《管理运筹学》(第二版)课后习题参考答案第1章线性规划(复习思考题)1. 什么是线性规划？线性规划的三要素是什么？答：线性规划(Lin ear Programmi ng , LF)是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。

线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。

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

决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。

2. 求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？答：(1)唯一最优解：只有一个最优点；(2)多重最优解：无穷多个最优解；(3)无界解：可行域无界，目标值无限增大；(4)没有可行解：线性规划问题的可行域是空集。

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

3. 什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项 ' ，决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业 来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明 “遅 约束的左边取值大于右边规划值，出现剩余量。

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

答：可行解：满足约束条件 扎—‘丸 的解，称为可行解。

基可行解：满足非负性约束的基解，称为基可行解最优解：使目标函数最优的可行解，称为最优解。

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

它们的相互关系如右图所示：5 •用表格单纯形法求解如下线性规划解：标准化1可行基：对应于基可行解的基，称为可行基。

基可行解SA] +S 2s.t.列出单纯形表/4 3/20 1/2 [8]/83/2/6/8 1/8]5/4 /41/2/8 1/4/(1/83/4 13/2/(1/412 5故最优解为二「 - 1，即——二凡八，此时最优值为「产J 士匚6.表1 —15中给出了求极大化问题的单纯形表，问表中1为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以代替基变量；（4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。

表1 —15某极大化问题的单纯形表■■-:：i 兀0".倉. b -'i0 d 4解: (1)，■ 11；(2) 阮存①匚監D ｛小口中至少有一个为零）. 7(3)八d 3c. >0, a, > 0* — > ——4 心.▲7(4)为人工变量，且为包含M的大于零的数,量，且为包含M的大于零的数，".(5) 为人工变7 •用大M法求解如下线性规划max Z = 5A,+3X; +6州2^ + x2 4 3咼<16A；4■凡 +比=10解：加入人工变量，进行人造基后的数学模型如下:列出单纯形表5360 Mbv.-811 21 18/1612 1 3][0 6/3M11 11 0 0/1+M5 +M36+M 0 0 031/35/3018/311/3 8/52/31/3106/31/3 61/3[2/3]00M4/31/3 4/200-01一0011/2/2 5/23[1/2]010/2 1/271/21001/2 /2 41000一123/240011610 2 0140101100-1021-M故最优解为卅=(640,400)「，即1臥辿-5此时最优值为Z (卅)= 42 .8. A, B, C三个城市每年需分别供应电力320, 250和350单位，由I ,11两个电站提供，它们的最大可供电量分别为400单位和450单位，单位费用如表1 —16所示。

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

试建立线性规划模型，求将可供电量用完的最低总费用分配方案。

表1 —16单位电力输电费（单位：元）电站城市I 15 182II 21 256解：设为第i电站向第j城市分配的电量”(i=1,2; j=1,2,3)，建立模型如下：max Z= 15 +18x]2 +22^ + 21^, +25 屉 + 16 心九I * + 心-450片 + x3l> 290x u+ x3l< 320x., + = 250a+ X：3> 270若j + < 350s.t. 口“小9•某公司在3年的计划期内，有4个建设项目可以投资：项目I从第一年到第三年年初都可以投资。

预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目II需要在第一年初投资，经过两年可收回本利150%，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资不得超过20万元；项目III需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资不得超过15万元；项目IV需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资不得超过10万元。

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

问怎样的投资方案，才能使该公司在这个计划期获得最大利润？朴 | （2）（ J）解：设表示第一次投资项目i，设•表示第二次投资项目i，设•表示第三次投资项目i，（i=1,2,3,4），则建立的线性规划模型为max Z -+ 1,6彳"+ ] ,4 A?1牢+叩M 30f黑乜］2屮+ 30_岸"_老‘申+ 叩=1挣+ L5Z h+ 1.2岸1+ 30-屮-宅-叩＜20聲乜15时£)0通过LINGO软件计算得：「■…' 1 - 110•某家具制造厂生产五种不同规格的家具。

每种家具都要经过机械成型、打磨、上漆几道重要工序。

每种家具的每道工序所用的时间、每道工序的可用时间、每种家具的利润由表1—17给出。

问工厂应如何安排生产，使总利润最大？表1—17家具生产工艺耗时和利润表生产工序所需时间（小时）每道工序可用时间（小时）12345成型346233600打磨435643950上漆233432800利润（百元） 2.73 4.5 2.53解：设表示第i种规格的家具的生产量（i=1,2,-…,), 则max Z二+ 3乳+ 4.5.t + 2.5r +3^3X[ + 4A,+ 6 A.+ 2 A J+ 3 < 36004為+ 3儿+ 5旺+ &旺+ 4A5< 39502州+ 3x2+ 3A,+ 4.q + 3旺< 2S00s.t.[暫> 0,/- L2,-%5通过LINGO软件计算得:—厂黑"识氏-讥•-沁I -沁】11 •某厂生产甲、乙、丙三种产品，分别经过A, B, C三种设备加工。

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

表1 —18产品生产工艺消耗系数设甲乙丙备能力A （小时）11110B （小时）10456030C （小时）226单位产品利润（元）1064（1）建立线性规划模型，求该厂获利最大的生产计划。

（2）产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加到6,求最优生产计划。

（3）产品甲的利润在多大范围内变化时，原最优计划保持不变？（4）设备A的能力如为100+10q，确定保持原最优基不变的q的变化范围（5）如合同规定该厂至少生产10件产品丙，试确定最优计划的变化。

解：（1）设分别表示甲、乙、丙产品的生产量，建立线性规划模型max Z = 10 片+6X2+ 铭I(X)10X, + 4 v：+ < 6002珀-2也+ 6^ < 300S.t. > 0标准化得max Z = 10 ij + 6 吗 + 4 杓+ Di. +0x5 + 0 兀%r+ x, + = 10010 州+ 4^2+ 5* + Xj = 6002^ 4- 2JT?+ 6 码+ ^ = 300s.t. 斗、耳」q > 0列出单纯形表106400 r,b百X.0100111 0600[10]45 0300226 T」1064001 0 0 100 0 1 0 60 0 0 1 1500400[3/5]1/210 200/31/10 106012/51/201/10 0 150018006/550 1 1501/502-10—106%200/3015/65/301/610100/3101/6—2/31/6 0 0100004—20 100—8/3—10/3—2/30故最优解为L = 100 13：Xy -200 y，又由于'取整数，故四舍五入可得最优解为’=671= 732(2)产品丙的利润’变化的单纯形法迭代表如下:106 5 000H儿b耳町q■、6200/3015/65/301/610100/3101/6—2/31/6 00100004—20 1 00—20/3—10/3—2/30要使原最优计划保持不变，只要20Cj_T£0 2，即26—a 6.673 .故当产品丙每件的利润增加到大于6.67时，才值得安排生产。

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

(3)由最末单纯形表计算出,I 2 A A打* =—I —<?. £ j =一10 + —C| £=】一一G兰06 3 6,解得. ，即当产品甲的利润在I范围内变化时，原最优计划保持不5/3-1/6 (T-2/3 1/6 0° 1丿，新的最优解为解得八匕鼓，故要保持原最优基不变的(5)如合同规定该厂至少生产10件产品丙，则线性规划模型变成max Z= 10占十6坷+ 4為A r + ® + 舌 £ 100 10 E + 4 ,Y ? +5 .¥? < 600 * 2 州 * 2 扎 + 6 召 < 300码> 10s.t. S 勺小去°通过LINGO 软件计算得到：三沢乜"沁沁、=二总「懐第2章对偶规划(复习思考题)1 •对偶问题和对偶向量(即影子价值)的经济意义是什么？答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利 润是产品生产带来的，同时又是资源消耗带来的。