清華大學(xué)MBA課程——運(yùn)籌學(xué)

1、課程介紹一、運(yùn)籌學(xué)產(chǎn)生的和發(fā)展1. 運(yùn)籌學(xué)產(chǎn)生的原因 ü 科學(xué)技術(shù)的發(fā)展，利用和改造自然的規(guī)模擴(kuò)大，生產(chǎn)規(guī)模擴(kuò)大，生產(chǎn)組織形式復(fù)雜，出現(xiàn)了更復(fù)雜的管理方面的問題。 ü 管理方面的新問題：如何有效和合理地利用有限的或稀缺的資源，使系統(tǒng)的整體目標(biāo)達(dá)到最優(yōu)。2. 運(yùn)籌學(xué)的起源 ü 運(yùn)籌學(xué)的三個(gè)來源：軍事、經(jīng)濟(jì)、管理 ü 1981年美國軍事運(yùn)籌學(xué)會(huì)出版的 “System analysis and modeling in defence”一書中稱孫武子是世界上第一個(gè)軍事運(yùn)籌學(xué)家。 ü 第二次世界大戰(zhàn)期間英、美等國軍事部門成立的一些研究小組的研究活動(dòng)。最初

2、人們稱這類研究為 “運(yùn)作研究” (operational research)，或“運(yùn)作分析” (operational analysis)。 ü 研究的特點(diǎn)是集中一批跨多學(xué)科的研究人員，有組織地對一特定問題進(jìn)行系統(tǒng)分析，提出提高某武器系統(tǒng)效率的操作方法和執(zhí)行策略。ü 二戰(zhàn)期間成功的運(yùn)籌研究案例有： 英國防空部門如何布置防空雷達(dá)，建立有效的空防預(yù)警系統(tǒng)； 研究反潛飛機(jī)巡邏路線及深水炸彈引爆深度，擊沉德軍潛艇數(shù)提高4倍； 研究如何使用機(jī)載雷達(dá)提高轟炸命中率，兩年內(nèi)使命中率提高3倍； 研究船隊(duì)在受敵機(jī)攻擊時(shí)的躲避策略，使中彈率從47%下降到29%；ü 數(shù)理經(jīng)濟(jì)對運(yùn)籌學(xué)的

3、影響 Qusnay 的經(jīng)濟(jì)表 Walras 提出的經(jīng)濟(jì)平衡問題 Von Neumann 提出的廣義經(jīng)濟(jì)平衡模型 康托洛維奇 (Kantorovich)發(fā)表的生產(chǎn)組織和計(jì)劃中的數(shù)學(xué)方法ü 管理科學(xué) - 運(yùn)籌學(xué)的關(guān)系 ü 管理理論中最有影響的三個(gè)學(xué)派中的兩個(gè)（古典學(xué)派與系統(tǒng)學(xué)派）廣泛應(yīng)用定量分析與系統(tǒng)分析的方法。 ü 古典學(xué)派的代表性人物 Taylor, Gantt 等提出的動(dòng)作分析、甘特圖至今還在使用。3. 運(yùn)籌學(xué)的發(fā)展 二戰(zhàn)結(jié)束后運(yùn)籌學(xué)在理論上得到全面的發(fā)展；線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)分析、整數(shù)規(guī)劃、對策論、排隊(duì)論等分枝得到迅速的發(fā)展。運(yùn)籌學(xué)應(yīng)用從軍事部

4、門迅速向工業(yè)部門轉(zhuǎn)移。經(jīng)過50多年的發(fā)展，運(yùn)籌學(xué)已成為一個(gè)門類齊全、理論完善、有廣泛應(yīng)用前景的新興的科學(xué)學(xué)科。運(yùn)籌學(xué)發(fā)展有以下幾方面的原因： ü 運(yùn)籌學(xué)在戰(zhàn)爭中的成功吸引更多的資源投入這一研究領(lǐng)域； ü 二戰(zhàn)結(jié)束后，經(jīng)濟(jì)發(fā)展成為各方注視的焦點(diǎn)，經(jīng)濟(jì)和工業(yè)界有許多問題可以用運(yùn)籌學(xué)方法解決； ü 計(jì)算機(jī)的出現(xiàn)為運(yùn)籌學(xué)的應(yīng)用提供了最好的技術(shù)支持。線性規(guī)劃的發(fā)明 ü 丹捷格(Danzing)1947年提出單純形法； ü 康托洛維奇 (Kantorovich) 于1939提出用于前蘇聯(lián)經(jīng)濟(jì)計(jì)劃的類似模型及“解乘數(shù)法”的求解方法； ü 馮. 諾伊

5、曼 (Von Neuman) 和摩根斯坦(Morgenstern) 1944年發(fā)表的對策論與經(jīng)濟(jì)行為涉及與線性規(guī)劃等價(jià)的對策問題及線性規(guī)劃對偶理論。ü 康托洛維奇和庫伯曼斯(Koopmans)因?qū)Y源最優(yōu)分配理論的貢獻(xiàn)而獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng) ü 從1964年諾貝爾獎(jiǎng)設(shè)經(jīng)濟(jì)學(xué)獎(jiǎng)后，到1992年24年間的32名獲獎(jiǎng)?wù)咧杏?3人 (40%) 從事過與線性規(guī)劃有關(guān)的研究工作，其中比較著名的還有Simon， Samullson，Leontief，Arrow，Miller 等。4. 運(yùn)籌學(xué)對社會(huì)的影響運(yùn)籌學(xué)應(yīng)用領(lǐng)域的進(jìn)一步擴(kuò)大，運(yùn)籌學(xué)已滲透到社會(huì)生活各個(gè)角落，在石油、電力、航空、

6、冶金、交通運(yùn)輸、通訊、軍事等領(lǐng)域有廣泛的應(yīng)用，給人們帶來巨大的財(cái)富二、運(yùn)籌學(xué)研究的對象與特點(diǎn)1. 運(yùn)籌學(xué)的研究對象運(yùn)籌學(xué)（Operations Research） Research：表明是一種研究，隱含其理性與科學(xué)性的一面； Operations：表明是針對具體運(yùn)作的，隱含其實(shí)踐與應(yīng)用性的一面。一些教科書給運(yùn)籌學(xué)下的定義： 運(yùn)籌學(xué)是一種科學(xué)決策方法； 運(yùn)籌學(xué)是依照給定目標(biāo)和條件從多方案中選擇最優(yōu)方案的最優(yōu)化技術(shù)； 運(yùn)籌學(xué)是一門尋求在給定資源條件下，如何設(shè)計(jì)和運(yùn)行一個(gè)系統(tǒng)的科學(xué)決策方法” 運(yùn)籌學(xué)與事理科學(xué)ü 科學(xué)知識(shí)的兩大類：自然科學(xué)與社會(huì)科學(xué)。 研究一般“事物”的科學(xué)稱為哲學(xué) 研究“

7、物”的科學(xué)稱為“物”理科學(xué) 研究“事”的科學(xué)稱為“事”理科學(xué) ü 運(yùn)籌學(xué)與其它自然科學(xué)明顯的區(qū)別在于它研究的對象是“事”而不是“物”。它揭示的是辦事的內(nèi)在規(guī)律，研究的是如何把事辦好。因此也有人稱運(yùn)籌學(xué)為事理科學(xué)。 ü 運(yùn)籌學(xué)與其它自然科學(xué)明顯的區(qū)別在于它研究的對象是“事”而不是“物”。它揭示的是辦事的內(nèi)在規(guī)律，研究的是如何把事辦好。因此也有人稱運(yùn)籌學(xué)為事理科學(xué)。 ü 物是看得見、摸得著的實(shí)實(shí)在在的東西，如石頭，金屬，有生命的，無生命的，自然界中的一切，包括人； ü 事是指有人參與的活動(dòng)過程，這種過程是一種客觀存在，但是看不見、摸不著。 ü 物有

