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

第一部分：優(yōu)化模型1、線性規(guī)劃模型（算法：?jiǎn)渭冃畏ǎ?、整數(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ì)求解結(jié)果進(jìn)行檢驗(yàn)；第四步：將求解結(jié)果形成優(yōu)化方案，付諸實(shí)施；線性規(guī)劃模型一般包括三個(gè)要素：（1）決策變量（2）目標(biāo)函數(shù)（3）約束條件線性規(guī)劃的一般形式為：

max(或min)z=c1x1+c2x2+…+cnxn

（1.1)（1.2)（1.3)或矩陣形式其中c=(c1,c2,…,cn)，稱為價(jià)值系數(shù)向量；稱為技術(shù)系數(shù)矩陣(也稱消耗系數(shù)矩陣)

稱為資源限制向量,

X=(x1,x2,…,xn)T稱為決策變量向量下面我們來看幾個(gè)實(shí)際例子。案例1(投資計(jì)劃問題）某公司經(jīng)調(diào)研分析知，在今后三年內(nèi)有四種投資機(jī)會(huì)。第Ⅰ種方案是在三年內(nèi)每年年初投資，年底可獲利15%，并可將本金收回；第Ⅱ種是在第一年的年初投資，第二年的年底可獲利45%，并將本金收回，但該項(xiàng)投資不得超過2萬元；第Ⅲ種是在第二年的年初投資，第三年的年底可獲利65%，并將本金收回，但該項(xiàng)投資不得超過1.5萬元；第Ⅳ種是在第三年的年初投資，年底收回本金，且可獲利35%，但該項(xiàng)投資不得超過1萬元?，F(xiàn)在本公司準(zhǔn)備拿出3萬元來投資，問如何計(jì)劃可使到第三年年未本利和最大？

解：?jiǎn)栴}分析。該問題的實(shí)際投資背景如下表所示：（1）確定決策變量：設(shè)xij表示第i年對(duì)第j個(gè)方案的投資額,i=1,2,3;j=1,2,3,4年份一二三四x111.15x11x121.45x12

x211.15x21

x231.65x23

x311.15x31

x341.35x34（2）確定目標(biāo)函數(shù)：第三年年未的本利和為maxz=1.65x23+1.15x31+1.35x34

（3）確定約束條件：每一年的投資額應(yīng)等于當(dāng)年公司擁有的資金數(shù)：x11+x12=3x21+x23=1.15x11x31+x34=1.45x12+1.15x21

每個(gè)方案投資額的限制：x12≤2x23≤1.5非負(fù)約束：xij≥0,i=1,2,3;j=1,2,3,4x34≤1案例2

