線性規(guī)劃和整數(shù)規(guī)劃

《線性規(guī)劃和整數(shù)規(guī)劃》由會(huì)員分享，可在線閱讀，更多相關(guān)《線性規(guī)劃和整數(shù)規(guī)劃（93頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第一部分：優(yōu)化模型,1、線性規(guī)劃模型（算法：?jiǎn)渭冃畏ǎ?2、整數(shù)規(guī)劃模型（算法：分枝定界法）,3、非線性規(guī)劃模型（化為線性規(guī)劃求解）,4、動(dòng)態(tài)規(guī)劃模型（算法：遞歸算法）,5、多目標(biāo)規(guī)劃模型（化為線性規(guī)劃求解）,一、線性規(guī)劃模型,線性規(guī)劃主要解決兩個(gè)方面的問題：,（1）對(duì)于給定的一項(xiàng)任務(wù)，如何統(tǒng)籌安排，使以最少的資源消耗去完成？,（2）在給定的一定數(shù)量的資源條件下，如何合理安排，使完成的任務(wù)最多？,用線性規(guī)劃方法解決問題一般按下列步驟進(jìn)行,第一步：建立線性規(guī)劃模型；,第二步：用單純形算法進(jìn)行求解；,第三步：對(duì)

2、求解結(jié)果進(jìn)行檢驗(yàn)；,第四步：將求解結(jié)果形成優(yōu)化方案，付諸實(shí)施；,線性規(guī)劃模型一般包括三個(gè)要素,：,（1）決策變量,（2）目標(biāo)函數(shù),（3）約束條件,線性規(guī)劃的一般形式為：,max(或min)z=c,1,x,1,+c,2,x,2,+c,n,x,n,（1.1),（1.2),（1.3),或矩陣形式,其中c=(c,1,c,2,c,n,)，稱為價(jià)值系數(shù)向量；,稱為技術(shù)系數(shù)矩陣(也稱消耗系數(shù)矩陣),稱為資源限制向量,X=(x,1,x,2,x,n,),T,稱為決策變量向量,下面我們來看幾個(gè)實(shí)際例子。,案例1(,投資計(jì)劃問題）某公司經(jīng)調(diào)研分析知，在今后三年內(nèi)有四種投資機(jī)會(huì)。第種方案是在三年內(nèi)每年年初投資，年底可

3、獲利15%，并可將本金收回；第種是在第一年的年初投資，第二年的年底可獲利45%，并將本金收回，但該項(xiàng)投資不得超過2萬元；第種是在第二年的年初投資，第三年的年底可獲利65%，并將本金收回，但該項(xiàng)投資不得超過1.5萬元；第種是在第三年的年初投資，年底收回本金，且可獲利35%，但該項(xiàng)投資不得超過1萬元。現(xiàn)在本公司準(zhǔn)備拿出3萬元來投資，問如何計(jì)劃可使到第三年年未本利和最大？,解：?jiǎn)栴}分析。該問題的實(shí)際投資背景如下表所示：,（1）確定決策變量：設(shè)x,ij,表示第i年對(duì)第j個(gè)方案的投資額,i=1,2,3; j=1,2,3,4,年份 一 二 三 四,x,11,1.15x,11,x,12,1.45,x,12,

4、x,21,1.15,x,21,x,23,1.65,x,23,x,31,1.15,x,31,x,34,1.35,x,34,（2）確定目標(biāo)函數(shù)：第三年年未的本利和為,maxz=1.65x,23,+1.15x,31,+1.35x,34,（3）,確定約束條件：,每一年的投資額應(yīng)等于當(dāng)年公司擁有的資金數(shù)：,x,11,+x,12,=3,x,21,+x,23,=1.15x,11,x,31,+x,34,=1.45x,12,+1.15x,21,每個(gè)方案投資額的限制：,x,12,2,x,23,1.5 非負(fù)約束：x,ij,0,i=1,2,3;j=1,2,3,4,x,34,1,案例2,債券投資問題,國(guó)家農(nóng)業(yè)銀行(Na

5、tional Agricultural Bank,NAB)希望為十五名要提前退休的員工制定一項(xiàng)提前退休計(jì)劃。這些員工將要在從明年開始的七年內(nèi)逐漸退休完。為了給這個(gè)提前退休計(jì)劃籌集資金，此銀行決定在這七年期間進(jìn)行債券投資。下表給出了每年應(yīng)向這些提早退休的員工支付的金額，這些金額必須在每年年初支付。,年,1,2,3,4,5,6,7,金額（千歐元）,1000,600,640,480,760,1020,950,表：每年要求金額,此銀行計(jì)劃購(gòu)買三種不同的債券，即SNCF公司（法國(guó)國(guó)營(yíng)鐵路公司）的債券，F(xiàn)ujutsu（富士通）公司債券，以及國(guó)債。未投資于這些債券的資金將作為儲(chǔ)蓄保存，儲(chǔ)蓄的利率為3.2%,

6、下表列出了各個(gè)債券的收益,時(shí)間長(zhǎng)度,以及價(jià)格等信息.這些債券只能按整數(shù)數(shù)目進(jìn)行購(gòu)買,并且一旦購(gòu)買之后在債券期限內(nèi)即無法更改投資金額.每年只返回投資的利息.此退休計(jì)劃的負(fù)責(zé)人決定只在第一年年,初購(gòu)買債券,而在此后的幾年內(nèi)不再購(gòu)買,應(yīng)該如何分配在各個(gè)債券的投資金額才能使得只需要花費(fèi)最少的資金就能夠滿足此退休計(jì)劃的要求?,債券,價(jià)值(千歐元),利率,期限,SNCF,Fujitsu,國(guó)債,1.0,0.8,0.5,7.0%,7.0%,6.5%,5年,4年,6年,表: 債券信息,分析：,決策變量：初始投資y，債券購(gòu)買量,x,i,，每年的儲(chǔ)蓄量,S,t,P債券價(jià)格，D,t,每年資金需求，,r,i,-債券利率

7、,第1年,第24年,第5，6年,第7年,例題3：養(yǎng)老金管理問題,華信金融公司管理的金融產(chǎn)品中有一只很受贊譽(yù)的養(yǎng)老基金，這些養(yǎng)老基金是很多公司用來為其雇員提供養(yǎng)老金的，華信公司希望能夠進(jìn)行合理的投資來保證養(yǎng)老金的供應(yīng)。,現(xiàn)在是2007年的12月了，在接下去的10年中需要支付的總的養(yǎng)老金如表所示：,表： 未來十年的養(yǎng)老金需求,年份,需要支付的養(yǎng)老金（萬美元）,2008,800,2009,1200,2010,1300,2011,1400,2012,1600,2013,1700,2014,2000,2015,2100,2015,2200,2016,2400,為了使養(yǎng)老基金的提供有安全保證，華信公司希望

