對(duì)偶單純形法經(jīng)典運(yùn)籌學(xué)演示

（優(yōu)選）對(duì)偶單純形法經(jīng)典運(yùn)籌學(xué)目前一頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)單純形法（原始單純形法）的兩個(gè)條件：1、問(wèn)題為標(biāo)準(zhǔn)型2、有初始基本可行解用單純形法求解目前二頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)對(duì)偶單純形法的優(yōu)點(diǎn)：1、不需要人工變量；2、當(dāng)變量多于約束時(shí)，用對(duì)偶單純形法可減少迭代次數(shù)；3、在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡(jiǎn)化。目前三頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)B可逆原始單純形法的基本思路：目前四頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)關(guān)于可行基B的典則形式檢驗(yàn)數(shù)目前五頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)XBXN常數(shù)項(xiàng)檢驗(yàn)行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b初始單純形表：原始單純形法的迭代過(guò)程：目前六頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)對(duì)偶單純形法的基本思路：XBXN常數(shù)項(xiàng)檢驗(yàn)行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b作對(duì)偶單純形表：目前七頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)基B的典則形式X1X2X3X4X5檢-2-1000ZX3-3-1100-3X4-4-3010-6X5120013不可行檢驗(yàn)行≤0分析：若X3或X4所在的行的aij均非負(fù)，則問(wèn)題一定無(wú)可行解否則，做換基迭代目前八頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)X1X2X3X4X5檢-2-1000ZX3-3-1100-3X4-4-3010-6X51200131、確定出基變量：設(shè)br=min{bi|bi<0}則取br所在行的基變量為出基變量即取X4為出基變量2、確定入基變量：原則：保持檢驗(yàn)行系數(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目前九頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)目前十頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)對(duì)偶單純形法步驟：1、找出一個(gè)初始對(duì)偶可行解。把原問(wèn)題寫成該基的典則形式時(shí)，目標(biāo)函數(shù)的系數(shù)均≤02、判斷：（1）若B-1b≥0，則得到最優(yōu)解結(jié)束（2）若B-1b≥0，則問(wèn)題無(wú)可行解。3、換基迭代：（1）確定出基變量：（2）確定入基變量即找出一個(gè)基B，否則轉(zhuǎn)下一步目前十一頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)不是典則形式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目前十二頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)注意：對(duì)偶單純形法僅限于初始基B對(duì)應(yīng)的典則形式中目標(biāo)函數(shù)的系數(shù)（檢驗(yàn)數(shù)）均≤0的情形?？捎脤?duì)偶單純形法B的典則形式目前十三頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)為什么叫對(duì)偶單純形法？目前十四頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)X解檢驗(yàn)行Z-CBB-1bXBB-1b設(shè)B為可行基XBXN解檢驗(yàn)行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b原始單純形法的基本思路：目前十五頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)X解檢驗(yàn)行Z-CBB-1bXBB-1b設(shè)B為可行基原始單純形法的迭代過(guò)程：目前十六頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)對(duì)偶單純形法的基本思路：目前十七頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)如何用？目前十八頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)求解線性規(guī)劃問(wèn)題的方法與步驟：1、把原問(wèn)題化為標(biāo)準(zhǔn)型2、找初始基，轉(zhuǎn)第3步，轉(zhuǎn)第4步3、把問(wèn)題寫成關(guān)于基B的典則形式，用單純形法，對(duì)偶單純形法，轉(zhuǎn)第4步4、增加人工變量，用大M法或兩階段法求解目前十九頁(yè)\總數(shù)二十二頁(yè)\編于二十二點(diǎn)對(duì)應(yīng)B1的基本解：可用對(duì)偶單純形法求解檢驗(yàn)數(shù)全部≤0不可行對(duì)應(yīng)B2的基本解用單純形法求解