債券投資問題國(guó)家農(nóng)業(yè)銀行(NationalAgriculturalBank,NAB)希望為十五名要提前退休的員工制定一項(xiàng)提前退休計(jì)劃。這些員工將要在從明年開始的七年內(nèi)逐漸退休完。為了給這個(gè)提前退休計(jì)劃籌集資金，此銀行決定在這七年期間進(jìn)行債券投資。下表給出了每年應(yīng)向這些提早退休的員工支付的金額，這些金額必須在每年年初支付。年1234567金額（千歐元）10006006404807601020950表：每年要求金額此銀行計(jì)劃購買三種不同的債券，即SNCF公司（法國(guó)國(guó)營(yíng)鐵路公司）的債券，F(xiàn)ujutsu（富士通）公司債券，以及國(guó)債。未投資于這些債券的資金將作為儲(chǔ)蓄保存，儲(chǔ)蓄的利率為3.2%,下表列出了各個(gè)債券的收益,時(shí)間長(zhǎng)度,以及價(jià)格等信息.這些債券只能按整數(shù)數(shù)目進(jìn)行購買,并且一旦購買之后在債券期限內(nèi)即無法更改投資金額.每年只返回投資的利息.此退休計(jì)劃的負(fù)責(zé)人決定只在第一年年初購買債券,而在此后的幾年內(nèi)不再購買,應(yīng)該如何分配在各個(gè)債券的投資金額才能使得只需要花費(fèi)最少的資金就能夠滿足此退休計(jì)劃的要求?債券價(jià)值(千歐元)利率期限SNCFFujitsu國(guó)債1.00.80.57.0%7.0%6.5%5年4年6年表:債券信息分析：決策變量：初始投資y，債券購買量xi，每年的儲(chǔ)蓄量StP—債券價(jià)格，Dt—每年資金需求，ri---債券利率第1年第2…4年第5，6年第7年例題3：養(yǎng)老金管理問題華信金融公司管理的金融產(chǎn)品中有一只很受贊譽(yù)的養(yǎng)老基金，這些養(yǎng)老基金是很多公司用來為其雇員提供養(yǎng)老金的，華信公司希望能夠進(jìn)行合理的投資來保證養(yǎng)老金的供應(yīng)?，F(xiàn)在是2007年的12月了，在接下去的10年中需要支付的總的養(yǎng)老金如表所示：表：未來十年的養(yǎng)老金需求年份需要支付的養(yǎng)老金（萬美元）2008800200912002010130020111400201216002013170020142000201521002015220020162400為了使養(yǎng)老基金的提供有安全保證，華信公司希望投資在能夠與未來10年中的養(yǎng)老金支付相匹配的項(xiàng)目。養(yǎng)老基金管理中心授權(quán)華信公司的投資項(xiàng)目只能是資本市場(chǎng)基金和債券。資本市場(chǎng)基金獲得每年固定的5%的利息收入，公司所考慮投資的四只債券的特征如表3-7所示。表：四種債券的信息債券當(dāng)前價(jià)格（美元）年利息率到期日面值（美元）債券19804%2009.1.11000債券29202%2011.1.11000債券37500%2013.1.11000債券48003%2016.1.11000所有的債券均可在2008年1月1日購買，可以購買任意數(shù)量單位。債券在每年的1月1日付息，支付期為購買后的第一年到到期日為止(包括到期日)。因此這些每年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)年債券的購得價(jià)格。華信公司希望在2008年1月1日用最小可能的投資(包括市場(chǎng)基金的存款)來應(yīng)付到2016年為止的所有所需的養(yǎng)老金的支付，請(qǐng)對(duì)此問題進(jìn)行分析，并求出最優(yōu)投資方案。例題4：定額投資問題通用公司的董事會(huì)正在考慮幾個(gè)大型的投資項(xiàng)目，每個(gè)項(xiàng)目只能投資一次，且各項(xiàng)目所需要的投資金額與能夠產(chǎn)生的預(yù)期收益是不同的，如表所示：表：投資額及預(yù)期收益

投資項(xiàng)目預(yù)期收益（百萬美元）所需資金（百萬美元）117432102831534419485717613327923假設(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（合理下料問題）要用一批長(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.9111200002.1201012301.503113204合計(jì)7.17.46.57.36.67.26.36料頭（米）0.300.90.10.80.21.11.4（1）

確定決策變量：設(shè)xj表示按第j種方案所用的園鋼的數(shù)量（2）

確定目標(biāo)函數(shù)：?jiǎn)栴}要求所用原料最省，所用原料為：minz=x1+x2+x3+x4+x5+x6+x7+x8（3）

