第2章線性規(guī)劃與單純形法.

1、主講教師：馬越峰第二章線性規(guī)劃與單純形法 21線性規(guī)劃問題與數(shù)學(xué)模型 2.2圖解法 2.3線性規(guī)劃的應(yīng)用 24單純形法基本原理及計算步驟 25單純形法的進一步討論 2.6線性規(guī)劃的對偶問題B性規(guī)劃與單純形法2.1線形規(guī)劃（Linear Programming）!題及 其數(shù)學(xué)模型【引例】某工廠在計劃期內(nèi)要安排甲乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及 A. B 兩種 原材料的消耗，以及資源的限制如下表所示：甲乙資源限制設(shè)備11300 臺時原料 A21400 千克原料 B01250 千克單件利潤50 （元/件）100 （元/件）設(shè)生產(chǎn)甲產(chǎn)品勺個，生產(chǎn)乙產(chǎn)品X2個目標(biāo)函數(shù) max Z= 5

2、0 x1+100X2Xj+x2300 2X:+X2400約束條件問:工廠應(yīng)分別生產(chǎn)多少個產(chǎn)品甲.乙才能使工廠獲利最多？X20,X20線性規(guī)劃模型1 適用條件:（1） 優(yōu)化條件:問題目標(biāo)最大化、最小化的要求；（2） 約束條件:問題目標(biāo)受一系列條件的限制；（3） 選擇條件:實現(xiàn)目標(biāo)存在多種備選方案；（4） 非負(fù)條件的選擇:根據(jù)問題的實際意義決定是否非負(fù)。2.構(gòu)建線性規(guī)劃模型的步驟（1）科學(xué)選擇決策變量（2） 明確目標(biāo)要求（3） 根據(jù)實際問題的背景材料，找出所有的約束條件（4） 確定是否增加決策變量的非負(fù)條件線性規(guī)劃模型表示形式（1） 一般形式：Max（Min）Z = cxxx+c2x2H-cnxn

3、+ 勺2尤2 + （或 n，=）ba2X+ a22X2 + + 2nXH（或b2S.t.+a,n2X2 + +蘭（或亠=）bmx/J = l,2,-,n）決策變量；?/；= 1,2,/?）一目標(biāo)函數(shù)系數(shù)、價值系數(shù)或費用系數(shù)；= 1,2,，加）一右端項或資源常數(shù)；呦（i = 1,2,，加;）=1,2,，n）一稱為約束系數(shù)或技術(shù)系數(shù)。(3)(4)集合形式:向量形式:Max(Min)Z =j=i工匕內(nèi) 5(或=總)b：(i = 12) / 0(j = 1,2,)nMax(Min)Z=工兮形fn/=】I 2Pjxj- 或=亠)bXj(丿=1,2,丿)矩陣形式：MaxMin)Z = CX f/AX) h

