线性规划问题的求解方法

线性规划问题的求解方法第1页，课件共28页，创作于2023年2月一、利用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页，创作于2023年2月3.求解线性规划问题格式为：x=linprog(f,A,b,Aeq,beq,LB,UB)[x,fval]=linprog(f,A,b,Aeq,beq,LB,UB)注：这里x、b不要求非负第3页，课件共28页，创作于2023年2月例3.1例3.2第4页，课件共28页，创作于2023年2月例3.3例3.5第5页，课件共28页，创作于2023年2月例3.6第6页，课件共28页，创作于2023年2月P75T2（5）P75T2（6）第7页，课件共28页，创作于2023年2月P75T2（10）第8页，课件共28页，创作于2023年2月二、利用LINGO软件求解例1max=3*x1+2*x2;x1+2*x2<=200;3*x1+x2<=240;例2min=4*x+9*y;9*x+7*y>=56;7*x+20*y>=70;1.max或min后面跟着等号＝；2.不区分大小写字母，变量必须以字母开头；3.模型中已经假设所有的变量非负；4.变量可以放在约束条件的右边，数字可在左边；5.每个语句都以分号“；”结尾；6.以感叹号“！”开始的是说明语句。第9页，课件共28页，创作于2023年2月例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页，创作于2023年2月例5model:max=3*x1+2*x2;2*x1+3*x2<=14;2*x1+x2<9;@gin(x1);@gin(x2);end例6model:max=x1+x2;3*x1+2*x2+x3<=10;2*x2+x4<=5;@gin(x1);@gin(x2);end第11页，课件共28页，创作于2023年2月例7!线性规划运输问题p169例子;model:sets:supply/1..5/:gy;demond/1..6/:xq;link(supply,demond):c,x;endsetsdata:c=302831025182741121795121228161321191523720142926624;gy=1015254010;xq=9172233145;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第12页，课件共28页，创作于2023年2月model:!线性规划运输问题p169例子;sets:supply/1..5/:gy;demond/1..6/:xq;link(supply,demond):c,x;endsetsdata:c=302831025182741121795121228161321191523720142926624;gy=1015254010;xq=9172233145;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页，创作于2023年2月三、自编MATLAB程序求解dan0求解特殊线性规划问题dan0-bland用bland法则求解特殊线性规划问题dan0-improve用改进的单纯形法求解线性规划问题danm用大M法求解线性规划问题dan2用两阶段法求解线性规划问题第14页，课件共28页，创作于2023年2月特殊的线性规划问题要求输入的数据（第一张单纯形表，典式）3101004401010351200180-2-50000基变量下标增广系数矩阵目标函数的系数的相反数标准线性规划问题要求输入的数据:去掉上表最左边的一列第15页，课件共28页，创作于2023年2月用分支定界法求解整数规划问题[书P120T1（1）]解：原问题记为A，将该问题进行松弛，得到问题B：第16页，课件共28页，创作于2023年2月松弛问题B的最优解：（2.2，1.2）最优值12.4问题B的最优解不是整数解，对该问题关于x1进行分支：B1的最优解为:(2,4/3)最优值为12B2的可行解域为空集第17页，课件共28页，创作于2023年2月对问题B1关于x2进行分支：B11的最优解为:(2,1)最优值为11B12的最优解为:(1,2)最优值为10该整数线性规划问题的最优解就是（2，1），最优值是11第18页，课件共28页，创作于2023年2月用分支定界法求解整数规划问题[书P120T1（3）]解：原问题记为A，将该问题进行松弛，得到问题B：第19页，课件共28页，创作于2023年2月松弛问题B的最优解：（4.8，0）最优值96问题B的最优解不是整数解，对该问题关于x1进行分支：B1的最优解为:(4，1)最优值为90B2的可行解域为空集该整数线性规划问题的最优解就是（4，1），最优值是90第20页，课件共28页，创作于2023年2月用割平面法求解整数线性规划问题[P120T2（1）]解：原问题记为A，将其松弛得到问题B：第21页，课件共28页，创作于2023年2月用对偶单纯形法求得最优解为（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页，创作于2023年2月x1x2x3x4x5x6bx30010.3-1.104.2x2010-0.30.100.8x11000.2-0.401.8x6000-0.2-0.61-0.8S0000.71.10-11.2用对偶单纯形法求得最优解为（2.3333，0.6667），最优值为12.6667，最优解不是整数解。最后一张单纯形表为：将新约束条件加入到原规划中，得到新的规划问题：第23页，课件共28页，创作于2023年2月123456b30012/30-11/617/32010-1/301/62/311001/30-2/37/350001/31-5/34/300001/3011/6-38/3根据第四行得到新约束条件：将新约束条件加入到规划中，得到新的规划问题：第24页，课件共28页，创作于2023年2月1234567b30012/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页，创作于2023年2月1234567b300100-5/22/352010001/2-1/31110000-11/32500001-21/314000101-110000003/21/3-13最优解为（2，1），最优值为13.最优解为整数解，故整数规划问题的最优解就是（2，1），最优值为13第26页，课件共28页，创作于2023年2月运输问题的初始调运方案的编制

1.希奇柯克法:xiqikeke12.主对角线法:zhuduijiaoxian23.最小元素法:zuixiaoyuan34.小元素差额法:xiaoyuancha4第27页，课件共28页