【正文】 ?21決策向量 ?????????????nbbbB?21約束方程組的限定向量 C=(c1， c2 ， … ， c )； 價(jià)值向量 約束條件系數(shù)矩陣 （ 2） 將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形式 非標(biāo)準(zhǔn)形式是 max ( min ) Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn ≥（ = ， ≤） b1 a21x1 + a22x2 + … a2nxn ≥（ = ， ≤） b2 …… am1x1 + am2x2 + … amnxn ≥（ = ， ≤） bm x1， x2， … xn ≥ 0 標(biāo)準(zhǔn)形式是 ： max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm x1， x2， … xn ≥ 0 （ 2） 將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形式 非標(biāo)準(zhǔn)形式 min Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm x1， x2， … xn ≥ 0 （ 1 ） 若目標(biāo)函數(shù)求最小值可以把它轉(zhuǎn)化為求負(fù)的同一目標(biāo)函數(shù)的最大值，即 令 Z‵ = Z min Z = max Z‵ 非標(biāo)準(zhǔn)形式 max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn ≤ b1 a21x1 + a22x2 + … a2nxn ≥ b2 …… am1x1 + am2x2 + … amnxn ≤ bm x1， x2， … xn ≥ 0 （ 2 ） 約束方程組中有不等式，這時(shí)有兩種情況：一種是“ ≤”形式的不等式，則可在式子的左端加一非負(fù)變量稱為“松弛變量”； 如： x1 + x2 + x3 ≤ 60 另外一種是 ≥形式的不等式則在左端減一松弛變量使之變?yōu)榈仁郊s束。 每一個(gè)問題都用一組未知數(shù)（ ……x n） 表示某一方案，這組未知數(shù)的一組定值代表一個(gè)具體的規(guī)劃方案。到目前為止，它的應(yīng)用也最廣泛，是數(shù)學(xué)規(guī)劃及運(yùn)籌學(xué)其他分支的基礎(chǔ)。 線性規(guī)劃 整數(shù)規(guī)劃 動(dòng)態(tài)規(guī)劃 零一規(guī)劃 非線性規(guī)劃 目標(biāo)規(guī)劃 2 理論分支 理論分支 康脫絡(luò)維奇 ——論文 “生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法” ， 1939年。通常要求這些未知數(shù)取值是非負(fù)。 如： x1 + x2 + x3 ≥ 60 （ 2） 將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形式 非標(biāo)準(zhǔn)形式是 max ( min ) Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 … …… …… …… ………… …… … … am1x1 + am2x2 + … amnxn = bm xk 無非負(fù)要求 ， xj ≤0 ， 其余的變量大于等于零 。 圖解法解題的基本步驟 確定可行域 確定目標(biāo)函數(shù)移動(dòng)的方向 確定最優(yōu)解 用圖解法求解如下線性規(guī)劃問題 min Z = 2x1 + 2x2 x1 x2 ≥ 1 x1 + 2x2 ≤ 0 x1 ， x2 ≥ 0 練習(xí) 1 用圖解法求解如下線性規(guī)劃問題 min Z = 2x1 + 2x2 x1 + x2 ≥1 x1 + x2 ≤2 x1， x2 ≥0 練習(xí) 2 5 有關(guān)線性規(guī)劃問題解的概念 可行域 ——所有可行解所構(gòu)成的集合就是可行域 對(duì)于圖解法，可行域就是由約束條件圍成的一個(gè)凸多邊形，我們?nèi)绻?R表示可行域，則 R={x/Ax=b,x≥0} 可行解 ——同樣 ， 在可行域上的點(diǎn)都滿足約束條件所以 ， 我們稱這些點(diǎn)為可行解 。 此解的非零數(shù)目不超過個(gè) m個(gè) ， 非 0分量的數(shù)目等于 m的基本解稱為非退化的 ， 否則稱為退化的 。 （ 1） 基本概念 凸集數(shù)學(xué)表述 頂點(diǎn) 設(shè) 集合 R 是一個(gè)凸集 ， Z 是這個(gè)集合中中的一點(diǎn) ， 如果在此集合中找不到兩個(gè)不同的點(diǎn) X 和 Y ， 使 Z = ( 1 u ) x+ u y ， 1 ≥ u ≥0 成立 ， 則可說 Z 點(diǎn)為 S凸集的頂點(diǎn) 。 此定理說 ， 這個(gè)凸集的頂點(diǎn)是基本可行解 , 同樣基本可行解也必是這個(gè)凸集的頂點(diǎn) . 首先還要理解基本可行解的含義 , 基本可行解是線性規(guī)劃問題系數(shù)矩陣一個(gè)特定的基所對(duì)應(yīng)的可行解 .基本解首先是一個(gè)可行解 , 然后它還是一個(gè)基本解 . 可行域 R 必要性的證明 也就是已知線性規(guī)劃問題的一個(gè)解 X 是這個(gè)線性規(guī)劃問題可行解集合 (可行域 ) R 的頂點(diǎn) ,要證明 X 是此線性規(guī)劃問題的一個(gè)基本可行解 . 簡(jiǎn)單地加以分析 在這個(gè)問題中 ,已經(jīng)知道了 X 線性規(guī)劃問題可行解集合 (可行域 ) R 的頂點(diǎn) , 那么 X 就肯定是一個(gè)可行解了 . 關(guān)鍵是要如何再證明這個(gè)可行解是一個(gè)基本解了 . 可行域 R X 設(shè) X = (x1 , x2 , … , xn)T ,中有 K 個(gè)分量大于 0 , 不失一般性可以設(shè)其前 K 個(gè)分量大于 0 , 則 X =(x1 , x2 , … , xK , 0 , 0 , … , 0 )T 那么約束條件 AX=B 中 AX 的就可以寫成 AX= ??????mnmmnnaaaaaaaaa????212222111211??????x1 X2 … xK 0 … 0 = (P1, P2,…,P k) x1 X2 … xK x1 X2 … xK 0 … 0 ????????????mnnnmkmmkkaaaaaaaaaaaa?????????21212222111211= P1 P2 … Pk … Pn ????????????mnnnmkmmkkaaaaaaaaaaaa?????????21212222111211= x1 X2 … xK 0 … 0 = x1 P1+ x2 P2+…+ xk Pk 最終整理結(jié)果就是： 那么 ,如果我們能夠證明 P1,P2,…,Pk 是線性無關(guān)的 , 則由 P1,P2,…,Pk 列向量所構(gòu)成的矩陣 = x1 P1+ x2 P2+…+ xk Pk x1 X2 … xK 0 … 0 ????????????AX= mnnnmkmmkkaaaaaaaaaaaa?????????21212222111211P1 P2 … Pk … Pn 中的 K個(gè)列向量是線性無關(guān)的 ,則說明必然存在一個(gè) K階子矩陣 BK是非奇異矩陣 ,也就說明 BK是一個(gè)基 .這樣 ,也就證明了 X是一個(gè)基本可行解 . 所以整個(gè)問題就轉(zhuǎn)化為證明向量 P1,P2,…,Pk 是線性無關(guān)的 ， 用反證法來證明這個(gè)問題。 充分性的證明留給同志們自己課下學(xué)習(xí) 定理 3 如果可行域 R 有界 ， 則線性規(guī)劃問題的目標(biāo)函數(shù)一定在其頂點(diǎn)處達(dá)到最大值 。 定理 3 如果可行域 R 有界 ， 則線性規(guī)劃問題的目標(biāo)函數(shù)一定在其頂點(diǎn)處達(dá)到最大值 。 三個(gè)定理 頂點(diǎn)個(gè)數(shù) = mnC 1 單純形法求解線性規(guī)劃問題的基本思想 第二節(jié) 單純形法 1 2 3 對(duì)于線性規(guī)劃問題的標(biāo)準(zhǔn)形式 ， 從可行域中一個(gè)基本可行解出發(fā) ， 尋求使目標(biāo)函數(shù)值有較大增加的另一個(gè)基本可行解 ， 由于基本可行解個(gè)數(shù)是有限的 ， 所以經(jīng)過有限次迭代目標(biāo)函數(shù)值將逐步增大最終達(dá)到最優(yōu) 。 （ 3） 迭代（ 也就是求改進(jìn)的基本可行解 ） 2 x1 + x2 +x3 = 2 … … … … （ 1） X1 + 3 x2 +x4 = 3 … … … … （ 2） X1 , x2 , x3, x4 ≥0 以上選擇出基變量的方法可用數(shù)學(xué)的方法歸納為 min {2/1 , 3/3},也就是 : min {b1/a1j , b2/a2j , b3/a3j, …, bm/amj } 在確定了 x 2 進(jìn)基， x 4 出基以后，為了求得以 x2， x3 為基變量的上述新的基本可行解x (1) 及目標(biāo)值 z (x (1))， 只要對(duì)原約束方程進(jìn)行一次初等變換，即把方程組中第二等式里x2 的系數(shù)化為 1 也就是以第二等式里 x2 的系數(shù)化為 1， 也就是以第二等式中 x2 的系數(shù)為主元進(jìn)行一次高斯消元，得到 2 x1 + x2 +x3 =2 X1 + 3 x2 +x4 = 3 X1 , x2 , x3, x4 ≥0 也就是以第二個(gè)等式中 x2 的系數(shù)為主元進(jìn)行一次高斯消元，得到 1/3x1+x2 +1/3x4 = 1 5/3x1 +x3 1/3x4 = 1 1/3x1+x2 + 1/3x4 = 1