1、線性規(guī)劃求解線性規(guī)劃求解Matlab的優(yōu)化工具箱：Optimization Toolbox線性規(guī)劃的一般形式max Z = c1x1 + c2x2 + . + cnxn （或（或min）s.t. a11x1 + a12x2 + . + a1nxn b1 (=或或 ) a21x1 + a22x2 + . + a2nxn b2 (=或或 ) . . . . . . am1x1 +am2x2 + .+ amnxn bm (=或或 ) x1, x2, ., xn 0max. .0TZc XAXbstX112211121121222212=,=,=,=nnnnmmmnmcxcxcXcxaaabaaabA

2、baaab其中：線性規(guī)劃的Matlab標(biāo)準(zhǔn)形式min Z = c1x1 + c2x2 + . + cnxns.t. a11x1 + a12x2 + . + a1nxn b1 a21x1 + a22x2 + . + a2nxn b2 . . . . . . am1x1 + am2x2 + . + amnxn bm aeq11x1 + aeq12x2 + . + aeq1nxn = beq1 aeq21x1 + aeq22x2 + . + aeq2nxn = beq2 . . . . . . aeqh1x1 + aeqh2x2 + . + aeqhnxn = beqh lx1 x1 ux1, lx

3、2 x2 ux2, ., lxn xn uxn注意！注意?。? 1）最小化問題；）最小化問題；（2 2）約束分成兩組；）約束分成兩組；（3 3）決策變量給出下界和上界；）決策變量給出下界和上界；線性規(guī)劃的Matlab標(biāo)準(zhǔn)形式的矩陣表示min. .TeqeqZC XAXbs tA XblbXub11112122122211221112112122221212=,=,=,=,=,=nnnneqeqeqeqneeqeqeqneqeqeqeqeqmmmnmhhhncxcxcXcxbaaaaaabbaaabaaaAbAbaaabaaa其中：1122,hqeqxxxxxnxnblululbubluMatl

4、ab使用linprog函數(shù)求解線性規(guī)劃x = linprog(c, A, b)x = linprog(c, A, b, Aeq, beq)x = linprog(c, A, b, Aeq, beq, lb, ub)x = linprog(c, A, b, Aeq, beq, lb, ub, x0)x = linprog(c, A, b, Aeq, beq, lb, ub, x0, options)x, fval = linprog(。)x, fval, exitflag = linprog(。) x, fval, exitflag, output = linprog(。)x, fval, ex

5、itflag, output, lambda = linprog(。) help linprog help linprog例1 c=-2; -3; A=2 2; 1 2; 4 0; 0 4; b=12; 8; 16; 12; x=linprog(c, A, b) fval=c*x12121212max23221228. .416412Zxxxxxxs txx 2=32212128=,=,=,=40160412,eqeqcAbAblbub例2 c=-5; -1.5; A=0 5; 6 2; 1 1; b=15; 24; 5; Aeq=; beq=; lb=0; 0; ub=; % ub=inf;

6、 inf x=linprog(c, A, b, Aeq, beq, lb, ub)122121212max51.55156224. .500Zxxxxxs txxxx 5=1.50515= 62 ,= 24 ,=,=1150,0eqeqcAbAblbub 例3 c=-4; 2; -1; A=2 -1 1; 8 -2 2; b=12; -8; Aeq=-2 0 1; 1 1 0; beq=3; 7; lb=0; 0; 0; ub=; x=linprog(c, A, b, Aeq, beq, lb, ub) 4=2121112=,=,82282013=,=110700 ,0eqeqcAbAblbu

7、b123123231312123max422128 1228. .237000Zxxxxxxxxxstxxxxxxx輸入?yún)?shù)說明c目標(biāo)函數(shù)中的系數(shù)向量行、列形式均可A b不等式約束對(duì)應(yīng)的矩陣和常數(shù)列若沒有不等式約束，則 A = ; b = Aeqbeq等式約束對(duì)應(yīng)的矩陣和常數(shù)列若沒有等式約束，則 Aeq = ; beq = lbub決策變量的上界和下界若所有變量上界或下界無限制，則lb= ; 或 ub= ;若某個(gè)變量i的上界或下界無限制，則取lb(i) = -inf 或 ub(i) = infx0迭代初始點(diǎn)只適用于active-set算法，默認(rèn)時(shí)大型算法將忽略初值。options用于指定優(yōu)化的

8、控制參數(shù)options用于指定優(yōu)化的控制參數(shù)options = optimset(param1, value1, param2, value2, );示例：options = optimset(LargeScale, off, Simplex, on);表示不采用大規(guī)模算法，采用單純形發(fā)求解；options = optimset(Display,iter,TolFun,1e-8); 表示給出每一步迭代結(jié)果，計(jì)算誤差限位1e-8；options用于指定優(yōu)化的控制參數(shù)參數(shù)名稱參數(shù)設(shè)置Diagnosticson 或off（默認(rèn)值）設(shè)置是否顯示優(yōu)化中的診斷信息，特別是計(jì)算終止的原因；Displayof

9、f（默認(rèn)值）：不顯示任何輸出信息；iter：顯示每一步的迭代信息；final：僅顯示最終的輸出信息；Simplex該參數(shù)值為on時(shí)，采用單純形算法；LargeScaleon（默認(rèn)值）：采用大型規(guī)模算法；off：采用中性規(guī)模算法；MaxIter設(shè)置算法的最大迭代次數(shù)大型規(guī)模算法：默認(rèn)85；單純形算法：默認(rèn)10*決策變量數(shù)；TolFun函數(shù)計(jì)算終止的誤差限大型規(guī)模算法：默認(rèn)1e-8；單純形算法：默認(rèn)1e-6； help linprog help linprog help optimset help optimset輸出參數(shù)說明（1）x由優(yōu)化函數(shù)求得的值若exitflag0，則x為解；否則，x只是迭

