1、1 線性規劃問題的標準形式線性規劃問題的標準形式0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目標函數目標函數約束條件約束條件(1) 線性規劃模型一般形式線性規劃模型一般形式2價值系數價值系數決策變量決策變量技術系數技術系數右端常數右端常數0,b,bbxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMaxm21nmnmnmmnnnnnn0,.21221122222121112121112211(2) 線性規劃模型標準形式線性規劃模型標準形式3簡記形式簡記形式nj

2、xmibxatsxcZMaxjinjjijnjjj, 2 , 10, 2 , 1.11(3) 線性規劃模型其它形式線性規劃模型其它形式4矩陣形式矩陣形式0.XbAXtsCXZMaxncccC21mnmmnnaaaaaaaaaA212222111211nxxxX21價值向量價值向量決策向量決策向量系數矩陣系數矩陣mbbbb21右端向量右端向量5ncccC21nxxxX21價值向量價值向量決策向量決策向量mbbbb21右端向量右端向量向量形式向量形式0.1XbxPtsCXZMaxjnjjnjjjjaaaP21列向量列向量6對于各種非標準形式的線性規劃問題，我們總可對于各種非標準形式的線性規劃問題，

3、我們總可以通過以下變換，將其轉化為標準形式以通過以下變換，將其轉化為標準形式: :(4) 一般型向標準型的轉化一般型向標準型的轉化l目標函數目標函數l目標函數為極小化目標函數為極小化l約束條件約束條件l分兩種情況：大于零和小于零分兩種情況：大于零和小于零l決策變量決策變量l可能存在小于零的情況可能存在小于零的情況7(4) 一般型向標準型的轉化一般型向標準型的轉化SLPSLP的特點的特點n（1 1）目標函數目標函數取極大取極大n（2 2）所有）所有約束條件約束條件均由等式表示均由等式表示n（3 3）所有）所有決策變量決策變量取非負值取非負值n（4 4）每一約束的）每一約束的右端常數右端常數( (

4、資源向量的分資源向量的分量量) )均為非負值均為非負值線性規劃問題標準形式的特點線性規劃問題標準形式的特點81.1.極小化目標函數的問題：極小化目標函數的問題： 設目標函數為設目標函數為 Min f = c1x1 + c2x2 + + cnxn 則可以令則可以令z z -f-f ，該極小化問題與下面的，該極小化問題與下面的極大化問題有相同的最優解，即極大化問題有相同的最優解，即 Max z = -c1x1 - c2x2 - - cnxn 但必須注意，盡管以上兩個問題的最優解但必須注意，盡管以上兩個問題的最優解相同，但他們最優解的目標函數值卻相差一個相同，但他們最優解的目標函數值卻相差一個符號，

5、即符號，即 Min f - Max z92 2、約束條件不是等式的問題：、約束條件不是等式的問題： 設約束條件為設約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進一個新的變量可以引進一個新的變量s s ，使它等于約束右，使它等于約束右邊與左邊之差邊與左邊之差 s = bi (ai1 x1 + ai2 x2 + + ain xn ) 顯然，顯然，s s 也具有非負約束，即也具有非負約束，即s s00， 這時新的約束條件成為這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+s = bi 變量變量 s s 稱為稱為松弛變量松弛變量10lMax Z=40X1+

6、 50X2 X1 +2X2 30 s.t 3X1 +2X2 60 引入引入松弛變量松弛變量X3、 X4、X5 2X2 24 X1 , X2 0 0lMax Z=40X1+ 50X2+0 X3 +0 X4+0 X5 X1 +2X2 + X3 30 s.t 3X1 +2X2 + X4 60 2X2 + X5 24 X1 , X5 0 011當約束條件為當約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時，類似地令時，類似地令 s = (ai1 x1+ai2 x2+ +ain xn)- bi 顯然，顯然，s 也具有非負約束，即也具有非負約束，即s0，這時新的約，這時新的約束條件成為束

