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

《線性規(guī)劃和整數(shù)規(guī)劃.ppt》由會員分享，可在線閱讀，更多相關《線性規(guī)劃和整數(shù)規(guī)劃.ppt（93頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,第一部分：優(yōu)化模型,1、線性規(guī)劃模型（算法：單純形法） 2、整數(shù)規(guī)劃模型（算法：分枝定界法） 3、非線性規(guī)劃模型（化為線性規(guī)劃求解） 4、動態(tài)規(guī)劃模型（算法：遞歸算法） 5、多目標規(guī)劃模型（化為線性規(guī)劃求解） 一、線性規(guī)劃模型,線性規(guī)劃主要解決兩個方面的問題： （1）對于給定的一項任務，如何統(tǒng)籌安排，使以最少的資源消耗去完成？ （2）在給定的一定數(shù)量的資源條件下，如何合理安排，使完成的任務最多？,用線性規(guī)劃方法解決問題一般按下列步驟進行 第一步：建立線性規(guī)劃模型； 第二步：用單純形算法進行求解； 第三步：對求解結果進行檢驗； 第四步：將求解結果形成優(yōu)化方案，付諸實施； 線性規(guī)劃模型一般包括三

2、個要素： （1）決策變量 （2）目標函數(shù) （3）約束條件,線性規(guī)劃的一般形式為： max(或min)z=c1x1+c2x2+cnxn,（1.1),（1.2),（1.3),或矩陣形式,其中c=(c1,c2,cn)，稱為價值系數(shù)向量；,稱為技術系數(shù)矩陣(也稱消耗系數(shù)矩陣),稱為資源限制向量,X=(x1,x2,xn)T稱為決策變量向量,下面我們來看幾個實際例子。 案例1(投資計劃問題）某公司經(jīng)調研分析知，在今后三年內有四種投資機會。第種方案是在三年內每年年初投資，年底可獲利15%，并可將本金收回；第種是在第一年的年初投資，第二年的年底可獲利45%，并將本金收回，但該項投資不得超過2萬元；第種是在第二

3、年的年初投資，第三年的年底可獲利65%，并將本金收回，但該項投資不得超過1.5萬元；第種是在第三年的年初投資，年底收回本金，且可獲利35%，但該項投資不得超過1萬元?，F(xiàn)在本公司準備拿出3萬元來投資，問如何計劃可使到第三年年未本利和最大？,解：問題分析。該問題的實際投資背景如下表所示： （1）確定決策變量：設xij表示第i年對第j個方案的投資額,i=1,2,3; j=1,2,3,4,年份 一 二 三 四 x11 1.15x11 x12 1.45x12 x21 1.15x21 x23 1.65x23 x31 1.15x31 x34 1.35x34,（2）確定目標函數(shù)：第三年年未的本利和為 maxz

4、=1.65x23+1.15x31+1.35x34,（3）確定約束條件： 每一年的投資額應等于當年公司擁有的資金數(shù)： x11+x12=3 x21+x23=1.15x11 x31+x34=1.45x12+1.15x21,每個方案投資額的限制： x122 x231.5 非負約束：xij0,i=1,2,3;j=1,2,3,4 x341,案例2 債券投資問題,國家農(nóng)業(yè)銀行(National Agricultural Bank,NAB)希望為十五名要提前退休的員工制定一項提前退休計劃。這些員工將要在從明年開始的七年內逐漸退休完。為了給這個提前退休計劃籌集資金，此銀行決定在這七年期間進行債券投資。下表給出了

5、每年應向這些提早退休的員工支付的金額，這些金額必須在每年年初支付。,表：每年要求金額,此銀行計劃購買三種不同的債券，即SNCF公司（法國國營鐵路公司）的債券，F(xiàn)ujutsu（富士通）公司債券，以及國債。未投資于這些債券的資金將作為儲蓄保存，儲蓄的利率為3.2%,下表列出了各個債券的收益,時間長度,以及價格等信息.這些債券只能按整數(shù)數(shù)目進行購買,并且一旦購買之后在債券期限內即無法更改投資金額.每年只返回投資的利息.此退休計劃的負責人決定只在第一年年,初購買債券,而在此后的幾年內不再購買,應該如何分配在各個債券的投資金額才能使得只需要花費最少的資金就能夠滿足此退休計劃的要求?,表: 債券信息,分析

6、： 決策變量：初始投資y，債券購買量xi，每年的儲蓄量St,P債券價格，Dt每年資金需求，ri-債券利率,第1年,第24年,第5，6年,第7年,例題3：養(yǎng)老金管理問題,華信金融公司管理的金融產(chǎn)品中有一只很受贊譽的養(yǎng)老基金，這些養(yǎng)老基金是很多公司用來為其雇員提供養(yǎng)老金的，華信公司希望能夠進行合理的投資來保證養(yǎng)老金的供應。 現(xiàn)在是2007年的12月了，在接下去的10年中需要支付的總的養(yǎng)老金如表所示：,表： 未來十年的養(yǎng)老金需求,為了使養(yǎng)老基金的提供有安全保證，華信公司希望投資在能夠與未來10年中的養(yǎng)老金支付相匹配的項目。養(yǎng)老基金管理中心授權華信公司的投資項目只能是資本市場基金和債券。資本市場基金獲

7、得每年固定的5%的利息收入，公司所考慮投資的四只債券的特征如表3-7所示。,表： 四種債券的信息,所有的債券均可在2008年1月1日購買，可以購買任意數(shù)量單位。債券在每年的1月1日付息，支付期為購買后的第一年到到期日為止(包括到期日)。因此這些每年1月1日的利息支付獲得正好能夠用來沖抵當年養(yǎng)老金的支付，所有多余的利息收入將存入資本市場基金。為金融計劃的保守起見，華信公司假定所有的養(yǎng)老金支付在每年的年初，正好在利息收入(包括資本市場基金的利息收入)獲得之后，債券的面值也將在到期日獲得。既然當前的債券價格低于面值，真正的債權的收益比利息率要高。如債券3是一個零利息率的債券，所以每年得到的利息為0，

8、但是到到期日獲得的面值要遠大于當年債券的購得價格。 華信公司希望在2008年1月1日用最小可能的投資(包括市場基金的存款)來應付到2016年為止的所有所需的養(yǎng)老金的支付，請對此問題進行分析，并求出最優(yōu)投資方案。,例題4：定額投資問題,通用公司的董事會正在考慮幾個大型的投資項目，每個項目只能投資一次，且各項目所需要的投資金額與能夠產(chǎn)生的預期收益是不同的，如表所示：,表：投資額及預期收益,假設公司現(xiàn)有的總投資金額為1億美元，其中投資項目1和項目2是互斥的，項目3與項目4也是互斥的。此外，如果不選擇項目1或是項目2的話，就不能選擇項目3、4。投資項目5、6、7上沒有附加約束。問題的目標是通過組合各種

9、投資，使得估計的預期收益最大。,解：,例題5 （合理下料問題）要用一批長度為7.4米的園鋼做100套鋼架，每套鋼架由2.9米、2.1米、1.5米的園鋼各一根組成，問：應如何下料才能使所用的原料最??？ 解：問題分析：一根長度為7.4米的園鋼，要裁出2.9米、2.1米、1.5米的料有多種裁法，如可裁出一根2.9米、二根2.1米，也可裁出三根2.1米的。這樣我們把所有裁法列舉出來，如下表所示：,下料 方案 根數(shù) 一 二 三 四 五 六 七 八 長度米 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 合計 7.1 7.4 6.5

10、7.3 6.6 7.2 6.3 6 料頭（米） 0.3 0 0.9 0.1 0.8 0.2 1.1 1.4,（1） 確定決策變量：設xj表示按第j種方案所用的園鋼的數(shù)量 （2） 確定目標函數(shù)：問題要求所用原料最省，所用原料為： minz=x1+x2+x3+x4+x5+x6+x7+x8 （3） 確定約束條件： 2.9米園鋼的數(shù)量限制 x1+x2+x3+2x4100 2.1米園鋼的數(shù)量限制 2x1+x3+x5+2x6+3x7100 1.5米園鋼的數(shù)量限制 3x2+x3+x4+3x5+2x6+4x3100 非負限制 xj0，且為整數(shù)， j=1,2,8,建立線性規(guī)劃模型的一般步驟： （1）確定決策變量

11、； （2）確定目標函數(shù)； （3）確定約束條件。,例題6一個木材儲運公司有很大的倉庫用以儲運出售木材。由于木材季度價格的變化，該公司于每季度初購進木材，一部分于本季度內出售，一部分儲存起來以后出售。已知該公司倉庫的最大儲存量為2000萬米3，儲存費用為（70+100u）千元/萬米3，u為存儲時間（季度數(shù)）。已知每季度的買進賣出價及預計的銷售量如下表所示。,由于木材不宜久貯，所有庫存木材應于每年秋末售完。為使售后利潤最大，試建立這個問題的線性規(guī)劃模型。,設yi分別表示冬、春、夏、秋四個季度采購的木材數(shù)，xij代表第i季度采購的用于第j季度銷售的木材數(shù)。,例題7 自行車生產(chǎn)規(guī)劃問題,有一家公司生產(chǎn)兒

12、童自行車。在下表中給出了明年預期的銷售量（以千輛為單位計）。此公司的生產(chǎn)能力為每個月30000輛自行車。通過工人加班，可以將產(chǎn)量提高50%，但會將每輛自行車的生產(chǎn)成本從30歐元提高到40歐元。,表： 明年的銷售預期（千輛）,當前自行車的庫存量為2000輛，對于庫存中的每輛自行車，在每個月月底都需要支出5歐元的存儲費用。我們假定此公司的庫存能力是無限的。現(xiàn)在是一月一日，在下面的十二個月里面每個月應生產(chǎn)和存儲多少輛自行車才能滿足此銷售預期，并最小化總成本？,分析： 決策變量：設t時間內的正常工作時間內和加班時間內生產(chǎn)的自行車數(shù)量分別為xt，yt ,每個月月底時庫存的自行車數(shù)量為St,目標：生產(chǎn)成本

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

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

15、條生產(chǎn)線，每輛貨車都可以選擇在哪條生產(chǎn)線上進行加工。一車甘蔗的加工時間為兩個小時。必須在這車甘蔗的質量壽命結束之前完成加工。制糖廠的經(jīng)理希望找出一個生產(chǎn)計劃，使總的蔗糖損失降到最低。,表 每車甘蔗屬性,解：,例題10：石油精煉問題,石油精煉廠將使用兩種原油生產(chǎn)出丁烷(butane)，汽油(petrol)，柴油(dieseloil)，以及民用燃料油(heating oil)。為生產(chǎn)出這些產(chǎn)品，需要四道工序：分離、轉化、提純、混合。 在分離工序中將把原材料進行分餾，使其分離為丁烷(butane)、石腦油(naphtha)、輕柴油(gasoil)、以及殘渣。殘渣然后將進行催化裂解以獲得較輕的產(chǎn)品。從

16、分餾工序得到的各種產(chǎn)品將進行提純(脫硫)，或通過重整工藝增加其辛烷值。最終，為獲得可以出售的最終產(chǎn)品，精煉廠需要將若干種中間產(chǎn)物進行混合，以滿足商業(yè)產(chǎn)品所要求的各種屬性。下圖中是對此精煉廠的生產(chǎn)過程的簡單的示意圖。,石油精煉流程圖,在分餾之后，原油1能夠得到3%的丁烷，15%的石腦油，40%的輕柴油，以及15%的殘渣。原油2能夠得到5%的丁烷，20%的石腦油，25%的輕柴油，以及10%的殘渣。對石腦油進行重整能夠得到5%的丁烷和85%的重整油(重整石腦油)。對殘渣的催化裂解可以生成45%的裂解石腦油和35%的裂解輕柴油(注意，由于在此工藝中也將生成15%的氣體和5%的石油焦以及其他另一種無法計

17、入我們的問題中的殘余物，因此這兩個百分比之和不等于1)。汽油由三種成分混合而成：重組石腦油(重組油)，丁烷，以及裂解石腦油。柴油可以通過將脫硫輕柴油，裂解輕柴油，以及裂解石腦油混合得到。民用燃料油由輕柴油及裂解石腦油組成，對其成分含量沒有要求。,法律規(guī)定了一些汽油和柴油的規(guī)格指標。對于汽油有三項重要指標：辛烷值，蒸汽壓，以及揮發(fā)性。辛烷值是對汽油的抗爆能力的度量。蒸汽壓能夠反映出汽油儲存過程中發(fā)生爆炸的風險，尤其在炎熱氣候條件下。揮發(fā)性能夠決定在寒冷氣候條件下發(fā)動機是否能夠容易啟動?？諝馕廴痉ㄒ?guī)對柴油的含硫量進行了規(guī)定。表2-19中列出了最終產(chǎn)品的規(guī)格指標和中間產(chǎn)品的成分組成。如果對某一項沒有

