运筹学复习题解答.pptx

《运筹学复习题解答.pptx》由会员分享，可在线阅读，更多相关《运筹学复习题解答.pptx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 药名药名原料原料ABC成本（元成本（元/kg）甲甲1525乙乙1416丙丙1517丁丁1628生产量生产量恰好恰好100克克至少至少530克克不超过不超过160克克第1页/共42页解：设 x1 ,x2 ,x3 ,x4 分别为原料甲、乙、丙、丁的选配数量（单位：公斤），则有min z=5x1+6x2+7x3+8x4 s.t.x1+x2+x3+x4=100 5x1+4 x2+5 x3+6 x4 530 2x1+x2+x3+2 x4 160 x1 ,x2 ,x3 ,x4 0第2页/共42页2：用单纯形法求解线性规划问题解：化为标准形为第3页/共42页C211000 CBXBB-1bx1x2x3x4

2、x5x60 x4603111000 x5101 120100 x62011 1001 02110002010200 x4603111002x1101 120100 x62011 1001 02110000304-5-30102-3-101-3-2207.550 x43004 51302x1101 12010-1x21002 3011 15-1.5-0.50.51500.50.50.51001-1-225000-1.5-1.5-0.5所以，所求最优解为,x1=15,x2=5,x3=0,x4=10,x5=x6=0 最优值为：z*=25 第4页/共42页3：用大M法计算下列线性规划 max z =2

3、x1+3x2 s.t.2x1+x2 16 x1+3x2 20 x1+x2 =10 x1,x2 0第5页/共42页解：化为标准形并加入人工变量为：max z =2x1+3x2-Mx5-Mx6s.t.2x1+x2 +x4 =16 x1+3x2 -x3 +x5 =20 x1+x2 +x6=10 x1,x2,x3,x4,x5,x6 0第6页/共42页第7页/共42页cj2300-M-MCBXBB-1bx1x2x3x4x5x60 x4610010-13x2102100010 x3101010-13 j30-1000-M-M-3最优解为(0，10)T,最优值为 z*=30第8页/共42页4：利用两阶段法计

4、算下题：max z=30 x1+40 x2100 x3 s.t.4x1+3x2 x3=30 x1+3x2 x3=12 x1,x2,x3 30第一阶段：m in z=x4+x5 s.t.4x1+3x2 x3+x4 =30 x1+3x2 x3 +x5=12 x1,x2,x3,x4 ,x5 30第9页/共42页C000 1 1 CBXBbx1x2x3x4x5 1x43043 11010 1x51213 1014 j 4256200 1x4183001 160 x241/31 1/301/312 j 186000 10 x161001/3 1/30 x2201 1/3 1/94/9 j 18000 1

5、 1第10页/共42页第二阶段：C3040 100 CBXBbx1x2x330 x1610040 x2201 1/3 j24000 260/3原规划最优解为：x1=6,x2=2,x3=0,z=240第11页/共42页5：写出下面问题的对偶问题 max z=2x1 2x2+2x3+x4 s.t.x1+x2+x3 +x4 12 2 x1 x2+3 x3 =7 x1 x3+4x4 3 x1 0,x3 0,x2,x4 无约束第12页/共42页6:求解下列产销平衡的运输问题，下表中 列出的为产地到销地之间的运价。销地销地产地产地B1B2B3B4产量产量A13113127A219284A3741059销量

6、销量365620第13页/共42页解：由差额法得初始运输方案 销销产产B1B2B3B4产产量量B1B2B3B4A17311312A241928A3974105销量销量3656200112513差额差额4601253214831125第14页/共42页 销销产产B1B2B3B4A1311312A21928A374105最优性检验uivj30017-262721912第15页/共42页所有的非基变量的检验数都大于零。所以所得运输方案为最优方案，最少运费为：Z*=23+5 3+1 1+3 8+6 4+3 5=857：求解下列运费最少的运输问题 销地销地产地产地B1B2B3B4产量产量A1105672

7、5A2827625A3934850销量销量15203035100第16页/共42页 销销产产B1B2B3B4产产量量B1B2B3B4A125 10567A2258276A3509348销量销量15 20 30 35100由伏格法（差额法）得：差额差额14111212201144303217251265515第17页/共42页最优性检验：由位势法得 销地销地产地产地B1B2B3B4A110567A28276A39348uivj610222712315-1从表中可以看出，a32 的检验数小于零，第18页/共42页需要进行调整，得 销地销地产地产地B1B2B3B4A125A2205A315305+5

8、 5+55新的运输方案为第19页/共42页 销地销地产地产地B1B2B3B4A125A21510A315530重新进行检验得：第20页/共42页 销地销地产地产地B1B2B3B4A110567A28276A39348uivj6102138122041z*=257+15 2+10 6+15 9+5 3+30 4=535第21页/共42页8:用对偶单纯形法求解下列问题Max z=2x1 2x2+3x3s.t.x1+4x2+3 x3 8 x1+2x2+2 x3 6 x1,x2,x3 0+x4=8+x5=,x4,x5 0第22页/共42页cj2 2300 CBXBB-1 bx1x2x3x4x50 x4