7、條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi變量變量s s稱為稱為剩余變量剩余變量12Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2X4 12 s.t X1+ X2+7X3+5X4 14 2X2+ X3+3X4 8 X1 , , X4 0 0引入引入剩余變量剩余變量：X5、X6、X7Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2X4 - X5 12 s.t X1+ X2+7X3+5X4 - X6 14 2X2+ X3+3X4 - X7 8 X1 , , X7 0 0133. 決策變量決策變量如果某個變量的約束條

8、件為如果某個變量的約束條件為jjlx 或者或者jjlx 可令可令jjjlxy或者或者jjjxly代入原問題代入原問題如果某個變量為自由變量（無非負限如果某個變量為自由變量（無非負限制），則可令制），則可令 0,jjjjjxxxxx0jl且且14 X1+X2 5s.t -6 X1 10 X2 0 0令令 X1 = X1 +6 -6+6 X1+6 10+6 0 X1 16 X1 +X2 11s.t X1 16 X1 , X2 0 015 3X1+2X2 8 s.t X1 -4X2 14 X2 0,0, X1 無限制無限制 令令X1= X1- X1 3 X1 -3 X1 +2X2 8 s.t X1

9、- X1 - 4X2 14 X1 , X1 ,X2 0 016例：將線性規劃模型例：將線性規劃模型 Min Z = -X1+2X2 -3X3 X1+X2 +X3 7 s.t X1 -X2 +X3 2 X1，X2 0，X3無限制無限制 化為標準型化為標準型四個方面考慮四個方面考慮17 圖解法的靈敏度分析圖解法的靈敏度分析 靈敏度分析：建立數學模型和求得最優解后，研究線性規劃的一個或多個參數（系數）ci , aij , bj 變化時，對最優解產生的影響。18可用資源可用資源設備設備原料原料1原料原料2A B1 12 10 1單位利潤單位利潤50 100300臺時臺時400kg250kgA, B A

10、, B 各生各生產多產多少少, , 可獲可獲最大最大利潤利潤? ?1 目標函數中的系數目標函數中的系數 ci 的靈敏度分析的靈敏度分析 考慮上例的情況， ci 的變化只影響目標函數等值線的斜率，目標函數 z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率為0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率為 -1 )之間時，原最優解 x1 = 50，x2 = 250 仍是最優解。n一般情況： z = c1 x1 + c2 x2 寫成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目標函數等值線的斜率為 - (c1 / c2 ) ，

11、 當 -1 - (c1 / c2 ) 0 （*） 時，原最優解仍是最優解。20n假設產品的利潤100元不變，即 c2 = 100，代到式（*）并整理得 0 c1 100 n假設產品的利潤 50 元不變，即 c1 = 50 ，代到式（*）并整理得 50 c2 + n假若產品、的利潤均改變，則可直接用式（*）來判斷。n假設產品、的利潤分別為60元、55元，則 - 2 - (60 / 55) - 1 那么，最優解為 300 = x1 + x2 和 400 = 2 x1 + x2 的交點 x1 = 100，x2 = 200 。21 2 約束條件中右邊系數約束條件中右邊系數 bj 的靈敏度分析的靈敏度分

12、析 當約束條件中右邊系數 bj 變化時，線性規劃的可行域發生變化，可能引起最優解的變化。 考慮例1的情況： 假設設備臺時增加10個臺時，即 b1變化為310，這時可行域擴大，最優解為 x2 = 250 和 x1 + x2 = 310 的交點 x1 = 60，x2 = 250 。 變化后的總利潤 - 變化前的總利潤 = 增加的利潤 (5060+ 100250) - (50 50+100 250) = 500 ， 500 / 10 = 50 元 說明在一定范圍內每增加（減少）1個臺時的設備能力就可增加（減少）50元利潤，稱為該約束條件的對偶價格。22 假設原料 A 增加10 千克時，即 b2變化為

