《线性规划问题的求解方法幻灯片.ppt》由会员分享,可在线阅读,更多相关《线性规划问题的求解方法幻灯片.ppt(28页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性规划问题的求解方法第1页,共28页,编辑于2022年,星期一一、利用MATLAB软件中的linprog命令求解1.求解线性规划问题2.求解线性规划问题格式为:x=linprog(f,A,b)x,fval=linprog(f,A,b)格式为:x=linprog(f,A,b,Aeq,beq)x,fval=linprog(f,A,b,Aeq,beq)注:x,b不要求非负第2页,共28页,编辑于2022年,星期一3.求解线性规划问题格式为:x=linprog(f,A,b,Aeq,beq,LB,UB)x,fval=linprog(f,A,b,Aeq,beq,LB,UB)注:这里x、b不要求非负第3页
2、,共28页,编辑于2022年,星期一例3.1例3.2第4页,共28页,编辑于2022年,星期一例3.3例3.5第5页,共28页,编辑于2022年,星期一例3.6第6页,共28页,编辑于2022年,星期一P75T2(5)P75T2(6)第7页,共28页,编辑于2022年,星期一P75T2(10)第8页,共28页,编辑于2022年,星期一二、利用LINGO软件求解例1max=3*x1+2*x2;x1+2*x2=200;3*x1+x2=56;7*x+20*y=70;1.max或min后面跟着等号;2.不区分大小写字母,变量必须以字母开头;3.模型中已经假设所有的变量非负;4.变量可以放在约束条件的右
3、边,数字可在左边;5.每个语句都以分号“;”结尾;6.以感叹号“!”开始的是说明语句。第9页,共28页,编辑于2022年,星期一例3max=8*x+5*y+4*z;x+y+z=9;8*x+5*y+4*z=45;x=1;y=5;z=5;gin(x);gin(y);gin(z);例4model:max=5*x1+7*x2;x1+x2=20;3*x1+7*x2=80;end第10页,共28页,编辑于2022年,星期一例5model:max=3*x1+2*x2;2*x1+3*x2=14;2*x1+x29;gin(x1);gin(x2);end例6model:max=x1+x2;3*x1+2*x2+x3
4、=10;2*x2+x4=5;gin(x1);gin(x2);end第11页,共28页,编辑于2022年,星期一例7!线性规划运输问题p169例子;model:sets:supply/1.5/:gy;demond/1.6/:xq;link(supply,demond):c,x;endsets data:c=30 28 3 10 25 18 27 4 11 2 17 9 5 12 1 22 8 16 13 21 19 15 23 7 20 14 29 26 6 24;gy=10 15 25 40 10;xq=9 17 22 33 14 5;enddata obj min=sum(link:c*x)
5、;for(supply(i):supply_con sum(demond(j):x(i,j)=gy(i););for(demond(j):demond_con sum(supply(i):x(i,j)=xq(j););end第12页,共28页,编辑于2022年,星期一model:!线性规划运输问题p169例子;sets:supply/1.5/:gy;demond/1.6/:xq;link(supply,demond):c,x;endsets data:c=30 28 3 10 25 18 27 4 11 2 17 9 5 12 1 22 8 16 13 21 19 15 23 7 20 14
6、29 26 6 24;gy=10 15 25 40 10;xq=9 17 22 33 14 5;enddata obj min=sum(link:c*x);for(supply(i):supply_con sum(demond(j):x(i,j)=gy(i);for(demond(j):demond_con sum(supply(i):x(i,j)=xq(j);end第13页,共28页,编辑于2022年,星期一三、自编MATLAB程序求解dan0求解特殊线性规划问题dan0-bland用bland法则求解特殊线性规划问题dan0-improve 用改进的单纯形法求解线性规划问题danm用大M法
7、求解线性规划问题dan2用两阶段法求解线性规划问题第14页,共28页,编辑于2022年,星期一u特殊的线性规划问题要求输入的数据(第一张单纯形表,典式)3101004401010351200180-2-50000基变量下标增广系数矩阵目标函数的系数的相反数u标准线性规划问题要求输入的数据:去掉上表最左边的一列第15页,共28页,编辑于2022年,星期一用分支定界法求解整数规划问题 书P120 T1(1)解:原问题记为A,将该问题进行松弛,得到问题B:第16页,共28页,编辑于2022年,星期一松弛问题B的最优解:(2.2,1.2)最优值12.4问题B的最优解不是整数解,对该问题关于x1进行分支
8、:B1的最优解为:(2,4/3)最优值为12B2的可行解域为空集第17页,共28页,编辑于2022年,星期一对问题B1关于x2进行分支:B11的最优解为:(2,1)最优值为11B12的最优解为:(1,2)最优值为10该整数线性规划问题的最优解就是(2,1),最优值是11第18页,共28页,编辑于2022年,星期一用分支定界法求解整数规划问题 书P120 T1(3)解:原问题记为A,将该问题进行松弛,得到问题B:第19页,共28页,编辑于2022年,星期一松弛问题B的最优解:(4.8,0)最优值96问题B的最优解不是整数解,对该问题关于x1进行分支:B1的最优解为:(4,1)最优值为90B2的可
9、行解域为空集该整数线性规划问题的最优解就是(4,1),最优值是90第20页,共28页,编辑于2022年,星期一用割平面法求解整数线性规划问题 P120 T2(1)解:原问题记为A,将其松弛得到问题B:第21页,共28页,编辑于2022年,星期一用对偶单纯形法求得最优解为(1.8,0.8),最优值为11.2,最后一张单纯形表为x1x2x3x4x5bx30010.3-1.14.2x2010-0.30.10.8x11000.2-0.41.8S0000.71.1-11.2第22页,共28页,编辑于2022年,星期一x1x2x3x4x5x6bx30010.3-1.104.2x2010-0.30.100.
10、8x11000.2-0.401.8x6000-0.2-0.61-0.8S0000.71.10-11.2用对偶单纯形法求得最优解为(2.3333,0.6667),最优值为12.6667,最优解不是整数解。最后一张单纯形表为:将新约束条件加入到原规划中,得到新的规划问题:第23页,共28页,编辑于2022年,星期一123456b30012/30-11/617/32010-1/301/62/311001/30-2/37/350001/31-5/34/300001/3011/6-38/3根据第四行得到新约束条件:将新约束条件加入到规划中,得到新的规划问题:第24页,共28页,编辑于2022年,星期一1
11、234567b30012/30-11/6017/32010-1/301/602/311001/30-2/307/350001/31-5/304/37000-10-11-100001/3011/60-38/3用对偶单纯形法求解得到:第25页,共28页,编辑于2022年,星期一1234567b300100-5/22/352010001/2-1/31110000-11/32500001-21/314000101-110000003/21/3-13最优解为(2,1),最优值为13.最优解为整数解,故整数规划问题的最优解就是(2,1),最优值为13第26页,共28页,编辑于2022年,星期一运输问题的初
12、始调运方案的编制z 1.希奇柯克法:xiqikeke1z 2.主对角线法:zhuduijiaoxian2z 3.最小元素法:zuixiaoyuan3z 4.小元素差额法:xiaoyuancha4第27页,共28页,编辑于2022年,星期一自编matlab程序求解运输问题transport_dan用单纯形法求解运输问题transport_fixed先用最小元素法求解初始方案,再用单纯形法求最优解transport_special用特殊方法求解运输问题zuixiaofenpeiwenti求解最小分配问题zuiyoupanbie_weishifa用位势法判别运输方案是否达到最优第28页,共28页,编辑于2022年,星期一