運籌學(xué)03-線性規(guī)劃

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

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

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

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

5、即符號，即 Min f - Max z92 2、約束條件不是等式的問題：、約束條件不是等式的問題： 設(shè)約束條件為設(shè)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進一個新的變量可以引進一個新的變量s s ，使它等于約束右，使它等于約束右邊與左邊之差邊與左邊之差 s = bi (ai1 x1 + ai2 x2 + + ain xn ) 顯然，顯然，s s 也具有非負(fù)約束，即也具有非負(fù)約束，即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當(dāng)約束條件為當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時，類似地令時，類似地令 s = (ai1 x1+ai2 x2+ +ain xn)- bi 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即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代入原問題代入原問題如果某個變量為自由變量（無非負(fù)限如果某個變量為自由變量（無非負(fù)限制），則可令制），則可令 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例：將線性規(guī)劃模型例：將線性規(guī)劃模型 Min Z = -X1+2X2 -3X3 X1+X2 +X3 7 s.t X1 -X2 +X3 2 X1，X2 0，X3無限制無限制 化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型四個方面考慮四個方面考慮17 圖解法的靈敏度分析圖解法的靈敏度分析 靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn)生的影響。18可用資源可用資源設(shè)備設(shè)備原料原料1原料原料2A B1 12 10 1單位利潤單位利潤50 100300臺時臺時400kg250kgA, B A

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

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

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

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

14、“管理運籌學(xué)”2.0版（Window版），是1.0版（DOS版）升級版。它包括15個子模塊：線性規(guī)劃運輸問題整數(shù)規(guī)劃目標(biāo)規(guī)劃對策論最短路徑最小生成樹 最大流量最小費用最大流關(guān)鍵路徑存儲論排隊論決策分析預(yù)測問題層次分析法243.1 軟件操作方法軟件操作方法例例1.目標(biāo)函數(shù)： 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 輸出結(jié)果分析輸出結(jié)果分析273.2 輸出結(jié)果分析輸出結(jié)果分析q本題中目標(biāo)函數(shù)的最優(yōu)值是

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

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

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

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

19、員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?324.1 人力資源分配問題人力資源分配問題 解：設(shè) xi 表示第i班次時開始上班的司機和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： 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一家中型的百貨商場，它對售貨員的需求經(jīng)過統(tǒng)計分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5

20、天，休息兩天，并要求休息的兩天是連續(xù)的。問應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？時間所需售貨員人數(shù)星期日28星期一15星期二24星期三25星期四19星期五31星期六28344.1 人力資源分配問題人力資源分配問題 解：設(shè) xi ( i = 1,2,7)表示星期一至日開始休息的人數(shù),這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： 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 生產(chǎn)計劃問題生產(chǎn)計劃問題 例3某公司面臨一個是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。 問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公

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

23、。 求 xi 的利潤：利潤 = 售價 - 各成本之和 產(chǎn)品甲全部自制的利潤 =23-(3+2+3)=15 產(chǎn)品甲鑄造外協(xié)，其余自制的利潤 =23-(5+2+3)=13 產(chǎn)品乙全部自制的利潤 =18-(5+1+2)=10 產(chǎn)品乙鑄造外協(xié)，其余自制的利潤 =18-(6+1+2)=9 產(chǎn)品丙的利潤 =16-(4+3+2)=7 可得xi （i = 1,2,3,4,5） 的利潤分別為15、10、7、13、9 元。374.2 生產(chǎn)計劃問題生產(chǎn)計劃問題通過以上分析,可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)： 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，問：應(yīng)如何下料，可使所用原料最?。?94.3 套材下料問題套材下料問題 設(shè) x1,x2,x3,x4,x5 分別為上面 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： 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某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資。已知：項目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過1

26、00萬元。 據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如表：問：問：a）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險系數(shù)為最小？項目ABCD風(fēng)險指數(shù)（次/萬元）1345.5414.4 投資問題投資問題 解：解： 1 1）確定決策變量：連續(xù)投資問題 設(shè) 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+