8、投資在能夠與未來10年中的養(yǎng)老金支付相匹配的項(xiàng)目。養(yǎng)老基金管理中心授權(quán)華信公司的投資項(xiàng)目只能是資本市場(chǎng)基金和債券。資本市場(chǎng)基金獲得每年固定的5%的利息收入，公司所考慮投資的四只債券的特征如表3-7所示。,表： 四種債券的信息,債券,當(dāng)前價(jià)格（美元）,年利息率,到期日,面值（美元）,債券1,980,4%,2009.1.1,1000,債券2,920,2%,2011.1.1,1000,債券3,750,0%,2013.1.1,1000,債券4,800,3%,2016.1.1,1000,所有的債券均可在2008年1月1日購(gòu)買，可以購(gòu)買任意數(shù)量單位。債券在每年的1月1日付息，支付期為購(gòu)買后的第一年到到期日

9、為止(包括到期日)。因此這些每年1月1日的利息支付獲得正好能夠用來沖抵當(dāng)年養(yǎng)老金的支付，所有多余的利息收入將存入資本市場(chǎng)基金。為金融計(jì)劃的保守起見，華信公司假定所有的養(yǎng)老金支付在每年的年初，正好在利息收入(包括資本市場(chǎng)基金的利息收入)獲得之后，債券的面值也將在到期日獲得。既然當(dāng)前的債券價(jià)格低于面值，真正的債權(quán)的收益比利息率要高。如債券3是一個(gè)零利息率的債券，所以每年得到的利息為0，但是到到期日獲得的面值要遠(yuǎn)大于當(dāng)年債券的購(gòu)得價(jià)格。,華信公司希望在2008年1月1日用最小可能的投資(包括市場(chǎng)基金的存款)來應(yīng)付到2016年為止的所有所需的養(yǎng)老金的支付，請(qǐng)對(duì)此問題進(jìn)行分析，并求出最優(yōu)投資方案。,例題

10、4：定額投資問題,通用公司的董事會(huì)正在考慮幾個(gè)大型的投資項(xiàng)目，每個(gè)項(xiàng)目只能投資一次，且各項(xiàng)目所需要的投資金額與能夠產(chǎn)生的預(yù)期收益是不同的，如表所示：,表：投資額及預(yù)期收益,投資項(xiàng)目,預(yù)期收益（百萬美元）,所需資金（百萬美元）,1,17,43,2,10,28,3,15,34,4,19,48,5,7,17,6,13,32,7,9,23,假設(shè)公司現(xiàn)有的總投資金額為1億美元，其中投資項(xiàng)目1和項(xiàng)目2是互斥的，項(xiàng)目3與項(xiàng)目4也是互斥的。此外，如果不選擇項(xiàng)目1或是項(xiàng)目2的話，就不能選擇項(xiàng)目3、4。投資項(xiàng)目5、6、7上沒有附加約束。問題的目標(biāo)是通過組合各種投資，使得估計(jì)的預(yù)期收益最大。,解：,例題5,（合理下

11、料問題）要用一批長(zhǎng)度為7.4米的園鋼做100套鋼架，每套鋼架由2.9米、2.1米、1.5米的園鋼各一根組成，問：應(yīng)如何下料才能使所用的原料最??？,解：?jiǎn)栴}分析：一根長(zhǎng)度為7.4米的園鋼，要裁出2.9米、2.1米、1.5米的料有多種裁法，如可裁出一根2.9米、二根2.1米，也可裁出三根2.1米的。這樣我們把所有裁法列舉出來，如下表所示：,下料 方案,根數(shù) 一 二 三 四 五 六 七 八,長(zhǎng)度米,2.9 1 1 1 2 0 0 0 0,2.1 2 0 1 0 1 2 3 0,1.5 0 3 1 1 3 2 0 4,合計(jì) 7.1 7.4 6.5 7.3 6.6 7.2 6.3 6,料頭（米） 0.3

12、 0 0.9 0.1 0.8 0.2 1.1 1.4,（1）,確定決策變量：設(shè)x,j,表示按第j種方案所用的園鋼的數(shù)量,（2）,確定目標(biāo)函數(shù)：?jiǎn)栴}要求所用原料最省，所用原料為： minz=x,1,+x,2,+x,3,+x,4,+x,5,+x,6,+x,7,+x,8,（3）,確定約束條件：,2.9米園鋼的數(shù)量限制 x,1,+x,2,+x,3,+2x,4,100,2.1米園鋼的數(shù)量限制 2x,1,+x,3,+x,5,+2x,6,+3x,7,100,1.5米園鋼的數(shù)量限制 3x,2,+x,3,+x,4,+3x,5,+2x,6,+4x,3,100,非負(fù)限制 x,j,0，且為整數(shù)， j=1,2,8,建立

13、線性規(guī)劃模型的一般步驟：,（1）確定決策變量；,（2）確定目標(biāo)函數(shù)；,（3）確定約束條件。,例題6,一個(gè)木材儲(chǔ)運(yùn)公司有很大的倉(cāng)庫(kù)用以儲(chǔ)運(yùn)出售木材。由于木材季度價(jià)格的變化，該公司于每季度初購(gòu)進(jìn)木材，一部分于本季度內(nèi)出售，一部分儲(chǔ)存起來以后出售。已知該公司倉(cāng)庫(kù)的最大儲(chǔ)存量為2000萬米,3,，儲(chǔ)存費(fèi)用為（70+100u）千元/萬米,3,，u為存儲(chǔ)時(shí)間（季度數(shù)）。已知每季度的買進(jìn)賣出價(jià)及預(yù)計(jì)的銷售量如下表所示。,季度,買進(jìn)價(jià)（萬元/萬米,3,）,賣出價(jià)（萬元/萬米,3,）,預(yù)計(jì)銷售量（萬米,3,）,冬,410,425,1000,春,430,440,1400,夏,460,465,2000,秋,450,

14、455,1600,由于木材不宜久貯，所有庫(kù)存木材應(yīng)于每年秋末售完。為使售后利潤(rùn)最大，試建立這個(gè)問題的線性規(guī)劃模型。,設(shè)y,i,分別表示冬、春、夏、秋四個(gè)季度采購(gòu)的木材數(shù)，x,ij,代表第i季度采購(gòu)的用于第j季度銷售的木材數(shù)。,季度,買進(jìn)價(jià)（萬元/萬米,3,）,賣出價(jià)（萬元/萬米,3,）,預(yù)計(jì)銷售量（萬米,3,）,冬,410,425,1000,春,430,440,1400,夏,460,465,2000,秋,450,455,1600,例題7,自行車生產(chǎn)規(guī)劃問題,有一家公司生產(chǎn)兒童自行車。在下表中給出了明年預(yù)期的銷售量（以千輛為單位計(jì)）。此公司的生產(chǎn)能力為每個(gè)月30000輛自行車。通過工人加班，可以

