【文章內(nèi)容簡介】 1 am,m+1 … amn bm z 0 0 0 0 σm+1 … σn z0 ? 單純形表的說明與功能： （ 1）一個(gè)基對應(yīng)一個(gè)單純形表，且單純形表中必須有一個(gè)初始單位基。 （ 2）從單純表中，可立即得到一個(gè)基可行解，如上表中： X=（ b1， b2， … ， bm， 0， … ， 0） T為基可行解。 （ 3）很容易計(jì)算檢驗(yàn)數(shù)，并可判別上述基可行解是否為最優(yōu)解或線性規(guī)劃問題無最優(yōu)解。 4. 單純形法計(jì)算步驟 （ 1）找出初始可行基，建立初始單純形表； （ 2）計(jì)算檢驗(yàn)數(shù)，若對于一切 j∈ J有 σj≤0， 則已得到線性規(guī)劃的最優(yōu)解，可停止計(jì)算，否則轉(zhuǎn)下一步； （ 3）若有 σk0（ k∈ J）， 且 Pk≤0，則該線性規(guī)劃問題具有無界解（無最優(yōu)解），停止計(jì)算，否則轉(zhuǎn)下一步； （ 4）根據(jù) max｛ σj|σj0｝ =σk， 確定 xk為換入變量； 按 θ規(guī)則確定換出變量，即 θ=｛ bi/aik|aik0｝ =bs/ask，對應(yīng)的 xs為換出變量，轉(zhuǎn)下一步； （ 5）以 ask為主元素進(jìn)行迭代，得新的單純形表，轉(zhuǎn)（ 2） 三、單純形法解題舉例 ? 例 1：用單純形法求解 max z=6x1+4x2 2x1 + 3x2≤100 4x1 + 2x2≤120 x x2≥0 ? 解：化為標(biāo)準(zhǔn)型 max z=6x1+4x2+0x3+0x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x x2， x3， x4 ≥0 找初始可行基： B1=（ P3， P4） 現(xiàn)成的初始可行基； ?從表中有： X（ 1） =（ 0， 0， 100， 120） T為對應(yīng)于基 B1的基可行解，顯然不是最優(yōu)解； ?根據(jù) max｛ σj|σj0｝ =σ1，確定 x1為換入變量； ? 按 θ規(guī)則確定換出變量，即： θ=｛ bi/aik|aik0｝=120/4，對應(yīng)的 x4為換出變量； Cj 6 4 0 0 b θ CB XB x1↓ x2 x3 x4 0 ← 0 x3 x4 2 3 1 0 [4] 2 0 1 100 120 100/2 120/4(min) z 6 4 0 0 0 –列初始單純形表 ?以 [4]為主元素進(jìn)行迭代，得新的單純形表： ?從表中有： X（ 2） =（ 30， 0， 40， 0） T為對應(yīng)于基B2的基可行解，顯然不是最優(yōu)解； ?根據(jù) max｛ σj|σj0｝ =σ2， 確定 x2為換入變量； ? 按 θ規(guī)則確定換出變量，即： θ=｛ bi/aik|aik0｝=40/2，對應(yīng)的 x3為換出變量； Cj 6 4 0 0 b θ CB XB x1 x2↓ x3 x4 ← 0 x3 0 [2] 1 1/2 40 40/2 6 x1 1 1/2 0 1/4 30 30/(1/2) Z 0 1 0 3/8 180 ?表中 σj≤0， j=1， … ， 4， ?因此得最優(yōu)解： X*=（ 20， 20， 0， 0） T， Z*=200 Cj 6 4 0 0 b CB XB x1 x2 x3 x4 4 6 x1 x2 0 1 1/2 1/4 1 0 1/4 3/8 20 20 Z 0 0 1/2 5/4 200 以 [2]為主元素進(jìn)行迭代，得新的單純形表： 將上述計(jì)算列在一個(gè)表中為： Cj 6 4 0 0 b θ CB XB x1↓ x2 x3 x4 0 x3 2 3 1 0 100 100/2 ← 0 x4 [4] 2 0 1 120 120/4(min) z 6 4 0 0 0 ← 0 x3 0 [2] 1 1/2 40 40/2(min) 6 x1 1 1/2 0 1/4 30 30/(1/2) Z 0 1 0 3/8 180 4 x2 0 1 1/2 1/4 20 6 x1 1 0 1/4 3/8 20 Z 0 0 1/2 5/4 200 例 2：用單純形法求解 max z=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x x2≥0 Cj 50 100 0 0 0 b θ CB XB x1↓ x2↓ X3 x4 x5 0 x3 1 1 1 0 0 300 300/1 0 x4 2 1 0 1 0 400 400/1 ← 0 x5 0 [1] 0 0 1 250 250/1(min) z 50 100 0 0 0 0 ← 0 x3 1 0 1 0 1 50 50/1(min) 0 x4 2 0 0 1 1 150 150/2 100 x2 0 1 0 0 1 250 — Z 50 0 0 0 100 25000 50 x1 1 0 1 0 1 500 0 x4 0 0 2 1 1 50 100 x2 0 1 0 0 1 250 Z 0 0 50 0 50 27500 ? 例 3：用單純形法求解 max z=2x1+x2 － x1 + x2≤5 2x1－ 5x2≤10 x x2≥0 ? σ2=6 0，且 P2≤0，故該線性規(guī)劃有無界解。 Cj 2 1 0 0 b θ CB XB x1↓ x2 x3 x4 0 x3 1 1 1 0 5 100/2 ← 0 x4 [2] 5 0 1 10 120/4(min) z 2 1 0 0 0 0 x3 0 3/2 1 1/2 10 40/2(min) 2 x1 1 5/2 0 1/2 5 30/(1/2) Z 0 6 0 1 10 ?例 4：用單純形法求解 max z=6x1+2x2+10x3+8x4 5x1 + 6x2－ 4x3－ 4x4≤20 3x1－ 3x2 +2x3 + 8x4≤25 4x1－ 2x2 + x3 + 3x4≤10 x x x x4≥0 σ7=340, p7≤0,故該 LP有無解解 Cj 6 2 10 8 0 0 0 b CB XB x1↓ x2↓ x3 x4 x5 x6 x7 0 x5 5 6 4 4 1 0 0 20 0 x6 3 3 2 8 0 1 0 25 0 x7 4 2 [1] 3 0 0 1 10 z 6 2 10 8 0 0 0 0 0 x5 21 2 0 8 1 0 4 60 0 x6 5 [1] 0 2 0 1 2 5 10 x3 4 2 1 3 0 0 1 10 Z 34 22 0 22 0 0 10 100 0 x5 11 0 0 12 1 2 0 70 2 x2 5 1 0 2 0 1 2 5 10 x3 6 0 1 7 0 2 3 20 Z 76 0 0 66 0 22 34 210 四、極小化問題 (Minimization Problem) ? 若標(biāo)準(zhǔn)形式的線性規(guī)劃問題的目標(biāo)函數(shù)是極小化形式，則問題的判別準(zhǔn)則就會(huì)有所改變。這樣三個(gè)判別定理如下 ： ? 判別定理 1：設(shè) X為線性規(guī)劃的一個(gè)基可行解，且對于一切 j∈ J（ J為非基變量的下標(biāo)集）有 σj ≥0，則 X為線性規(guī)劃的最優(yōu)解； ? 判別定理 2：設(shè) X為線性規(guī)劃的一個(gè)基可行解，且對于一切 j∈ J（ J為非基變量的下標(biāo)集）有 σj ≥ 0，同時(shí)有某個(gè)非基變量的檢驗(yàn)數(shù) σk=0（ k∈ J） ，則該線性規(guī)劃有無窮多最優(yōu)解； ? 判別定理 3：設(shè) X為線性規(guī)劃的一個(gè)基可行解，若有 σk 〈 0（ k∈ J） ，且 Pk≤0，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。 ?上述單純形法的基礎(chǔ)是線性規(guī)劃問題有初始基可行解 。 有些線性規(guī)劃問題化為標(biāo)準(zhǔn)形式以后 ， 就存在初始可行基 ， 如約束條件全部為 “ ≤ ” 的線性規(guī)劃問題 。 對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題 ， 若約束方程系數(shù)矩陣中不存在現(xiàn)成的初始可行基 ，則不能簡單的用上述單純形法 ， 而通常采用所謂的人工變量法 。 人工變量法一般有大 M法和兩階段法 。 五、人工變量法 (Artificial Variable Method) （一）大 M法 (Big M method) ? 對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題（問題 A） max z=c1x1+c2x2+…+c nxn a11x1+a12x2+…+a 1nxn= b1 a21x1+a22x2+…+a 2nxn= b2 ……………………… am1x1+am2x2+…+a mnxn= bm x1， x2， … ， xn≥0 ? 若其約束方程的系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則引入所謂的人工變量 xn+1， … ， xn+m構(gòu)造如下形式的線性規(guī)劃問題（問題 B） max z=c1x1+c2x2+…+c nxn－ Mxn+1－ … － Mxn+m a11x1+a12x2+…+a 1nxn+xn+1 = b1 a21x1+a22x2+…+a 2nxn +xn+2 = b2 ………………………………………… am1x1+am2x2+…+a mnxn +xn+m = bm x1， x2， … ， xn， xn+1， … ， xn+m≥0 ? 問題 B中 M為任意大的正數(shù)。顯然問題 B存在現(xiàn)成的單位基，且初始基可行解中，以人工變量為基變量。 ? 關(guān)于問題 B的幾點(diǎn)結(jié)論： （ 1）問題 B要實(shí)現(xiàn)極大化，必須將人工變量從基變量中換出，否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)極大化； （ 2）若在求解問題 B的過程中，已將人工變量從基變量中換出，則已得到問題 A的一個(gè)基可行解，可繼續(xù)求解，以獲得問題 A的最優(yōu)解或判別問題 A無最優(yōu)解； （ 3）若求解問題 B已得到最優(yōu)解，但最優(yōu)解的基變量中含有不為零人工變量，則問題 A無可行解； （ 4）若求解問題 B已得到最優(yōu)解，且最優(yōu)解的基變量中不含有人工變量，則問題 B的最優(yōu)解就是問題 A的最優(yōu)解。 ?例：用單純形法（大 M法）求解 max z=3x1－ 2x2－ x3 x1 － 2x2 + x3 ≤ 11 － 4x1 + x2 +2x3 ≥ 3 － 2x1 x3 = 1 x x x3≥0 ?解：化為標(biāo)準(zhǔn)形式，并引入人工變量，構(gòu)造如下模型： max z=3x1－ 2x2－ x3－ Mx6－ Mx7 x1－ 2x2 + x3 + x4 = 11 － 4x1 + x2 +2x3