线性规划问题的求解方法课件.ppt

1、一、利用MATLAB软件中的linprog命令求解min*. .SfX stAXb1.求解线性规划问题2.求解线性规划问题min*. .SfXAXbstAeqXbeq格式为：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不要求非负3.求解线性规划问题min*. .SfXAXbstAeqXbeqLBXUB格式为：x=linprog(f,A,b,Aeq,beq,LB,UB)x,fval=linprog(f,A,b,Aeq,beq,LB,UB)注：这

2、里x、b不要求非负12121max328. .60,1,2iSxxxxstxxi例3.1121212max8045205400. .15104500,1,2iSxxxxstxxxi例3.2123412341234max2322325. .2100,1,2,3,4iSxxxxxxxxstxxxxxi例3.3123123123max6321. .2230,1,2,3iSxxxxxxstxxxxi例3.51231231231413max32246. .232100,1,2,3,4iSxxxxxxxxxstxxxxxi例3.6123123123123min3225433. .20,1,2,3iSxxx

3、xxxxxxstxxxxi P75 T2（5）1231231212min32822. .2100,1,2,3iSxxxxxxxxstxxxiP75 T2（6）1234123412341234min223622. .70,1,2,3,4iSxxxxxxxxxxxxstxxxxxiP75 T2（10）二、利用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. 变量可以放在约束条件的右边，数字可在左边；5. 每个

4、语句都以分号“ ；”结尾；6. 以感叹号“ ！”开始的是说明语句。例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例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=10;2*x2+x4=5;gin(x1);gin(x2);end例7!线性规划运输问题p169例子;mo

5、del: 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); for(supply(i):supply_con sum(demond(j):x(i,j)=gy(i);); for(demon

6、d(j):demond_con sum(supply(i):x(i,j)=xq(j););endmodel: !线性规划运输问题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 29 26 6 24; gy=10 15 25 40 10; xq=9 17 22 33 14 5; enddata obj min=sum(link:c*x

7、); 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三、自编MATLAB程序求解dan0求解特殊线性规划问题dan0-bland用bland法则求解特殊线性规划问题dan0-improve 用改进的单纯形法求解线性规划问题danm用大M法求解线性规划问题dan2用两阶段法求解线性规划问题u特殊的线性规划问题要求输入的数据（第一张单纯形表，典式）3101004401010351200180-2-50000基变量下标增广系数矩阵目

8、标函数的系数的相反数u标准线性规划问题要求输入的数据:去掉上表最左边的一列用分支定界法求解整数规划问题 书P120 T1（1）1212121212max43410238,0,NSxxxxxxx xx x解：原问题记为A，将该问题进行松弛，得到问题B：12121212max43410238,0Sxxxxxxx x松弛问题B的最优解： （2.2， 1.2） 最优值12.4问题B的最优解不是整数解，对该问题关于x1进行分支：121212112B1max434102382,0Sxxxxxxxx x121212112B2max434102383,0Sxxxxxxxx xB1的最优解为: (2,4/3)最

9、优值为12B2的可行解域为空集1212121212B11max4341023821,0Sxxxxxxxxx x对问题B1关于x2进行分支：1212121212B12max4341023822,0Sxxxxxxxxx xB11的最优解为: (2,1)最优值为11B12的最优解为: (1,2)最优值为10该整数线性规划问题的最优解就是（2，1），最优值是11用分支定界法求解整数规划问题 书P120 T1（3）1212121212max201054242513,0,NSxxxxxxx xx x解：原问题记为A，将该问题进行松弛，得到问题B：12121212max201054242513,0Sxxxx

10、xxx x松弛问题B的最优解： （4.8， 0） 最优值96问题B的最优解不是整数解，对该问题关于x1进行分支：121212112B1max2010542425134,0Sxxxxxxxx xB1的最优解为: (4，1)最优值为90B2的可行解域为空集121212112B1max2010542425135,0Sxxxxxxxx x该整数线性规划问题的最优解就是（4，1），最优值是90用割平面法求解整数线性规划问题 P120 T2（1）121212121212min453245327,0,Sxxxxxxxxx xx xN解：原问题记为A，将其松弛得到问题B：1212121212min453245

11、327,0Sxxxxxxxxx x1212312412512345min453245327,0Sxxxxxxxxxxxx xx x x 用对偶单纯形法求得最优解为（1.8，0.8），最优值为11.2，最后一张单纯形表为x1x2x3x4x5bx30010.3-1.14.2x2010-0.30.10.8x11000.2-0.41.8S0000.71.1-11.21450.2( 1 0.6)1 0.8xxx 154510.80.20.60 xxxx 450.20.60.8xx x1x2x3x4x5x6bx30010.3-1.104.2x2010-0.30.100.8x11000.2-0.401.8x

12、6000-0.2-0.61-0.8S0000.71.10-11.2用对偶单纯形法求得最优解为（2.3333，0.6667），最优值为12.6667，最优解不是整数解。最后一张单纯形表为：将新约束条件加入到原规划中，得到新的规划问题：123456b30012/30-11/617/32010-1/301/62/311001/30-2/37/350001/31-5/34/300001/3011/6-38/3根据第四行得到新约束条件：461xx 将新约束条件加入到规划中，得到新的规划问题：1234567b30012/30-11/6017/32010-1/301/602/311001/30-2/307/

13、350001/31-5/304/37000-10-11-100001/3011/60-38/3用对偶单纯形法求解得到：1234567b300100-5/22/352010001/2-1/31110000-11/32500001-21/314000101-110000003/21/3-13最优解为（2，1），最优值为13. 最优解为整数解，故整数规划问题的最优解就是（2，1），最优值为13运输问题的初始调运方案的编制z 1.希奇柯克法:xiqikeke1z 2.主对角线法:zhuduijiaoxian2z 3.最小元素法:zuixiaoyuan3z 4.小元素差额法:xiaoyuancha4自编matlab程序求解运输问题transport_dan用单纯形法求解运输问题transport_fixed先用最小元素法求解初始方案，再用单纯形法求最优解transport_special用特殊方法求解运输问题zuixiaofenpeiwenti求解最小分配问题zuiyoupanbie_weishifa用位势法判别运输方案是否达到最优