(四)可化為線性規(guī)劃的問(wèn)題

問(wèn)題一

汽車廠月度生產(chǎn)計(jì)劃一汽車廠生產(chǎn)小、中、大三種類型的汽車,各種類型的汽車對(duì)鋼材以及勞動(dòng)時(shí)間的需求如下表.試制訂月生產(chǎn)計(jì)劃,使該工廠的利潤(rùn)最大.小型車中型車大型車現(xiàn)有量鋼材1.535600勞動(dòng)時(shí)間28025040060000利潤(rùn)234分析小型車中型車大型車現(xiàn)有量鋼材1.535600勞動(dòng)時(shí)間28025040060000利潤(rùn)234從收益率來(lái)看,比較中型車和大型車得出結(jié)論,生產(chǎn)大型車不經(jīng)濟(jì).因此,若允許車輛數(shù)量為實(shí)數(shù),則不生產(chǎn)大型車.但是現(xiàn)在車輛為整數(shù),因此模型為1模型的建立記月生產(chǎn)的小、中、大型車的數(shù)量分別為x1,x2,x3,模型為這是個(gè)整數(shù)線性規(guī)劃問(wèn)題,有三個(gè)決策變量,要用軟件來(lái)求ILP.但是本題比較特殊,我們可以發(fā)現(xiàn)2LP圖解法我們先得到實(shí)數(shù)型的最優(yōu)解為（64.5,167.7),利潤(rùn)的最大值為632.3.（64.5,167.7)?但是,遺憾的是,這個(gè)解不是整數(shù)解,因此不合要求.解決方法:(1)由于解的數(shù)字都比較大,我們可以簡(jiǎn)單地舍去小數(shù),即取(64,167),此時(shí)利潤(rùn)為629,可以接受.同時(shí)定界.(2)在最優(yōu)解附近試探:(64,168);(65,167);(66,167),(65,166,1)等等.利潤(rùn)分別為632,631,后兩個(gè)不滿足約束.由于最大利潤(rùn)為632,故最優(yōu)解為(64,168).3進(jìn)一步討論由于各種原因(比如,工藝),若生產(chǎn)某種汽車,則至少生產(chǎn)80輛,問(wèn)生產(chǎn)計(jì)劃有何改變?分析:要么xi=0,要么xi≥80,組合起來(lái),共有八種情形:方法一:

讓它們分別與模型(*)一起來(lái)求解新的LP,逐一得到它們的最優(yōu)解.其中(1)不用解;(7),(8)無(wú)解;(2)的解為(214.3,0,0),z=428.5;(3)的解為(0,200,0),z=600;;(4)的解為(0,0,120),z=480;(5)的最優(yōu)解為(80,150.4,0),z=611.2;工時(shí)為緊約束;(6)的最優(yōu)解為(80,0,94),z=536;工時(shí)為緊約束;結(jié)論:此時(shí)最優(yōu)解為(80,150.4,0),利潤(rùn)為611.2（64.5,167.7)?(75,97.5)?可行域方法二引入0-1變量的作用是當(dāng)yi=0時(shí),必有xi=0.本例中,方法三從數(shù)學(xué)上講,不過(guò),這個(gè)式子對(duì)變量而言,出現(xiàn)了非線性函數(shù),因此就變成了非線性規(guī)劃問(wèn)題,其求解往往比較困難,即使用軟件求解(如:LINGO,Matlab),也往往依賴于初值的選擇.評(píng)注:若能用線性規(guī)劃處理,則盡量不要用非線性規(guī)劃.例2原油的采購(gòu)與加工問(wèn)題某公司用兩種原油(A和B)混合加工成兩種汽油(甲和乙).甲乙兩種汽油含原油A的最低比例分別是50%和60%,每噸售價(jià)分別為4800元和5600元.該公司現(xiàn)有原油A和B的庫(kù)存量分別為500噸和1000噸,還可以從市場(chǎng)上買到不超過(guò)1500噸的原油A.原油A的市場(chǎng)價(jià)為:購(gòu)買量不超過(guò)500噸時(shí)的單價(jià)為10000元/噸;購(gòu)買量超過(guò)500噸但不超過(guò)1000噸時(shí),超過(guò)500噸的部分8000元/噸;購(gòu)買量超過(guò)1000噸時(shí),超過(guò)1000噸的部分6000元/噸.該公司應(yīng)如何安排原油的采購(gòu)和加工?模型的建立設(shè)購(gòu)買原油Ax噸,生產(chǎn)汽油甲所用的原油A和B分別為x11和x21噸;乙的分別為x12和x22噸.公司銷售生產(chǎn)的汽油收入為P千元,純收入為R千元.則購(gòu)買原油A的成本為于是模型為其中模型求解方法一由于c(x)為分段函數(shù),且在每一段內(nèi)都是線性函數(shù),因此我們可以通過(guò)求解三個(gè)線性規(guī)劃問(wèn)題,最后比較即可得到模型的最優(yōu)解.方法二處理分段函數(shù)c(x)方法三引入0-1變量yi以yi=1分別表示以三種價(jià)格購(gòu)買原油,等價(jià)于模型為混合線性規(guī)劃.方法四處理分段線性函數(shù)的一般方法500100015001200090005000這個(gè)分段函數(shù)在三個(gè)區(qū)間內(nèi)分別是線性函數(shù),區(qū)間的分段點(diǎn)為0,500,1000,1500.當(dāng)x落在某個(gè)區(qū)間時(shí)我們可以取做區(qū)間兩個(gè)端點(diǎn)的線性組合來(lái)解決.500100015001200090005000取分點(diǎn)b1=0,b2=500,b3=1000,b4=1500.取分點(diǎn)的比例z1,z2,z3,z4.當(dāng)x落在區(qū)間[b1,b2]時(shí),取x=b1z1+b2z2,z1+z2=1;當(dāng)x落在區(qū)間[b2,b3]時(shí),取x=b2z2+b3z3,z2+z3=1;當(dāng)x落在區(qū)間[b3,b4]時(shí),取x=b3z3+b4z4,z3+z4=1;由于c(x)是x的線性函數(shù),自然也是zi的線性函數(shù).為了表示x落在某個(gè)區(qū)間,我們還要引入表示這個(gè)屬性的變量:0-1變量yi.關(guān)系式y(tǒng)i中有只有一個(gè)為1.投資的收益與風(fēng)險(xiǎn)問(wèn)題(98年A題)市場(chǎng)上有n種資產(chǎn)（如股票、債券、……）Si（i=1,2,…,n）供投資者選擇，某公司有數(shù)額為M的一筆相當(dāng)大的資金可用于作一個(gè)時(shí)期的投資。公司財(cái)務(wù)分析人員對(duì)這n種資產(chǎn)進(jìn)行了評(píng)估，估算出在這一時(shí)期內(nèi)購(gòu)買Si的平均收益率為ri，并預(yù)測(cè)出購(gòu)買Si的的風(fēng)險(xiǎn)損失率為qi。考慮到投資越分散，總的風(fēng)險(xiǎn)越小，公司確定，當(dāng)用這筆資金購(gòu)買若干種資產(chǎn)時(shí)，總體風(fēng)險(xiǎn)可用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來(lái)度量。購(gòu)買Si要付交易費(fèi)，費(fèi)率為pi，并且當(dāng)購(gòu)買額不超過(guò)給定值ui時(shí)，交易費(fèi)按購(gòu)買ui計(jì)算（不買當(dāng)然無(wú)須付費(fèi)）。另外，假定同期銀行存款利率是r0，且既無(wú)交易費(fèi)又無(wú)風(fēng)險(xiǎn)。（r0=5%）1)已知n=4時(shí)的相關(guān)數(shù)據(jù)如下：Siri(%)qi(%)pi(%)ui(元)S1282.51103S2211.52198S3235.54.552S4252.66.540試給該公司設(shè)計(jì)一種投資組合方案，即用給定的資金M，有選擇地購(gòu)買若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，而總風(fēng)險(xiǎn)盡可能小。2)試就一般情況對(duì)以上問(wèn)題進(jìn)行討論，并利用以下數(shù)據(jù)進(jìn)行計(jì)算。Siri(%)qi(%)pi(%)ui(元)S19.6422.1181S218.5543.2407S349.4606.0428S423.9421.5549S58.11.27.6270Siri(%)qi(%)pi(%)ui(元)S614393.4