線性規(guī)劃問題的求解方法課件

一、利用MATLAB軟件中的linprog命令求解1.求解線性規(guī)劃問題2.求解線性規(guī)劃問題格式為：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不要求非負(fù)一、利用MATLAB軟件中的linprog命令求解1.求解線13.求解線性規(guī)劃問題格式為：x=linprog(f,A,b,Aeq,beq,LB,UB)[x,fval]=linprog(f,A,b,Aeq,beq,LB,UB)注：這里x、b不要求非負(fù)3.求解線性規(guī)劃問題格式為：x=linprog(f,A,b,2例3.1例3.2例3.1例3.23例3.3例3.5例3.3例3.54例3.6例3.65P75T2（5）P75T2（6）P75T2（5）P75T2（6）6P75T2（10）P75T2（10）7二、利用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后面跟著等號(hào)＝；2.不區(qū)分大小寫字母，變量必須以字母開頭；3.模型中已經(jīng)假設(shè)所有的變量非負(fù)；4.變量可以放在約束條件的右邊，數(shù)字可在左邊；5.每個(gè)語句都以分號(hào)“；”結(jié)尾；6.以感嘆號(hào)“！”開始的是說明語句。二、利用LINGO軟件求解例1例21.max或min后面跟8例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例3例49例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例5例610例7!線性規(guī)劃運(yùn)輸問題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例711model:!線性規(guī)劃運(yùn)輸問題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));endmodel:!線性規(guī)劃運(yùn)輸問題p169例子;12三、自編MATLAB程序求解dan0求解特殊線性規(guī)劃問題dan0-bland用bland法則求解特殊線性規(guī)劃問題dan0-improve用改進(jìn)的單純形法求解線性規(guī)劃問題danm用大M法求解線性規(guī)劃問題dan2用兩階段法求解線性規(guī)劃問題三、自編MATLAB程序求解dan0求解特殊線性規(guī)劃問題da13特殊的線性規(guī)劃問題要求輸入的數(shù)據(jù)（第一張單純形表，典式）3101004401010351200180-2-50000基變量下標(biāo)增廣系數(shù)矩陣目標(biāo)函數(shù)的系數(shù)的相反數(shù)標(biāo)準(zhǔn)線性規(guī)劃問題要求輸入的數(shù)據(jù):去掉上表最左邊的一列特殊的線性規(guī)劃問題要求輸入的數(shù)據(jù)（第一張單純形表，典式）3114用分支定界法求解整數(shù)規(guī)劃問題[書P120T1（1）]解：原問題記為A，將該問題進(jìn)行松弛，得到問題B：用分支定界法求解整數(shù)規(guī)劃問題[書P120T1（1）]解：15松弛問題B的最優(yōu)解：（2.2，1.2）最優(yōu)值12.4問題B的最優(yōu)解不是整數(shù)解，對(duì)該問題關(guān)于x1進(jìn)行分支：B1的最優(yōu)解為:(2,4/3)最優(yōu)值為12B2的可行解域?yàn)榭占沙趩栴}B的最優(yōu)解：（2.2，1.2）最優(yōu)值1216對(duì)問題B1關(guān)于x2進(jìn)行分支：B11的最優(yōu)解為:(2,1)最優(yōu)值為11B12的最優(yōu)解為:(1,2)最優(yōu)值為10該整數(shù)線性規(guī)劃問題的最優(yōu)解就是（2，1），最優(yōu)值是11對(duì)問題B1關(guān)于x2進(jìn)行分支：B11的最優(yōu)解為:(2,1)B17用分支定界法求解整數(shù)規(guī)劃問題[書P120T1（3）]解：原問題記為A，將該問題進(jìn)行松弛，得到問題B：用分支定界法求解整數(shù)規(guī)劃問題[書P120T1（3）]解：18松弛問題B的最優(yōu)解：（4.8，0）最優(yōu)值96問題B的最優(yōu)解不是整數(shù)解，對(duì)該問題關(guān)于x1進(jìn)行分支：B1的最優(yōu)解為:(4，1)最優(yōu)值為90B2的可行解域?yàn)榭占撜麛?shù)線性規(guī)劃問題的最優(yōu)解就是（4，1），最優(yōu)值是90松弛問題B的最優(yōu)解：（4.8，0）最優(yōu)值96問題19用割平面法求解整數(shù)線性規(guī)劃問題[P120T2（1）]解：原問題記為A，將其松弛得到問題B：用割平面法求解整數(shù)線性規(guī)劃問題[P120T2（1）]解：20用對(duì)偶單純形法求得最優(yōu)解為（1.8，0.8），最優(yōu)值為11.2，最后一張單純形表為x1x2x3x4x5bx30010.3-1.14.2x2010-0.30.10.8x11000.2-0.41.8S0000.71.1-11.2用對(duì)偶單純形法求得最優(yōu)解為（1.8，0.8），最優(yōu)值為11.21x1x2x3x4x5x6bx30010.3-1.104.2x2010-0.30.100.8x11000.2-0.401.8x6000-0.2-0.61-0.8S0000.71.10-11.2用對(duì)偶單純形法求得最優(yōu)解為（2.3333，0.6667），最優(yōu)值為12.6667，最優(yōu)解不是整數(shù)解。最后一張單純形表為：將新約束條件加入到原規(guī)劃中，得到新的規(guī)劃問題：x1x2x3x4x5x6bx30010.3-1.104.2x22123456b30012/30-11/617/32010-1/301/62/311001/30-2/37/350001/31-5/34/300001/3011/6-38/3根據(jù)第四行得到新約束條件：將新約束條件加入到規(guī)劃中，得到新的規(guī)劃問題：123456b30012/30-11/617/32010-1231234567b30012/30-11/6017/32010-1/301/602/311001/30-2/307/350001/31-5/304/37000-10-11-100001/3011/60-38/3用對(duì)偶單純形法求解得到：1234567b30012/30-11/6017/32010241234567b300100-5/22/352010001/2-1/31110000-11/32500001-21/314000101-110000003/21/3-13最優(yōu)解為（2，1），最優(yōu)值為13.最優(yōu)解為整數(shù)解，故整數(shù)規(guī)劃問題的最優(yōu)解就是（2，1），最優(yōu)值為131234567b300100-5/22/352010001/25運(yùn)輸問題的初始調(diào)運(yùn)方案的編制

1.希奇柯克法:xiqikeke12.主對(duì)角線法:zhuduijiaoxian23.最小元素法:zuixiaoyuan34.小元素差額法:xiaoyuancha4運(yùn)輸問題的初始調(diào)運(yùn)方案的編制1.希奇柯