运筹学例题及答案.ppt

作业及答案,1。用单纯形法解LP问题,线性规划,达到最优解，且最优解唯一,2。用大M或两阶段法解LP问题,无界解,3，某厂在今后四个月内需租用仓库堆放物资。已知各月份需租用仓库面积见表，仓库租借费用随合同期不同而不同，期限越长折扣越大，具体数字见表。租借合同每个月月初都可办理，合同规定具体的租借面积和月数，因此该厂可根据需要，在任何一个月月初办理合同，每次办理可签一份或多份，总目标是总的租借费用最低，请建立数学模型并用软件给出结果。,解:设一月初签订合同期限为一个月，两个月，三个月，四个月的仓库面积分别为 ， ， ， ，二月初签订合同期限为一个月，两个月，三个月的仓库面积分别为 ，三月初签订合同期限为一个月，两个月的仓库面积分别为 ，四月初签订合同期限为一个月的仓库面积为 。 则,计算结果如下,4，某厂生产I,II,III三种产品，都分别经过A,B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1，B2，B3三种设备可用于完成B工序。已知产品I可在A,B任何一种设备上加工；产品II可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品III只能在A2和B2设备上加工。加工单位产品所需的工序时间及其它各项数据见表，试安排最优生成计划，使该厂获利最大。,解：设第种产品中，分别在 上加工的数量依次为 ，第种产品中分别在A1,B1和A2,B1 上加工的数量为 生产种产品数量为 。,对偶理论,1. 已知线性规划问题：,要求：a)写出对偶问题，b)已知原问题最有解X*=(2,2,4,0),用互补松弛性求出对偶问题的最优解。,解：对偶问题：,将原问题的最优解带入约束，发现第4个约束为严格不等式，所以，得y4*=0,又因为，原问题最优解的前三个分量都大于0，所以，有如下三个等式成立。,解方程组得对偶问题的最优解为Y*=(4/5,3/5,1,0),2。已知线性规划问题,及最终单纯形表,表1,解：a）,将其加到表（1）的最终单纯形表的基变量b这一列数字上得表（2）,（表2）,表（2）中原问题为非可行解，故用对偶单纯形法继续计算得表（3）,（表3）,即新解为,b) 将cj的改变反应到最终单纯形表上,得表（4）,继续迭代,得表（5）,表5,即新解为,c）,将其加到最终单纯形表上得表（6）,继续迭代,得表（7）,表6,即新解为,表7,d）,将其加到最终单纯形表上得表（8）,表8,因x2已变化为x/2，故用单纯形法算法将x/2替换出基变量中的x2，并在下一个表中不再保留x2，得表（9）,表9,此时已经达到最优，新解为,e) 此时将原来的最优解带入约束，发现满足，所以最优解不变。,运输问题,1，试求下表给出的产销不平衡问题的最优解。,解：用最小元素法求得初始方案如下,用位势法求检验数知,找到闭回路，调整得,又用位势法求检验数知,找到闭回路，调整得,又用位势法求检验数知所有的检验数都非负，达到最优z=32。,2，某市有三个面粉厂，他们供给三个面食加工厂所需的面粉。各面粉厂的产量、面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价见下表。假定在第1，2，3面食加工厂制作单位面粉食品的利润分别为12元，16元，11元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）,食品厂,面粉厂,解：从题意很容易知道，总效益最大实际上是食品利润减去单位运价之后再求的总效益。再因为面粉的总产量为70，比食品厂的总需求量60多了10个单位，可以认为，多的10个单位最后还是会分配给13个食品厂，所以就需要增加一个虚拟的食品厂4。 设xij第i个面粉厂运到第j个食品厂的运量，i=1,2,3;j=1,2,3,4 得下表：,为使用求解运输问题的表上作业法，用上表中的最大数减去其他各数，得下表,使用表上作业法，得最优解.,整数规划,1，分配甲、乙、丙、丁四个人完成ABCDE五项任务，每个人完成各项任务的时间如表所示：,由于任务多于人数，故考虑： （a）任务E必须完成，其他各项可任意选3项完成； （b）其中有一人完成2项，其他每人完成一项。 分别确定最优方案，使完成任务总时间最少,解（a）增加一个虚拟的人，由题目要求，其对应的效率如下,Z=105,解（b）增加一个虚拟的人，由题目要求，其对应的效率如下,最优方案：甲B，乙C，D，丙E，丁A，Z=131,2，用割平面法求解,单纯形迭代得最终单纯形表,写出第一行的约束,将上式中所有常数写成正数和一个正分数之和,分数项移到右边，整数项移到左边,由于左边为整数，所以右边也为整数，所以,所以,由于,加入松弛变量,放入单纯形表,对偶单纯形法继续迭代，得,写出第二行的约束,将上式中所有常数写成正数和一个正分数之和,分数项移到右边，整数项移到左边,由于左边为整数，所以右边也为整数，所以,所以,由于,加入松弛变量,放入单纯形表,达到最优，,还可以得到另一个最优解：。,目标规划,1，已知目标规划问题,用图解法求解最优解。,2，某工厂生产A,S两种型号的微型计算机，他们都需要经过两道工序，每台计算机所需的加工时间、销售利润及该厂每周最大的加工能力如下表：,工厂经营目标的各优先级如下：,P1：每周总利润不低于10000元； P2：合同要求A型机每周至少生产10台，S型机至少15台； P3：工序1每周生成时间最好恰为150h,工序2生成时间可适当超过其能力； 试写出目标规划的模型。,解：设生产A，S机器分别为x1,x2台，则有,3，查找参考书，参阅较复杂问题的模型,图论,1，用避圈法或破圈法求下图的最小树,或选取 去掉,解答：,2，下图中 是仓库， 是商店，求一条 到 的最短路,最优方案可以有几种：,3，用标号算法求下图的最大流,得增广链如右图中红色部分，调整后得新图如下：,再次标号知：没有增广链存在，故达到最大流。最大流量为13,4，求下图中流值为6的最小费用流，其中弧旁边的数字为 , 表示容量， 表示单位流量费用。,解：以0作为初始流量，得长度网络,最短路：,调整流量，得新的流量网络,对新的流量网络，得到长度网络,最短路：,调整流量，得新的流量网络,对新的流量网络，得到长度网络,最短路：,调整流量，得新的流量网络,PERT图 与 关键路线法,1，下表给出一个汽车库及引道的施工计划：,请解答（1）该工程从施工开始道工程结束的最短周期；（2）如果引道混凝土施工工期拖延10天，对整个工程进度有何影响？（3）若装天花板的施工时间从12天缩短为8天，对整个工程进度有何影响？（4）为保证工期不拖延，装门这项作业最晚应从哪一天开工？（5）如果要求该工程必须在75天内完工，是否应采取措施，应采取什么措施？,解：作业编号分别对应A,B,C,D,E,F,G,H,I,J,K,L,M,N，PERT 图如下,（1）该工程从施工开始道工程结束的最短周期为80天,可计算出自由时差和总时差,若使用公式：,表示总时差,表示自由时差,如此可找到关键路线：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天内完工，在合适的关 键工序上压缩5天工期。,动态规划,1. 设有6万元资金用于四个工厂的扩建。已知每个工厂的利润增长额同投资数的大小有关，数据见表。如何确定对四个工厂的投资数，使得总利润增长额最大。,利润增长额,工厂,投资,1.解： 设sk表示第k个工厂到第4个工厂的投资数。Xk表示第k个工厂的投资数,则第4个阶段如下：,第3个阶段：,第2个阶段：,第1个阶段：,最优方案： 1，0，200，300，100 2，100，100，300，100 3，200，100，200，100 4，200，200，0，200,2. 用动态规划解以下静态问题：,解：令k=2, 状态变量：k阶段初各约束条件右端项的剩余值R1k,R2k 决策变量：x1,x2 ，状态转移方程为：,令k=1,由于,k=2时,而由第2个约束知，,所以,此时,x2=0.5,决策分析,1,某钟表公司计划通过它的销售网销售一种低价钟表，计划每块售价10元。生产这种钟表有3个设计方案：方案1需一次投资10万元，以后生产一个的费用为5元，方案2需一次投资16万元，以后生产一个的费用为4元；方案3需一次投资25万元，以后生产一个的费用为3元。对该种钟表的需求量为未知，但估计有三种可能： E130000；E2120000；E3200000 a)建立这个问题的收益矩阵；b)分别用悲观主义、乐观主义和等可能性决策准则决定该公司应采用哪一个设计方案；c)建立机会损失矩阵，并用最小机会损失决策准则决定采取哪一个设计方案。,收益矩阵（单位：万）：,乐观准则：,选A3,悲观准则：,选A1,机会损失矩阵（单位：万）：,选A3,2，某工程队承担一个桥梁的施工任务，由于该地区夏季多雨，有三个月时间不能施工。在不施工期内，该工程队可将施工机械搬走或留在原处。假如搬走，需华搬迁费1800元，若留在原处，一种方案是花500元筑一护堤，防止河水上涨发生高水位侵袭；若不筑护堤，发生高水位侵袭时将损失10000元。又若下暴雨发生洪水，则不管是否修护堤，施工机械留在原处都将受到60000元的损失。如果预测在这三个月中，高水位的发生率为25%,洪水的发生率为2%,试依据决策树的方法分析该施工队要不要把施工机械搬走及要不要修筑护堤。,3，某公司经理的决策效用函数如下：U(-10000)=-800, U(-200)=-2, U(-100)=-1, U(0)=0, U(10000)=250,他需要决定是否为该公司的财产报火险。据大量统计资料，一年内可能发生火灾的概率为0.0015，问他是否愿意每年支付100元保10000元财产的潜在火灾损失。,排队论,1.汽车按照平均90辆/h的Poisson流到达高速公路的一个收费关卡，通过关卡的时间是38秒。由于驾驶人员反应等待时间太长，主管部门打算采用新装置，使汽车通过关卡的平均时间减少到30秒。但增加新装置只有在原系统中等待的汽车平均数超过5辆和新系统中关