13、410，這時可行域擴大，但最優解仍為 x2 = 250 和 x1 + x2 = 300 的交點 x1 = 50，x2 = 250 。此變化對總利潤無影響，該約束條件的對偶價格為 0 。 解釋：原最優解沒有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫存，而不會增加利潤。 在一定范圍內，當約束條件右邊常數增加1個單位時 （1）若約束條件的對偶價格大于0，則其最優目標函數值得到改善（變好）； （2）若約束條件的對偶價格小于0，則其最優目標函數值受到影響（變壞）； （3）若約束條件的對偶價格等于0，則最優目標函數值不變。23線性規劃問題的計算機求解線性規劃問題的計算機求解 隨書軟件為

14、“管理運籌學”2.0版（Window版），是1.0版（DOS版）升級版。它包括15個子模塊：線性規劃運輸問題整數規劃目標規劃對策論最短路徑最小生成樹 最大流量最小費用最大流關鍵路徑存儲論排隊論決策分析預測問題層次分析法243.1 軟件操作方法軟件操作方法例例1.目標函數： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)253.1 軟件操作方法軟件操作方法263.2 輸出結果分析輸出結果分析273.2 輸出結果分析輸出結果分析q本題中目標函數的最優值是

15、27500，x1=50, x2=250。q相差值表示相應的決策變量的目標系數需要改進的數量，使得決策變量為正值，當決策變量已為正數時，相差數為零。q松弛/剩余變量的數值表示還有多少資源沒有被使用。如果為零，則表示與之相對應的資源已經全部用上。q對偶價格表示其對應的資源每增加一個單位，將增加多少個單位的最優值。q目標函數系數范圍表示最優解不變的情況下，目標函數的決策變量系數的變化范圍。當前值是指當前的最優解中的系數取值。q常數項范圍是指約束條件的右端常量。上限值和下限值是指當約束條件的右端常量在此范圍內變化時，與其對應的約束條件的對偶價格不變。當前值是指現在的取值。 以上計算機輸出的目標函數系數

16、和約束條件右邊值的靈敏度分析都是在其他系數值不變，只有一個系數變化的基礎上得出的！283.2 輸出結果分析輸出結果分析2.當有多個系數變化時，需要進一步討論。 百分之一百法則：對于所有變化的目標函數決策系數（約束條件右邊常數值），當其所有允許增加的百分比與允許減少的百分比之和不超過100%時，最優解不變（對偶價格不變，最優解仍是原來幾個線性方程的解）。 * 允許增加量 = 上限 - 現在值 c1 的允許增加量為 100 - 50 = 50 b1 的允許增加量為 325 - 300 = 25 * 允許減少量 = 現在值 - 下限 c2 的允許減少量為 100 - 50 = 50 b3 的允許減少

17、量為 250 - 200 = 50 * 允許增加的百分比 = 增加量 / 允許增加量 * 允許減少的百分比 = 減少量 / 允許減少量 293.2 輸出結果分析輸出結果分析 例：例： c1 變為 74 , c2 變為 78, 則 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最優解不變。 b1 變為 315 , b3 變為 240, 則 (315 - 300) / 25 + (250 - 240 ) / 50 = 80%，故對偶價格不變（最優解仍是原來幾個線性方程的解）。在使用百分之一百法則進行靈敏度分析時，要注意：1）當允許增加量（允許減少量）為無窮大時，

18、則對任意增加量（減少量），其允許增加（減少）百分比均看作0；2）百分之一百法則是充分條件，但非必要條件；也就是說超過100%并不一定變化；3）百分之一百法則不能用于目標函數決策變量系數和約束條件右邊常數值同時變化的情況。這種情況下，只有重新求解。30線性規劃在工商管理中的應用線性規劃在工商管理中的應用n1 1 人力資源分配的問題n2 2 生產計劃的問題n3 3 套裁下料問題n4 4 投資問題314.1 人力資源分配問題人力資源分配問題 例1某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下： 設司機和乘務人員分別在各時間段一開始時上班，并連續工作八小時，問該公交線路怎樣安排司機和乘務人