8、明顯的規(guī)律性，比較容易認(rèn)識(shí)，大量關(guān)于物的科學(xué)構(gòu)成了自然科學(xué)的主體； ü 事有明顯的權(quán)變性，不同的人辦事可能得到不同的結(jié)果，長期以來人們認(rèn)為如何辦事屬于經(jīng)驗(yàn)和藝術(shù)的范疇，不存在普遍規(guī)律性。ü 關(guān)于物的知識(shí)是硬的，科學(xué)的，可以形式化、定量化地加以描述和講授； ü 關(guān)于事的知識(shí)是軟的，非科學(xué)的，難以形式化、定量化地加以描述，只可意會(huì)而不可言傳。 ü 事理科學(xué)的存在性 在科學(xué)不發(fā)達(dá)的過去，事的復(fù)雜性并不突出，辦事完全可以憑經(jīng)驗(yàn)，沒有必要尋找如何辦事的科學(xué)； ü 工業(yè)革命之后，事變的越來越復(fù)雜，人們無法單憑經(jīng)驗(yàn)對復(fù)雜的系統(tǒng)進(jìn)行管理。 ü 運(yùn)籌學(xué)

9、方法的提煉和發(fā)展過程對現(xiàn)代科學(xué)思想的貢獻(xiàn)： 明確了事與物是一對矛盾，實(shí)踐的對象包含了物和事兩個(gè)方面。 ü 事物總有一定的規(guī)律性，事的權(quán)變性不可能取消其規(guī)律性，只是更復(fù)雜，更難被認(rèn)識(shí)。ü 事理是可以被認(rèn)識(shí)和利用的，認(rèn)識(shí)這些規(guī)律，就掌握了辦事的主動(dòng)權(quán)。 ü 運(yùn)籌學(xué)完成了對辦事內(nèi)在規(guī)律的形式化，定量化的描述，建立起可以研究、應(yīng)用和講授的理論框架。 ü 事在人為靠運(yùn)籌 物理科學(xué)回答“是什么”“為什么”等問題，揭示物質(zhì)運(yùn)動(dòng)的規(guī)律； 事理科學(xué)回答“做什么”“怎么做”等問題，探討如何辦事的規(guī)律性； 事是由人的活動(dòng)構(gòu)成的，一切事情都需要人的參與才能完成，人的主觀能動(dòng)性有

10、時(shí)起決定性的作用。2、運(yùn)籌學(xué)的研究特點(diǎn)ü 科學(xué)性 在科學(xué)理論指導(dǎo)下，通過規(guī)范化步驟進(jìn)行； ü 廣泛利用多學(xué)科知識(shí)。 ü 實(shí)踐性 以實(shí)際系統(tǒng)為研究對象，通過分析鑒別問題的性質(zhì)、系統(tǒng)目標(biāo)以及系統(tǒng)內(nèi)主要變量之間的關(guān)系； 以改進(jìn)實(shí)際系統(tǒng)運(yùn)行效率為目標(biāo)，利用數(shù)學(xué)模型對系統(tǒng)進(jìn)行優(yōu)化； 分析獲得的結(jié)果要在實(shí)踐中進(jìn)行檢驗(yàn)，并可指導(dǎo)實(shí)際系統(tǒng)的優(yōu)化運(yùn)行。ü 系統(tǒng)性 用系統(tǒng)的觀點(diǎn)來分析一個(gè)組織（或系統(tǒng)），著眼于整個(gè)系統(tǒng)而不是一個(gè)局部； 通過協(xié)調(diào)各組成部分之間的相互關(guān)系，使整個(gè)系統(tǒng)達(dá)到最優(yōu)狀態(tài)ü 綜合性 問題的綜合性：運(yùn)籌學(xué)研究涉及的系統(tǒng)問題多，規(guī)模大，結(jié)構(gòu)復(fù)雜； 知

11、識(shí)的綜合性：應(yīng)用多學(xué)科知識(shí)，因此，需要一 個(gè)由各方面專家組成的專家組共同完成，個(gè)人是不可能完成的。3、運(yùn)籌學(xué)的研究方法ü 運(yùn)籌學(xué)研究廣泛應(yīng)用現(xiàn)代科學(xué)技術(shù)知識(shí)解決實(shí)踐中提出的管理與決策問題； ü 運(yùn)籌學(xué)研究有規(guī)范的分析方法和分析步驟，提高人們對問題的把握和理解； ü 運(yùn)籌學(xué)研究借助數(shù)學(xué)模型與計(jì)算機(jī)；ü 運(yùn)籌學(xué)定義：運(yùn)籌學(xué)是一門應(yīng)用學(xué)科，它廣泛應(yīng)用現(xiàn)代科學(xué)技術(shù)知識(shí)，通過規(guī)范化的分析方法和步驟，提高人們對實(shí)際事物的把握與理解，從而發(fā)現(xiàn)需要解決的管理與決策問題，并為選擇最優(yōu)決策提供定量分析的依據(jù)。三、運(yùn)籌學(xué)研究的具體過程 ü 運(yùn)籌學(xué)研究的主要目的 -

12、發(fā)現(xiàn)問題和解決問題： ü 發(fā)現(xiàn)影響系統(tǒng)運(yùn)行效率的主要問題； ü 提出改進(jìn)現(xiàn)有系統(tǒng)的運(yùn)行效率的建議； ü 合理配置和使用系統(tǒng)內(nèi)的稀缺資源；發(fā)現(xiàn)問題和解決問題的過程：1 尋找、鑒別問題； 2 確定可能的解決方案； 3 確定方案選擇、評價(jià)的準(zhǔn)則； 4 進(jìn)行方案評價(jià)； 5 方案選擇； 6 執(zhí)行選擇的方案； 7 執(zhí)行結(jié)果的評價(jià) 利用模型解決問題的過程：ü 系統(tǒng)分析與問題描述（1，2） ü 模型建立與修改（2，3） ü 模型求解與檢驗(yàn)（4，5） ü 結(jié)果分析與實(shí)施（6，7）1、系統(tǒng)分析與問題描述提出問題，明確目標(biāo)，找出系統(tǒng)變量，弄清其變

13、化范圍、相互關(guān)系、以及對目標(biāo)的影響，分析解決問題的可行性： 技術(shù)可行性：有無現(xiàn)成方法可使用； 經(jīng)濟(jì)可行性：需要投入什么樣的資源，研究成本是多少，預(yù)期效果如何； 操作可行性：研究的人員和組織是否落實(shí)，研究能否順利進(jìn)行；2、模型建立與修改模型是對現(xiàn)實(shí)世界的抽象和映射，構(gòu)造模型時(shí)要根據(jù)一些假設(shè)對模型進(jìn)行必要的抽象和簡化。 模型構(gòu)造是一門基于經(jīng)驗(yàn)的藝術(shù)，既要有理論作指導(dǎo)，又要靠不斷的實(shí)踐來積累建模的經(jīng)驗(yàn)。 模型往往要經(jīng)過多次修改才能在允許的限度內(nèi)符合實(shí)際情況。 3、模型求解與檢驗(yàn)假設(shè)條件的合理性，模型結(jié)構(gòu)的正確性要通過求解和分析進(jìn)行檢驗(yàn)，并通過一個(gè)反饋環(huán)節(jié)退回到模型建立和修改階段，有時(shí)甚至還需要退回到

