1、1運籌學2運籌學的歷史與發展 國際上運籌學的思想可追溯到1914年，當時的蘭徹斯特提出了軍事運籌學的作戰模型。1917年，丹麥工程師埃爾朗在研究自動電話系統中通話線路與用戶呼叫的數量關系問題時，提出了埃爾朗公式，研究了隨機服務系統中的系統排隊與系統擁擠問題。存儲論的最優批量公式是在20世紀20年代初提出的。 運籌學作為科學名字出現在20世紀30年代。當時英美對付德國的空襲，雷達作為防空系統的一部分，從技術上是可行的，但實際運用時卻并不好用。為此一些科學家研究如何合理運用雷達開始進行新一類問題的研究。因為它與研究技術問題不同，就稱之為“運用研究”(Operational Research)。 為

2、了進行運籌學研究，在英美軍隊中成立了一些專門小組，開展了護航艦隊保護商船隊的編隊問題和當船隊遭到德國艦艇攻擊時，如何使船隊損失最少的問題。3 研究了反潛深水炸彈的合理爆炸深度后，使德國潛艇被摧毀的數量增加到400%； 研究了船只在受敵機攻擊時，提出大船應急轉向和小船應緩慢轉向的逃避方法，結果船只中彈數由47%降到29%。 在生產管理方面的應用，最早是1939年前蘇聯的數學家康托洛維奇提出了生產組織與計劃中的線性規劃問題，并給出解乘數法的求解方法，出版了第一部關于線性規劃的著作生產組織與計劃中的數學方法。 線性規劃提出后很快受到經濟學家重視，如二次世界大戰中從事運輸模型研究的美國經濟學家庫普曼斯

3、(T.C.Koopmans)，他很快看到了線性規劃在經濟中應用的意義，并呼吁年輕的經濟學家要關注線性規劃。其中阿羅、薩謬爾遜、西蒙、多夫曼和胡爾威茨等都獲得了諾貝爾獎。 但當時并沒有引起重視，直到1960年康托洛維奇再次出版了最佳資源利用的經濟計算，才受到國內外的一致重視，為此康托洛維奇獲得了諾貝爾經濟學獎。 50年代中期，錢學森、許國志等教授在國內全面介紹和推廣運籌學知識，1956年，中國科學院成立第一個運籌學研究室，1957年運籌學運用到建筑和紡織業中，1958年提出了圖上作業法，山東大學的管梅谷教授提出了“中國郵遞員問題”，1970年，在華羅庚教授的直接指導下，在全國范圍內推廣統籌方法和

4、優選法。 在中國，最早的運籌學思想有戰國時期的田忌賽馬，它是對策論的一個典型例子，北宋時期的丁渭造皇宮，它是統籌規劃的一個例子。第一章 線性規劃(Linear Programming)線性規劃問題及其數學模型線性規劃圖解法線性規劃問題解的性質 單純形法 單純形法的其他問題討論 線性規劃應用舉例 WinQSB軟件應用第一節 線性規劃問題及其數學模型 產 品資 源 甲乙每天可用于產品生產的資源量設備1116材料A3236材料B565利潤（元）9070 【例1-1】已知某企業生產資料如下表所示，問如何安排生產才能企業使利潤最大？數學模型：一、線性規劃問題的提出設甲產品的生產量為 x1 ,乙產品的生產

5、量為 x2 ，則：約束條件： 【例1-2】設某種動物每天需要攝入的蛋白質、礦物質、維生素的最低量及A、B、C、D、E五種飼料每公斤營養成分的含量及單位價格如下表所示。要求既滿足該種動物每天營養成分的需要量，又使總的費用最省。 目標函數： 約束條件： ABCDE每天最低攝入量(克)蛋白質(克)礦物質(克)維生素(克)310.520.5110.20.2622180.50.870030100價格(元/千克)27438設 為第 j 種飼料的每天使用量，則： 線性規劃問題數學模型的組成要素： 二、線性規劃問題數學模型的一般形式 (1)變量，或稱決策變量，它們是問題中所要解決的未知量，表明規劃中用數量表示

