運(yùn)籌學(xué)模型.doc

第五章 運(yùn)籌學(xué)模型源于第二次世界大戰(zhàn)期間的運(yùn)籌學(xué)研究，有效地解決了如何將有限的資源分配于各項(xiàng)軍事活動(dòng)，以取得最優(yōu)的戰(zhàn)爭效果等重大軍事決策問題，為盟軍取得二戰(zhàn)的勝利作出了不可磨滅的貢獻(xiàn)。戰(zhàn)后，該項(xiàng)技術(shù)不但在軍事科學(xué)上不斷發(fā)展，在工農(nóng)業(yè)生產(chǎn)、科學(xué)實(shí)驗(yàn)、工程技術(shù)、經(jīng)濟(jì)管理和社會(huì)科學(xué)中都有著廣泛的應(yīng)用和發(fā)展。特別是計(jì)算機(jī)技術(shù)的引入，更使得運(yùn)籌學(xué)的研究和應(yīng)用如虎添翼，一些大規(guī)?；虺笠?guī)模的決策變量和約束條件問題的求解也變成了現(xiàn)實(shí)。運(yùn)籌學(xué)的分支較多，這里我們只介紹線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃等方面的運(yùn)籌學(xué)應(yīng)用和模型，讀者通過學(xué)習(xí)解決這些運(yùn)籌學(xué)問題的思想和方法，而對(duì)運(yùn)籌學(xué)模型的建立、應(yīng)用和求解有更深的認(rèn)識(shí)。5.1 線性規(guī)劃模型1線性規(guī)劃數(shù)學(xué)模型的一般形式 為了能更容易理解線性規(guī)劃模型，我們先看下面的例子。例1農(nóng)作物的生產(chǎn)安排問題1）問題的提出以色列的某社區(qū)聯(lián)盟，其農(nóng)業(yè)生產(chǎn)受農(nóng)田面積和灌溉配水量的限制，其資料如表4.1所示表4.1社區(qū)可耕地（英畝）配水量140060026008003300375適合該地區(qū)種植的農(nóng)作物有甜菜、棉花和栗子，其每英畝的期望凈收益、用水量及可種植的最大面積如表4.2所示表4.2農(nóng)作物最大面積（英畝）每英畝用水量凈收益（元/英畝）甜菜6003400棉花5002300栗子3251100試問，該社區(qū)聯(lián)盟應(yīng)如何安排這三種農(nóng)作物的生產(chǎn)，方使總的收益最大？2）假設(shè)與分析決策變量分別表示這三個(gè)社區(qū)三種農(nóng)作物的種植面積（見表4.3所示）。 表4.3農(nóng)作物社區(qū)123甜菜棉花栗子則該問題的線性規(guī)劃模型為：目標(biāo)函數(shù) 約束條件為：非負(fù)性： 土地約束： 水資源約束： 最大面積約束：3）模型的建立與求解用單純形法或用數(shù)學(xué)軟件包求得其最優(yōu)解如下表所示：農(nóng)作物社區(qū)123甜菜10025棉花100250150栗子000一般地，線性規(guī)劃問題的求解過程具有如下的一些共同特征：（1）每一問題都可用一組稱之為決策變量的未知數(shù)來表示相應(yīng)的活動(dòng)方案，由于實(shí)際問題的要求，這些決策變量通常是非負(fù)的。（2）對(duì)決策變量，大都存在一定的限制條件（稱為約束條件），且這些限制條件一般可用關(guān)于決策變量的一組線性不等式或等式來表示。（3）有一個(gè)追求的目標(biāo)函數(shù)，且目標(biāo)函數(shù)一般可表示為決策變量的線性函數(shù)，并由實(shí)際問題來決定目標(biāo)函數(shù)應(yīng)追求最大還是最小。用數(shù)學(xué)語言描述，線性規(guī)劃問題的的數(shù)學(xué)模型為：目標(biāo)函數(shù)： 約束條件為：簡單線性規(guī)劃問題大都用圖解法或單純形法求解，而復(fù)雜線性規(guī)劃問題可用相應(yīng)的數(shù)學(xué)軟件包求解，這里，不再詳述。2.應(yīng)用實(shí)例例2空氣污染管理問題1) 問題的提出 位于鋼城的諾利公司為當(dāng)?shù)氐闹饕撹F廠家之一，公司為鋼城的繁榮與發(fā)展作出了一定的貢獻(xiàn)。但現(xiàn)在情況有所改變，由于鋼廠對(duì)熔爐的排放物未進(jìn)行管理，致使空氣污染破壞了鋼城的環(huán)境，并危害了當(dāng)?shù)鼐用竦慕】?。公司董事?huì)就此作出了明智的決定，指定專門人員與市政官員和人民團(tuán)體商討解決空氣污染問題，以保證工廠的排放物能達(dá)到環(huán)保部門的要求。研究發(fā)現(xiàn)，造成空氣污染的物質(zhì)主要有三種：微粒、氧化硫及碳化氫，鋼廠每年須減少的污染物排放量達(dá)到表4.4的要求時(shí)，方滿足環(huán)保的要求。表4.4 （環(huán)保部門的空氣清潔標(biāo)準(zhǔn)）污染物每年須減少的污染物排放量（百萬磅）微粒60氧化硫150碳化氫125污染物的主要來源為：（1）制造生鐵之鼓風(fēng)爐；（2）煉鋼之敞爐。減少污染物排放的有效方法為：（1）增加煙囪高度；（2）在煙囪內(nèi)安裝過濾器；（3）使用優(yōu)質(zhì)燃料。這些方法對(duì)減少污染雖有幫助（其效果見表4.5），但任一方法的單獨(dú)使用，均不能達(dá)到環(huán)保部門的要求，若三種方法同時(shí)以最高的標(biāo)準(zhǔn)實(shí)施，則工廠的產(chǎn)品成本將陡增，從而使產(chǎn)品失去市場(chǎng)競(jìng)爭力甚至因此而破產(chǎn)，管理部門因此而憂心忡忡。表4.5（各減污法每年最高可能減少的污染排放量（單位：百萬磅）污染物增高煙囪安裝過濾器使用優(yōu)質(zhì)燃料鼓風(fēng)爐敞爐鼓風(fēng)爐敞爐鼓風(fēng)爐敞爐微 粒12925201713氧化硫354218315649碳化氫375328242920專題組人員經(jīng)分析知各減污方法中最高減污量之總成本的近似值如表4.6所示。而公司每年可撥出的治污?？钜灿幸坏紫?，試確定該公司是否能實(shí)施“空氣污染管理”工程。表4.6（最高減污法之總成本：以百萬元為單位）減 污 法鼓風(fēng)爐敞 爐增高煙囪810過 濾 器76優(yōu)質(zhì)燃料1192）假設(shè)與模型的建立工程實(shí)施的關(guān)鍵在于既要確保排污效果能達(dá)到環(huán)保部門的要求，又要最大限度地降低成本（不超過其所能承受的底限）。由于問題的解決具有組合性，故可考慮用線性規(guī)劃模型求解，假設(shè)決策變量分別表示各減污法中最高成本的比例值（見下表）減污方法鼓風(fēng)爐敞爐增高煙囪過濾器優(yōu)質(zhì)燃料則其目標(biāo)函數(shù)為：約束條件為：求解得：工程造價(jià)為：。若問題的最優(yōu)解3215.9萬元未超過公司所能承受的底限，則該治污工程可上馬，否則得另謀它法。例3飼料配比問題1) 問題的提出 某公司長期飼養(yǎng)實(shí)驗(yàn)用的動(dòng)物以供出售，已知這些動(dòng)物的生長對(duì)飼料中的蛋白質(zhì)、礦物質(zhì)、維生素這三種營養(yǎng)成分特別敏感，每個(gè)動(dòng)物每天至少需要蛋白質(zhì)70g、礦物質(zhì)3g、維生素10mg，該公司能買到五種不同的飼料，每種飼料1 kg所含的營養(yǎng)成分如表4.7所示，每種飼料1kg的成本如表4.8所示，試為公司制定相應(yīng)的飼料配方，以滿足動(dòng)物生長的營養(yǎng)需要，并使投入的總成本最低。表4.7飼料蛋白質(zhì)（g）礦物質(zhì)（g）維生素（mg）10.30.10.05220.050.1310.020.0240.60.20.251.80.050.08表4.8飼 料12345成本（元）0.20.70.40.30.52）假設(shè)與分析設(shè)表示混合飼料中所含的第種飼料的數(shù)量（即決策變量），因每個(gè)動(dòng)物每天至少需要蛋白質(zhì)70g、礦物質(zhì)3g、維生素10mg，所以應(yīng)滿足如下的約束條件因要求配制出來的飼料其總成本最低，故其目標(biāo)函數(shù)為：由于約束條件及目標(biāo)函數(shù)均為線性函數(shù)，故原問題是一線性規(guī)劃模型。3）模型的建立與求解由上述討論知，飼料配比問題的線性規(guī)劃模型為：，使如下約束條件成立：例4 連續(xù)投資問題1) 問題的提出 某部門在今后五年內(nèi)考慮給下列項(xiàng)目投資，已知如下條件：項(xiàng)目A，從第一年到第四年每年年初均需投資，并于次年末回收本利115%；項(xiàng)目B，第三年初需要投資，到第五年末回收本利125%，但規(guī)定最大投資額不超過4萬元；項(xiàng)目C，第二年初需要投資，到第五年末回收本利140%，但規(guī)定最大投資額不超過3萬元；項(xiàng)目D，五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，可獲利息6%。該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給給這些項(xiàng)目每年的投資額，使到第五年末部門所擁有的資金的本利總額最大。2）假設(shè)與分析這是一個(gè)連續(xù)投資問題，能否定義好決策變量，并使之滿足線性關(guān)系，是能否用線性規(guī)劃方法求最優(yōu)解的關(guān)鍵。我們用表示第年初分別用于項(xiàng)目A，B，C，D的投資額（即決策變量），根據(jù)題設(shè)條件，可列出表4.9（表中空格部分表示該項(xiàng)目當(dāng)年的投資為0）：表4.9年份項(xiàng)目12345ABCD下面討論這些決策變量應(yīng)滿足的線性約束條件。從表4.9知：第一年年初僅對(duì)項(xiàng)目A、D進(jìn)行投資，因年初擁有資金10萬元，設(shè)項(xiàng)目A、D的投資額分別為、，則有：。同理，第二年對(duì)項(xiàng)目A、C、D的投資額應(yīng)滿足方程：而第三年、第四年、第五年對(duì)項(xiàng)目A、B、D；項(xiàng)目A、D；項(xiàng)目D的投資額應(yīng)分別滿足如下的方程：另外，項(xiàng)目B、C的投資額度應(yīng)受如下