18、限制，則對應在域保留為空。我們假定所有這些成分都將按照質量線性混合(實際上只有含硫量才如此)。,表 中間產(chǎn)物和最終產(chǎn)品規(guī)格屬性,下個月此精煉廠需要生產(chǎn)20,000噸丁烷，40,000噸汽油，30,000噸柴油，42,000噸燃料油。可用原油分別為250,000噸原油1，300,000噸原油2。重整爐每月加工能力為70,000噸，脫硫工藝每月加工能力為80,000噸，裂解工藝每月加工能力為40,000噸。各個工藝的成本取決于其中使用的燃料和催化劑。整流，重整，脫硫，和裂解的成本分別為每噸2.10，4.18，2.04，0.60歐元。,解：此案例的特點是信息多而且雜。首先進行適當?shù)男畔⒄?，列為?

19、和表2。,表1 原油分餾可得到的產(chǎn)品及可用量,表2 各工序加工能力和單位加工成本,案例11、有一艘貨輪，分前、中、后三個艙位，它們的容積與最大允許載重量如表1所示?，F(xiàn)有三種貨物待運，已知有關數(shù)據(jù)列于表2。為了航運安全，要求前、中、后艙在實際載重量上大體保持各艙最大允許載重量的比例關系，具體要求前、后艙分別與中艙之間載重量比例上偏差不超過15%，前、后艙之間不超過10%。問該貨輪應裝載A，B，C各多少件，運費收入為最大？試建立這個問題的線性規(guī)劃模型。,表1,設表示xij裝于第j(j=1,2,3)艙位的第i(i=1,2,3)種商品的數(shù)量,艙位載重限制,艙位體積限制,商品數(shù)量限制,平衡條件,案例12

