運(yùn)籌學(xué)模型運(yùn)籌學(xué)作為科學(xué)名字是出現(xiàn)在20世紀(jì)30年代末。當(dāng)時英、美對付德國的空襲，雷達(dá)作為防空系統(tǒng)的一部分，從技術(shù)上是可行的，但實(shí)際運(yùn)用時卻并不好用。為此一些科學(xué)家研究如何合理運(yùn)用雷達(dá)開始進(jìn)行一類新問題的研究。因?yàn)樗c研究技術(shù)問題不同，就稱之為“運(yùn)用研究”（OperationalResearch）（我國在1957年正式定名為運(yùn)籌學(xué)）。為了進(jìn)行運(yùn)籌學(xué)研究，在英、美的軍隊(duì)中成立了一些專門小組，開展了護(hù)航艦隊(duì)保護(hù)商船隊(duì)的編隊(duì)問題和當(dāng)船隊(duì)遭受德國潛艇攻擊時，如何使船隊(duì)損失最少的問題的研究。研究了反潛深水炸彈的合理爆炸深度后，使德國潛艇被摧毀數(shù)增加到400%，研究還使船只在受敵機(jī)攻擊時，中彈數(shù)由47%降到29%。二戰(zhàn)結(jié)束后，在英、美軍隊(duì)中相繼成立了更為正式的運(yùn)籌研究組織。并以蘭德公司（RAND）為首的一些部門開始著重研究戰(zhàn)略性問題、未來的武器系統(tǒng)的設(shè)計(jì)和未來戰(zhàn)爭的戰(zhàn)略。到60年代，參與了戰(zhàn)略力量的構(gòu)成和數(shù)量問題研究，除軍事方面的應(yīng)用研究以外，相繼在工業(yè)、農(nóng)業(yè)、經(jīng)濟(jì)和社會問題等各領(lǐng)域都有應(yīng)用。與此同時，運(yùn)籌學(xué)有了飛快的發(fā)展，并形成了運(yùn)籌學(xué)的許多分支。如數(shù)學(xué)規(guī)劃（線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動態(tài)規(guī)劃、隨機(jī)規(guī)劃等）、圖論與網(wǎng)絡(luò)、排隊(duì)論（隨機(jī)服務(wù)系統(tǒng)理論）、存貯論、對策論、決策論等。0緒論

0-1運(yùn)籌學(xué)簡史在中國，最早的運(yùn)籌學(xué)思想有戰(zhàn)國時期的田忌賽馬，它是對策論的一個典型例子，北宋時期的丁渭造皇宮，它是統(tǒng)籌規(guī)劃的一個例子。50年代中期，錢學(xué)森、許國志等教授在國內(nèi)全面介紹和推廣運(yùn)籌學(xué)知識，1956年，中國科學(xué)院成立第一個運(yùn)籌學(xué)研究室，1957年運(yùn)籌學(xué)運(yùn)用到建筑和紡織業(yè)中，1958年提出了圖上作業(yè)法，山東大學(xué)的管梅谷教授提出了“中國郵遞員問題”，1970年，在華羅庚教授的直接指導(dǎo)下，在全國范圍內(nèi)推廣統(tǒng)籌方法和優(yōu)選法。1978年11月，在成都召開了全國數(shù)學(xué)年會，對運(yùn)籌學(xué)的理論與應(yīng)用研究進(jìn)行了一次檢閱，1980年4月在山東濟(jì)南正式成立了“中國數(shù)學(xué)會運(yùn)籌學(xué)會”，1984年在上海召開了“中國數(shù)學(xué)會運(yùn)籌學(xué)會第二屆代表大會暨學(xué)術(shù)交流會”，并將學(xué)會改名為“中國運(yùn)籌學(xué)會”。

