簡介與線性規(guī)劃(第一至四章)打印

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

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

3、10原料B400千克12原料A300臺時11設備資源限制III（下料問題）某工廠要做 100套鋼架，每套用長為 2.9米、2.1米、1.5米的圓鋼各一根。已知原配料每根長 7.4米。如何下料，可使所用原材料最??？（人員安排問題）某醫(yī)院根據(jù)日常工作統(tǒng)計，每晝夜 24小時中至少需要下列數(shù)量的護士。護士們分別在各時間段開始時上班，并連續(xù)工作 8小時，如何安排各時間段開始上班工作的人數(shù)，才能使護士的總人數(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)訂貨量，兩次訂貨的間隔時間以及年庫存成本。某公司從兩個產地 A1、A2將物品運往三個銷地 B1、B2、B3，各產地的產量、各銷地的銷量、各產地運往各銷地的每件物品的運費如表所示：200150150銷量（件）300556A2200646A1產量（件）B3B2B1運費單價? ? ABCD踶? 2 Y 夯Z 氽*糊疔yF ? 亜鯛 俬 : 俇踶; 弼? ? ? ? ? ? ? ? ? ? ? ? ?9119

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

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

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

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

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

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

11、根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應不大于0.2%，這兩個工廠都需要各自處理一部分工業(yè)污水，第一化工廠處理工業(yè)污水的成本是1000元/萬m3，第二化工廠處理工業(yè)污水的成本是800元/萬m3，現(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費用最?。?00萬m3500萬m3工廠2工廠114o1.確定決策變量：x x1 1, x x2 2 (x x1 1第一化工廠每天處理污水 , x x2 2為第二化工廠每天處理污水 )2.確定目標函數(shù)：Z=1000 x x1 1+800 x x2 23.尋找約束條件 o處理污水量限制 ：o環(huán)保限制：o 非負條件： 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市場調查公司（MSI）專門評定消費者對新產品、服務和廣告活動的反應。一個客戶要求MSI幫助確定消費者對一種近期推出的家居產品的反應?？蛻粢蟛扇€人入戶調查（分為日間調查和晚間調查），以從有孩家庭和無孩家庭獲得回答?？蛻舻暮贤笠罁?jù)以下條款進行1000個訪問：1）至少訪問400個有孩家庭；2）至少訪問400個無孩

13、家庭；3）晚間訪問的總數(shù)量至少等于日間訪問的數(shù)量；4）至少40%有孩家庭必須在晚間訪問；5）至少60%無孩家庭必須在晚間訪問。訪談成本見表所示。怎樣安排，才能既滿足合同要求，又成本最低？練習17 決策變量：對有孩家庭日間訪問的數(shù)量x1、對有孩家庭晚間訪問的數(shù)量x2、對無孩家庭日間訪問的數(shù)量x3、對無孩家庭晚間訪問的數(shù)量x4目標函數(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ù)學模型o 1. 每一個問題都用一組決策變量表示某一方案，這組變量的值就代表一個具體方案，一般這些變量的取值非負 決策變量o 2. 存在一定的限制條件(如供求關系，生產任務、資源限制等) ，它們可以用變量的線性等式或線性不等式來表示，這些條件稱為約束條件。 線性約束o 3. 都有一個要求達到的目標，它可以用變量的線性函數(shù)（稱為目標函數(shù)）來表示。根據(jù)需要要求目標函數(shù)最大化或最小化。 目標函數(shù)o -具有上面三個特征的問題是線性規(guī)劃問題19建模過程建模過程 （P12）o 1.理解要解決的問題，了解解題的目標和條件；o 2.

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

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

17、2627運運 輸輸 問問 題題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某廠在今后四個月內需租用倉庫堆存貨物。已知各個月所需的倉庫面積數(shù)如表1所示。又知，當租借合同期限越長時，場地租借費用享受的折扣優(yōu)待越大，有關數(shù)據(jù)如表2所示。租借倉庫的合同每月初都可辦理，每份合同應具體說明租借的場地面積數(shù)和租借期限。工廠在任何一個月初辦理簽約時，可簽一份，也可同時簽若干份租借場地面積數(shù)和租借期限不同的合同。