15、將產(chǎn)量提高50%，但會(huì)將每輛自行車的生產(chǎn)成本從30歐元提高到40歐元。,表： 明年的銷售預(yù)期（千輛）,1月,2月,3月,4月,5月,6月,7月,8月,9月,10月,11月,12月,30,15,15,25,33,40,45,45,26,14,25,30,當(dāng)前自行車的庫(kù)存量為2000輛，對(duì)于庫(kù)存中的每輛自行車，在每個(gè)月月底都需要支出5歐元的存儲(chǔ)費(fèi)用。我們假定此公司的庫(kù)存能力是無限的?，F(xiàn)在是一月一日，在下面的十二個(gè)月里面每個(gè)月應(yīng)生產(chǎn)和存儲(chǔ)多少輛自行車才能滿足此銷售預(yù)期，并最小化總成本？,分析：,決策變量：設(shè)t時(shí)間內(nèi)的正常工作時(shí)間內(nèi)和加班時(shí)間內(nèi)生產(chǎn)的自行車數(shù)量分別為,x,t,，,y,t,每個(gè)月月底時(shí)庫(kù)

16、存的自行車數(shù)量為,S,t,目標(biāo)：生產(chǎn)成本與庫(kù)存成本和最小,約束： 第一個(gè)月,其它月份,生產(chǎn)能力限制,最優(yōu)方案如下：,例題8：,計(jì)算機(jī)生產(chǎn)問題,案例概述：,Sytech 國(guó)際公司是一家在同行業(yè)中處于領(lǐng)先地位的計(jì)算機(jī)和外圍設(shè)備的制造商。公司的主導(dǎo)產(chǎn)品分類如下：大型計(jì)算機(jī)（MFRAMES）、小型計(jì)算機(jī)（MINIS）、個(gè)人計(jì)算機(jī)（PCS）、和打印機(jī)（PRINTERS）。公司的兩個(gè)主要市場(chǎng)是北美和歐洲。,公司一直按季度作出公司最初的重要決策。公司必須按照營(yíng)銷部門的需求預(yù)測(cè)來對(duì)分布在全球的三個(gè)工廠調(diào)整產(chǎn)量，公司下一季度需求預(yù)測(cè)如下：,而公司的三個(gè)工廠的生產(chǎn)能力限度又使得其不能隨心所欲地在任一工廠進(jìn)行生產(chǎn)，

17、限制主要是各工廠規(guī)模及勞動(dòng)力約束。,最終分析所要求的數(shù)據(jù)由會(huì)計(jì)部門提供，下表所顯示的數(shù)據(jù)表示單位利潤(rùn)貢獻(xiàn)（稅后）：,根據(jù)以上信息，為SYTECH公司建立了一個(gè)線性優(yōu)化模型，幫助其進(jìn)行生產(chǎn)決策。,解：,例題9：,蔗糖生產(chǎn)計(jì)劃,在澳大利亞甘蔗的收割已經(jīng)實(shí)現(xiàn)了高度機(jī)械化。甘蔗在砍下之后將馬上通過運(yùn)行于小型鐵路網(wǎng)上的貨車運(yùn)送到蔗糖廠。一輛貨車的運(yùn)量、能夠生產(chǎn)的蔗糖取決于甘蔗收購(gòu)的地點(diǎn)以及甘蔗成熟的程度。在收割之后，甘蔗中的含糖量將由于發(fā)酵而迅速下降，在一段時(shí)間之后，所含糖份將完全流失?，F(xiàn)在有11輛貨車到達(dá)了蔗糖廠，每輛貨車運(yùn)載的甘蔗量都相同。已經(jīng)對(duì)每輛貨車每小時(shí)的損失量以及剩余時(shí)間進(jìn)行了測(cè)算，具體數(shù)據(jù)

18、如表所示。,表 每車甘蔗屬性,貨車編號(hào),1,2,3,4,5,6,7,8,9,10,11,損失率（千克/小時(shí)）,43,26,37,28,13,54,62,49,19,28,30,剩余時(shí)間,8,8,2,8,4,8,8,8,8,8,8,在制糖廠內(nèi)有三條生產(chǎn)線，每輛貨車都可以選擇在哪條生產(chǎn)線上進(jìn)行加工。一車甘蔗的加工時(shí)間為兩個(gè)小時(shí)。必須在這車甘蔗的質(zhì)量壽命結(jié)束之前完成加工。制糖廠的經(jīng)理希望找出一個(gè)生產(chǎn)計(jì)劃，使總的蔗糖損失降到最低。,貨車編號(hào),1,2,3,4,5,6,7,8,9,10,11,損失率（千克/小時(shí)）,43,26,37,28,13,54,62,49,19,28,30,剩余時(shí)間,8,8,2,8,

19、4,8,8,8,8,8,8,表 每車甘蔗屬性,解：,例題10：,石油精煉問題,石油精煉廠將使用兩種原油生產(chǎn)出丁烷(butane)，汽油(petrol)，柴油(dieseloil)，以及民用燃料油(heating oil)。為生產(chǎn)出這些產(chǎn)品，需要四道工序：分離、轉(zhuǎn)化、提純、混合。,在分離工序中將把原材料進(jìn)行分餾，使其分離為丁烷(butane)、石腦油(naphtha)、輕柴油(gasoil)、以及殘?jiān)?。殘?jiān)缓髮⑦M(jìn)行催化裂解以獲得較輕的產(chǎn)品。從分餾工序得到的各種產(chǎn)品將進(jìn)行提純(脫硫)，或通過重整工藝增加其辛烷值。最終，為獲得可以出售的最終產(chǎn)品，精煉廠需要將若干種中間產(chǎn)物進(jìn)行混合，以滿足商業(yè)產(chǎn)品所

20、要求的各種屬性。下圖中是對(duì)此精煉廠的生產(chǎn)過程的簡(jiǎn)單的示意圖。,石油精煉流程圖,在分餾之后，原油1能夠得到3%的丁烷，15%的石腦油，40%的輕柴油，以及15%的殘?jiān)?。原?能夠得到5%的丁烷，20%的石腦油，25%的輕柴油，以及10%的殘?jiān)?。?duì)石腦油進(jìn)行重整能夠得到5%的丁烷和85%的重整油(重整石腦油)。對(duì)殘?jiān)拇呋呀饪梢陨?5%的裂解石腦油和35%的裂解輕柴油(注意，由于在此工藝中也將生成15%的氣體和5%的石油焦以及其他另一種無法計(jì)入我們的問題中的殘余物，因此這兩個(gè)百分比之和不等于1)。汽油由三種成分混合而成：重組石腦油(重組油)，丁烷，以及裂解石腦油。柴油可以通過將脫硫輕柴油，裂解

