最優(yōu)化方法論文

彈性約束下的線性規(guī)劃之最優(yōu)化方法摘要：線性規(guī)劃方法是解決最優(yōu)化問題的有效方法之一，有著極其廣泛的應(yīng)用，在管理學(xué)的應(yīng)用過程中也時(shí)常穿插著關(guān)于最優(yōu)化的問題。本文將在古典的線性規(guī)劃方法的基礎(chǔ)上，引入彈性約束一詞，以彈性約束下的線性規(guī)劃類型為對(duì)象建立新的數(shù)學(xué)模型，在解決具體的管理學(xué)案例的過程中，尋求其最優(yōu)化方法，同時(shí)為管理決策提供依據(jù)。關(guān)鍵詞：線性規(guī)劃；最優(yōu)化；單純形法；彈性約束；保證率前言在生產(chǎn)過程、科學(xué)實(shí)驗(yàn)以及日常生活中，人們總希望用最少的人力、物力、財(cái)力和時(shí)間去辦更多的事，活得最大的效益，在管理學(xué)中被看作是生產(chǎn)者的利潤最大化和消費(fèi)者的效用最大化，如果從數(shù)學(xué)的角度來看就被看作是“最優(yōu)化問題”。在最優(yōu)化的研究生教學(xué)中我們所說的最優(yōu)化問題一般是在某些特定的“約束條件”下尋找某個(gè)“目標(biāo)函數(shù)”的最大（或最?。┲?，其解法稱為最優(yōu)化方法。線性規(guī)劃方法是最優(yōu)化方法中的一個(gè)重要部分。但是，經(jīng)典的線性規(guī)劃方法，常將目標(biāo)函數(shù)和約束條件都視為確定的。然而，在實(shí)際問題中不論目標(biāo)函數(shù)還是約束條件都具有不同形式的不確定性。本文重點(diǎn)引入新的名詞彈性約束，以彈性約束下的線性規(guī)劃類型為對(duì)象建立新的數(shù)學(xué)模型，從而尋求其最優(yōu)化方法。1、問題的提出某工廠生產(chǎn)甲、乙、丙、丁共4種產(chǎn)品，需用到A,B,C共3種原料，每種產(chǎn)品需要使用的各種原料的數(shù)量及其可能獲得的利潤如表1所示。又A,B兩種原料供應(yīng)量有限，單位生產(chǎn)周期內(nèi)只能提供一定的數(shù)量，而C種原料一經(jīng)開包使用就必須用足一定量后方可停止使用，且不能單獨(dú)使用?，F(xiàn)有關(guān)數(shù)據(jù)均見下表。問應(yīng)如何安排生產(chǎn)，方能使該廠所獲利潤達(dá)到最大值？表1：加工產(chǎn)品所需原料及可能獲得的利潤原料加工每件產(chǎn)品所需原料單位周期內(nèi)原料的供應(yīng)量或必須使用量甲乙丙丁A1.01.21.41.5<2100B0.50.60.60.8<1000C0.70.70.80.8<1300每件利潤1215810現(xiàn)設(shè)甲、乙、丙、丁4種產(chǎn)品各自產(chǎn)量分別為七，七，七，X4。依題意有maxf=12x+15x+8x+10xTOC\o"1-5"\h\z1234x+1.2x+1.4x+1.5x<21001234(1-1)s.t0.5x+0.6x+0.6x+0.8x<100012340.7x+0.7x+0.8x+0.8xN1300(1-1)1234xxxxN0I1'2’3'4"0這是一個(gè)經(jīng)典的線性規(guī)則問題。可直接利用單純形法對(duì)其進(jìn)行求解。在以上問題中，現(xiàn)因交通條件的改善，單位生產(chǎn)周期內(nèi)A'B兩種原料的供應(yīng)量可分別保證在2100?2200與1000?1050之間；因技術(shù)的改進(jìn)，C原料的使用量可變?yōu)?250?1300之間。問:在此情況下，應(yīng)如何安排生產(chǎn)，方能使該廠所獲利潤Z盡可能地達(dá)到最大？顯然，這是一個(gè)目標(biāo)函數(shù)和約束條件都具有一定的不確定性的線性規(guī)劃問題。為得到其最優(yōu)化方法，先給出以下標(biāo)記、定義和命題。2、標(biāo)記、定義和命題記C=(c'c'…，c),x=(x'x'…，x)T,b=(b'b')T,12n12n12nA=(a)mXn,X={x|xERn,xN0}.允許有一定的變動(dòng)范圍的約束條件，稱為彈性約束。所有滿足彈性約束條件的元素組成的集合，稱為彈性約束集。記加粗的“W絲”表示彈性約束，我們可理解為大約小于的意思。D={xI乎axWb,xEx}(i=1,2,-,m)；M={fl<f<f<f+d,xEX},iijji000j=1其中f表示目標(biāo)函數(shù)，f+d與f分別表示希望目標(biāo)函數(shù)值達(dá)到的最優(yōu)的上下界，d>0。0000用于表示約束條件變化范圍的量，稱為伸縮指標(biāo)，記為diN0(i=1，2,…，m)

