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

應(yīng)用LINGO、MATLAB軟件求解線性規(guī)劃1a一、LINGO使用簡(jiǎn)介

LINGO軟件是美國的LINDO系統(tǒng)公司（LindoSystemInc）開發(fā)的一套用于求解最優(yōu)化問題的軟件包。LINGO除了能用于求解線性規(guī)劃和二次規(guī)劃外，還可以用于非線性規(guī)劃求解以及一些線性和非線性方程（組）的求解等。LINGO軟件的最大特色在于它允許優(yōu)化模型中的決策變量為整數(shù)，而且執(zhí)行速度快。LINGO內(nèi)置了一種建立最優(yōu)化模型的語言，可以簡(jiǎn)便地表達(dá)大規(guī)模問題，利用LINGO高效的求解器可快速求解并分析結(jié)果，這里簡(jiǎn)單介紹LINGO的使用方法。

LINGO可以求解線性規(guī)劃、二次規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、圖論及網(wǎng)絡(luò)優(yōu)化和排隊(duì)論模型中的最優(yōu)化問題等。2a一個(gè)LINGO程序一般會(huì)包含集合段、數(shù)據(jù)輸入段、優(yōu)化目標(biāo)和約束段、初始段和數(shù)據(jù)預(yù)處理段等部分，每一部分有其獨(dú)特的作用和語法規(guī)則，讀者可以通過查閱相關(guān)的參考書或者LINGO的HELP文件詳細(xì)了解，這里就不展開介紹了。3aLINGO的主要功能特色為：1、既能求解線性規(guī)劃問題，也有較強(qiáng)的求解非線性規(guī)劃問題的能力；2、輸入模型簡(jiǎn)練直觀；3、運(yùn)算速度快、計(jì)算能力強(qiáng)；4、內(nèi)置建模語言，提供幾十個(gè)內(nèi)部函數(shù)，從而能以較少語句，較直觀的方式描述大規(guī)模的優(yōu)化模型；5、將集合的概念引入編程語言，很容易將實(shí)際問題轉(zhuǎn)換為L(zhǎng)INGO模型；并且能方便地與Excel、數(shù)據(jù)庫等其他軟件交換數(shù)據(jù)。4aLINGO的語法規(guī)定：（1）求目標(biāo)函數(shù)的最大值或最小值分別用MAX=…或MIN=…來表示；（2）每個(gè)語句必須以分號(hào)“；”結(jié)束，每行可以有許多語句，語句可以跨行；（3）變量名稱必須以字母(A~Z)開頭，由字母、數(shù)字(0~9)和下劃線所組成，長(zhǎng)度不超過32個(gè)字符，不區(qū)分大小寫；（4）可以給語句加上標(biāo)號(hào)，例如[OBJ]MAX=200*X1+300*X2；（5）以驚嘆號(hào)“！”開頭，以分號(hào)“；”結(jié)束的語句是注釋語句;（6）如果對(duì)變量的取值范圍沒有作特殊說明，則默認(rèn)所有決策變量都非負(fù)；（7）LINGO模型以語句“MODEL：”開頭，以“END”結(jié)束，對(duì)于比較簡(jiǎn)單的模型，這兩個(gè)語句可以省略。5a在LINGO的MODEL窗口內(nèi)輸入如下模型：model:max=2*x1+3*x2;x1+2*x2<=8;4*x1<=16;4*x2<=12;End例

