《线性规划问题的求解方法》由会员分享，可在线阅读，更多相关《线性规划问题的求解方法（28页珍藏版）》请在金锄头文库上搜索。
1、线性规划问题的求解方法,利用MATLAB软件中的linprog命令求解； 利用LINGO软件求解； 自编MATLAB程序求解。,一、利用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不要求非负,3.求解线性规划问题,格式为：x=linprog(f,A,b,Aeq,beq,LB,UB),x,fval=linprog(f,A,b,Aeq,beq,
2、LB,UB),注：这里x、b不要求非负,例3.1,例3.2,例3.3,例3.5,例3.6,P75 T2（5）,P75 T2（6）,P75 T2（10）,二、利用LINGO软件求解,例1 max=3*x1+2*x2; x1+2*x2=200; 3*x1+x2=56;7*x+20*y=70;,1. max或min后面跟着等号； 2. 不区分大小写字母，变量必须以字母开头； 3. 模型中已经假设所有的变量非负； 4. 变量可以放在约束条件的右边，数字可在左边； 5. 每个语句都以分号“ ；”结尾； 6. 以感叹号“ ！”开始的是说明语句。,例3 max=8*x+5*y+4*z; x+y+z=9; 8
3、*x+5*y+4*z=45; x=1; y=5; z=5; gin(x); gin(y); gin(z);,例4 model: max=5*x1+7*x2; x1+x2=20; 3*x1+7*x2=80; end,例5 model: max=3*x1+2*x2; 2*x1+3*x2=14; 2*x1+x29; gin(x1); gin(x2); end,例6 model: max=x1+x2; 3*x1+2*x2+x3=10; 2*x2+x4=5; gin(x1); gin(x2); end,例7 !线性规划运输问题p169例子; model:sets: supply/15/:gy; demo
4、nd/16/:xq; link(supply,demond):c,x;endsetsdata: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;enddataobj 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(
5、j);); end,model: !线性规划运输问题p169例子;sets:supply/15/:gy;demond/16/:xq;link(supply,demond):c,x;endsetsdata: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;enddataobj min=sum(link:c*x);for(supply(i):supply_con sum(demond(j):x(i,j)=gy(
6、i);for(demond(j):demond_con sum(supply(i):x(i,j)=xq(j); end,三、自编MATLAB程序求解,特殊的线性规划问题要求输入的数据（第一张单纯形表，典式）,基变量下标,增广系数矩阵,目标函数的系数的相反数,标准线性规划问题要求输入的数据:去掉上表最左边的一列,用分支定界法求解整数规划问题 书P120 T1（1）,解：原问题记为A，将该问题进行松弛，得到问题B：,松弛问题B的最优解： （2.2， 1.2） 最优值12.4,问题B的最优解不是整数解，对该问题关于x1进行分支：,B1的最优解为: (2,4/3) 最优值为12,B2的可行解域为空集,
7、对问题B1关于x2进行分支：,B11的最优解为: (2,1) 最优值为11,B12的最优解为: (1,2) 最优值为10,该整数线性规划问题的最优解就是（2，1），最优值是11,用分支定界法求解整数规划问题 书P120 T1（3）,解：原问题记为A，将该问题进行松弛，得到问题B：,松弛问题B的最优解： （4.8， 0） 最优值96,问题B的最优解不是整数解，对该问题关于x1进行分支：,B1的最优解为: (4，1) 最优值为90,B2的可行解域为空集,该整数线性规划问题的最优解就是（4，1），最优值是90,用割平面法求解整数线性规划问题 P120 T2（1）,解：原问题记为A，将其松弛得到问题B
8、：,用对偶单纯形法求得最优解为（1.8，0.8），最优值为11.2，最后一张单纯形表为,用对偶单纯形法求得最优解为（2.3333，0.6667），最优值为12.6667，最优解不是整数解。 最后一张单纯形表为：,将新约束条件加入到原规划中，得到新的规划问题：,根据第四行得到新约束条件：,将新约束条件加入到规划中，得到新的规划问题：,用对偶单纯形法求解得到：,最优解为（2，1），最优值为13. 最优解为整数解，故整数规划问题的最优解就是（2，1），最优值为13,运输问题的初始调运方案的编制,1.希奇柯克法:xiqikeke12.主对角线法:zhuduijiaoxian23.最小元素法:zuixiaoyuan34.小元素差额法:xiaoyuancha4,自编matlab程序求解运输问题,
