【正文】 sxcxcxcz）或（nmmnmmnnnccbbbaaaaaaaaamxxx??????????212121222211121121c21價值系數動活資源決策變量決策變量及各類系數之間的對應關系 二、線性規(guī)劃問題的數據模型 線性規(guī)劃模型的一般表達形式 （ 1）一般形式 模型的簡寫形式為： ????????????????),. ..,1(0),. .... .,2,1(),(..m a xm inj11njxmibxatsxczinjjijnjjj）或（二、線性規(guī)劃問題的數據模型 線性規(guī)劃模型的一般表達形式 （ 1）一般形式 （ 2）向量形式 ?????????????),. ..,1(0),(P..CXm a xm inj1njxbxtsznjjj）或（???????????????????????????????????????????mmjjjjnnbbbbnjaaaPxxxXccc...)。,...,2,1(,...。...。,...,C21212121 ）（式中：二、線性規(guī)劃問題的數據模型 線性規(guī)劃模型的一般表達形式 （ 1）一般形式 （ 2）向量形式 （ 3）矩陣形式 ????????0X),(AX..CXm a xm inbtsz）或（?????????????mnmmnnaaaaaaaaa.....................A212222111211式中：A為約束方程組（約束條件）的 系數矩陣 。 二、線性規(guī)劃問題的數據模型 線性規(guī)劃模型的標準形式 為了研究問題的方便，規(guī)定線性規(guī)劃問題的標準形式為： ??????????????),...,1(0),......,2,1(..m a xj11njxmibxatsxczinjjijnjjj線性規(guī)劃模型的標準形式 對標準形式的說明： （ 1）標準形式的線性規(guī)劃模型中的要求 ① 目標函數為 求最大值 （有些文獻規(guī)定是求最小值）； ② 約束條件 全為等式 ，約束條件右端常數項 bi全為 非負值 ； ③ 變量 xj的取值全為 非負值 。 ??????????????),...,1(0),......,2,1(..m a xj11njxmibxatsxczinjjijnjjj線性規(guī)劃模型的標準形式 （ 2）非標準形式的線性規(guī)劃問題轉化為標準形式的方法 ① 目標函數為求最小值 只需令 z’=z，則目標函數轉化為 ② 約束條件為不等式 當約束條件為 “ ≦ ” 時，例如 2x1+2x2≦12 可令 x3=12 2x12x2或者 2x1+2x2+x3=12。 顯然， x3≧0 ，稱 x3為 松弛變量 。 ???njjj xcz1m in????njjj xcz139。m a x線性規(guī)劃模型的標準形式 （ 2）非標準形式的線性規(guī)劃問題轉化為標準形式的方法 ② 約束條件為不等式 當約束條件為 “ ≧ ” 時，例如 10x1+12x2≧ 18 可令 x4=10x1+12x218或者 10x1+12x2x4=18。 顯然， x4≧0 ，稱 x4為 剩余變量 。 松弛變量和剩余變量在實際問題中分別 表示未被利用的資源數和短缺的資源數 ，均未轉化為價值和利潤。因此在目標函數中，松弛變量和剩余變量的系數均為零。 線性規(guī)劃模型的標準形式 （ 2）非標準形式的線性規(guī)劃問題轉化為標準形式的方法 ① 目標函數為求最小值 ② 約束條件為不等式 ③ 無約束變量。 設 x為無約束變量，則令 無約束變量的實際含義：若變量 x代表某產品當年計劃數與上一年計劃數之差，則 x的取值可正可負。 0,0 39。39。39。39。39。39。 ???? xxxxx ，二、線性規(guī)劃問題的數據模型 例如 14 將下述線性規(guī)劃模型化為標準形式 ??????????????????取值無約束，3213213213213210,632342392..32m inxxxxxxxxxxxxtsxxxz二、線性規(guī)劃問題的數據模型 例如 14 【 解 】 ： 按規(guī)則將問題轉化為： ????????????????????????????0,,633234223932..00332m a x5439。39。339。32139。39。339。321539。39。339。321439。39。339。3215439。39。3339。2139。xxxxxxxxxxxxxxxxxxxxtsxxxxxxz 63323,422329),0,0(,39。39。339。32139。39。339。321539。39。339。321439。39。339。339。39。339。3339。?????????????????????xxxxxxxxxxxxxxxxxxzz令X4為松弛變量 X5為剩余變量 二、線性規(guī)劃問題的數據模型 線性規(guī)劃模型的標準形式 自己動手試一試：將下列線性規(guī)劃模型轉化為標準型。 ????????????0,24261553..2m a x21212121xxxxxxtsxxz????????????????0,24261553..002m a x43214213214321xxxxxxxxxxtsxxxxz二、線性規(guī)劃問題的數據模型 線性規(guī)劃模型的標準形式 自己動手試一試：將下列線性規(guī)劃模型轉化為標準型 ????????????????????????無約束43214321432143214321,0,2232x143224..5243m inxxxxxxxxxxxxxxxtsxxxxz參考答案 : ????????????????????????????????0,2)(232x143224..00)(5243m a x39。39。439。4321639。39。439。4321539。39。4439。32139。39。439。43216539。39。439。432139。xxxxxxxxxxxxxxxxxxxxxtsxxxxxxxz)0,0(, 39。39。439。439。39。439。4439。 ?????? xxxxxzz令三、求解線性規(guī)劃模型的圖解法 線性規(guī)劃模型的基本求解方法有： 圖解法 和單純形法。 圖解法直觀明了，但是只適用于兩個變量的問題，目前常用的方法是單純形法。 圖解法的步驟： 第 1步：建立坐標系，畫出由約束條件所確定的區(qū)域 第 2步：對任意確定的 z，畫出目標函數所代表的直線 第 3步：平移目標函數直線，確定最優(yōu)解。 三、求解線性規(guī)劃模型的圖解法 圖解法的實例 例 15 用圖解法求最優(yōu)解 ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxz圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 1）先分析約束條件是如何圖示的。 ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxzx1 x2 Q4 Q3 Q2 Q1 圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 1）先分析約束條件是如何圖示的。 ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxzx1 x2 Q4 Q3(3,3) Q2 (4,2) Q1 從圖形中我們看到陰影部分的圖形是凸的，以后我們要證明，如果線性規(guī)劃問題存在可行域，則可行域一定是一個凸集。 圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 2）目標函數的幾何意義。 目標函數 maxz=2x1+3x2， z是待定的值，將函數改寫為 x2=2/3x1+z/3，由解析幾何知，這是變量為 z、斜率為 2/3的一族平行的直線。如圖！ 這族平行線中，離原點越遠的直線， z的直線越大。若對 x x2的取值無限制， z的值可以無限增大。但在線性規(guī)劃問題中，對 x x2的取值范圍是有限制。 ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxz圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 2）目標函數的幾何意義。 ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxzx1 x2 33212zxx ???Z=6 圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 3）最優(yōu)解的確定。 最優(yōu)解必須滿足約束條件的要求，并使目標函數達到最優(yōu)值。因此 x x2的取值范圍只能從凸多邊形 OQ1Q2Q3Q4中去尋找。 從圖中看到，當代表目標函數的直線和約束條件包圍成的凸多邊形相切時為止，切點就代表最優(yōu)解的點。 思考：為什么 z直線不能繼續(xù)向右上方移動？ ??????????????）（）（）（）（40,3515216411222..32m a x21212121xxxxxxtsxxzx1 x2 Q4 Q3(3,3) Q2 (4,2) Q1 圖解法的實例 例 15 用圖解法求最優(yōu)解 （ 3）最優(yōu)解的確定。 例 15中目標函數直線與凸多邊形的切點是 Q3，該點的坐標（ 3， 3），將其代入到目標函數得 z=15。 圖解法的實例 例 16 將例 15中的目標函數 max z=2x1+3x2改為maxz=3x1+3x2，則線性規(guī)劃問題的最優(yōu)解為？ 最優(yōu)解為 Q3Q2上的所有點，因此此問題有無窮多個最優(yōu)解。 ??????????????）（）（）（）（40,3515216411222..33m a x21212121xxxxxxtsxxzx1 x2 Q4 Q3(3,3) Q2 (4,2) Q1