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

1第一章习题解答第一章习题解答 1.1 用图解法求解下列线性规划问题并用图解法求解下列线性规划问题并指出问题具有惟一最优解、无穷多最优解、无指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解界解还是无可行解 234 1.2 1.2 将下述线性规划问题化成标准形式将下述线性规划问题化成标准形式 567 1.3 1.3 对下述线性规划问题找出所有基解，对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解指出哪些是基可行解，并确定最优解 8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,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10x1x2x3x4是否基可行解Z(x1,x2)-411/200否(x1,x3)2/5011/50是43/5(x1,x4)-1/30011/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11 1.4 分分别别用用图图解解法法和和单单纯纯形形法法求求解解下下述述线线性性规规划划问问题题，，并并对对照照指指出出单单纯纯形形表表中中的的各各基基可行解对应图解法中可行域的哪一顶点。

可行解对应图解法中可行域的哪一顶点 1050009341008[5]20110500021/50[14/5]1-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13 l.5 上上题题(1)中中，，若若目目标标函函数数变变为为max Z = cx1 + dx2，，讨讨论论c,d的的值值如如何何变变化化，，使使该该问问题题可可行行域域的的每每个个顶顶点点依依次次使使目目标标函函数数达达到最优 最优值1)c<0d<0d=0d>0O点OA3线段A3点2)c=0d<0d>0OA1线段A3点3)c>0d<0d=0d>0A1点A1点A3点A2A3线段A2点A1A2线段A1点17 式中，式中，1≤≤c1≤≤3, 4≤≤c2≤≤6, -1≤≤a11≤≤3, 2≤≤a12≤≤5, 8≤≤b1≤≤12, 2≤≤a21≤≤5, 4≤≤a22≤≤6, 10≤≤b2≤≤14,试确定目标函数最优值的下界和上试确定目标函数最优值的下界和上界。

界 l.6 考虑下述线性规划问题：考虑下述线性规划问题： 18 目标函数最优值的上界为：目标函数最优值的上界为：2121 解：上界对应的模型如下（解：上界对应的模型如下（c,b取大，取大，a取小）取小） 19 目标函数最优值（下界）为：目标函数最优值（下界）为：6.46.4 解：下界对应的模型如下（解：下界对应的模型如下（ c,b取小，取小，a取大）取大）20 l.7 l.7 分别用单纯形法中的大分别用单纯形法中的大M M法和两阶法和两阶段法求解下列线性规划问题，并指出属哪段法求解下列线性规划问题，并指出属哪—类类解 26见下表31方法一：大方法一：大M法法引入人工变量引入人工变量x6和和x7,线性规划问题变为：线性规划问题变为：00-M4M-17M-4010214000-1346-M1001[3]3-M-M00-1-401013/240-7M/3+4/30-M5M/3+1/30-1/3105/3030-4/30-1[5/3]02-M1/3001/311-4106/59/5003-M-M+8/501/50011[1]0010-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)，因此已经得到唯一最优解，最优解为：，因此已经得到唯一最优解，最优解为：方法二：两阶段法方法二：两阶段法第一阶段：第一阶段：00-147010214000-1346-11001[3]3-1-1000001013/240-7/30-15/30-1/3105/3030-4/30-1[5/3]02-11/3001/3110106/59/5003-1-1000011[1]0010-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，转入第二阶段。

转入第二阶段01/5001[1]00100-3/5106/5-101/5013/5-400-1-43-1/50001100103/50105/9-1-1/50012/5-4 由于上表中所有检验数都小于等于零由于上表中所有检验数都小于等于零(且非基变量检验数都且非基变量检验数都小于小于0)，因此已经得到唯一最优解，最优解为：，因此已经得到唯一最优解，最优解为：13943 1.8 1.8 已知某线性规划问题的初始单纯形已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求括表和用单纯形法迭代后得到下面表格，试求括弧中未知数弧中未知数a a∼ ∼l值 项   目X1X2X3X4X5X46(b)(c)(d)10X51-13(e)01Cj－Zja-1200X1(f)(g)2-11/20X54(h)(i)1  1/21Cj－Zj0-7(j)(k)(l) b=2, c=4, d= -2, g=1, h=0, f=3, i=5, e=2, l=0, -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 45 1.9 若若X(1)、、X(2)均为某线性规划问题的均为某线性规划问题的最优解，证明在这两点连线上的所有点也是最优解，证明在这两点连线上的所有点也是该问题的最优解。