6、的方案、措施，可由決策者決定和控制； (2)目標函數，是決策變量的函數，按問題的目標不同分別在這個函數前加上max或min； (3)約束條件，由一組含決策變量的等式或不等式組成，表明決策變量取值時所受到的各種資源條件的限制。 假定線性規劃問題中含有 n 個決策變量 xj (j1，n)， 在目標函數中 xj 的系數為 cj (cj 通常稱為價值系數)； 有m 種資源的限制，每種資源數量用 bi(i=1,.m)表示； 用 aij表示變量 xj 取值為1個單位時所消耗或含有的第 i 種資源的數量，通常稱 aij 為技術系數或消耗系數。 目標函數：約束條件：線性規劃問題的數學模型的一般形式：為目標函數

7、；為資源約束；為非負約束。xj決策變量；cj價值系數；aij技術（消耗）系數；bi資源常量，bi0線性規劃模型的簡寫形式為：用向量形式表達時，模型可寫為：式中：矩陣形式為：其中：A為約束方程組（約束條件）的系數矩陣。三、線性規劃問題的標準形式化一般形式為標準形式的方法： 1、目標函數為求極小值，即為:因為求Min z，等價于求Max(-z)，令z=-z，即化為：2右端項 bi0又Pj0，對應的變量 xj 就可作為換入基的變量，當有一個以上檢驗數大于零時，一般從中找出最大一個s。作為進基變量(也稱換入變量)確定進基變量確定離基變量根據最小的規則確定： 確定是離基的變量(也稱換出變量)。元素 決定

8、了從一個基可行解到相鄰基可行解的轉移去向，取名主元素。 以 ahs ，為主元素進行迭代。 迭代計算 第4步：重復第2，3兩步，直到所有的檢驗數小于等于0時，計算結束。【例1-5】用單純形法求解線性規劃問題 解：將上述問題化為標準形式有： 其約束條件系數矩陣為： 列出初始單純形表為： cj cBxBb x1 x2 x3 x4 x5j 36/316/19070000111003201005001x3x4x500016366590700000900 x3x1x5 j0651215001001/32/370900 x2x1x5 j401/31-1/300100-30012181312013-10500

9、-1551410-2100-300-200【例】用單純形法求解線性規劃問題 解：將上述問題化為標準形式有： 列出初始單純形表為： cj cBxBb x1 x2 x3 x4 x5 j 906000011100201005001x3x4x500016366536/316/10900 x3x1x5 j90060000651215001001/32/360900 x2x1x5 j401/31-1/30000-3001218131201-10500-1551410-210000-30033max z2xl+x2 0,21xx52x2461x1552x+22xx1+例：利用單純形法求解下列問題化為標準型0

10、,54321xxxxx=+15532xx=+ 552xxx1+=+24641xx+2x2cj 2 1 0 0 0 cBxBb x1 x2 x3 x4 x5000 x3x4x515245 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1j 24/65/1020 x3x1x5 j2010001412/30-1/61001/61/3021x3x1x2 j150510001/30-1/303123/215/20015/4-15/23/2010-1/43/27/21001/4-1/2000-1/4-1/2建立初始單純形表如下：第五節 單純形法的其他問題討論一、關于標準形為最小化問題目標函數為最

11、小化的標準形式，最優性檢驗的判別定理 ： 定理1.7（最優解）設 為對應于基B的一個基可行解，且對于一切 有 ，則 為線性規劃問題的最優解。 定理1.8（無窮多最優解）設 為對應于基B的一個基可行解，且對于一切 有 ，同時又存在某個非基變量的檢驗數 ，則線性規劃問題存在無窮多最優解。 定理1.9（無界解）設 為對應于基B的一個基可行解，存在某個非基變量的檢驗數 ，且有 ，則線性規劃問題具有無界解。二、人工變量法 【例1-6】用單純形法求解線性規劃問題 解：將其化成標準形式有 上述標準化模型中，不存在單位矩陣，為構造單位矩陣，則需要通過添加人工變量的方法，人為構造一個單位矩陣，該方法即所謂的人工