14、系統(tǒng)分析階段。 4、結(jié)果分析與實(shí)施運(yùn)籌學(xué)研究的最終目的是要提高被研究系統(tǒng)的運(yùn)行效率。不應(yīng)把運(yùn)籌學(xué)研究的結(jié)果理解為僅是一組最優(yōu)解，它包括了獲得這些結(jié)果的方法、步驟、以及與之相關(guān)的管理理論。 運(yùn)籌學(xué)分析人員要與管理人員對問題取得共識(shí)，使管理人員了解分析過程，掌握分析方法，能獨(dú)立完成分析，以保證研究成果的實(shí)施。 模型的分類： - 按呈現(xiàn)和表達(dá)的方式分類： 實(shí)物模型：如建筑模型，飛機(jī)模型等; 符號模型：用數(shù)學(xué)符號表示的寫在記錄介質(zhì)上的模型，如 P = 10 x 計(jì)算機(jī)模型：可執(zhí)行的由計(jì)算機(jī)語言表達(dá)的程序。 - 按描述方法分類： 描述型模型：描述實(shí)際發(fā)生的具體過程而不探討過程背后的原因，如統(tǒng)計(jì)模型、模擬

15、模型和排隊(duì)模型； 規(guī)范化模型：使用規(guī)范的方法，對影響系統(tǒng)的內(nèi)在規(guī)律進(jìn)行探索，大部分優(yōu)化模型屬于這類模型； 啟發(fā)式模型：經(jīng)驗(yàn)?zāi)Ｐ?，主要由直觀的經(jīng)驗(yàn)和規(guī)則構(gòu)成。 - 按變量和參數(shù)的性質(zhì)分類： 確定型模型：參數(shù)和變量是確定的，如線性規(guī)劃、整數(shù)規(guī)劃和網(wǎng)絡(luò)模型； 隨機(jī)型模型：參數(shù)和變量是隨機(jī)的，如排隊(duì)模型、決策模型和對策模型。 - 按時(shí)間因素分類： 靜態(tài)模型：反映某一固定時(shí)點(diǎn)的狀態(tài)，變量、參數(shù)與時(shí)間無關(guān)； 動(dòng)態(tài)模型：反映一段時(shí)間內(nèi)系統(tǒng)變化狀態(tài)，變量、參數(shù)與時(shí)間有關(guān)。四、學(xué)習(xí)運(yùn)籌學(xué)的目的1、掌握運(yùn)籌學(xué)的基本分析方法ü 分析方法：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、網(wǎng)絡(luò)規(guī)劃、動(dòng)態(tài)規(guī)劃、決策理論、對策論

16、等 ü 分析方法論：實(shí)踐的觀點(diǎn)、系統(tǒng)觀點(diǎn)、優(yōu)化觀點(diǎn)2、提高運(yùn)用運(yùn)籌學(xué)方法解決實(shí)際問題的能力ü 能運(yùn)用運(yùn)籌學(xué)基本分析步驟分析實(shí)際問題； ü 掌握一般類型的運(yùn)籌學(xué)模型的構(gòu)模技巧； ü 能運(yùn)用計(jì)算機(jī)工具解決簡單的管理問題；緒言運(yùn)籌學(xué)(operations research)是近40年來發(fā)展起來的新興學(xué)科，盡管古樸的運(yùn)籌學(xué)思想可以追溯到幾百年甚至上千年以前，世界上公認(rèn)的運(yùn)籌學(xué)的起源是第二次世界大戰(zhàn)期間，英、美等國的軍事部門為戰(zhàn)爭需要而成立的一些研究小組的研究活動(dòng)。最初，人們稱這類研究為“運(yùn)作研究”(operational research)，或“運(yùn)作分析”(op

17、erational analysis)。這些研究的最主要的特點(diǎn)是集中一批跨多種學(xué)科領(lǐng)域的科學(xué)研究人員，有組織地對一特定問題進(jìn)行全面、系統(tǒng)的分析，提出提高某武器系統(tǒng)效率的操作方法和執(zhí)行策略。比較成功的研究案例有：英國防空部門對如何布置防空雷達(dá)，建立最有效的空防預(yù)警系統(tǒng)進(jìn)行的研究；英、美空軍對如何提高轟炸機(jī)對德國地面目標(biāo)轟炸的命中率進(jìn)行的研究；英、美海軍在反潛作戰(zhàn)中，如何安排反潛巡邏飛機(jī)的飛行路線，如何投放深水炸彈以及如何確定深水炸彈的起爆深度等研究。這些研究大大提高了盟軍的作戰(zhàn)能力，為取得反法西斯戰(zhàn)爭的最后勝利作出了巨大的貢獻(xiàn)。第二次世界大戰(zhàn)結(jié)束后，運(yùn)籌學(xué)的研究方法在理論上得到全面的發(fā)展，線性規(guī)

18、劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)分析、整數(shù)規(guī)劃、對策論、排隊(duì)論等運(yùn)籌學(xué)的分枝得到迅速的發(fā)展和完善。運(yùn)籌學(xué)的應(yīng)用也從軍事部門迅速向經(jīng)濟(jì)和工業(yè)部門轉(zhuǎn)移，并得到越來越廣泛的重視。經(jīng)過40多年的發(fā)展，運(yùn)籌學(xué)已成為一個(gè)門類齊全、理論完善、有著廣泛應(yīng)用前景的新興的科學(xué)學(xué)科。一、什么是運(yùn)籌學(xué)什么是運(yùn)籌學(xué)，人們一直試圖給運(yùn)籌學(xué)下一個(gè)簡單明了的定義。但是事情并不那么簡單，由于運(yùn)籌學(xué)研究問題的廣泛性和復(fù)雜性，以及與相鄰學(xué)科的相似性，人們一直還沒有形成一個(gè)統(tǒng)一的運(yùn)籌學(xué)定義。以下是一些教科書給運(yùn)籌學(xué)下的一些定義：“運(yùn)籌學(xué)是一種科學(xué)決策的方法”；“運(yùn)籌學(xué)是依照給定目標(biāo)和條件從眾多方案中選擇最優(yōu)方案的最優(yōu)化技術(shù)”； “運(yùn)籌

19、學(xué)是一門尋求在給定資源條件下，如何設(shè)計(jì)和運(yùn)行一個(gè)系統(tǒng)的科學(xué)決策的方法” . . . . . .以上定義都過于簡單，不能令人滿意。運(yùn)籌學(xué)的內(nèi)涵決不僅僅是解決復(fù)雜問題的優(yōu)化技術(shù)或各種科學(xué)決策方法的組合。它實(shí)際是一種對系統(tǒng)進(jìn)行科學(xué)的定量分析，從而發(fā)現(xiàn)問題、解決問題的哲學(xué)方法論。運(yùn)籌學(xué)具有多學(xué)科交叉的特點(diǎn)，它廣泛地應(yīng)用現(xiàn)代科學(xué)技術(shù)和知識(shí)，如：數(shù)學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)、心理學(xué)、物理學(xué)、生物學(xué)、化學(xué)等，解決人們在各類實(shí)踐活動(dòng)中提出的管理問題。運(yùn)籌學(xué)通過一整套規(guī)范化的分析方法和分析步驟，提高人們對實(shí)際問題的把握與理解，并為決策者選擇最優(yōu)決策提供定量分析的依據(jù)。運(yùn)籌學(xué)與其它自然科學(xué)明顯的區(qū)別在于它研究的對象是“事

20、”而不是“物”。它揭示的是事的內(nèi)在規(guī)律，研究的是如何把事辦的更好。因此也有人稱運(yùn)籌學(xué)為“事理科學(xué)”?！笆隆笔窍鄬Α拔铩贝嬖诘模锸强吹靡?、摸得著的實(shí)實(shí)在在的東西；而事是指有人參與的活動(dòng)，是看不見、摸不著的。物的運(yùn)動(dòng)有明顯的規(guī)律性，人們比較容易認(rèn)識(shí)它，大量的關(guān)于物的科學(xué)構(gòu)成了自然科學(xué)的主體；而事有明顯的權(quán)變性，不同的人們辦相同的事可能得到不同的結(jié)果，因此，人們長期以來認(rèn)為如何辦事屬于經(jīng)驗(yàn)和藝術(shù)的范疇，不存在普遍的規(guī)律性。在20世紀(jì)之前，事的復(fù)雜性并不突出，人們也沒有必要去尋找如何辦事的科學(xué)。工業(yè)革命發(fā)生之后，事情發(fā)生了明顯的變化，由于科學(xué)技術(shù)的加速發(fā)展，使人們面臨的事物越來越復(fù)雜，人們無法再憑單