该问题的最优解 47 1.10 1.10 线线性性规规划划问题问题max Zmax Z＝＝CX,AXCX,AX＝＝b b，，X≥0X≥0，，设设X X0 0为问题为问题的最的最优优解若目标标函数中用函数中用C C* *代替代替C C后，后，问题问题的最的最优优解解变为变为X X* *，求，求证证(C(C* *-C)(X-C)(X* *-X-X0 0)≥0)≥0的可行解的可行解一定是问题一定是问题的最优解，则的最优解，则是问题是问题12**X*X*的可行解的可行解一定是问题一定是问题的最优解，则的最优解，则是问题是问题2100XX49 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为为基基变变量量，，列列出出初始初始单纯单纯形表；形表；50Cj→a21-4CBxBbx1x2x3x4ax13+3011-12x21- 10-10j003-aa-4解解:51 (2)(2)在表中，假定在表中，假定β＝＝0 0，，则则α为为何何值时值时，，x x1 1, x, x2 2为为问题问题的最的最优优基基变量变量；； 解：解： 如果如果=0，则当3-a≥0且 a-4 ≥0时，即3≤a ≤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为问题为问题的最的最优优基基变量52 1.12 1.12 线线性性规规划划问题问题max Zmax Z＝＝CXCX，，AXAX＝＝b b，，X≥0X≥0，如，如X X* *是是该问题该问题的最的最优优解，又解，又λ>0为为某一某一常数，分常数，分别讨论别讨论下列情况下列情况时时最最优优解的解的变变化 (1)(1)目目标标函数函数变为变为max Zmax Z＝＝λCXCX；； (2)(2)目目标标函数函数变为变为max Zmax Z＝＝(C+(C+λ)X)X；； (3)(3)目目标标函函数数变变为为max max Z Z＝＝C/C/λ*X X，，约约束束条条件件变为变为AXAX＝＝λb b 解解:(1)最优解不变最优解不变; (2)C为常数时最优解不变，否则可能发生变化为常数时最优解不变，否则可能发生变化 (3)最优解变为最优解变为: λX* 。

53 1.13 1.13 某某饲饲养养场饲场饲养养动动物出售，物出售，设设每每头头动动物每天至少需物每天至少需700g700g蛋白蛋白质质、、30g30g矿矿物物质质、、100mg100mg维维生素现现有五种有五种饲饲料可供料可供选选用，各种用，各种饲饲料每料每kgkg营营养成分含量及养成分含量及单单价如价如下下表所示饲料饲料 蛋白质蛋白质(g)(g)矿物质矿物质(g)(g)维生素维生素(mg)(mg)价格（元价格（元/kg/kg））1310.50.2220.51.00.7310.20.20.446220.35180.50.80.854 要要求求确确定定既既满满足足动动物物生生长长的的营营养养需需要要，，又又使使费费用用最最省省的的选选用用饲饲料料的的方方案案 (建建立立这这个个问题问题的的线线性性规规划模型，不求解划模型，不求解) )55 1.14 1.14 某医院某医院护护士士值值班班次、每班工作班班次、每班工作时间时间及各班所需及各班所需护护士数如士数如下页下页表表格格所示班次班次工作时间工作时间所需护士数所需护士数（人）（人）1 16:00 6:00  10:0010:0060602 210:0010:00 14:0014:0070703 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56 (1)(1)若若护护士上班后士上班后连续连续工作工作8h8h，，该该医院最医院最少需多少名少需多少名护护士，以士，以满满足足轮轮班需要；班需要； 解：解： 57 (2)(2)若除若除2222：：0000上班的上班的护护士士连续连续工作工作8h8h外外( (取消第取消第6 6班班) )，其他班次，其他班次护护士由医院排定上士由医院排定上1-41-4班的其中两个班，班的其中两个班，则该则该医院又需多少名医院又需多少名护护士士满满足足轮轮班需要。

