運籌學(xué)實驗報告092086234

太原工業(yè)學(xué)院實驗報告PAGE4運籌學(xué)實驗報告開課系部及實驗室：11層多功能實驗室實驗時間：2012-5-17小組成員班級學(xué)號092086231姓名余川實驗名稱Matlab和lingo求解線性規(guī)劃1、實驗?zāi)康模?.了解、使用MATLAB中的優(yōu)化命令求解線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃等問題;2.了解用lindo軟件求解線性規(guī)劃。2、實驗儀器、設(shè)備及材料：Lindo11.0軟件，計算機(jī),MATLAB2010rb軟件，管理運籌學(xué)2.53、實驗內(nèi)容：線性規(guī)劃（linearprogramming）是運籌學(xué)中應(yīng)用最廣泛的模型之一。由于其理論和方法研究比較成熟，許多問題常借助線性規(guī)劃模型來求解，而且線性規(guī)劃為某些非線性規(guī)劃問題的解法起到間接作用。線性規(guī)劃的模型結(jié)構(gòu)線性規(guī)劃的標(biāo)準(zhǔn)形式為：單純形算法 根據(jù)單純形法的原理編寫MATLAB程序：simpleTabMATLAB優(yōu)化庫函數(shù)都是以最小化為標(biāo)準(zhǔn)，所以simpleTab（mat,numFreeVar）程序也以最優(yōu)化為標(biāo)準(zhǔn)。simpleTab的使用方法為：先將一般的線性規(guī)劃變?yōu)榫€性規(guī)劃的標(biāo)準(zhǔn)形式，再構(gòu)建初始單純形表格，輸入程序。 ：1.3linprog函數(shù)linprog函數(shù)在MATLAB優(yōu)化工具箱Optimization-Toolbox中。linprog針對的線性函數(shù)模型為具體用法可以helplinprog實例演示1 使用[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub)在命令窗口輸入：f=[-1,-1,-1]%目標(biāo)函數(shù)系數(shù)A=[7,3,9;8,5,4;6,9,5];%不等式約束的系數(shù)矩陣b=[1,1,1]%不等式約束的bAeq=[]%等式約束的系數(shù)矩陣（該問題無等式約束Aeq為空）beq=[]%等式約束的beq（該問題無等式約束beq為空）lb=[0,0,0]%變量的下屆ub=[]%變量得上界（無上界約束，ub為空）[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub)運行結(jié)果：f=-1-1-1b=111Aeq=[]beq=[]lb=000ub=[]Optimizationterminated.x=0.08700.03560.0316fval=-0.1542exitflag=1output=iterations:7algorithm:[1x27char]cgiterations:0message:[1x24char]constrviolation:0firstorderopt:3.2143e-014lambda=ineqlin:[3x1double]eqlin:[0x1double]upper:[3x1double]lower:[3x1double]1.4用lingo11.0軟件求解例1某家具公司制造書桌、餐桌和椅子，所用的資源有三種：木料、木工和漆工。生產(chǎn)數(shù)據(jù)如下表所示：

每個書桌每個餐桌每個椅子現(xiàn)有資源總數(shù)木料8單位6單位1單位48單位漆工4單位2單位1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價60單位30單位20單位