21、輕柴油，以及裂解石腦油混合得到。民用燃料油由輕柴油及裂解石腦油組成，對(duì)其成分含量沒有要求。,法律規(guī)定了一些汽油和柴油的規(guī)格指標(biāo)。對(duì)于汽油有三項(xiàng)重要指標(biāo)：辛烷值，蒸汽壓，以及揮發(fā)性。辛烷值是對(duì)汽油的抗爆能力的度量。蒸汽壓能夠反映出汽油儲(chǔ)存過程中發(fā)生爆炸的風(fēng)險(xiǎn)，尤其在炎熱氣候條件下。揮發(fā)性能夠決定在寒冷氣候條件下發(fā)動(dòng)機(jī)是否能夠容易啟動(dòng)?？諝馕廴痉ㄒ?guī)對(duì)柴油的含硫量進(jìn)行了規(guī)定。表2-19中列出了最終產(chǎn)品的規(guī)格指標(biāo)和中間產(chǎn)品的成分組成。如果對(duì)某一項(xiàng)沒有限制，則對(duì)應(yīng)在域保留為空。我們假定所有這些成分都將按照質(zhì)量線性混合(實(shí)際上只有含硫量才如此)。,表 中間產(chǎn)物和最終產(chǎn)品規(guī)格屬性,規(guī)格,丁烷,重整油,裂解石

22、腦油,裂解輕柴油,去硫輕柴油,汽油,柴油,辛烷值,120,100,74,=94,蒸氣壓,60,2.6,4.1,=17,含硫量（%）,0.12,0.76,0.03,=0.05,下個(gè)月此精煉廠需要生產(chǎn)20,000噸丁烷，40,000噸汽油，30,000噸柴油，42,000噸燃料油?？捎迷头謩e為250,000噸原油1，300,000噸原油2。重整爐每月加工能力為70,000噸，脫硫工藝每月加工能力為80,000噸，裂解工藝每月加工能力為40,000噸。各個(gè)工藝的成本取決于其中使用的燃料和催化劑。整流，重整，脫硫，和裂解的成本分別為每噸2.10，4.18，2.04，0.60歐元。,解：此案例的特點(diǎn)是

23、信息多而且雜。首先進(jìn)行適當(dāng)?shù)男畔⒄?，列為?和表2。,表1 原油分餾可得到的產(chǎn)品及可用量,丁烷,石腦油,輕柴油,殘?jiān)?可用量,原油1,3%,15%,40%,15%,250,000,原油2,5%,20%,25%,10%,300,000,表2 各工序加工能力和單位加工成本,工序,單位成本（歐元/噸）,加工能力（噸）,整流,2.10,重整,4.18,70000,脫流,2.04,80000,裂解,0.60,40000,案例11、,有一艘貨輪，分前、中、后三個(gè)艙位，它們的容積與最大允許載重量如表1所示?，F(xiàn)有三種貨物待運(yùn)，已知有關(guān)數(shù)據(jù)列于表2。為了航運(yùn)安全，要求前、中、后艙在實(shí)際載重量上大體保持各艙最大

24、允許載重量的比例關(guān)系，具體要求前、后艙分別與中艙之間載重量比例上偏差不超過15%，前、后艙之間不超過10%。問該貨輪應(yīng)裝載A，B，C各多少件，運(yùn)費(fèi)收入為最大？試建立這個(gè)問題的線性規(guī)劃模型。,前艙,中艙,后艙,最大允許載重量（噸）,2000,3000,1500,容積（立方米）,4000,5400,1500,表1,商品,數(shù)量（件）,每件體積（立方米/件）,每件重量（噸/件）,運(yùn)價(jià)（元/件）,A,600,10,8,1000,B,1000,5,6,700,C,800,7,5,600,設(shè)表示x,ij,裝于第j(j=1,2,3)艙位的第i(i=1,2,3)種商品的數(shù)量,艙位載重限制,艙位體積限制,商品數(shù)量

25、限制,平衡條件,前艙,中艙,后艙,重量,2000,3000,1500,容積,4000,5400,1500,商品,數(shù)量,體積,重量,運(yùn)價(jià),A,600,10,8,1000,B,1000,5,6,700,C,800,7,5,600,案例12 .,(倉(cāng)庫(kù)租用問題)捷運(yùn)公司擬在下一年度的1-4月的4個(gè)月內(nèi)需租用倉(cāng)庫(kù)堆放物資.已知各月份所需倉(cāng)庫(kù)面積數(shù)列于表1.倉(cāng)庫(kù)租借費(fèi)用隨合同期而定,期限越長(zhǎng),折扣越大,具體數(shù)字見表2.租借倉(cāng)庫(kù)的合同每月初都可辦理,每份合同具體規(guī)定租用面積數(shù)和期限.因此該廠可根據(jù)需要,在任何一個(gè)月初辦理租借合同.每次辦理時(shí)可簽一份,也可簽若干份租用面積和租借期限不同的合同,試確定該公司簽

26、訂租借合同的最優(yōu)決策,目的是使所付租借費(fèi)用最小.,月份,1,2,3,4,所需倉(cāng)庫(kù)面積(100m,2,),15,10,20,12,表1,合同租借期限,1個(gè)月,2個(gè)月,3個(gè)月,4個(gè)月,倉(cāng)庫(kù)借費(fèi)用(元/100m,2,),2800,4500,6000,7300,表2,解,:1),設(shè)決策變量x,ij,表示捷運(yùn)公司在第i(I=1,2,3,4)個(gè)月初簽訂的租借期為j(j=1,2,3,4)個(gè)月的倉(cāng)庫(kù)面積的合同(單位為100m,2,).因5月份起該公司不需要租借倉(cāng)庫(kù),故x,24,x,33,x,34,x,42,x,43,x,44,均為零,2)目標(biāo)函數(shù):使總的租借費(fèi)用最小,3)約束條件:每個(gè)月份所需倉(cāng)庫(kù)面積的限制,

27、二、 整數(shù)規(guī)劃模型,案例1,某單位有5個(gè)擬選擇的投資項(xiàng)目，其所需投資額與期望收益如下表。由于各項(xiàng)目之間有一定聯(lián)系，A、C、E之間必須選擇一項(xiàng)且僅需選擇一項(xiàng)；B和D之間需選擇也僅需選擇一項(xiàng)；又由于C和D兩項(xiàng)目密切相關(guān)，C的實(shí)施必須以D的實(shí)施為前提條件，該單位共籌集資金15萬元，問應(yīng)該選擇哪些項(xiàng)目投資，使期望收益最大？,項(xiàng)目,所需投資額（萬元）,期望收益（萬元）,A,6,10,B,4,8,C,2,7,D,4,6,E,5,9,解：決策變量：設(shè),目標(biāo)函數(shù)：期望收益最大,約束條件：投資額限制條件 6x,1,+4x,2,+2x,3,+4x,4,+5x,5,15,項(xiàng)目A、C、E之間必須且只需選擇一項(xiàng)：x,1