20、 . (倉庫租用問題)捷運公司擬在下一年度的1-4月的4個月內需租用倉庫堆放物資.已知各月份所需倉庫面積數(shù)列于表1.倉庫租借費用隨合同期而定,期限越長,折扣越大,具體數(shù)字見表2.租借倉庫的合同每月初都可辦理,每份合同具體規(guī)定租用面積數(shù)和期限.因此該廠可根據(jù)需要,在任何一個月初辦理租借合同.每次辦理時可簽一份,也可簽若干份租用面積和租借期限不同的合同,試確定該公司簽訂租借合同的最優(yōu)決策,目的是使所付租借費用最小.,表1,表2,解:1)設決策變量xij表示捷運公司在第i(I=1,2,3,4)個月初簽訂的租借期為j(j=1,2,3,4)個月的倉庫面積的合同(單位為100m2).因5月份起該公司不需要

21、租借倉庫,故x24,x33,x34,x42,x43,x44均為零,2)目標函數(shù):使總的租借費用最小,3)約束條件:每個月份所需倉庫面積的限制,二、 整數(shù)規(guī)劃模型,案例1 某單位有5個擬選擇的投資項目，其所需投資額與期望收益如下表。由于各項目之間有一定聯(lián)系，A、C、E之間必須選擇一項且僅需選擇一項；B和D之間需選擇也僅需選擇一項；又由于C和D兩項目密切相關，C的實施必須以D的實施為前提條件，該單位共籌集資金15萬元，問應該選擇哪些項目投資，使期望收益最大？,解：決策變量：設,目標函數(shù)：期望收益最大,約束條件：投資額限制條件 6x1+4x2+2x3+4x4+5x515,項目A、C、E之間必須且只需