記d=(d,d，…,d)T彈性約束集中的元素與滿足彈性約束條件的程度之間的對(duì)應(yīng)關(guān)系，稱為滿足程度函數(shù)。記u(X)表示任意的Xe度函數(shù)。記u(X)表示任意的XeD，滿足￡axWb(i=1,2,…，m)的程度，且ijjij=1乙xWb,ijjij=1bWXaxWb+d,

iijjiij=1Xax>b+d.ijjiij=1記"肱(x)表示任意xex函數(shù)在X處取得最大值的程度，且Di1，1—1/d(Xaxj=1-b.)0，<0,XcxVf,jj0j=1u(x)W1/d(^^cx-f),0jj0j=1fWXcxVf+d,0jj00j=1疽f+dWXcx.00jjj=1記D=DADE???ED，u(X)=inf{u(x),u(x),…，u(x)}。12mDD1D2Dm"V"運(yùn)算符定義為aVb=max{a,b}，"A"定義為aAb=min{a,b}，其中a,be[0,1].入表示彈性約束下的目標(biāo)函數(shù)最優(yōu)值的保證率，入e[0,1]。3、模型的建立與求解對(duì)應(yīng)于彈性約束的線性規(guī)劃問題可以寫成：求maxf=C,sXtAV絲b,xN0,(3-1)對(duì)應(yīng)于其中的約束條件，可轉(zhuǎn)化為maxuD(x)；目標(biāo)函數(shù)可轉(zhuǎn)為求maxu〃⑴,模型(3-1)，可轉(zhuǎn)換成如下模型：max(uAu)(3-2)根據(jù)命題1，模型(3-2)可進(jìn)一步轉(zhuǎn)換成如下線性規(guī)劃問題：

