《清华大学运筹学教程胡运权主编课后习题答案.pptx》由会员分享，可在线阅读，更多相关《清华大学运筹学教程胡运权主编课后习题答案.pptx（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第1页/共66页2第2页/共66页3 1.2 1.2 将下述线性规划问题化成标准形式。第3页/共66页4第4页/共66页5第5页/共66页6 1.3 1.3 对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。第6页/共66页7第7页/共66页x1x2x3x4x5x6是否基可行解Z(x1,x2,x3)061/3-7/6000否(x1,x2,x4)0100-700否(x1,x2,x5)03007/20是3(x1,x2,x6)7/4-400021/4否(x1,x3,x4)00-5/2800否(x1,x3,x5)001.5080是3(x1,x3,x6)10-0.5003否(x1,x4
2、,x5)000350是0(x1,x4,x6)5/400-2015/4否(x1,x5,x6)3/400029/4是9/4(x2,x3,x6)016/3-7/6000否(x2,x4,x6)0100-700否(x2,x5,x6)03007/20是3(x3,x4,x6)00-5/2800否(x3,x5,x6)003/2080是3(x4,x5,x6)000350是0所有基可行解中最优解为X=(0,3,0,0,3.5,0)T和X=(0,0,1.5,0,8,0)T第8页/共66页9x1x2x3x4是否基可行解Z(x1,x2)-411/200否(x1,x3)2/5011/50是43/5(x1,x4)-1/30
3、011/6否(x2,x3)01/220是5(x2,x4)0-1/202否(x3,x4)0011是5所有基可行解中最优解为X=(0,1/2,2,0)T和X=(0,0,1,1)T第9页/共66页10 1.4 分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。第10页/共66页1050009341008520110500021/5014/51-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/140点A1点A2点所以最优解为X*=(1,3/2,0,0)T第11页/共66页12第
4、12页/共66页第13页/共66页第14页/共66页 l.5 上题(1)中，若目标函数变为max Z=cx1+dx2，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。最优值1)c0d0O点OA3线段A3点2)c=0d0OA1线段A3点3)c0d0A1点A1点A3点A2A3线段A2点A1A2线段A1点第15页/共66页16 式中，1c13,4c26,-1a113,2a125,8b112,2a215,4a226,10b214,试确定目标函数最优值的下界和上界。l.6 考虑下述线性规划问题：第16页/共66页17 目标函数最优值的上界为：2121 解：上界对应的模型如下（c,
5、b取大，a取小）第17页/共66页18 目标函数最优值（下界）为：6.46.4 解：下界对应的模型如下（c,b取小，a取大）第18页/共66页19 l.7 l.7 分别用单纯形法中的大M M法和两阶段法求解下列线性规划问题，并指出属哪类解。第19页/共66页第20页/共66页第21页/共66页第22页/共66页第23页/共66页第24页/共66页25第25页/共66页第26页/共66页第27页/共66页见下表。第28页/共66页第29页/共66页30第30页/共66页方法一：大M法引入人工变量x6和x7,线性规划问题变为：第31页/共66页00-M4M-17M-4010214000-1346-
6、M100133-M-M00-1-401013/240-7M/3+4/30-M5M/3+1/30-1/3105/3030-4/30-15/302-M1/3001/311-4106/59/5003-M第32页/共66页-M+8/501/5001110010-4/50-3/5106/5-13/501/5013/5-4-M00-1-4-1/5-3/5-131-M-1/5-M+7/5-1/50001110010-1/53/50105/9-12/5-1/50012/5-40-1-M0-M 由于上表中所有检验数都小于等于零(且非基变量检验数都小于0)，因此已经得到唯一最优解，最优解为：第33页/共66页方法
7、二：两阶段法第一阶段：第34页/共66页00-147010214000-1346-1100133-1-1000001013/240-7/30-15/30-1/3105/3030-4/30-15/302-11/3001/3110106/59/5003-1第35页/共66页-100001110010-4/50-3/5106/503/501/5013/50-M0000-1/5-3/5-1-1-M该模型最优解为X=（3/5，6/5，0，1，0，0）T，其基变量不含人工变量，说明原问题的一个基可行解为X=（3/5，6/5，0，1）T，转入第二阶段。第36页/共66页01/5001100100-3/510
8、6/5-101/5013/5-400-1-43-1/50001100103/50105/9-1-1/50012/5-4 由于上表中所有检验数都小于等于零(且非基变量检验数都小于0)，因此已经得到唯一最优解，最优解为：1第37页/共66页38第38页/共66页第39页/共66页第40页/共66页第41页/共66页42 1.8 1.8 已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求括弧中未知数a a l值。项目X1X2X3X4X5X46(b)(c)(d)10X51-13(e)01CjZja-1200X1(f)(g)2-11/20X54(h)(i)11/21CjZj0-7(j)
9、(k)(l)b=2,c=4,d=-2,g=1,h=0,f=3,i=5,e=2,l=0,第42页/共66页 -7=-1-(c/b)*a -7=-1-2a a=3 j=2-(d/b)*a j=2+3=5 k=-(1/b)*a k=-3/2 第43页/共66页44 1.9 若X(1)、X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。第44页/共66页第45页/共66页46 1.10 1.10 线性规划问题max Zmax ZCX,AXCX,AXb b，X0X0，设X X0 0为问题的最优解。若目标函数中用C C*代替C C后，问题的最优解变为X X*，求证(C(C*
10、-C)(X-C)(X*-X-X0 0)0)0的可行解的可行解一定是问题一定是问题的最优解，则的最优解，则是问题是问题12*X*X*的可行解的可行解一定是问题一定是问题的最优解，则的最优解，则是问题是问题2100XX第46页/共66页第47页/共66页48 1.11 1.11 考虑线性规划问题 模型中，为参数，要求：(1)(1)组成两个新的约束(i)(i)(i)+(ii)(i)+(ii)，(ii)(ii)(ii)(ii)一2(i)2(i)，根据(i)(i)，(ii)(ii)以x x1 1,x,x2 2为基变量，列出初始单纯形表；第48页/共66页49Cja21-4CBxBbx1x2x3x4ax1
11、3+3011-12x21-10-10j003-aa-4解:第49页/共66页50 (2)(2)在表中，假定0 0，则为何值时，x x1 1,x x2 2为问题的最优基变量；解：如果=0，则当3-a0且 a-4 0时，即3a 4时，x x1 1,x,x2 2为问题的最优基变量；(3)(3)在表中，假定3 3，则为何值时，x x1 1,x x2 2为问题的最优基。解：如果a=3，则当3+3 0 且1-0时，即-1 1时，x x1 1,x,x2 2为问题的最优基变量。第50页/共66页51 1.12 1.12 线性规划问题max Zmax ZCXCX，AXAXb b，X0X0，如X X*是该问题的最
12、优解，又0为某一常数，分别讨论下列情况时最优解的变化。(1)(1)目标函数变为max Zmax ZCXCX；(2)(2)目标函数变为max Zmax Z(C+(C+)X)X；(3)(3)目标函数变为max max Z ZC/C/*X X，约束条件变为AXAXb b。解:(1)最优解不变;(2)C为常数时最优解不变，否则可能发生变化。(3)最优解变为:X*。第51页/共66页52 1.13 1.13 某饲养场饲养动物出售，设每头动物每天至少需700g700g蛋白质、30g30g矿物质、100mg100mg维生素。现有五种饲料可供选用，各种饲料每kgkg营养成分含量及单价如下表所示。饲料饲料 蛋白
13、质蛋白质(g)(g)矿物质矿物质(g)(g)维生素维生素(mg)(mg)价格（元价格（元/kg/kg）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8第52页/共66页53 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。(建立这个问题的线性规划模型，不求解)第53页/共66页54 1.14 1.14 某医院护士值班班次、每班工作时间及各班所需护士数如下页表格所示。班次班次工作时间工作时间所需护士数所需护士数（人）（人）1 16:00 6:00 10:0010:0060602 210:0010:00 14:0014:00707
14、03 314:0014:00 18:0018:0060604 418:0018:00 22:0022:0050505 522:0022:00 2:002:0020206 62:00 2:00 6:006:003030第54页/共66页55 (1)(1)若护士上班后连续工作8h8h，该医院最少需多少名护士，以满足轮班需要；解：第55页/共66页56 (2)(2)若除2222：0000上班的护士连续工作8h8h外(取消第6 6班)，其他班次护士由医院排定上1-41-4班的其中两个班，则该医院又需多少名护士满足轮班需要。解:第56页/共66页57 1.15 1.15 艘货轮分前、中、后三个舱位，它们
15、的容积与最大允许载重量见后面的表格。现有3 3种货物待运，已知有关数据列于后面的表格。又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过1515，前、后舱之间不超过1010。问该货轮应装载A A，B B，C C各多少件运费收入才最大?试建立这个问题的线性规划模型。第57页/共66页58商品商品数量数量（件）（件）每件体积每件体积(m(m3 3/件件)每件重量每件重量(t/(t/件件)运价运价（元（元/件）件）A A60060010108 810001000B B100010005 56 6700700C C800
16、8007 75 5600600项目项目前舱前舱中舱中舱后舱后舱最大允许载重量最大允许载重量（t t）200020003000300015001500容积（容积（m m3 3）400040005400540015001500解：设x xijij表示第i i种商品在第j j舱的数量。第58页/共66页59第59页/共66页60 1-16 时代服装公司生产款新的时装，据预测今后6个月的需求量如下表所示。每件时装用工2h和10元原材料费，售价40元。该公司1月初有4名工人，每人每月可工作200h，月薪2000元。该公司可于任何个月初新雇工人，但每雇1人需次性额外支出1500元，也可辞退工人，但每辞退1
17、人需补偿1000元。如当月生产数超过需求，可留到后面月份销售，但需付库存费每件每月5元。当供不应求时，短缺数不需补上。试帮助该公司决策，如何使6个月的总利润达到最大。月月份份123456需需求求500 600 300 400 500 800第60页/共66页61解：设x xi i表示第i i个月的工人数量，y yi i表示第i i个月生产产品的数量。p pi i表示第i i个月初新雇工人数量，d di i表示第i i个月初解雇工人数量。ppppi i表示第i i个月月末的库存量，ddddi i表示第i i个月的短缺量。第61页/共66页第62页/共66页63 1.17 1.17 童心玩具厂下一
18、年度的现金流(万元)如下表所示，表中负号表示该月现金流出大于流人，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷款额，从1 1月底起每月还息1 1，于1212月归还本金和最后一次利息；二是得到短期贷款，每月初获得，于月底归还，月息1.51.5。当该厂有多余现金时，可短期存款，月初存人，月末取出，月息0.40.4。问该厂应如何进行存贷款操作，既能弥补可能出现的负现金流，又可使年末现金总量为最大?月份月份123456789101112现金流现金流-12-10-8-10-45-7-2 1512-745第63页/共66页64解：设x x表示第1 1个月初长期借款数额，y yi i表示第i i个月初短期借款数额，z zi i表示第i i个月初短期存款数额。第64页/共66页 1.181.18解：设z z表示20022002年末筹得的资金数，x xi i表示购买第i i种债劵的金额，y yi i表示第i i年初短期存款数额。第65页/共66页66感谢您的观看！第66页/共66页