12、變量法。 1.大M法 大 M 法又稱懲罰法，其基本思想是：約束條件加入人工變量后，為使目標函數取值不受影響，給定它們在求最大值(max)的目標函數中的系數為(-M)(稱為懲罰因子，M為任意大的正數)，以作為對基變量中存在人工變量的懲罰，從而迫使人工變量從基變量中分離出來，否則目標函數將不能實現最大化。 添加人工變量后，例1-6的數學模型形式變為： 列出初始單純形表如下： cj32-100- M- McBxBbx1x2x3x4x5x6x7- Mx64-431-10100 x5101-120100- Mx712-210001j-Mx60 x5- 1x3j38-60-101-1-330010-2-2

13、100011- 2M5-6M5M-M000213/58/32x20 x5-1x3j-6/53/510-1/501/5-1/531/5003/51-3/5-7/511/5-2/501-2/502/53/550000-M1-M53/531/32x21301012-1-33x131/310015/3-1-7/3-1x319/300102/30-1/3j000-5-25/35-M38/3-M-M2+M2M-13-2M000451 計算機處理數據時，只能用很大的數代替M,可能造成計算機上的錯誤，故多采用兩階段法。 2、兩階段法第一階段：添加人工變量，重新構造目標函數 將原問題加入人工變量，構造僅含人工變

14、量的新的目標函數，并要求實現最小化。新的目標函數形式如下： 求解上述線性規劃問題。若 w =0，則原線性規劃問題存在基可行解，計算轉入第二階段；若 w 0，則原線性規劃問題無可行解，計算停止。 第二階段：對原目標函數求解 在第一階段的最終單純形表中，將 cj 行的數字換為原目標函數的系數，并且去掉表中含有人工變量的列，繼續求解。 將例1-6問題利用兩階段法進行求解。 第一階段：添加人工變量，重新構造目標函數。例1-6用兩階段法求解時，第一階段的線性規劃問題可寫為： 將上述數學模型標準化后，用單純形法求解過程見下表： cj00000- 1-1cBxBbx1x2x3x4x5x6x7- 1x64-4

15、31-101040 x5101-1201005- 1x712-2100011j-212-1000-1x60 x50 x3j38-60-101-1-330010-2-210001-2-65-1000213/58/30 x20 x50 x3j-6/53/510-1/501/5-1/531/5003/51-3/5-7/511/5-2/501-2/502/53/500000-1-153/5可以看出：W=0，該問題有解；轉入第二階段。cj32-100cBxBbx1x2x3x4x52x23/5-6/510-1/500 x531/53/5003/51-1x311/5-2/501-2/50j500002x21

16、3010123x131/310015/3-1x319/300102/3j000-5-22/3第二階段： 得最優解。 將第一階段得到的最終單純形表的人工變量列去掉，將目標Cj行換為原目標函數的系數，再進行迭代。31/3三、單純形法計算中退化與循環問題 單純形法計算中按最小比值來確定離基變量時，有時存在兩個以上相同的最小比值，這樣在下一次迭代中就會出現一個或多個基變量等于零的情形，這就出現了所謂的退化解。當存在退化解時，就有可能出現迭代計算的循環。 勃蘭特規則： (1)當存在多個 且相等時，選取 中下標值最小的變量作為進基變量； (2)當按規則計算出現兩個或兩個以上相同的最小比值時，選取下標值最小

17、的變量作為離基變量。 第六節 線性規劃應用舉例一、混合配料問題 【例1-7】某工廠要用三種原材料C、P、H混合調配出三種不同規格的產品A、B、D。已知產品的規格、產品單價、每天能供應的原材料數量及原材料單價如表1-10、表1-11所示。表1-1025不限D原材料P不超過50%35原材料C不少于25%B原材料P不超過25%50原材料C不少于50%A單價(元/kg)規格要求產品名稱表1-113560H25100P65100C單價(元/kg)每天最大供應量(kg)原材料名稱 問該廠如何安排生產，利潤收入最大？解：設Ac表示A產品中C的成分，其數量用x1表示； AP表示A產品中P的成分，其數量用x2表

