【正文】 4 x5 0 2 0 x3 x1 x5 15 4 1 0 5 1 0 0 1 1/3 0 1/6 0 0 2/3 0 1/6 1 0 1/3 0 1/3 0 基可行解為： 1,0,15,0,4 54321 ????? xxxxx目標函數(shù)值為： z=8 15/5 4/(1/3) 1/(2/3) 2 1 0 0 0 Cb Xb b x1 x2 x3 x4 x5 0 2 1 x3 x1 x2 15/2 7/2 3/2 0 0 1 5/4 5/2 1 0 0 1/4 1/2 0 1 0 1/4 3/2 0 0 0 1/4 1/2 廣東工業(yè)大學管理學院 89 2 1 0 0 0 Cb Xb b x1 x2 x3 x4 x5 0 2 1 x3 x1 x2 15/2 7/2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 1/2 0 1 0 1/4 3/2 0 0 0 1/4 1/2 最優(yōu)解為： 0,0,215,23,27 54321 ????? xxxxx最優(yōu)目標函數(shù)值為： z= 8 189。為了簡化運算過程，并使運算過程程序化?；氐降冢?2）步。 （ 5）旋轉運算。用換入變量在各方程中的正的系數(shù)去除該方程的右端常數(shù)，在除得的商中取最小者，該最小商所在方程中的基變量就是換出變量。取最大的正檢驗數(shù)對應的變量為換入變量。若是，結束運算；否則進行下一步。 一般地，對一個基可行解而言， 若非基變量的檢驗數(shù)中存在正數(shù)，則該解不是最優(yōu)解；否則它一定是最優(yōu)解 。 由于 x2的系數(shù)（檢驗數(shù)）為 1/3，是正數(shù)，因此如果能使 x2取正數(shù)，則目標函數(shù)還能增加。 因此對應于這一新的基可行解，目標函數(shù)值為 z = 8。為了判斷這一新的基可行解是否為最優(yōu)解， 需要將原目標函數(shù)改寫為新的非基變量的函數(shù) 。 旋轉運算可以利用對約束方程組進行加減消元法完成。 ??????????????????0,524261552m a x515214213221xxxxxxxxxxxxz?對例 1 由于已經(jīng)確定了 x1是換入變量。因此取 xl為換出變量。由于 )( klkllkl xabax ??因此 xl = 0。若 xk0，則第 i個約束條件可以寫成 ininkikii bxaxaxxa ??????? ???11并且由于其余的非基變量保持零值，因此 )( kikiiki xabax ??廣東工業(yè)大學管理學院 76 由此可見為保證 xi≥0，就必須 從而對所有的 i，若 aik0，則 ikik abx ?ikik abx ?廣東工業(yè)大學管理學院 77 若確定 xk為換入變量，則可估計 xk的取值，使得： 其余的決策變量都取非負值；并且目標函數(shù)得到盡可能的增加 。 換出變量與 換入變量 是密切相關的。 廣東工業(yè)大學管理學院 74 確定換入變量 目的： 新的基變量換入后，會使目標函數(shù)值增大（通常還希望增加的越大越好） 因此選擇在目標函數(shù)中系數(shù)為正值的非基變量作為換入變量，通常取在目標函數(shù)中最大的正系數(shù)對應的非基變量為換入變量，即 取最大的正檢驗數(shù)對應的非基變量為換入變量 。 所謂 相鄰 的基可行解是指兩個基可行解只有一個基變量不同而其它的基變量都相同。這時目標函數(shù)中各變量的系數(shù)稱為 檢驗數(shù) 。所以目標函數(shù)還未達到其最大值。將這個解代入到目標函數(shù)，就可得到這個解對應的目標函數(shù)值。 廣東工業(yè)大學管理學院 71 已知初始基變量，求初始基可行解 以例 1為例說明求法。初始基可行解對應的基，也稱 初始可行基 ，它具有特定的形式，它是 單位矩陣或者由單位矩陣經(jīng)過交換列以后得到的矩陣 。 凸集 凸集 不是凸集 頂點 廣東工業(yè)大學管理學院 66 幾個基本定理 定理 1 若 LP問題存在可行解，則問題的可行域為凸集 定理 2 LP問題的基可行解對應著 LP問題可行域的頂點 定理 3 若 LP問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解 廣東工業(yè)大學管理學院 67 單純形法迭代原理 單純形法迭代步驟： 找出一個基可行解 是否為最優(yōu)解 停止 （依據(jù)： LP問題的最優(yōu)解若存在，則一定有一個基可行解為最優(yōu)解。 ??????????????????0,41025..32m a x543215242131321xxxxxxxxxxxxtsxxxz廣東工業(yè)大學管理學院 64 序號 x1 x2 x3 x4 x5 z 是否基可行解 1 0 0 5 10 4 5 是 2 0 4 5 2 0 17 是 3 5 0 0 5 4 10 是 4 0 5 5 0 1 20 否 5 10 0 5 0 4 15 否 6 5 0 0 是 7 5 4 0 3 0 22 否 8 2 4 3 0 0 19* 是 廣東工業(yè)大學管理學院 65 凸集及其頂點 凸集 ——如果一個非空集合中任意兩點的連線段上所有點仍屬于該集合，則稱該集合為 凸集 。并且每一個基可行解對應著可行域的一個頂點。因此 LP問題的基解不是唯一的，但總數(shù)不超過 此外基解不一定是可行解 。 廣東工業(yè)大學管理學院 61 LP問題的基本概念（續(xù) 2） 基解 在約束方程組 中令所有的非基變量 xm+1=xm+2=…=x n=0,則由于剩下的變量（基變量）構成的方程組的系數(shù)行列式 |B|≠0，因此約束方程組此時有唯一的解XB=（ x1, x2, …, x m, 0, …, 0) T這個解稱為 LP問題的（對應基 B的） 基解 。若 B是 LP問題的一個基，則它的每一個列向量稱為 基向量 ，與基向量對應的變量稱為 基變量 ? ?mmmmmmmPPPaaaaaaaaaB ???????21212222111211??????????????LP問題的基本概念（續(xù) 1） 廣東工業(yè)大學管理學院 60 秩的概念 如果矩陣 A中有一個 r階子式 Dr不等于零，而所有 r+1階子式（如果存在的話）的值全等于零，則稱 Dr為矩陣 A的一個最高階非零子式，其階數(shù) r稱為矩陣 A的秩。 LP問題的可行域是一個凸集。所有可行解的集合稱為可行域。 采用圖解法時通常無須將 LP問題化為標準形式 廣東工業(yè)大學管理學院 54 圖解法步驟： 在平面上建立直角坐標系 圖示約束條件，找出可行域 圖示目標函數(shù) 尋找最優(yōu)解 廣東工業(yè)大學管理學院 55 例 1 Max z=2x1+x2 . 5x2≤15 6x1+2x2 ≤24 x1+x2 ≤5 x1,x2≥0 x2=3 3x1+x2 =12 x1+x2 =5 最優(yōu)解 可行域 x1 x2 廣東工業(yè)大學管理學院 56 線性規(guī)劃問題幾種可能的結局 1. 有唯一的最優(yōu)解 2. 有無窮多個最優(yōu)解 3. 無界解 4. 無解（無可行解） 廣東工業(yè)大學管理學院 57 由圖解法得到的啟示 1. 揭示了求 LP問題的解的可能情況 2. 若可行域非空，則必為凸集 3. 若 LP問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一是可行域的頂點 4. LP問題的求解思路（單純形法） 先找出可行域的任一頂點，計算該頂點處的目標函數(shù)值；比較周圍相鄰頂點的目標函數(shù)值是否比這個值大，如果為否，則該頂點為最優(yōu)解（或最優(yōu)解之一）對應的點，否則轉到比這個點目標函數(shù)值更大的頂點，重復上述過程，直到找出目標函數(shù)值最大的頂點為止。 ? 圖解法的目的有二，一是利用它來說明 LP問題求解的可能結局。 （ 5）取非正值的變量。 廣東工業(yè)大學管理學院 46 線性規(guī)劃問題的（模型）的標準形式 ??????????????),2,1(0),2,1(m a x11njxmibxaxczjnjijijnjjj??廣東工業(yè)大學管理學院 47 標準形式的特征 ? 目標函數(shù)為求最大值 ? 約束條件均為等式 ? 資源常數(shù)非負 ? 決策變量只能取非負值 不具備上述所有特征的線性規(guī)劃問題稱為非標準形式的線性規(guī)劃問題 廣東工業(yè)大學管理學院 48 化線性規(guī)劃問題為標準形式的方法 （ 1）目標函數(shù)為求最小值的，即 ??? njjj xcz1m i n將目標函數(shù)用其相反數(shù)代替，得到新的目標函數(shù) ，即令 則 求原目標函數(shù)的最小值問題等價于求新目標函數(shù)的最大值問題 zz ???廣東工業(yè)大學管理學院 49 化線性規(guī)劃問題為標準形式的方法（續(xù) 1） （ 2）右端常數(shù)小于零，即 將該約束條件兩端同乘（ 1） 0?ib（ 3）約束條件為不等式 “ ”型，左端加上一個非負的松弛變量 “ ”型，左端減去一個非負的剩余變量 ??松弛變量和剩余變量在目標函數(shù)中的系數(shù)為零 廣東工業(yè)大學管理學院 50 化線性規(guī)劃問題為標準形式的方法（續(xù) 2） （ 4）取值無約束的變量。)。 廣東工業(yè)大學管理學院 39 模型的特征 ? 模型的三個要素 （ 1）決策變量 （ 2）目標函數(shù) （ 3）約束條件 ? 線性規(guī)劃模型的特征 （ 1）目標函數(shù)是決策變量的 線性 函數(shù) （ 2）約束條件是含決策變量的 線性 等式或不等式 廣東工業(yè)大學管理學院 40 線性規(guī)劃模型的一般形式 ???????????????????????????0,),(),(),(m i n )m a x (21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz???????或或或或廣東工業(yè)大學管理學院 41 線性規(guī)劃模型的一般形式（續(xù) 1） ? 決策變量： ? 價值系數(shù)： ? 資源常數(shù)： ? 技術（工藝）系數(shù)： njx j ,2,1, ??njc j ,2,1, ??mib i ,2,1, ??njmia ij ,2,1。 總共用料是 321 xxx ??要達到最省料的目的，就必須使總用料最小。 廣東工業(yè)大學管理學院 37 例 2 設有一批規(guī)格為 10米長的圓鋼筋，將它截成分別為 3米，4米長的預制構件的短鋼筋各 100根，問怎樣截取最省料。生產(chǎn)這兩種產(chǎn)品的單位資源消耗