线性规划问题的求解方法幻灯片.ppt

《线性规划问题的求解方法幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的求解方法幻灯片.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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年，星期一