1、1運(yùn)籌學(xué)研究的基本思想與方法o （1）基本思想n運(yùn)籌學(xué)研究的是如何用科學(xué)的方法來解決某一比較復(fù)雜的系統(tǒng)的最優(yōu)管理或運(yùn)行問題。n模型就是某一物體或系統(tǒng)的替代物。模型有實(shí)物模型和數(shù)學(xué)模型。如果所用的替代物具有一種數(shù)學(xué)的形式或與其相似的符號形式（如邏輯形式），則為數(shù)學(xué)模型。數(shù)學(xué)模型又可分為確定型模型和隨機(jī)型模型。 n運(yùn)籌學(xué)模型是數(shù)學(xué)模型的一種，其典型形式為：n如何確定可控變量應(yīng)取的值，使效能指標(biāo)達(dá)到最優(yōu)化。這就是運(yùn)籌學(xué)的基本思想。2（2）基本方法或工作步驟o提出和形成問題實(shí)際問題決策目標(biāo)問題中的變量可能的方案以及行動步驟問題的來龍去脈o建立模型辯認(rèn)并確定相關(guān)的變量確定變量之間的關(guān)系 3.測試模型把以

2、前的數(shù)據(jù)代入模型，看它所預(yù)言的結(jié)果與實(shí)際結(jié)果是否接近修改模型時，分析模型中是否有不相關(guān)的變量、是否忽視了相關(guān)的變量、變量間的函數(shù)關(guān)系是否正確4.得到問題的解決方案用相應(yīng)算法求解軟件求解5.方案實(shí)施與控制外在因素變化時，調(diào)整模型或方案以適應(yīng)變化31.3 運(yùn)籌學(xué)在工商管理中的應(yīng)用 生產(chǎn)計(jì)劃 庫存管理 運(yùn)輸問題 人事管理 市場營銷 財(cái)務(wù)與會計(jì)某工廠在計(jì)劃期內(nèi)要安排 I、II兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及 A，B兩種原材料的消耗，以及資源的限制，如下表所示。該工廠每生產(chǎn)一單位產(chǎn)品 I可獲利50元，每生產(chǎn)一單位產(chǎn)品II可獲利100元，如何制訂工廠的生產(chǎn)計(jì)劃，才能使獲利最多？ 250千克

3、10原料B400千克12原料A300臺時11設(shè)備資源限制III（下料問題）某工廠要做 100套鋼架，每套用長為 2.9米、2.1米、1.5米的圓鋼各一根。已知原配料每根長 7.4米。如何下料，可使所用原材料最?。浚ㄈ藛T安排問題）某醫(yī)院根據(jù)日常工作統(tǒng)計(jì)，每晝夜 24小時中至少需要下列數(shù)量的護(hù)士。護(hù)士們分別在各時間段開始時上班，并連續(xù)工作 8小時，如何安排各時間段開始上班工作的人數(shù)，才能使護(hù)士的總?cè)藬?shù)最少 ？2:006:00 30人14:0018:00 60人22:002:00 20人10:0014:00 70人18:0022:0050人6:0010:00 60人一個公司一年工作 50周，對某一物

4、品的需求恒為 100件。每一件的成本為 200元，該公司的資金回報率為 20%。年倉庫成本為存儲貨物價值的 5%。公司采購部門每年成本為450000元，平均發(fā)生 2000個訂單。試分析該物品的最優(yōu)訂貨量，兩次訂貨的間隔時間以及年庫存成本。某公司從兩個產(chǎn)地 A1、A2將物品運(yùn)往三個銷地 B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地運(yùn)往各銷地的每件物品的運(yùn)費(fèi)如表所示：200150150銷量（件）300556A2200646A1產(chǎn)量（件）B3B2B1運(yùn)費(fèi)單價? ? ABCD踶? 2 Y 夯Z 氽*糊疔yF ? 亜鯛 俬 : 俇踶; 弼? ? ? ? ? ? ? ? ? ? ? ? ?9119

5、717141781614712Y7161792DCBA? 鯛某廠要確定一種新產(chǎn)品在今后五年內(nèi)的價格 ,并已擬定只在 5,6,7,8元這四種單價中進(jìn)行選擇 .據(jù)預(yù)測,今后五年不同價格下每年盈利 (萬元)如下表所示,但是各相鄰年度價格不得超過1元.問今后五年內(nèi)每年定價各為多少 ,可預(yù)期五年總利潤最大 ?466788元379567元468576元854295元54321年價格某公司有100萬元用于投資，可選擇的投資項(xiàng)目如下：項(xiàng)目A：從第一年到第四年每年年初都可投資，并于次年末回收本利 110%，規(guī)定每年的最低投資額為 10萬元；項(xiàng)目B：第二年初可以投資，到第五年年末能收回本利135%，規(guī)定投資額不超