28、,+x,3,+x,5,=1,項(xiàng)目C的實(shí)施要以項(xiàng)目D的實(shí)施為前提條件： x,3,x,4,項(xiàng)目B、D之間必須且只需選擇一項(xiàng)：x,2,+x,4,=1,歸納起來，其數(shù)學(xué)模型為：,案例2,某服務(wù)部門各時(shí)段（每2小時(shí)為一時(shí)段）需要的服務(wù)員人數(shù)如下表，按規(guī)定，服務(wù)員連續(xù)工作8小時(shí)（即四個(gè)時(shí)段）為一班，現(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門服務(wù)員總數(shù)最小。,時(shí)段,1,2,3,4,5,6,7,8,服務(wù)員最少數(shù)目,10,8,9,11,13,8,5,3,解：設(shè)在第j時(shí)段開始時(shí)上班的服務(wù)員人數(shù)為x,j,，由于第j時(shí)段開始時(shí)上班的服務(wù)員將在第(j+3)時(shí)段結(jié)束時(shí)下班，故決策變量只需考慮x,1,x,2,x,3,x,4,x

29、,5，,此問題的數(shù)學(xué)模型為：,案例3：,護(hù)士工作時(shí)間調(diào)度問題,Mr.Schedule 先生受人之托要為 St.Joseph醫(yī)院的心腦血管部門制定護(hù)士的工作時(shí)間表。在心腦血管部門中一個(gè)工作日分為12個(gè)兩小時(shí)長(zhǎng)的時(shí)段，每個(gè)時(shí)段的人員要求都不同。例如，在夜間只要求有很少的幾個(gè)護(hù)士就足夠了，但是在早晨為了給病人提供特殊服務(wù)，需要很多護(hù)士。下表列出了每個(gè)時(shí)段的人員需求量。,編號(hào),時(shí)段,需要護(hù)士人數(shù),0,1,2,3,4,5,6,7,8,9,10,11,00am-02am,02am-04am,04am-06am,06am-08am,08am-10am,10am-12pm,12pm-02pm,02pm-04p

30、m,04pm-06pm,06pm-08pm,08pm-10pm,10pm-12am,15,15,15,35,40,40,40,30,31,35,30,20,問題1：請(qǐng)計(jì)算出為滿足需求最少需要多少護(hù)士，假定已知護(hù)士每天工作8小時(shí)，且在工作四小時(shí)后需要休息兩小時(shí)。,問題2：此部門目前只有80名護(hù)士，這個(gè)數(shù)目不足以滿足給定的需求。因此Schedule先生建議每天安排部分人加班。每天加班時(shí)間為2小時(shí)，且緊隨在后一個(gè)四小時(shí)工作時(shí)段之后，中間沒有休息。請(qǐng)給出護(hù)士工作時(shí)間安排方案，以使需要加班的護(hù)士數(shù)目最少。,分析：設(shè),x,t,為時(shí)段,t,開始工作的護(hù)士數(shù)目,問題1模型,最優(yōu)方案,由此我們看到，第1問題求出

31、的最優(yōu)解為至少需要100名護(hù)士，然而目前只有80名，這就需要安排一部分人加班。,設(shè)變量,y,t,表示,t,時(shí)段開始工作并且需要加班2小時(shí)的護(hù)士人數(shù),問題需要求的是滿足服務(wù)需要，最小需要加班的人數(shù)，因此模型變?yōu)椋?t時(shí)段加班人數(shù)小于開始工作人數(shù),總?cè)藬?shù)限制,各時(shí)段需求人數(shù)限制,最優(yōu)方案如下表，表中列示了各時(shí)段開始工作的人數(shù)及保時(shí)段需要加班的人數(shù)，最少需要加班人數(shù)為40人。,案例4,（固定費(fèi)用問題）有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用售價(jià)、資源單件耗量及組成三種產(chǎn)品生產(chǎn)的固定費(fèi)用見下表。要求制定一個(gè)生產(chǎn)計(jì)劃，使總收益最大。,產(chǎn)品,單件耗量,資源,1,2,3,資源量,A,2,4,8

32、,500,B,2,3,4,300,C,1,2,3,100,單件可變費(fèi)用,4,5,6,固定費(fèi)用,100,150,200,單件售價(jià),8,10,12,解：總收益等于銷售收入減去生產(chǎn)上述產(chǎn)品的固定費(fèi)用和可變費(fèi)用之和。建模碰到的困難主要是事先不能確切知道某種產(chǎn)品是否生產(chǎn)，因而不能確定相應(yīng)的固定費(fèi)用是否發(fā)生。下面借助0-1變量解決這個(gè)困難,設(shè)xj是第j種產(chǎn)品的產(chǎn)量，j=1,2,3,再設(shè),則問題的整數(shù)規(guī)劃模型為：,M為很大的正數(shù),案例5,（工件排序問題）用4臺(tái)機(jī)床加工3件產(chǎn)品。各產(chǎn)品的機(jī)床加工順序，以及產(chǎn)品i在機(jī)床j上的加工工時(shí)a,ij,如下表。由于某種原因，產(chǎn)品2的加工總時(shí)間不得超過d，現(xiàn)要求確定各件產(chǎn)品

33、在機(jī)床上的加工方案，使在最短的時(shí)間內(nèi)加工完全部產(chǎn)品。,產(chǎn)品1,a11 a13 a14,機(jī)床1 機(jī)床3 機(jī)床4,產(chǎn)品2,a21 a22 a24,機(jī)床1 機(jī)床2 機(jī)床4,產(chǎn)品3,a32 a33,機(jī)床2 機(jī)床3,解：設(shè)xij表示產(chǎn)品i在機(jī)床j上開始加工的時(shí)間(i=1,2,3;j=1,2,3,4),下面將逐步列出問題的整數(shù)規(guī)劃模型,1、同一件產(chǎn)品在不同機(jī)床上的加工順序約束,對(duì)于同一件產(chǎn)品，在下一臺(tái)機(jī)床上加工的開始時(shí)間不得早于在上一臺(tái)機(jī)床上加工的約束時(shí)間，故應(yīng)有：,產(chǎn)品1：,及,產(chǎn)品2：,及,產(chǎn)品3：,2、每一臺(tái)機(jī)床對(duì)不同產(chǎn)品的加工順序約束,一臺(tái)機(jī)床在工作中，如已開始的加工還沒有結(jié)束，則不能開始另一件產(chǎn)

34、品的加工。對(duì)于機(jī)床1，有兩種加工順序?；蛳燃庸ぎa(chǎn)品1，后加工產(chǎn)品2；或反之。對(duì)于其它3臺(tái)機(jī)床，情況也類似。為了容納兩種相互排斥的約束條件，對(duì)于每臺(tái)機(jī)床，分別引入0-1變量,各y,j,的意義是明顯的。如當(dāng)y,j,=0時(shí)，表示機(jī)床1先加工產(chǎn)品1，后加工產(chǎn)品2，當(dāng)y,j,=1時(shí)，表示機(jī)床1先加工產(chǎn)品2，后加工產(chǎn)品1。,機(jī)床1：,及,機(jī)床2：,及,機(jī)床3：,及,機(jī)床4：,及,那么，每臺(tái)機(jī)床上的加工產(chǎn)品的順序可用下列四組約束條件來保證,3、產(chǎn)品2的加工時(shí)間約束,產(chǎn)品2的開始加工時(shí)間是x,21,，結(jié)束加工時(shí)間是x,24,+a,24,，故應(yīng)有：,4、目標(biāo)函數(shù)的建立,設(shè)全部產(chǎn)品加工完畢的結(jié)束時(shí)間為W，由于三件