22、選擇一項：x1+x3+x5=1,項目C的實施要以項目D的實施為前提條件： x3 x4,項目B、D之間必須且只需選擇一項：x2+x4=1,歸納起來，其數(shù)學模型為：,案例2 某服務部門各時段（每2小時為一時段）需要的服務員人數(shù)如下表，按規(guī)定，服務員連續(xù)工作8小時（即四個時段）為一班，現(xiàn)要求安排服務員的工作時間，使服務部門服務員總數(shù)最小。,解：設在第j時段開始時上班的服務員人數(shù)為xj，由于第j時段開始時上班的服務員將在第(j+3)時段結束時下班，故決策變量只需考慮x1,x2,x3,x4,x5，此問題的數(shù)學模型為：,案例3：護士工作時間調度問題,Mr.Schedule 先生受人之托要為 St.Jose

23、ph醫(yī)院的心腦血管部門制定護士的工作時間表。在心腦血管部門中一個工作日分為12個兩小時長的時段，每個時段的人員要求都不同。例如，在夜間只要求有很少的幾個護士就足夠了，但是在早晨為了給病人提供特殊服務，需要很多護士。下表列出了每個時段的人員需求量。,問題1：請計算出為滿足需求最少需要多少護士，假定已知護士每天工作8小時，且在工作四小時后需要休息兩小時。,問題2：此部門目前只有80名護士，這個數(shù)目不足以滿足給定的需求。因此Schedule先生建議每天安排部分人加班。每天加班時間為2小時，且緊隨在后一個四小時工作時段之后，中間沒有休息。請給出護士工作時間安排方案，以使需要加班的護士數(shù)目最少。,分析：

