【文章內容簡介】 設線性規(guī)劃為 max z = CX ① AX = b ② X ≥ 0 ③ A為 m n矩陣 , n m, Rank A = m (A為行滿秩矩陣） 可行解：滿足條件 ②、③ 的 X； 最優(yōu)解：滿足 條件 ①的可行解； 基：取 B為 A中的 m m子矩陣， Rank B = m， 則稱 B為線性規(guī) 劃問題的一個基。 取 B = (p1,p2,,pm) pj = (a1j,a2j,,amj)T 則稱 x1,x2,,xm為基變量，其它為非基變量。 26 基解：取 B = (p1,p2,,pm) a11,,a1m x1 a1m+1,,a1n xm+1 b1 ┆ ┆ ┆ + ┆ ┆ ┆ = ┆ am1,,amm xm amm+1,,amn xn bm ↑ ↑ ↑ ↑ 基 基變量 非基 非基變量 令 xm+1 = = xn = 0 (非基變量為 0) 則 BXB = b ∴ )!(!!mnmnC mn ???基解個數(shù)TmnmTmBxxxXxxxbBX)0,0,(),(m )0()0(2)0(1)0()0(2)0(11??? ??? ??? ?? ??個個基解：?????27 基可行解 滿足 ③ 式要求的基解。 如右圖所示，各邊交點 O,Q1,Q2,Q3,Q4 均為基可行解 ； 而其延長線的交點 Q5為 基解，但不是基可行解。 O(0,0) Q1(4,0) Q2(4,2) Q4(0,3) Q3(2,3) Q5(4,3) 可行基 基可行解對應的 B為可行基。 可行解 基可行解 非可行解 基解 28 167。 2 線性規(guī)劃問題的幾何意義 基本概念 凸集：設 K為 En(n維歐式空間 )的一點集， X(1)∈ K， X(2)∈ K。 若 α X(1)+(1α )X(2)∈ K， 則稱 K為凸集。（ 0α 1） 非凸集 X(1) X(1) X(2) X(2) 凸集 X(1) X(2) X(2) X(1) 29 頂點： X∈ K， X(1)∈ K， X(2)∈ K (任意兩點 )。若 X不能用α X(1)+(1α )X(2)表示，則稱 X為 K的一個頂點。 (0α 1) 注：頂點所對應的解是基可行解。 凸組合：設 X(i)∈ En， 若存在 0μ i1， i = 1,2,,k， 使 ,則稱 X為 X(i)(i=1,2,,k)的凸組合。 1k1 ii ???????? k1i) i (i XX 基本定理 定理 1 若線性規(guī)劃存在可行域，則 : 可行域 D = {X|AX = b,X ≥ 0}為凸集。 30 證明： 設 X(1)=(x1(1),x2(1),,xn(1))T ∈ D； X(2)=(x1(2),x2(2),,xn(2))T ∈ D； (X(1) ≠ X(2)) 有 AX(1) = b， AX(2) = b 令 X = α X(1) + (1 α )X(2) (0α 1) 則 AX = α AX(1) + (1 α )AX(2) = α b + (1 α )b = b ∵ α 0 1 – α 0 ∴ X ≥ 0， 即 D為凸集 定理 2 線性規(guī)劃的基可行解對應于可行域的頂點。 定理 3 若線性規(guī)劃有解，則一定存在基可行解為最優(yōu)解。 31 167。 3 單純形法 基本思路： 從可行域的一個頂點到另一個頂點迭代求最優(yōu)解。 初始基可行解的確定 松弛基（松弛變量對應的 B） []max z = x1 + 3x2 x1 + 2x2 ≤ 3 2x1 + 3x2 ≤ 4 x1,x2 ≥ 0 max z = x1 + 3x2 + 0x3 + 0x4 x1 + 2x2 + x3 = 3 2x1 + 3x2 + x4 = 4 x1,x2,x3,x4 ≥ 0 化標準型 取 x x4為基變量 ,令非基變量 x1= x2=0 ∴ 初始基可行解： X(0) = (0 0 3 4)T ? ? ? ? B , 1 0 3 2 0 1 2 1 434321 ppppppA ????????? 則系數(shù)矩陣32 觀察法 []max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 ≥ 0 選 XB = (x1 x4)T 令 x2 = x3 = 0 則 初始基可行解： X(0) = (3 0 0 4)T ? ? ? ? B , 1 1 3 00 3 2 1 :414321 ppppppA ????????? 則解33 人工基 []max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 2x1 + x2 + x3 = 4 x1,x2,x3 ≥ 0 分析： A = 1 3 2 2 1 1 ∵ 找不到單位矩陣基 ∴ 引入人工變量為初始基變量（ 2個） 34 最優(yōu)性的檢驗與解的判別 ????????????????????????????mnjxmibxxaxcxczjnjiinjijmiininnjjj,1 0,1 m a x 111對于? ?