應(yīng)用LINGO、MATLAB軟件求解線性規(guī)劃.ppt

,1.5 應(yīng)用LINGO、MATLAB軟件求解線性規(guī)劃,1.5.1 應(yīng)用LINGO軟件求解線性規(guī)劃,一、LINGO使用簡介 LINGO軟件是美國的LINDO系統(tǒng)公司（Lindo System Inc）開發(fā)的一套用于求解最優(yōu)化問題的軟件包。LINGO除了能用于求解線性規(guī)劃和二次規(guī)劃外，還可以用于非線性規(guī)劃求解以及一些線性和非線性方程（組）的求解等。LINGO軟件的最大特色在于它允許優(yōu)化模型中的決策變量為整數(shù)，而且執(zhí)行速度快。LINGO內(nèi)置了一種建立最優(yōu)化模型的語言，可以簡便地表達大規(guī)模問題，利用LINGO高效的求解器可快速求解并分析結(jié)果，這里簡單介紹LINGO的使用方法。 LINGO可以求解線性規(guī)劃、二次規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、圖論及網(wǎng)絡(luò)優(yōu)化和排隊論模型中的最優(yōu)化問題等。,一個LINGO程序一般會包含集合段、數(shù)據(jù)輸入段、優(yōu)化目標和約束段、初始段和數(shù)據(jù)預(yù)處理段等部分，每一部分有其獨特的作用和語法規(guī)則，讀者可以通過查閱相關(guān)的參考書或者LINGO的HELP文件詳細了解，這里就不展開介紹了。,LINGO的主要功能特色為：既能求解線性規(guī)劃問題，也有較強的求解非線性規(guī)劃問題的能力；輸入模型簡練直觀；運算速度快、計算能力強；內(nèi)置建模語言，提供幾十個內(nèi)部函數(shù)，從而能以較少語句，較直觀的方式描述大規(guī)模的優(yōu)化模型；將集合的概念引入編程語言，很容易將實際問題轉(zhuǎn)換為LINGO模型；并且能方便地與Excel、數(shù)據(jù)庫等其他軟件交換數(shù)據(jù)。,LINGO的語法規(guī)定： （1）求目標函數(shù)的最大值或最小值分別用MAX=或MIN=來表示； （2）每個語句必須以分號“；”結(jié)束，每行可以有許多語句，語句可以跨行； （3）變量名稱必須以字母(AZ)開頭，由字母、數(shù)字(09)和下劃線所組成，長度不超過32個字符，不區(qū)分大小寫； （4）可以給語句加上標號，例如OBJMAX=200*X1+300*X2； （5）以驚嘆號“！”開頭，以分號“；”結(jié)束的語句是注釋語句; （6）如果對變量的取值范圍沒有作特殊說明，則默認所有決策變量都非負； （7）LINGO模型以語句“MODEL：”開頭，以“END”結(jié)束，對于比較簡單的模型，這兩個語句可以省略。,在LINGO的MODEL窗口內(nèi)輸入如下模型： model: max=2*x1+3*x2; x1+2*x2=8; 4*x1=16; 4*x2=12; End,例1.5.1 用LINGO求解例1.1.2。 解 例1.1.2建立的線性規(guī)劃數(shù)學(xué)模型為（1.1.4）,選菜單Lingo|Solve(或按Ctrl+S),或用鼠標點擊“求解”按紐，如果模型有語法錯誤，則彈出一個標題為“LINGO Error Message”(錯誤信息)的窗口，指出在哪一行有怎樣的錯誤，每一種錯誤都有一個編號（具體含義可查閱相關(guān)文獻或LINGO的Help）。改正錯誤以后再求解，如果語法通過, LINGO用內(nèi)部所帶的求解程序求出模型的解, 然后彈出一個標題為“LINGO Solver Status”(求解狀態(tài))的窗口, 其內(nèi)容為變量個數(shù)、約束條件個數(shù)、優(yōu)化狀態(tài)、耗費內(nèi)存、所花時間等信息, 點擊Close關(guān)閉窗口, 屏幕上出現(xiàn)標題為“Solution Report”(解的報告)的信息窗口, 顯示優(yōu)化計算(線性規(guī)劃中換基迭代)的步數(shù)、優(yōu)化后的目標函數(shù)值、列出各變量的計算結(jié)果。本例的具體內(nèi)容如下：,Global optimal solution found at iteration: 5 Objective value: 14.00000 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price 1 14.00000 1.000000 2 0.000000 1.500000 3 0.000000 0.1250000 4 4.000000 0.000000,該報告說明：運行5步找到全局最優(yōu)解，目標函數(shù)值為14，變量值分別為 ?！癛educed Cost”的含義是需縮減成本系數(shù)或需增加利潤系數(shù)（最優(yōu)解中取值非零的決策變量的Reduced Cost值等于零）?！癛ow”是輸入模型中的行號，目標函數(shù)是第一行；“Slack or Surplus”的意思是松弛或剩余，即約束條件左邊與右邊的差值，對于“ ”的不等式，右邊減左邊的差值為Slack（松弛），對于“ ”的不等式，左邊減的右邊差值為Surplus（剩余），當約束條件兩邊相等時，松弛或剩余的值等于零?！癉ual Price”的意思是對偶價格（或稱為影子價格，意義見2.5），上述報告中Row2的松弛值為0，表明生產(chǎn)甲產(chǎn)品4單位、乙產(chǎn)品2單位，所需設(shè)備8臺時已經(jīng)飽和，對偶價格1.5的含義是：如果設(shè)備增加1臺時，能使目標函數(shù)值增加1.5。報告中Row4的松弛值為4，表明生產(chǎn)甲產(chǎn)品4單位、乙產(chǎn)品2單位，所需原材料乙8公斤還剩余4公斤，因此增加原材料乙不會使目標函數(shù)值增加，所以對偶價格為0。,在LINGO的MODEL窗口內(nèi)輸入如下模型： Min=0.2*x1+0.7*x2+0.4*x3+0.3*x4+0.5*x5; 0.3*x1+2*x2+x3+0.6*x4+1.8*x560; 0.1*x1+0.05*x2+0.02*x3+0.2*x4+0.05*x53; 0.05*x1+0.1*x2+0.02*x3+0.2*x4+0.08*x58; X1+x2+x3+x4+x552;,例1.5.2 用LINGO求解例1.1.3食譜問題。 解 例1.1.3食譜問題的數(shù)學(xué)模型為（1.1.6）,求解輸出結(jié)果如下: Global optimal solution found at iteration: 4 Objective value: 22.40000 Variable Value Reduced Cost X1 0.000000 0.7000000 X2 12.00000 0.000000 X3 0.000000 0.6166667 X4 30.00000 0.000000 X5 10.00000 0.000000 Row Slack or Surplus Dual Price 1 22.40000 -1.000000 2 0.000000 -0.5833333 3 4.100000 0.000000 4 0.000000 -4.166667 5 0.000000 0.8833333,因此,每周每個動物的配料為飼料A2、A4、A5分別為12、30和10，合計為52，可使得飼養(yǎng)成本達到最小，最小成本為22.4元；不選用飼料和的原因是因為這兩種飼料的價格太高了，沒有競爭力?！癛educed Cost”分別等于0.7和0.617，說明當這兩種飼料的價格分別降低0.7元和0.62元以上時，不僅選用這兩種飼料而且使得飼養(yǎng)成本降低。從“Slack or Surplus”可以看出，蛋白質(zhì)和維生素剛達到最低標準，礦物質(zhì)超過最低標準4.1；從“Dual Price”可以得到降低標準蛋白質(zhì)1單位可使飼養(yǎng)成本降低0.583元，降低標準維生素1單位可使飼養(yǎng)成本降低4.167元，但降低礦物質(zhì)的標準不會降低飼養(yǎng)成本，如果動物的進食量減少，就必須選取精一些的飼料但要增加成本，大約進食量降低1可使得飼養(yǎng)成本增加0.88元。,(1.5.1),1.5.2 應(yīng)用MATLAB求解線性規(guī)劃,MATLAB（MATrix LABoratory）的基本含義是矩陣實驗室，它是由美國MathWorks公司研制開發(fā)的一套高性能的集數(shù)值計算、信息處理、圖形顯示等于一體的可視化數(shù)學(xué)工具軟件。它是建立在向量、數(shù)組和矩陣基礎(chǔ)之上的，除了基本的數(shù)值計算、數(shù)據(jù)處理、圖形顯示等功能之外，還包含功能強大的多個“工具箱”，如優(yōu)化工具箱（optimization toolbox）、統(tǒng)計工具箱、樣條函數(shù)工具箱和數(shù)據(jù)擬合工具箱等都是優(yōu)化計算的有力工具。在這里僅介紹用MATLAB6.5優(yōu)化工具箱求解線性規(guī)劃問題。 一般線性規(guī)劃問題的數(shù)學(xué)模型為,其中C是目標函數(shù)的系數(shù)行向量（常數(shù)）, X 是n維列向量（決策變量），A, A1是常數(shù)矩陣，b,b1是常數(shù)向量，lb,ub是n維列向量分別表示決策變量X的下界與上界。 在Matlab優(yōu)化工具箱（Optimization Toolbox）中，求解(1.5.1)的程序如下：x，fval，exitflag，output，lambda = linprog (c，A，b，Aeq，beq，lb，ub，x0，options) 說明：(1)A是不等式約束的系數(shù)矩陣，b是相應(yīng)的常數(shù)列向量，若沒有不等式約束，則均用 代替； (2) Aeq是等式約束的系數(shù)矩陣，beq是相應(yīng)的常數(shù)列向量，若沒有等式約束，則均用代替； (3)如果某個變量無下界，則用-inf表示；如果某個變量無上界，則用inf表示，若決策變量 無下界，則lb用代替；若決策變量 無上界，則ub用代替； (4) x0是線性規(guī)劃的初始解，這種設(shè)計僅對中規(guī)模算法有效，通?？梢匀笔　?(5) 輸出 是最優(yōu)解，fval是最優(yōu)值。 (6) 輸出exitflag描述了程序的運行情況，若其值大于零，表示程序收斂到最優(yōu)解 ；若其值等于零，表示計算達到了最大次數(shù)；若其值小于零，表示問題無可行解，或程序運行失敗。 (7)輸出output表示程序運行的某些信息，如迭代次數(shù)(iterations)、所用算法(algorithm)、共軛梯度(cgiterations)等。 (8)lambda表示解處的拉格朗日乘子，其中l(wèi)ower，upper，ineqlin，eqlin分別對應(yīng)于下界、上界、不等式約束與等式約束。,解 Matlab程序如下: c=-2,-1,1; A=1,4,-1;2,-2,1; b=4;12; Aeq=1,1,2; beq=6; lb=0,0,-inf; ub=inf,inf,5; x,z=linprog(c,A,b,Aeq,beq,lb,ub) 運行后得到輸出 Optimization terminated successfully. x= 4.6667 0.0000 0.6667 z= -8.6667,例1.5.4 用MATLAB求解線性規(guī)劃問題,（1.5.3）,解 首先轉(zhuǎn)化為求最小值問題,Matlab程序如下 c=-2,-3,5; A=-2,5,-1; b=-10; Aeq=1,1,1; beq=7; lb=0,0,0; x,z=linprog(c,A,b,Aeq,beq,lb),運行后得到輸出 x = 6.4286 0.5714 0.0000 z = -14.5714 鍵入 s=-z 運行后得到原問題的目標函數(shù)最大值 s=14.5714,用MATLAB求解例1.5.2的程序與輸出結(jié)果為： c=0.2,0.7,0.4,0.3,0.5; A=-0.3,-2,-1,-0.6,-1.8;-0.1,-0.05,-0.02,-0.2,-0.05;-0.05,-0.1,-0.02,-0.2,-0.08;1,1,1,1,1; b=-60;-3;-8;52; lb=0,0,0,0,0; x,z=linprog(c,A,b,lb),Optimization terminated successfully. x = 0.0000 12.0000 0.0000 30.0000 10.0000 z = 22.4000,習(xí)題1 1.建立下列線性規(guī)劃問題的數(shù)學(xué)模型 （1）某工廠生產(chǎn)A、B、C三種產(chǎn)品，三種產(chǎn)品對于材料費用、勞動力和電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價格如表1.1所示。問應(yīng)如何確定生產(chǎn)計劃可使得總產(chǎn)值達到最大？建立線性規(guī)劃問題的數(shù)學(xué)模型。,表1.1 生產(chǎn)計劃問題的數(shù)據(jù),（2）某療養(yǎng)院營養(yǎng)師要為某類病人擬訂一周的菜單?？晒┻x擇的蔬菜及其費用和所含營養(yǎng)成分的數(shù)量以及這類病人每周所需各種營養(yǎng)成分的最低數(shù)量如表1.2所示。另外，為了口味的需要，規(guī)定一周內(nèi)所用卷心菜不多于2份，其他蔬菜不多于4份。若病人每周需要14份蔬菜，問選用每種蔬菜各多少份，可使生活費用最小。建立線性規(guī)劃問題的數(shù)學(xué)模型。,表1.2 食譜問題的數(shù)據(jù),（4）某糖果廠用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙，已知各種牌號的糖果中A、B、C的含量，原料成本，各種原料的每月限制用量，三種牌號糖果的單位加工費及售價如表1.4所示，問該廠每月應(yīng)生產(chǎn)這三種牌號的糖果各多少千克，使該廠獲利最大？試建立這個問題的線性規(guī)劃數(shù)學(xué)模型。,表1.4 糖果廠生產(chǎn)計劃數(shù)據(jù)表,表1.5 隨 變化的數(shù)據(jù)表,求擬合以上數(shù)據(jù)的直線 ，目標為使y的各個觀察值同按直線關(guān)系所預(yù)期的值的絕對偏差總和為最?。矗赫`差絕對值之和最?。＝⒕€性規(guī)劃問題的數(shù)學(xué)模型。 （提示：對任意的 ，令： 那么， ）,2.將下列線性規(guī)劃問題化成標準形,(1),(2),3.用圖解法求解下列線性規(guī)劃問題,(1),(2),(3),(4),(5),4.試將下述問題改寫成線性規(guī)劃問題,8.用單純形方法求解下列線性規(guī)劃問題,(1),(2),(3),(4),9某工廠在計劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制和每單位產(chǎn)品的獲利如表1.6。問工廠應(yīng)分別生產(chǎn)甲、乙產(chǎn)品多少單位才能使