清华版《运筹学》(第三版)课后习题详解、...

1绪论1、运筹学的内涵答：本书将运筹学定义为：“通过构建、求解数学模型，规划、优化有限资源的合理利用，为科学决策提供量化依据的系统知识体系。”2、运筹学的工作过程答：解释、修正求解构造模型现实系统模型现实结论模型结论图1-1运筹学的工作过程（1）提出和形成问题。即要弄清问题的目标、可能的约束、可控变量、有关的参数以及搜索有关信息资料。（2）建立模型。即要把问题中的决策变量、参数和目标、约束之间的关系用一定的模型表示出来。（3）求解模型。根据模型的性质，选择相应的求解方法，求得昀优或者满意解，解的精度要求可由决策者提出。（4）解的检验和转译。首先检查求解过程是否有误，然后再检查解是否反映客观实际。如果所得之解不能较好地反映实际问题，必须返回第（1）步修改模型，重新求解；如果所得之解能较好地反映实际问题，也必须仔细将模型结论转译成现实结论。（5）解的实施。实施过程必须考虑解的应用范围及对各主要因素的敏感程度，向决策者讲清楚用法，以及在实施中可能产生的问题和修改的方法。3、数学模型及其三要素答：数学模型可以简单的描述为：用字母、数字和运算符来精确地反映变量之间相互关系的式子或式子组。数学模型由决策变量、约束条件和目标函数三个要素构成。决策变量即问题中所求的未知的量，约束条件是决策所面临的限制条件，目标函数则是衡量决策效益的数量指标。2线性规划1、试述线性规划数学模型的组成部分及其特性答：线性规划数学模型由决策变量、约束条件和目标函数三个部分组成。线性规划数学模型特征：（1）用一组决策变量表示某一方案，这组决策变量均为非负的连续变量；（2）存在一定数量（m）的约束条件，这些约束条件可以用关于决策变量的一组线性等式或者不等式来加以表示；（3）有一个可以用决策变量加以表示的目标函数，而该函数是一个线性函数。2、一家餐厅24小时全天候营业，在各时间段中所需要的服务员数量分别为：2：00~6：003人6：00~10：009人10：00~14：0012人14：00~18：005人18：00~22：0018人22：00~2：004人设服务员在各时间段的开始时点上上班并连续工作八小时，问该餐厅至少配备多少服务员，才能满足各个时间段对人员的需要。试构造此问题的数学模型。解：用决策变量,,1x2x3x,4x,5x,6x分别表示2：00~6：00，6：00~10：00，10：00~14：00，14：00~18：00，18：00~22：00，22：00~2：00时间段的服务员人数。其数学模型可以表述为：12345min6Zxxxxxx=+++++16122334455612345639125184,,,,,0xxxxxxxxxxxxxxxxxx+=+=+=+=+=+=≥3、现要截取2.9米、2.1米和1.5米的元钢各100根，已知原材料的长度是7.4米，问应如何下料，才能使所消耗的原材料昀省。试构造此问题的数学模型。解：圆钢的截取有不同的方案，用θ表示每种切割方案的剩余材料。其切割方案如下所示：2.92.11.5θ1'1110.92'2000.13'1200.34'10305'0130.86'0041.47'0220.28'0301.1目标函数为求所剩余的材料昀少，即1234567min0.90.10.300.81.40.21.18Zxxxxxxx=+++++++x1234135781245671234567821002231003342100,,,,,,,0xxxxxxxxxxxxxxxxxxxxxxx+++=++++=+++++=≥1234135781245671234567821002231003342100,,,,,,,0xxxxxxxxxxxxxxxxxxxxxxx+++=++++=+++++=≥4、某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C三种原料的含量要求、各种原料的单位成本、各种原料每月的限制用量、三种牌号糖果的单位加工费及售价如表1所示。问该厂每月生产这三种牌号糖果各多少千克，才能使该厂获利昀大？试建立这个问题的线性规划模型。4、某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C三种原料的含量要求、各种原料的单位成本、各种原料每月的限制用量、三种牌号糖果的单位加工费及售价如表1所示。问该厂每月生产这三种牌号糖果各多少千克，才能使该厂获利昀大？试建立这个问题的线性规划模型。表1表1甲甲乙乙丙丙原料成本原料成本限制用量限制用量A60%以上15%以上2.002000B1.502500C20%以下60%以下50%以下1.001200加工费0.500.400.30售价3.402.852.25解：以表示甲产品中的A成分，表示甲产品中的B成分，表示甲产品中的C成分，依此类推。据表2-16，有：A甲B甲C甲35A=甲甲，15C=甲甲，320A=乙乙，35C=乙乙，12A=丙丙．．．．．．①其中：，，．．．．．．②A+=BC甲+甲甲甲A+=BC乙+乙乙乙A+=BC丙+丙丙丙把②逐个代入①并整理得：203A−+=BC甲+甲甲40A−+=BC甲-甲甲，，0A+=BC17-乙+乙乙3203A+=BC-乙-乙乙，0A+=BC-丙-丙丙原材料的限制，有以下不等式成立：AA2000A+=甲+乙丙，，BBB2500+=甲+乙丙CCC1200+=甲+乙丙在约束条件中共有9个变量，为方便计算，分别用,．．．1x2x9x表示，即令=，1xA甲2x=，B甲3x=，C甲4x=，A乙5x=，B乙6x=C乙，7x=A丙，8x=丙，B9x=C丙由此约束条件可以表示为：1231234564567891472583691234567892-xxx03-x-x4x017-xxx032-x-xx03-x-xx0x+xx2000x+xx2500x+xx1200x,x,x,x,x,x,x,x,x0++=+=++=+=+=+=+=+==我们的目的是使利润昀大，即产品售价减加工费再减去原材料的价格为昀大。目标函数为123456780.91.41.90.450.951.450.050.450.95MaxZxxxxxxxxx=+++++−++95、某厂在今后4个月内需租用仓库存放物资，已知各个月所需的仓库面积如表2所示。租金与租借合同的长短有关，租用的时间越长，享受的优惠越大，具体数字见表3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。因此该厂可根据需要在任何一个月初办理租借合同，且每次办理时，可签一份，也可同时签若干份租用面积和租借期限不同的合同，总的目标是使所付的租借费用昀小。试根据上述要求，建立一个线性规划的数学模型。表2月份1234所需面积（100m2）15102012表3合同租借期限1个月2个月3个月4个月单位（100m2）租金（元）2800450060007300解：设ijx（i＝1,2,3,4;j=1,2．．．4-i+1）为第i个月初签订的租借期限为j个月的合同租借面积（单位：100m）；r表示第i个月所需的面积（j表示每100仓库面积租借期为j个月的租借费）；则线性规划模型为：2i2m44111ijijijMinZCX−+===∑∑4111(1,2,3,4)0(1,2,3,4;1,2...41)kiijkijkiijXrkXiji−+==−+=====−+∑∑6、某农场有100公顷土地及25万元资金可用于发展生产。农场劳动力情况为秋冬季4500人日，春夏季6000人日，如劳动力本身过剩可外出打工，春夏季收入为20元／人日，秋冬季12元／人日。该农场种植三种作物：大豆、玉米和小麦，并饲养奶牛和鸡。种作物不需要专门投资，而饲养动物时每头奶牛投资8000元，每只鸡投资2元。养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入3000元／每头奶牛。养鸡不占土地，需人工为每只鸡秋冬季0.3人日，春夏季0.1人日，年净收入为每只8元。农场现有鸡舍允许昀多养5000只鸡，牛栏允许昀多养50头奶牛，三种作物每年需要的人工及收入情况如表4所示。试决定该农场的经营方案，使年净收入昀大。表4大豆玉米麦子每公顷秋冬季所需人日数203510每公顷春夏季所需人日数507540年净收入（元/公顷）11001500900解：设,,1x2x3x分别代表大豆、玉米、麦子的种植数（公顷）；4x,5x分别代表奶牛和鸡的饲养数；6x,7x分别代表秋冬季和春夏季多余的劳动力（人．日数）则有12345611001500900300081220MaxZxxxxxxx=++++++7124451234561234574512345671.5100(80002250000(2035101000.34500(507540500.14500(50(5000x,x,x,x,x,x,x0xxxxxxxxxxxxxxxxxxx++=+=+++++=+++++====土地限制)资金限制）劳动力限制）劳动力限制）牛栏限制）（鸡栏限制）7、用图解法求解下列线性规划问题（1）（2）212maxxxz+=2123maxxxz+=123421≤+xx4221≤+−xx8221≤+xx142321≤+xx8421≤−xx321≤−xx0,21≥xx0,21≥xx（3）（4）2132maxxxz+=21maxxxz+=221≤−xx021≥−xx4321≤+−xx3321−≤−xx0,21≥xx0,21≥xx解：（1）（2）23484此题有无穷多昀有解，其中一个是*(4,1)TX=*9(,1)4Q84*9(,1)4TX=此题有唯一昀有解，234（3）（4）8、考虑线性规划：43212maxxxxxz++−=1x−+++=52x3x4x1x++=22x5x2+++=61x2x3x6x0,,61≥xxΛ（1）通过观察写出初始的基可行解并构造初始单纯形表；（2）在保持2x和3x为零的情况下，给出非基变量1x增加一个单位时的可行解，并指出目标函数的净增量是多少?（3）在模型约束条件的限制下，1x的昀大增量是多少？（4）在1x有其昀大增量时，给出一个新的基可行解。解：（1）因存在初始可行基()456,,Txxx，故可令,,1x2x3x全为0,则可得初始可行解为，Z＝5。(0,0,0,5,2,6)T初始单纯行表为：cj2-11100CBXBx1x2x3x4x5x6b10x4x5-11110011001052243找不到可行域，此题为无可行解244此题为无界解0x62110016σj3-20000z=0(2)非基变量,2x3x仍然取零，由0变为1,即＝1,＝0,1x1x2x3x=0,代入约束条件得一个可行解X=(。其目标函数值为Z＝81,0,0,6,1,4)T因此，随着增加1个单位目标函数值的净增量为△Z＝8-5=3.1x（3）因为决策变量全非负所以由约束条件①知增加可以引起,1x2x3x,4x增加，即条件①对无约束；由约束条件②知增加可引起,1x1x2x5x减少，由非负约束知昀大增量为2；同理可得约束条件③的昀大增量为3，综合得的昀大增量为2。1x1x1x（4）＝2，非基变量=0,1x2x3x＝0,代入约束条件得基可行解X=(，目标函数值为Z＝11。2,0,0,7,2,2)T9、将线性规划模型转化为标准形式432132maxxxxxZ+++=1024321≤+++xxxx85324321−=−+−xxxx12464321≥+−+xxxx0,,321≥xxx，无约束4x解：（1）令4x＝5x－6x并代入模型，这里5x=0,6x=0；（2）第二个约束条件方程两侧同乘“-1”；（3）第一个约束条件引入松弛变量7x，第三个约束条件引入8x作为松弛变量。（4）目标函数同乘“-1”，即可实现昀少化。1235min236Zxxxxx=−−−−+1235671236123568123456782123586441,,,,,,,0xxxxxxx