確定約束條件：2.9米園鋼的數(shù)量限制x1+x2+x3+2x4≥1002.1米園鋼的數(shù)量限制2x1+x3+x5+2x6+3x7≥1001.5米園鋼的數(shù)量限制3x2+x3+x4+3x5+2x6+4x3≥100非負(fù)限制xj≥0，且為整數(shù)，j=1,2,…,8建立線性規(guī)劃模型的一般步驟：（1）確定決策變量；（2）確定目標(biāo)函數(shù)；（3）確定約束條件。例題6．一個(gè)木材儲(chǔ)運(yùn)公司有很大的倉庫用以儲(chǔ)運(yùn)出售木材。由于木材季度價(jià)格的變化，該公司于每季度初購進(jìn)木材，一部分于本季度內(nèi)出售，一部分儲(chǔ)存起來以后出售。已知該公司倉庫的最大儲(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）冬4104251000春4304401400夏4604652000秋4504551600由于木材不宜久貯，所有庫存木材應(yīng)于每年秋末售完。為使售后利潤(rùn)最大，試建立這個(gè)問題的線性規(guī)劃模型。

設(shè)yi分別表示冬、春、夏、秋四個(gè)季度采購的木材數(shù)，xij代表第i季度采購的用于第j季度銷售的木材數(shù)。季度買進(jìn)價(jià)（萬元/萬米3）賣出價(jià)（萬元/萬米3）預(yù)計(jì)銷售量（萬米3）冬4104251000春4304401400夏4604652000秋4504551600例題7

自行車生產(chǎn)規(guī)劃問題有一家公司生產(chǎn)兒童自行車。在下表中給出了明年預(yù)期的銷售量（以千輛為單位計(jì)）。此公司的生產(chǎn)能力為每個(gè)月30000輛自行車。通過工人加班，可以將產(chǎn)量提高50%，但會(huì)將每輛自行車的生產(chǎn)成本從30歐元提高到40歐元。表：明年的銷售預(yù)期（千輛）1月2月3月4月5月6月7月8月9月10月11月12月301515253340454526142530當(dāng)前自行車的庫存量為2000輛，對(duì)于庫存中的每輛自行車，在每個(gè)月月底都需要支出5歐元的存儲(chǔ)費(fèi)用。我們假定此公司的庫存能力是無限的?，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ù)量分別為xt，yt,每個(gè)月月底時(shí)庫存的自行車數(shù)量為St目標(biāo)：生產(chǎn)成本與庫存成本和最小約束：第一個(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)，限制主要是各工廠規(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)的蔗糖取決于甘蔗收購的地點(diǎn)以及甘蔗成熟的程度。在收割之后，甘蔗中的含糖量將由于發(fā)酵而迅速下降，在一段時(shí)間之后，所含糖份將完全流失。現(xiàn)在有11輛貨車到達(dá)了蔗糖廠，每輛貨車運(yùn)載的甘蔗量都相同。已經(jīng)對(duì)每輛貨車每小時(shí)的損失量以及剩余時(shí)間進(jìn)行了測(cè)算，具體數(shù)據(jù)如表所示。表每車甘蔗屬性貨車編號(hào)1234567891011損失率（千克/小時(shí)）4326372813546249192830剩余時(shí)間88284888888在制糖廠內(nèi)有三條生產(chǎn)線，每輛貨車都可以選擇在哪條生產(chǎn)線上進(jìn)行加工。一車甘蔗的加工時(shí)間為兩個(gè)小時(shí)。必須在這車甘蔗的質(zhì)量壽命結(jié)束之前完成加工。制糖廠的經(jīng)理希望找出一個(gè)生產(chǎn)計(jì)劃，使總的蔗糖損失降到最低。貨車編號(hào)1234567891011損失率（千克/小時(shí)）4326372813546249192830剩余時(shí)間88284888888表每車甘蔗屬性解：例題10：石油精煉問題

石油精煉廠將使用兩種原油生產(chǎn)出丁烷(butane)，汽油(petrol)，柴油(dieseloil)，以及民用燃料油(heatingoil)。為生產(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)品所要求的各種屬性。下圖中是對(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)。汽油由三種成分混合而成：重組石腦油(重組油)，丁烷，以及裂解石腦油。柴油可以通過將脫硫輕柴油，裂解輕柴油，以及裂解石腦油混合得到。民用燃料油由輕柴油及裂解石腦油組成，對(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ī)格丁烷重整油裂解石腦油裂解輕柴油去硫輕柴油汽油柴油辛烷值12010074——>=94—蒸氣壓602.64.1——<=12.7—揮發(fā)性105312——>=17—含硫量（%）——0.120.760.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)是信息多而且雜。首先進(jìn)行適當(dāng)?shù)男畔⒄恚袨楸?和表2。

表1原油分餾可得到的產(chǎn)品及可用量

丁烷石腦油輕柴油殘?jiān)捎昧吭?3%15%40%15%250,000原油25%20%25%10%300,000表2各工序加工能力和單位加工成本工序單位成本（歐元/噸）加工能力（噸）整流2.10—重整4.1870000脫流2.0480000裂解0.6040000案例11、有一艘貨輪，分前、中、后三個(gè)艙位，它們的容積與最大允許載重量如表1所示?，F(xiàn)有三種貨物待運(yùn)，已知有關(guān)數(shù)據(jù)列于表2。為了航運(yùn)安全，要求前、中、后艙在實(shí)際載重量上大體保持各艙最大允許載重量的比例關(guān)系，具體要求前、后艙分別與中艙之間載重量比例上偏差不超過15%，前、后艙之間不超過10%。問該貨輪應(yīng)裝載A，B，C各多少件，運(yùn)費(fèi)收入為最大？試建立這個(gè)問題的線性規(guī)劃模型。