21、純的經(jīng)驗(yàn)對如此復(fù)雜的系統(tǒng)進(jìn)行管理。這些因素促使人們尋找如何辦事的科學(xué)，從而引來的新的學(xué)科 - 運(yùn)籌學(xué)的發(fā)展。人們認(rèn)識(shí)和實(shí)踐的對象包含物和事兩個(gè)方面：物是“硬件”，如企業(yè)的廠房、設(shè)備和原料，戰(zhàn)爭中的軍隊(duì)和武器；事是“軟件”，如企業(yè)的管理方法，戰(zhàn)爭中的戰(zhàn)法和戰(zhàn)略。很明顯，硬件只有在軟件的配合下才能發(fā)揮出更大的作用。物有物理，事有事理，事的權(quán)變性不可能取消它的規(guī)律性，只是它更復(fù)雜，更難被認(rèn)識(shí)而以。運(yùn)籌學(xué)的分析表明，許多看起來毫不相關(guān)的事，背后都被共同的規(guī)律支配著。一旦人們認(rèn)識(shí)這些規(guī)律之后，就掌握了如何辦事的主動(dòng)權(quán)，“事在人為靠運(yùn)籌”說的就是這個(gè)道理。運(yùn)籌學(xué)的開拓者大都是自然科學(xué)家和數(shù)學(xué)家，良好的科學(xué)

22、訓(xùn)練使他們意識(shí)到事理科學(xué)的存在，并將它們發(fā)掘出來。他們把自然科學(xué)方法應(yīng)用到對事的規(guī)律的分析上，創(chuàng)造出運(yùn)籌學(xué)的分析方法，成功地完成了對事的內(nèi)在規(guī)律的形式化，定量化的描述，建立起可以研究和應(yīng)用的理論框架。運(yùn)籌學(xué)研究的核心是將科學(xué)方法應(yīng)用到對具體事物的分析中去。從方法論上講，運(yùn)籌學(xué)和一些相鄰學(xué)科有著密切的關(guān)系。例如，人們常常把運(yùn)籌學(xué)和管理科學(xué)聯(lián)系在一起。然而，管理科學(xué)涵蓋的領(lǐng)域要比運(yùn)籌學(xué)更寬一些。可以說，運(yùn)籌學(xué)是管理科學(xué)最重要的組成部分。再例如，運(yùn)籌學(xué)與系統(tǒng)科學(xué)、系統(tǒng)分析、工業(yè)工程等學(xué)科也有很多共同之處，但它們涉及的面要比運(yùn)籌學(xué)窄一些。運(yùn)籌學(xué)研究的特點(diǎn)可以簡單地歸納如下：1. 1. 

23、60;       科學(xué)性：運(yùn)籌學(xué)研究是建立在科學(xué)的基礎(chǔ)上的。運(yùn)籌學(xué)研究的科學(xué)性表現(xiàn)的兩個(gè)方面：首先，它是在科學(xué)方法論的指導(dǎo)下通過一系列規(guī)范化步驟進(jìn)行的；其次，它是廣泛利用多種學(xué)科的科學(xué)技術(shù)知識(shí)進(jìn)行的研究。運(yùn)籌學(xué)研究不僅僅涉及數(shù)學(xué)，還要涉及經(jīng)濟(jì)科學(xué)、系統(tǒng)科學(xué)、工程物理科學(xué)等其它學(xué)科。2. 2.         實(shí)踐性：運(yùn)籌學(xué)是一門實(shí)踐的科學(xué)，它完全是面向應(yīng)用的。離開實(shí)踐，運(yùn)籌學(xué)就失去了存在的意義。運(yùn)籌學(xué)以實(shí)際問題為分析對象，通過鑒別問題的性質(zhì)、系統(tǒng)的目標(biāo)以

24、及系統(tǒng)內(nèi)主要變量之間的關(guān)系，利用數(shù)學(xué)方法達(dá)到對系統(tǒng)進(jìn)行優(yōu)化的目的。更為重要的是分析獲得的結(jié)果要能被實(shí)踐檢驗(yàn)，并被用來指導(dǎo)實(shí)際系統(tǒng)的運(yùn)行。3. 3.         系統(tǒng)性：運(yùn)籌學(xué)用系統(tǒng)的觀點(diǎn)來分析一個(gè)組織（或系統(tǒng)），它著眼于整個(gè)系統(tǒng)而不是一個(gè)局部，通過協(xié)調(diào)各組成部分之間的關(guān)系和利害沖突，使整個(gè)系統(tǒng)達(dá)到最優(yōu)狀態(tài)。4. 4.         綜合性：運(yùn)籌學(xué)研究是一種綜合性的研究，它要涉及問題的方方面面，應(yīng)用多學(xué)科的知識(shí)，因此，要由一個(gè)各方面

25、的專家組成的小組來完成。二、運(yùn)籌學(xué)模型許多科學(xué)研究都要利用模型，模型通常是指為特定目的建立的，反映某種客觀存在特征和特性的一種結(jié)構(gòu)。模型可以是實(shí)際模型，也可以是抽象模型。運(yùn)籌學(xué)研究的模型主要為抽象模型 - 數(shù)學(xué)模型。數(shù)學(xué)模型的基本特點(diǎn)是用一些數(shù)學(xué)關(guān)系（數(shù)學(xué)方程、邏輯關(guān)系等）來描述被研究對象的實(shí)際關(guān)系（技術(shù)關(guān)系、物理定律、外部環(huán)境等）。利用模型進(jìn)行研究有以下優(yōu)點(diǎn)：1. 1.           在建立模型的過程中，需要對被研究系統(tǒng)進(jìn)行深入細(xì)致的分析，可增加人們對系統(tǒng)的了解和把握；2. 2.

26、0;        模型可以更全面的描述一個(gè)復(fù)雜的系統(tǒng)，并揭示系統(tǒng)的一些用其它方法不可能發(fā)現(xiàn)的內(nèi)在聯(lián)系；3. 3.         利用模型，人們可以對系統(tǒng)進(jìn)行多種試驗(yàn)分析，而這種分析是不可能利用實(shí)際系統(tǒng)完成的。模型的種類是多種多樣的，分類的方法也很多，如：l l         按呈現(xiàn)和表達(dá)的方式可分為： 實(shí)物模型：規(guī)模縮小的由實(shí)物制成的模型，如建筑模型，飛機(jī)模型等

27、; 符號模型：用數(shù)學(xué)符號表示的寫在紙上或其它記錄介質(zhì)上的模型； 計(jì)算機(jī)模型：模型表現(xiàn)為可在計(jì)算機(jī)上執(zhí)行的由計(jì)算機(jī)語言表達(dá)的程序。l l         按描述方法的特點(diǎn)，模型可分為以下幾類：描述型模型：這類模型僅僅描述實(shí)際發(fā)生的具體過程而不探討過程背后的原因。許多統(tǒng)計(jì)模型、模擬模型和排隊(duì)模型都是這類描述性模型。規(guī)范化模型：這類模型使用規(guī)范的方法，對影響系統(tǒng)的內(nèi)在規(guī)律進(jìn)行探索，并詳細(xì)描述系統(tǒng)的變量、目標(biāo)和約束。大部分優(yōu)化模型屬于這類模型，也是我們主要研究的模型；啟發(fā)式模型：這類模型是一種經(jīng)驗(yàn)?zāi)Ｐ停饕梢恍┲庇^的經(jīng)

