管理學運籌學ppt課件(完整版)

　　

【正文】 化為非負常數 對于右端常數為負數的約束，可以兩端同時乘以 1。制造每件甲產品需要勞動力 3個，而制造每件乙產品需要勞動力 8個。 1. 圖解法的一般步驟 ： （ 1） 建立直角坐標系，以 為橫軸， 為縱軸。 ?無界解 （ 可行域一定無界 ） 。 可行域凸性的證明思路 設 X1,X2為可行域 R內任意兩點，則 X1∈ R,X2∈ R,將 X1， X2帶入約束條件有 AX1=b,AX2=b,X1和 X2連線上的任意一點可表示為： X=aX1+(1a)X2, (0a1) 則 AX= A[aX1+(1a)X2]=aAX1+AX2aAX2=ab+bab=b, 所以 X∈ ，所以 R為凸集 m ax0Z CXA X bX???? ??四、基可行解及線性規劃的基本定理 1. 基可行解的 定義 2. 線性規劃的基本定理 3. 問題 1. 基可行解的定義 考慮標準形式的線性規劃問題 1 1 2 211 1 12 2 1 111 12 121 1 22 2 2 221 22 21 1 2 212m a x ............................................. ... ... .........0 1 , 2 , ... ,nnnnnnnnm m m n n mm m m njz c x c x c xa x a x a x ba a aa x a x a x ba a as t Aa x a x a x ba a ax j n? ? ? ?? ? ? ????? ? ? ?????? ? ? ? ?????????????基： A是約束方程組的系數矩陣 (設 nm)， 其秩為 m， B是 A中的一個 m階滿秩子方陣，稱 B是線性規劃問題的一個基。 可行基： 對應于基可行解的基。C.(3,2,3,2)。 基的修改準則：新基與原有基有 m1 個相同的基變量，只有一個基變量不同。0 , 0j i j?? ??（ 2 ） 如 果 某 個 非 基 變 量 的 檢 驗 數 而 ， 則 原 問 題 無 界 。 Step 4 若進基變量所對應的約束條件系數全為非正數 ,則原問題無界 ,結束 。 實際上 X1與 X2的連線上的任意點都是最優解 . 例 4：用單純形法求解線性規劃問題（無有限最優解的情況） Max z = 2 x1 + x2 . x1 + x2 + x3 = 5 2 x15 x2 + x4 = 10 x1 , x2 , x3 , x4 ? 0 2 1 0 0 CB B b x1 x2 x3 x4 0 x3 5 1 1 1 0 0 x4 10 2 5 0 1 ?j 0 2 1 0 0 0 x3 10 0 3/2 1 1/2 2 x1 5 1 5/2 0 1/2 ?j 10 0 6 0 1 ? 5 X2的檢驗數為正，但約束條件中 x2的系數全為負，因此該問題無有限最優解。 且取值非零，此時原問題無可行解。 2. 第一階段最優解的基變量中含有人工變量，表明原問題無可行解。 例 7：用兩階段法求解下列線性規劃問題 131 2 31 2 3231 2 3m a x 342139, , 0z x xx x xx x xxxx x x? ? ?? ? ???? ? ? ??????? ??131 2 3 41 2 3 523m a x 3421390 , 1 , . . . 5jz x xx x x xx x x xxxxj? ? ?? ? ? ???? ? ? ? ??????? ???化標準型 第一階段的線性規劃問題為 671 2 3 41 2 3 5 62 3 7m in421390 , 1 , . . . 7jg x xx x x xx x x x xx x xxj??? ? ? ???? ? ? ? ? ???? ? ??? ???第一階段：用單純形法求解輔助問題 0 0 0 0 0 1 1 CB B b x1 x2 x3 x4 x5 x6 x7 0 x4 4 1 1 1 1 0 0 0 1 x6 1 2 1 1 0 1 1 0 1 x7 9 0 3 1 0 0 0 1 ?j 10 2 4 0 0 1 0 0 0 x4 3 3 0 2 1 1 1 0 0 x2 1 2 1 1 0 1 1 0 1 x7 6 6 0 4 0 3 3 1 ?j 6 6 0 4 0 3 4 0 0 x4 0 0 0 0 1 1/2 1/2 1/2 0 x2 3 0 1 1/3 0 0 0 1/3 0 x1 1 1 0 2/3 0 1/2 1/2 1/6 ?j 0 0 0 0 0 0 1 1 得原問題的基可行解 X=(1,3,0,0,0,)T。 ，且取值為 0，這時也得到了原問題的一個最優解。但是實際問題往往并非如此，因此我們需要尋找第一個基可行解，通常使用兩種常用的方法求解第一個基可行解。 Step 5 進行迭代 (用方程組的初等變換法確定新的基對應的典式 )及檢驗數 ),轉 step 2. 121212212m a x 1500 25003 2 652 403 750 , 0z x xxxxxxxx????????????? ???例 1：利用單純形法求下列線性規劃問題 將該問題化成標準形式（也是典式） 121 2 31 2 425m a x 1 5 0 0 2 5 0 03 2 6 52 4 03 7 50 1 , 2 , 3 , 4 , 5jz x xx x xx x xxxxj??? ? ???? ? ??????? ???基變量是： x3 ， x4 ，x5 ， 非基變量是 x1 x2 求出第一個基可行解 X0=(0,0,65,40,75)T， 非基變量的檢驗數均為正數，所以 X0不是最優解。但實際情況表明這種策略不一定最好。 出基變量： 由基變量變為非基變量的變量。 一、 單純形方法 二、 第一個基可行解的求法 一、單純形方法 1. 典式 2. 最優性檢驗和解的判別 3. 基可行解的改進 4. 單純形方法的基本步驟 5. 單純形表 考慮標準形式的 LP問題 Max CX () . AX=b () X?0 () 假設可行域非空， A為一 m?n實矩陣， r(A)=mn 。而 X2不是基可行解。其余變量稱為 非基變量。 ?最優解存在且不唯一 ， 一定存在一個頂點是最優解 ?無解 2. 圖解法求解兩變量 LP問題時可能出現的情況 ： 三、可行區域的幾何結構 1. 凸集及其性質 2. 可行域的凸性 凸集 ： 若集合 S中任意兩點 X(1)?S, X(2)?S的連線上的所有點也都是集合 S中的點，則稱 S為一個凸集 。 （ 3）作出目標函數的等值線簇，找出目標函數值的增加（或減小）方向，用箭頭表示。制造每件甲產品需要原材料 1000克，而乙產品需要原材料 600克，車間共有原材料 5500克可供利用。 39。 2. 線性規劃問題的一般形式 1 1 2 2m a x( m i n) ... nnz c x c x c x? ? ? ?11 1 12 2 1 121 1 22 2 2 21 1 2 212... ( , )... ( , ).......................................... ( , ), , ..., 0nnnnm m m n n mna x a x a x ba x a x a x ba x a x a x bx x x? ? ? ? ? ???? ? ? ? ? ????? ? ? ? ? ? ????? （ 1） （ 2） （ 3） 一般形式的簡化表達 1( , )0nij j ijja x bx?? ? ? ???? ???1m a x ( m i n ) n jjjz c x?? ?m i n..0CXA X bstX????? m a x..0CXA X bstX????? 規范形式 極小化問題 極大化問題 3. 線性規劃的標準形式 1m a x n jjjz c x?? ?10nij j ijja x bx???? ( 1, 2 , ..., )im?( 1, 2,..., )jn?. 標準形式的矩陣表達 m ax0Z CXA X bX???? ?? ???????????????mnmmnnaaaaaaaaaA. . .. . .. . .. . .. . .. . .. . .212222111211???????????????nxxxX?21???????????????mbbbb?21? ?ncccC ?21?標準形式的特點 ： (1).目標函數極大化 (2).約束條件全部是等式 (3).所有的變量都是非負的 (4).約束條件右端常數為非負的 4. 一般形式向標準形式的轉化 ： (1) 目標函數極大化 對于極小化的目標函數