4、Lt.0X =X2A =(%*)，(丿=12/)c =【例】將線性規(guī)劃模型一般表達式化為矩陣形式。Ma.xZ = 70X + 65X2?X + 3x2 S 210設(shè)：X =(xpx2)rC = (CpC2) =(70,65)4x + 5x 200M丿2xt+4X2 0, x2 0bib21273_22=4532-24Z 丿210=200180 7 3rri2104 52002 4匕2180解： MorZ = (70,65)MaxZ = CX(AX 0對于只有兩個決策變量的線性規(guī)劃問題， 可以在平面直角 坐標(biāo)系上作圖表示線 性規(guī)劃問題的有關(guān)概 念，并求解。下面通過例 1 詳細(xì)講解其方法：約束條件

5、：s.t.X +x2300(A)2 +x20(D)x20(E)得到最優(yōu)解：X = 50, x2= 250最優(yōu)目標(biāo)值Z =27500(1)分別取決策變量X丄，X2為坐標(biāo)向量建立直角坐標(biāo)系。 在直角朋標(biāo)系里，圖上任意一點的處標(biāo)代表了決策變量的 一組值，例1的每個約朿條件都代表一個半平面。例1目標(biāo)函數(shù)：Max z = 50 x1+ 100 x2步驟：（2）對每個不等式（約束條件），先取其等式在朋標(biāo)系中作 直線，然后確定不等式所決定的半平面。4）日標(biāo)函數(shù)Z=50XI+100X2,當(dāng)z取某一固左值時得到一條 直線，卓線上的每一點那負(fù)冇相同的目標(biāo)函數(shù)值，程之為 “等值線”。平行移動辱值線，當(dāng)移動到B螢硏z

6、卷可行 域內(nèi)實現(xiàn)了最大化。A, B, C, D, E是可行域的頂點， 對有限個約束條件則其町行域的頂點也是有限的。解的幾種可能結(jié)果A 唯一最優(yōu)解解無窮多個最優(yōu)解無界解（可行域無界，常為模型遺漏了某些 必要的約束條件）無可行解（可行域為空集，約束條件自相矛 盾，資源滿足不了人們的需求）可行解:滿足LP問題所有約束條件的解 最優(yōu)解:滿足目標(biāo)要求的可行解無界解max z = x+ x22x+ x 1令z =_zMaxZ= -藝CJXJ=藝（-勺）Xj/= /=no=9召+。兀+ + 兀7+仏2.約束條件為不等式：毎為+耳2兀+ + % bi引進剩余變量&anxi +ai2x2 + +ainX

7、n7= bj4.決策變量為自由變量：令Xj =u v u 0, v 05.約束右端項為負(fù)：兩端乘-1：-州斗_絳2勺-%心=-0引入松馳變量（含義是資源的剩余量）【引例】中引入S,s2, S3模型化為目標(biāo)函數(shù)：Max約束條件：s.t.z = 50 X + 100 X2 + 0 S + 0 S2 + 0 S3x +x2+ s1= 3002 x1+x2+ s2= 400 x2+ s3= 250 s5S2 , S3 0對于最優(yōu)解=50 x2= 250 , S = 0 s2=50 s3= 0說明：生產(chǎn)50單位I產(chǎn)品和250單位II產(chǎn)品將消耗完所有可能的設(shè)備臺時數(shù)及原料B,但對原料A則還剩余50千克?！?/p>

8、例】將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)式MinZ = 3xx+ 5X2 x3_ X + 2-9-2xx+ x分 +3xy 4 SJ. -6x 0, “無約束解：-(l)-r,O,.S無約束令 K =一兒兀3=歹2歹3 J涉MinZ = _3y + 5x2- y2+ y3才+-6兀，兀no(2)MinZf= Max(-Z) = 3”一5x2+ y2 y3(3) 3必 +2X2 y2+ y3 63yi-2x2+ y2-y30Max(Z) = 3y, 5x2+ y2y, + x2+ x4=92y+ x2+ 3y2+ 3y3-x5=4 $F0習(xí)題1用圖解法求解下列LP問題(1) minZ=6XJ+4X22X+X

9、?3Xj+4x23X, x20(2)maxZ= 3xr2x2X+X? 12X+2X24X,x202、對下面 LP 問題(1) 用圖解法求解(2) 寫出此問題的標(biāo)準(zhǔn)形式(3) 求剩余變量的值minZ=llx1+8x2s.t. 10X1+2X220 3XX+3X218 4XX+9X236xlzx20圖解法的靈敏度分析 1、目標(biāo)函數(shù)中的系數(shù)G的靈敏度分析分析G在什么范圍內(nèi)變化，原最優(yōu)解不變C=50C2=100直線BC的斜截式為：X2二-X+300斜率為-1直線BF的斜截式為：x2= Oxx:+250斜率為0目標(biāo)函數(shù)Z=c1x1+c2x2的斜截式為:x2= cl/c2xi+z/c；斜率為-ct/c2所

10、以，當(dāng)-1W -Ci/c20H寸，頂點B仍然是最 優(yōu)解假設(shè)c2不變，則有-1W -c/100 W0 ,解之 得OWCiWlOO練習(xí):計算 C2 在什么范圍內(nèi)變化時頂在什么范圍內(nèi)變化時頂點點 B 仍然是最優(yōu)解仍然是最優(yōu)解2、約束條件右邊 b 系數(shù)的靈敏度分析b 變化時通常引起可行域的變化從而引起最優(yōu)解的變化 設(shè)例 1 中的設(shè)備臺時增加了 10 個臺時數(shù)， 則約束變?yōu)椋?X+X2- - - - -X3 +x2s+x5孫Tllnxxxtx.XBeXBxp【練習(xí)】某中型百貨商場對售貨人員的需求統(tǒng)計如下表, 并規(guī)定售貨員每周工作 5 天且連續(xù)休息 2 天， 問如何安排 人員的作息既滿足工作需要又使配備人