前艙中艙后艙最大允許載重量（噸）200030001500容積（立方米）400054001500表1商品數(shù)量（件）每件體積（立方米/件）每件重量（噸/件）運(yùn)價(jià)（元/件）A6001081000B100056700C80075600設(shè)表示xij裝于第j(j=1,2,3)艙位的第i(i=1,2,3)種商品的數(shù)量艙位載重限制艙位體積限制商品數(shù)量限制平衡條件前艙中艙后艙重量200030001500容積400054001500商品數(shù)量體積重量運(yùn)價(jià)A6001081000B100056700C80075600案例12.(倉庫租用問題)捷運(yùn)公司擬在下一年度的1-4月的4個(gè)月內(nèi)需租用倉庫堆放物資.已知各月份所需倉庫面積數(shù)列于表1.倉庫租借費(fèi)用隨合同期而定,期限越長(zhǎng),折扣越大,具體數(shù)字見表2.租借倉庫的合同每月初都可辦理,每份合同具體規(guī)定租用面積數(shù)和期限.因此該廠可根據(jù)需要,在任何一個(gè)月初辦理租借合同.每次辦理時(shí)可簽一份,也可簽若干份租用面積和租借期限不同的合同,試確定該公司簽訂租借合同的最優(yōu)決策,目的是使所付租借費(fèi)用最小.月份1234所需倉庫面積(100m2)15102012表1合同租借期限1個(gè)月2個(gè)月3個(gè)月4個(gè)月倉庫借費(fèi)用(元/100m2)2800450060007300表2解:1)設(shè)決策變量xij表示捷運(yùn)公司在第i(I=1,2,3,4)個(gè)月初簽訂的租借期為j(j=1,2,3,4)個(gè)月的倉庫面積的合同(單位為100m2).因5月份起該公司不需要租借倉庫,故x24,x33,x34,x42,x43,x44均為零2)目標(biāo)函數(shù):使總的租借費(fèi)用最小3)約束條件:每個(gè)月份所需倉庫面積的限制二、整數(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)目所需投資額（萬元）期望收益（萬元）A610B48C27D46E59解：決策變量：設(shè)目標(biāo)函數(shù)：期望收益最大約束條件：投資額限制條件6x1+4x2+2x3+4x4+5x515項(xiàng)目A、C、E之間必須且只需選擇一項(xiàng)：x1+x3+x5=1項(xiàng)目C的實(shí)施要以項(xiàng)目D的實(shí)施為前提條件：x3