28、驗(yàn)和規(guī)則構(gòu)成。 l l           按模型變量和參數(shù)的性質(zhì)，模型可分為： 確定型模型：模型的參數(shù)和變量都是確定型的，如本書將要介紹的線性規(guī)劃、整數(shù)規(guī)劃、網(wǎng)絡(luò)規(guī)劃模型； 隨機(jī)型模型 模型的參數(shù)和變量是隨機(jī)型的，如排隊(duì)模型、決策模型和對策模型就屬于隨機(jī)模型。l l           按模型是否考慮時(shí)間因素，模型還可分為： 靜態(tài)模型：模型只反映某一固定時(shí)點(diǎn)的系統(tǒng)狀態(tài)，變量、參數(shù)與時(shí)間

29、無關(guān)； 動(dòng)態(tài)模型：模型反映一段時(shí)間內(nèi)系統(tǒng)變化的狀態(tài)，變量、參數(shù)與時(shí)間有關(guān)，如動(dòng)態(tài)規(guī)劃模型就是典型的動(dòng)態(tài)模型。 還有很多準(zhǔn)則可用來對運(yùn)籌學(xué)模型進(jìn)行分類，這里就不一一列舉了。 運(yùn)籌學(xué)模型的一個(gè)顯著的特點(diǎn)是它們大部分優(yōu)化模型。一般來說，運(yùn)籌學(xué)模型都有一個(gè)目標(biāo)函數(shù)和一系列約束條件，模型的目標(biāo)是在滿足約束條件的前提下使目標(biāo)函數(shù)最大化或最小化。三、運(yùn)籌學(xué)分析的主要步驟運(yùn)籌學(xué)的分析步驟一般包括：發(fā)現(xiàn)和定義待研究的問題；構(gòu)造數(shù)學(xué)模型；尋找經(jīng)過模型優(yōu)化的結(jié)果，并通過應(yīng)用這些結(jié)果來改善系統(tǒng)的運(yùn)行效率。具體步驟如圖I所示。圖I 運(yùn)籌學(xué)研究的基本步驟 1.系統(tǒng)分析和問題描述運(yùn)籌學(xué)分析的第一步是分析問題和提出

30、問題，它是從對現(xiàn)有系統(tǒng)的詳細(xì)分析開始的，通過分析找到影響系統(tǒng)的最主要的問題。另外，通過分析，還要明確系統(tǒng)或組織的主要目標(biāo)，找出系統(tǒng)的主要變量和參數(shù)，弄清它們的變化范圍、相互關(guān)系、以及對目標(biāo)的影響。問題提出后，還要分析解決該問題的可能性和可行性。一般需要進(jìn)行以下分析：(1) 技術(shù)可行性 - 有沒有現(xiàn)成的運(yùn)籌學(xué)方法可以用來解決存在的問題；(2) 經(jīng)濟(jì)可行性 - 研究的成本是多少，需要投入什么樣的資源，預(yù)期效果如何；(3) 操作可行性 - 研究的人員和組織是否落實(shí)，各方面的配合如何，研究能否順利進(jìn)行；通過以上分析，可對研究的困難程度，可能發(fā)生的成本，可能獲得的成功和收益做到心中有數(shù)，使研究的目的更加

31、明確。2. 模型的建立和修改模型建立是運(yùn)籌學(xué)分析的關(guān)鍵步驟。運(yùn)籌學(xué)模型一般是數(shù)學(xué)模型或模擬模型，并以數(shù)學(xué)模型為主。模型是對現(xiàn)實(shí)世界的一種抽象和映射。由于實(shí)際問題的復(fù)雜性，模型不可能完全準(zhǔn)確的反映現(xiàn)實(shí)世界或?qū)嶋H問題，人們在構(gòu)造模型時(shí)，往往要根據(jù)一些理論的假設(shè)或設(shè)立一些前提條件來對模型進(jìn)行必要的抽象和簡化。人們對問題的理解不同，根據(jù)的理論不同，設(shè)立的前提條件不同，構(gòu)造的模型也會(huì)不同。因此，模型構(gòu)造是一門基于經(jīng)驗(yàn)的藝術(shù)，既要有理論作指導(dǎo)，又要靠不斷的實(shí)踐來積累建模的經(jīng)驗(yàn)。模型建立不是一個(gè)一次性的過程，由于實(shí)際問題與人們對它的認(rèn)識(shí)之間存在的差異，模型往往要經(jīng)過多次修改才能在允許的限度內(nèi)符合實(shí)際情況。一

32、個(gè)典型的模型包括以下組成部分：(1)一組需要通過求解模型確定的決策變量；(2)一個(gè)反映決策目標(biāo)的目標(biāo)函數(shù)；(3)一組反映系統(tǒng)復(fù)雜邏輯和約束關(guān)系的約束方程；(4)模型要使用的各種參數(shù)。簡單的模型可以用一般的數(shù)學(xué)公式表示，復(fù)雜的模型由于必須借助于計(jì)算機(jī)求解，還必須表達(dá)為相應(yīng)的計(jì)算機(jī)程序。3. 模型的求解和檢驗(yàn)?zāi)Ｐ徒ǔ芍?，它所依賴的理論和假設(shè)條件的合理性，以及模型結(jié)構(gòu)的正確性都要通過試驗(yàn)進(jìn)行檢驗(yàn)。通過對模型的試驗(yàn)求解，人們可以發(fā)現(xiàn)模型的結(jié)構(gòu)和邏輯錯(cuò)誤，并通過一個(gè)反饋環(huán)節(jié)退回到模型建立和修改階段，有時(shí)甚至還需要退回到系統(tǒng)分析階段。模型結(jié)構(gòu)和邏輯上的問題解決之后，通過收集數(shù)據(jù)、數(shù)據(jù)處理、模型生成、模型

33、求解等過程得到了模型的最優(yōu)解。值得強(qiáng)調(diào)的是，由于模型和實(shí)際之間存在的差異，模型的最優(yōu)解并不一定是真實(shí)問題的最優(yōu)解。只有模型相當(dāng)準(zhǔn)確地反映實(shí)際問題時(shí)，該解才是實(shí)際最優(yōu)解的一個(gè)很好的近似。4. 結(jié)果分析與實(shí)施運(yùn)籌學(xué)分析的最后一步是獲取分析的結(jié)果并將之付諸實(shí)施。運(yùn)籌學(xué)研究的最終目的是要提高被研究系統(tǒng)的效率，因此，這一步也是最重要的一步。絕不能把運(yùn)籌學(xué)分析的結(jié)果理解為僅僅是一個(gè)或一組最優(yōu)解，它也包括了獲得這些解的方法和步驟，以及支持這些結(jié)果的管理理論和方法。通過分析，要使管理人員與運(yùn)籌學(xué)分析人員對問題取得共識(shí)，并使管理人員了解分析的全過程，掌握分析的方法和理論，并能獨(dú)立完成日常的分析工作，這樣才能保證

34、研究分析成果的真正實(shí)施。四、本教材的結(jié)構(gòu)本教材是參考“試辦工商管理碩士學(xué)位協(xié)作小組”發(fā)布的工商管理碩士教學(xué)大綱編寫的。在討論運(yùn)籌學(xué)的基本理論和方法的同時(shí)，本教材還安排了大量的應(yīng)用例題，每一章的結(jié)尾都安排了必要的習(xí)題。第一章 線性規(guī)劃與單純形方法根據(jù)統(tǒng)計(jì)，應(yīng)用最廣泛的運(yùn)籌學(xué)學(xué)方法為： 數(shù)學(xué)規(guī)劃（線性規(guī)劃，整數(shù)規(guī)劃） 模擬 網(wǎng)絡(luò)模型（包括PERT/CPM） 決策分析 排隊(duì)理論 庫存模型最基本的運(yùn)籌學(xué)方法：網(wǎng)絡(luò)規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的； 解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大； 線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一。自從1947年G.B.