35、產(chǎn)品的加工結(jié)束時(shí)間分別為x,14,+a,14，,x,24,+a,24，,x,33,+a,33，,故全部產(chǎn)品的實(shí)際加工結(jié)束時(shí)間為：,轉(zhuǎn)化為線性表達(dá)式：,0-1規(guī)劃特別適合用在選址問題中,某個(gè)公司準(zhǔn)備投資一項(xiàng)大型的房地產(chǎn)開發(fā)項(xiàng)目，該項(xiàng)目是建造一個(gè)占地?cái)?shù)平方英里的住宅小區(qū)。由于地球變暖的趨勢(shì)越來越嚴(yán)重，小區(qū)如何預(yù)防火災(zāi)變得越來越重要。因此，公司需要解決的一個(gè)重要問題之一是如何布置兩個(gè)消防站。為便于規(guī)劃，整個(gè)小區(qū)分為5個(gè)區(qū)域，每個(gè)區(qū)域最多只能設(shè)一個(gè)消防站。每個(gè)消防站必須負(fù)責(zé)處理所處區(qū)域以及分配給該站的其他區(qū)域發(fā)生的火災(zāi)。這樣，要作出的決策就包括：（1）消防站設(shè)在哪個(gè)區(qū)域？（2）將其他區(qū)域分配給某一個(gè)消

36、防站。問題的目標(biāo)是發(fā)生火災(zāi)之后平均的反應(yīng)時(shí)間最短。,下表給出的是將消防站建在各區(qū)域（行）的情況下，每個(gè)區(qū)域?qū)馂?zāi)反應(yīng)的平均時(shí)間，表中最后一行給出是各區(qū)域每天估計(jì)會(huì)發(fā)生火災(zāi)的平均次數(shù)。,案例6：,消防站位置設(shè)置問題,問題：（1）消防站設(shè)在哪個(gè)區(qū)域？（2）將其他區(qū)域分配給某一個(gè)消防站。目標(biāo)是發(fā)生火災(zāi)之后平均的反應(yīng)時(shí)間最短。,下表給出的是將消防站建在各區(qū)域（行）的情況下，每個(gè)區(qū)域?qū)馂?zāi)反應(yīng)的平均時(shí)間，表中最后一行給出是各區(qū)域每天估計(jì)會(huì)發(fā)生火災(zāi)的平均次數(shù)。,消防站所在區(qū)域,各區(qū)發(fā)生火災(zāi)后的反應(yīng)時(shí)間(分),1,2,3,4,5,1,5,12,30,20,15,2,20,4,15,10,25,3,15,20

37、,6,15,12,4,25,15,25,4,10,5,10,25,15,12,5,每年平均發(fā)生火災(zāi)次數(shù),2,1,3,1,3,有一家大公司希望開設(shè)一些新的倉(cāng)庫(kù)，以向銷售中心供貨。每開設(shè)一個(gè)新倉(cāng)庫(kù)都有一些固定費(fèi)用。貨物將從倉(cāng)庫(kù)運(yùn)輸?shù)礁浇匿N售中心。每次運(yùn)輸?shù)倪\(yùn)費(fèi)取決于運(yùn)輸?shù)木嚯x。這兩種類型的費(fèi)用非常不同：倉(cāng)庫(kù)開設(shè)費(fèi)用屬于投資支出，通常在若干年后將勾銷，而運(yùn)輸費(fèi)用屬于運(yùn)營(yíng)成本。我們假定這兩種費(fèi)用可比，為此可能需要以年為單位計(jì)算運(yùn)營(yíng)費(fèi)用。,有12個(gè)可以建造新倉(cāng)庫(kù)的位置，并且需要從這些倉(cāng)庫(kù)向12個(gè)銷售中心供貨。下表給出了每個(gè)倉(cāng)庫(kù)完全滿足每個(gè)客戶（銷售中心）需求所需的總成本（千歐元，不是單位成本）。因此，

38、例如從倉(cāng)庫(kù)1向客戶9（根據(jù)表3可以看到此客戶總需求量為30噸）供貨的單位成本為60000歐元/30噸，即2000歐元/噸。,如果無法進(jìn)行送貨，則對(duì)應(yīng)的成本標(biāo)記為無窮大。,倉(cāng)庫(kù)位置設(shè)置問題,案例7：,客戶,倉(cāng)庫(kù) 1 2 3 4 5 6 7 8 9 10 11 12,1 100 80 50 50 60 100 120 90 60 70 65 110,2 120 90 60 70 65 110 140 110 80 80 75 130,3 140 110 80 80 75 130 160 125 100 100 80 150,4 160 125 100 100 80 150 190 150 130

39、,5 190 150 130 200 180 50 ,6 200 180 150 100 80 50 50 60 100,7 100 80 50 50 60 100 120 90 60 70 65 110,8 120 90 60 70 65 110 140 110 80 80 75 130,9 140 110 80 80 75 130 160 125 100 100 80 150,10 160 125 100 100 80 150 190 150 130 ,11 190 150 130 200 180 150 ,12 200 180 150 100 80 50 50 60 100,表格1：滿足

40、客戶需求所需的運(yùn)輸成本,此外，對(duì)每個(gè)倉(cāng)庫(kù)，還有如下信息：倉(cāng)庫(kù)建設(shè)的固定費(fèi)用（需要計(jì)入目標(biāo)函數(shù)）和倉(cāng)庫(kù)的容量上限，這些信息都列于表2中。,表格2：倉(cāng)庫(kù)建設(shè)費(fèi)用和容量限制,倉(cāng)庫(kù),1,2,3,4,5,6,7,8,9,10,11,12,建設(shè)費(fèi)用,3500,9000,10000,4000,3000,9000,9000,3000,4000,10000,9000,35000,容量上限,300,250,100,180,275,300,200,220,270,250,230,180,表3列出了各個(gè)銷售中心（客戶）的需求量,客戶,1,2,3,4,5,6,7,8,9,10,11,12,需求量,120,80,75,1

41、00,110,100,90,60,30,150,95,120,任何時(shí)候都要保證滿足客戶需求，可以從多個(gè)倉(cāng)庫(kù)向同一個(gè)客戶送貨。應(yīng)在哪些位置開辦倉(cāng)庫(kù)才能使總的建設(shè)成本以及運(yùn)輸成本最低，同時(shí)仍然能夠滿足所有客戶需求？,分析,決策變量：12個(gè)倉(cāng)庫(kù)中需要決策選擇哪些倉(cāng)庫(kù)，,每個(gè)被選中的倉(cāng)庫(kù)運(yùn)輸給每個(gè)客戶的運(yùn)輸量,x,ij,目標(biāo)：總成本=建設(shè)成本+運(yùn)輸成本,約束：倉(cāng)庫(kù)容量上限約束,客戶需求量約束,只有當(dāng)某一位置建設(shè)了倉(cāng)庫(kù)才能向客戶運(yùn)輸產(chǎn)品,數(shù)據(jù)處理,最優(yōu)方案,更深入的問題：一個(gè)客戶只允許由一個(gè)倉(cāng)庫(kù)共貨，但一個(gè)倉(cāng)庫(kù)可供多個(gè)客戶。,案例8：,所得稅交納點(diǎn)選址問題,所得稅管理部門計(jì)劃對(duì)某個(gè)地區(qū)的所得稅交納點(diǎn)網(wǎng)絡(luò)