24、設xt為時段t開始工作的護士數(shù)目,問題1模型,最優(yōu)方案,由此我們看到，第1問題求出的最優(yōu)解為至少需要100名護士，然而目前只有80名，這就需要安排一部分人加班。 設變量yt表示t時段開始工作并且需要加班2小時的護士人數(shù),問題需要求的是滿足服務需要，最小需要加班的人數(shù)，因此模型變?yōu)椋?t時段加班人數(shù)小于開始工作人數(shù),總人數(shù)限制,各時段需求人數(shù)限制,最優(yōu)方案如下表，表中列示了各時段開始工作的人數(shù)及保時段需要加班的人數(shù)，最少需要加班人數(shù)為40人。,案例4 （固定費用問題）有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費用售價、資源單件耗量及組成三種產(chǎn)品生產(chǎn)的固定費用見下表。要求制定一個生產(chǎn)計劃，

25、使總收益最大。,解：總收益等于銷售收入減去生產(chǎn)上述產(chǎn)品的固定費用和可變費用之和。建模碰到的困難主要是事先不能確切知道某種產(chǎn)品是否生產(chǎn)，因而不能確定相應的固定費用是否發(fā)生。下面借助0-1變量解決這個困難,設xj是第j種產(chǎn)品的產(chǎn)量，j=1,2,3,再設,則問題的整數(shù)規(guī)劃模型為：,M為很大的正數(shù),案例5 （工件排序問題）用4臺機床加工3件產(chǎn)品。各產(chǎn)品的機床加工順序，以及產(chǎn)品i在機床j上的加工工時aij如下表。由于某種原因，產(chǎn)品2的加工總時間不得超過d，現(xiàn)要求確定各件產(chǎn)品在機床上的加工方案，使在最短的時間內加工完全部產(chǎn)品。,解：設xij表示產(chǎn)品i在機床j上開始加工的時間(i=1,2,3;j=1,2,3

26、,4) 下面將逐步列出問題的整數(shù)規(guī)劃模型 1、同一件產(chǎn)品在不同機床上的加工順序約束 對于同一件產(chǎn)品，在下一臺機床上加工的開始時間不得早于在上一臺機床上加工的約束時間，故應有：,產(chǎn)品3：,2、每一臺機床對不同產(chǎn)品的加工順序約束 一臺機床在工作中，如已開始的加工還沒有結束，則不能開始另一件產(chǎn)品的加工。對于機床1，有兩種加工順序。或先加工產(chǎn)品1，后加工產(chǎn)品2；或反之。對于其它3臺機床，情況也類似。為了容納兩種相互排斥的約束條件，對于每臺機床，分別引入0-1變量,各yj的意義是明顯的。如當yj=0時，表示機床1先加工產(chǎn)品1，后加工產(chǎn)品2，當yj=1時，表示機床1先加工產(chǎn)品2，后加工產(chǎn)品1。,那么，每臺

