清华大学《运筹学教程》胡运权主编课后习题答案(第一章).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学教程,School of Management,page,*,*,1,第一章习题解答,1.1,用图解法求解下列线性规划问题。并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。,sdadsd,2,sdadsd,3,sdadsd,4,1.2,将下述线性规划问题化成标准形式。,sdadsd,5,sdadsd,6,sdadsd,7,1.3,对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。,sdadsd,8,sdadsd,x,1,x,2,x,3,x,4,x,5,x,6,是否基可行解,Z,(x1,x2,x3),0,61/3,-7/6,0,0,0,否,(x1,x2,x4),0,10,0,-7,0,0,否,(x1,x2,x5),0,3,0,0,7/2,0,是,3,(x1,x2,x6),7/4,-4,0,0,0,21/4,否,(x1,x3,x4),0,0,-5/2,8,0,0,否,(x1,x3,x5),0,0,1.5,0,8,0,是,3,(x1,x3,x6),1,0,-0.5,0,0,3,否,(x1,x4,x5),0,0,0,3,5,0,是,0,(x1,x4,x6),5/4,0,0,-2,0,15/4,否,(x1,x5,x6),3/4,0,0,0,2,9/4,是,9/4,(x2,x3,x6),0,16/3,-7/6,0,0,0,否,(x2,x4,x6),0,10,0,-7,0,0,否,(x2,x5,x6),0,3,0,0,7/2,0,是,3,(x3,x4,x6),0,0,-5/2,8,0,0,否,(x3,x5,x6),0,0,3/2,0,8,0,是,3,(x4,x5,x6),0,0,0,3,5,0,是,0,所有基可行解中最优解为,X=(0,3,0,0,3.5,0),T,和,X=(0,0,1.5,0,8,0),T,9,sdadsd,10,x,1,x,2,x,3,x,4,是否基可行解,Z,(x1,x2),-4,11/2,0,0,否,(x1,x3),2/5,0,11/5,0,是,43/5,(x1,x4),-1/3,0,0,11/6,否,(x2,x3),0,1/2,2,0,是,5,(x2,x4),0,-1/2,0,2,否,(x3,x4),0,0,1,1,是,5,所有基可行解中最优解为,X=(0,1/2,2,0),T,和,X=(0,0,1,1),T,sdadsd,11,1.4,分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。,sdadsd,10,5,0,0,0,9,3,4,1,0,0,8,5,2,0,1,10,5,0,0,0,21/5,0,14/5,1,-3/5,10,8/5,1,2/5,0,1/5,0,1,0,-2,5,3/2,0,1,5/14,-3/14,10,1,1,0,-1/7,2/7,0,0,-5/14,-25/14,0,点,A1,点,A2,点,所以最优解为,X*=(1,3/2,0,0),T,12,sdadsd,13,sdadsd,14,sdadsd,15,sdadsd,l.5,上题,(1),中，若目标函数变为,max Z=cx,1,+dx,2,，讨论,c,d,的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。,最优值,1)c0,d0,O,点,OA3,线段,A3,点,2)c=0,d0,OA1,线段,A3,点,3)c0,d0,A1,点,A1,点,A3,点,A2A3,线段,A2,点,A1A2,线段,A1,点,16,sdadsd,17,式中，,1,c,1,3,4,c,2,6,-1,a,11,3,2,a,12,5,8,b,1,12,2,a,21,5,4,a,22,6,10,b,2,14,试确定目标函数最优值的下界和上界。,l.6,考虑下述线性规划问题：,sdadsd,18,目标函数最优值的上界为：,21,解：上界对应的模型如下（,c,b,取大，,a,取小）,sdadsd,19,目标函数最优值（下界）为：,6.4,解：下界对应的模型如下（,c,b,取小，,a,取大）,sdadsd,20,l.7,分别用单纯形法中的大,M,法和两阶段法求解下列线性规划问题，并指出属哪,类解。,sdadsd,21,sdadsd,22,sdadsd,23,sdadsd,24,sdadsd,25,sdadsd,26,sdadsd,27,sdadsd,28,sdadsd,见下表。,29,sdadsd,30,sdadsd,31,sdadsd,方法一：大,M,法,引入人工变量,x6,和,x7,线性规划问题变为：,32,sdadsd,0,0,-M,4M-1,7M-4,0,1,0,2,1,4,0,0,0,-1,3,4,6,-M,1,0,0,1,3,3,-M,-M,0,0,-1,-4,0,1,0,1,3/2,4,0,-7M/3+4/3,0,-M,5M/3+1/3,0,-1/3,1,0,5/3,0,3,0,-4/3,0,-1,5/3,0,2,-M,1/3,0,0,1/3,1,1,-4,1,0,6/5,9/5,0,0,3,-M,33,sdadsd,-M+8/5,0,1/5,0,0,1,1,1,0,0,1,0,-4/5,0,-3/5,1,0,6/5,-1,3/5,0,1/5,0,1,3/5,-4,-M,0,0,-1,-4,-1/5,-3/5,-1,3,1,-M-1/5,-M+7/5,-1/5,0,0,0,1,1,1,0,0,1,0,-1/5,3/5,0,1,0,5/9,-1,2/5,-1/5,0,0,1,2/5,-4,0,-1,-M,0,-M,由于上表中所有检验数都小于等于零,(,且非基变量检验数都小于,0),，因此已经得到唯一最优解，最优解为：,34,sdadsd,方法二：两阶段法,第一阶段：,35,sdadsd,0,0,-1,4,7,0,1,0,2,1,4,0,0,0,-1,3,4,6,-1,1,0,0,1,3,3,-1,-1,0,0,0,0,0,1,0,1,3/2,4,0,-7/3,0,-1,5/3,0,-1/3,1,0,5/3,0,3,0,-4/3,0,-1,5/3,0,2,-1,1/3,0,0,1/3,1,1,0,1,0,6/5,9/5,0,0,3,-1,36,sdadsd,-1,0,0,0,0,1,1,1,0,0,1,0,-4/5,0,-3/5,1,0,6/5,0,3/5,0,1/5,0,1,3/5,0,-M,0,0,0,0,-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,，转入第二阶段。,37,sdadsd,0,1/5,0,0,1,1,0,0,1,0,0,-3/5,1,0,6/5,-1,0,1/5,0,1,3/5,-4,0,0,-1,-4,3,-1/5,0,0,0,1,1,0,0,1,0,3/5,0,1,0,5/9,-1,-1/5,0,0,1,2/5,-4,由于上表中所有检验数都小于等于零,(,且非基变量检验数都小于,0),，因此已经得到唯一最优解，最优解为：,1,38,sdadsd,39,sdadsd,40,sdadsd,41,sdadsd,42,sdadsd,43,1.8,已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求括弧中未知数,a,l,值。,项 目,X,1,X,2,X,3,X,4,X,5,X,4,6,(b),(c),(d),1,0,X,5,1,-1,3,(e),0,1,C,j,Z,j,a,-1,2,0,0,X,1,(f),(g),2,-1,1/2,0,X,5,4,(h),(i),1,1/2,1,C,j,Z,j,0,-7,(j),(k),(,l,),b=,2,c=,4,d=-,2,g=,1,h=,0,f=3,i=5,e=2,l=0,sdadsd,-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,44,sdadsd,45,1.9,若,X,(1),、,X,(2),均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。,sdadsd,46,sdadsd,47,1.10,线性规划问题,max Z,CX,AX,b,，,X0,，设,X,0,为问题的最优解。若目标函数中用,C,*,代替,C,后，问题的最优解变为,X,*,，求证,(C,*,-C)(X,*,-X,0,)0,的可行解,一定是问题,的最优解，则,是问题,1,2,*,*,X*,X*,的可行解,一定是问题,的最优解，则,是问题,2,1,0,0,X,X,sdadsd,48,sdadsd,49,1.11,考虑线性规划问题,模型中,，,为参数，要求：,(1),组成两个新的约束,(i),(i)+(ii),，,(ii),(ii),一,2(i),，根据,(i),，,(ii),以,x,1,x,2,为基变量，列出初始单纯形表；,sdadsd,50,C,j,a,2,1,-4,C,B,x,B,b,x,1,x,2,x,3,x,4,a,x,1,3+3,0,1,1,-1,2,x,2,1-,1,0,-1,0,j,0,0,3-a,a-4,解,:,sdadsd,51,(2),在表中，假定,0,，则,为何值时，,x,1,x,2,为问题的最优基,变量,；,解：,如果,=0,，则当,3-a,0,且,a-4,0,时，即,3a 4,时，,x,1,x,2,为问题的最优基,变量,；,(3),在表中，假定,3,，则,为何值时，,x,1,x,2,为问题的最优基。,解：,如果,a=3,，则当,3+3,0,且,1-,0,时，即,-1 1,时，,x,1,x,2,为问题的最优基,变量。,sdadsd,52,1.12,线性规划问题,max Z,CX,，,AX,b,，,X0,，如,X,*,是该问题的最优解，又,0,为某一常数，分别讨论下列情况时最优解的变化。,(1),目标函数变为,max Z,CX,；,(2),目标函数变为,max Z,(C+,)X,；,(3),目标函数变为,max Z,C/,*,X,，约束条件变为,AX,b,。,解,:,(,1),最优解不变,;,(2)C,为常数时最优解不变，否则可能发生变化。,(3),最优解变为,:,X*,。,sdadsd,53,1.13,某饲养场饲养动物出售，设每头动物每天至少需,700g,蛋白质、,30g,矿物质、,100mg,维生素。现有五种饲料可供选用，各种饲料每,kg,营养成分含量及单价如,下,表所示。,饲料,蛋白质,(g),矿物质,(g),维生素,(mg),价格（元,/kg,）,1,3,1,0.5,0.2,2,2,0.5,1.0,0.7,3,1,0.2,0.2,0.4,4,6,2,2,0.3,5,18,0.5,0.8,0.8,sdadsd,54,要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。,(,建立这个问题的线性规划模型，不求解,),sdadsd,55,1.14,某医院护士值班班次、每班工作时间及各班所需护士数如,下页,表,格,所示。,班次,工作时间,所需护士数（人）,1,6:00,10:00,60,2,10:00,14:00,70,3,14:00,18:00,60,4,18:00,22:00,50,5,22:00,2:00,20,6,2:00,6:00,30,sdadsd,56,(1),若护士上班后连续工作,8h,，该医院最少需多少名护士，以满足轮班需要；,解：,sdadsd,57,(2),若除,22,：,00,上班的护士连续工作,8h,外,(,取消第,6,班,),，其他班次护士由医院排定上,1-4,班的其中两个班，则该医院又需多少名护士满足轮班需要。,解,:,sdadsd,58,1.15,艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量见后面的表格。现有,3,种货物待运，已知有关数据列于后面的表格。,又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过,15,，前、后舱之间不超过,10,。问该货轮应装载,A,，,B,，,C,各多少件运费收入才最大,?,试建立这个问题的线性规划模型。,sdadsd,59,商品,数量,（件）,每件体积,(m,3,/,件,),每件重量,(t/,件,),运价,（元,/,件）,A,600,10,8,1000,B,1000,5,6,700,C,800,7,5,600,项目,前舱,中舱,后舱,最大允许载重量（,t,）,2000,3000,1500,容积（,m,3,）,4000,5400,1500,解：设,x,ij,表示第,i,种商品在第,j,舱的数量。,sdadsd,60,sdadsd,61,1-16,时代服装公司生产,款新的时装，据预测今后,6,个月的需求量如下表所示。每件时装用工,2h,和,10,元原材料费，售价,40,元。该公司,1,月初有,4,名工人，每人每月可工作,200h,，月薪,2000,元。该公司可于任何,个月初新雇工人，但每雇,1,人需,次性额外支出,1500,元，也可辞退工人，但每辞退,1,人需补偿,1000,元。如当月生产数超过需求，可留到后面月份销售，但需付库存费每件每月,5,元。当供不应求时，短缺数不需补上。试帮助该公司决策，如何使,6,个月的总利润达到最大。,月份,1,2,3,4,5,6,需求,500,600,300,400,500,800,sdadsd,62,解：设,x,i,表示第,i,个月的工人数量，,y,i,表示第,i,个月生产产品的数量。,p,i,表示第,i,个月初新雇工人数量，,d,i,表示第,i,个月初解雇工人数量。,pp,i,表示第,i,个月月末的库存量，,dd,i,表示第,i,个月的短缺量。,sdadsd,63,sdadsd,64,1.17,童心玩具厂下一年度的现金流,(,万元,),如,下,表所示，表中负号表示该月现金流出大于流人，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷款额，从,1,月底起每月还息,1,，于,12,月归还本金和最后一次利息；二是得到短期贷款，每月初获得，于月底归还，月息,1.5,。当该厂有多余现金时，可短期存款，月初存人，月末取出，月息,0.4,。问该厂应如何进行存贷款操作，既能弥补可能出现的负现金流，又可使年末现金总量为最大,?,月份,1,2,3,4,5,6,7,8,9,10,11,12,现金流,-12,-10,-8,-10,-4,5,-7,-2,15,12,-7,45,sdadsd,65,解：设,x,表示第,1,个月初长期借款数额，,y,i,表示第,i,个月初短期借款数额，,z,i,表示第,i,个月初短期存款数额。,sdadsd,1.18,解：设,z,表示,2002,年末筹得的资金数，,x,i,表示购买第,i,种债劵的金额，,y,i,表示第,i,年初短期存款数额。,66,sdadsd,