1、1第三部分第三部分運籌學運籌學第四章第四章運籌學建模運籌學建模4.1運籌學概述運籌學概述運籌學是用數(shù)學方法研究各種系統(tǒng)最優(yōu)化問題的學科。其研究方法是應用數(shù)學語言來描述實際系統(tǒng)，建立相應的數(shù)學模型，并對模型進行研究和分析，據(jù)此求得模型的最優(yōu)解；其目的是制定合理運用人力、物力和財力的最優(yōu)方案；為決策者提供科學決策的依據(jù)；其研究對象是各種社會系統(tǒng)，可以是對新的系統(tǒng)進行優(yōu)化設計，也可以是研究已有系統(tǒng)的最佳運營問題。因此，運籌學既是應用數(shù)學，也是

2、管理科學，同時也是系統(tǒng)工程的基礎之一。運籌學一詞最早出現(xiàn)于第二次世界大戰(zhàn)期間，當時為了急待解決作戰(zhàn)中所遇到的許多錯綜復雜的戰(zhàn)略戰(zhàn)術(shù)問題，英美一些具有不同學科和背景的科學家，組成了許多研究小組，專門從事軍事行動的優(yōu)化研究。研究的典型課題有：高射炮陣地火力的最佳配置、護航艦隊規(guī)模的大小以及開展反潛艇作戰(zhàn)的偵察等方面。由于受到戰(zhàn)時壓力的推動，加上不同學科互相滲透而產(chǎn)生的協(xié)同作用，在上述幾個方面的研究都卓有成效，為第二次世界大戰(zhàn)盟軍的勝利起到積

3、極作用，也為運籌學各個分支的進一步研究打下了基礎。戰(zhàn)后，這些科學家們轉(zhuǎn)向研究在民用部門應用類似方法的可能性。因而，促進了在民用部門中應用運籌學有關(guān)方法的研究和實踐。1947年，美國數(shù)學家GBDantzig提出了求解線性規(guī)劃的有效方法——單純形法。50年代初，應用電子計算機求解線性規(guī)劃問題獲得了成功。50年代末，工業(yè)先進國家的一些大型企業(yè)也陸續(xù)應用了運籌學的方法以解決企業(yè)在生產(chǎn)經(jīng)營活動中所出現(xiàn)的許多問題，取得了良好效果。60年代中期，一些

4、銀行、醫(yī)院、圖書館等都已陸續(xù)認識到運籌學對幫助改進服務功能、提高服務效率所起的作用，由此帶來了運籌學在服務性行業(yè)和公用事業(yè)中的廣泛應用。電子計算機技術(shù)的迅速發(fā)展，為廣泛應用運籌學方法提供了有力工具，運籌學的應用又開創(chuàng)了新的局面。當前，運籌學在經(jīng)濟管理、生產(chǎn)管理、工程建設、軍事作戰(zhàn)、科學試驗以及社會系統(tǒng)等各個領(lǐng)域中都得到了極為廣泛的應用。一些發(fā)達國家的企業(yè)、政府、軍事等部門都擁有相當規(guī)模的運籌學研究組織，專門從事運籌學的應用研究，并為上層

5、決策部門提供科學決策所需的信息和依據(jù)。隨著運籌學技術(shù)的推廣應用，各國都先后成立了運籌學研究的專業(yè)學術(shù)機構(gòu)。早在1948年，英國成立了運籌學俱樂部，并出版運籌學的專門學術(shù)刊物。1957年，在英國牛津大學召開了第一屆國際運籌學會議。1959年，成立了國際運籌學聯(lián)合會。我國于1956年成立了第一個運籌學小組，1980年成立了全國運籌學會，這對促進我國運籌學的應用和發(fā)展起了積極作用，特別是著名數(shù)學家華羅庚教授早在50年代中期就在一些企業(yè)和事業(yè)單

6、位積極推廣和普及優(yōu)選法、統(tǒng)籌法等運籌學方法，取得了顯著成效。今天，我國有關(guān)高等院校不僅設置了運籌學專業(yè)，而且在管理類、財經(jīng)類等的有關(guān)專業(yè)普遍開設了運籌學的必修課程。許多專業(yè)的碩土生，也設置了運籌學作為學位課程。運籌學的實質(zhì)在于模型的建立和使用。應用運籌學處理問題時，首先要求從系統(tǒng)觀點來分析問題，即不僅要求提出需要解決的問題和希望達到的目標，而且還要弄清問題所處的環(huán)境和約束條件，包括：時間、地點、資金、原材料、設備、人力、能源、動力、信息

7、、技術(shù)等的環(huán)境和約束條件，以及要處理問題中的主要因素、各種環(huán)境和約束條件之間的邏輯關(guān)系。運籌學是一門多分支的應用學科，隨著新的系統(tǒng)問題的不斷出現(xiàn)，運籌學的有關(guān)分支3定義定義5.1設線性規(guī)劃模型的一般式為：nnxcxcxcZ?????2211max(min)（5.1）約束條件（s.t.）?????????????????????????????????????njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn?????

8、??21022112222212111212111（5.2）滿足約束條件（5.2）的一組數(shù)，稱為該線性規(guī)劃模型的可行解。??nxxx?21滿足目標函數(shù)，即使得目標函數(shù)達到最大值或最小值的可行解，稱為該線性規(guī)劃模型的最優(yōu)解。把最優(yōu)解代入目標函數(shù)所得到的目標函數(shù)的最大值或最小值稱為最優(yōu)值。定義定義5.2某個線性規(guī)劃模型的全體可行解組成的集合，稱為該線性規(guī)劃模型的可行解域。4.2.2線性規(guī)劃模型的標準型線性規(guī)劃模型的標準型為討論方便，我們規(guī)定

9、線性規(guī)劃模型的標準型，而其它非標準型總可以通過一些方法化為標準型。線性規(guī)劃模型的標準型線性規(guī)劃模型的標準型為：目標函數(shù)（5.3）nnxcxcxcZ?????2211max約束條件（s.t.）（5.4）?????????????????????????njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn???????21022112222212111212111注意，在線性規(guī)劃模型的標準型中，約束條件是一組線性等式，也稱