對偶單純形法經(jīng)典運籌學演示

（優(yōu)選）對偶單純形法經(jīng)典運籌學目前一頁\總數(shù)二十二頁\編于二十二點單純形法（原始單純形法）的兩個條件：1、問題為標準型2、有初始基本可行解用單純形法求解目前二頁\總數(shù)二十二頁\編于二十二點對偶單純形法的優(yōu)點：1、不需要人工變量；2、當變量多于約束時，用對偶單純形法可減少迭代次數(shù)；3、在靈敏度分析中，有時需要用對偶單純形法處理簡化。目前三頁\總數(shù)二十二頁\編于二十二點B可逆原始單純形法的基本思路：目前四頁\總數(shù)二十二頁\編于二十二點關于可行基B的典則形式檢驗數(shù)目前五頁\總數(shù)二十二頁\編于二十二點XBXN常數(shù)項檢驗行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b初始單純形表：原始單純形法的迭代過程：目前六頁\總數(shù)二十二頁\編于二十二點對偶單純形法的基本思路：XBXN常數(shù)項檢驗行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b作對偶單純形表：目前七頁\總數(shù)二十二頁\編于二十二點基B的典則形式X1X2X3X4X5檢-2-1000ZX3-3-1100-3X4-4-3010-6X5120013不可行檢驗行≤0分析：若X3或X4所在的行的aij均非負，則問題一定無可行解否則，做換基迭代目前八頁\總數(shù)二十二頁\編于二十二點X1X2X3X4X5檢-2-1000ZX3-3-1100-3X4-4-3010-6X51200131、確定出基變量：設br=min{bi|bi<0}則取br所在行的基變量為出基變量即取X4為出基變量2、確定入基變量：原則：保持檢驗行系數(shù)≤0X1X2X3X4X5檢X3X2X5X1X2X3X4X5檢X3X2X1-2/300-1/30Z+2-5/301-1/30-14/310-1/302-5/3002/31-1000-3/5-2/5Z+12/5001-1-100101/54/56/5100-2/5-3/53/5目前九頁\總數(shù)二十二頁\編于二十二點目前十頁\總數(shù)二十二頁\編于二十二點對偶單純形法步驟：1、找出一個初始對偶可行解。把原問題寫成該基的典則形式時，目標函數(shù)的系數(shù)均≤02、判斷：（1）若B-1b≥0，則得到最優(yōu)解結束（2）若B-1b≥0，則問題無可行解。3、換基迭代：（1）確定出基變量：（2）確定入基變量即找出一個基B，否則轉下一步目前十一頁\總數(shù)二十二頁\編于二十二點不是典則形式X1X2X3X4X5檢21000ZX1111005X4021105X50-4-601-90-1-200Z-10X1X2X3X4X5檢X1X4X2013/20-1/49/400-211/21/210-1/201/411/400-1/20-1/4Z-31/4目前十二頁\總數(shù)二十二頁\編于二十二點注意：對偶單純形法僅限于初始基B對應的典則形式中目標函數(shù)的系數(shù)（檢驗數(shù)）均≤0的情形?？捎脤ε紗渭冃畏˙的典則形式目前十三頁\總數(shù)二十二頁\編于二十二點為什么叫對偶單純形法？目前十四頁\總數(shù)二十二頁\編于二十二點X解檢驗行Z-CBB-1bXBB-1b設B為可行基XBXN解檢驗行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b原始單純形法的基本思路：目前十五頁\總數(shù)二十二頁\編于二十二點X解檢驗行Z-CBB-1bXBB-1b設B為可行基原始單純形法的迭代過程：目前十六頁\總數(shù)二十二頁\編于二十二點對偶單純形法的基本思路：目前十七頁\總數(shù)二十二頁\編于二十二點如何用？目前十八頁\總數(shù)二十二頁\編于二十二點求解線性規(guī)劃問題的方法與步驟：1、把原問題化為標準型2、找初始基，轉第3步，轉第4步3、把問題寫成關于基B的典則形式，用單純形法，對偶單純形法，轉第4步4、增加人工變量，用大M法或兩階段法求解目前十九頁\總數(shù)二十二頁\編于二十二點對應B1的基本解：可用對偶單純形法求解檢驗數(shù)全部≤0不可行對應B2的基本解用單純形法求解