9、 81431080 x56(1)22016 j2 23000 x4 20 2(1)112x1612201 j06102 323x32021112x1212023 j04013第23页/共42页9:某厂生产甲、乙、丙3种产品，分别经过A、B、C三种设备加工，已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润见下表：甲甲乙乙丙丙设备能力设备能力/台时台时A111100B1045600C226300单位产品利润单位产品利润/元元1064（1）建立线性规划模型，求该厂获利最大的生产计划；第24页/共42页（2）产品丙每件的利润增加到多少时才值得安排 生产？如产品丙每件的利润增加到50

10、/6，求 最优生产计划。（3）产品甲的利润在什么范围内变化时，原最优 计划保持不变？（4）设备A的能力如为100+10，确定保持原最优 基不变的 的变化范围。（5）如有一种新产品丁，加工一件需设备A、B、C的台时各为 1h，4h，3h，预期每件的利润第25页/共42页 为8元，是否值得安排生产？（6）如合同规定该厂至少生产10件产品丙，试确定 最优生产计划。解：设甲、乙、丙的产量分别为 x1,x2,x3，则 max z=10 x1+6x2+4x3 s.t.x1+x2+x3100 10 x1+4 x2+5 x3600 2x1+2 x2+6 x3300 x1,x2,x3 0第26页/共42页C10

11、64000 CBXBB-1bx1x2x3x4x5x60 x41001111001000 x56001045010600 x6300226001300 j010640000 x44000.60.51 0.10200/310 x16010.40.500.101500 x618001.250 0.21150 j00210 106x2200/3015/65/3 1/6010 x1100/3101/6-2/31/600 x6100004-201 j0008/3-10/3 2/30第27页/共42页（2）对c3 作灵敏度分析：因为x3为非基变量当丙每件的利润增加到50/6时，有C10650/6000 CB

12、XBB-1bx1x2x3x4x5x66x2200/3015/65/3 1/608010 x1100/3101/6-2/31/602000 x6100004-20125 j2200/3005/3-10/3 2/306x2275/601015/12 1/6-5/2410 x1175/6100-7/121/6-1/2450/6x325001-1/201/4 j000-5/3 2/3-5/12第28页/共42页（3）产品甲的利润的范围为：即当甲的利润在6，15之间变化时，最优计划不变。（4）对设备A的工时作灵敏度分析：（5）因为产品丁的影子（机会）成本为：第29页/共42页产品丁的影子价格小于其利润，

13、故该产品值得安排生产。（6）合同要求至少生产10件产品丙 x3 必须大于等于10 目标值下降;下降程度可用 x3 的检验数进行计算：第30页/共42页10.下表中给出某求极大化问题的单纯形表，问表中 a1,a2,c1,c2,d 为何值时，以及表中变量属于哪 种类型时有：(a)表中解为唯一最优解；(b)表中解为无穷多最优解之一；(c)表中解为退化的可行解；(d)下一步迭代将以 x1 替代基变量 x5；(e)该线性规划问题具有无界解；(d)该线性规划无可行解。第31页/共42页x1x2x3x4x5x3d4a1100 x4215010 x53a23001cj zjc1c2000解：中至少有一个为0。

14、第32页/共42页为人工变量，且第33页/共42页11.求A到E的下列最短路线及其长度。AB1B2B3C1C2D1D2D3E32144313353253142315第34页/共42页解：图形变化为AB1B2B3C1C2D1D2D3E3214431335325314231500C3C0031553548678最短路线 AB2C1D1E，其长度为 8。第35页/共42页12.某工厂购进100台机器，准备生产 p1,p2 两种产 品。若生产产品 p1，每台机器每年可收入45万 元，损坏率为65%；若生产产品 p2，每台机器 每年可收入35万元，损坏率为35%；估计三年后 将有新 的机器出现，旧的机器

15、将全部淘汰。试 问每年应如何安排生产，使在三年内收入最多？解：解：首先构造这个问题的动态规划模型。1.变量设置 (1)设阶段变量k表示年度，因此，阶段总数n=3。第36页/共42页(2)状态变量sk表示第k年度初拥有的完好机床台数，同时也是第 k1 年度末时的完好机床数量。(3)决策变量uk，表示第k年度中分配于生产产品 p1 的机器台数。于是sk uk便为该年度中分配于生 产产品 p1的机器台数2.状态转移方程为 k=1，2，3,43允许决策集合,在第 k 段为第37页/共42页4目标函数。设gk(sk,uk)为第k年度的产量，则 gk(sk,uk)=45uk+35(skuk),因此，目标函

16、数为5条件最优目标函数递推方程。k 1,2,3.令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第3年度结束这段时间的产品产量，根据最优化原理有以下递推关系：k=1,2,3。第38页/共42页 6.边界条件为下面采用逆序递推计算法,从第3年度开始递推计算。k=3 时有 当 u3*=s3 时,f3(s3)有最大值,相应的有f3(s3)=45s3k=2时有第39页/共42页因此，当 u2*=0 时，有最大值 f2(s2)=64.25 s2k=1 时有第40页/共42页当取u1*=0时,f1(s1)有最大值，即f1(s1)=76.7625s1,因为s1=100,故 f1(s1)=7676.25 万元得最优决策为：第一年将100台机器全部生产产品p2，第二年把余下的机器继续生产产品p2，第三年把余下的机器全部生产产品p1。三年的总收入为7676.25万元。第41页/共42页感谢您的观看！第42页/共42页