35、Dantzig發(fā)明了求解線性規(guī)劃的單純形方法后，線性規(guī)劃已被廣泛地應(yīng)用于解決經(jīng)濟(jì)管理和工業(yè)生產(chǎn)中遇到的實(shí)際問題。曾經(jīng)有人進(jìn)行過調(diào)查，在世界500家最大的企業(yè)中，有85的企業(yè)使用過線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使用已為使用者節(jié)約了數(shù)以億萬計(jì)的資金。線性規(guī)劃實(shí)質(zhì)上是解決稀缺資源在有競爭的使用方向中如何進(jìn)行最優(yōu)分配的問題。這類最優(yōu)分配問題大部分是從經(jīng)營管理中引出的，例如：產(chǎn)品的最優(yōu)組合，生產(chǎn)排序，最優(yōu)投資方案，人力資源分配等。在這類問題中，一個(gè)共性的問題是一些稀缺或有限的資源必須被分配到一些指定的生產(chǎn)活動(dòng)中去，而這些資源的使用會(huì)伴隨著費(fèi)用或效益的發(fā)生。線性規(guī)劃可用于合理分配這些資源

36、，并使付出的費(fèi)用最小或獲得的收益最大。在本章中我們將首先介紹什么是線性規(guī)劃問題，線性規(guī)劃問題的數(shù)學(xué)表達(dá)式，簡單線性規(guī)劃問題的圖解法等線性規(guī)劃的基本概念，然后介紹線性規(guī)劃的基本理論和求解線性規(guī)劃的單純形方法。1.1 線性規(guī)劃的基本概念本小節(jié)介紹什么是線性規(guī)劃問題，如何將實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型，線性規(guī)劃問題的標(biāo)準(zhǔn)形式以及求解簡單線性規(guī)劃問題的圖解法。1.1.1 線性規(guī)劃模型用線性規(guī)劃方法解決實(shí)際問題的第一步是要將實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型。下面通過例子說明如何把具體問題轉(zhuǎn)化為線性規(guī)劃模型。ü 線性規(guī)劃是求一個(gè)線性函數(shù)在滿足一組線性等式或不等式方程條件下極值的數(shù)學(xué)問題的統(tǒng)稱。 

37、2; 線性規(guī)劃模型由三部分組成： 1一個(gè)反映決策目標(biāo)的目標(biāo)函數(shù)； 2一組線性等式、不等式約束方程； 3限制決策變量取值范圍的非負(fù)約束 一、線性規(guī)劃模型舉例例1.1 生產(chǎn)計(jì)劃問題勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元。椅子售價(jià)30元，生產(chǎn)桌子和椅子需要木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠每月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大。解：將一個(gè)實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟：1.      

38、60;  確定決策變量：決策變量是模型要決定的未知量，也是模型最重要的參數(shù)。對簡單的模型，如上例，決策變量是顯而易見的。但對較復(fù)雜的問題，決策變量的定義就不那么簡單了。在本例中，家具廠要確定柜子和桌子的生產(chǎn)數(shù)量，因此可定義：x1 = 生產(chǎn)桌子的數(shù)量，x2 = 生產(chǎn)椅子的數(shù)量。2.         確定目標(biāo)函數(shù)：目標(biāo)函數(shù)決定線性規(guī)劃問題的優(yōu)化方向，是線性規(guī)劃模型的重要組成部分。很明顯，家具廠的目標(biāo)是使銷售收入最大，更具體一點(diǎn)，是使兩種產(chǎn)品售價(jià)與產(chǎn)量的乘積的總和最大，因此目標(biāo)函數(shù)可寫為： max: z = 5

39、0x1 + 30x23.         確定約束方程：如果家具廠可以隨意選擇生產(chǎn)桌子和椅子的數(shù)量，他們的銷售收入可以隨意大。而這實(shí)際是不可能的，因?yàn)槿魏紊a(chǎn)都會(huì)受到種種客觀條件的限制。一個(gè)正確的模型應(yīng)通過約束方程來反映這些客觀條件。本例中的限制條件是每月可用的木工和油漆工的工時(shí)不能超過120和50小時(shí)。這兩個(gè)條件可由以下方程表示： 4x1 + 3x2£120 2x1 + x2£504. 變量取值限制：一般情況下，決策變量只取正值（非負(fù)值）。因此，模型中應(yīng)有變量的非負(fù)約束。在本例中，非負(fù)約束為x

40、1 0，x2 0。將以上幾部分結(jié)合起來就得到反映家具廠經(jīng)營活動(dòng)的完整的數(shù)學(xué)模型： max: z = 50x1 + 30x2 s.t. 4x1 + 3x2 £120(1.1)2x1 + x2 £50 x1, x2 ³ 0例1.2 營養(yǎng)配餐問題假定一個(gè)成年人每天需要從食物中獲取3000大卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每公斤所含熱量和營養(yǎng)成分以及市場價(jià)格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小。表1.1 各種食物的營養(yǎng)成分表序號食品名稱熱量(大卡)蛋白質(zhì)(g)鈣(mg)價(jià)格(元)1豬肉1000504001

41、42雞蛋8006020063大米10002030034白菜200105002解：設(shè)xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型如下：min: z = 14x1 + 6x2 + 3x3 + 2x4s.t. 1000x1 + 800x2 + 900x3 + 200x4 ³ 3000 50 x1 + 60 x2 + 20x3 + 10x4 ³ 55(1.2) 400 x1 + 200x2 + 300x3 + 500x4 ³ 800 xi ³ 0 i =1, ., 4實(shí)用的配餐問題要比上例復(fù)雜的多，可包括幾十甚至上百種原料，幾十種營養(yǎng)配方。例如醫(yī)院的營

42、養(yǎng)配餐和養(yǎng)殖業(yè)中的配合飼料問題。二、線性規(guī)劃的一般形式 由以上兩個(gè)例子可知，線性規(guī)劃是求一個(gè)線性函數(shù)在滿足一組線性等式或不等式方程條件下極值的數(shù)學(xué)問題的統(tǒng)稱。線性規(guī)劃問題（或稱線性規(guī)劃模型）一般由三部分組成：1 由決策變量構(gòu)成的反映決策者目標(biāo)的線性目標(biāo)函數(shù)；2 一組由決策變量的線性等式或不等式構(gòu)成的約束方程；以及3 限制決策變量取值范圍的非負(fù)約束。線性規(guī)劃問題的一般形式可以寫為：max: z = c1x1 + c2 x2 + + cnxns.t. a11x1 + a12 x2 + + a1nxn £ b1 a21x1 + a22 x2 + + a2nxn £ b2(1.3)

43、 am1x1 + am2 x2 + + amnxn £ bm x1, x2, xn 0ü x1, ., xn為決策變量，表示第 n 種生產(chǎn)經(jīng)營活動(dòng)的規(guī)模， ü z = c1x1+×××+cnxn 稱為目標(biāo)函數(shù)，反映生產(chǎn)活動(dòng)的目標(biāo)。cj (j = 1, 2, ., n) 為目標(biāo)函數(shù)系數(shù)（又稱價(jià)值系數(shù)）。表示與活動(dòng)相關(guān)的費(fèi)用或收益。 ü ai1x1+ai2x2+ainxn £ bi 為使用第 i種資源的資源限制約束；(1.3) 中的x1, x2, , xn為決策變量，一般可解釋為反映n種生產(chǎn)經(jīng)營活動(dòng)的規(guī)模，例如，一個(gè)工