若要求桌子的生產(chǎn)量不超過5件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤最大？用DESKS、TABLES和CHAIRS分別表示三種產(chǎn)品的生產(chǎn)量，建立LP模型。max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs<=48;4*desks+2*tables+1.5*chairs<=20;2*desks+1.5*tables+.5*chairs<=8;tables<=5;求解這個模型，并激活靈敏性分析。這時，查看報告窗口（ReportsWindow）,可以看到如下結(jié)果。Globaloptimalsolutionfoundatiteration:3Objectivevalue:280.0000VariableValueReducedCostDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000RowSlackorSurplusDualPrice1280.00001.000000224.000000.00000030.00000010.0000040.00000010.0000055.0000000.000000“Globaloptimalsolutionfoundatiteration:3”表示3次迭代后得到全局最優(yōu)解?！癘bjectivevalue:280.0000”表示最優(yōu)目標(biāo)值為280?！癡alue”給出最優(yōu)解中各變量的值：造2個書桌（desks）,0個餐桌（tables）,8個椅子（chairs）。所以desks、chairs是基變量（非0），tables是非基變量（0）?！癝lackorSurplus”給出松馳變量的值：第1行松馳變量=280（模型第一行表示目標(biāo)函數(shù)，所以第二行對應(yīng)第一個約束）第2行松馳變量=24第3行松馳變量=0第4行松馳變量=0第5行松馳變量=5“ReducedCost”列出最優(yōu)單純形表中判別數(shù)所在行的變量的系數(shù)，表示當(dāng)變量有微小變動時,目標(biāo)函數(shù)的變化率。其中基變量的reducedcost值應(yīng)為0，對于非基變量Xj,相應(yīng)的reducedcost值表示當(dāng)某個變量Xj增加一個單位時目標(biāo)函數(shù)減少的量(max型問題)。本例中：變量tables對應(yīng)的reducedcost值為5，表示當(dāng)非基變量tables的值從0變?yōu)?時（此時假定其他非基變量保持不變,但為了滿足約束條件，基變量顯然會發(fā)生變化），最優(yōu)的目標(biāo)函數(shù)值=280-5=275?！癉UALPRICE”（對偶價格）表示當(dāng)對應(yīng)約束有微小變動時,目標(biāo)函數(shù)的變化率。輸出結(jié)果中對應(yīng)于每一個約束有一個對偶價格。若其數(shù)值為p，表示對應(yīng)約束中不等式右端項若增加1個單位，目標(biāo)函數(shù)將增加p個單位（max型問題）。顯然，如果在最優(yōu)解處約束正好取等號（也就是“緊約束”，也稱為有效約束或起作用約束），對偶價格值才可能不是0。本例中：第3、4行是緊約束，對應(yīng)的對偶價格值為10，表示當(dāng)緊約束3)4DESKS+2TABLES+1.5CHAIRS<=20變?yōu)?)4DESKS+2TABLES+1.5CHAIRS<=21時，目標(biāo)函數(shù)值=280+10=290。對第4行也類似。對于非緊約束（如本例中第2、5行是非緊約束），DUALPRICE的值為0,表示對應(yīng)約束中不等式右端項的微小擾動不影響目標(biāo)函數(shù)。有時,通過分析DUALPRICE,也可對產(chǎn)生不可行問題的原因有所了解。靈敏度分析的結(jié)果是Rangesinwhichthebasisisunchanged:ObjectiveCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseDESKS60.000000.00.0TABLES30.000000.00.0CHAIRS20.000000.00.0RighthandRowCurrentAllowableAllowableRHSIncreaseDecrease248.000000.00.0320.000000.00.048.0000000.00.055.0000000.00.0目標(biāo)函數(shù)中DESKS變量原來的費用系數(shù)為60，允許增加（AllowableIncrease）=4、允許減少（AllowableDecrease）=2，說明當(dāng)它在[60-4，60+20]=[56，80]范圍變化時，最優(yōu)基保持不變。對TABLES、CHAIRS變量，可以類似解釋。由于此時約束沒有變化（只是目標(biāo)函數(shù)中某個費用系數(shù)發(fā)生變化），所以最優(yōu)基保持不變的意思也就是最優(yōu)解不變（當(dāng)然，由于目標(biāo)函數(shù)中費用系數(shù)發(fā)生了變化，所以最優(yōu)值會變化）。第2行約束中右端項（RightHandSide，簡寫為RHS）原來為48，當(dāng)它在[48-24，48+∞]=[24，∞]范圍變化時，最優(yōu)基保持不變。第3、4、5行可以類似解釋。不過由于此時約束發(fā)生變化，最優(yōu)基即使不變，最優(yōu)解、最優(yōu)值也會發(fā)生變化。靈敏性分析結(jié)果表示的是最優(yōu)基保持不變的系數(shù)范圍。由此，也可以進(jìn)一步確定當(dāng)目標(biāo)函數(shù)的費用系數(shù)和約束右端項發(fā)生小的變化時，最優(yōu)基和最優(yōu)解、最優(yōu)值如何變化。下面我們通過求解一個實際問題來進(jìn)行說明。例2一奶制品加工廠用牛奶生產(chǎn)A1,A2兩種奶制品，1桶牛奶可以在甲車間用12小時加工成3公斤A1，或者在乙車間用8小時加工成4公斤A2。根據(jù)市場需求，生產(chǎn)的A1,A2全部能售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動時間480小時，并且甲車間每天至多能加工100公斤A1，乙車間的加工能力沒有限制。試為該廠制訂一個生產(chǎn)計劃，使每天獲利最大，并進(jìn)一步討論以下3個附加問題：1）若用35元可以買到1桶牛奶，應(yīng)否作這項投資？若投資，每天最多購買多少桶牛奶？2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？3）由于市場需求變化，每公斤A1的獲利增加到30元，應(yīng)否改變生產(chǎn)計劃？模型代碼如下：max=72*x1+64*x2;x1+x2<=50;12*x1+8*x2<=480;3*x1<=100;求解這個模型并做靈敏性分析，結(jié)果如下。Globaloptimalsolutionfoundatiteration:0Objectivevalue:3360.000VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.00000020.00000048.0000030.0000002.000000440.000000.000000Rangesinwhichthebasisisunchanged:ObjectiveCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandRowCurrentAllowableAllowableRHSIncreaseDecrease250.0000010.000006.6666673480.000053.3333380.000004100.0000INFINITY40.00000結(jié)果告訴我們：這個線性規(guī)劃的最優(yōu)解為x1=20，x2=30，最優(yōu)值為z=3360，即用20桶牛奶生產(chǎn)A1,30桶牛奶生產(chǎn)A2，可獲最大利潤3360元。輸出中除了告訴我們問題的最優(yōu)解和最優(yōu)值以外，還有許多對分析結(jié)果有用的信息，下面結(jié)合題目中提出的3個附加問題給予說明。3個約束條件的右端不妨看作3種“資源”：原料、勞動時間、車間甲的加工能力。輸出中SlackorSurplus給出這3種資源在最優(yōu)解下是否有剩余：原料、勞動時間的剩余均為零，車間甲尚余40（公斤）加工能力。目標(biāo)函數(shù)可以看作“效益”，成為緊約束的“資