42、進(jìn)行重新設(shè)計(jì)。下圖是對(duì)此地區(qū)內(nèi)的城市和主要道路的示意圖。城市這邊的黑體數(shù)字表示城市的居民數(shù)目，單位為千人。在連接城市之間的弧上標(biāo)出了它們之間的距離，單位為千米。為覆蓋各城市，所得稅管理部門決定在三個(gè)城市中設(shè)置納稅點(diǎn)。應(yīng)在哪三個(gè)城市中設(shè)置納稅點(diǎn)才能使居民與最近的納稅點(diǎn)之間平均距離最?。?1,2,3,5,7,10,11,4,9,6,12,8,15,22,18,12,22,12,19,19,21,20,24,30,25,19,22,15,18,24,15,10,12,18,24,20,19,22,16,5,13,11,12,1,2,3,5,7,10,11,4,9,6,12,8,15,22,18,12

43、,22,12,19,19,21,20,24,30,25,19,22,15,18,24,15,10,12,18,24,20,19,22,16,5,13,11,12,分析：首先要根據(jù)圖求出任意兩點(diǎn)之間的最短距離矩陣,其次：確定納稅點(diǎn)選址，與消防站點(diǎn)設(shè)置問題相似,將每一個(gè)居民點(diǎn)乘以其人數(shù)，得人數(shù)加權(quán)距離矩陣,決策變量：,y,i,第,i,個(gè)居民點(diǎn)設(shè)置為納稅點(diǎn)，,x,ij,第,j,個(gè)居民點(diǎn)的人到第,i,個(gè)納稅點(diǎn)交稅,目標(biāo)總距離最?。?w,ij,人數(shù)，,d,ij,距離,約束：設(shè)置納稅點(diǎn)3個(gè),每個(gè)居民點(diǎn)只能到一個(gè)納稅點(diǎn)交稅,每個(gè)居民點(diǎn)只能到設(shè)置了納稅點(diǎn)的地方交稅,最優(yōu)方案：,案例9：,移動(dòng)電話網(wǎng)絡(luò)設(shè)計(jì),下圖

44、是一個(gè)典型的移動(dòng)電話網(wǎng)絡(luò)的結(jié)構(gòu)圖。每個(gè)基本地理區(qū)域，也稱為一個(gè)蜂窩（cell），將由一個(gè)稱為中繼站的收發(fā)器提供服務(wù)。從一個(gè)移動(dòng)電話撥出的電話呼叫將首先通過這些中繼站。每個(gè)中繼站都通過纜線或微波連接到一個(gè)中間結(jié)點(diǎn)（樞紐，hub）。其中有一個(gè)樞紐將對(duì)此網(wǎng)絡(luò)進(jìn)行控制，此樞紐即為MTSO(移動(dòng)電話交換局)。將使用高帶寬光纖纜線在各個(gè)樞紐與MTSO之間建立十分可靠的環(huán)路連接。如果發(fā)生故障，則此環(huán)路可以自動(dòng)重建連接（自修復(fù)環(huán)路），因此不需要對(duì)其全部替換。,中繼站,蜂窩1,2 個(gè)連接,中繼站,蜂窩2,1 個(gè)連接,樞紐4,樞紐1,樞紐3,樞紐2,交換局,環(huán)路,在目前的技術(shù)條件下，中繼站和交換局之間無法進(jìn)行動(dòng)態(tài)

45、連接。在設(shè)計(jì)階段即應(yīng)固定這些連接，因此需要為每個(gè)中繼站選擇其連接到的環(huán)路結(jié)點(diǎn)。在蜂窩c和環(huán)路之間的連接數(shù)目稱為蜂窩c的多徑數(shù)，用CNCT,c,表示。為使系統(tǒng)更為可靠，多徑數(shù)應(yīng)大于1。,這種類型的系統(tǒng)中的通信是完全數(shù)字化的，通信帶寬可以表示為帶寬為64kbps（千比特每秒）的雙向回路數(shù)目。則此帶寬數(shù)值即對(duì)應(yīng)于在高峰期可并發(fā)的通信數(shù)。環(huán)路的帶寬上限為CAP。從蜂窩c發(fā)出的通信量TRAF,c,可以平均分配到蜂窩與環(huán)路之間的各個(gè)連接上，每個(gè)連接分配到的通信量為TRAF,c,/CNTC,c,。此通信量將通過環(huán)路傳輸?shù)浇粨Q局，在交換局中將把各個(gè)呼叫轉(zhuǎn)移到另一個(gè)蜂窩或移動(dòng)電話與固定電話之間的接口結(jié)點(diǎn)。由于交

46、換局具有普通樞紐的所有功能，因此中繼站也可以直接連接到交換局。,我們考慮到一個(gè)有10個(gè)蜂窩和5個(gè)結(jié)點(diǎn)組成的環(huán)路的網(wǎng)絡(luò)，此網(wǎng)絡(luò)的總帶寬為CAP=90路電話。交換局為結(jié)點(diǎn)5。下表6列出了每個(gè)蜂窩的通話量，要求連接數(shù)，以及每個(gè)連接的成本（單位為千元）。例如蜂窩1連接到結(jié)點(diǎn)1，連接成本為15,000元。蜂窩1的多徑數(shù)為2，這表示它至少應(yīng)連接到環(huán)路中的兩個(gè)結(jié)點(diǎn)上。此蜂窩的通話量為22路電話。目標(biāo)是找出蜂窩與環(huán)路之間的連接方案，以最小化總連接費(fèi)用，同時(shí)仍然能夠滿足通話量限制，并滿足連接數(shù)要求。,表,6,：每個(gè)蜂窩的連接成本，通話量，以及連接數(shù),分析：決策變量：設(shè),C,cn,表示蜂窩,c,連接到結(jié)點(diǎn),n,的

