運(yùn)籌學(xué)第01章線性規(guī)劃

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

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

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

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

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

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

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

8、了從一個(gè)基可行解到相鄰基可行解的轉(zhuǎn)移去向，取名主元素。 以 ahs ，為主元素進(jìn)行迭代。 迭代計(jì)算 第4步：重復(fù)第2，3兩步，直到所有的檢驗(yàn)數(shù)小于等于0時(shí)，計(jì)算結(jié)束?！纠?-5】用單純形法求解線性規(guī)劃問題 解：將上述問題化為標(biāo)準(zhǔn)形式有： 其約束條件系數(shù)矩陣為： 列出初始單純形表為： 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【例】用單純形法求解線性規(guī)劃問題 解：將上述問題化為標(biāo)準(zhǔn)形式有： 列出初始單純形表為： 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+例：利用單純形法求解下列問題化為標(biāo)準(zhǔn)型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建立初始單純形表如下：第五節(jié) 單純形法的其他問題討論一、關(guān)于標(biāo)準(zhǔn)形為最小化問題目標(biāo)函數(shù)為最

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

12、變量法。 1.大M法 大 M 法又稱懲罰法，其基本思想是：約束條件加入人工變量后，為使目標(biāo)函數(shù)取值不受影響，給定它們?cè)谇笞畲笾?max)的目標(biāo)函數(shù)中的系數(shù)為(-M)(稱為懲罰因子，M為任意大的正數(shù))，以作為對(duì)基變量中存在人工變量的懲罰，從而迫使人工變量從基變量中分離出來，否則目標(biāo)函數(shù)將不能實(shí)現(xiàn)最大化。 添加人工變量后，例1-6的數(shù)學(xué)模型形式變?yōu)椋?列出初始單純形表如下： 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 計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很大的數(shù)代替M,可能造成計(jì)算機(jī)上的錯(cuò)誤，故多采用兩階段法。 2、兩階段法第一階段：添加人工變量，重新構(gòu)造目標(biāo)函數(shù) 將原問題加入人工變量，構(gòu)造僅含人工變

14、量的新的目標(biāo)函數(shù)，并要求實(shí)現(xiàn)最小化。新的目標(biāo)函數(shù)形式如下： 求解上述線性規(guī)劃問題。若 w =0，則原線性規(guī)劃問題存在基可行解，計(jì)算轉(zhuǎn)入第二階段；若 w 0，則原線性規(guī)劃問題無可行解，計(jì)算停止。 第二階段：對(duì)原目標(biāo)函數(shù)求解 在第一階段的最終單純形表中，將 cj 行的數(shù)字換為原目標(biāo)函數(shù)的系數(shù)，并且去掉表中含有人工變量的列，繼續(xù)求解。 將例1-6問題利用兩階段法進(jìn)行求解。 第一階段：添加人工變量，重新構(gòu)造目標(biāo)函數(shù)。例1-6用兩階段法求解時(shí)，第一階段的線性規(guī)劃問題可寫為： 將上述數(shù)學(xué)模型標(biāo)準(zhǔn)化后，用單純形法求解過程見下表： 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，該問題有解；轉(zhuǎn)入第二階段。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第二階段： 得最優(yōu)解。 將第一階段得到的最終單純形表的人工變量列去掉，將目標(biāo)Cj行換為原目標(biāo)函數(shù)的系數(shù)，再進(jìn)行迭代。31/3三、單純形法計(jì)算中退化與循環(huán)問題 單純形法計(jì)算中按最小比值來確定離基變量時(shí)，有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就會(huì)出現(xiàn)一個(gè)或多個(gè)基變量等于零的情形，這就出現(xiàn)了所謂的退化解。當(dāng)存在退化解時(shí)，就有可能出現(xiàn)迭代計(jì)算的循環(huán)。 勃蘭特規(guī)則： (1)當(dāng)存在多個(gè) 且相等時(shí)，選取 中下標(biāo)值最小的變量作為進(jìn)基變量； (2)當(dāng)按規(guī)則計(jì)算出現(xiàn)兩個(gè)或兩個(gè)以上相同的最小比值時(shí)，選取下標(biāo)值最小

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

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

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

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

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

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

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