6、過 20萬元；項(xiàng)目C：第三年初可以投資，到第五年末回收本利 125%，規(guī)定最低投資額為 20萬元，最高投資額為 40萬元；項(xiàng)目D：五年內(nèi)每年年初都可投資，年末回收本 104%；應(yīng)如何確定給這些項(xiàng)目每年的投資額，使收益最大？4運(yùn)籌學(xué)方法的使用情況各個工商企業(yè)使用運(yùn)籌學(xué)方法的頻率不同，有的經(jīng)常使用，有的只是偶爾使用。大公司大企業(yè)使用運(yùn)籌學(xué)方法的百分比高。據(jù)統(tǒng)計(jì)，88%的美國大公司使用預(yù)測方法，超過50%的大公司用運(yùn)籌學(xué)方法制定生產(chǎn)計(jì)劃、存儲控制、資金預(yù)算、運(yùn)輸方案等。各種運(yùn)籌學(xué)方法的使用程度也是不同的，統(tǒng)計(jì)、線性規(guī)劃、網(wǎng)絡(luò)計(jì)劃、計(jì)算機(jī)模擬、決策論、排隊(duì)論使用的頻率高。如制造業(yè)中最經(jīng)常使用的是網(wǎng)絡(luò)計(jì)

7、劃，其次是統(tǒng)計(jì)、模擬、線性規(guī)劃。3.227.469.4對策論4.833.961.3動態(tài)規(guī)劃8.138.753.2非線性規(guī)劃9.750.040.3排隊(duì)論14.559.725.8線性規(guī)劃21.053.225.8網(wǎng)絡(luò)計(jì)劃33.953.212.9計(jì)算機(jī)模擬59.738.71.6統(tǒng)計(jì)經(jīng)常使用有時使用從不使用方法排列（按重要性和有效性）統(tǒng)計(jì)方法線性規(guī)劃和整數(shù)規(guī)劃模擬網(wǎng)絡(luò)模型（包括 PERT/CPM）決策分析排隊(duì)模型存貯模型動態(tài)規(guī)劃5中國使用運(yùn)籌學(xué)方法的情況690年以前的一些經(jīng)典應(yīng)用790年代以來的一些應(yīng)用舉例81.4 學(xué)習(xí)管理運(yùn)籌學(xué)必須使用相應(yīng)的計(jì)算機(jī)軟件，必須注重學(xué)以致用的原則 o例如，有人要從北京去烏

8、魯木齊。在一百多年以前，我們應(yīng)該告訴他如何配備糧草、銀兩、衣物，如何選購馬匹、馬車，挑選馬夫和保鏢，如何根據(jù)天氣、地理?xiàng)l件和社會諸因素來確定行車路線和行程，更重要的是如何在幾個月的行程中處理吃穿住行，應(yīng)付突發(fā)事件等問題；但是現(xiàn)在我們只需告訴他如何去北京飛機(jī)場，如何在烏魯木齊下飛機(jī)后提取行李和坐車就可以了，其余的問題交給航空公司和機(jī)組人員就行了。完全沒有必要為了一次旅行攻讀空氣動力學(xué)、噴氣發(fā)動機(jī)設(shè)計(jì)和制造、飛行器駕駛手冊等厚厚的教科書。o“他山之石，可以攻玉”。o計(jì)算機(jī)為運(yùn)籌學(xué)提供解題工具。9Chapter Two Linear Programming 線性規(guī)劃問題 線性規(guī)劃模型 線性規(guī)劃的求解

9、 圖解法 單純形法 線性規(guī)劃的應(yīng)用10線性規(guī)劃問題(P11)（生產(chǎn)計(jì)劃）某工廠在計(jì)劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A，B兩種原材料的消耗，以及資源的限制，如下表所示。該工廠每生產(chǎn)一單位產(chǎn)品I可獲利50元，每生產(chǎn)一單位產(chǎn)品可獲利100元，工廠應(yīng)分別生產(chǎn)多少產(chǎn)品I、 才能使工廠獲得最多？11建立模型第一步：確定決策變量(要決定的未知量) 第二步：確定追求目標(biāo)、目標(biāo)與決定變量 之間的函數(shù)關(guān)系(目標(biāo)函數(shù)) 第三步：確定約束條件(決策變量受到的約束)12生產(chǎn)計(jì)劃問題的模型1.確定決策變量：x x1 1, x x2 2 (x x1 1 為產(chǎn)品I的生產(chǎn)數(shù)量, x x2 2為產(chǎn)品

10、II的生產(chǎn)數(shù)量)2.確定目標(biāo)函數(shù)：Z=50 x x1 1+100 x x2 23.尋找約束條件 s.t. (subject to) 設(shè)備限制：x x1 1+x x2 2300原料A的限制：2x x1 1+x x2 2400 原料B的限制：x x2 2250 非負(fù)條件： x x1 1 0 ，x x2 20 13o靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3,在兩個工廠之間有一條流量為每天200萬支流，第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬m3，第二化工廠每天排放含有這種有害物質(zhì)的工業(yè)污水1.4萬m3。從第一化工廠排出的工業(yè)污水流到第二化工廠之前，有20可自然凈化，

