【正文】 為非基變量，令非基變量等于零，求解方程組就可以找出基解。 ?????????????????????)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。 定理 3：若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。 定理 2描述了可行解集的頂點與基本可行解的對應(yīng)關(guān)系，頂點是基本可行解；反之，基本可行解在頂點上。 定理 1描述了可行解集的特征。 例 滿足約束方程和非負(fù)約束，因 此是可行解，但它不是任何基矩陣的基本解。 )1(22112222212111212111???????????????????nnnnnnnnnnbxaxaxabxaxaxabxaxaxa??????????????定理 (克拉默法則 ) 如果含有 n 個方程 的 n 元線性方程組 的系數(shù)行列式 0d e t212222111211??nnnnnnaaaaaaaaaA??????則方程組 (1)有唯一解，并且 njABx jj ,2,1,d e td e t ???其中 detBj 是將系數(shù)行列式 detA 的第 j 列元 a1j , a2j , … , anj , 換成常數(shù)項 b1 , b2 , … , bn 后得到的行列式 . ??????????????),...,1(0),......,2,1(..m a x zj11njxmibxatsxcinjjijnjjj（ a） （ b） （ c） 四、單純形法 （ 5）基本可行解 滿足變量非負(fù)約束條件（ c）的基解稱為基可行解。顯然在基解中變量取非零值的個數(shù)不大于方程數(shù) m，又基解的總數(shù)不超過 Cnm個。 ??????????????),...,1(0),......,2,1(..m a x zj11njxmibxatsxcinjjijnjjj（ a） （ b） （ c） 四、單純形法 （ 4）基本解 在約束方程組（ b）中，令所有 非基變量xm+1=xm+2=… =xn=0,又因為有 |B|≠0 ，根據(jù) 克拉默規(guī)則 ，由 m個約束方程可解出 m個基變量的惟一解 XB=（ x1， … ，xm）。 ?????????01015B2 ?????????10261001115AB2的基向量是 A中的第一列和第四列 B2的基變量是 x1和 x4 B2的非基變量是 x x3和 x5。線性規(guī)劃中除基變量以外的其他變量稱為 非基變量 。當(dāng)矩陣 B的行列式等于零是就不是基。 r ( AT ) = r ( A ) . 例 求矩陣 A 的秩，其中 .174532321????????????A 解 :在 A 中，容易看出２階子式 ,0132 21 ???而 A 的三階子式只有一個 ｜ Ａ ｜ ,0|| ?A 因此 .2)( ?Ar（ 3）基 例 19 已知線性規(guī)劃 ?????????????????)5,...,2,1(02261035..24m a x53214321321jxxxxxxxxxtsxxxzj求所有基矩陣。線性規(guī)劃中除基變量以外的其他變量稱為 非基變量 。 B是矩陣 A中的一個 m m階的 滿秩子矩陣 ，稱 B是線性規(guī)劃問題的一個 基 。 （ 2）最優(yōu)解 使目標(biāo)函數(shù)（ a）達(dá)到最大值的可行解稱為最優(yōu)解。 四、單純形法 線性規(guī)劃問題的解 假設(shè)所要研究的線性規(guī)劃模型的形式為： 求解線性規(guī)劃問題，就是滿足約束條件（ b）、（ c）的方程組中找出一個解，使目標(biāo)函數(shù)（ a）達(dá)到最大值。 對任何 X1∈C ， X2 ∈C ，不存在 X=aX1+（ 1a） X2 （ 0a1），則稱 X是凸集 C的頂點。 四、單純形法 預(yù)備知識：凸集和頂點 ① 凸集： 因為 X X2的連線可表示為： aX1+（ 1a） X2（ 0a1） 所以凸集定義用數(shù)學(xué)語言表示為： 對任何 X1∈C ， X2 ∈C ，有 aX1+（ 1a） X2 ∈C （ 0a1），則稱 C為凸集。但容易產(chǎn)生錯誤。引入單純形法！ 四、單純形法 預(yù)備知識：凸集和頂點 線性規(guī)劃問題的解 幾個基本定理（不要求證明） 單純形法求解線性規(guī)劃 單純形法的計算步驟 四、單純形法 單純形法是求解一般線性規(guī)劃問題的基本方法，是1947年由丹齊格（ ）提出。比較周圍相鄰頂點的目標(biāo)函數(shù)值是否比這個值更優(yōu)，如果為否，則該頂點就是最優(yōu)解的點或最優(yōu)解的點之一，否則轉(zhuǎn)到比這個點的目標(biāo)函數(shù)值更優(yōu)的另一個頂點，重復(fù)上述過程，一直到找出使目標(biāo)函數(shù)值達(dá)到最優(yōu)的頂點為止。原因是模型本身有錯誤，約束條件相互矛盾，應(yīng)檢查修正。 ??????????????）（）（）（）（40,3515216411222..33m a x21212121xxxxxxtsxxz圖解法的實例 例 17 用圖解法求下列線性規(guī)劃問題的最優(yōu)解 ??????????0,242..2m a x2112121xxxxxtsxxzx1 x2 如圖：此問題有可行域，但為無界解（無最優(yōu)解） 其原因是由于在建立實際問題的數(shù)學(xué)模型時遺漏了某些必要的資源約束。當(dāng)目標(biāo)函數(shù)直線向右上方移動時，他與凸多邊形相切時不是一個點，而是在整個線段 Q2Q3上相切。 圖解法的實例 例 16 將例 15中的目標(biāo)函數(shù) max z=2x1+3x2改為maxz=3x1+3x2，則線性規(guī)劃問題的最優(yōu)解為？ 最優(yōu)解為 Q3Q2上的所有點，因此此問題有無窮多個最優(yōu)解。 思考：為什么 z直線不能繼續(xù)向右上方移動？ ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxzx1 x2 Q4 Q3(3,3) Q2 (4,2) Q1 圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 3）最優(yōu)解的確定。因此 x x2的取值范圍只能從凸多邊形 OQ1Q2Q3Q4中去尋找。 ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxzx1 x2 33212zxx ???Z=6 圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 3）最優(yōu)解的確定。但在線性規(guī)劃問題中，對 x x2的取值范圍是有限制。如圖！ 這族平行線中，離原點越遠(yuǎn)的直線， z的直線越大。 圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 2）目標(biāo)函數(shù)的幾何意義。 ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxzx1 x2 Q4 Q3 Q2 Q1 圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 1）先分析約束條件是如何圖示的。 圖解法的步驟： 第 1步：建立坐標(biāo)系，畫出由約束條件所確定的區(qū)域 第 2步：對任意確定的 z，畫出目標(biāo)函數(shù)所代表的直線 第 3步：平移目標(biāo)函數(shù)直線，確定最優(yōu)解。 ?????? xxxxxzz令三、求解線性規(guī)劃模型的圖解法 線性規(guī)劃模型的基本求解方法有： 圖解法 和單純形法。439。439。39。432139。39。439。32139。39。439。4321639。39。?????????????????????xxxxxxxxxxxxxxxxxxzz令X4為松弛變量 X5為剩余變量 二、線性規(guī)劃問題的數(shù)據(jù)模型 線性規(guī)劃模型的標(biāo)準(zhǔn)形式 自己動手試一試：將下列線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)型。339。339。39。339。321539。39。339。xxxxxxxxxxxxxxxxxxxxtsxxxxxxz 63323,422329),0,0(,39。3339。3215439。39。339。321539。39。339。 ???? xxxxx ，二、線性規(guī)劃問題的數(shù)據(jù)模型 例如 14 將下述線性規(guī)劃模型化為標(biāo)準(zhǔn)形式 ??????????????????取值無約束，3213213213213210,632342392..32m inxxxxxxxxxxxxtsxxxz二、線性規(guī)劃問題的數(shù)據(jù)模型 例如 14 【 解 】 ： 按規(guī)則將問題轉(zhuǎn)化為： ????????????????????????????0,633234223932..00332m a x5439。39。39。 0,0 39。 線性規(guī)劃模型的標(biāo)準(zhǔn)形式 （ 2）非標(biāo)準(zhǔn)形式的線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法 ① 目標(biāo)函數(shù)為求最小值 ② 約束條件為不等式 ③ 無約束變量。 松弛變量和剩余變量在實際問題中分別 表示未被利用的資源數(shù)和短缺的資源數(shù) ，均未轉(zhuǎn)化為價值和利潤。m a x線性規(guī)劃模型的標(biāo)準(zhǔn)形式 （ 2）非標(biāo)準(zhǔn)形式的線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法 ② 約束條件為不等式 當(dāng)約束條件為 “ ≧ ” 時，例如 10x1+12x2≧ 18 可令 x4=10x1+12x218或者 10x1+12x2x4=18。 顯然， x3≧0 ，稱 x3為 松弛變量 。 二、線性規(guī)劃問題的數(shù)據(jù)模型 線性規(guī)劃模型的標(biāo)準(zhǔn)形式 為了研究問題的方便，規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)形式為： ??????????????),...,1(0),......,2,1(..m a xj11njxmibxatsxczinjjijnjjj線性規(guī)劃模型的標(biāo)準(zhǔn)形式 對標(biāo)準(zhǔn)形式的說明： （ 1）標(biāo)準(zhǔn)形式的線性規(guī)劃模型中的要求 ① 目標(biāo)函數(shù)為 求最大值 （有些文獻(xiàn)規(guī)定是求最小值）； ② 約束條件 全為等式 ，約束條件右端常數(shù)項 bi全為 非負(fù)值 ； ③ 變量 xj的取值全為 非負(fù)值 。...。 二、線性規(guī)劃問題的數(shù)據(jù)模型 線性規(guī)劃模型的一般表達(dá)形式 （ 1）一般形式 ????????????????????????????????0,...,),(...............),(...),(........m a xm in21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxats