《管理运筹学》-田世海(习题及解答)

习题11.1判断对错（1）运筹学作为一门科学正式诞生于20世纪40年代。√（2）运筹学在英国一般被译作OperationalResearch。√（3）田忌赛马属于决策论部分的内容。×博弈论（4）运筹学是一门以决策支持为目标的学科。√（5）第一次世界大战大量新式武器的使用，促进了现代运筹学的诞生。×第二次世界大战1.2试举例说明管理运筹学的具体应用？1.3运筹学的主要分支有哪些？习题22.1判断对错（1）线性规划一般模型中，自由变量可以用两个非负变量的差来代换。√（2）线性规划模型中增加一个约束条件，可行域的范围一般将缩小。√（3）图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的。√（4）线性规划的目标函数一般取最大值。×（5）线性规划问题中自变量仅能取大于等于零的数。×（6）如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。√（7）单纯形法计算中，如不按最小比值原则选出基变量，则在下一个解中至少有一个基变量的值为负。√（8）单纯形法计算中，选取最大正检验数对应的变量作为进基变量，将使目标函数值得到最快的增长。×（9）人工变量法求线性规划问题时，若所有检验数≤0，但基变量中仍有人工变量，则问题无可行解。√（10）单纯形法求解线性规划问题时，引入人工变量的目的是为了构造单位矩阵。√2.2将下列问题化为标准形式（1）（2）解：（1）（2）将绝对值化为两个不等式，则标准形式为2.3用图解法对下列问题进行求解，并指出问题具有唯一最优解，无穷多最优解，无界解还是无可行解。（1）（2）（3）（4）解：(1)唯一最优(2)有多重解。最优解X（1）＝（3/2，1/2）；X（2）＝（4/5，6/5）最优值Z=2(3)无最优(4)唯一最优2.4分别用图解法、单纯形法求解下列线性规划问题，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个点。（1）（2）解：(1)(2)2.5用单纯形法和Excel求解下列线性规划问题。（1）（2）解：(1)(2)最优解：目标函数最优值2.6分别用M法和两阶段法求解下述线性规划问题，并指出是哪一类解。（1）（2）（1）解法一：大M法标准化加入人工变量得：迭代最优单纯形表如下：Cj→－2－3－100－M－MCBXBB－1bX1X2X3X4X5X6X7－3X29/5013/5－3/101/103/10-1/10－2X14/510－2/51/5－2/5－1/52/5Cj－Zj000－1/2－1/21/2－M1/2－M最优解：目标函数最优值解法二：两阶段法第一阶段数学模型为：最优单纯形表如下：Cj→00000－1－1CBXBB－1bX1X2X3X4X5X6X70X29/5013/5－3/101/103/10-1/100X14/510－2/51/5－2/5－1/52/5Cj－Zj00000－1－1第二阶段最优单纯形表如下：Cj→－2－3－100CBXBB－1bX1X2X3X4X53X29/5013/5－3/101/102X14/510－2/51/5－2/5Cj－Zj0001/21/2最优解：目标函数最优值因为x3的检验数=0，所以此线性规划问题有无穷多最优解。（2）解：大M法。数学模型为C(j)10-510-MR.H.S.RatioBasisC(i)X1X2X3X4X5X5-M53101102X40-51-101015MC(j)-Z(j)10-51000*BigM531000X11013/51/501/52X4004-91125C(j)-Z(j)0-11-10-220*BigM0000-10最优解X＝(2,0,0)；Z=20两阶段法。第一阶段：数学模型为C(j)00001R.H.S.RatioBasisC(i)X1X2X3X4X5X51[5]3101102X40-51-101015MC(j)-Z(j)-5-3-100X1013/51/501/52X4004-91125C(j)-Z(j)00001第二阶段C(j)10-510R.H.S.RatioBasisC(i)X1X2X3X4X11013/51/5022X4004-9125MC(j)-Z(j)0-11-10最优解X=(2,0,0)；Z=202.7（1）当现行解为可行解，且对应非基变量的检验数均小于0时，线性规划问题才有惟一最优解．即a2≥0，a5＜0，a6＜0·（2）线性规划问题有多重最优解是当某个非基变量的检验数为0，所以a2≥0，a5=0，a6≤0或a2≥0，a5≤0，a6=0，a4＞0（3）现行解为退化基本最优解的条件是基变量中含有零分量，且所有的检验数均非负。所以a2=0，a5≤0，a6≤0（4）a2≥0，现行解为可行解，a6＞0，a4≤0时，该线性规划目标函数无界。因此参数范围是a2≥0，a6＞0，a4≤0（5）当a1≥0，a2＜0时，该线性规划问题的第一个等式约束为矛盾方程，因而无可行解。2.8已知线性规划问题的初始单纯形表和用单纯形表迭代后得到的表2-27如下，试求a～L的值。表2-27初始单纯形表和用单纯形表迭代后得到的表x1x2x3x4x5x46bcd10x51－13e01Cj－Zja－1200┇┇x1fg2－11/20x54hi11/21Cj－Zj0－7jkL解：a=3，b=2，c=4，d=－2，e=2，f=3，g=1，h=0，I=5，j=5，k=－3/2，L=02.9工厂每月生产甲、乙、丙三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表2-28所示。表2-28三种产品单件产品利润如表产品资源甲乙丙资源限量材料(kg)1.51.242500设备(台时)31.61.21400利润(元/件)101412根据市场需求，预测三种产品最低月需求量分别是150、260和120，最高月需求是250、310和130，试建立该问题的数学模型,使每月利润最大。解：设x1、x2、x3分别为产品甲、乙、丙的产量，则数学模型为2.10某糖果厂用原料A,B,C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A,B,C的含量，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如表2-29所示。问该厂每月生产这三种牌号糖果各多少㎏，使得到的利润为最大？试建立这个问题的线性规划数学模型。表2-29三种牌号糖果的单位加工费及售价甲乙丙原料成本/元/kg每月限用量/kgA≥60%≥20%2.002000B1.502500C≤20%≤50%≤60%1.001200加工费/元/kg0.500.400.30售价/元/kg3.402.852.25解：设为生产第j种糖果耗用的第i种原料的数量，则三种糖果的生产量分别为：X甲=x11+x21+x31；X乙=x12+x22+x32；X丙=x13+x23+x332.11建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架，两种窗架所需材料规格及数量如表2-30所示。问怎样下料使得（1）用料最少；（2）余料最少？表2-30两种窗架所需材料规格及数量型号A型号B每套窗架需要材料长度（m）数量(根)长度(m)数量(根)A1：1.72B1：2.72A2：1.33B2：2.03需要量（套）200150解：第一步：求下料方案，见下表。方案一二三四五六七八九十十一十二十三十四需要量B1:2.7m21110000000000300B2:2m01003221110000450A1:1.7m00100102103210400A2:1.3m01120010130234600余料0.600.30.700.30.70.610.10.900.40.8第二步：建立线性规划数学模型设xj（j=1,2,…，14）为第j种方案使用原材料的根数，则（1）用料最少数学模型为用单纯形法求解得到两个基本最优解X(1)=(50,200,0,0,84,0,0,0,0,0,0,200,0,0);Z=534X(2)=(0,200,100,0,84,0,0,0,0,0,0,150,0,0);Z=534（2）余料最少数学模型为用单纯形法求解得到两个基本最优解X(1)=(0,300,0,0,50,0,0,0,0,0,0,200,0,0);Z=0，用料550根X(2)=(0,450,0,0,0,0,0,0,0,0,0,200,0,0);Z=0，用料650根显然用料最少的方案最优。习题33.1判断对错，并说明为什么。（1）任何线性规划问题存在并具有唯一的对偶问题。（2）根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题具有无界解。（3）若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解。（4）设分别为标准形式的原问题与对偶问题的可行解，分别为其最优解，则恒有：（5）已知为线性规划的对偶问题的最优解，若＞0，说明在最优生产计划中，第i种资源已完全耗尽。（6）若某种资源的影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k。（7）互为对偶的问题中，原问题一定是求最大值的线性规划问题。（8）对偶单纯形法是直接解对偶问题的一种方法。（9）线性规划灵敏度分析的主要功能是分析线性规划参数变化对最优解的影响。（10）若线性规划问题最优基中某个基变量的目标系数发生变化，则所有非基变量的检验数发生变化。解：2，6，7，8×；其余√3.2求出下列线性规划的对偶规划：（1）（2）（3）（4）解：（1）（2）（3）（4）3.3用对偶单纯形法求下列线性规划问题（1）（2）解：(1)(2)最优解：目标函数最优值03.4解：(1)对偶问题为：(2)将带入约束条件的①为严格不等式，由互不松弛性得最优解：目标函数最优值：3.5（1）（2）3.6解（1）设：分别为产品A、B、C的产量，则该问题的线性规划模型为：用单纯形法迭代的最优解如下表：Cj→31500CBXBB－1bX1X2X3X4X50X4153-101-15X363/54/5101/5Cj－Zj0-300-1因而最优解，最大利润为30（2）劳动力和原料的影子价格分别为0，1。设购进的原料数为，为保持最优基不变，必有，而解得：因而最多可购进原料15单位，总利润增加（单位）。净利润增加15-0.8×15=3单位。（3）C1≤3，原最优解不变，C3≥5最优计划不变。（4）劳动力可以减少15个单位，原最优解不变。（5）最优解，最大利润为30。注：本题还有另一个最优解，3≤C1≤6，5/2≤C3≤53.7解最优解为：（1）最优基不变，最优解为：（2）最优解为：（3）最优解不变。（4）最优解为：（5）最优解不变。（6）最优解为：（7）最优解不变。（8）最优解为：（9）最优解为：3.8（1）按从初始表为最终表的迭代顺序，从最终表反推回去即得初始表。如下x1x2x3x4x5x4501210x5103－1101Cj-Zj6－21000（2）计算最终表中x2，x4，x5的新的检验数即时，原最优解不变。（3）得，此时原最优基不变。3.9（1）解：令λ=0，求最优解（目标函数化为求极大）x1x2x3x4x321012*x252103Cj-Zj1003x411/201/21x221/21－3/20Cj-Zj－1/20－3/20λ≥0时，CBB－1（P1,P3）-（C1,C3）=（-2λ,-1）-（-1,λ）=（1/2-λ,3/2-2λ）最终表如下：x1x2x3x4x411/2*01/21x221/21－3/20Cj-Zjλ－1/202λ－3/20解得0≤λ≤1/2此时上表为最优表。minz=2λ+2λ>1/2时，表1中x1的检验数首先变为负数，故迭代得下表x1x2x3x4x12101*2x2101－2－1Cj-Zj00λ－11－2λ解，知1/2≤λ≤1，为最优表，minZ=3λ>1时，表中x3的检验数首先变为负数，故迭代得下表x1x2x3x4x321012x252103Cj-Zj1－λ003－4λ解得λ≥1,为最优表，minz=－2λ+5。画出minz(λ)的函数关系曲线如下图3.10解：目标函数化为求极大。先求出λ=0时的最优解，为简便用对偶单纯形法，即x1x2x3x4x1210－2－1x2－101－1*1Cj-Zj00－5－1x141－20－3x310－11－1Cj-Zj0－50－6λ≥0时，B－1最终表变为x1x2x3x4x14－3λ1－20－3x31－λ0－1*1－1Cj-Zj0－50－60≤λ≤1时为最优表minz=－5λ+6x12－λ10－2－1*x2λ－101－11Cj-Zj00－5－11≤λ≤2时为最优表minz=1x1λ－2－1021x2111－30Cj-Zj－10－30λ≥2时为最优表，minz=λ-1图示如右所示3.11解：（1）先将θ值反映到最终表中。故最终表变为x1x2x3x4x5x12+101/2－1/20x26+011/21/20x54－00－1/21/2*1Cj-Zj00－2－－100≤θ≤2时为最优，maxz(θ)=20++x1610001x22+0110-1x48－00-1*12Cj-Zj00-302-2≤θ≤8时为最优，maxz(θ)=12+x1610001x21001011x3－8001-1-2Cj-Zj000-3-4-θ≥8时为最优，maxz(θ)=36+（2）作图如下3.12解：设该厂每天生产原稿纸x1捆，日记本x2打，练习本x3箱，又用λ表示该厂招收的临时工数，则本例可列出如下的参数线性规划模型：当λ=0时求解得最终单纯形表如下：x1x2x3x4x5x22000107/31/10－10x1100001－4/3－1/1040Cj-Zj00－1/3－1/10－20即该厂最优生产计划为生产原稿纸1000捆，日记本2000打，可盈利5000元/天。从上表中看出劳动力的影子价格为20元/天，大于市场价格，故该厂应招收临时工，将其反映到上表中，并用对偶单纯形表计算，过程如下：x1x2x3x4x5x22000－10λ017/31/10－10*x11000+40λ10－4/3－1/1040Cj-Zj00－1/3－1/10－200≤λ≤200x5λ－200－1/10－7/30－1/1001x190001483/100Cj-Zj0－2－5－3/100λ≥200由此可知，当招收临时工人数在200人以下时，该厂盈利z=5000+5λ,当λ≥200时，盈利为z=9000－15λ。z（λ）随参数λ变化如右图。

习题44.1（3）（5）（7）（8）（10）√其余×4.24.34.4（1）（2）运量表1销地产地B1B2B3B4产量A11515A200151025A35销量5151510运量表2销地产地B1B2B3B4产量A110515A2515525A35销量51515104.5①增加一个假想销地B4，得最优调运方案如下表。销地产地B1B2B3B4产量A188A2527A34004销量4852②C11≥0；③2≤C23≤44.6解：产销平衡表为123虚产量04080120021500540580021`570610650032M600640042`M670710023MM550013`MM62003销量33474.8销地产地B1B2B3B4B5产量A1501060A250202090A3302050A45050A55050销量5050508070总运费为：Z=c14x14+c23x23+c25x25+c34x34=2404.9解：运输问题的产地与销地也可看作发地与收地，该问题可将各季度的生产能力看作是相应发点的发货量；同样把按合同交付柴油机的四个季度的数量看作是收货点的收货量．这样总发货量为：25＋35＋30＋10＝100（台），总收货量为：10＋15＋25＋20＝70（台）。于是该问题就可以看作是一个产大于销的运输问题．引进虚设收货点D，其收货量为30(台)，即化为产销平衡问题，这时单位运价可取作：Cij＝第i季度每台柴油机的生产成本+（j-i）个季度每台柴油机的存贮费（j≥i）。如：C12=10.80+(2-1)×0.15＝10.95；C13=10.80+(3-1)×0.15＝11.10。当j<i时，实际上i季度生产的柴油机不可能在j季度销售，所以这时将费用记为M（任意大正数）；各发点到虚设收点D的单位运价均为0。于是单位运价表和经用表上作业法求解，得多个最优方案之一如下表。3.9单位运价表（台）收地发地1234D发量Ⅰ10.810.9511.1011.25025ⅡM11.1011.2511.40035ⅢMM11.0011.15030ⅣMMM11.30010收量10152520303.9最优调运方案收地发地1234D发量Ⅰ1015025Ⅱ53035Ⅲ25530Ⅳ1010收量1015252030即第一季度生产25台，10台当季度交货，10台2季度交货，5台3季度交货；第二季度生产5台，当季度交货；第三季度生产30台。20台当季度交货，10台4季度交货；第四季度生产10台，于当季度交货．按此方案生产，该厂消耗的生产与存贮总费用最少为773万元。4.10运价表如表4-66，B1的需求为30≤b1≤50，B2的需求为40，B3的需求为20≤b3≤60，A1不可达B4，B4的需求为30，求目标函数最小值。表4-66习题4.10运价表B1B2B3B4供给量A1497-70A2653220A38591050解：先化为平衡表B11B12B2B31B32B4aiA144977M70A266533220A3885991050A4M0MM0M40bj302040204030180最优解：习题55.1（1）×，（2）×，（10）×，（3）－（9）√；5.2X=（5，2.75，3）TMaxf=26.755.3（1）X=（4，3）TMaxf=55（2）X=（2，1）TMaxf=13（3）X=（2，1，6）TMaxf=36（4）X=（2，3）TMaxf=345.4X=（0，0，1，1，1）TMaxf=6；5.5（1）甲做C，乙做B，丙做D，丁做A。最少完工时间为48。（2）Minf=215.6甲做C，乙做A，丙做B，丁做D。最少完工时间为15。5.7解：设=1或0，分别代表选择第Sj个井位或不选第Sj个井位。则：（1）；（2）；（3），所以该问题的数学模型为：5.8（1）（2）的初始效率矩阵如下：（1）任务人ABCDE甲2529314237乙3938262033丙3427284032丁2442362345D0000M（2）任务人ABCDE甲2529314237乙3938262033丙3427284032丁2442362345D2427262032采用匈牙利法求解后得：（1）甲－B，乙－D，丙－E，丁－A，C放弃，最少时间为105小时。（2）甲－B，乙－C和D，丙－E，丁－A，最少时间为131小时。5.9354500676800898100010109110012111012001312111300化极小354500676800898100010109110012111012001312111300之后用匈牙利法求解得，其余为0最大受益43。5.10设A、B、C、D设备分别生产产品的数量为、、、，习题66.1（1）满意解为区域(0,0),(4,0),(6,1),(2,3),(0,2)（2）满意解是线段GD上任意点，其中G点X＝(2,4)T,D点X＝(10/3,10/3)T6.2（1）满意解为其余变量为0。偏差向量（2）满意解为其余变量为0。偏差向量6.3Minf=P1d1－+P2d2－+P3d3++P4（d4－+d4++d5－+d5++d6－+d6+）s.t.500x1+650x2+800x3+d1－–d1+=1.6×1046x1+8x2+10x3+d2－–d2+=200d2++d3－–d3+=24x1+d4－–d4+=12x2+d5－–d5+=10x3+d6－–d6+=6xj≥0（j=1,2,3）dl－,dl+≥0（l=1,2,3,…,6）6.4（1）（3）（6）（7）（8）（9）（10）√（2）（4）（5）×6.5解：minZ=P1d2－+P2d1－s.t.10x1+16x2+d1－=20011x1+3x2≥25100x1+50x2+d2－–d2+=1900x1,x2≥0,dl－,dl+≥0（l=1,2）6.6解：1）建模为2）单纯形求解：Cj00P2P1P3P10P3CBXBB-1bX1X2d1－d1+d2－d2+d3－d3+P2d1－31*01-10000P3d2－201001-1000d3－41100001-1P1000-10-100P2100-10000P301000-10-1X13101-10000d2－201001-100d3－101*-11001-1P1000-10000P200-100-100P30100000-1X13101-10000d2－1001-11-1-11X2101-11001-1P1000-10-100P200-100000P3001-100-10得满意解偏差向量3）讨论权数对满意解的影响Cj00P2P1W1P3P10W2P3CBXBB-1bX1X2d1－d1+d2－d2+d3－d3+0X13101-10000W1P3d2－1001-11-1-11*0X2101-11001-1P1000-10-100P200-100000P300W1-W10-W1-W1W1-W2Cj00P2P1W1P3P10W2P3CBXBB-1bX1X2d1－d1+d2－d2+d3－d3+0X13101-10000W2P3d3+1001-11-1-110X2201001-101P1000-10000P200-100-100P300W2-W2W2-W1-W2-W20W1≤W2时，满意解不变；W1>W2时，满意解改变；6.7（a）设x1,x2为分配给A、B县的救护车数，其目标规划模型为：minZ=P1d1++P2d2++P3d3+s.t.20x1+20x2+d1－–d1+=40040–3x1+d2－–d2+=550–4x2+d3－–d3+=5x1,x2≥0,dl－,dl+≥0（l=1,2,3）解得x1=,x2=整数解为x1=12,x2=8（b）解得x1=,x2=整数解为x1=12,x2=126.8满意解：（1,0）,（6,10）6.9设x1,x2为每月生产录音机和电视机的台数，其目标规划模型为：minZ=P1d3++P2d4－+P3（4d1－+d2－）+P4d6++P5d5－+P6（4d1++d2+）s.t.2x1+x2+d1－–d1+=120x1+3x2+d2－–d2+=15050x1+30x2+d3－–d3+=4600x1+d4－–d4+=50x2+d5－–d5+=80d1++d6－–d6+=20x1,x2≥0,dl－,dl+≥0（l=1,2,…,6）解得每月生产录音机50台，电视机40台，利润8000元。6.10解：Minf=P1d5－+P2(d7－+d8－+d9－)+P3d13++P4d6－+P5（3d10++2d11+）+P6（d12－+d12+）s.t.x11+x12+x13+d1－=3000x21+x22+x23+d2－=4000x11+x21+d3－=2000x12+x22+d4－=1500x13+x23+d5－=5000x21+d6－–d6+=1000x11+x21+d7－–d7+=2000×75％=1500x12+x22+d8－–d8+=1500×75％=1125x13+x23+d9－–d9+=5000×75％=3750x13–d10+=0x21–d11+=03x11–4x12+3x21–4x22+d12－–d12+=010x11+4x12+12x13+8x21+10x22+3x23–d13+=0xij≥0（i=1,2；j=1,2,3,4,）dl－,dl+≥0（l=1,2,3,…,13）

习题77.1（5）（6）（8）多阶段决策过程×7.2该题用逆序法求得的结果如右图所示。从A到G的总运费最小的路线有两条，分别是：A→B→E→G,A→C→F→G总运费为120。7.3（1）该线性规划最优解：目标函数最优值18（2）最优解为：目标函数最优值497.4（1）该线性规划最优解：目标函数最优值64（2）设s3=x3,s3+x2=s2，s2+x1=s1=C则有x3=s3，0≤x2≤s2，0≤x1≤s1=C用逆推法，从后向前依次有k＝3，及最优解x3*=s3k＝2，由故为极大值点。所以及最优解x2*=s2k=1时，，由，得故已知知x1+x2+x3=C，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下，由s2=s1－x1*=2C/3，由s3=s2－x2*=C/3，最优解为：7.5（1）分三阶段，逆序法求解K=3时K=2时K=1时最优解：（2）设s3=x3,s3+x2=s2，s2+x1=s1=C则有x3=s3，0≤x2≤s2，0≤x1≤s1=C用逆推法，从后向前依次有k＝3，及最优解x3*=s3k＝2，由=4>0,故x2=为极小值点。因而有k＝1时，由知得到最优解7.6解：设k为阶段数k=1，2，3uk为第k个阶段可提供生产的原料总吨数，xk为第k个阶段可提供生产A产品的原料吨数则第k阶段的收益为g(xk)+h(uk－xk)=0.6xk+0.4(uk－xk)=0.4uk+0.2xk状态转移方程为uk+1=axk+b(uk－xk)=0.2xk+0.5(uk－xk)=0.5uk－0.3xk因为三年末剩9吨，所以u4=9=0.5u3－0.3x3所以x3=1.67u3－30第k阶段至n阶段采用最优方案的总收益为k=3时，k=2时，uk投产A产品的原料吨数投产B产品的原料吨数u1=100x1=0u1－x1=100u2=50x2=0u2－x2=50u3=25x3=11.75u3－x3=13.25k=1时，7.7解：可将k个工厂的投资看成第k个阶段，k=1,2,3，该问题可化为动态规划中的一个最短路问题如下图所示。Sk表示第k个阶段可用于分配的资金数。最优路线为S1=3→S2=0→S3=0→S4=0最优值为107.8最优策略是机龄为1的旧设备继续使用到第5年末，总利润最大为42。7.9最优策略为第1,2,3个组件分别并联2个、1个、3个，才能使仪器的可靠性达到最高，为0.504。7.10解：建立数学模型：逆序法:k=1,2,3代回最优解:若只串联的7.11解：将问题按工厂分个阶段，甲、乙、丙三个工厂分别编号为1、2、3。Sk表示为分配给第k个工厂到第n个工厂的设备台数。xk表示为分配给第k个工厂的设备台数。由Sk+1=Sk-xk为分配给第k+1个工厂至第n个工厂的设备台数。Pk(xk)表示xk台设备分到第k个工厂所得的盈利值。fk(Sk)表示Sk台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。因而可以写出递推关系式为：下面从最后一个阶段开始向前递推计算。当k=3时，设将S3台设备（S3=0,1,2,3,4,5）全部分配给工厂丙时，则最大盈利值为，其中x3=S3=0,1,2,3,4,5。因为此时只有一个工厂，有多少设备就全部分配给丙工厂，故它的盈利值就是该段的最大盈利值，其数值计算如下表所示。x3S3P3(x3)f3(S3)x3*012345000014412662311113412124512125当k=2时，把台设备分配给工厂乙和工厂丙时，则对每个值，有一种最优的分配方案，使最大盈利值为：其中，x2=0,1,2,3,4,5。因为给工厂乙x2台，其盈利为P2(x2)，余下的S2-x2台就给工厂丙，则它的盈利最大值为f3(S2-x2)。现在要选择x2的值，使P2(x2)+f3(S2-x2)取最大值。其数值计算如下表所示。x2S2P2(x2)+f3(S2-x2)f2(S2)01234500+00010+45+005120+65+410+010230+115+610+410+014240+125+1110+611+411+0161,250+125+1210+1111+611+411+0212当k=1时，设把S1（这里只有S1=5的情况）设备分配给甲、乙、丙三个工厂时，则最大盈利值为其中，x1=0,1,2,3,4,5。因为给甲工厂x1台其盈利为P1(x1)，剩下的5-x1台分给乙和丙两个工厂，则它的盈利最大值为f2(5-x1)。现在要选择x1值，使P1(x1)+f2(5-x1)取最大值，它就是所求的总盈利最大值，其数值计算如下表所示。x1S1P1(x1)+f2(5-x1)f1(5)x1*01234550+213+167+149+1012+513+0210,2然后按计算表格的顺序反推算，可知最优分配方案有两个：（一）由于x1*=0，根据S2=S1-x1*=5-0=5，查表知，x2*=2；由S3=S2-x2*=5-2=3，故x3*=S3=3，即得到甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。（二）由于x1*=2，根据S2=S1-x1*=5-2=3，查表知，x2*=2；由S3=S2-x2*=3-2=1，故x3*=S3=1，即得到甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。以上两个分配方案所得到的盈利均为21万元。7.12解：只建模不求解（1）根据给3个车间分别供给能源，决策分为三个阶段（2）状态变量：第阶段可分配的能源（3）决策变量：第阶段分配的能源（4）状态转移方程：（5）阶段指标函数：分配能源为单位时收益（6）最优指标函数：（7）递推公式和边界条件：

习题88.1（1）不能，7+6+5+4+3+2=27≠2q不满足定理1图中所有点次的和是边数的2倍。（2）不能，奇点5,3,1奇点的个数是3。（3）可以（4）不能，若存在某个简单图，将次为1的节点去掉，余下由6个节点次为5,5,5,4,3,2，而3个次为5的节点中的每一个都与其余5个节点相邻，所以其余3个节点的次至少是3而不是2。8.2最小修建费用为215.图8-1图8-28.3(2)如图8-28.4解：用6个点表示6门课，如果有一人要考两门课，就表示这两门课间连一条线，如图8-3(a)所示，在求其补图如图7-3(b)所示。图8-3(a)图8-3(b)图8.3(b)中每条边的两个端点对应的课程可在同一天考，具体日程如表7-3上午下午第一天AE第二天CB第三天DF8.58.6最大流13，最小割集{(1,2),(1,3),(1,4)}8.7解：1、一个店建eq\o\ac(○,2)或eq\o\ac(○,3)村。2、(第s列与第k列中同行取小，在各行小中取大)则两店建eq\o\ac(○,1)，eq\o\ac(○,4)村。1234A=06045120100017517560140010024021015004004103703953、的第一行乘以eq\o\ac(○,1)村的人数，表示学校建于各村时eq\o\ac(○,1)村的学生走的总距离数，以此类推如下：即应建粮仓于eq\o\ac(○,3)村4、则建两校为eq\o\ac(○,1)eq\o\ac(○,4)村或eq\o\ac(○,2)eq\o\ac(○,4)村。8.8（（5.5）（4.4）（3.2）（5.4）（3.3）（3.2）（2.2）（2.2）（4.4）（3.3）（5.4）（）（）（5.5）（4.2）（3.2）（5.2）（3.3）（3.0）（2.2）（2.2）（4.2）（3.3）（5.4）（）（）（）（）（）（）（）（）（）（5.5）（4.1）（3.2）（5.2）（3.3）（3.0）（2.1）（2.2）（4.2）（3.3）（5.3）（）（）2（）（）（）最大流为11，最小割={（4、t）,（5、t）（2、6）（3、6）}或{(s、1)，(s、2)，(3、6)}最小割值118.9最大流14，最小割集{(vs,v2),(vs,v4),(v1,v4),(v1,v3)}。

习题99.1解：计划期一年，已知即最优策略为每隔一个月进货1次，全年进货12次，每次进货82吨，总费用为504123元。9.2解：已知，最优策略为半个月进货1次，每次进货5000公升，总费用为20009.3解：铣加工连续生产意为不允许缺货，已知；；，9.4解：计划期为一个月，，，即工厂每隔20天组织一次生产，产量为67件，最大存储量为37件，最大缺货量为30件。9.5依题意取一年为时间单位，且知：取为最优订购量，9.6解：由题意可知：；所以，根据（8-36）式，则，查表8-6可知，最佳订货量为1200块。9.7解：计算临界值求的最小整数值使下式成立因为所以9.8解：令查正态分表，可知使成立的，习题1010.1解（1）略；（2）略；（3）10.2解（1）略；（2）略。10.3解（1）正定；（2）不定；（3）负定。10.4解略。10.5解（1）为鞍点；（2）和均为鞍点；（3）在上为全局最小点；在上为全局最大点。10.6解（1）严格凸；（2）非凸非凹；（3）非凸非凹；（4）严格凹；（5）凹。10.7解在上为严格凸；在上为凸；在E2内任何区域上都非凹。10.8证明略。10.9解（1）为严格全部最小点；（2）为严格全部最小点；（3）为严格全部最小点；（4）为严格局部极大点；为严格局部极小点。10.10解（1）不是；（2）是；（3）是；（4）是；（5）不是；（6）不是。10.11解（1）；（2）。10.12解由可得，故精确解为函数求值次数，最终区间为，近似极小点为，近似极小值为。10.13解（1）；（2）。10.14解，计算结果见表10-1。表10-1迭代次数k0123由，，，可知相邻两步的搜索方向正交。10.15解求的极大点，即求的极小点。以为初始点，取精度，因为，所以，，，，于是，即为极小点，从而为的极大点。以为初始点，取精度，方法同上进行两次迭代，有：两次步长：，两次迭代结果：， 比较：相对于目标函数的等值线为椭圆的问题来说，椭圆的圆心即为最小值，负梯度方向指向圆心，但初值点与圆心在同一水平线上时，收敛速度很快，即尽量使搜索路径呈现较少的直角锯齿状。10.16解，从开始，，，于是，，，，故即为极小值点。10.17解（1）；（2）。习题1111.1解不是正则点。11.2解分析本题考查了K-T条件及其解法。（1）；（2）；（3）。（4）等同于写出目标函数和约束函数的梯度，，对第一个和第二个约束条件分别引入广义拉格朗日乘子，，得K-T点为，则有：=1\*GB3①令，，无解；=2\*GB3②令，，解之得，是K-T点，目标函数值；=3\*GB3③令，，解之得，是K-T点，；=4\*GB3④令，则，是K-T点，，但不是最优。此问题不为凸规划，故极小点1和5是最优点。（5）等同于，，引入广义拉格朗日乘子，，设K-T点为，则有：=1\*GB3①令，，无解；=2\*GB3②令，，则，，不是K-T点；=3\*GB3③令，，则，，不是K-T点；=4\*GB3④令，则，为K-T点，目标函数值。由于该非线性规划问题为凸规划，故是全局极小点。11.3解（1）；（2）；（3）。11.4解（1）；（2）分析二次规划和线性规划有着直接联系，解题时将二次规划转化为线性规划求解。解将上述二次规划改写为可知目标函数为严格凸函数，此外，，，，，，，，，，由于和小于零，故引入的人工变量和前面取负号，这样得到线性规划问题如下解此线性规划问题的，，，，，，，，11.5解（1）；（2）。11.6解构造惩罚函数，由得最优解为当时，当时，11.7解构造惩罚函数解得最优解为11.8解（1）；（2）。11.9解构造障碍函数由即当时，则或（舍去）故最优解为，。11.10解构造障碍函数得最优解为，。习题1212.1一个有两名服务员的排队系统，该系统最多容纳4名顾客，当系统稳态时，系统恰好有n名顾客的概率为：试求：（1）系统中的平均顾客数；（2）系统中的平均排队的顾客数；（3）某一时刻正在被服务顾客的平均数；（4）若顾客的平均到达率为2人/小时，求顾客在系统中的平均逗留时间；解：（1）人（2）人（3）人（4）由Little公式，，，12.2某车间的工具仓库只有一个管理员，平均每小时有4个工人来借工具，平均服务时间为6分钟，到达为流，服务为负指数分布，（1）没有人借工具的概率；（2）系统中借工具的平均人数；（3）排队等待借工具的平均人数；（4）工人在系统中平均花费的时间。解：M／M／1／∞系统，（1）（2）人（3）人（4）12.3某修理店只有一个修理工，顾客到达平均4人/小时；修理时间服从负指数分布平均需求6分钟，试求：（1）修理店空闲的概率；（2）店内至少有1个顾客的概率；（3）店内的顾客平均数；（4）每位顾客平均等待服务时间；（5）顾客在店内等待时间超过10分钟的概率。解：（1）（2）（3）（4）（5）12.4某修理店只有一个修理工人，来修理的顾客到达次数服从泊松分布，平均每小时3人，修理时间服从负指数分布，平均需10分钟,求（1）修理店空闲时间概率；（2）店内有4个顾客的概率；（3）店内至少有一个顾客的概率；（4）在店内顾客平均数；（5）等待服务的顾客平均数；（6）在店内平均逗留时间；（7）平均等待修理(服务)时间；（8）必须在店内消耗15分钟以上的概率。解：（1）店内空闲的时间：；（2）有4个顾客的概率：；（3）至少有一个顾客的概率：；（4）店内顾客的平均数：；（5）等待服务的顾客的平均数：（6）在店内平均逗留时间（7）平均等待修理的时间：；（8）一个顾客在店内逗留时间超过15分钟的概率。12.5某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson流，，服务时间服从负指数分布，平均需6分钟，由于场地限制，系统内最多不超过3名顾客，求：（1）系统内没有顾客的概率；（2）系统内顾客的平均数；（3）排队等待服务的顾客数；（4）顾客在系统中的平均花费时间；（5）顾客平均排队时间。解：单位时间为小时，；（1）系统内没有顾客的概率：；（2）系统内顾客的平均数：（人）；（3）排队等待服务的顾客数：（人）；（4）顾客在系统中的平均花费时间：（分钟）（5）顾客平均排队时间：（分钟）。12.6风景旅游区旅馆的建设既要满足旅客住宿的需求，又要考虑经济收益。某旅游公司拟在旅游风景区建造一个旅馆，根据已有旅馆的住宿情况对待建旅馆的规模大小进行设计。已知顾客的到达过程服从泊松流，平均每天入住50人。每天离开旅馆的顾客服从负指数分布，平均逗留时间为2天。在现有条件下，旅馆可建设的床位数量为40，60，80，100，120，140，160，180。试拟定一个最优的建设方案。解：由题意可知，旅馆建设方案主要考虑每天顾客满员的概率和旅馆客房占用率两项指标。旅馆规模过小，顾客因满员而离去，旅馆失去收益机会；旅馆规模过大，会导致入住率太低，造成资源浪费，旅馆的利益受损。在旅馆客房满员的情况下，若再有顾客到来将会被拒绝入住，是不允许排队等待的，因此，这是一个多服务台、即时制服务的排队问题，符合排队模型。系统可能的服务台（床位）个数为；平均每天到达的顾客数（到达率）为，平均每天离开的顾客数（服务率）为，平均服务强度为，在这里。由模型的运行指标，有：（1）平均每天客房空闲的概率为；（2）客房满员的概率为；（3）平均每天客房的占用数为。记，。利用Lingo中的函数求出系统满员（损失）的概率；单位时间内平均进入系统的顾客数（有效到达率）为；系统相对通过能力（Q）与绝对通过能力（A）分别为,。于是单位时间内系统服务台的利用率为。当床位数即服务台的个数为，可以得到每天床位平均占用数量和客房满员的概率，相应的Lingo程序如图12.7所示。图12-7习题12.6Lingo程序运行该程序得到结果如图12-25、图12-26所示，整理得表12-10。图12-15习题12.6Lingo程序运行结果（一）图12-16习题12.6Lingo程序运行结果（二）表SEQ表\*ARABIC12-10求解结果数据床位数满员的概率床位的占用数量4060801001201401601800.60630.41350.22950.07570.00570.000030039.367058.651377.050692.430099.9972100100表中是旅馆满员的概率，是每天床位的平均占用数量，即顾客入住的数量。对求解结果进行分析，该旅馆建设规模选择100个床位为最佳，因为100个床位基本可以满足旅客的需求，顾客满员的概率为0.0757，且平均每天床位空闲量最多为8个。若选择更少的床位，则满员的概率偏大；选择更多的床位，则床位的空闲率偏大。12.7某理发店准备招聘一名理发师，并拟设6把椅子供客人排队等待。当店里的椅子坐满时，后面的客人将不再进入理发店。根据以往理发店的统计数据，来理发店理发的客人服从平均到达率为的泊松分布，该理发店运营的成本平均为，顾客在店内逗留的平均成本为。若要求理发师的理发效率起码为每为一位顾客提供服务，其服务时间服从负指数分布。试求：使顾客在理发店中逗留费用与单位时间服务成本之和（）达到最小值的理发师理发效率；顾客到达理发店时无需等待就能理发的概率；该理发店的平均顾客数以及需要等待理发的平均顾客数；顾客在该理发店里的平均逗留时间和平均等待时间。解：首先，由题意可知，这是一个排队系统，其中，，，，。因为，所以，可建立上式的MATLAB函数文件MM1Exam.m：functionf=MM1Exam(x)f=30*x+25*((3/(x-1))-(8*3^8/(x^8-3^8));然后调用0.618法的MATLAB程序p618.m（见附录）进行计算。根据题意，选择的初始值为3（即理发师的理发效率为，也就是）结果如图12-27所示。图12-27习题12.7程序运行结果这表明，为使目标函数达到极小值，该理发师的理发效率应该提高到，即平均理发一人。此时，。顾客到达不用等待的概率为理发店的平均顾客数为需要等待的平均顾客数为顾客在理发店的平均逗留时间为平均等待时间为12.8在上题中，考虑如下问题。由于理发店对顾客的最大限制数是，故理发店中若已有个顾客，则后来的顾客将被拒绝，于是，表示理发店中有个顾客的概率，则表示顾客能够接受服务的概率，而表示在单位时间实际进入理发店的平均顾客数，在稳定情况下，它也等于单位时间内实际服务完成的平均顾客数。假设该理发店每服务一人能得到元收入，则单位时间收入的数学期望为元，服务成本为，于是该服务机构的纯利润为，其中。假设顾客到理发店理发平均每人需支付15元，或者说理发店平均理发一人收入为15元，其他条件不变，试求使得上式达到极大值时的服务率。解：根据题意，建立MATLAB函数文件：functionf=MM2Exam(x)f=-(3*15*x*((x^7-3^7)/(x^8-3^8))-30*x);end注意到：由于使用的是极小化程序p618.m求解问题，所以函数文件中函数是原式的相反函数。运行结果如图12-28所示。图12-28习题12.8程序运行结果计算结果表明，极大化得到最有服务率，此时最优利润为50.6381元，这意味着理发店是亏损的。若将收费调整到平均（即），并重新计算，得到functionf=MM3Exam(x)f=-(3*34*x*((x^7-3^7)/(x^8-3^8))-30*x);end运行程序，结果如图12-29所示。图12-29习题12.8调整收费后程序运行结果此时利润几乎为零，不亏损也不盈利。若继续调高收费，则将会开始有盈利。但