11、根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%，這兩個工廠都需要各自處理一部分工業(yè)污水，第一化工廠處理工業(yè)污水的成本是1000元/萬m3，第二化工廠處理工業(yè)污水的成本是800元/萬m3，現(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費(fèi)用最??？200萬m3500萬m3工廠2工廠114o1.確定決策變量：x x1 1, x x2 2 (x x1 1第一化工廠每天處理污水 , x x2 2為第二化工廠每天處理污水 )2.確定目標(biāo)函數(shù)：Z=1000 x x1 1+800 x x2 23.尋找約束條件 o處理污水量限制 ：o環(huán)保限制：o 非負(fù)條件： x x1

12、1 0 ，x x2 20 %2 . 050021 x11x %2 . 0700)4 . 1 ()2(8 . 021xx6 . 18 . 021 xx4 . 1,221xx1504 . 126 . 18 . 01. .8001000min212121121xxxxxxxtsxxz、16市場調(diào)查公司（MSI）專門評定消費(fèi)者對新產(chǎn)品、服務(wù)和廣告活動的反應(yīng)。一個客戶要求MSI幫助確定消費(fèi)者對一種近期推出的家居產(chǎn)品的反應(yīng)?？蛻粢蟛扇€人入戶調(diào)查（分為日間調(diào)查和晚間調(diào)查），以從有孩家庭和無孩家庭獲得回答?？蛻舻暮贤笠罁?jù)以下條款進(jìn)行1000個訪問：1）至少訪問400個有孩家庭；2）至少訪問400個無孩

13、家庭；3）晚間訪問的總數(shù)量至少等于日間訪問的數(shù)量；4）至少40%有孩家庭必須在晚間訪問；5）至少60%無孩家庭必須在晚間訪問。訪談成本見表所示。怎樣安排，才能既滿足合同要求，又成本最低？練習(xí)17 決策變量：對有孩家庭日間訪問的數(shù)量x1、對有孩家庭晚間訪問的數(shù)量x2、對無孩家庭日間訪問的數(shù)量x3、對無孩家庭晚間訪問的數(shù)量x4目標(biāo)函數(shù)：min z=20 x1+25x2+18x3+20 x4 約束條件：x1+x2+x3+x41000 x1+x2400 x3+x4400 x2+x4x1+x3 即- x1+x2- x3+x40 x20.4（x1+x2）即-0.4x1+0.6x20 x40.6（x3+x4

14、）即-0.6x3+0.4x40 x1 、x2 、x3 、x4 018線性規(guī)劃的數(shù)學(xué)模型o 1. 每一個問題都用一組決策變量表示某一方案，這組變量的值就代表一個具體方案，一般這些變量的取值非負(fù) 決策變量o 2. 存在一定的限制條件(如供求關(guān)系，生產(chǎn)任務(wù)、資源限制等) ，它們可以用變量的線性等式或線性不等式來表示，這些條件稱為約束條件。 線性約束o 3. 都有一個要求達(dá)到的目標(biāo)，它可以用變量的線性函數(shù)（稱為目標(biāo)函數(shù)）來表示。根據(jù)需要要求目標(biāo)函數(shù)最大化或最小化。 目標(biāo)函數(shù)o -具有上面三個特征的問題是線性規(guī)劃問題19建模過程建模過程 （P12）o 1.理解要解決的問題，了解解題的目標(biāo)和條件；o 2.

15、定義決策變量（ x1 ，x2 ， ，xn ），每一組值表示一個方案；o 3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；o 4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件20練習(xí)題：人員安排問題(P39)o 某晝夜服務(wù)公共交通系統(tǒng)每天各時間段（每4 4小時為一個時間段）所需的值班人員如下表所示。這些值班人員在某時段上班后要連續(xù)工作8 8個小時（包括輪流用膳時間在內(nèi)）。問該公交系統(tǒng)至少需多少名工作人員才能滿足值班的需要。2122某地區(qū)在今后三年內(nèi)有四種投資機(jī)會o 第種：三年內(nèi)每年年初投資，年底可獲利潤20%，并將本金收回；o 第種：第一年年初投資，第二年年

16、底可獲利潤50%，并將本金收回，但該項(xiàng)目投資不得超過二萬元；o 第種：第二年年初投資，第三年年底收回本金，并獲利潤60%，但該項(xiàng)投資不得超過一萬五千元；o 第種：第三年年初投資，于該年年底收回本金，且獲利40%，但該項(xiàng)投資不得超過一萬元。o 現(xiàn)在該地區(qū)準(zhǔn)備拿出三萬元資金，問如何制定投資計(jì)劃，使到第三年年末本利最大。232425截料問題(P46)o某工程施工中需要制作1000010000套鋼筋，每套鋼筋有2.92.9米、2.12.1米和1.51.5米三種不同長度但直徑和材質(zhì)相同的鋼筋各一根組成。目前可采購到的同類鋼筋的長度均為7.47.4米，問應(yīng)購進(jìn)多少根7.47.4米的鋼筋才能滿足工程的需要？

17、2627運(yùn)運(yùn) 輸輸 問問 題題28問問 題題 分分 析析29模模 型型min 2141ijijijxc 2 , 1;4321 iaxxxxiiiii s.t. 4 , 3 , 2 , 1;21 jbxxjjj 4 , 3 , 2 , 1, 2 , 1; 0 jixij 30o某廠在今后四個月內(nèi)需租用倉庫堆存貨物。已知各個月所需的倉庫面積數(shù)如表1所示。又知，當(dāng)租借合同期限越長時，場地租借費(fèi)用享受的折扣優(yōu)待越大，有關(guān)數(shù)據(jù)如表2所示。租借倉庫的合同每月初都可辦理，每份合同應(yīng)具體說明租借的場地面積數(shù)和租借期限。工廠在任何一個月初辦理簽約時，可簽一份，也可同時簽若干份租借場地面積數(shù)和租借期限不同的合同。

18、為使所付的場地總租借費(fèi)用最少，試建立一個線性規(guī)劃模型。313233343536373839引用（引用（“”“”）記號，）記號，LPLP模型的一般形式可寫為：模型的一般形式可寫為：o 式中，常數(shù)Cj稱為價值系數(shù)，aij是直接消耗系數(shù)，即變量xj取值為1時，第i種資源的直接消耗數(shù)量，bi是第i種資源的限制用量。njxmibxatsxcZjnjijijnjjj, 2, 1, 0, 2, 1),(.max(min)1140LP的向量表示的向量表示 oC =C =（c c1 1，c c2 2，c cn n）, , 是目標(biāo)函數(shù)系數(shù)組成的行向量；是目標(biāo)函數(shù)系數(shù)組成的行向量；oX = ( xX = ( x1

19、1 , x , x2 2 , x , xn n) )T T , , 是模型中所有變量組成的列向量；是模型中所有變量組成的列向量；opj = ( apj = ( a1j1j , a , a2j2j ,a ,amj mj ) )T T , , 是約束條件中是約束條件中x xj j的系數(shù)組成列向量；的系數(shù)組成列向量；ob = ( bb = ( b1 1 , b , b2 2 , ,b , ,bm m ) )T T , , 是約束條件右邊常數(shù)組成的列向量；是約束條件右邊常數(shù)組成的列向量；oO = ( 0, 0, , 0 )O = ( 0, 0, , 0 )T T ，是，是n n維零向量。維零向量。0)

20、,(max(min)1XbxpCXZnjjj41LP模型的矩陣表示為模型的矩陣表示為 OXbAXCXZ),(max(min)mnmmnnaaaaaaaaaA21222211121142標(biāo)準(zhǔn)模型有四點(diǎn)要求：標(biāo)準(zhǔn)模型有四點(diǎn)要求：o 1目標(biāo)函數(shù)求極大值；o 2除非負(fù)約束條件外，其他所有約束條件全為等式；o 3約束等式右端常數(shù)項(xiàng)bi非負(fù)；o 4決策變量取值非負(fù)。43如何化標(biāo)準(zhǔn)形？當(dāng)碰到最小化問題，即當(dāng)碰到最小化問題，即min z =CXmin z =CX化標(biāo)準(zhǔn)形的方法：令化標(biāo)準(zhǔn)形的方法：令z z =-z(z =-z(z =-CX) =-CX)，min zmin z=-CX =-CX 與與max max

21、 z=CXz=CX最優(yōu)解相同，最優(yōu)值反號最優(yōu)解相同，最優(yōu)值反號當(dāng)約束條件是不等式當(dāng)約束條件是不等式不等式左邊加減一個非負(fù)變量不等式左邊加減一個非負(fù)變量( (稱稱松馳變量松馳變量) )化為標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形當(dāng)某個當(dāng)某個b bi i0=0 =0 ，替代，替代 x xk k 444546標(biāo)準(zhǔn)化練習(xí)o 無約束，3213213223213210, 063244239232minxxxxxxxxxxxxxxxz47答案o 0, 0, 0, 0, 0, 06332442239200332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxz48標(biāo)準(zhǔn)化練

22、習(xí)o P24 課后習(xí)題349LP問題的解的概念o 可行解：可行解：滿足約束條件的解滿足約束條件的解X=(xX=(x1 1，x x2 2，x xn n) )o 最優(yōu)解：最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解o 基：基：已知已知A A是約束條件的是約束條件的m mn n系數(shù)矩陣，其秩為系數(shù)矩陣，其秩為m m。若若B B是是A A中中m mm m階非奇異子矩陣階非奇異子矩陣( (即即|B|0),|B|0),則稱則稱B B是是LPLP問題的一個基問題的一個基o 基向量：基向量：基基B B中的一個列向量中的一個列向量p pi io 基變量：基變量：與基向量與基向量P Pi i對

23、應(yīng)的變量對應(yīng)的變量x xi i稱為基變量稱為基變量( (個數(shù)為個數(shù)為m)m)，其它變量稱為非基變量，其它變量稱為非基變量(n-m(n-m個個) )o 基解：基解：由一個基所求出的解稱為基解，基解有可由一個基所求出的解稱為基解，基解有可行的基解行的基解( (稱基可行解稱基可行解) )，也有非可行的基解，也有非可行的基解( (稱基稱基不可行解不可行解) )50LP問題的求解：圖解法 例：例：maxz=50 xmaxz=50 x1 1+100 x+100 x2 2 s.t. xs.t. x1 1+x+x2 2300300 x x1 1+x+x2 2400400 x x2 2250250 x x1 1

24、00 x x2 20051o分別取決策變量分別取決策變量X1, X2X1, X2為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1 1的每的每個約束條件都代表一個半平面。個約束條件都代表一個半平面。52o （2）對每個不等式）對每個不等式(約束條件約束條件)，先取其等，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。定的半平面。53（3）把五個圖合并成一個圖，取各約束條件）把五個圖合并成一個圖，取各約束條件的公共部分，如圖的

25、公共部分，如圖2-1所示。所示。54200300400100200300400100 x1+x23002x1+x2400 x2250X20 x10B(50,250)Z=0 50 x1+100 x2Z=27500 50 x1+100 x2可行域最優(yōu)解線性規(guī)劃問題的最優(yōu)解一定是在可行域的頂點(diǎn)上0500剩余量s302503*50+1*250 250原料Bs2=504002*50+1*250 350原料As1=03001*50+1*250 300設(shè)備臺時松馳變量值資源總量x150，x2250時用掉的資源量約束555657x1x25100788可行域最優(yōu)解101221 xx821 xx0,21xxs.t

26、.72x58x1x2目標(biāo)函數(shù)等值線可行域最優(yōu)解66-8459練習(xí)圖解法0,1241648232max21212121xxxxxxxxz60Q3484Q4Q1Q2x1x2C4x2 =12x1+ 2x2 =81641x6162無界解0,242max21212121xxxxxxxxz4x1x24221xx221 xx63圖解法的靈敏度分析圖解法的靈敏度分析（P18） 任務(wù)：討論模型的系數(shù)或變量發(fā)生小的變化任務(wù)：討論模型的系數(shù)或變量發(fā)生小的變化時對解的影響（如它們在何范圍內(nèi)變化時可時對解的影響（如它們在何范圍內(nèi)變化時可使原最優(yōu)解或最優(yōu)基不變？）使原最優(yōu)解或最優(yōu)基不變？）641. 目標(biāo)函數(shù)系數(shù)變化的靈敏

27、度分析目標(biāo)函數(shù)系數(shù)變化的靈敏度分析2. 右邊項(xiàng)變化的靈敏度分析右邊項(xiàng)變化的靈敏度分析3.約束條件中的系數(shù)變化的靈敏度分析約束條件中的系數(shù)變化的靈敏度分析4. 增加新變量的靈敏度分析增加新變量的靈敏度分析5. 增加約束條件的靈敏度分析增加約束條件的靈敏度分析65 假定只有一個假定只有一個 cj 變化，假定變化，假定 cj 從從 cj 變到變到cj*=cj+ cj，當(dāng)當(dāng) cj在什么范圍內(nèi)變化時，不在什么范圍內(nèi)變化時，不會影響最優(yōu)解。會影響最優(yōu)解。66 假定只有一個假定只有一個 br 變化，假定變化，假定 br 從從 br 變到變到br*=br+ br，當(dāng)當(dāng) br在什么范圍內(nèi)變化時，不在什么范圍內(nèi)變

28、化時，不會影響最優(yōu)解。會影響最優(yōu)解。67 靈敏度分析靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn)變化時，對最優(yōu)解產(chǎn)生的影響。生的影響。3.1 目標(biāo)函數(shù)中的系數(shù)目標(biāo)函數(shù)中的系數(shù) ci 的靈敏度分析的靈敏度分析 考慮例考慮例1的情況，的情況， ci 的變化只影響目標(biāo)函數(shù)等值線的斜率，的變化只影響目標(biāo)函數(shù)等值線的斜率，目標(biāo)函數(shù)目標(biāo)函數(shù) z = 50 x1 + 100 x2 在在 z = x2 (x2 = z 斜率為斜率為0 ) 到到 z = x1 + x2

29、(x2 = -x1 + z 斜斜率為率為 -1 )之間時，原最優(yōu)解之間時，原最優(yōu)解 x1 = 50，x2 = 100 仍是最優(yōu)解。仍是最優(yōu)解。o一般情況：一般情況： z = c1 x1 + c2 x2 寫成斜截式寫成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目標(biāo)函數(shù)等值線的斜率為目標(biāo)函數(shù)等值線的斜率為 - (c1 / c2 ) ， 當(dāng)當(dāng) -1 - (c1 / c2 ) 0 （*） 時，原最優(yōu)解仍是最優(yōu)解。時，原最優(yōu)解仍是最優(yōu)解。 68o假設(shè)產(chǎn)品假設(shè)產(chǎn)品的利潤的利潤100元不變，即元不變，即 c2 = 100，代到式（，代到式（*）并整理得并整理得 0 c1 100 o

30、假設(shè)產(chǎn)品假設(shè)產(chǎn)品的利潤的利潤 50 元不變，即元不變，即 c1 = 50 ，代到式（，代到式（*）并整理得并整理得 50 c2 + o假若產(chǎn)品假若產(chǎn)品、的利潤均改變，則可直接用式（的利潤均改變，則可直接用式（*）來判斷。）來判斷。o假設(shè)產(chǎn)品假設(shè)產(chǎn)品、的利潤分別為的利潤分別為60元、元、55元，則元，則 - 2 - (60 / 55) - 1 那么，最優(yōu)解為那么，最優(yōu)解為 z = x1 + x2 和和 z = 2 x1 + x2 的的交點(diǎn)交點(diǎn) x1 = 100，x2 = 200 。693圖解法的靈敏度分析圖解法的靈敏度分析 3.2 約束條件中右邊系數(shù)約束條件中右邊系數(shù) bj 的靈敏度分析的靈敏度

