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