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

線性規(guī)劃問題的求解方法第一頁，共二十八頁，編輯于2023年，星期三一、利用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ù)第二頁，共二十八頁，編輯于2023年，星期三3.求解線性規(guī)劃問題格式為：x=linprog(f,A,b,Aeq,beq,LB,UB)[x,fval]=linprog(f,A,b,Aeq,beq,LB,UB)注：這里x、b不要求非負(fù)第三頁，共二十八頁，編輯于2023年，星期三例3.1例3.2第四頁，共二十八頁，編輯于2023年，星期三例3.3例3.5第五頁，共二十八頁，編輯于2023年，星期三例3.6第六頁，共二十八頁，編輯于2023年，星期三P75T2（5）P75T2（6）第七頁，共二十八頁，編輯于2023年，星期三P75T2（10）第八頁，共二十八頁，編輯于2023年，星期三二、利用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)“！”開始的是說明語句。第九頁，共二十八頁，編輯于2023年，星期三例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第十頁，共二十八頁，編輯于2023年，星期三例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第十一頁，共二十八頁，編輯于2023年，星期三例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第十二頁，共二十八頁，編輯于2023年，星期三model:!線性規(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));end第十三頁，共二十八頁，編輯于2023年，星期三三、自編MATLAB程序求解dan0求解特殊線性規(guī)劃問題dan0-bland用bland法則求解特殊線性規(guī)劃問題dan0-improve用改進(jìn)的單純形法求解線性規(guī)劃問題danm用大M法求解線性規(guī)劃問題dan2用兩階段法求解線性規(guī)劃問題第十四頁，共二十八頁，編輯于2023年，星期三特殊的線性規(guī)劃問題要求輸入的數(shù)據(jù)（第一張單純形表，典式）3101004401010351200180-2-50000基變量下標(biāo)增廣系數(shù)矩陣目標(biāo)函數(shù)的系數(shù)的相反數(shù)標(biāo)準(zhǔn)線性規(guī)劃問題要求輸入的數(shù)據(jù):去掉上表最左邊的一列第十五頁，共二十八頁，編輯于2023年，星期三用分支定界法求解整數(shù)規(guī)劃問題[書P120T1（1）]解：原問題記為A，將該問題進(jìn)行松弛，得到問題B：第十六頁，共二十八頁，編輯于2023年，星期三松弛問題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)榭占谑唔?，共二十八頁，編輯?023年，星期三對(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第十八頁，共二十八頁，編輯于2023年，星期三用分支定界法求解整數(shù)規(guī)劃問題[書P120T1（3）]解：原問題記為A，將該問題進(jìn)行松弛，得到問題B：第十九頁，共二十八頁，編輯于2023年，星期三松弛問題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第二十頁，共二十八頁，編輯于2023年，星期三用割平面法求解整數(shù)線性規(guī)劃問題[P120T2（1）]解：原問題記為A，將其松弛得到問題B：第二十一頁，共二十八頁，編輯于2023年，星期三用對(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第二十二頁，共二十八頁，編輯于2023年，星期三x1x2x3x4x5x6bx30010.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ī)劃問題：第二十三頁，共二十八頁，編輯于2023年，星期三123456b30012/30-11/617/32010-1/301/62/311001/30-2/37/350001/31-5/34/300001/3011/6-38/3根據(jù)第四行得到新約束條件：將新約束條件加入到規(guī)劃中，得到新的規(guī)劃問題：第二十四頁，共二十八頁，編輯于2023年，星期三1234567b30012/30-11/6017/32010-1/301/602/311001/30-2/307/350001/31-5/304/37000-10-11-100001/3011/60-38/3用對(duì)偶單純形法求解得到：第二十五頁，共二十八頁，編輯于2023年，星期三1234567b300100-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)值為13第二十六頁，共二十八頁，編輯于2023年，星期三運(yùn)輸問題的初始調(diào)運(yùn)方案的編制

1.希奇柯克法:xiqikeke12.主對(duì)角線法:zhuduijiaoxian23.最小元素法:zuixiaoyuan34.小元素差額法:xiaoyuancha4第二十七頁，共二十八頁，編