maxg=X廠1-1/dmaxg=X廠1-1/d(Yj=iax—b)N入，(i=1,2，…，m)ijjis.t1/d(￡cxj=1'l0GW1,xN0.將上式整理可得以下模型:maxg=X￡ax+d入Wbd,ij￡ax+d入Wbd,ijjiii(i=1,2,…，m),j=1S.tJYcx-dWfjj00j=1(3-3)xN0.假設(shè)(x*,x*,???,x*,入)T是問題(3-3)的最優(yōu)解，則x*=(x*,12n1x*,…，x*）T是問題（3-1）在限定條件fVfVf+d之后的解000f*=Ycx*是問題(3-1)在條件fVfV

jj0j=1f0+d0下所得目標(biāo)函數(shù)的最大值。關(guān)于問題（3-3）中f與f+d的確定，可由實(shí)際問題給出，也可參照生產(chǎn)實(shí)踐經(jīng)驗(yàn)或0平時(shí)生產(chǎn)統(tǒng)計(jì)數(shù)據(jù)給定，還可以根據(jù)以下問題AxVbAxVb+d求maxf=Cx,s.t(1)s.txN0(2)的解，決策者采用悲觀、樂觀、等可能、折衷主義等策略進(jìn)行確定：設(shè)問題（1）的解為f*，問題（2）的解為f*+d*，因d>0，故問題（2）放寬了問題（1）的約束條件，從而有d*>0。彈性約束使用的目標(biāo)在于希望在一定“保證率”下適當(dāng)擴(kuò)大收益（即增大目標(biāo)函數(shù)值），故應(yīng)取f+d>f，但f取值越大，所冒風(fēng)險(xiǎn)越大，當(dāng)f>f+d時(shí)，00*00**

實(shí)現(xiàn)f的可能性只能是0，故還應(yīng)取fvf+d。一般地，可令a表示樂觀系數(shù)00**(0<a<1平時(shí)生產(chǎn)統(tǒng)計(jì)數(shù)據(jù)給定，還可以根據(jù)以下問題AxVbAxVb+d求maxf=Cx,s.t(1)s.txN0(2)(1)若采用悲觀主義決策準(zhǔn)則，可取f0=f*f0+d0=f1;(2)若采用樂觀主義決策準(zhǔn)則，可取f(1)若采用悲觀主義決策準(zhǔn)則，可取f0=f*f0+d0=f1;(2)若采用樂觀主義決策準(zhǔn)則，可取fo=f1,4、案例求解下面對(duì)本文開始所提出的問題基礎(chǔ)具體的求解:①利用單純形法，首先求得問題(1—1)的最佳基可行解x和最優(yōu)函數(shù)值為x=(x,x,x,x)t=(8100/7,5000/7,0,0)t,f=171000/7.1234②利用單純形法，求解以下問題：求maxf=12%+15x2+8x3+10x4x+1.2x+1.4x+1.5x<21001234s.t0.5x+0.6x+0.6x+0.8x<10001234(4-1)0.7x+0.7x+0.8x+0.8xN13001234x,x,x,xN01234得其最優(yōu)基可行解x及最優(yōu)解f*+d*為:x=(x,x,x,x)t=(1500/7,11000/7,0,0)t,1234f+d=18700/7,d=1200/7③最后求解彈性約束線性規(guī)劃問題:maxf=12七+15x2+8x3+10x4<x+1.2x+1.4x+1.5x<￡210012340.5x+0.6x+0.6x+0.8x<￡10001234s.t—0.7x—0.7x—0.8x—0.8x<￡—13001234給定d1=100,d2=d3=50。為得到以上問題的解答，先令a=1/3,得f*=17500/7,采用樂觀主義決策準(zhǔn)則取f0=17500/7,d0=8000/7，且有式(3-3)將問題(4-1)轉(zhuǎn)換為如下經(jīng)典線性規(guī)劃問題：求maxg=入cx+1.2X+1.4X+1.5X+100入W2100+100,TOC\o"1-5"\h\z12340.5x+0.6x+0.6x+0.8x+50入W1000+501234s.t—0.7x—0.7x—0.8x—0.8x+50入W—1300+50,y'123412七+15x2+8x3+10x4-8000/7入N17500/70W入W1將其化為標(biāo)準(zhǔn)形式，利用單純形法同樣可求得其最優(yōu)基可行解為:x=(x,x,x,x，入)T=(4100/7,8600/7,0,0,2/5)t.1234因此得x=(x,x,x,x)t=(4100/7,8600/7,0,0)t是問題(4-1)在選擇f=1234017500/7,d0=8000/7時(shí)的最優(yōu)解，且保證率入=2/5獲得最優(yōu)目標(biāo)值f=12X4100/7+15X8600/7=178200/7。與問題(1-1)相比，收益增加了1028元，增幅為4.2%。在問題(4-1)中，采用悲觀主義決策準(zhǔn)則取f0=17500/7,d0=8000/7,則得入=3/4,f=17400/7；若由生產(chǎn)經(jīng)驗(yàn)直接取f0=16500/7,d0=15000/7,則得入=2/3,最優(yōu)值f=175000/7=25000。5、總結(jié)需要指出的是，使用模型(3-3)所得結(jié)果與f和d的選取有關(guān)。一般地，若fVf和000*dVd，則入將取得最大化。但所得f值增幅不大，若f>f或d>d，因入將取較0*0*0*小值，故f值增