10、代終止時(shí)的值。fval解x處的目標(biāo)函數(shù)值exitflag描述退出條件 1：目標(biāo)函數(shù)收斂于解x處； 0：已經(jīng)達(dá)到最大的迭代次數(shù)限制ptions.MaxIter;-2：沒有找到可行解；-3：問題無有限最優(yōu)解；-4：算法執(zhí)行過程中遇到NaN值；-5：原問題和對(duì)偶問題均不可行；例2 c=-5; -1.5; A=0 5; 6 2; 1 1; b=15; 24; 5; Aeq=; beq=; lb=0; 0; ub=inf; inf; x0=; options=optimset(LargeScale, off, Simplex, on); x, fval, exitflag, output . =linp

11、rog(c, A, b, Aeq, beq, lb, ub, x0, options);輸出參數(shù)說明（2）output包含優(yōu)化結(jié)果信息的結(jié)構(gòu).iterations：實(shí)際的迭代次數(shù)；.algorithm：所采用的算法；.cgiterations：0； （僅用于大型算法，為向后兼容而 設(shè)置的參數(shù)）.message：退出信息；lambda包含解x處的拉格朗日乘子的結(jié)構(gòu).ineqlin：線性不等式約束的拉格朗日乘子；.eqlin：等式約束的拉格朗日乘子；.upper：上界約束的拉格朗日乘子；.lower：下界約束的拉格朗日乘子；例4：求最優(yōu)生產(chǎn)計(jì)劃，使公司獲利最大設(shè)某公司生產(chǎn)另種產(chǎn)品：食物（x1），

12、服裝（x2）生產(chǎn)單位食品獲利40元，單位服裝獲利30元需要投入三種資源：土地（H）、勞動(dòng)（L)、資本（K)生產(chǎn)一個(gè)單位食品投入：3H 2L 1K生產(chǎn)一個(gè)單位服裝投入：2H 2L 2K公司擁有：54H 40L 35K1212121212max403032542240. .23500Zxxxxxxs txxxxlambda給出影子價(jià)格 f=-40; -30; A=3 2; 2 2; 1 2; b=54; 40; 35; lb=0; 0; x, fval, exitflag, output, lambda =linprog(f, A, b, , , lb, ) lambda.ineqlin 實(shí)驗(yàn)將土

13、地資源增加一個(gè)單位后的最優(yōu)值！ 1212121212max403032542240. .23500Zxxxxxxs txxxx工具箱GUI界面 Start按鈕 toolboxesoptimization optimization tool對(duì)偶性質(zhì)驗(yàn)證若原問題有最優(yōu)解，則對(duì)偶問題也有最優(yōu)解，且： 對(duì)偶問題的解是原問題的影子價(jià)格； 對(duì)偶問題與原問題的最優(yōu)值相等；若互為對(duì)偶問題中一個(gè)有可行解，但無最優(yōu)解，則另一個(gè)無可行解。123123123123min5440353240. .22230000Wyyyyyys tyyyyyy1212121212max403032542240. .23500Zxxxx

14、xxs txxxxLingo/LindoLingo：Linear Interactive and General OptimizerLindo：Linear Interactive and Discrete Optimizer由美國芝加哥大學(xué)的Linus Scharge教授于1980年前后開發(fā)，專門用于求解最優(yōu)化問題，后經(jīng)不斷完善和擴(kuò)充，并成立LINDO公司進(jìn)行商業(yè)化運(yùn)作，取得巨大的成功。特色在于可以允許決策變量是整數(shù)，執(zhí)行速度很快；Lingo實(shí)際上還是一種建模語言，即使對(duì)優(yōu)化方面的專業(yè)知識(shí)了解不多的用戶，也能方便的進(jìn)行輸入、求解，并能快速的得到復(fù)雜優(yōu)化問題的高質(zhì)量的解。Lingo/Lindo

15、優(yōu)化模型優(yōu)化模型連續(xù)模型連續(xù)模型整數(shù)模型整數(shù)模型線性規(guī)劃線性規(guī)劃二次規(guī)劃二次規(guī)劃非線性規(guī)劃非線性規(guī)劃LindoLingo簡單示例max = 40*x1 + 30*x2;3*x1 + 2*x2 =54;2*x1 + 2*x2 = 40;x1 + 2*x2 = 0;x2 = 0;1212121212max403032542240. .23500Zxxxxxxs txxxx第一行對(duì)應(yīng)目標(biāo)函數(shù)，從第二行起對(duì)應(yīng)約束！第一行對(duì)應(yīng)目標(biāo)函數(shù)，從第二行起對(duì)應(yīng)約束！Report結(jié)果說明Reduced Cost： 最優(yōu)單純形表中目標(biāo)函數(shù)行中變量對(duì)應(yīng)的系數(shù)； 表示為了使某個(gè)非基變量在解中的數(shù)值增加一個(gè)單位，目標(biāo)函數(shù)值必須付出的代價(jià)； 在一個(gè)最大值的模型中，對(duì)應(yīng)的非基變量增加一個(gè)單位，目標(biāo)值會(huì)減少Reduced Cost； 在一個(gè)最小值