x4項(xiàng)目B、D之間必須且只需選擇一項(xiàng)：x2+x4=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í)段12345678服務(wù)員最少數(shù)目10891113853解：設(shè)在第j時(shí)段開始時(shí)上班的服務(wù)員人數(shù)為xj，由于第j時(shí)段開始時(shí)上班的服務(wù)員將在第(j+3)時(shí)段結(jié)束時(shí)下班，故決策變量只需考慮x1,x2,x3,x4,x5，此問題的數(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ù)0123456789101100am-02am02am-04am04am-06am06am-08am08am-10am10am-12pm12pm-02pm02pm-04pm04pm-06pm06pm-08pm08pm-10pm10pm-12am151515354040403031353020問題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è)xt為時(shí)段t開始工作的護(hù)士數(shù)目問題1模型最優(yōu)方案由此我們看到，第1問題求出的最優(yōu)解為至少需要100名護(hù)士，然而目前只有80名，這就需要安排一部分人加班。設(shè)變量yt表示t時(shí)段開始工作并且需要加班2小時(shí)的護(hù)士人數(shù),問題需要求的是滿足服務(wù)需要，最小需要加班的人數(shù)，因此模型變?yōu)椋簍時(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)品單件耗量資源123資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價(jià)81012解：總收益等于銷售收入減去生產(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í)aij如下表。由于某種原因，產(chǎn)品2的加工總時(shí)間不得超過d，現(xiàn)要求確定各件產(chǎn)品在機(jī)床上的加工方案，使在最短的時(shí)間內(nèi)加工完全部產(chǎn)品。產(chǎn)品1a11a13a14機(jī)床1機(jī)床3機(jī)床4產(chǎn)品2a21a22a24機(jī)床1機(jī)床2機(jī)床4產(chǎn)品3a32a33機(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)品的加工。對(duì)于機(jī)床1，有兩種加工順序。或先加工產(chǎn)品1，后加工產(chǎn)品2；或反之。對(duì)于其它3臺(tái)機(jī)床，情況也類似。為了容納兩種相互排斥的約束條件，對(duì)于每臺(tái)機(jī)床，分別引入0-1變量各yj的意義是明顯的。如當(dāng)yj=0時(shí)，表示機(jī)床1先加工產(chǎn)品1，后加工產(chǎn)品2，當(dāng)yj=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í)間是x21，結(jié)束加工時(shí)間是x24+a24，故應(yīng)有：4、目標(biāo)函數(shù)的建立設(shè)全部產(chǎn)品加工完畢的結(jié)束時(shí)間為W，由于三件產(chǎn)品的加工結(jié)束時(shí)間分別為x14+a14，x24+a24，x33+a33，故全部產(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è)消防站。問題的目標(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í)間(分)1234515123020152204151025315206151242515254105102515125每年平均發(fā)生火災(zāi)次數(shù)21313有一家大公司希望開設(shè)一些新的倉庫，以向銷售中心供貨。每開設(shè)一個(gè)新倉庫都有一些固定費(fèi)用。貨物將從倉庫運(yùn)輸?shù)礁浇匿N售中心。每次運(yùn)輸?shù)倪\(yùn)費(fèi)取決于運(yùn)輸?shù)木嚯x。這兩種類型的費(fèi)用非常不同：倉庫開設(shè)費(fèi)用屬于投資支出，通常在若干年后將勾銷，而運(yùn)輸費(fèi)用屬于運(yùn)營(yíng)成本。我們假定這兩種費(fèi)用可比，為此可能需要以年為單位計(jì)算運(yùn)營(yíng)費(fèi)用。有12個(gè)可以建造新倉庫的位置，并且需要從這些倉庫向12個(gè)銷售中心供貨。下表給出了每個(gè)倉庫完全滿足每個(gè)客戶（銷售中心）需求所需的總成本（千歐元，不是單位成本）。因此，例如從倉庫1向客戶9（根據(jù)表3可以看到此客戶總需求量為30噸）供貨的單位成本為60000歐元/30噸，即2000歐元/噸。如果無法進(jìn)行送貨，則對(duì)應(yīng)的成本標(biāo)記為無窮大∞。倉庫位置設(shè)置問題案例7：客戶倉庫12345678910111211008050506010012090607065110212090607065110140110808075130314011080807513016012510010080150416012510010080150190150130∞∞∞5190150130∞∞∞20018050∞∞∞6200180150∞∞∞10080505060100710080505060100120906070651108120906070651101401108080751309140110808075130160125100100801501016012510010080150190150130∞∞∞11190150130∞∞∞200180150∞∞∞12200180150∞∞∞10080505060100表格1：滿足客戶需求所需的運(yùn)輸成本此外，對(duì)每個(gè)倉庫，還有如下信息：倉庫建設(shè)的固定費(fèi)用（需要計(jì)入目標(biāo)函數(shù)）和倉庫的容量上限，這些信息都列于表2中。表格2：倉庫建設(shè)費(fèi)用和容量限制倉庫123456789101112建設(shè)費(fèi)用350090001000040003000900090003000400010000900035000容量上限300250100180275300200220270250230180表3列出了各個(gè)銷售中心（客戶）的需求量客戶123456789101112需求量120807510011010090603015095120任何時(shí)候都要保證滿足客戶需求，可以從多個(gè)倉庫向同一個(gè)客戶送貨。應(yīng)在哪些位置開辦倉庫才能使總的建設(shè)成本以及運(yùn)輸成本最低，同時(shí)仍然能夠滿足所有客戶需求？分析決策變量：12個(gè)倉庫中需要決策選擇哪些倉庫，

