《运筹学》课堂作业及答案.doc

第一部分 绪 论第二部分 线性规划与单纯形法1 判断下列说法是否正确：(a)图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；(b)线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；(c)线性规划问题的每一个基解对应可行域的一个顶点；(d)如线性规划问题存在可行域，则可行域一定包含坐标的原点；(e)对取值无约束的变量xi，通常令其中，在用单纯形法求得的最优解中有可能同时出现(f)用单纯形法求解标准型的线性规划问题时，与对应的变量都可以被选作换入变量；(g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；(h)单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，将使目标函数值得到最快的增长；(i)一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；(k)若x1，x2分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中1，2可以为任意正的实数；(1)线性规划用两阶段法求解时，第一阶段的目标函数通常写为Xai为人工变量)，但也可写为，只要所有ki均为大于零的常数；(m)对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为个；(n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解；(o)线性规划问题的可行解如为最优解，则该可行解一定是基可行解；(p)若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解；(q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优；(r)将线性规划约束条件的“”号及“”号变换成“”号，将使问题的最优目标函数值得到改善；(s)线性规划目标函数中系数最大的变量在最优解中总是取正的值；(t)一个企业利用3种资源生产4种产品，建立线性规划模型求解得到的最优解中，最多只含有3种产品的组合；(u)若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解；(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。【答案】1.1(a)(b)(f)(g)(i)(J)(1)(q)(t)正确，(c)(d)(e）(h)(k)(m)(n)(o)(p)（r)(s)(U)(v)不正确。2用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。【答案】(a)唯一最优解，z*=3，x1=12，x2=0；(b)无可行解；(c)有可行解，但max z无界；(d)无穷多最优解，z*=66。表1.6x1x2x3x4X5x3 dx4 2x5 341a 2a1531OOO10OO1cj一zjC1C2OOO【答案】1.25(a)d0，C10，C20，而c10且d43a2；(d)C10，3a20，a10；(f)x5为人工变量，且c10，C2o。3 某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000 1、重型炸弹48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2 km，带轻型炸弹时每升汽油可飞行3 km。又知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来回路程汽油消耗(空载时每升汽油可飞行4 km)外，起飞和降落每次各消耗100 1。有关数据如表117所示。表117摧毁可能性要害部位离机场距离km每枚重型弹每枚轻型弹12344504805406000.100.200.150.250.O80.160.120.20为了使摧毁敌方军事门标的可能性最大，应如何确定飞机轰炸的方案。要求建立这个问题的线性规划模型。【答案】用i=1，2分别代表重型和轻型炸弹，j=1，2，3，4分别代表四个要害部位，xij为投到第J部位的i种型号炸弹的数量，则问题的数学模型为式中目标函数非线性，但rain z等价于max 1g(1z)，因此目标函数可改写为4 用单纯形法求解下列线性规划(1)【解】单纯形表：C(j)34100R. H. S.RatioBasisC(i)X1X2X3X4X5X402311011/3X501220133/2C(j)-Z(j)341000X242/311/31/301/31/2X50-1/304/3-2/317/3MC(j)-Z(j)1/30-1/3-4/30-4/3X1313/21/21/201/2X5001/23/2-1/215/2C(j)-Z(j)0-1/2-1/2-3/20-3/2最优解：X=（1/2，0，0，0，5/2）；最优值Z3/2 (2) 【解】单纯形表：C(j)21-35000R. H. S.RatioBasisC(i)X1X2X3X4X5X6X7X50153-710030MX603-1110101010X702-6-14001205C(j)-Z(j)21-35000X509/2-11/25/40107/465MX605/21/25/4001-1/4510X451/2-3/2-1/41001/45MC(j)-Z(j)-1/217/2-7/4000-5/4X50320150111-1120MX21515/2002-1/21010X45807/2103-1/220MC(j)-Z(j)-430-2300-173因为730并且ai74000时，x1=0，x2=0，x3=b10；zmax=6/103 当0b4000时，x1=0，x2=6，x3=0；Zmax=4b2(d)将.271，z2，X3的取值划分为三个阶段，状态变量s1=4，s2=42x1，S3=s2一x2，边界条件f4(s4)=0由此【解析】（a）将问题分为三个阶段，当k=3， 01234560000111128823272734646445125125562162166当k=2， 01234560000100002010113082081402716302715064542440641601251288132501282当k=1， 012345660641087216001082得到最优解为：x1=2，x2=1，x3=3；maxz =108.(b)由于第2个约束中x2的系数为负号，故将问题改写为用S1h,S2h表示k阶段初的状态变量，则本题的动态规划基本方程为边界条件为采用逆序算法，当k=2时有当k=1时推导得X1*8=9.6，x2*=0.2，z*=702.92(c)(d)将.271，z2，X3的取值划分为三个阶段，状态变量s1=4，s2=42x1，S3=s2一x2，边界条件f4(s4)=0由此已知某指派问题的有关数据(每人完成各项工作的时间)如表71所示，试对此问题用动态规划方法求解。要求：(a)列出动态规划的基本方程(b)用逆推解法求解。表71人工作1234123415192619182318212122162324181917【答案】(a)任务的指派分4个阶段完成，用状态变量sk表第k阶段初未指派的工作集合，决策变量为uki状态转移本问题的逆推关系式为(b)本题有两组最优解：。某T厂购进100台机器，准备生产P1，P2两种产品。若生产产品P1，每台机器每年可收入45万元，损坏率为65；若生产产品P2，每台机器每年收入为35万元，但损坏率只有35；估计三年后将有新的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多?【答案】最优决策为：第一年将100台机器全部生产产品P2，第二年把余下的机器继续生产产品P2，第三年把余下的所有机器全部生产产品P1.三年的总收人为7676.25万元。【解析】设阶段序数k表示年度；状态变量为第k年度初拥有的完好机器数量；决策变量为第k年度中分配给生产P1产品的机器数量，于是为该年度中分配给生产P2产品的机器数量；状态转移方程为：，k=1,2,3设为第k年度的产量，则因而有逆推关系式为：当k=3时，有当k=2时，有当k=1时，有最后把代入，逆推得到最优决策为：第一年将100台机器全部生产产品P2，第二年把余下的机器继续生产产品P2，第三年把余下的所有机器全部生产产品P1.三年的总收人为7676.25万元。某工厂的交货任务如表7-5所示。表中数字为月底的交货量。该厂的生产能力为每月400件，该厂仓库的存货能力为300件，已知每100件货物的生产费用为10000元，在进行生产的月份，工厂要支出经常费用4000元，仓库保管费用为每百件货物每月1000元。假定开始时及6月底交货后无存货。试问应在每个月各生产多少件物品，才能既满足交货任务又使总费用最小?表75月份123456交货量百件125321【答案】各月份生产货物数量的最优决策为：第八部分 图与网络分析10名研究生参加6门课程的考试。由于选修内容不同，考试门数也不一样。表8-3给出了每个研究生应参加考试的课程(打的)。表8-3规定考试在三天内结束，每天上下午各安排一门。研究生提出希望每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门，课程B只能安排在下午考。试列出一张满足各方面要求的考试日程表。【答案】把同一个研究生参加的考试课程用边连接，得图8-6。由图看出，课程A只能同E排在一天，B同C安排一天，D同F在一天。再根据题意要求，满足各方面要求的考试日程表只能是表8-4。 表8-4 图8分别用破圈法和避圈法求图8-7中各图的最小支撑树(最小部分树)。 图8-7【答案】(a)最小支撑树树枝总长12；(b)最小支撑树树枝总长15；(c)最小支撑树树枝总长12； (d)最小支撑树树枝总长18。 【解析】破圈法就是任取一个圈，从圈中去掉一条权最大的边，对余下的图重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。避圈法是开始选一条最小权的边，以后每一步，总从与已选边不构成圈的那些未选边中，选择一条权最小的。第九部分 网络计划对由图91及图9-2给出的PERT网络图，计算各作业的最早开始、最早结束，最迟开始及最迟结束时间，计算各工序的总时差，找出关键路线。解：图91总用时为12，关键路线为一一一一；计算过程详见表9-1(1)表9-1(1)工作工作时间t（i,j）最早开工时间tES（i,j）最早完工时间tEF（i,j）最迟开工时间tLS（i,j）最迟完工时间tLF（i,j）总时差R（i,j）单时差r（i,j）关键工作2022420404040020235301233411044440024679302247952123563034747001679103057127120033671041235683027910123325781035图92总用时为20，关键路线为一一一。计算过程详见表9-2(1)表9-2(1)工作工作时间t（i,j）最早开工时间tES（i,j）最早完工时间tEF（i,j）最迟开工时间tLS（i,j）最迟完工时间tLF（i,j）总时差R（i,j）单时差r（i,j）关键工作3032420404151080808003365822841251310088880028101113323811131652281014166378158150011213151630712191320114131716203351520152000表9-3给出了一个汽车库及引道的施工计划工序代号工序名称工序时间d紧前工序abcdefg清理场地，准备施工备料车库地面施工预制墙及房顶的桁架车库混凝土地面保养立墙架立房顶桁架1086162444一一a，bbcd，ef续表工序代号工序名称工序时间d紧前工序ZJk1mn装窗及边墙装门装天花板油漆引道混凝土施工引道混凝土保养清理场地，交工验收10412168244ffgh，i，jfzk,m要求回答：(a)该项工程从施工开始到全部结束的最短周期是多长?(b)如果引道混凝土施工工期拖延10d，对整个工期有何影响?(c)若装天花板的施工时间从12d缩短到8d，对整个工期进度有何影响?(d)为保证工期不拖延，装门这道工序最晚应从哪一天开始?(e)如果要求全部工程必须在75d内结束，是否应采取措施及应采取什么措施?解：先画出网络图，见图9A一5，图中双线为根据计算结果画出的关键路线。计算过程见表9A一3由表中计算知：(a)从施工开始到全部结束最短周期为80 d；(b)混凝土施工拖延10d，对整个工期无影响；(C)天花板施工从12d缩短到8d，整个工期可缩短4d；(d)装门这道工序最迟应在开工后的第56d开始；(e)应采取措施，并从关键路线上的作业着手缩短工期。第十部分 排队论来到一个汽车加油站加油的汽车服从普阿松分布，平均每5 min到达1辆。设加油站对每辆汽车的加油时间为10 min，问在这段时间内发生以下情况的概率：a)没有一辆汽车到达；(b)有两辆汽车到达；(c)不少于5辆汽车到达。【答案】(a)0.135(b)0.270(C)0.0527某加油站有一台油泵。来加油的汽车按普阿松分布到达，平均每小时20辆，但当加油站中已有n辆汽车时，新来汽车中将有一部分不愿等待而离去，离去概率为n4(n=0，1，2，3，4)。油泵给一辆汽车加油所需要的时间为具有均值3 rain的负指数分布。(a)画出此排队系统的速率图；(b)导出其平衡方程式；(c)求出加油站中汽车数的稳态概率分布；(d)求那些在加油站的汽车的平均逗留时间。【答案】(a)如图10A一2速率图和表10A一1所示。（b）因为所以u=20(辆h)0=20(辆h)，1=15(辆h)，2=10(辆h)，3=5(辆h)第十一部分 存贮论1 依据不允许缺货、生产时间很短模型的计算，A公司确定对一种零件的订货批量定为Q*=80。但由于银行贷款利率及仓库租金等费用的增加，每件的存储费将从原来占成本的22上升到占成本的27。求在这个新条件下的经济订货批量。解：由题意设零件的生产成本为K，则C1=22%K，=27%K2 某单位每年需零件A 5000件，这种零件可以从市场购买到，故订货提前期为零。设该零件的单价为5元件，年存储费为单价的20，不允许缺货。若每组织采购一次的费用为49元，又一次购买10002499件时，给予3折扣，购买2500件以上时，给予5折扣。试确定一个使采购加存储费用之和为最小的采购批量。解：先分别计算享受不同折扣时的经济订货批量，K1=5元件 K2=5(1-3%)=4.85元件 K3=5(1-5%)=4.75