27、機床上的加工產(chǎn)品的順序可用下列四組約束條件來保證,3、產(chǎn)品2的加工時間約束 產(chǎn)品2的開始加工時間是x21，結束加工時間是x24+a24，故應有：,4、目標函數(shù)的建立 設全部產(chǎn)品加工完畢的結束時間為W，由于三件產(chǎn)品的加工結束時間分別為x14+a14， x24+a24， x33+a33，故全部產(chǎn)品的實際加工結束時間為：,轉化為線性表達式：,0-1規(guī)劃特別適合用在選址問題中,某個公司準備投資一項大型的房地產(chǎn)開發(fā)項目，該項目是建造一個占地數(shù)平方英里的住宅小區(qū)。由于地球變暖的趨勢越來越嚴重，小區(qū)如何預防火災變得越來越重要。因此，公司需要解決的一個重要問題之一是如何布置兩個消防站。為便于規(guī)劃，整個小區(qū)分為

28、5個區(qū)域，每個區(qū)域最多只能設一個消防站。每個消防站必須負責處理所處區(qū)域以及分配給該站的其他區(qū)域發(fā)生的火災。這樣，要作出的決策就包括：（1）消防站設在哪個區(qū)域？（2）將其他區(qū)域分配給某一個消防站。問題的目標是發(fā)生火災之后平均的反應時間最短。 下表給出的是將消防站建在各區(qū)域（行）的情況下，每個區(qū)域對火災反應的平均時間，表中最后一行給出是各區(qū)域每天估計會發(fā)生火災的平均次數(shù)。,案例6：消防站位置設置問題,問題：（1）消防站設在哪個區(qū)域？（2）將其他區(qū)域分配給某一個消防站。目標是發(fā)生火災之后平均的反應時間最短。 下表給出的是將消防站建在各區(qū)域（行）的情況下，每個區(qū)域對火災反應的平均時間，表中最后一行給出

29、是各區(qū)域每天估計會發(fā)生火災的平均次數(shù)。,有一家大公司希望開設一些新的倉庫，以向銷售中心供貨。每開設一個新倉庫都有一些固定費用。貨物將從倉庫運輸?shù)礁浇匿N售中心。每次運輸?shù)倪\費取決于運輸?shù)木嚯x。這兩種類型的費用非常不同：倉庫開設費用屬于投資支出，通常在若干年后將勾銷，而運輸費用屬于運營成本。我們假定這兩種費用可比，為此可能需要以年為單位計算運營費用。 有12個可以建造新倉庫的位置，并且需要從這些倉庫向12個銷售中心供貨。下表給出了每個倉庫完全滿足每個客戶（銷售中心）需求所需的總成本（千歐元，不是單位成本）。因此，例如從倉庫1向客戶9（根據(jù)表3可以看到此客戶總需求量為30噸）供貨的單位成本為600

30、00歐元/30噸，即2000歐元/噸。 如果無法進行送貨，則對應的成本標記為無窮大。,倉庫位置設置問題,案例7：,表格1：滿足客戶需求所需的運輸成本,此外，對每個倉庫，還有如下信息：倉庫建設的固定費用（需要計入目標函數(shù)）和倉庫的容量上限，這些信息都列于表2中。,表格2：倉庫建設費用和容量限制,表3列出了各個銷售中心（客戶）的需求量,任何時候都要保證滿足客戶需求，可以從多個倉庫向同一個客戶送貨。應在哪些位置開辦倉庫才能使總的建設成本以及運輸成本最低，同時仍然能夠滿足所有客戶需求？,分析 決策變量：12個倉庫中需要決策選擇哪些倉庫， 每個被選中的倉庫運輸給每個客戶的運輸量xij 目標：總成本=建設