19、員，既能滿足工作需要，又配備最少司機和乘務人員?324.1 人力資源分配問題人力資源分配問題 解：設 xi 表示第i班次時開始上班的司機和乘務人員數,這樣我們建立如下的數學模型。 目標函數： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0334.1 人力資源分配問題人力資源分配問題 例2一家中型的百貨商場，它對售貨員的需求經過統計分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5

20、天，休息兩天，并要求休息的兩天是連續的。問應該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數最少？時間所需售貨員人數星期日28星期一15星期二24星期三25星期四19星期五31星期六28344.1 人力資源分配問題人力資源分配問題 解：設 xi ( i = 1,2,7)表示星期一至日開始休息的人數,這樣我們建立如下的數學模型。 目標函數： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 約束條件：s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x

21、7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 0354.2 生產計劃問題生產計劃問題 例3某公司面臨一個是外包協作還是自行生產的問題。該公司生產甲、乙、丙三種產品，都需要經過鑄造、機加工和裝配三個車間。甲、乙兩種產品的鑄件可以外包協作，亦可以自行生產，但產品丙必須本廠鑄造才能保證質量。數據如表。 問：公司為了獲得最大利潤，甲、乙、丙三種產品各生產多少件？甲、乙兩種產品的鑄造中，由本公

22、司鑄造和由外包協作各應多少件？甲乙丙資 源 限 制鑄 造 工 時 (小 時 /件 )51078000機 加 工 工 時 (小 時 /件 )64812000裝 配 工 時 (小 時 /件 )32210000自 產 鑄 件 成 本 (元 /件 )354外 協 鑄 件 成 本 (元 /件 )56-機 加 工 成 本 (元 /件 )213裝 配 成 本 (元 /件 )322產 品 售 價 (元 /件 )231816364.2 生產計劃問題生產計劃問題 解：設 x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產品的件數，x4,x5 分別為由外協鑄造再由本公司加工和裝配的甲、乙兩種產品的件數

23、。 求 xi 的利潤：利潤 = 售價 - 各成本之和 產品甲全部自制的利潤 =23-(3+2+3)=15 產品甲鑄造外協，其余自制的利潤 =23-(5+2+3)=13 產品乙全部自制的利潤 =18-(5+1+2)=10 產品乙鑄造外協，其余自制的利潤 =18-(6+1+2)=9 產品丙的利潤 =16-(4+3+2)=7 可得xi （i = 1,2,3,4,5） 的利潤分別為15、10、7、13、9 元。374.2 生產計劃問題生產計劃問題通過以上分析,可建立如下的數學模型:目標函數： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約束條件： 5x1 + 10 x2 +

24、 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0384.3 套材下料問題套材下料問題 例5某工廠要做100套鋼架，每套用長為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：應如何下料，可使所用原料最??？394.3 套材下料問題套材下料問題 設 x1,x2,x3,x4,x5 分別為上面 5 種方案下料的原材料根數。這樣我們建立如下的數學模型。 目標函數： Min x1 + x2 + x3 + x4 + x5 約束條件： s.t.

25、 x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0404.4 投資問題投資問題例8某部門現有資金200萬元，今后五年內考慮給以下的項目投資。已知：項目A：從第一年到第五年每年年初都可投資，當年末能收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規定最大投資額不能超過1

26、00萬元。 據測定每萬元每次投資的風險指數如表：問：問：a）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎上使得其投資總的風險系數為最??？項目ABCD風險指數（次/萬元）1345.5414.4 投資問題投資問題 解：解： 1 1）確定決策變量：連續投資問題 設 xij ( i = 15，j = 14)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24424.4 投資問題投資問題2 2）約束條件：）約束條件：第一年：x11+ x12 = 200；第二年：x21 + x22+