47、成本，,x,cn,表示蜂窩,c,是否連接到結(jié)點(diǎn),n,，則,目標(biāo)：連接成本最小,約束：每個(gè)蜂窩的連接數(shù)等于需要的連接數(shù),通話能力（帶寬）限制,案例10：產(chǎn)品配送問題,某公司準(zhǔn)備建K個(gè)配送中心，負(fù)責(zé)配送它的產(chǎn)品。該公司把它的所有客戶按地理位置分成n個(gè)客戶群，每個(gè)客戶群由一個(gè)配送中心向它配送產(chǎn)品?，F(xiàn)有m個(gè)備選點(diǎn)可建立配送中心(mk)。如果第i個(gè)備選點(diǎn)建配送中心，那么它的建設(shè)成本為bi，它向第j個(gè)客戶群配送產(chǎn)品的成本是cij?，F(xiàn)在該公司的問題是要從m個(gè)備選點(diǎn)中選擇K個(gè)點(diǎn)建立配送中心，使得總成本最低。請(qǐng)建立該問題的運(yùn)籌學(xué)模型。,案例11：水資源利用問題,某地區(qū)現(xiàn)有耕地可分為兩種類型，第一類耕地各種水利設(shè)

48、施配套，土地平整，排灌便利；第二類耕地則未具備以上條件。其中，第一類耕地有2.5萬畝，第二類耕地有8.2萬畝，此外尚有宜墾荒地3.5萬畝。該地區(qū)主要作物是小麥，完全靠地表水進(jìn)行灌溉。由于地表水的供應(yīng)量隨季節(jié)波動(dòng)，在小麥揚(yáng)花需水時(shí)恰值枯水季節(jié)，往往由于缺水使一部分麥田無法灌溉，影響產(chǎn)量。而由于第二類耕地高，進(jìn)一步合理利用水資源的措施有二：其一是進(jìn)行農(nóng)田建設(shè)，把一部分第二類耕地改造為第一類耕地，以節(jié)約用水，提高單產(chǎn)；其二是修建一座水庫(kù)，閑水期蓄水，到小麥揚(yáng)花需水的枯水期放水，從而調(diào)節(jié)全年不同季節(jié)的水量。目前該地區(qū)在整個(gè)小麥生長(zhǎng)期的地表水資源可利用量為96.5百萬方，其中小麥揚(yáng)花需水季節(jié)可供水量為7

49、.5百萬方，水庫(kù)建成后在小麥揚(yáng)花需水季節(jié)可供水量為6.5百萬方，修建水庫(kù)需投資5.5百萬元，將第二類耕地改為第一類耕地每畝需投資20元，將荒地開墾為第二類耕地每畝需投資85元，將荒地開墾并改造為第一類耕地每畝需投資100元，,規(guī)劃期內(nèi)，計(jì)劃總投資額為9百萬元，該地區(qū)對(duì)小麥的需求及國(guó)家征購(gòu)指標(biāo)共計(jì)2萬噸，超額向國(guó)家交售商品糧每噸可加價(jià)100元。各種條件下水的灌溉定額及收益的情況如表所示,類別,全生長(zhǎng)期澆水量（百萬方/畝）,揚(yáng)花時(shí)澆水量（百萬方/畝）,單產(chǎn)（噸/畝）,凈產(chǎn)值（百元/畝）,揚(yáng)花時(shí)澆水的第一類耕地,7.5,1.4,0.25,0.52,揚(yáng)花時(shí)不澆水的第一類耕地,6.1,0.0,0.2,0

50、.43,揚(yáng)花時(shí)澆水的第二類耕地,9.0,1.65,0.23,0.47,揚(yáng)花時(shí)不澆水的第二類耕地,7.35,0.0,0.185,0.39,現(xiàn)在需要我們論證的問題是：為了充分利用水資源，發(fā)揮最大的經(jīng)濟(jì)效益，規(guī)劃期內(nèi)應(yīng)該將多少畝第二類耕地改造為第一類耕地，應(yīng)該開墾多少畝荒地，水庫(kù)有沒有必要建？,解：,設(shè)x1為規(guī)劃年份第類耕地中小麥揚(yáng)花時(shí)可以灌溉的耕地面積（萬畝）；,設(shè)x2為規(guī)劃年份第類耕地中小麥揚(yáng)花時(shí)不能灌溉的耕地面積（萬畝）；,設(shè)x3為規(guī)劃年份第類耕地中小麥揚(yáng)花時(shí)可以灌溉的耕地面積（萬畝）；,設(shè)x4為規(guī)劃年份第類耕地中小麥揚(yáng)花時(shí)不能灌溉的耕地面積（萬畝）；,設(shè)x5為規(guī)劃年份該地區(qū)超額向國(guó)家交售的商

51、品糧數(shù)量（萬噸）；,設(shè) x1為規(guī)劃期內(nèi)由荒地直接開墾并改造為第類耕地的面積（萬畝）；,設(shè) x2為規(guī)劃期內(nèi)由荒地直接開墾為第類耕地的面積（萬畝）；,設(shè) x3為規(guī)劃期內(nèi)由第類耕地改造為第類耕地的面積（萬畝）；,1.土地資源約束,對(duì)第類耕地有:,對(duì)第類耕地有:,對(duì)宜墾荒地有:,2.水資源約束,對(duì)小麥揚(yáng)花季節(jié)有:,對(duì)整個(gè)生長(zhǎng)期有:,3.投資資金限制:,4.社會(huì)對(duì)小麥的需求約束:,y為表示規(guī)劃期內(nèi)水庫(kù)是否興建的指示變量，它的取值只能是0和1。若y=0，表示該水庫(kù)不建;y=1,表示該水庫(kù)存興建，,本模型的目標(biāo)函數(shù)應(yīng)選為規(guī)劃年份的凈收益最大.由于表中所列規(guī)劃年各種條件下的凈收益數(shù)字并未包括規(guī)劃期內(nèi)各項(xiàng)投資的

52、資本回收成本,也未包括超額交售商品糧的加價(jià)收益,所以在目標(biāo)函數(shù)中,這兩項(xiàng)尚需要單獨(dú)處理.在本模型中,我們?nèi)∧昀⒙蔵=0.06,投資回收年限n=20年,則資本回收因子CRF=0.087.在目標(biāo)函數(shù)中,相應(yīng)于各工程項(xiàng)目的資本回收成本系數(shù)即為CRF乘以各自的投資額,例如,相應(yīng)于x,2,的資本回收成本系數(shù)應(yīng)為0.0870.85=0.074.相應(yīng)于y的資本回收系數(shù)應(yīng)有為0.0875.5=0.479.另外,在目標(biāo)函數(shù)中相應(yīng)于表示超額交售商品糧的決策變量x5的系數(shù),其數(shù)值應(yīng)有取超額交售后由于價(jià)格提高而較計(jì)劃內(nèi)出售多收的那部分收益,而不是直接取它的出售價(jià)格,因?yàn)樵诟黝惛氐膬羰障禂?shù)中,已包括了這部分小麥按平常價(jià)格計(jì)算的收益,這里如再取它的出售價(jià)格作為系數(shù),就出現(xiàn)了重復(fù)計(jì)算的錯(cuò)誤.,則該問題的數(shù)學(xué)模型為：,模型的解為：x1=5.357, x2=8.843, x3=0.0, x4=0.0 x5=1.108, x1=3.5, x2=0.0, x3=8.2, y=0 maxZ=7.252,