0-3運(yùn)籌學(xué)的基本內(nèi)容1、線性規(guī)劃（LinearProgram）是一個成熟的分支，它有效的算法——單純形法，主要解決生產(chǎn)計(jì)劃問題，合理下料問題，最優(yōu)投資問題。2、整數(shù)規(guī)劃(IntegrateProgram)：在線性規(guī)劃的基礎(chǔ)上，變量加上整數(shù)約束。3、非線性規(guī)劃(NonlinearProgram)：目標(biāo)函數(shù)和約束條件是非線性函數(shù)，如證券投資組合優(yōu)化:如何合理投資使風(fēng)險最小。4、動態(tài)規(guī)劃(DynamicProgram):多階段決策問題。是美國貝爾曼于1951年提出的。5、圖與網(wǎng)絡(luò)(GraphTheoryandNetwork)：中國郵遞員問題、哥尼斯堡城問題、最短路、最大流問題。6、存儲模型（InventoryTheory)：主要解決生產(chǎn)中的庫存問題，訂貨周期和訂貨量等問題。7、排隊(duì)論(QueueTheory)：主要研究排隊(duì)系統(tǒng)中的系統(tǒng)排隊(duì)和系統(tǒng)擁擠現(xiàn)象，從而評估系統(tǒng)的服務(wù)質(zhì)量。8、對策論(GameTheory)：主要研究具有斗爭性質(zhì)的優(yōu)化問題。9、決策分析(DecisionAnalysis)：主要研究定量化決策。今天我們給大家介紹的是應(yīng)用最為廣泛的線性規(guī)劃1線性規(guī)劃問題及其數(shù)學(xué)模型

1-1問題的提出例1某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ的兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時，A、B兩種原材料的消耗以及每件產(chǎn)品可獲得的利潤如下表所示。問應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲利最多？ⅠⅡ資源限量設(shè)備128(臺時)原材料A4016(kg)原材料B0412(kg)單位產(chǎn)品利潤（元）23

例2

靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3，兩工廠之間有一條流量為每天200萬m3的支流（見圖）。

第一化工廠每天排放污水2萬m3，第二化工廠每天排放污水1.4萬m3。污水從工廠1流到工廠2前會有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于0.2%。而工廠1和工廠2處理污水的成本分別為1000元/萬m3和800元/萬m3。問兩工廠各應(yīng)處理多少污水才能使處理污水的總費(fèi)用最低？解：設(shè)工廠1和工廠2每天分別處理污水x1

和x2萬m3，總費(fèi)用為z，則有：1-2線性規(guī)劃的基本概念以上兩例都有一些共同的特征：用一組變量表示某個方案，通常是該問題要求解的那些未知量，用x=(x1,x2,…xn)T表示，一般這些變量取值是非負(fù)的，這里的變量稱之為決策變量。存在對決策變量的約束條件，即x允許取值的范圍，通常用一組關(guān)于x的等式hi(x)=0或不等式gj(x)≥0(≤0)來界定，分別稱為等式約束和不等式約束。⑵與⑵’中的幾個不等式是問題的約束條件，記為s.t.(即subjectto)。都有一個要達(dá)到的目標(biāo)，一般是達(dá)到最大或者最小，它是決策變量x的函數(shù)，可以表示成maxf(x)或minf(x)

。⑴與⑴’式被稱為問題的目標(biāo)函數(shù)。上述“決策變量、約束條件、目標(biāo)函數(shù)”即為一規(guī)劃問題數(shù)學(xué)模型的三個要素。由于上面例子中的目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題。線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題，簡稱線性規(guī)劃(LinearProgramming)或簡稱LP。1、線性規(guī)劃的數(shù)學(xué)模型一般式標(biāo)準(zhǔn)式2、線性規(guī)劃的解法：常用的解法有圖解法和單純型法，但在建模中更普遍的是使用數(shù)學(xué)軟件求解。如LINGO，MATHEMATICA。對線性規(guī)劃的解法有興趣的讀者可以參閱其它相關(guān)書籍介紹3、線性規(guī)劃的建模步驟：設(shè)置要求解的決策變量x1,x2,…xn

。明確目標(biāo)函數(shù)，并用決策變量的線性函數(shù)來表示，確定對函數(shù)是取最大還是取最小的要求。找出所有的限制，即約束條件。并用決策變量的線性方程或線性不等式來表示。當(dāng)限制條件多，背景比較復(fù)雜時，可以采用圖示或表格形式列出所有的已知數(shù)據(jù)和信息，以避免“遺漏”或“重復(fù)”所造成的錯誤。例4合理利用線材問題現(xiàn)要做一百套鋼管，每套要長為2.9m、2.1m和1.5m的鋼管各一根。已知原料長7.4m，問應(yīng)如何下料，使用的原料最省。解：先看有多少種裁料方案，再進(jìn)行組合和選擇。方案如下表所示：決策變量