用LINGO求解線性規(guī)劃問題：6a選菜單Lingo|Solve(或按Ctrl+U),或用鼠標(biāo)點(diǎn)擊“求解”按紐，如果模型有語法錯(cuò)誤，則彈出一個(gè)標(biāo)題為“LINGOErrorMessage”(錯(cuò)誤信息)的窗口，指出在哪一行有怎樣的錯(cuò)誤，每一種錯(cuò)誤都有一個(gè)編號(hào)（具體含義可查閱相關(guān)文獻(xiàn)或LINGO的Help）。改正錯(cuò)誤以后再求解，如果語法通過,LINGO用內(nèi)部所帶的求解程序求出模型的解,然后彈出一個(gè)標(biāo)題為“LINGOSolverStatus”(求解狀態(tài))的窗口,其內(nèi)容為變量個(gè)數(shù)、約束條件個(gè)數(shù)、優(yōu)化狀態(tài)、耗費(fèi)內(nèi)存、所花時(shí)間等信息,點(diǎn)擊Close關(guān)閉窗口,屏幕上出現(xiàn)標(biāo)題為“SolutionReport”(解的報(bào)告)的信息窗口,顯示優(yōu)化計(jì)算(線性規(guī)劃中換基迭代)的步數(shù)、優(yōu)化后的目標(biāo)函數(shù)值、列出各變量的計(jì)算結(jié)果。7a本例的具體內(nèi)容如下：Globaloptimalsolutionfoundatiteration:5VariableValueReducedCostRowSlackorSurplusDualPrice8a該報(bào)告說明：運(yùn)行5步找到全局最優(yōu)解，目標(biāo)函數(shù)值為14，變量值分別為。“ReducedCost”的含義是需縮減成本系數(shù)或需增加利潤(rùn)系數(shù)（最優(yōu)解中取值非零的決策變量的ReducedCost值等于零）?！癛ow”是輸入模型中的行號(hào)，目標(biāo)函數(shù)是第一行；“SlackorSurplus”的意思是松弛或剩余，即約束條件左邊與右邊的差值，對(duì)于“”的不等式，右邊減左邊的差值為Slack（松弛），對(duì)于“”的不等式，左邊減的右邊差值為Surplus（剩余），當(dāng)約束條件兩邊相等時(shí)，松弛或剩余的值等于零。9a“DualPrice”的意思是對(duì)偶價(jià)格（或稱為影子價(jià)格），上述報(bào)告中Row2的松弛值為0，表明生產(chǎn)甲產(chǎn)品4單位、乙產(chǎn)品2單位，所需設(shè)備8臺(tái)時(shí)已經(jīng)飽和，對(duì)偶價(jià)格的含義是：如果設(shè)備增加1臺(tái)時(shí)，能使目標(biāo)函數(shù)值增加。報(bào)告中Row4的松弛值為4，表明生產(chǎn)甲產(chǎn)品4單位、乙產(chǎn)品2單位，所需原材料乙8公斤還剩余4公斤，因此增加原材料乙不會(huì)使目標(biāo)函數(shù)值增加，所以對(duì)偶價(jià)格為0。10a在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*x5>60;0.1*x1+0.05*x2+0.02*x3+0.2*x4+0.05*x5>3;0.05*x1+0.1*x2+0.02*x3+0.2*x4+0.08*x5>8;X1+x2+x3+x4+x5<52;例1.2用LINGO求解如下問題11a求解輸出結(jié)果如下:Globaloptimalsolutionfoundatiteration:4VariableValueReducedCostRowSlackorSurplusDualPrice12a(1.1)1.2應(yīng)用MATLAB求解線性規(guī)劃MATLAB（MATrixLABoratory）的基本含義是矩陣實(shí)驗(yàn)室，它是由美國MathWorks公司研制開發(fā)的一套高性能的集數(shù)值計(jì)算、信息處理、圖形顯示等于一體的可視化數(shù)學(xué)工具軟件。它是建立在向量、數(shù)組和矩陣基礎(chǔ)之上的，除了基本的數(shù)值計(jì)算、數(shù)據(jù)處理、圖形顯示等功能之外，還包含功能強(qiáng)大的多個(gè)“工具箱”，如優(yōu)化工具箱（optimizationtoolbox）、統(tǒng)計(jì)工具箱、樣條函數(shù)工具箱和數(shù)據(jù)擬合工具箱等都是優(yōu)化計(jì)算的有力工具。在這里僅介紹用優(yōu)化工具箱求解線性規(guī)劃問題。一般線性規(guī)劃問題的數(shù)學(xué)模型為13a其中C是目標(biāo)函數(shù)的系數(shù)行向量（常數(shù)）,X是n維列向量（決策變量），A,A1是常數(shù)矩陣，b,b1是常數(shù)向量，lb,ub是n維列向量分別表示決策變量X的下界與上界。在Matlab優(yōu)化工具箱（OptimizationToolbox）中，求解線性規(guī)劃的程序如下：[x，fval，exitflag，output，lambda]=linprog(c，A，b，Aeq，beq，lb，ub，x0，options)，具體說明見下頁。14a說明：(1)A是不等式約束的系數(shù)矩陣，b是相應(yīng)的常數(shù)列向量，若沒有不等式約束，則均用[]代替；(2)Aeq是等式約束的系數(shù)矩陣，beq是相應(yīng)的常數(shù)列向量，若沒有等式約束，則均用[]代替；(3)如果某個(gè)變量無下界，則用-inf表示；如果某個(gè)變量無上界，則用inf表示，若決策變量無下界，則lb用[]代替；若決策變量無上界，則ub用[]代替；