44、廠生產(chǎn)的n種產(chǎn)品的產(chǎn)量。z = c1x1 + c2x2+ ××× + cnxn被稱為目標(biāo)函數(shù)，記為z = f(x)，反映生產(chǎn)活動(dòng)追求的目標(biāo)。目標(biāo)函數(shù)中的cj 稱為目標(biāo)函數(shù)系數(shù)，也稱價(jià)值系數(shù)，代表伴隨決策變量發(fā)生的單位費(fèi)用和效益。模型(1.3)的每一個(gè)約束是一種資源約束，模型共有m中稀缺或受限制的資源，列向量b = (b1 ,.,bm )T 稱為約束條件的右邊項(xiàng)，它代表m種資源的可用量。aij 為技術(shù)系數(shù)或投入產(chǎn)出系數(shù)，代表第j種經(jīng)營活動(dòng)需要第i種資源的單位投入或產(chǎn)出量，這些系數(shù)構(gòu)成一個(gè)矩陣。和右邊項(xiàng)一起構(gòu)成線性規(guī)劃模型的約束條件。xj ³0 限制決策變量

45、的取值范圍，是決策變量的非負(fù)約束，它表達(dá)了生產(chǎn)經(jīng)營活動(dòng)的規(guī)模不能為負(fù)值這樣一個(gè)事實(shí)。三、線性規(guī)劃隱含的假定 線性規(guī)劃要求目標(biāo)函數(shù)和約束方程必須是線性函數(shù)隱含了如下假定：1 比例性假定: 決策變量變化引起的目標(biāo)函數(shù)的改變量和決策變量的改變量成比例每個(gè)決策變量的變化引起約束方程左端值的改變量和該變量的改變量成比例。比例性假定意味著每種經(jīng)營活動(dòng)對目標(biāo)函數(shù)的貢獻(xiàn)是一個(gè)常數(shù)，對資源的消耗也是一個(gè)常數(shù)。2 可加性假定: 每個(gè)決策變量對目標(biāo)函數(shù)和約束方程的影響是獨(dú)立于其他變量的，目標(biāo)函數(shù)值是每個(gè)決策變量對目標(biāo)函數(shù)貢獻(xiàn)的總和。3 連續(xù)性假定: 線性規(guī)劃問題中的決策變量應(yīng)取連續(xù)值。4 確定性假定: 線性規(guī)劃中的

46、所有參數(shù)都是確定的參數(shù)。線性規(guī)劃問題是確定性問題，不包含隨機(jī)因素。上述隱含的假定條件是很強(qiáng)的，在現(xiàn)實(shí)生活中，完全滿足這些條件的例子并不多見。因此在使用線性規(guī)劃時(shí)必須注意你的問題在什么程度上滿足這些假定。如果不滿足，不滿足的程度有多大。當(dāng)不滿足的程度較大時(shí)，應(yīng)考慮使用其它方法，如：非線性規(guī)劃、整數(shù)規(guī)劃或不確定性分析方法。1.1.2 線性規(guī)劃的標(biāo)準(zhǔn)型和矩陣表達(dá)式一、線性規(guī)劃的標(biāo)準(zhǔn)型從以上例子可知線性規(guī)劃形式的多樣性。目標(biāo)函數(shù)可求最大化也可求最小化；約束類型可以是³，£或=；變量限制既可非負(fù)，也可非正或無限制。為統(tǒng)一起見，人們?yōu)榫€性規(guī)劃規(guī)定了標(biāo)準(zhǔn)形式。線性規(guī)劃的標(biāo)準(zhǔn)型規(guī)定如下：m

47、ax: z = c1x1 + c2 x2 + + cnxns.t. a11x1 + a12 x2 + + a1nxn = b1 a21x1 + a22 x2 + + a2nxn = b2(1.4) am1x1 + am2 x2 + + amnxn = bm x1, x2, xn 0線性規(guī)劃的標(biāo)準(zhǔn)型要求所有的約束必須為等式約束，所有的變量為非負(fù)變量，對目標(biāo)函數(shù)的類型原則上沒有硬性規(guī)定，求最大化和最小化都可以。但是為了后面討論方便，在本教材中規(guī)定目標(biāo)函數(shù)最大化為標(biāo)準(zhǔn)型。 二、如何將線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)型任何一個(gè)非標(biāo)準(zhǔn)的線性規(guī)劃問題都可通過適當(dāng)變化而轉(zhuǎn)為標(biāo)準(zhǔn)形式。以下列出各種轉(zhuǎn)化的方法：

48、1.    將最小化的目標(biāo)函數(shù)轉(zhuǎn)化最大化的目標(biāo)函數(shù)：求一個(gè)函數(shù)的最小值等價(jià)于求該負(fù)函數(shù)的最大值，即：min f(x) = - max-f(x)。因此只需改變目標(biāo)函數(shù)的符號就可以在最大和最小之間轉(zhuǎn)換。2.    把不等式約束轉(zhuǎn)化為等式約束：可在約束中加入松弛變量或剩余變量。例如，把小于等于約束 x1+ x2 £ 10 化為標(biāo)準(zhǔn)約束，需引入一松弛變量xs ³ 0，標(biāo)準(zhǔn)約束即可寫為 x1 + x2 + xs = 10 。將大于等于約束 x1 + x2 ³ 0化為標(biāo)準(zhǔn)形式，可引入一剩余變量xs

49、 ³0，約束可改寫為 x1 + x2 xs = 0。3.     變量取值限制約束的轉(zhuǎn)化：變量取值限制約束也可做相應(yīng)的變化：變量的非正約束xi £ 0 可通過變量代換改為非負(fù)約束，即令 yi = -xi ，代入原模型后，新變量yi 即為非負(fù)變量。如果變量xi 是自由變量，則可做變量代換：xi = ui vi，ui ³ 0,vi ³ 0，代入原模型后，自由變量xi 被兩個(gè)非負(fù)變量ui 和vi 取代。例1.3 將下列線性規(guī)劃模型轉(zhuǎn)變?yōu)闃?biāo)準(zhǔn)形式：min: 3x1- x2 + 4x3s.t. x1 - 2x2 +

50、 5x3 ³ 0 2x1 + x2 - 3x3 £ 0 3x1 - 5x2 = 0 x1 ³ 0, x2 £ 0解：令x2= -y，x3 = u - v，并引入松弛變量s1和s2，標(biāo)準(zhǔn)型為：max: -3x1 - y - 4u + 4vs.t. x1 + 2y + 5u - 5v - s1 = 0 2x1 - y - 3u + 3v + s2 = 0 3x1 + 5y = 0 x1³0, y³0, u³0, v³0, s1³0, s2³0  三 線性規(guī)劃的向量和矩陣表達(dá)形式 為理論討論

51、方便，線性規(guī)劃還經(jīng)常用向量和矩陣形式表示。例如，(1.4)可寫為向量式：(1.5) xj ³ 0j=1,2, ., n式中：pj = (a1j,.,amj )，b =(b1,.,bm)，還可寫成更簡潔的矩陣形式：max: cxs.t. Ax = b(1.6) x ³ 0式中：c = (c1, ., cn)，x = (x1, ., xn)T，矩陣A = (aij)m´n是約束系數(shù)矩陣，其他參數(shù)定義同前。1.1.3 線性規(guī)劃的圖解法ü 可行域：由約束平面圍起來的凸多邊形區(qū)域，可行域內(nèi)的每一個(gè)點(diǎn)代表一 個(gè)可行解。 ü 最優(yōu)解：總是在可行域的邊界上，一

