[理學(xué)]運(yùn)籌學(xué)清華大學(xué)課件第一章-文庫(kù)吧資料
2024-10-25 00:36本頁(yè)面
【正文】 Q3(2,3) x2 x1 ① ② Q1 Q2(4,2) ③ Q3(2,3) Q4 * O(0,0) 45 167。 1 θ m z z0 σ 1 0 θ 1 ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ +m xn+m bm am1 xn+m +1 xn+1 b1 a11 +m θ x1 + 0xn+m z = Z0 ?????????????????mn,2,1j0xbxxaxczm axjiinn1jjijmn1jjj?，設(shè)40 建立單純形表 cB xB b c1 + +mxn+m z = 0 σ 1x1 + ? 2x2 + + amnxn + xn+m = bm +m c1x1 + c2x2 + + a1nxn + xn+1 = b1 +1 a21x1 + a22x2 + 則，若、入基變量kkjj x?? ?? 0m a x1 基變換 38 旋轉(zhuǎn)運(yùn)算（消元運(yùn)算） a1k’ 0 ┆ ┆ al1k’ 0 pk’ = （ alk’） （ 1） al+1k’ 0 ┆ ┆ amk’ 0 得到基可行解，重復(fù) —， 求出最優(yōu)解。39。39。39。39。 ..的檢驗(yàn)數(shù)為稱 jj x?kx 0?k?njj ,1,0 ??????0?kp0?j? 0?k?kx37 ? ?為主元出基行對(duì)應(yīng)的變量則若、出基變量 0m i nm i n0239。 3 單純形法 基本思路： 從可行域的一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)迭代求最優(yōu)解。 定理 3 若線性規(guī)劃有解，則一定存在基可行解為最優(yōu)解。,xn(1))T ∈ D； X(2)=(x1(2),x2(2), 1k1 ii ???????? k1i) i (i XX 基本定理 定理 1 若線性規(guī)劃存在可行域，則 : 可行域 D = {X|AX = b,X ≥ 0}為凸集。,k， 使 ,則稱 X為 X(i)(i=1,2, (0α 1) 注：頂點(diǎn)所對(duì)應(yīng)的解是基可行解。（ 0α 1） 非凸集 X(1) X(1) X(2) X(2) 凸集 X(1) X(2) X(2) X(1) 29 頂點(diǎn)： X∈ K， X(1)∈ K， X(2)∈ K (任意兩點(diǎn) )。 2 線性規(guī)劃問(wèn)題的幾何意義 基本概念 凸集：設(shè) K為 En(n維歐式空間 )的一點(diǎn)集， X(1)∈ K， X(2)∈ K。 O(0,0) Q1(4,0) Q2(4,2) Q4(0,3) Q3(2,3) Q5(4,3) 可行基 基可行解對(duì)應(yīng)的 B為可行基。 = xn = 0 (非基變量為 0) 則 BXB = b ∴ )!(!!mnmnC mn ???基解個(gè)數(shù)TmnmTmBxxxXxxxbBX)0,0,(),(m )0()0(2)0(1)0()0(2)0(11??? ??? ??? ?? ??個(gè)個(gè)基解：?????27 基可行解 滿足 ③ 式要求的基解。,amm xm amm+1,a1m x1 a1m+1, 26 基解：取 B = (p1,p2,amj)T 則稱 x1,x2, 取 B = (p1,p2, (3)無(wú)約束變量 令 xk = xk’ xk”， xk’,xk” ≥ 0， 代入即可。,bm)T 為系數(shù)矩陣 212222111211????????????????????????????mnmmnnaaaaaaaaaA23 標(biāo)準(zhǔn)型的化法 (1)min→max ∵ min z = cx = max(z) ∴ max(z) = min z = cx 令 z’ = z 則 max z’ = cx (2)不等式 (≤ ， ≥) 對(duì)于 “ ≤ ” 情況：在 “ ≤ ” 左邊加上一個(gè)松弛變量 （ 非負(fù) ）， 變?yōu)榈仁剑? 對(duì)于 “ ≥ ” 情況：在 “ ≥ ” 左邊減去一個(gè)剩余變量 （ 非負(fù) ） ， 變?yōu)榈仁?。,xn)T C = (c1,c2, + amnxn = bm x1， x2， + a1nxn = b1 a21x1 + a22x2 + 1 1 2 4 x1 x2 20 線性規(guī)劃的標(biāo)準(zhǔn)型 標(biāo)準(zhǔn)型 max z = c1x1 + c2x2 + 即無(wú)可行解。 在實(shí)際問(wèn)題中，可能 是缺少約束條件。 x2 x1 ② Q1 Q2(4,2) ③ Q3(2,3) Q4 o 4 3 * ① 18 (3)無(wú)界解 [] max z = 2x1 + 3x2 4x1 ≤ 16 x1， x2 ≥ 0 則 x2 → ∞ ， z → ∞ 。 (2)無(wú)窮多最優(yōu)解 [] 對(duì) ， 若目標(biāo)函數(shù) z = 2x1 + 4x2， 此時(shí)表示 目標(biāo)函數(shù)的直線與表示 條件 ① 的直線平行 ， 最優(yōu)點(diǎn)在線段 Q3Q2上 。 Q2點(diǎn)坐標(biāo)為 (4， 2)。 * 可見(jiàn)，在 Q2點(diǎn) z取到最大值。j=1,… ,n) . 15 圖解法 []用圖解法求 。 (3)約束條件 一組線性不等式 。 xn 。 + amnxn ≤(=, ≥) bm x1， x2， + a1nxn ≤(=, ≥) b1 a21x1 + a22x2 + 200萬(wàn) m3 500萬(wàn) m3 2萬(wàn) m3 m3 化工廠 1 化工廠 2 1000元 /萬(wàn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1