班需要 解解:58 1.15 1.15 —艘货轮分前、中、后三个舱位，艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量见后面的表格它们的容积与最大允许载重量见后面的表格现有现有3 3种货物待运，已知有关数据列于后面的种货物待运，已知有关数据列于后面的表格 又又为为了了航航运运安安全全，，前前、、中中、、后后舱舱的的实实际际载载重重量量大大体体保保持持各各舱舱最最大大允允许许载载重重量量的的比比例例关关系系具具体体要要求求：：前前、、后后舱舱分分别别与与中中舱舱之之间间载载重重量量比比例例的的偏偏差差不不超超过过1515％％，，前前、、后后舱舱之之间间不不超超过过1010％％问问该该货货轮轮应应装装载载A A，，B B，，C C各各多多少少件件运运费费收收入才最大入才最大? ?试试建立建立这这个个问题问题的的线线性性规规划模型59商品商品数量数量（件）（件）每件体积每件体积(m(m3 3/ /件件) )每件重量每件重量(t/(t/件件) )运价运价（元（元/ /件）件）A A60060010108 810001000B B100010005 56 6700700C C8008007 75 5600600项目项目前舱前舱中舱中舱后舱后舱最大允许载重量最大允许载重量（（t t））200020003000300015001500容积（容积（m m3 3））400040005400540015001500解：设解：设x xijij表示第表示第i i种商品在第种商品在第j j舱的数量。

舱的数量6061 1-16 时代服装公司生产时代服装公司生产—款新的时装，款新的时装，据预测今后据预测今后6个月的需求量如下表所示每件个月的需求量如下表所示每件时装用工时装用工2h和和10元原材料费，售价元原材料费，售价40元该公司公司1月初有月初有4名工人，每人每月可工作名工人，每人每月可工作200h，月薪，月薪2000元该公司可于任何元该公司可于任何—个月初新雇个月初新雇工人，但每雇工人，但每雇1人需人需—次性额外支出次性额外支出1500元，元，也可辞退工人，但每辞退也可辞退工人，但每辞退1人需补偿人需补偿1000元如当月生产数超过需求，可留到后面月份销售，如当月生产数超过需求，可留到后面月份销售，但需付库存费每件每月但需付库存费每件每月5元当供不应求时，元当供不应求时，短缺数不需补上试帮助该公司决策，如何使短缺数不需补上试帮助该公司决策，如何使6个月的总利润达到最大个月的总利润达到最大 月月份份123456需需求求500 600 300 400 500 80062解：设解：设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个月个月的短缺量的短缺量64 1.17 1.17 童心玩具厂下一年度的童心玩具厂下一年度的现现金流金流( (万万元元) )如如下下表所示，表中表所示，表中负负号表示号表示该该月月现现金流出金流出大于流人，大于流人，为为此此该该厂需借款借款有两种方式：厂需借款借款有两种方式：一是于上一年末借一年期一是于上一年末借一年期贷贷款，一次得全部款，一次得全部贷贷款款额额，从，从1 1月底起每月月底起每月还还息息1 1％，于％，于1212月月归还归还本本金和最后一次利息；二是得到短期金和最后一次利息；二是得到短期贷贷款，每月款，每月初初获获得，于月底得，于月底归还归还，月息，月息1.51.5％当该该厂有厂有多余多余现现金金时时，可短期存款，月初存人，月末取，可短期存款，月初存人，月末取出，月息出，月息0.40.4％。

％问该问该厂厂应应如何如何进进行存行存贷贷款操款操作，既能弥作，既能弥补补可能出可能出现现的的负现负现金流，又可使年金流，又可使年末末现现金金总总量量为为最大最大? ?月份月份123456789101112现金流现金流-12-10-8 -10 -45-7-2 1512-74565解：设解：设x x表示第表示第1 1个月初长期借款数额，个月初长期借款数额，y yi i表示第表示第i i个月初个月初短期借款数额，短期借款数额，z zi i表示第表示第i i个月初短期存款数额个月初短期存款数额 1.181.18解：设解：设z z表示表示20022002年末筹得的资金数，年末筹得的资金数，x xi i表示购买第表示购买第i i种债种债劵的金额，劵的金额，y yi i表示第表示第i i年初短期存款数额年初短期存款数额。