11、員最少？時間所需售貨員人數(shù)星期日28星期一15星期二24星期三25星期四19星期五31星期六28解：設(shè)X為星期一開始休息的人數(shù),X2為星期二開 始休息的人數(shù)，X7為星期日開始休息的人數(shù) 目 標(biāo)函 C：minZ=X1+X2+X3+X4+X5+X6+X7X1+X2+X3+X4+X528X2+X3+X4+X5+X615X3+X4+X5+X6+X724X4+X5+X6+X7+ Xx25X5+X6+X7+ X1+X219X6+X7+ X1+X2+X331X7+X1+X2+X3+X428Xj 0最優(yōu)解:Xi =12 X2=0 x3=ll X4=5X5=0 X6=8 X7=0他、某公司生產(chǎn)甲， 乙，丙三種產(chǎn)

12、品，這三種產(chǎn)品都要經(jīng)過鑄造，機加工和裝配三個 車間。甲乙兩種產(chǎn)品的鑄件可以外包協(xié)作也 可自行生產(chǎn)，但丙產(chǎn)品必須本廠鑄造才能保 證質(zhì)量。有關(guān)情況見下表；公司中可利用的 總工時為鑄造 8000 小時機加工 12000 小時和 裝配10000 小時。公司為了獲得最大利潤， 甲，乙，丙三種產(chǎn)品各生產(chǎn)多少件，甲乙兩 種產(chǎn)品的鑄造應(yīng)多少由本公司完成？多少由 外包協(xié)作？二生產(chǎn)計劃問題工時與成本甲乙丙每件鑄造工時5107每件機加工工時648每件裝配工時322自產(chǎn)鑄件每件成本354外協(xié)鑄件每件成本56機加工每件成本213裝配每件成本322每件產(chǎn)品售價231816解:設(shè) X, x2,勺分別為三道工序都由本公司加工

13、的 甲，乙，丙三袖產(chǎn)品的件數(shù)，設(shè)分別為由外 協(xié)鑄造再由本公司機加工和裝配的甲乙兩種產(chǎn)品的 件數(shù)。計算每件產(chǎn)品的利潤分別如下:產(chǎn)品甲全部自制的利潤=23.產(chǎn)品甲鑄造外協(xié)， 其余自制的利潤=23- 產(chǎn)品乙全部自制的利潤=18-產(chǎn)品乙鑄造外協(xié)， 其余自制的利潤=18- 產(chǎn)品(3+2+3) =15(5+2+3) =13(5+1+2) =10(6+1+2) =9(4+3+2) =7丙的利潤=16-目標(biāo)函數(shù)：max Z= 15Xi +10X2+ 7X3+13 X4+9X55X + 10X2+ 7X380006X + 4X2+ 8X3+6 X4+4X5 12000 3Xx+ 2X2+2 X3+ 3X4+2X

14、50三套裁下料問題例3、某工廠要做100套鋼架，每套用29m. 2-1m和1 5m的原鋼各一根。已知原料每根長7 4m,問應(yīng)如何下料，可使所用原料最省。下料方案IIIIIIIVV2-9120102-1002211-531203合計7-47-37-27-16-6余料00-10-20-30-8設(shè)按各方案下料的原材料根數(shù)分別為目標(biāo)函數(shù)：min Z= Xi + X2+ X3+ X4+X5約束條件：Xi +2X2+ X41002X3 + 2X4 +X51003Xi + X2+ 2X3+3X5100Xt, X2, X3, X4, X50最優(yōu)解X=30 X2=10 X3=0X4=50X5=0Z=90例 4、某部門現(xiàn)有資金 200 萬元，今后五年內(nèi)考慮以下的 項目投資，已知項目 A：第一年到第五年年初都可投資, 當(dāng)年末能收回本利 110%o 已知項目 B：第一年到第四 年年初都可投資，次年末能收回本利 125%,但規(guī)定每 年最大投資額不能超過 30 萬元。項目