MATLAB在線性規(guī)劃中的應(yīng)用

MATLAB在線性規(guī)劃中的應(yīng)用摘要在各類經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這樣的問題：在生產(chǎn)條件不變的情下，如何通過(guò)統(tǒng)籌安排，改進(jìn)生產(chǎn)組織或計(jì)劃，合理安排人力、物力資源，組織生產(chǎn)過(guò)程，使總的經(jīng)濟(jì)效益最好。這樣的問題常?？梢曰苫蚪频鼗伤^的“線性規(guī)劃”（LinearProgramming，簡(jiǎn)記為L(zhǎng)P）問題。線性規(guī)劃是應(yīng)用分析、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)有效管理。利用線性規(guī)劃我們可以解決很多問題。如：在不違反一定資源限制下，組織安排生產(chǎn)，獲得最好的經(jīng)濟(jì)效益（產(chǎn)量最多、利潤(rùn)最大、效用最高）。也可以在滿足一定需求條件下，進(jìn)行合理配置，使成本最小。同時(shí)還可以在任務(wù)或目標(biāo)確定后，統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原材料、人工、時(shí)間等）去完成任務(wù)。常規(guī)的手工解法復(fù)雜且運(yùn)算量大，而MATLAB語(yǔ)言可以很好的處理線性規(guī)劃問題，既能進(jìn)行數(shù)值的求解，又能繪制有關(guān)線性圖形，非常方便實(shí)用，利用其可以減少工作量，節(jié)約時(shí)間，加深理解，同樣可以培養(yǎng)應(yīng)用能力。關(guān)鍵詞:線性規(guī)劃優(yōu)化求解MATLAB語(yǔ)言一、線性規(guī)劃問題的在實(shí)際中的應(yīng)用線性規(guī)劃問題的在實(shí)際應(yīng)用中的作用任何資源都是有限的，如何通過(guò)分配有限的資源獲得人們所期望的效果，在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、資本增值等各項(xiàng)經(jīng)濟(jì)活動(dòng)中，如何提高經(jīng)濟(jì)效益，做到耗費(fèi)較少的人力物力財(cái)力，創(chuàng)造出較多的經(jīng)濟(jì)價(jià)值，這些問題涉及分配，而線性規(guī)劃為最優(yōu)分配提供了工具。線性規(guī)劃主要研究的兩類問題一是一項(xiàng)任務(wù)確定后，如何統(tǒng)籌安排，盡量做到用最少的人力物力資源去完成這一任務(wù)。二是已有一定數(shù)量的人力物力資源，如何安排使用它們，使得完成任務(wù)最多。常見的線性規(guī)劃問題如：運(yùn)輸問題，生產(chǎn)的組織與計(jì)劃問題，合力下料問題，配料問題、布局問題、分派問題等。MATLAB在線性規(guī)劃中的應(yīng)用1.MATLAB在線性規(guī)劃中的指令線性規(guī)劃是一種優(yōu)化方法，Matlab優(yōu)化工具箱中有現(xiàn)成函數(shù)linprog[1]對(duì)如下式描述的LP問題求解：%minf'x%s.t.(約束條件)：Ax<=b%(等式約束條件)：Aeqx=beq%lb<=x<=ub linprog函數(shù)的調(diào)用格式如下：x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=linprog(…)[x,fval,exitflag]=linprog(…)[x,fval,exitflag,output]=linprog(…)[x,fval,exitflag,output,lambda]=linprog(…)相關(guān)說(shuō)明x=linprog(f,A,b)返回值x為最優(yōu)解向量。x=linprog(f,A,b,Aeq,beq)作有等式約束的問題。若沒有不等式約束，則令A(yù)=[]、b=[]。x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)中l(wèi)b,ub為變量x的下界和上界，x0為初值點(diǎn)，options為指定優(yōu)化參數(shù)進(jìn)行最小化。Options的參數(shù)描述：Display顯示水平；選擇’off’不顯示輸出；選擇’Iter’顯示每一步迭代過(guò)程的輸出；選擇’final’顯示最終結(jié)果。MaxFunEvals函數(shù)評(píng)價(jià)的最大允許次數(shù)。Maxiter最大允許迭代次數(shù)。TolXx處的終止容限。[x,fval]=linprog(…)左端fval返回解x處的目標(biāo)函數(shù)值。[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beg,lb,ub,x0)的輸出部分。exitflag描述函數(shù)計(jì)算的退出條件：若為正值，表示目標(biāo)函數(shù)收斂于解x處；若為負(fù)值，表示目標(biāo)函數(shù)不收斂；若為零值，表示已經(jīng)達(dá)到函數(shù)評(píng)價(jià)或迭代的最大次數(shù)。output返回優(yōu)化信息：output.iterations表示迭代次數(shù)；output.algorithm表示所采用的算法；outprt.funcCount表示函數(shù)評(píng)價(jià)次數(shù)。lambda返回x處的拉格朗日乘子。它有以下屬性：lambda.lower-lambda的下界；lambda.upper-lambda的上界；lambda.ineqlin-lambda的線性不等式；lambda.eqlin-lambda的線性等式。三、運(yùn)用MATLAB解決線性規(guī)劃問題的實(shí)例對(duì)于給定的實(shí)際問題，首先是要建立線性規(guī)劃問題[2]的數(shù)學(xué)模型，其次是求問題的最優(yōu)解。1、直接運(yùn)用MATLAB編程計(jì)算求解線性規(guī)劃問題線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件可以是不等式也可以是等式，變量可以有非負(fù)要求也可以沒有非負(fù)要求（稱這樣的變量為自由變量）。為了避免這種由于形式多樣性而帶來(lái)的不便，規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為（1）極小值模型（2）極大值模型利用矩陣與向量記為（3）其中C和x為n維列向量，b為m維列向量，b≥0，A為m×n矩陣,m<n且rank(A)=m。如果根據(jù)實(shí)際問題建立起來(lái)的線性規(guī)劃問題并非標(biāo)準(zhǔn)形式，可以將它如下化為標(biāo)準(zhǔn)形式：（1）若目標(biāo)函數(shù)為，可將它化為(2）若第i個(gè)約束為，可增加一個(gè)松馳變量，將不等式化為，且0。 若第i個(gè)約束為ai1x1+…+ainxnbi，可引入剩余量，將不等式化為ai1x1+…+ainxn－yi=bi，且yi0。（3）若xi為自變量，則可令,其中、0。問題一、某牧場(chǎng)飼養(yǎng)一批動(dòng)物，平均每頭動(dòng)物至少需要700g蛋白質(zhì)，30g礦物質(zhì)和100g維生素。現(xiàn)有A,B,C,D,E五種飼料可供選用，每千克飼料的營(yíng)養(yǎng)成分（單位：g）與價(jià)格（單位：元/kg）如下表所示：表1每千克飼料的營(yíng)養(yǎng)成分（單位：g）與價(jià)格（單位：元/kg）蛋白質(zhì)礦物質(zhì)維生素價(jià)格A31.00.50.4B20.51.01.4C10.21.20.8D62.02.01.6E120.50.81.6試求能滿足動(dòng)物生長(zhǎng)營(yíng)養(yǎng)需求又最經(jīng)濟(jì)的選用飼料方案。設(shè)配合飼料中，用A種飼料單位，用B種飼料單位，用C種飼料單位，用D種飼料單位，用E種飼料單位，則配合飼料的原料成本函數(shù)，即決策的目標(biāo)函數(shù)為Z?？紤]三種營(yíng)養(yǎng)含量限制條件后，得這一問題的線性規(guī)劃模型[3]如下目標(biāo)函數(shù)：（4）約束條件為：（5）編寫M文件如下：c=[0.4;1.4;0.8;1.6;1.6];%產(chǎn)生有五個(gè)元素的列向量cA=[-3,-2,-1,-6,-12;-1.0,-0.5,-0.2,-2.0,-0.5;-0.5,-1.0,-1.2,-2.0,-0.8];%約束條件中的變量系數(shù)構(gòu)成的矩陣Ab=[-700;-30;-100];%約束條件中的上下界構(gòu)成的列向量Aeq=[];%沒有等式約束beq=[];%沒有等式約束vlb=zeros(5,1);%生成一個(gè)五行一列的零矩陣[x,fval,eval]=linprog(c,A,b,Aeq,beq，vlb)%調(diào)用linprog函數(shù)可得到如下結(jié)果：Optimizationterminated.x=224.71150.00000.00000.00002.1555fval=93.3333從以上結(jié)果可以看出，買224.7115千克的A飼料，2.1555千克的E飼料，能滿足動(dòng)物生能滿足動(dòng)物生長(zhǎng)營(yíng)養(yǎng)需求又最經(jīng)濟(jì)，所用價(jià)錢為93.3333元。問題二、某農(nóng)場(chǎng)I、II、III等耕地的面積分別為100hm2、300hm2和200hm2，計(jì)劃種植水稻、大豆和玉米，要求三種作物的最低收獲量分別為190000kg、130000kg和350000kg。I、II、III等耕地種植三種作物的單產(chǎn)如表5.1.4所示。若三種作物的售價(jià)分別為水稻1.20元/kg，大豆1.50元/kg，玉米0.80元/kg表2不同等級(jí)耕地種植不同作物的單產(chǎn)(單位:kg/hm2)I等耕地II等耕地III等耕地水稻1100095009000大豆800068006000玉米140001200010000首先根據(jù)題意建立線性規(guī)劃模型（決策變量設(shè)置如表2所示，表中表示第種作物在第j等級(jí)的耕地上的種植面積。）：表3作物計(jì)劃種植面積（單位:hm2)I等耕地II等耕地III等耕地水稻大豆玉米約束方程[4]如下：耕地面積約束：（6）最低收獲量約束：（7）非負(fù)約束：追求總產(chǎn)量最大，目標(biāo)函數(shù)為：（8）追求總產(chǎn)值最大，目標(biāo)函數(shù)為：（9）根據(jù)求解函數(shù)linprog中的參數(shù)含義，列出系數(shù)矩陣，目標(biāo)函數(shù)系數(shù)矩陣，以及約束條件等。這些參數(shù)中沒有的設(shè)為空。譬如，當(dāng)追求總產(chǎn)量最大時(shí)，只要將參數(shù)f=[-11000–9500–9000–8000–6800–6000–14000–12000-10000];A=[1.00000.00000.00001.00000.00000.00001.00000.00000.0000;0.00001.00000.00000.00001.00000.00000.00001.00000.0000;0.00000.00001.00000.00000.00001.00000.00000.00001.0000;-11000.00000.00000.0000-9500.00000.00000.0000-9000.00000.00000.0000;0.0000-8000.00000.00000.0000-6800.00000.00000.0000-6000.00000.0000;0.00000.0000-14000.00000.00000.0000-12000.00000.00000.0000-10000.0000];b=[100300200-190000-130000-350000];lb=[0.00000.00000.00000.00000.00000.00000.00000.00000.0000];代入求解函數(shù)，即可得到求解結(jié)果。運(yùn)用MATLAB的圖解法求解線性規(guī)劃問題若一個(gè)線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的某個(gè)極點(diǎn)上找到一個(gè)最優(yōu)解。同時(shí)仍有可能有其他最優(yōu)解存在，但它們也只可能存在于可行域的其他極點(diǎn)或是邊界上。如果我們的目的是找出一個(gè)最優(yōu)解而不是全部最優(yōu)解，這一定理實(shí)際上是把尋找的范圍，從可行域中的無(wú)窮多個(gè)可行點(diǎn)，縮小到可行域的有限幾個(gè)極點(diǎn)上。[5]問題一、某農(nóng)戶有耕地20公頃，可采用甲乙兩種種植方式。甲種植方式每公頃需投資280元，每公頃投工6個(gè)，可獲收入1000元，乙方式每公頃需投資150元，勞動(dòng)15個(gè)工日，可獲收入1200元，該戶共有可用資金4200元、240個(gè)勞動(dòng)工日。問如何安排甲乙兩種方式的生產(chǎn)，可使總收入最大?解：設(shè)甲方式種公頃，乙方式種公頃，總收入為Z，則有：（13）圖問題一線性規(guī)劃圖解所以，如圖所示，在B點(diǎn)時(shí)，甲級(jí)兩種方式的總收入最大，即甲方式種6.7公頃，乙方式種13.3公頃。結(jié)論1、由于將線性規(guī)劃問題化為標(biāo)準(zhǔn)形式之后的約束條件是一個(gè)非齊次線性方程組，故當(dāng)考慮LP問題的解時(shí)，首先可以考慮非齊次線性方程組的解，然后再考慮目標(biāo)函數(shù)的解最大、最小值問題。單純形法是求解LP問題的一種常用方法，但單純形法的運(yùn)算量比較大，當(dāng)約束條件中的約束變量比較多時(shí)，效費(fèi)比就比較低，因此借助計(jì)算機(jī)軟件的強(qiáng)大運(yùn)算功能，既節(jié)約時(shí)間又提高了運(yùn)算的準(zhǔn)確性，對(duì)于一般的線性規(guī)劃問題，應(yīng)用excel、MATLAB都可以輕松解決，但MATLAB的整數(shù)線性規(guī)劃運(yùn)算功能欠缺，此時(shí)可以應(yīng)用lingo、excel軟件解決這類問題。2、在接觸MATLAB之后,我發(fā)現(xiàn)MATLAB語(yǔ)法簡(jiǎn)單,易于繪制圖形,編程也非常容易.并且有功能強(qiáng)大的開放式的toolbox。MATLAB是功能強(qiáng)大的科學(xué)及工程計(jì)算軟件,它不但具有矩陣計(jì)算為基礎(chǔ)的強(qiáng)大數(shù)學(xué)計(jì)算和分析功能,而且還具有豐富的可視化圖形表現(xiàn)功能和方便的程序設(shè)計(jì)能力。3、對(duì)于MATLAB自帶函數(shù)的問題,要多利用MATLAB的幫助功能,例如:對(duì)于某些不是很明確的命令,只知道大體的所屬范圍,譬如說(shuō)某個(gè)工具箱,直接在命令窗口中敲入helptoolboxname.可以這么說(shuō)任何問題都可以在MATLAB幫助里找到解決方法,問題不論大小