18、示； AH表示A產品中H的成分，其數量用x3表示； BC表示B產品中C的成分，其數量用x4表示； BH表示B產品中H的成分，其數量用x6表示； BP表示B產品中P的成分，其數量用x5表示； DC表示D產品中C的成分，其數量用x7表示； DH表示D產品中H的成分，其數量用x9表示. DP表示D產品中P的成分，其數量用x8表示； 依據題意，得： 依據產品規格要求得： 整理得： 25不限D原材料P不超過50%35原材料C不少于25%B原材料P不超過25%50原材料C不少于50%A單價(元/千克)規格要求產品名稱依據原材料每天供應量限制得：該問題的線性規劃數學模型為： 3560H25100P65100

19、C單價每天最大供應量原材料二、生產計劃安排問題 【例1-8】某廠生產、三種產品，都分別經A、B兩道工序加工。設A工序可分別在設備A1或A2上完成，有B1、B2、B3三種設備可用于完成B工序。已知產品可在A、B任何一種設備上加工；產品可在任何規格的A設備上加工，但完成B工序時，只能在B1設備上加工；產品只能在A2與B2設備上加工。加工單位產品所需工序時間及其它各項數據見下表：2.802.001.25售價（元/件）0.500.350.25原料費(元/件)0.0540007B30.117000114B20.06400086B10.03100001297A20.056000105A1設備加工費設備有效

20、臺時產品設備 試安排最優生產計劃，使該廠獲利最大。 解：設產品、的產量分別為x1,x2,x3件 工廠的盈利為產品售價減去相應的原料費和設備加工費。產品加工量只受設備有效臺時的限制。故可建立如下線性規劃模型： 產品有6種加工方案，分別利用設備(A1,B1)(A1,B2)(A1,B3)(A2，B1)(A2,B2)(A2,B3)，各方案加工的產品數量用 xll，x12，x13，x14，x15，x16 表示； 產品有2種加工方案，即(A1,B1)(A2,B1)，加工數量用 x21，x22 表示； 產品只有1種加工方案(A2,B2)，加工數量等于 x3。 2.802.001.25售價（元/件）0.500

21、.350.25原料費（元/件）0.0540007B30.117000114B20.06400086B10.03100001297A20.056000105A1設備加工費設備有效臺時產品設備三、生產與存貯問題 解：設 xij 為 i 種產品 j 月份在正常時間內生產的數量， 為第 i 種產品 j 月份在加班時間內生產的數量。該廠盈利總額為生產的5種產品銷售價減去成本和庫存費用。問題的限制條件有兩項：一是各個月的正常和加班的允許工時，二是滿足交貨要求。本例的線性規劃模型可表示為: 【例1-9】某廠簽訂了5種產品(i1，5)上半年的交貨合同。已知各產品在第j月(j1，6)的合同交貨量Dij，該月售價

22、 sij 、成本價 cij 及生產1件時所需工時 aij 。該廠第j月的正常生產工時為 tj ，但必要時可加班生產，第j月允許的最多加班工時不超過 ，并且加班時間內生產出來的產品每件成本增加額外費用 元；若生產出來的產品當月不交貨，每件庫存1個月交存貯費 pi 元。試為該廠設計一個保證完成合同交貨，又使上半年預期盈利總額為最大的生產計劃安排。 解：設 為 i 種產品 j 月份在正常時間內生產的數量， 為第 i 種產品 j 月份在加班時間內生產的數量。本例的線性規劃模型可表示為: 四、人力資源分配問題 【例1-10】某醫院護士值班班次及每班所需要的護士人數如下表所示。 班次工作時間所需人數(人)

23、1 6:0010:0060210:0014:0070314:0018:0060418:0022:0050522:00 2:00206 2:00 6:0030 若該醫院值班護士分別在各時間段開始時上班，并連續工作8小時。問該醫院最少需要多少護士，才能滿足工作需要？ 解：設 xi 表示第 i 班開始時上班的護士人數。根據題意，該問題的數學模型為： 班次工作時間所需人數(人)1 6:0010:0060210:0014:0070314:0018:0060418:0022:0050522:00 2:00206 2:00 6:0030五、連續投資問題 【例1-11】某部門今后五年內考慮給以下項目投資，已知：項目A，從第一年到第四年每年年初需要投資，并于次年末收回本利115%； 項目B，第三年初需要投資，到第五年末收回本利125%，但規定最大投資額不超過4萬元； 項目C，第二