管理學運籌學ppt課件(編輯修改稿)

　

【文章內容簡介】 +1=x m+2=x n=0， 得 11 1 12 2 1 121 1 22 2 2 21 1 2 2..................................mmmmm m m m m ma x a x a x ba x a x a x ba x a x a x b? ? ? ???? ? ? ????? ? ? ? ????此方程組有唯一解 XB=(x1， x2， …x m)T， 將這個解加上非基變量取 0的值有 X=(x1， x2， …x m,0,…,0) T,稱 X為線性規劃問題的基解。 顯然，基解中取非零值的變量個數不超過 m， 基解的總數不超過 Cnm個。 基可行解： 滿足非負約束的基解稱為基可行解。 可行基： 對應于基可行解的基。 可行解 基解 基可行解 用矩陣形式表示的基解 考慮標準形式的線性規劃問題： m ax0z C XAX bX???? ??( , ) ,( , ) ,BNBBNNXA B N X A X bXXB N b B X NX bX??? ? ???????? ? ?????令 將 分 塊 得即1 1 1BNB X B N X B b? ? ???左 乘 得10,NBX X B b???令 得10BbX ???? ????即例如 LP問題 Max z=x1x2 . 2x1X2x3 =2 X12x2 +x4 =2 X1+x2 +x5=5 X j?0, j=1,2,3,4,5 2 1 1 0 01 2 0 1 01 1 0 0 1A??????????? ?1 3 4 51 0 00 1 00 0 1B P P P???????????? ?2 1 4 52001101 0 1B P P P??????????是它的兩個基，對應的基解分別為 12( 0 , 0 , 2 , 2 , 5 )( 1 , 0 , 0 , 3 , 6 )TTXX???可見 X1是基可行解， B1是可行基。而 X2不是基可行解。 根據以上定義 可行解集 基礎可行解 最優解 基礎最優解 2. 線性規劃的基本定理 定理 2： LP問題的可行解 X是基可行解的充要條件是它的正分量所對應的 A中的列向量線性無關。 定理 3： 線性規劃問題的基可行解對應可行域的頂點。（ X是基可行解 ?X是 可行域的頂點）（基可行解個數有限） 定理 4：一個 LP問題，若有最優解，則一定存在一個基可行解是最優解。 例 設線性規劃為 ??????????????????0,1226232m a x4321432143214321xxxxxxxxxxxxxxxxz則下述解中為基可行解的是 A.(2,0,4,0)。B.(6,0,3,3)。C.(3,2,3,2)。D.(0,6,0,0) 3. 問題 1) 如何得到第一個基可行解？ 2) 如何判別一個基可行解是否最優？ 3) 如果當前的基可行解不是最優，如何從一個基可行解轉化到另一個基可行解？ 第三節 單純形方法 單純形方法（ Simplex Method） 是 在 1947年提出的。 一、 單純形方法 二、 第一個基可行解的求法 一、單純形方法 1. 典式 2. 最優性檢驗和解的判別 3. 基可行解的改進 4. 單純形方法的基本步驟 5. 單純形表 考慮標準形式的 LP問題 Max CX () . AX=b () X?0 () 假設可行域非空， A為一 m?n實矩陣， r(A)=mn 。 1. 典式 假設 B是一個可行基，不妨設 B是由 A的前 m個列向量組成的，即 A=(B,N)， 則線性規劃問題的等式約束AX=b 可以化成： 11BNX B N X B b????目標函數 Z=CX 可以化成 111101( , )()()BBNNB B N NB N N NB N B NnB j jjmnjjjmXz C X C CXC X C XC B b B N X C XC B b C C B N XC B b xzx????????????? ??????? ? ?? ? ???????011 1 1 1 1 12 2 1 1 2 211( 3 .4 )...... .. ( 3 .5 )........................................ .....................0 1 , 2 , .. .. ..njjjmm m n nm m n nm m m m m n n mjM a x Z Z xx x xx x xx x xx j n?? ? ?? ? ?? ? ???????????? ? ? ? ??? ? ? ?????? ? ? ???????線性規劃問題的典式（典則形式） 典式的特點： （ 1） 約束條件中含有一個單位矩陣，（ 2）目標函數中不含基變量。 有了典式，就很容易寫出線性規劃問題的基解 0 0X ????????其中 12m?????????????????如果基 B是可行基，則 即 X0是基可行解，對應的目標函數值為 z0 。 0??問題：如何判斷一個基可行解是否為最優解呢？ 在典式中，目標函數中非基變量的系數稱為 檢驗數 ，檢驗數是用來判斷相應基可行解是否最優的標志。 3. 基可行解的改進 1) 基的修改： 進基變量、出基變量的選取準則。 2) 迭代： 得到新基對應的典式。 基的修改準則：新基與原有基有 m1 個相同的基變量，只有一個基變量不同。 進基變量： 從非基變量變為基變量的變量 。 出基變量： 由基變量變為非基變量的變量。 1) 進基變量的選取原則 ： 最優性原則：若 ?K0,則與 ?K相對應的變量 xk是非基變量，當 xk變為基變量時，它的值由 0變為正數，比如說xk=?0， 其余的非基變量仍取值為零。由 ()式知，對應新解的目標函數值為 z=z0+ ? ? Kz0， 顯然 ?越大目標函數值越大 。 可行性原則（最小比值原則）： ? 的取值應保證新解仍然是基可行解。 2) 出基變量的選取原則 進基變量和出基變量的選取準則 Max z=z0+ ? m+1xm+1+…+ ? kxk+…+ ? nxn . x1 +a1m+1xm+1+…+ a 1kxk …+ a 1nxn= ? 1 x2 +a2m+1xm+1+…+ a 2kxk …+a 2nxn= ? 2 ………………………………………………………………………………. xm +amm+1xm+1+ …+a mkxk …+ a mnxn= ? m xj?0 j=1,2,…,n 當 xk=??0成為基變量以后，其余非基變量仍然取值為 0。設新基對應的基可行解為X1=(x11,…, x n1)T,則 X1應滿足約束條件，即 x11 + a1k? = ? 1 x21 + a2k ? = ? 2 ……………………………………………. xm1 +amk ? = ? m xj1?0 j=1,2,…,n 由于 xi1必須是非負的，即 xi1 = ? i aik? ?0 (i=1,2,…,m) xk1= ?0 如果 aik?0， 顯然只要 ?0， 就有 xi1 = ? i aik? ?0 ， 對于aik0， 就要求 iika???所以 ?應滿足 0 m in iika??? ???? ????2. 最優性檢驗和解的判別 10 j? ?（ ） 當 所 有 檢 驗 數 時 ， 當 前 基 可 行 解 為 最 優 解 。0 , 0j i j?? ??（ 2 ） 如 果 某 個 非 基 變 量 的 檢 驗 數 而 ， 則 原 問 題 無 界 。0,0jij???? 11（ 3 ） 如 果 某 個 非 基 變 量 的 檢 驗 數 且 至 少 存 在 一 個 i, 使 得 ， 則 可 以 找 到 一 個 新 的 基 可 行 解 X ， 使 得 C X C X .對于 ?j 0,而 aij0,則 ?可以無限大使得目標函數值的增量（ ?j ?）無限大 注意： ，若有幾個非基變量的檢驗數都是正數，則可以任意選取一個正檢驗數對應的非基變量作為進基變量，一般選取最大正檢驗數對應的非基變量。但實際情況表明這種策略不一定最好。 (當 ? j最大時對應的 xj 不一定最大，我們要求的是 ? j ?0最大 ) ，若有幾個比值同時達到最小，可以任意選擇一個，但在新的基本可行解中這些對應分量均為零。從而新的基本可行解是一個退化的基本可行解。假若問題是非退化的，則不會出現這種情況。 迭代（新的基可行解對應的典式的確定） 利用線性方程組的等價變換將約束條件和目標函數化成新基對應的典式，從而求出新的基可行解及相應的檢驗數 4. 單純形方法的基本步驟 Step 1 將線性規劃問題化成典式 ,求出各個非基變量的檢驗數 . Step 2 判斷所有非基變量的檢驗數是否非正 ,若是 ,則結束 。否則轉 step 3. Step 3 選取一個檢驗數大于零的