(4)x0是線性規(guī)劃的初始解，這種設(shè)計(jì)僅對(duì)中規(guī)模算法有效，通常可以缺省。15a(5)輸出x是最優(yōu)解，fval是最優(yōu)值。(6)輸出exitflag描述了程序的運(yùn)行情況，若其值大于零，表示程序收斂到最優(yōu)解；若其值等于零，表示計(jì)算達(dá)到了最大次數(shù)；若其值小于零，表示問題無可行解，或程序運(yùn)行失敗。(7)輸出output表示程序運(yùn)行的某些信息，如迭代次數(shù)(iterations)、所用算法(algorithm)、共軛梯度(cgiterations)等。(8)lambda表示解處的拉格朗日乘子，其中l(wèi)ower，upper，ineqlin，eqlin分別對(duì)應(yīng)于下界、上界、不等式約束與等式約束。16a例1.3用MATLAB解線性規(guī)劃問題（1.2）17a解

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)運(yùn)行后得到輸出Optimizationterminatedsuccessfully.x=z=18a例

用MATLAB求解線性規(guī)劃問題（1.3）

解首先轉(zhuǎn)化為求最小值問題19aMatlab程序如下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)運(yùn)行后得到輸出x=z=鍵入

s=-z運(yùn)行后得到原問題的目標(biāo)函數(shù)最大值

20a用MATLAB求解例的程序與輸出結(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)Optimizationterminatedsuccessfully.x=z=21a習(xí)題建立下列線性規(guī)劃問題的數(shù)學(xué)模型并求解。（1）某工廠生產(chǎn)A、B、C三種產(chǎn)品，三種產(chǎn)品對(duì)于材料費(fèi)用、勞動(dòng)力和電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價(jià)格如表所示。問應(yīng)如何確定生產(chǎn)計(jì)劃可使得總產(chǎn)值達(dá)到最大？建立線性規(guī)劃問題的數(shù)學(xué)模型。表1.1生產(chǎn)計(jì)劃問題的數(shù)據(jù)產(chǎn)品資源ABC資源限量材料費(fèi)用（元）22.54320勞動(dòng)力（人天）618640電力（度）5510750單位價(jià)格（百元）641022a（2）某療養(yǎng)院營(yíng)養(yǎng)師要為某類病人擬訂一周的菜單?？晒┻x擇的蔬菜及其費(fèi)用和所含營(yíng)養(yǎng)成分的數(shù)量以及這類病人每周所需各種營(yíng)養(yǎng)成分的最低數(shù)量如表所示。另外，為了口味的需要，規(guī)定一周內(nèi)所用卷心菜不多于2份，其他蔬菜不多于4份。若病人每周需要14份蔬菜，問選用每種蔬菜各多少份，可使生活費(fèi)用最小。建立線性規(guī)劃問題的數(shù)學(xué)模型。表1.2食譜問題的數(shù)據(jù)蔬菜每份蔬菜所含營(yíng)養(yǎng)成分費(fèi)用（元/份）鐵(mg)磷(mg)VA(單位)VC(mg)煙酸(mg)青豆0.451041580.31.5胡蘿卜0.4528906530.351.5花菜1.05502550530.62.4卷心菜0.42575270.150.6甜菜0.5221550.251.8土豆0.57523580.81.0每周營(yíng)養(yǎng)最低需求量6.0325175002455.023a播種計(jì)劃表畝產(chǎn)量表土地作物作物面積100600700500500800500850400400150300土地面積20030050024a（4）某糖果廠用原料A、B、C加工成三種不同牌號(hào)的糖果甲、乙、丙，已知各種牌號(hào)的糖果中A、B、C的含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單位加工費(fèi)及售價(jià)如表所示，問該廠每月應(yīng)生產(chǎn)這三種牌號(hào)的糖果各多少千克，使該廠獲利最大？試建立這個(gè)問題的線性規(guī)劃數(shù)學(xué)模型。甲乙丙原料成本(元/千克)每月限制用量（千克）A8.002000B6.002500C4.001200加工費(fèi)（元/千克）2.01.61.2售價(jià)（元）13.611.49表1.4糖果廠生產(chǎn)計(jì)劃數(shù)據(jù)表25a0.00.51.01.51.92.53.03.54.04.51.00.90.71.52.02.43.22.02.73.55.05.5