31、成本+運輸成本 約束：倉庫容量上限約束 客戶需求量約束 只有當某一位置建設了倉庫才能向客戶運輸產(chǎn)品,數(shù)據(jù)處理,最優(yōu)方案,更深入的問題：一個客戶只允許由一個倉庫共貨，但一個倉庫可供多個客戶。,案例8：所得稅交納點選址問題,所得稅管理部門計劃對某個地區(qū)的所得稅交納點網(wǎng)絡進行重新設計。下圖是對此地區(qū)內的城市和主要道路的示意圖。城市這邊的黑體數(shù)字表示城市的居民數(shù)目，單位為千人。在連接城市之間的弧上標出了它們之間的距離，單位為千米。為覆蓋各城市，所得稅管理部門決定在三個城市中設置納稅點。應在哪三個城市中設置納稅點才能使居民與最近的納稅點之間平均距離最小？,分析：首先要根據(jù)圖求出任意兩點之間的最短距離矩陣

32、,其次：確定納稅點選址，與消防站點設置問題相似,將每一個居民點乘以其人數(shù)，得人數(shù)加權距離矩陣,決策變量：yi第i個居民點設置為納稅點，xij第 j個居民點的人到第i個納稅點交稅,目標總距離最小：,wij人數(shù)，dij距離,約束：設置納稅點3個,每個居民點只能到一個納稅點交稅,每個居民點只能到設置了納稅點的地方交稅,最優(yōu)方案：,案例9：移動電話網(wǎng)絡設計,下圖是一個典型的移動電話網(wǎng)絡的結構圖。每個基本地理區(qū)域，也稱為一個蜂窩（cell），將由一個稱為中繼站的收發(fā)器提供服務。從一個移動電話撥出的電話呼叫將首先通過這些中繼站。每個中繼站都通過纜線或微波連接到一個中間結點（樞紐，hub）。其中有一個樞紐將

33、對此網(wǎng)絡進行控制，此樞紐即為MTSO(移動電話交換局)。將使用高帶寬光纖纜線在各個樞紐與MTSO之間建立十分可靠的環(huán)路連接。如果發(fā)生故障，則此環(huán)路可以自動重建連接（自修復環(huán)路），因此不需要對其全部替換。,中繼站,蜂窩1 2 個連接,中繼站,蜂窩2 1 個連接,樞紐4,樞紐1,樞紐3,樞紐2,交換局,環(huán)路,在目前的技術條件下，中繼站和交換局之間無法進行動態(tài)連接。在設計階段即應固定這些連接，因此需要為每個中繼站選擇其連接到的環(huán)路結點。在蜂窩c和環(huán)路之間的連接數(shù)目稱為蜂窩c的多徑數(shù)，用CNCTc表示。為使系統(tǒng)更為可靠，多徑數(shù)應大于1。 這種類型的系統(tǒng)中的通信是完全數(shù)字化的，通信帶寬可以表示為帶寬為6

34、4kbps（千比特每秒）的雙向回路數(shù)目。則此帶寬數(shù)值即對應于在高峰期可并發(fā)的通信數(shù)。環(huán)路的帶寬上限為CAP。從蜂窩c發(fā)出的通信量TRAFc可以平均分配到蜂窩與環(huán)路之間的各個連接上，每個連接分配到的通信量為TRAFc/CNTCc。此通信量將通過環(huán)路傳輸?shù)浇粨Q局，在交換局中將把各個呼叫轉移到另一個蜂窩或移動電話與固定電話之間的接口結點。由于交換局具有普通樞紐的所有功能，因此中繼站也可以直接連接到交換局。,我們考慮到一個有10個蜂窩和5個結點組成的環(huán)路的網(wǎng)絡，此網(wǎng)絡的總帶寬為CAP=90路電話。交換局為結點5。下表6列出了每個蜂窩的通話量，要求連接數(shù)，以及每個連接的成本（單位為千元）。例如蜂窩1連接

35、到結點1，連接成本為15,000元。蜂窩1的多徑數(shù)為2，這表示它至少應連接到環(huán)路中的兩個結點上。此蜂窩的通話量為22路電話。目標是找出蜂窩與環(huán)路之間的連接方案，以最小化總連接費用，同時仍然能夠滿足通話量限制，并滿足連接數(shù)要求。,表6：每個蜂窩的連接成本，通話量，以及連接數(shù),分析：決策變量：設Ccn表示蜂窩c連接到結點n的成本，xcn表示蜂窩c是否連接到結點n，則,目標：連接成本最小,約束：每個蜂窩的連接數(shù)等于需要的連接數(shù),通話能力（帶寬）限制,案例10：產(chǎn)品配送問題,某公司準備建K個配送中心，負責配送它的產(chǎn)品。該公司把它的所有客戶按地理位置分成n個客戶群，每個客戶群由一個配送中心向它配送產(chǎn)品。

