【正文】 最少！ 調(diào)運(yùn)方案如何理解？ – A1分別向 B B B3三個電廠輸送多少萬 t煤炭？ – A2分別向 B B B3三個電廠輸送多少萬 t煤炭？ – A3分別向 B B B3三個電廠輸送多少萬 t煤炭？ 總的運(yùn)輸量（總?cè)f噸公里數(shù)）如何計(jì)算？ – 各個煤礦向各個電廠輸送的煤的噸數(shù) 輸送的距離之和。問該工廠如何安排這兩種產(chǎn)品的生產(chǎn)計(jì)劃，才能使總利潤最大？ 自己動手試一試 【 解 】 兩種新產(chǎn)品的有關(guān)數(shù)據(jù)如表： 車間 單位產(chǎn)品的生產(chǎn)時間（小時） 每周可獲得的生產(chǎn)時間 （小時） 門 窗 1 1 0 4 2 0 2 12 3 3 2 18 單位利潤（元） 300 500 自己動手試一試 【 解 】 設(shè) x1為每周門的產(chǎn)量（扇）， x2為每周窗的產(chǎn)量（扇）。 顯然， x3≧0 ，稱 x3為 松弛變量 。 0,0 39。339。39。339。39。39。32139。39。 圖解法的步驟： 第 1步：建立坐標(biāo)系，畫出由約束條件所確定的區(qū)域 第 2步：對任意確定的 z，畫出目標(biāo)函數(shù)所代表的直線 第 3步：平移目標(biāo)函數(shù)直線，確定最優(yōu)解。但在線性規(guī)劃問題中，對 x x2的取值范圍是有限制。 圖解法的實(shí)例 例 16 將例 15中的目標(biāo)函數(shù) max z=2x1+3x2改為maxz=3x1+3x2，則線性規(guī)劃問題的最優(yōu)解為？ 最優(yōu)解為 Q3Q2上的所有點(diǎn)，因此此問題有無窮多個最優(yōu)解。比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個值更優(yōu)，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個點(diǎn)的目標(biāo)函數(shù)值更優(yōu)的另一個頂點(diǎn)，重復(fù)上述過程，一直到找出使目標(biāo)函數(shù)值達(dá)到最優(yōu)的頂點(diǎn)為止。 對任何 X1∈C ， X2 ∈C ，不存在 X=aX1+（ 1a） X2 （ 0a1），則稱 X是凸集 C的頂點(diǎn)。線性規(guī)劃中除基變量以外的其他變量稱為 非基變量 。 ?????????01015B2 ?????????10261001115AB2的基向量是 A中的第一列和第四列 B2的基變量是 x1和 x4 B2的非基變量是 x x3和 x5。 例 滿足約束方程和非負(fù)約束，因 此是可行解，但它不是任何基矩陣的基本解。 ?????????????????????)5,. ..,1(01551641222..00032m a x524132154321jxxxxxxxxtsxxxxxzj標(biāo)準(zhǔn)型 例 110 解 寫出約束方程組的系數(shù)矩陣 ?????????????????????)5,. ..,1(01551641222..00032m a x524132154321jxxxxxxxxtsxxxxxzj???????????100500100400122AP1 P2 P3 P4 P5 矩陣 A的秩 ≦ 3。 我們將主要介紹單純形法。 從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品 Ⅰ 或 Ⅱ ，就可以使工廠的利潤指標(biāo)增加。 由這些 資源中的 薄弱環(huán)節(jié) ，就確定了產(chǎn)品 Ⅱ 的產(chǎn)量 。513?????????????????xxxxxxx再將 (17)式代入目標(biāo)函數(shù) (11)式得到 令非基變量 x1=x5=0，得到 z=9，并得到另一個基可行解 X（ 1） X（ 1） =（ 0， 3， 2， 16， 0） T ）（ 81432951 xxz ???從目標(biāo)函數(shù)的表達(dá)式 (18)中可以看到 ， 非基變量 x1的系數(shù)是正的 ， 說明目標(biāo)函數(shù)值還可以增大 ， X(1)還不是最優(yōu)解 。 ? ? ??????????1001, 43 PPB基變量為： x3， x4 非基變量為： x1， x2 令非基變量 x1=x2=0，代入約束方程中 0,3034024321421321???????xxxxxxxxxx 得到： x3=40， x4=30 則初始基本可行解為： X（ 0） =（ 0， 0， 40， 30） T 例 112 【 解 】 以上得到的一組基本可行解是否是最優(yōu)解 ? 從目標(biāo)函數(shù) z=3x1+4x2中看出： X1和 x2的系數(shù)大于零，如果 x1和 x2為一個正數(shù)，那么目標(biāo)值就能夠變得更大。 （ 1）確定換入變量（進(jìn)基變量） 方法： λ k=max{λj | λj 0} （ 2）確定換出變量（出基變量） 方法： θ k=min{θi =bi/aik|aik0} cj 3 4 0 0 θi (min) CB XB x1 x2 x3 x4 b 0 x3 2 1 1 0 40 0 x4 1 3 0 1 30 λj (max) 3 4 0 0 0 換入變量為： x2 那么換出變量為 x3還是 x4呢？ 確定換出變量為 x4 40/1 30/3 cj 3 4 0 0 θi (min) CB XB x1 x2 x3 x4 b 0 x3 2 1 1 0 40 0 x4 1 3 0 1 30 λj (max) 3 4 0 0 0 換入變量為： x2。 5/3 ② ① 1/3 確定基本可行解 X（ 2） =（ 18， 4， 0， 0） T 最優(yōu)性性判斷？ ③ ① 5/3 看到所有的檢驗(yàn)數(shù)都小于 0，所以 X（ 2） 是最優(yōu)解 同時目標(biāo)函數(shù)值為 70 1 3/5 1/5 18 0 1/5 2/5 4 0 1 1 70 z 練習(xí)：將例 111用單純形表求解。 四、單純形法 預(yù)備知識：凸集和頂點(diǎn) 線性規(guī)劃問題的解 幾個基本定理（不要求證明） 單純形法求解線性規(guī)劃 單純形法的計(jì)算步驟 四、單純形法 單純形法的計(jì)算步驟 （ 1）將線性規(guī)劃問題轉(zhuǎn)換為標(biāo)準(zhǔn)型 （ 2）求初始基本可行解 （ 3）通過計(jì)算檢驗(yàn)數(shù)判斷基本可行解是否為最優(yōu) – 若所有檢驗(yàn)數(shù)都小于等于零，則得到最優(yōu)解 – 若某個檢驗(yàn)數(shù)大于零，但對應(yīng)變量系數(shù)都小于等于零，則線性規(guī)劃有無界解 – 若存在檢驗(yàn)數(shù)大于零，而且對應(yīng)變量的系數(shù)不全為負(fù)，則進(jìn)行換基 單純形法的計(jì)算步驟 （ 1）將線性規(guī)劃問題轉(zhuǎn)換為標(biāo)準(zhǔn)型 （ 2）求初始基本可行解 （ 3）通過計(jì)算檢驗(yàn)數(shù)判斷基本可行解是否為最優(yōu) （ 4）換基 – 選進(jìn)基變量：選擇檢驗(yàn)數(shù)最大的變量 – 選出基變量：最小比值法則 }0|m in { ?? ikiki aab?（ 5）求新的基本可行解：用初等變換將 aLK化為 1，k列其他元素化為零（基向量成單位矩陣），再判斷是否得到最優(yōu) 五、單純形法的進(jìn)一步討論 在實(shí)際問題中 有些模型并不含有單位矩陣 ，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。 人工變量法（大 M法） 兩階段法 五、單純形法的進(jìn)一步討論 人工變量法（大 M法） （ 1）人工變量法的思路 當(dāng)線性規(guī)劃問題的 約束條件是等式 ，而系數(shù)矩陣中又不包含有單位矩陣時，采用人工變量法在 約束條件左端加上一個人工變量 ，從而人為地構(gòu)造一個單位基矩陣。 例 113 單純形法求解 ?????????????????0,212665..22m in2121212121xxxxxxxxtsxxz以上我們討論的是有惟一最優(yōu)解的情況，如果最優(yōu)解有無窮多個，求解的過程是怎樣的呢？ 例 114 ???????????????0,210242..42ax2121212121xxxxxxxxtsxxzm例 114 【 解 】 化為標(biāo)準(zhǔn)型為： 54321 00042m a x xxxxxz ?????0,20124254321521421321??????????xxxxxxxxxxxxxxcj 2 4 0 0 0 θi (min) CB XB x1 x2 x3 x4 x5 b 0 x3 1 2 1 0 0 4 0 x4 1 2 0 1 0 10 0 x5 1 1 0 0 1 2 λj (max) 初始單純形表如下： X（ 0） =（ 0， 0， 4， 10， 2） T 2 4 0 0 0 0 判斷是否最優(yōu)？ 不是最優(yōu)！ 換基方案？ 換入變量： x2， 2 5 換出變量： x3 54321 00042m a x xxxxxz ?????0,20124254321521421321??????????xxxxxxxxxxxxxxcj 2 4 0 0 0 θi (min) CB XB x1 x2 x3 x4 x5 b 4 x2 1 2 1 0 0 4 0 x4 1 2 0 1 0 10 0 x5 1 1 0 0 1 2 λj (max) 2 4 0 0 0 0 經(jīng)初等變換，將（ P2， P4， P5）變換為單位矩陣 判斷是否最優(yōu)？ 1/2 21/2 1 0 0 1/2 1 1/2 基本解為 X（ 1） =（ 0， 2， 0， 6， 4） T 2 6 4 不是最優(yōu)解！ 4 0 2 8 換基方案？ 換入變量： x1， 3 8 換出變量： x4 cj 2 4 0 0 0 θi (min) CB XB x1 x2 x3 x4 x5 b 4 x2 1/2 1 1/2 0 0 2 2 x1 2 0 1 1 0 6 0 x5 1/2 0 1/2 0 1 4 λj (max) 4 0 2 0 0 8 經(jīng)初等變換，將（ P1， P2， P5）變換為單位矩陣 判斷是否最優(yōu)？ 基本解為 X（ 2） =（ 3， 7/2， 0， 0， 5/2） T 是最優(yōu)解！ 0 1 0 1/41/2 3/4 1/4 1/2 1/4 7/2 3 5/2 2 20 0 0 目標(biāo)函數(shù)值為 z=20 但是這時，非基變量 x3的檢驗(yàn)數(shù)為零，表示原問題還有其他的最優(yōu)解，也就是說這是多重最優(yōu)解的情況。因此，對增廣矩陣進(jìn)行 初等變換 ！ 4cj 3 4 0 0 θi (min) CB XB x1 x2 x3 x4 b 0 x3 2 1 1 0 40 4 x2 1 3 0 1 30 λj (max) 3 4 0 0 0 換入變量為： x2。 判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作λ j（ j=1， 2， … ， n）。這說明若要用剩余資源 x3,x4，就必須支付附加費(fèi)用。 為了求得以 x3,x4,x2為基變量的一個基可行解和進(jìn)一步分析問題，需將 (13)中 x2的位置與 x5的位置對換。 因此，最優(yōu)解否定后，又要去尋找新的基本可行解，這就需要將非基變量與基變量進(jìn)行對換。 單純形法示例： 例 111 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn) Ⅰ 、 Ⅱ 兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及 A、 B兩種原材料的消耗，如表所示。 例 110 解 寫出約束方程組的系數(shù)矩陣 ???????????100500100400122AP1 P2 P3 P4 P5 令與基對應(yīng)的變量為基變量，其余變量為非基變量，令非基變量等于零，求解方程組就可以找出基解。 定理 1描述了可行解集的特征。 ??????????????),...,1(0),......,2,1(..m a x zj11njxmibxatsxcinjjijnjjj（ a） （ b） （ c） 四、單純形法 （ 4）基本解 在約束方程組（ b）中，令所有 非基變量xm+1=xm+2=… =xn=0,又因?yàn)橛?|B|≠0 ，根據(jù) 克拉默規(guī)則 ，由 m個約束方程可解出 m個基變量的惟一解 XB=（ x1， … ，xm）。 r ( AT ) = r ( A ) . 例 求矩陣 A 的秩，其中 .174532321????????????A