運籌學基礎及應用第五版 胡運權第一章.ppt

1、1 .一般線性規(guī)劃問題的數學模型，2 .圖解法，3 .單純形法原理，4 .單純形法的計算順序，5 .進一步討論單純形法，6 .單純形法的改進，7 .例子和Matlab的解法，第一章線性規(guī)劃和單純形法，1 .一般線性規(guī)劃問題的數學模型，如附圖所示一、問題的提出，有企業(yè)計劃生產I、ii兩種產品。 這兩種產品要分別用a、b、c、d四種設備加工。 生產產品I，各設備分別為2、1、4、0h，生產產品ii，各設備必須分別為2、2、0、4h。 已知在各設備的計劃期間生產這兩種產品的能力分別為12、8、16、12h，另外，生產產品I的企業(yè)可以獲得2元利潤，生產產品ii的企業(yè)可以獲得3元利潤，企業(yè)可以安排生產兩

2、種產品多少1 .一般線性規(guī)劃問題的數學模型，條件：實現目的：2，線性規(guī)劃問題的數學模型，三個組成部分：1 .決策變量：是決策者為了實現計劃目標所采取的方案、措施，問題中應確定的未知量。 2 .目標函數：指定要實現問題的目的的請求，并且是被表示為決策變量的函數。 3 .約束條件：根據在確定變量取值時接收的各種可用資源的限制，被表示為包含確定變量的方程式或不等式。 一般線性規(guī)劃問題的數學模型：目標函數：制約條件：簡稱：矩陣形為：中：三，線性規(guī)劃問題的標準形，標準形：標準形的特征：4 .決定變量的值不為負。 1 .目標函數求極大值，2 .制約條件都是方程式，制約條件右端的常數項都不是負，一般的線性規(guī)

3、劃問題是標準型：1 .目標函數是極小值：令：即：2 .制約條件是不等式：(1)制約條件是“”的情況：可能：很明顯，(2)制約條件是“”的情況稱為剩馀變量。緩和變量和剩馀變量統(tǒng)稱為緩和變量，(3)目標函數中的緩和變量的系數表示緩和變量和剩馀變量分別未被充分利用的資源和超過的資源，所以沒有被轉換成價值和利益，所以在目標函數中系數為0。 3 .取值沒有制約的變量。 如果變量x表示產品的年計劃數和上一年計劃數的差，則x取的值是正還是負是明確的，在此情況下，可以：例如，將下一個線性計劃建模為標準形，解：取標準形：求解線性計劃問題：從滿足約束方程和約束不等式的決定變量中取值，找到目標函數為最大的值。 四、

4、線性規(guī)劃問題的解、可行解：滿足制約條件的解稱為可執(zhí)行解，可執(zhí)行解的集合稱為可執(zhí)行域。 最佳解：使目標函數為最大值的可執(zhí)行解。 基：約束方程的滿秩子矩陣被稱為規(guī)劃問題的一個基，基中的各列向量被稱為基向量，與基向量相對應的變量被稱為基變量，其他變量被稱為非基變量。 基解：在制約方程式中，所有的非基變量都為0，可以解基變量的唯一的解，該解和非基變量的0一起構成基解。 基本可執(zhí)行解：滿足變量的非負的基本解稱為基本可執(zhí)行解，可執(zhí)行基：對應于基本可執(zhí)行解的基本稱為可執(zhí)行基，例4說明基本、基本變量、基本可執(zhí)行解和可執(zhí)行基是什么，實現目的： n維空間中線性規(guī)劃問題的概念的確立和解決一般的線性規(guī)劃問題的單求解下

5、一個線性規(guī)劃問題：2 .線性規(guī)劃問題的圖解法，畫出線性規(guī)劃問題的可能域：目標函數的幾何意義：確定最佳解：圖解法的步驟：建立坐標系，建立滿足圖中所示約束條件的解的范圍，創(chuàng)建目標函數的圖表，確定最佳解。無限多最佳解的情況：目標函數和某個制約條件正好平行，沒有邊界解(或沒有最佳解)的情況：可執(zhí)行域上沒有邊界，沒有可執(zhí)行解的情況：制約條件沒有共同范圍，圖解法的啟發(fā)：線性規(guī)劃問題的情況：唯一最佳解，無限多最佳解，沒有邊界解線性規(guī)劃問題存在可執(zhí)行域時，如果在可執(zhí)行域中存在作為凸集的線性規(guī)劃問題的最佳解，則最佳解或最佳解之一一定能在可執(zhí)行域的頂點取得的解題的想法是，首先尋找凸集的任一頂點，計算其目標函數值。