31、分析 當(dāng)約束條件中右邊系數(shù)當(dāng)約束條件中右邊系數(shù) bj 變化時，線性規(guī)劃的可行域發(fā)生變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。變化，可能引起最優(yōu)解的變化。 考慮例考慮例1的情況：的情況： 假設(shè)設(shè)備臺時增加假設(shè)設(shè)備臺時增加10個臺時，即個臺時，即 b1變化為變化為310，這時可行，這時可行域擴(kuò)大，域擴(kuò)大，最優(yōu)解為最優(yōu)解為 x2 = 250 和和 x1 + x2 = 310 的交點(diǎn)的交點(diǎn) x1 = 60，x2 = 250 。 變化后的總利潤變化后的總利潤 - 變化前的總利潤變化前的總利潤 = 增加的利潤增加的利潤 (5060+ 100250) - (50 50+100 250) = 5

32、00 ，500 / 10 = 50 元元 說明在一定范圍內(nèi)每增加（減少）說明在一定范圍內(nèi)每增加（減少）1個臺時的設(shè)備能力就個臺時的設(shè)備能力就可增加（減少）可增加（減少）50元利潤，稱為該約束條件的對偶價格。元利潤，稱為該約束條件的對偶價格。70 假設(shè)原料假設(shè)原料 A 增加增加10 千克時，即千克時，即 b2變化為變化為410，這時可行域，這時可行域擴(kuò)大，但擴(kuò)大，但最優(yōu)解仍為最優(yōu)解仍為 x2 = 250 和和 x1 + x2 = 300 的交的交點(diǎn)點(diǎn) x1= 50，x2 = 250 。此變化對總利潤無影響。此變化對總利潤無影響。 解釋：解釋：原最優(yōu)解沒有把原料原最優(yōu)解沒有把原料 A 用盡，有用盡

33、，有50千克的剩余，因此增千克的剩余，因此增加加10千克值增加了庫存，而不會增加利潤。千克值增加了庫存，而不會增加利潤。 在一定范圍內(nèi)，當(dāng)約束條件右邊常數(shù)增加在一定范圍內(nèi)，當(dāng)約束條件右邊常數(shù)增加1個單位時（個單位時（P23） （1）若約束條件的對偶價格大于）若約束條件的對偶價格大于0，則其最優(yōu)目標(biāo)函數(shù)值得，則其最優(yōu)目標(biāo)函數(shù)值得到改善（變好）；到改善（變好）； （2）若約束條件的對偶價格小于）若約束條件的對偶價格小于0，則其最優(yōu)目標(biāo)函數(shù)值受，則其最優(yōu)目標(biāo)函數(shù)值受到影響（變壞）；到影響（變壞）； （3）若約束條件的對偶價格等于）若約束條件的對偶價格等于0，則最優(yōu)目標(biāo)函數(shù)值不變。，則最優(yōu)目標(biāo)函數(shù)值不

34、變。71線性規(guī)劃模型線性規(guī)劃模型72x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)4x1+ 6x2=48 2x1+ 2x2 =187318 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE目標(biāo)函數(shù)的系數(shù)目標(biāo)函數(shù)的系數(shù)34x1+ 40 x2= Z40 x2= - 34x1+ Zx2= -+34x1Z40407418 16 14 12 10 8

35、 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE目標(biāo)函數(shù)的系數(shù)目標(biāo)函數(shù)的系數(shù)34x1+ 40 x2= Z40 x2= - 34x1+ Zx2= -+c1x1Zc2c27518 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE目標(biāo)函數(shù)的系數(shù)目標(biāo)函數(shù)的系數(shù)34x1+ 40 x2= Z40 x2= - 34x1+ Zx2= -+c1x1Zc2c27618 16 14 12 10 8 6 4 2 0 |2468

36、1012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE(斜率斜率 = - 1)= - 1)( (斜率斜率 = - 2/3)= - 2/3)最優(yōu)解不變的范圍最優(yōu)解不變的范圍（設(shè)（設(shè)c1固定固定c2可變）可變）51343234122cc77目標(biāo)系數(shù)變化目標(biāo)系數(shù)變化 目標(biāo)線傾角改變；目標(biāo)線傾角改變；右邊項(xiàng)變化右邊項(xiàng)變化 約束線位置平移；約束線位置平移；在不引起最優(yōu)解改變在不引起最優(yōu)解改變的前提下允許變化的的前提下允許變化的范圍。范圍。78圖解法 (a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域無界可行域無界 唯一最優(yōu)解唯一最優(yōu)解多

37、個最優(yōu)解多個最優(yōu)解 唯一最優(yōu)解唯一最優(yōu)解 (d)可行域無界可行域無界 (e)可行域無界可行域無界 (f)可行域?yàn)榭占尚杏驗(yàn)榭占?多個最優(yōu)解多個最優(yōu)解 目標(biāo)函數(shù)無界目標(biāo)函數(shù)無界 無可行解無可行解79基本定理o 只要存在可行解，就一定存在頂點(diǎn)o 若目標(biāo)函數(shù)有最優(yōu)值，則最優(yōu)值必至少在某一頂點(diǎn)上達(dá)到o 頂點(diǎn)的個數(shù)是有限的，為(n!/m!(n-m)!)o 線性規(guī)劃問題的基可行解對應(yīng)于可行域的頂點(diǎn)80線性規(guī)劃問題的解的概念線性規(guī)劃問題的解的概念可行解： 變量滿足所有約束條件的一組值可行解集： 所有可行解構(gòu)成的集合可行域： 可行解集構(gòu)成n維空間的區(qū)域 0 xbAX0 xb,Ax|xD）（njxmibxat