每個(gè)被選中的倉庫運(yùn)輸給每個(gè)客戶的運(yùn)輸量xij

目標(biāo)：總成本=建設(shè)成本+運(yùn)輸成本

約束：倉庫容量上限約束客戶需求量約束只有當(dāng)某一位置建設(shè)了倉庫才能向客戶運(yùn)輸產(chǎn)品數(shù)據(jù)處理最優(yōu)方案更深入的問題：一個(gè)客戶只允許由一個(gè)倉庫共貨，但一個(gè)倉庫可供多個(gè)客戶。案例8：所得稅交納點(diǎn)選址問題所得稅管理部門計(jì)劃對(duì)某個(gè)地區(qū)的所得稅交納點(diǎn)網(wǎng)絡(luò)進(jìn)行重新設(shè)計(jì)。下圖是對(duì)此地區(qū)內(nèi)的城市和主要道路的示意圖。城市這邊的黑體數(shù)字表示城市的居民數(shù)目，單位為千人。在連接城市之間的弧上標(biāo)出了它們之間的距離，單位為千米。為覆蓋各城市，所得稅管理部門決定在三個(gè)城市中設(shè)置納稅點(diǎn)。應(yīng)在哪三個(gè)城市中設(shè)置納稅點(diǎn)才能使居民與最近的納稅點(diǎn)之間平均距離最??？12357101149612815221812221219192120243025192215182415101218242019221651311121235710114961281522181222121919212024302519221518241510121824201922165131112分析：首先要根據(jù)圖求出任意兩點(diǎn)之間的最短距離矩陣其次：確定納稅點(diǎn)選址，與消防站點(diǎn)設(shè)置問題相似將每一個(gè)居民點(diǎn)乘以其人數(shù)，得人數(shù)加權(quán)距離矩陣決策變量：yi第i個(gè)居民點(diǎn)設(shè)置為納稅點(diǎn)，xij第j個(gè)居民點(diǎn)的人到第i個(gè)納稅點(diǎn)交稅目標(biāo)總距離最小：wij人數(shù)，dij距離約束：設(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ì)下圖是一個(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ì)其全部替換。●中繼站蜂窩12個(gè)連接●中繼站蜂窩21個(gè)連接樞紐4樞紐1樞紐3樞紐2交換局環(huán)路在目前的技術(shù)條件下，中繼站和交換局之間無法進(jìn)行動(dòng)態(tài)連接。在設(shè)計(jì)階段即應(yīng)固定這些連接，因此需要為每個(gè)中繼站選擇其連接到的環(huán)路結(jié)點(diǎn)。在蜂窩c和環(huán)路之間的連接數(shù)目稱為蜂窩c的多徑數(shù)，用CNCTc表示。為使系統(tǒng)更為可靠，多徑數(shù)應(yīng)大于1。這種類型的系統(tǒng)中的通信是完全數(shù)字化的，通信帶寬可以表示為帶寬為64kbps（千比特每秒）的雙向回路數(shù)目。則此帶寬數(shù)值即對(duì)應(yīng)于在高峰期可并發(fā)的通信數(shù)。環(huán)路的帶寬上限為CAP。從蜂窩c發(fā)出的通信量TRAFc可以平均分配到蜂窩與環(huán)路之間的各個(gè)連接上，每個(gè)連接分配到的通信量為TRAFc/CNTCc。此通信量將通過環(huán)路傳輸?shù)浇粨Q局，在交換局中將把各個(gè)呼叫轉(zhuǎn)移到另一個(gè)蜂窩或移動(dòng)電話與固定電話之間的接口結(jié)點(diǎn)。由于交換局具有普通樞紐的所有功能，因此中繼站也可以直接連接到交換局。我們考慮到一個(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è)Ccn表示蜂窩c連接到結(jié)點(diǎn)n的成本，xcn表示蜂窩c是否連接到結(jié)點(diǎn)n，則目標(biāo)：連接成本最小約束：每個(gè)蜂窩的連接數(shù)等于需要的連接數(shù)通話能力（帶寬）限制案例10