18、為使所付的場地總租借費用最少，試建立一個線性規(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）, , 是目標函數(shù)系數(shù)組成的行向量；是目標函數(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標準模型有四點要求：標準模型有四點要求：o 1目標函數(shù)求極大值；o 2除非負約束條件外，其他所有約束條件全為等式；o 3約束等式右端常數(shù)項bi非負；o 4決策變量取值非負。43如何化標準形？當碰到最小化問題，即當碰到最小化問題，即min z =CXmin z =CX化標準形的方法：令化標準形的方法：令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)值反號當約束條件是不等式當約束條件是不等式不等式左邊加減一個非負變量不等式左邊加減一個非負變量( (稱稱松馳變量松馳變量) )化為標準形化為標準形當某個當某個b bi i0=0 =0 ，替代，替代 x xk k 444546標準化練習o 無約束，3213213223213210, 063244239232minxxxxxxxxxxxxxxxz47答案o 0, 0, 0, 0, 0, 06332442239200332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxz48標準化練

22、習o P24 課后習題349LP問題的解的概念o 可行解：可行解：滿足約束條件的解滿足約束條件的解X=(xX=(x1 1，x x2 2，x xn n) )o 最優(yōu)解：最優(yōu)解：使目標函數(shù)達到最優(yōu)值的可行解使目標函數(shù)達到最優(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、應的變量對應的變量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為坐標向量建立直角坐標系。在直角坐標為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例系里，圖上任意一點的坐標代表了決策變量的一組值，例1 1的每的每個約束條件都代表一個半平面。個約束條件都代表一個半平面。52o （2）對每個不等式）對每個不等式(約束條件約束條件)，先取其等，先取其等式在坐標系中作直線，然后確定不等式所決式在坐標系中作直線，然后確定不等式所決定的半平面。定的半平面。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)解一定是在可行域的頂點上0500剩余量s302503*50+1*250 250原料Bs2=504002*50+1*250 350原料As1=03001*50+1*250 300設備臺時松馳變量值資源總量x150，x2250時用掉的資源量約束555657x1x25100788可行域最優(yōu)解101221 xx821 xx0,21xxs.t

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

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

28、化時，不會影響最優(yōu)解。會影響最優(yōu)解。67 靈敏度分析靈敏度分析：建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī)：建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產變化時，對最優(yōu)解產生的影響。生的影響。3.1 目標函數(shù)中的系數(shù)目標函數(shù)中的系數(shù) ci 的靈敏度分析的靈敏度分析 考慮例考慮例1的情況，的情況， ci 的變化只影響目標函數(shù)等值線的斜率，的變化只影響目標函數(shù)等值線的斜率，目標函數(shù)目標函數(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 目標函數(shù)等值線的斜率為目標函數(shù)等值線的斜率為 - (c1 / c2 ) ， 當當 -1 - (c1 / c2 ) 0 （*） 時，原最優(yōu)解仍是最優(yōu)解。時，原最優(yōu)解仍是最優(yōu)解。 68o假設產品假設產品的利潤的利潤100元不變，即元不變，即 c2 = 100，代到式（，代到式（*）并整理得并整理得 0 c1 100 o

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

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

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

33、，有50千克的剩余，因此增千克的剩余，因此增加加10千克值增加了庫存，而不會增加利潤。千克值增加了庫存，而不會增加利潤。 在一定范圍內，當約束條件右邊常數(shù)增加在一定范圍內，當約束條件右邊常數(shù)增加1個單位時（個單位時（P23） （1）若約束條件的對偶價格大于）若約束條件的對偶價格大于0，則其最優(yōu)目標函數(shù)值得，則其最優(yōu)目標函數(shù)值得到改善（變好）；到改善（變好）； （2）若約束條件的對偶價格小于）若約束條件的對偶價格小于0，則其最優(yōu)目標函數(shù)值受，則其最優(yōu)目標函數(shù)值受到影響（變壞）；到影響（變壞）； （3）若約束條件的對偶價格等于）若約束條件的對偶價格等于0，則最優(yōu)目標函數(shù)值不變。，則最優(yōu)目標函數(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目標函數(shù)的系數(shù)目標函數(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目標函數(shù)的系數(shù)目標函數(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目標函數(shù)的系數(shù)目標函數(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)解不變的范圍（設（設c1固定固定c2可變）可變）51343234122cc77目標系數(shù)變化目標系數(shù)變化 目標線傾角改變；目標線傾角改變；右邊項變化右邊項變化 約束線位置平移；約束線位置平移；在不引起最優(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ōu)解多個最優(yōu)解 目標函數(shù)無界目標函數(shù)無界 無可行解無可行解79基本定理o 只要存在可行解，就一定存在頂點o 若目標函數(shù)有最優(yōu)值，則最優(yōu)值必至少在某一頂點上達到o 頂點的個數(shù)是有限的，為(n!/m!(n-m)!)o 線性規(guī)劃問題的基可行解對應于可行域的頂點80線性規(guī)劃問題的解的概念線性規(guī)劃問題的解的概念可行解： 變量滿足所有約束條件的一組值可行解集： 所有可行解構成的集合可行域： 可行解集構成n維空間的區(qū)域 0 xbAX0 xb,Ax|xD）（njxmibxat

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

39、量及非基變量P6984方程組的現(xiàn)令85非可行解非可行解可可行行解解基解基解基可行解基可行解基可行解基可行解滿足非負條件圖(1) 的基解, 稱為基可行解。上圖圖中的點0 , Q1 , Q2 , Q3 , Q4 代表基可行解?？梢? 基可行解的非零分量的數(shù)目也不大于m, 并且都是非負的。圖(1)86o 可行基o 對應于基可行解的基, 稱為可行基。約束方程組具有基解的數(shù)目最多是 個。一般基可行解的數(shù)目要小于基解的數(shù)目。o 基解中的非零分量的個數(shù)小于m 個時, 該基解是退化解。在以下討論時, 假設不出現(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、練習o 在下列的線性規(guī)劃問題中找出滿足約束條件的所有基本解.指出哪些是基本可行解,并代入目標函數(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得代入目標函數(shù)將為最優(yōu)解57,0,0,5343X93LP問題的求解：單純形法 基本思路：從一個基可行解轉換到另一個“更好”的基可行解上(“更好”：目標函數(shù)值得到改善)，直到找到最優(yōu)解或者獲得無最優(yōu)解的信息（P67P67）94例題o 012416482. .32max21212121xxxxxxtsxxz、5 , 2 , 1012416482. .00032max524132154321jxxxxxxxxtsxxxxxzj54321,100400100400121pppppA543100010001

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

45、i /aij (aij 0)，最小比值對應的變量116單純形法的步驟o 將所給問題化為標準形o 找出一個初始基可行解,建立初始單純形表o 檢查所有檢驗數(shù)(若全為非負,則已得到最優(yōu)解,計算停止.否則繼續(xù)下一步)o 考察是否無解(若是,計算停止,否則繼續(xù)下一步)o 確定入基變量,出基變量o 對初始單純形表進行單純形變換117單純形法的計算步驟o單純形法的思路118單純形法的計算步驟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）將問題化為標準型，加入松馳變量將問題化為標準型，加入松馳變量x3、x4則標準型為則標準型為: 0,30340243max432142132121xxxxxxxxxxxxZ120單純形法的計算步驟o 2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。3)1020(3)(2141131 acacc1 檢驗數(shù)檢驗數(shù)j1213）進行最優(yōu)性檢驗o 4）從一個基可行解轉換到另一個目標值更大的基可行解，列出新的單純形表確定換入基的變量。選擇 ，對應的變量xj作為換入變量，當有一個以上檢驗數(shù)大于0時

47、，一般選擇最大的一個檢驗數(shù)，即： ，其對應的xk作為換入變量。確定換出變量。根據(jù)下式計算并選擇 ，選最小的對應基變量作為換出變量。0j0|max jjk 0minikikiLaab如果表中所有檢驗數(shù) ，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。0j122單純形法的計算步驟o 用換入變量xk替換基變量中的換出變量，得到一個新的基。對應新的基可以找出一個新的基可行解，并相應地可以畫出一個新的單純形表。o 5）重復3）、4）步直到計算結束為止。123單純形法的計算步驟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ù)學模型化為標準形式：解：將數(shù)學模型化為標準形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計算?？勺鳛槌跏蓟兞?，列單純形表計算。125單純形法的計算步驟j 201/3150120753017131/30902j 256011017/31/

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

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

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

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

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