【正文】 3 1 1 1 0 0 60 0 x5 [1] –1 2 0 1 0 20 λj 2 1 1 0 0 0 靜夜四無鄰，荒居舊業(yè)貧。 判斷最優(yōu)時，目標函數(shù)必須化成關(guān)于非基變量的函數(shù)，如果是最優(yōu)解，停止；反之繼續(xù)選代。即令 x1=0， 同時此例中不能超過二個基變量（因為約束條件的系數(shù)矩陣的秩為 2，最優(yōu)解肯定是二為的），還得從 x3, x4中換出一個做非基變量（離基）并需保證非負條件， （ 2）判斷基本可行解是否是最優(yōu)解 如果選 x 3 變量出基（也就是使 x 3 變量變?yōu)榉腔兞?，非基變量的值?0），根據(jù)（ 1）式得到 x 2 =2，將 x 2 =2 代入（ 2）式得到， x4 =3，這就不滿足了第三個約束條件。 定理 2 凸集的頂點對應(yīng)于基本可行解 。 因為 X（ 0） =（ 1u1 ） X（ Y） + u1 X（ K） 而 X（ K） = （ 1u2 ） X（ I） + u2 X（ L） u1 1u1 X（ K） u2 1u2 最后可得 X（ 0） =（ 1u1 ） X（ Y） + u1 （ 1u2 ） X（ I） + u1 u2 X（ L） 可以驗證各頂點前的 系數(shù)之和為 1。是中間點就不是頂點。 證明過程 設(shè)任意 X 和 Y ∈ R， 目標是要證明對于任意 1≥ u ≥0, Z= u X + ( 1 u) Y ∈ R A Z = A （ u X + ( 1 u) Y） 因為 X、 Y ∈ R， 所以 X ≥0， Y ≥0， 而且 AX = B AY = B = A uX + A ( 1 u) Y = u B + ( 1 u) B = B 定理 2 凸集的頂點對應(yīng)于基本可行解 。 a11x1 + a12x2 + … a1mx2 + … + a1nxn = b1 a21x1 + a22x2 + … a2mx2 + … + a2nxn = b2 …… am1x1 + am2x2 + … a2mx2 + … + amnxn = bm x1， x2， … xn ≥ 0 最優(yōu)解 X=(x1 , x2 , … , xm , 0 , 0…0) max Z = c1x1 + c2x2 + … + c nxn 滿足非負條件 可行解 基本 解 取定一個基 基本 可行解 最優(yōu)解 滿足目標函數(shù)要求 解 之 間 的 關(guān) 系 max z= x3 x1 + x2 + x3 + x4+ x5 = 4 x1 + x2 + x3 + x4 x5= 4 xi ≥ 0, i = 1,2,…,5 2 理論分支 例題 1 對于約束方程組 x1 x2 + 2 x3 = 1 x1 + x2 + x3 =1 x1 , x2 , x3 ≥0 系數(shù)矩陣 基 退化解 非退化解 2 理論分支 例 題 2 對于約束方程組 系數(shù)矩陣 基 退化解 非退化解 x1 + x2 x3 = 1 x1 x2 x3 = 2 x1 , x2 , x3 ≥0 6 線性規(guī)劃解的性質(zhì) 設(shè) Ｄ 是 n 維歐氏空間的一個點集 ， 連接Ｄ中任意兩點 X、 Y 的線段仍在Ｄ內(nèi) ， 則稱 Ｄ 為凸集 。 基本解 ——當取定一個基時 ， 令非基變量為 0， 由克萊姆法則可得對應(yīng)于該基的唯一解 。 而凸邊形外的點都不能滿足約束條件 ， 所以凸多邊形內(nèi)的任一點的坐標都是這個線性規(guī)劃問題的一個解 ， 我們稱之為可行解 。我們總是希望收益、效益、效率等指標達到最大化，而對于成本、費用 、支出等指標則希望達到最小化。 單位產(chǎn)品 產(chǎn)品 消耗量 原料 （ 公斤 ） I II 原料總量 A 9 4 360 B ４ ５ 200 C 3 10 300 單位產(chǎn)品利潤（元） 7 12 2 線性規(guī)劃問題的數(shù)學(xué)模型 確定目標：求出生產(chǎn)兩種產(chǎn)品的數(shù)量各為公斤 ， 以使總利潤達到最大 。規(guī)劃論就是研究針對不同需求對有限資源進行分配的一個運籌學(xué)分支。 二是對這個線性規(guī)劃進行求解 。 2）約束條件 。 因為只有二維幾何空間最為直觀 ， 所以圖解法只能用來求解二維線性規(guī)劃問題 ， 也就是只有兩個決策變量的線性規(guī)劃問題 。 ????????????mmmmmmaaaaaaaaa???????212222111211B= a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm x1， x2， … xn ≥ 0 ????????????mnmmnnaaaaaaaaa???????212222111211這是它的系數(shù)矩陣 5 有關(guān)線性規(guī)劃問題解的概念 基 ——設(shè)Ａ為約束方程組中的 m n階系數(shù)矩陣，其秩為 m，（ 秩為 m的意思為 m行線性無關(guān)），又 B是Ａ中 m n非奇異子矩陣（ |B|不等于 0），則稱 B是這個線性規(guī)劃問題的一個基?；究尚薪獾臄?shù)目（非零分量）不大于 m， 并且都是非負的。 首先 ， 線性規(guī)劃問題的可行解 X=(x1 , x2 , … , xn)是一個 n 維向量 ， 它可以看成是一個由 n 個坐標構(gòu)成的點 。 = x1 P1+ x2 P2+…+ xk Pk x1 X2 … xK 0 … 0 ????????????AX= mnnnmkmmkkaaaaaaaaaaaa?????????21212222111211P1 P2 … Pk … Pn 假設(shè) 是線性相關(guān)的 則必然存在 個不全為 的數(shù)， …使 成立。 有界可行域 R X（ 1） X（ 2） X（ H） …… 首先我們來證明 X（ 0） 可用其他頂點進行線性表示 。 定理 2 凸集的頂點對應(yīng)于基本可行解 。 引 例 求解如下線性規(guī)劃 max Z = 2 x1 + 3 x2 2 x1 + x2 ≤2 X1 + 3 x2 ≤3 X1 , x2 ≥0 （ 1） 將上例化為標準形式 max Z = 2 x1 + 3 x2 2 x1 + x2 +x3 =2 X1 + 3 x2 +x4 =3 X1 , x2 , x3, x4 ≥0 第一步 首先要求出其基本可行解來 找初始基本可行解 約束方程的系數(shù)矩陣為 : ),(103101124321 PPPPA ????????此系數(shù)矩陣 A 中的兩行很顯然是線性獨立的，所以它的秩為 2， 我們可以任意地組合其列向量 ，從而得到一個基，并求基本解。 MAX Z ＝ 7 x1 + 12 x2 9 x1 + 4 x2 ≤ 360 4 x1 + 5 x2 ≤ 200 3 x1 + 10 x2 ≤ 300 x1， x2， ， x3 ≥ 0 MAX Z ＝ 7 x1 + 12 x2 9 x1 + 4 x2 + x3 = 360 4 x1 + 5 x2 + x4 = 200 3 x1 + 10 x2 + x5 = 300 x1， x2， ， x3 ， x4 ， x5 ≥ 0 ??????????100010001B= （ 3）對于約束條件是“ ≥”的形式，采用人工造基的方法減去一個非負的松弛變量，再加上一個非負的人工變量總能得到一個單位矩陣。 3 利用單純形表解線性規(guī)劃 結(jié)合實例講解利用單純形表解線性規(guī)劃 max z = 2x1x2+x3 3x1+x2+x3 ≤60 x1x2+2x3 ≤10 x1+x2x3 ≤20 x1,x2,x3 ≥0 將它化為標準形式 maxz=2x1x2+x3 3x1+x2+x3+x4 = 60 x1 x2+2x3 +x5 = 10 x1 +x2 x3 +x6 = 20 x1,x2,x3,x4,x5,x6≥0 CB xB 2 1 1 0 0 0 B x1 x2 x3 x4 x5 x6 0 x4 3 1 1 1 0 0 60 0 x5 [1] –1 2 0 1 0 20 0 x6 1 1 1 0 0 1 10 λj 2 1 1 0 0 0 maxz=2x1x2+x3 3x1+x2+x3+x4 = 60 x1 x2+2x3 +x5 = 10 x1 +x2 x3 +x6 = 20 x1,x2,x3,x4,x5,x6≥0 人工變量求可行基的方法 例題 max z =