6、 比較該相鄰頂點的函數值，如果更好，則按點移動，直到找到最佳解為止。 3 .單純形法的原理、凸集：如果是集合c中的任意兩點，其連接上的所有點都是集合c中的點。 上圖的(1)(2)是凸點集合，(3)(4)不是凸點集合，因為頂點：對于凸點集合c中的點x，不存在c中的其他兩個不同點，所以x在它們的連接上時，將x稱為凸點集合的頂點。 一、線性規(guī)劃問題的基本定理，定理一線性規(guī)劃問題中存在可執(zhí)行解的話，問題的可執(zhí)行域就是凸集。 定理二線性規(guī)劃問題的基本可執(zhí)行解x對應于線性規(guī)劃問題可執(zhí)行域(凸集)的頂點。 定理三、線性規(guī)劃問題中如果有最佳解的話，必然存在一個基本可行的解才是最佳解。 根據以上三個定理求出線性

7、規(guī)劃問題的最佳解，只要比較與可執(zhí)行區(qū)域(凸集)的各頂點對應的目標函數值即可，最大的是我們求出的最佳解。 定理1 :如果LP模型中存在可執(zhí)行解，則可執(zhí)行區(qū)域為凸集。 證明：假設maxz=CXst.AX=bX0，其可能域為c，X1、X2為其可能解，X1X2，則X1c、X2c，即AX1=b、AX2=b、X10、X20， x為x1、x2連接線上的點，即x=x c是凸集合。 三個基本定理：引理：線性規(guī)劃問題的可執(zhí)行解X=(x1，x2，xn)T為基本可執(zhí)行解的充分條件是，與x的正分量對應的系數列向量是線性獨立的。 證明： (1)必要性：與x基本可執(zhí)行解x的正分量對應的系數列向量的線性獨立，可以設為X=(x

8、1，x2，xk，0，0)T，如果x是基本可執(zhí)行解，則根據基本可執(zhí)行解的定義，與x1，x2，xk對應的系數列向量P1，P2，Pk是線性的(2)充分性：設與x正分量對應的系數列向量的線性獨立x為基本可能解的a的等級為m，則x的正分量的個數km； 當k=m時，x1、x2和xk的系數列向量P1、P2、 Pk構成基礎，8756； x基本上是可能的解。 在k0、xj=0時，yj=ZJ=0，8756； pjyj=，j=1，n，pjyj=b(1)，j=1，r，pjzj=b(2)，j=1，r，(yj-zj)pj=0，j=1，r，(1)-(2)是必要的，(y1-Z1 ) P1 (y1 z1=CX1=CX0-C=z

9、max-C、z2=cX2=cx0c=zmaxcz0=zmaxz1、z0=zmaxz2、8756； z1=z2=z0，即X1、X2也是最佳解，如果X1、X2還不是頂點，則頂點可以這樣遞歸地推論直到成為最佳解為止。 因此，基本上找到可行的解作為最佳解是必然的。 定理3 :線性計劃模型中如果有最優(yōu)解，基本上一定存在可執(zhí)行的解。 證明：如果X0=(X10，X20，xn0)T是線性規(guī)劃模型的最佳解，則z0=zmax=CX0的X0基本上不是可能的解，即不是頂點，足夠小的話，X1=X0-0，x2=x0，即x1， x2是可能的解，簡單的形法的計算步驟：初始基本上是可能的解，STOP，y，n，二，確定初始基本可

10、行解，線性規(guī)劃問題的最佳解必須在基本可行解中獲得，我們首先找到了初始基本可行解。 然后，切換至可以在別的基礎上執(zhí)行的解，直到找到最佳解為止。給出的線性規(guī)劃問題：所以約束方程的系數矩陣為：因為該矩陣包含一個單位子矩陣，所以以該單位矩陣為基礎，一個基本可執(zhí)行解：其標準形式為：三，從初始基本可執(zhí)行解變換為另一個基本可執(zhí)行解，對初始可執(zhí)行解的系數矩陣進行初等行變換，構建一個新的單位矩陣從一個基本可執(zhí)行解到另一個基本可執(zhí)行解的轉換在不損失一般性的情況下，基本可執(zhí)行解X0=(x10，x20，x0，XM 0，0， 0)T，前m個分量為正值，秩為m，其系數矩陣為p1p2、 pmpm1、 pj.pnb 10、0

11、a1、m1a1j1nb101、0a2、m1a2ja2nb200、1am m 1amjamnbm， 喀嚓喀嚓喀嚓喀嚓喀嚓喀嚓地653即Pj=aijpi，移項，兩端乘以0 (2)，i=1，m，i=1，m 通過全部將xi0-aij0取得得足夠小，i=1、m、X1=(x10-a1j、x20-a2j、xm0-amj、0、0)T也是可以理解的。 假設min-aij0=-，則X1的前m個組件中至少有一個xL1為0。 xi0，aij，aLj，xL0，I，8756； p1、P2、PL-1、PL 1、Pm、Pj與線性沒有關系。x1也是基本上可能的解。 四、最優(yōu)檢查和解的判別，四、最優(yōu)檢查和解的判別，在所有情況下，

12、與現有頂點相對應的基本可執(zhí)行解是最優(yōu)解。 在所有情況下，還有一個非基變量，在能發(fā)現的情況下，這個線性規(guī)劃問題有無限的最佳解。 3 .存在一個者，存在向量的所有分量，并且可選地，如果是一定的，則存在邊界解。 由于0，有以下結論： z1=z0 j，4 .簡單形法的計算步驟，第一步：求初始可執(zhí)行解的列初始簡單形表，表的最上列是各變量的目標函數中的系數，最左列是各基變量的目標函數中的系數。 2 .表的最后一行是檢查數。 第二步：進行最佳性檢查，表中所有的檢查數，表中的基本可執(zhí)行解是問題的最佳解，到現在為止計算了，不然就轉到下一步。 第三步：轉換為新的基本可執(zhí)行解，構建新的單純形表，1 .確定變換變量，

13、2 .確定變換變量，3 .轉換為新的單純形表，(1)、(2)、(3)檢測常數的求出方法與初始單純形表的求出方法相同，第四步重復三個步驟，例子5用簡單形式法求解線性規(guī)劃問題，解：把原來的線性規(guī)劃問題變成標準形式的第一步驟：基于系數矩陣的單位矩陣部分，得到初始基的可執(zhí)行解，列出初始簡單形式表，第三步驟：1 .確定變換變量，2 .確定變換變量由于上表中所有的檢驗數都在零以下，所以得到了最佳解，最佳解為：代入目標函數，最佳值：計算檢驗數具有相同的值時，可以從其中選擇一個變量作為代入變量。 如果計算值相同，也可以從其中選擇一個作為轉換變量。 注意：5 .簡單形法的進一步研究，一、人工變量法，上節(jié)例5的線

14、性規(guī)劃問題的考察：化標準形：其系數矩陣為：系數矩陣中存在單位矩陣，因此容易找到初始可執(zhí)行基。 然而，可能不同，考慮下一個線性規(guī)劃問題：標準型：例6，此問題的系數矩陣：因為此矩陣中不包含單位矩陣，所以很難找到初始基礎。 當這個線性規(guī)劃問題的系數矩陣不包含單位矩陣時，我們通常采用添加人工變量的方法，人工構建單位矩陣。 這種方法是人工變量法。 為了構建單位矩陣，在系數矩陣中添加了兩列單位列向量，系數矩陣為：線性規(guī)劃問題的制約條件為：人為地添加，因此被稱為對應的變量，人工變量。在添加目標函數中人工變量的系數：人工變量之前，在線性規(guī)劃問題的標準形式中，每個約束條件都已經是等式約束，并且為了確保等式約束是

15、不變的，在最佳解中，人工變量的取值必須為0。 因此，如果將目標函數中的人工變量的系數設為任意大的負值來表示為“”的話，只要人工變量不使值為零，目標函數就不能極大化。 由于目標函數加：m處理人工變量的方法，大m法，求解過程：所以最佳解是：二，二階段法，大m處理人工變量時，計算機求解產生了錯誤，從而產生了二階段法。 的雙曲馀弦值。 第一階段：首先，解決目標函數中只包含人工變量的線性規(guī)劃問題。 將目標函數中其他變量的系數設為零，將人工變量的系數設為某個正的常數(一般為1 )，在保持原來的問題約束條件的同時，求出將該目標函數極小化時的解。 第二階段：從第一階段的最終單純形表中刪除人工變量，根據原問題的目標函數繼續(xù)尋找原問題的最佳解。 三、關于解的判別，所有情況下，又有一個非基變量，可以發(fā)現的情況下，這個線性規(guī)劃問題有無限的最佳解。 例7 .解線性規(guī)劃問題：在圖解法中，我們知道這個問題有無限解。 其標準形為：用單純形法計算，最終的單純形表為：從表中得到最佳解