52、般由可行域的極點(diǎn)表示。 ü 有效與無效(緊與松)約束：與最優(yōu)解相關(guān)的約束為有效(緊)約束。ü 如果可行域?yàn)榭占€性規(guī)劃 問題無可行解； ü 如果目標(biāo)函數(shù)線可以無限制地在可行域內(nèi)向改善的方向移動(dòng)，線性規(guī)劃問題無界； ü 線性規(guī)劃問題可能存在無窮多個(gè)最優(yōu)解。簡單的線性規(guī)劃問題可用圖解法求解。圖解法具有簡單、直觀、便于初學(xué)者了解線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。現(xiàn)用圖解法求解例1.1。由于例1.1只有兩個(gè)變量，我們可以在平面直角坐標(biāo)系中描述該問題(見圖1.1)。  圖1.1 例1.1問題的圖解  例1.1的每個(gè)不等式約束代表一個(gè)半平面（等

53、式約束代表一直線）。例如第一個(gè)約束在圖形上表示以直線 4x1 + 3x2 = 120 為界的左下方的半平面。該半平面內(nèi)所有的點(diǎn)都滿足第一個(gè)約束條件。兩個(gè)非負(fù)條件分別表示以兩個(gè)坐標(biāo)軸為界的正半平面的交集，也即直角坐標(biāo)系的第一象限。這四個(gè)半平面構(gòu)成一個(gè)封閉的多邊形。該多邊形內(nèi)的任一點(diǎn)以及邊界上的點(diǎn)都能同時(shí)滿足(1.2)的所有約束條件，因此都是(1.2)的可行解。線性規(guī)劃所有可行解構(gòu)成的集合稱為線性規(guī)劃的可行域。實(shí)際上，例1.1的線性規(guī)劃模型有無數(shù)多可行解，哪一個(gè)解是最優(yōu)解呢？這取決于目標(biāo)函數(shù)的圖形。目標(biāo)函數(shù) z = 50x1 + 30x2 在平面坐標(biāo)系中的圖形是一族以z為參數(shù)的平行線。任選一個(gè)z，

54、便可得到一條直線，該線上所有的可行點(diǎn)都有相同的目標(biāo)函數(shù)值，因此也被稱為等值線。讓目標(biāo)函數(shù)線沿其法線方向平行移動(dòng)，目標(biāo)函數(shù)值將逐漸增加，當(dāng)移到A點(diǎn)后，再向外移就會(huì)脫離可行區(qū)域，點(diǎn)A所代表的解即為最優(yōu)解。本例的最優(yōu)解值為x1 =15，x2 =20，即家具廠每周生產(chǎn)15個(gè)桌子和20個(gè)椅子時(shí)銷售收入最大，銷售收入z50(15)30(20)1350?？偨Y(jié)一下，圖解法可歸納為以下幾個(gè)步驟：1.畫直角坐標(biāo)系。2.依次做每條約束線，標(biāo)出可行域的方向并找出可行域。3.任取一目標(biāo)函數(shù)值做一條目標(biāo)函數(shù)線，然后根據(jù)目標(biāo)的類型平移該線直到該線即將離開可行域?yàn)橹?。與目標(biāo)函數(shù)線接觸的最后的點(diǎn)即代表一個(gè)最優(yōu)解。1.2 線性規(guī)

55、劃應(yīng)用舉例如何將一個(gè)復(fù)雜的實(shí)際問題轉(zhuǎn)化為一個(gè)合理的線性規(guī)劃模型既是一門科學(xué)，又是一門藝術(shù)。僅僅了解求解線性規(guī)劃的數(shù)學(xué)原理是不夠的，還需要在實(shí)踐中學(xué)習(xí)將實(shí)際問題抽象為數(shù)學(xué)模型的技巧，不斷總結(jié)和提高構(gòu)造模型的技術(shù)，才能真正將線性規(guī)劃技術(shù)應(yīng)用到實(shí)際中。下面再舉幾個(gè)比較典型的線性規(guī)劃問題。1.2.1 調(diào)和問題調(diào)和問題是研究將若干種不同的原料按一定的技術(shù)要求調(diào)和成不同的產(chǎn)品，例如化工、塑料、冶煉、石油加工都會(huì)遇到調(diào)和問題。典型的調(diào)和問題包含了具有不同技術(shù)特性的原料和產(chǎn)品并有相應(yīng)的成本和價(jià)格與之相關(guān)。調(diào)和問題的目標(biāo)是在滿足產(chǎn)品需求和調(diào)和指標(biāo)的前提下使調(diào)和成本最小或生產(chǎn)收益最大。例1.4 新星煉油廠生產(chǎn)三種

56、牌號的汽油：70#,80#和85#汽油。每種汽油有不同的辛烷值和含硫量的質(zhì)量要求并由三種原料油調(diào)和而成。每種原料也有不同的質(zhì)量指標(biāo)。每種原料每日可用數(shù)量、質(zhì)量指標(biāo)和生產(chǎn)成本見表1.2，每種汽油的質(zhì)量要求和銷售價(jià)格見表1.3。問該煉油廠如何安排生產(chǎn)才能使其利潤最大？假定在調(diào)和中辛烷值和含硫量指標(biāo)都符合線性相加關(guān)系。表1.2 汽油組分的質(zhì)量和成本數(shù)據(jù)序號i原料辛烷值含硫量%成本(元/噸)可用量(噸/日)1直餾汽油621.560020002催化汽油780.890010003重整汽油900.21400500 表1.3 汽油產(chǎn)品的質(zhì)量和價(jià)格數(shù)據(jù)序號j產(chǎn)品辛烷值含硫量銷售價(jià)(元/噸)170# 汽

57、油³70£1900280# 汽油³80£11200385# 汽油³85£0.61500 這個(gè)問題要比前兩個(gè)問題要復(fù)雜一些。首先決策變量的選擇就不很直觀。如果定義決策變量為各種汽油的產(chǎn)量，在寫模型時(shí)會(huì)遇到不少麻煩。正確的方法是定義決策變量xij 代表第i 種原料調(diào)入第j 種成品汽油的數(shù)量。令pj 代表第j 種產(chǎn)品的銷售價(jià)格，ci 為第i 種原料的生產(chǎn)成本，ei 和ej 分別為原料和產(chǎn)品的辛烷值，hi 和hj 為分別為原料和產(chǎn)品的含硫量，si 為原料每日的可用量，則模型可寫為：(1.7)模型(1.7)目標(biāo)函數(shù)的意義很清楚：調(diào)入j

58、 種產(chǎn)品的i 種原料的產(chǎn)品售價(jià)與原料成本之差(pj ci )即為調(diào)和組分xij 對目標(biāo)函數(shù)（利潤）的貢獻(xiàn)。前兩個(gè)約束方程分別是辛烷值和含硫量的質(zhì)量約束，每種產(chǎn)品都有兩個(gè)質(zhì)量約束。我們僅舉70#汽油的辛烷值含量為例來說明這些約束的寫法。該約束可寫為：62x11 + 78x21 + 90x31 ³ 70(x11 + x21 + x31 )(1.8)不等式(1.8)左邊是調(diào)入70汽油不同組分油辛烷值含量的總和，右端則為70汽油質(zhì)量要求的最低標(biāo)準(zhǔn)，x11 + x21 + x31代表70汽油的實(shí)際產(chǎn)量，整理后可得：(62 - 70)x11 + (78 - 70)x21 + (90 - 70)x

59、31 ³ 0(1.9)式(1.9)與(1.7)的形式一樣。最后一組約束表示所用原料不能超過原料可用量的限制。將數(shù)據(jù)代入并化簡后的模型如下：max: 300x11+600x12+900x13+300x22+600x23+500x31+200x32+100x33s.t. 8x11 + 8x21 + 20x31 ³ 0 18x12 + 2x22 + 10x32 ³ 0 23x13 + 7x23 + 5 x33 ³ 0 0.5x11 + 0.2x21 + 0.8x31 £ 0 0.5x12 + 0.2x22 + 0.8x32 £ 0 0.9x13 + 0.2x23 + 0.4x33 £ 0 x11 + x12 + x13 £ 2000 x21 + x22 + x23 £ 1000 x31 + x32 + x33