38、sxcjnjijijnjjj,2,10),.,1(.zmax 11線性規(guī)劃問題TnxxxX),(2181解的概念最優(yōu)解： 使得目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解最優(yōu)值： 最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值目的： 求最優(yōu)解和最優(yōu)值CXZ max0. .XbAXts82 先研究AX=b基基(基矩陣基矩陣)：設(shè)系數(shù)矩陣A A是mn矩陣，秩為m，B B是A A中mm階非奇異子矩陣（即|B B|0），則稱B B是線性規(guī)劃問題的一個基基。(P68)B B 是由m個線性獨(dú)立的列向量組成),(21mrrrpppB), 2 , 1(mjxrj基向量 基變量非基變量： 其余變量83o 為不失一般性， 可設(shè)P68非基向量及非基變量非基向

39、量及非基變量P6984方程組的現(xiàn)令85非可行解非可行解可可行行解解基解基解基可行解基可行解基可行解基可行解滿足非負(fù)條件圖(1) 的基解, 稱為基可行解。上圖圖中的點(diǎn)0 , Q1 , Q2 , Q3 , Q4 代表基可行解?？梢? 基可行解的非零分量的數(shù)目也不大于m, 并且都是非負(fù)的。圖(1)86o 可行基o 對應(yīng)于基可行解的基, 稱為可行基。約束方程組具有基解的數(shù)目最多是 個。一般基可行解的數(shù)目要小于基解的數(shù)目。o 基解中的非零分量的個數(shù)小于m 個時, 該基解是退化解。在以下討論時, 假設(shè)不出現(xiàn)退化的情況。874 4、基解：取、基解：取B B = (p(p1 1,p,p2 2, ,p,pm m

40、) ) a a1111, ,a,a1m1m x x1 1 a a1m+11m+1, ,a,a1n1n x xm+1m+1 b b1 1 + + = a am1m1, ,a,ammmm x xm m a amm+1mm+1, ,a,amnmn x xn n b bm m 基基 基變量基變量 非基非基 非基變量非基變量 令令 x xm+1m+1 = = x xn n = 0 (0 (非基變量為非基變量為0)0) 則則 BXBXB B = b b )!( !mnmnCmn基解個數(shù)TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 個個基解：88

41、練習(xí)o 在下列的線性規(guī)劃問題中找出滿足約束條件的所有基本解.指出哪些是基本可行解,并代入目標(biāo)函數(shù),確定那一個是最優(yōu)解.0,376284327432max4321432143214321xxxxxxxxxxxxxxxx89o 解:4321,76214132ppppA0721322132,) 1 (1211BppB.1可作為基B2143jjjjjjxpbxp38213221xx2,121xx則且是基本可行解是滿足約束條件的基解則,0,0,2,11TX 90o 則01361126112,)2(2312BppB時令可作為基0,0.422xxB38611231xx1314,134521xxTX0,131

42、4,0,13452則是基解，但不是基本可行解. 01071427142,)3(3413BppB時令可作為基0,0.323xxB38714241xx57,53441xxTX57,0,0,5343是基解，且是基本可行解. 9101662136213,)4(4324BppB時令可作為基0,0.414xxB38621332xx167,164532xxTX0,167,1645,04是基解，且是基本可行解. 02972437243,)5(5425BppB時令可作為基0,0.315xxBTX297,0,2968,05是基解，且不是基本可行解. 9203176417641,)6(6436BppBTX3145,

43、31680,06是基解，但不是基本可行解. 16116,589,8:,4314,3,1ZZZXXX得代入目標(biāo)函數(shù)將為最優(yōu)解57,0,0,5343X93LP問題的求解：單純形法 基本思路：從一個基可行解轉(zhuǎn)換到另一個“更好”的基可行解上(“更好”：目標(biāo)函數(shù)值得到改善)，直到找到最優(yōu)解或者獲得無最優(yōu)解的信息（P67P67）94例題o 012416482. .32max21212121xxxxxxtsxxz、5 , 2 , 1012416482. .00032max524132154321jxxxxxxxxtsxxxxxzj54321,100400100400121pppppA543100010001

44、pppB9596979899初始基可行解的確定100101又因bi 0, 所以得到一個初始基可行解102最優(yōu)性檢驗(yàn)與解的判別（P71）103檢驗(yàn)數(shù)P71104P71105Maxz=-x1+x23x1-2x2+x3=1 2x1-x2+x4=1 xi0, i=1,2,3,4106基變換107108109110迭代(旋轉(zhuǎn)運(yùn)算)111112113114115o 最優(yōu)判別定理1：若所有檢驗(yàn)數(shù)0，則x是最優(yōu)解。定理2：若存在這樣一個檢驗(yàn)數(shù)0，它所對應(yīng)的列向量的全部分量均0，則所給問題的目標(biāo)函數(shù)值無下界，因而無最優(yōu)解。o 入基變量的確定正檢驗(yàn)數(shù)中，最大的檢驗(yàn)數(shù)對應(yīng)的變量先入基o 出基變量的確定最小比值法：b

45、i /aij (aij 0)，最小比值對應(yīng)的變量116單純形法的步驟o 將所給問題化為標(biāo)準(zhǔn)形o 找出一個初始基可行解,建立初始單純形表o 檢查所有檢驗(yàn)數(shù)(若全為非負(fù),則已得到最優(yōu)解,計(jì)算停止.否則繼續(xù)下一步)o 考察是否無解(若是,計(jì)算停止,否則繼續(xù)下一步)o 確定入基變量,出基變量o 對初始單純形表進(jìn)行單純形變換117單純形法的計(jì)算步驟o單純形法的思路118單純形法的計(jì)算步驟o 單純形表jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0 ijijjacc j 0 kjkjiiaab其其中中：119 o 例

46、1.8 用單純形法求下列線性規(guī)劃的最優(yōu)解0,30340243max21212121xxxxxxxxZ解：解：1）將問題化為標(biāo)準(zhǔn)型，加入松馳變量將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為則標(biāo)準(zhǔn)型為: 0,30340243max432142132121xxxxxxxxxxxxZ120單純形法的計(jì)算步驟o 2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。3)1020(3)(2141131 acacc1 檢驗(yàn)數(shù)檢驗(yàn)數(shù)j1213）進(jìn)行最優(yōu)性檢驗(yàn)o 4）從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇 ，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗(yàn)數(shù)大于0時

47、，一般選擇最大的一個檢驗(yàn)數(shù)，即： ，其對應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計(jì)算并選擇 ，選最小的對應(yīng)基變量作為換出變量。0j0|max jjk 0minikikiLaab如果表中所有檢驗(yàn)數(shù) ，則表中的基可行解就是問題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。0j122單純形法的計(jì)算步驟o 用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。o 5）重復(fù)3）、4）步直到計(jì)算結(jié)束為止。123單純形法的計(jì)算步驟j j j 換入列換入列bi /ai2，ai204010換換出出行行將將3化為化為15/311801/301/310

48、11/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011124 o 例1.9 用單純形法求解02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計(jì)算?？勺鳛槌跏蓟兞?，列單純形表計(jì)算。125單純形法的計(jì)算步驟j 201/3150120753017131/30902j 256011017/31/

49、31250128/9-1/92/335/300-98/9 -1/9 -7/3j 126練習(xí)o 214maxxxZ-X1+X22X1-4X24X1-2X28X1,X20127練習(xí)o 2123maxxxZ-X1+2X243X1+2X214X1-X23X1,X20128練習(xí)o P97 5(1) 5(2)129單純形法的計(jì)算步驟學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及3個基本定理2. 熟練掌握單純形法的解題思路及求解步驟130單純形法的進(jìn)一步討論人工變量法o人工變量法：o 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初

50、基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。131 o 例1.10 用大M法解下列線性規(guī)劃 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣，無法建單位矩陣，無法建立初始單純形表。立初始單純形表

51、。132 o 故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型： 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。 133 j j j j 134單純形法的進(jìn)一步討論人工變量法解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線 規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）

52、。3）無界解判別：某個k0且aik（i=1，2,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri0時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。135單純形法的進(jìn)一步討論人工變量法o 單純性法小結(jié):136停止停止A Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika對對任任一一)0( lklkiiaab 計(jì)計(jì)算算lkxx替替換換基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個個ax含有含有量中是否量中是否基變基變 0 j非非基基變變量量的的有有某某個個最最優(yōu)優(yōu)解解一一唯唯

53、 無無可可行行解解最優(yōu)解最優(yōu)解無窮多無窮多是是否否環(huán)環(huán)循循否否否否否否是是是是是是循環(huán)循環(huán)無無界界解解137 線性規(guī)劃模型的應(yīng)用o 一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。 要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù) 存在著多種方案 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述138人工變量法若約束條件全是型，化標(biāo)準(zhǔn)形時每個不等式都加上一個松馳變量，化為等式，而每個等式中的松馳變量正好構(gòu)成一組基變量，于是可以直接用單純形法若約束條件不全是型，即：含有或=時，不能找到一組基變量(或基變量個數(shù)不夠)，就必須用人工變量法人工變量法有兩種：大M法、兩階段法139大M法構(gòu)造輔助問題：Min z=cj xj + MR1 + MR2 + MRms.t. aij xj + Ri = bi ,i=1,2, m xj 0 , j=1,2,n定理：若輔助問題有最優(yōu)解，則當(dāng)輔助問題的最優(yōu)解中人工變量取值全部為0時，原問題才有最優(yōu)解(輔助問題最優(yōu)解去掉人工變量值),否則原問題無可行解。若輔助問題無最優(yōu)解，則原問題也無最優(yōu)解。140*M (同上)(同上)141故原問題的最優(yōu)解為(2，0)142兩階段法構(gòu)造