第19章線性優(yōu)化理論與方法19.1案例背景線性規(guī)劃是運籌學中研究較早、發(fā)展較快、應用廣泛、方法較成熟的一個重要分支,它是輔助人們進行科學管理的一種數(shù)學方法。在經(jīng)濟管理、交通運輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟活動中，提高經(jīng)濟效果是人們不可缺少的要求，而提高經(jīng)濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產(chǎn)工藝，使用新設備和新型原材料；二是生產(chǎn)組織與計劃的改進，即合理安排人力物力資源。線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟效果達到最好。19.1.1

線性規(guī)劃應用19.1.2

線性規(guī)劃的求解方法目前MATLAB求解線性規(guī)劃算法主要有內(nèi)點法（interiorpointmethods）與單純形法（simplexmethod）。單純形法（simplexmethod）是求解線性規(guī)劃問題的通用方法。它的理論根據(jù)是：線性規(guī)劃問題的可行域是n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。如果問題無最優(yōu)解也可用此法判別。單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問題的約束方程組表達成典型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數(shù)值更優(yōu)的另一基本可行解。④按步驟③進行迭代,直到對應檢驗數(shù)滿足最優(yōu)性條件（這時目標函數(shù)值不能再改善），即得到問題的最優(yōu)解。⑤若迭代過程中發(fā)現(xiàn)問題的目標函數(shù)值無界，則終止迭代。19.2線性模型建立線性規(guī)劃的標準數(shù)學模型為式中:A

為不等式約束的系數(shù)矩陣,b為不等式約束值向量,Aeq為等式約束的系數(shù)矩陣,beq為等式約束值向量,lb為x

取值下限,ub為x

取值上限。19.3線性優(yōu)化MATLAB求解19.3.1

linprog函數(shù)linprog的計算方法主要有兩個，分別為內(nèi)點法（interiorPointMethods）與單純形法（simplexmethod）。

函數(shù)語法：［x,fval,exitflag,output,lambda］=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)輸入?yún)?shù)：A：不等式約束系數(shù)矩陣；b：不等式約束常數(shù)向量；Aeq：等式約束系數(shù)矩陣；beq：等式約束常數(shù)向量；lb：x的可行域下界；ub：x的可行域上界；x0:初始迭代點(與linprog使用的算法有關)；options:優(yōu)化參數(shù)設置。輸出參數(shù)：x：最優(yōu)點（或者結束迭代點）。fval：最優(yōu)值（或者結束迭代點對應的函數(shù)值）。exitflag：迭代停止標識。1算法收斂于解x，即x是線性規(guī)劃的最優(yōu)解；0算法達到最大迭代次數(shù)停止迭代，即x不一定是線性規(guī)劃的最優(yōu)解；-2算法沒有找到可行解，即算法求解失敗，問題的可行解集合為空；-3原問題無解，即最有解可能為正（負）無窮大；-4在算法中出現(xiàn)除零問題或其他問題導致變量中出現(xiàn)非數(shù)值情況；-5線性規(guī)劃的原問題與對偶問題都不可解；-7可行搜索方向向量過小，無法再提高最優(yōu)解質(zhì)量。output：算法輸出（算法計算信息等）。Algorithm計算時使用的優(yōu)化算法；Cgiterations共軛梯度迭代次數(shù)（只有大規(guī)模算法時有）；iterations算法迭代次數(shù)；Exitmessage返回結束信息。lambda：最優(yōu)點（或者結束迭代點）拉格朗日乘子。Lower求得的解越下界；Upper求得的解越上界；Neqlin求得的解不滿足不等式約束；Eqlin求得的解不滿足等式約束。19.3.2

線性規(guī)劃目標函數(shù)線性規(guī)劃目標函數(shù)如下:使用[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub)19.3.3

內(nèi)點法求解調(diào)用linprog使用默認算法（linprog的默認算法為內(nèi)點法）計算線性規(guī)劃問題，M文件為linprogtest1.m。計算結果Commandwindow輸出。19.3.4

單純形法求解設置linprog使用單純形法，且顯示每次迭代計算結果。調(diào)用linprog進行計算。計算結果Commandwindow輸出。19.4含參數(shù)線性規(guī)劃在研究工作中，常常有不同的背景假設或參數(shù)假設，不同的參數(shù)假設會有不同的模型。例如：對應不同參數(shù)