目標(biāo)函數(shù)

原料最省約束條件三種長度的鋼管在8種切割方案下的總和各不少于100根；非負(fù)限制方案Ⅰ,Ⅱ,…,Ⅷ分別裁原料鋼管x1,x2,…,x8根

IIIIIIIVVVIVIIVIII2.9m211100002.1m021032101.5m10130234料頭0.10.30.901.10.20.81.4例5連續(xù)投資問題某公司經(jīng)調(diào)研分析知，在今后三年內(nèi)有四種投資機(jī)會。方案A是在三年內(nèi)每年年初投資，年底可獲利15%，并可將本金收回；方案B是在第一年的年初投資，第二年的年底可獲利45%，并將本金收回，但該項(xiàng)投資不得超過2萬元；方案C是在第二年的年初投資，第三年的年底可獲利65%，并將本金收回，但該項(xiàng)投資不得超過1.5萬元；方案D是在第三年的年初投資，年底收回本金，且可獲利35%，但該項(xiàng)投資不得超過1萬元?，F(xiàn)在本公司準(zhǔn)備拿出3萬元來投資，問如何計(jì)劃可使到第三年年未本利和最大？解：第i年初(即第i-1年末)投資各項(xiàng)目的資金為xiA,xiB,xiC,xiD該問題的實(shí)際投資背景如下表所示:年份一二三四x1A1.15x1Ax1B1.45x1Bx2A1.15x2Ax2C1.65x2Cx3A1.15x3Ax3D1.35x3D

決策變量

目標(biāo)函數(shù)

3年末擁有的資金最多約束條件每年的投資額等于手中的資金；非負(fù)限制解：設(shè)xij表示A公司在第i(i=1,2,3,4)個月初簽訂的租借期為j(j=1,2,3,4)個月的倉庫面積的合同(單位為100m2)。因5月份起該公司不需要租借倉庫，該問題的實(shí)際投資背景如下表所示:決策變量

月份（月初）1234x11x12x12x13x13x13x14x14x14x14x21x22x22x23x23x23x31x32x32x41目標(biāo)函數(shù)

約束條件每個月份所需倉庫面積的限制；非負(fù)限制例7混合配料問題某糖果廠用原料A，B，C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中A，B，C含量，原料成本，各種原料的每月限制用量,三種牌號糖果的單位加工費(fèi)及售價如下表所示。問該廠每月生產(chǎn)這三種牌號糖果各多少時，使該廠獲利最大。試建立這個問題的線性規(guī)劃模型。甲乙丙原料成本（元/kg）每月限制量（kg)A>60%>30%2.002000B1.502500C<20%<50%<60%1.001200加工費(fèi)（元/kg）0.500.400.30售價（元/kg）3.402.852.25例8一個木材儲運(yùn)公司有很大的倉庫用以儲運(yùn)出售木材。由于木材季度價格的變化，該公司于每季度初購進(jìn)木材，一部分于本季度內(nèi)出售，一部分儲存起來以后出售。已知該公司倉庫的最大儲存量為2000萬米3，儲存費(fèi)用為（70+100u）千元/萬米3，u為存儲時間（季度數(shù)）。已知每季度的買進(jìn)賣出價及預(yù)計(jì)的銷售量如下表所示。由于木材不宜久貯，所有庫存木材應(yīng)于每年秋末售完。為使售后利潤最大，試建立這個問題的線性規(guī)劃模型。季度買進(jìn)價（萬元/萬米3

）賣出價（萬元/萬米3

）預(yù)計(jì)銷售量（萬米3

）冬4104251000春4304401400夏4604652000秋4504551600例9有一艘貨輪，分前、中、后三個艙位，它們的容積與最大允許載重量如表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)收入為最大？試建立這個問題的線性規(guī)劃模型。前中后最大允許載重量(噸)200030001500容積（立方米）400054001500商品數(shù)量（件）每件體積（立方米/件）每件重量（噸/件）運(yùn)價（元/件）A6001081000B100056700C80075600在我國古代的北宋（公元960～1127年）年間，有一天皇帝居住的皇城（今河南開封）因不慎失火，釀成一場大災(zāi)，熊熊大火使鱗次櫛比、覆壓數(shù)里的皇宮，在一夜之間變成斷壁殘?jiān)?。為了修?fù)燒毀的宮殿，皇帝詔令