运筹学例题及答案.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《运筹学例题及答案.pptx》由会员分享,可在线阅读,更多相关《运筹学例题及答案.pptx(104页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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由
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 例题 答案
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内