36、現(xiàn)有m個備選點可建立配送中心(mk)。如果第i個備選點建配送中心，那么它的建設成本為bi，它向第j個客戶群配送產(chǎn)品的成本是cij?，F(xiàn)在該公司的問題是要從m個備選點中選擇K個點建立配送中心，使得總成本最低。請建立該問題的運籌學模型。,案例11：水資源利用問題,某地區(qū)現(xiàn)有耕地可分為兩種類型，第一類耕地各種水利設施配套，土地平整，排灌便利；第二類耕地則未具備以上條件。其中，第一類耕地有2.5萬畝，第二類耕地有8.2萬畝，此外尚有宜墾荒地3.5萬畝。該地區(qū)主要作物是小麥，完全靠地表水進行灌溉。由于地表水的供應量隨季節(jié)波動，在小麥揚花需水時恰值枯水季節(jié)，往往由于缺水使一部分麥田無法灌溉，影響產(chǎn)量。而由于

37、第二類耕地高，進一步合理利用水資源的措施有二：其一是進行農(nóng)田建設，把一部分第二類耕地改造為第一類耕地，以節(jié)約用水，提高單產(chǎn)；其二是修建一座水庫，閑水期蓄水，到小麥揚花需水的枯水期放水，從而調節(jié)全年不同季節(jié)的水量。目前該地區(qū)在整個小麥生長期的地表水資源可利用量為96.5百萬方，其中小麥揚花需水季節(jié)可供水量為7.5百萬方，水庫建成后在小麥揚花需水季節(jié)可供水量為6.5百萬方，修建水庫需投資5.5百萬元，將第二類耕地改為第一類耕地每畝需投資20元，將荒地開墾為第二類耕地每畝需投資85元，將荒地開墾并改造為第一類耕地每畝需投資100元，,規(guī)劃期內，計劃總投資額為9百萬元，該地區(qū)對小麥的需求及國家征購指標

38、共計2萬噸，超額向國家交售商品糧每噸可加價100元。各種條件下水的灌溉定額及收益的情況如表所示,現(xiàn)在需要我們論證的問題是：為了充分利用水資源，發(fā)揮最大的經(jīng)濟效益，規(guī)劃期內應該將多少畝第二類耕地改造為第一類耕地，應該開墾多少畝荒地，水庫有沒有必要建？,解：設x1為規(guī)劃年份第類耕地中小麥揚花時可以灌溉的耕地面積（萬畝）； 設x2為規(guī)劃年份第類耕地中小麥揚花時不能灌溉的耕地面積（萬畝）； 設x3為規(guī)劃年份第類耕地中小麥揚花時可以灌溉的耕地面積（萬畝）； 設x4為規(guī)劃年份第類耕地中小麥揚花時不能灌溉的耕地面積（萬畝）； 設x5為規(guī)劃年份該地區(qū)超額向國家交售的商品糧數(shù)量（萬噸）； 設 x1為規(guī)劃期內由荒

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

40、收益,所以在目標函數(shù)中,這兩項尚需要單獨處理.在本模型中,我們取年利息率i=0.06,投資回收年限n=20年,則資本回收因子CRF=0.087.在目標函數(shù)中,相應于各工程項目的資本回收成本系數(shù)即為CRF乘以各自的投資額,例如,相應于x2的資本回收成本系數(shù)應為0.0870.85=0.074.相應于y的資本回收系數(shù)應有為0.0875.5=0.479.另外,在目標函數(shù)中相應于表示超額交售商品糧的決策變量x5的系數(shù),其數(shù)值應有取超額交售后由于價格提高而較計劃內出售多收的那部分收益,而不是直接取它的出售價格,因為在各類耕地的凈收系數(shù)中,已包括了這部分小麥按平常價格計算的收益,這里如再取它的出售價格作為系數(shù),就出現(xiàn)了重復計算的錯誤.,則該問題的數(shù)學模型為：,模型的解為：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,