《运筹学例题及答案.pptx》由会员分享，可在线阅读，更多相关《运筹学例题及答案.pptx（104页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1。用单纯形法解LP问题线性规划第1页/共104页cj6-2300cBxBbx1x2x3x4x50 x422-12100 x5410401 cj-zj6-23006x111-1/211/200 x5301/23-1/21 cj-zj01-3-30第2页/共104页6x1410401-2x26016-12 cj-zj00-9-2-2cj6-2300cBxBbx1x2x3x4x5达到最优解，且最优解唯一第3页/共104页2。用大。用大M或两阶段法解或两阶段法解LP问题问题第4页/共104页cj2-12000-M-M-McBxBbx1x2x3x4x5x6x7x8x9-Mx76111-100100-M
2、x82-2010-10010-Mx9002-100-1001Cj-zj2-M3M-1M+2-M-M-M000-Mx76103/2-101/210-1/2-Mx82-2010-10010-1x2001-1/200-1/2001/2Cj-zj2-M05/2M+3/2-M-M1/2M-1/200-3/2M+1/2第5页/共104页cj2-12000-M-M-McBxBbx1x2x3x4x5x6x7x8x9-Mx73400-13/21/21-3/2-1/22x32-201000010-1x21-1100-1/2-1/201/21Cj-zj5+4M00-M3/2M+3/21/2M-1/20-5/2M-3
3、/2-3/2M+1/22x13/4100-1/43/81/81/4-3/8-1/82x37/2001-1/2-1/41/41/21/4-1/4-1x27/4010-1/4-1/8-3/81/81/83/8Cj-zj0005/4-无界解第6页/共104页3，某厂在今后四个月内需租用仓库堆放物资。已知各月份需租用仓库面积见表，仓库租借费用随合同期不同而不同，期限越长折扣越大，具体数字见表。租借合同每个月月初都可办理，合同规定具体的租借面积和月数，因此该厂可根据需要，在任何一个月月初办理合同，每次办理可签一份或多份，总目标是总的租借费用最低，请建立数学模型并用软件给出结果。月份1234所需仓库面积（
4、100m2）15102012合同租借期限1个月2个月3个月4个月租借费用2800450060007300第7页/共104页解:设一月初签订合同期限为一个月，两个月，三个月，四个月的仓库面积分别为 ，二月初签订合同期限为一个月，两个月，三个月的仓库面积分别为 ，三月初签订合同期限为一个月，两个月的仓库面积分别为 ，四月初签订合同期限为一个月的仓库面积为 。则计算结果如下第8页/共104页第9页/共104页4，某厂生产I,II,III三种产品，都分别经过A,B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1，B2，B3三种设备可用于完成B工序。已知产品I可在A,B任何一种设备上加工；产品
5、II可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品III只能在A2和B2设备上加工。加工单位产品所需的工序时间及其它各项数据见表，试安排最优生成计划，使该厂获利最大。第10页/共104页设备 产品I II III设备有效设备有效台时台时设备加工费设备加工费（元（元/h）A15 10 60000.05A27 9 12100000.03B16 840000.06B24 1170000.11B3740000.05原料费（元原料费（元/件）件）售价（元售价（元/件）件）0.25 0.35 0.501.25 2.00 2.80第11页/共104页解：设第种产品中，分别在 上加工的
6、数量依次为 ，第种产品中分别在A1,B1和A2,B1 上加工的数量为 生产种产品数量为 。第12页/共104页第13页/共104页对偶理论第14页/共104页1.已知线性规划问题：要求：a)写出对偶问题，b)已知原问题最有解X*=(2,2,4,0),用互补松弛性求出对偶问题的最优解。第15页/共104页解：对偶问题：将原问题的最优解带入约束，发现第4个约束为严格不等式，所以，得y4*=0又因为，原问题最优解的前三个分量都大于0，所以，有如下三个等式成立。第16页/共104页解方程组得对偶问题的最优解为Y*=(4/5,3/5,1,0)第17页/共104页2。已知线性规划问题及最终单纯形表第18页
7、/共104页cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3 003x110/3 10-1/3 2/3000 x5300-11100 x62/300-2/3 1/301cjzj00-1/3-4/3 00表1第19页/共104页分析下列各种条件单独变化时，最优解将如何变化。（a）第1，2个约束条件的后端项分别由6变7，8变4；（b）目标函数变为 ;（c）增加一个变量 ，系数为（d）问题中变量 的系数变为（e）增加一个新的约束第20页/共104页解：a）将其加到表（1）的最终单纯形表的基变量b这一列数字上得表（2）第21页/共104页（表2）表（2）中原问题为非可行
8、解，故用对偶单纯形法继续计算得表（3）cj320000cBxBbx1x2x3x4x5x62x210/3 012/3-1/3 003x11/310-1/3 2/3000 x5-200-11100 x6-4/3 00-2/3 1/301cjzj00-1/3-4/3 00第22页/共104页（表3）cj320000cBxBbx1x2x3x4x5x62x220101/32/303x111001/3-1/3 00 x32001-1-100 x60000-1/3-2/3 1cjzj000-5/3-1/3 0即新解为第23页/共104页b)将cj的改变反应到最终单纯形表上,得表（4）cj250000cBxB
9、bx1x2x3x4x5x65x24/3012/3-1/3 002x110/3 10-1/3 2/3000 x5300-11100 x62/300-2/3 1/301cjzj00-8/3 1/300继续迭代,得表（5）第24页/共104页cj250000cBxBbx1x2x3x4x5x65x220100012x1210100-20 x5100101-30 x4200-2103cjzj00-200-1表5即新解为第25页/共104页c）将其加到最终单纯形表上得表（6）第26页/共104页cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3 003x110/3 10-1/
10、3 2/3000 x5300-11100 x62/300-2/3 1/301cjzj00-1/3-4/3 004x701421继续迭代,得表（7）表6第27页/共104页cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3 003x131001/20-1/20 x55/3001/31/21-24x71/300-1/3 1/601/2cjzj000-3/2 0-1/24x700010即新解为表7第28页/共104页d）将其加到最终单纯形表上得表（8）第29页/共104页cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3 003x110/3
11、 10-1/3 2/3000 x5300-11100 x62/300-2/3 1/301cjzj00-1/3-4/3 004X24/31/302/31/3表8因x2已变化为x/2，故用单纯形法算法将x/2替换出基变量中的x2，并在下一个表中不再保留x2，得表（9）第30页/共104页cj320000cBxBbx1X2x3x4x5x64X21011/2-1/4 003x1310-1/2 3/4000 x5300-11100 x6000-11/201cjzj00-1/2-5/4 00表9此时已经达到最优，新解为第31页/共104页e)此时将原来的最优解带入约束，发现满足，所以最优解不变。第32页/
12、共104页运输问题第33页/共104页1，试求下表给出的产销不平衡问题的最优解。B1B2B3B4产量A137645A224322A343856销量3322第34页/共104页解：用最小元素法求得初始方案如下B1B2B3B4B5A123A220A3132用位势法求检验数知找到闭回路，调整得第35页/共104页B1B2B3B4B5A132A220A3321又用位势法求检验数知找到闭回路，调整得第36页/共104页B1B2B3B4B5A1320A220A333又用位势法求检验数知所有的检验数都非负，达到最优z=32。第37页/共104页2，某市有三个面粉厂，他们供给三个面食加工厂所需的面粉。各面粉厂
13、的产量、面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价见下表。假定在第1，2，3面食加工厂制作单位面粉食品的利润分别为12元，16元，11元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）123面粉厂产量A310220C411830B811420食品厂需要量152520食品厂面粉厂第38页/共104页解：从题意很容易知道，总效益最大实际上是食品利润减去单位运价之后再求的总效益。再因为面粉的总产量为70，比食品厂的总需求量60多了10个单位，可以认为，多的10个单位最后还是会分配给13个食品厂，所以就需要增加一个虚拟的食品厂4。设xij第i个面粉厂
14、运到第j个食品厂的运量，i=1,2,3;j=1,2,3,4得下表：1234面粉厂产量A969920C853830B457720食品厂需要量15252010第39页/共104页为使用求解运输问题的表上作业法，用上表中的最大数减去其他各数，得下表1234面粉厂产量A030020C146130B542220食品厂需要量15252010使用表上作业法，得最优解.第40页/共104页整数规划第41页/共104页1，分配甲、乙、丙、丁四个人完成ABCDE五项任务，每个人完成各项任务的时间如表所示：ABCDE甲2529314237乙乙3938262 033丙丙3427284 032丁丁2442362345由
15、于任务多于人数，故考虑：（a）任务E必须完成，其他各项可任意选3项完成；（b）其中有一人完成2项，其他每人完成一项。分别确定最优方案，使完成任务总时间最少第42页/共104页解（a）增加一个虚拟的人，由题目要求，其对应的效率如下Z=105第43页/共104页解（b）增加一个虚拟的人，由题目要求，其对应的效率如下最优方案：甲B，乙C，D，丙E，丁A，Z=131第44页/共104页2，用割平面法求解第45页/共104页cj1100cBxBbx1x2x3x41x15/3105/6-1/31x28/301-2/31/3 cj-zj00-1/6-1/6单纯形迭代得最终单纯形表第46页/共104页写出第一
16、行的约束将上式中所有常数写成正数和一个正分数之和分数项移到右边，整数项移到左边第47页/共104页由于左边为整数，所以右边也为整数，所以所以由于加入松弛变量放入单纯形表第48页/共104页cj1100cBxBbx1x2x3x41x15/3105/6-1/61x28/301-2/31/30 x5-2/300-5/61/6 cj-zj00-1/6-1/600 x5001对偶单纯形法继续迭代，得第49页/共104页cj1100cBxBbx1x2x3x41x1110001x216/50101/50 x34/5001-1/5 cj-zj000-1/5-1/50 x51-4/5-6/5第50页/共104页
17、写出第二行的约束将上式中所有常数写成正数和一个正分数之和分数项移到右边，整数项移到左边第51页/共104页由于左边为整数，所以右边也为整数，所以所以由于加入松弛变量放入单纯形表第52页/共104页cj1100cBxBbx1x2x3x41x1110001x216/50101/50 x34/5001-1/5 cj-zj000-1/5-1/500 x51-4/5-6/50 x60000 x6-1/5000-1/5-1/51第53页/共104页cj1100cBxBbx1x2x3x41x1110001x2301000 x310010 cj-zj00000-10 x51-1-10 x601-10 x410
18、0011-5达到最优，还可以得到另一个最优解：。第54页/共104页目标规划第55页/共104页1，已知目标规划问题用图解法求解最优解。第56页/共104页最优解第57页/共104页2，某工厂生产A,S两种型号的微型计算机，他们都需要经过两道工序，每台计算机所需的加工时间、销售利润及该厂每周最大的加工能力如下表：AS周最大加工能力工序1（h/台）46150h工序2（h/台）3275h利润（元/台）300450工厂经营目标的各优先级如下：第58页/共104页P1：每周总利润不低于10000元；P2：合同要求A型机每周至少生产10台，S型机至少15台；P3：工序1每周生成时间最好恰为150h,工序
19、2生成时间可适当超过其能力；试写出目标规划的模型。第59页/共104页解：设生产A，S机器分别为x1,x2台，则有第60页/共104页3，查找参考书，参阅较复杂问题的模型第61页/共104页图论第62页/共104页1，用避圈法或破圈法求下图的最小树第63页/共104页或选取 去掉解答：第64页/共104页2，下图中 是仓库，是商店，求一条 到 的最短路第65页/共104页第66页/共104页最优方案可以有几种：第67页/共104页3，用标号算法求下图的最大流第68页/共104页得增广链如右图中红色部分，调整后得新图如下：第69页/共104页再次标号知：没有增广链存在，故达到最大流。最大流量为1
20、3第70页/共104页4，求下图中流值为6的最小费用流，其中弧旁边的数字为 ,表示容量，表示单位流量费用。第71页/共104页解：以0作为初始流量，得长度网络最短路：调整流量，得新的流量网络第72页/共104页对新的流量网络，得到长度网络最短路：调整流量，得新的流量网络第73页/共104页对新的流量网络，得到长度网络最短路：调整流量，得新的流量网络第74页/共104页 PERT图 与关键路线法第75页/共104页1，下表给出一个汽车库及引道的施工计划：作业编号作业内容作业时间（天）紧前作业1清理场地准备施工10无2备料8无3车库地面施工61，24墙及房顶 架预制1625车库混凝土地面保养243
21、6竖立墙架44，57竖立房顶 架468装窗及边墙1069装门4610装天花板12711油漆168，9，1012引道混凝土施工8313引道混凝土保养241214清理场地交工验收411，13第76页/共104页请解答（1）该工程从施工开始道工程结束的最短周期；（2）如果引道混凝土施工工期拖延10天，对整个工程进度有何影响？（3）若装天花板的施工时间从12天缩短为8天，对整个工程进度有何影响？（4）为保证工期不拖延，装门这项作业最晚应从哪一天开工？（5）如果要求该工程必须在75天内完工，是否应采取措施，应采取什么措施？第77页/共104页解：作业编号分别对应A,B,C,D,E,F,G,H,I,J,K
22、,L,M,N，PERT 图如下第78页/共104页（1）该工程从施工开始道工程结束的最短周期为80天可计算出自由时差和总时差若使用公式：第79页/共104页表示总时差表示自由时差第80页/共104页如此可找到关键路线：A-C-E-F-G-J-K-N（2）如果引道混凝土施工(L)工期拖延10天，由于此工序有总时差28，所以它的工期拖延10天，对整个工程进度无影响。（3）若装天花板（J）的施工时间从12天缩短为8天，观察它的平行工序H，I，发现关键路线不会改变，所以整个工程进度也缩短4天。（4）为保证工期不拖延，装门（I）这项作业最晚应从第56天开工（5）如果要求该工程必须在75天内完工，在合适的
23、关键工序上压缩5天工期。第81页/共104页 动态规划第82页/共104页1.设有6万元资金用于四个工厂的扩建。已知每个工厂的利润增长额同投资数的大小有关，数据见表。如何确定对四个工厂的投资数，使得总利润增长额最大。010020030040050060010204260758590202545576570733018396178909540284765748085利润增长额工厂投资第83页/共104页1.解：设sk表示第k个工厂到第4个工厂的投资数。Xk表示第k个工厂的投资数,则第4个阶段如下：fX*01002003004005006000000100282810020047472003006
24、565300400747440050080805006008585600第84页/共104页fX*0100200300400500600000010028182802004746394703006565676167200400748386897889300500809210410810690108300600859811312612511895126300第3个阶段：第85页/共104页fX*0100 200 300400 500 6000000100 2825280200 47534553100300 6772735773200400 899292856592100，200500 108 1
25、14 112 1049370114 100600 126 133 134 124112 9873134 200第2个阶段：第86页/共104页fX*0100 200 300400 500 600600 134 134 134 133128 113 901340，100，200第1个阶段：最优方案：1，0，200，300，1002，100，100，300，1003，200，100，200，1004，200，200，0，200第87页/共104页2.用动态规划解以下静态问题：解：令k=2,状态变量：k阶段初各约束条件右端项的剩余值R1k,R2k决策变量：x1,x2，状态转移方程为：第88页/共10
26、4页令k=1,由于k=2时,而由第2个约束知，所以第89页/共104页此时,x2第90页/共104页 决策分析第91页/共104页1,某钟表公司计划通过它的销售网销售一种低价钟表，计划每块售价10元。生产这种钟表有3个设计方案：方案1需一次投资10万元，以后生产一个的费用为5元，方案2需一次投资16万元，以后生产一个的费用为4元；方案3需一次投资25万元，以后生产一个的费用为3元。对该种钟表的需求量为未知，但估计有三种可能：E130000；E2120000；E3200000a)建立这个问题的收益矩阵；b)分别用悲观主义、乐观主义和等可能性决策准则决定该公司应采用哪一个设计方案；c)建立机会损失
27、矩阵，并用最小机会损失决策准则决定采取哪一个设计方案。第92页/共104页E1E2E3A155090A2256104A3-459115收益矩阵（单位：万）：第93页/共104页E1E2E3A1550909A2256104104A3-459115115乐观准则：选A3第94页/共104页E1E2E3A1550909A2256104104A3-459115115悲观准则：选A1第95页/共104页E1E2E3A1092525A2231111A39009机会损失矩阵（单位：万）：选A3第96页/共104页2，某工程队承担一个桥梁的施工任务，由于该地区夏季多雨，有三个月时间不能施工。在不施工期内，该工
28、程队可将施工机械搬走或留在原处。假如搬走，需华搬迁费1800元，若留在原处，一种方案是花500元筑一护堤，防止河水上涨发生高水位侵袭；若不筑护堤，发生高水位侵袭时将损失10000元。又若下暴雨发生洪水，则不管是否修护堤，施工机械留在原处都将受到60000元的损失。如果预测在这三个月中，高水位的发生率为25%,洪水的发生率为2%,试依据决策树的方法分析该施工队要不要把施工机械搬走及要不要修筑护堤。第97页/共104页第98页/共104页3，某公司经理的决策效用函数如下：U(-10000)=-800,U(-200)=-2,U(-100)=-1,U(0)=0,U(10000)=250,他需要决定是否
29、为该公司的财产报火险。据大量统计资料，一年内可能发生火灾的概率为，问他是否愿意每年支付100元保10000元财产的潜在火灾损失。第99页/共104页第100页/共104页排队论第101页/共104页1.汽车按照平均90辆/h的Poisson流到达高速公路的一个收费关卡，通过关卡的时间是38秒。由于驾驶人员反应等待时间太长，主管部门打算采用新装置，使汽车通过关卡的平均时间减少到30秒。但增加新装置只有在原系统中等待的汽车平均数超过5辆和新系统中关卡的空闲时间不超过10%时才是合算的。根据这个要求，分析采用新装置是否合算？第102页/共104页2.某小型家电维修部声称对家电一般维修做到一个小时内完成，并保证若顾客停留超过一个小时，修理免费。已知每项修理收费10元，而修理成本为元。若送达修理的家电服从泊松分布，平均6件/小时，修理每件的时间服从负指数分布，平均每件分钟。该维修部有一名修理工，问：(1)该维修部能否做到盈利？（2）当维修时间不变，则维修家电送达率为何值时，该维修部的收支到达盈亏平衡？第103页/共104页感谢您的观看！第104页/共104页