【文章內容簡介】 和式： maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n 矩陣式： maxZ=CX AX=b X ≥0 約束方程的系數(shù)矩陣 A的秩為 m，且 mn。設A=B+N ， B是 A中 m?m階非奇異子矩陣，則稱B是 LP的一個 基 ，即： B是 A中 m個線性無關向量組。 n j=1 n j=1 OR1 32 基解的概念 不失一般性 ,設 B是 A的前 m列 ,即B=(p1,p2,…,p m） ,其相對應的變量XB=(x1,x2,…,x m)T,稱為基變量；其余變量XN=(Xm+1,…, Xn)T稱為非基變量。令所有非基變量等于零 ,則 X=（ x1,x2,…x m,0,…, 0)T稱為基解 。 OR1 33 基可行解的概念 ? 基可行解： 基解可正可負，負則不可行（違背非負性約束條件），稱滿足所有約束條件的基解為 基可行解。 ? 退化的基可行解 ： 若某個基變量取值為零，則稱之為退化的基可行解。 ? 基解的數(shù)目：最多 Cmn=n!/m!(nm)! OR1 34 例題 6 基可行解說明 maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj≥0 j=1,2,…,5 這里 m=3,n=5。 Cmn=10 OR1 35 例題 6 基可行解說明 ? 基（ p3,p4,p5） ，令非基變量 x1,x2=0，則基變量 x3=360, x4=200, x5=300, 可行解 ? 基（ p2,p4,p5） ,令非基變量 x1=0,x3=0基變量x2=90,x4=－ 250,x5=－ 600. 非可行解 ? 基（ p2,p3,p4 ），令非基變量 x1,x5=0，則基變量 x2=30, x3=240, x4=50,可行解 （ P21圖） OR1 36 ? 從系數(shù)矩陣中找到一個可行基 B，不妨設 B由 A的前 m列組成，即 B=(P1,P2,……Pm) 。進行等價變換－－約束方程兩端分別左乘 B－ 1 得 X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 …………………………….. xm+a’mm+1xm+1+…+ a’mnxn=b’m 令非基變量為 0，得基可行解 X(0)=(b1’， b2’， ……b m， 0， ……0 ） T z0=∑cibi’ OR1 37 ? ： LP經過若干步迭代，成為如下形式： X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x1=b’1 ∑ a’1jxj x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 x2=b’2 ∑a’2jxj …………………………….. …………….. xm+a’mm+1xm+1+…+ a’mnxn=b’m xm=b’m ∑a’mjxj OR1 38 單純形法 一般性表示 ： xi=b’i ∑a’ijxj i=1,2,…m 將 xi代入目標函數(shù)得 ： Z= ∑ cjxj = ∑ cixi+ ∑ cjxj = ∑ci（ b’i ∑a’ijxj ） + ∑ cjxj = ∑cibi’+ ∑(cj ∑ cia’ij)xj 令： σj= cj ∑ cia’ij z0=∑cibi’ 則 Z=z0+ ∑ σj xj σj判別準則 ： σj ≤0 時 ,達到最優(yōu)解 OR1 39 單純形法 ? 若存在 σj ≥ 0，則取 max{σj } = σK ，相應之非基變量 XK若取非零，將使 Z增加 ,故令 XK 進基。令 XK≠0 ，其余非基變量保持為零。 XK 原是非基變量，取零值， 若 XK ≠0 將迫使某個原基變量為零，當 XK取值超過任意 b’i / a’ik 時 ,將破壞非負性條件 ,于是令 θ = min {b’i / a’ik a’ik 0 } =b’L/ a’Lk 。 這時原基變量 XL=0，由基變量變成非基變量， a’Lk處在變量轉換的交叉點上，稱之為樞軸元素 σj ≥ 0 OR1 40 單純形法解題舉例 單純形表的格式： Cj C1 C2 … Cn θi CB XB b x1 x2 …. xn C1 C2 … Cm x1 x2…xm b 1 b2 … bm a11 a12 … a1n a21 a22 … a2n … … … am1 am2… amn θ1 θ2 … θm σj σ1 σ2 … σn OR1 41 Cj C1 C2 … Cn CB XB b X1 X2 X3 X4 X5 θj 0 0 0 X3 X4 X5 360 200 300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 90 40 30 σj 0 70 120 0 0 0 0 0 120 X3 X4 X2 240 50 30 0 1 0 0 0 1 1 0 0 20 100 σj 3600 34 0 0