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

（優(yōu)選）對(duì)偶單純形法經(jīng)典運(yùn)籌學(xué)現(xiàn)在是1頁(yè)\一共有22頁(yè)\編輯于星期一單純形法（原始單純形法）的兩個(gè)條件：1、問(wèn)題為標(biāo)準(zhǔn)型2、有初始基本可行解用單純形法求解現(xiàn)在是2頁(yè)\一共有22頁(yè)\編輯于星期一對(duì)偶單純形法的優(yōu)點(diǎn)：1、不需要人工變量；2、當(dāng)變量多于約束時(shí)，用對(duì)偶單純形法可減少迭代次數(shù)；3、在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡(jiǎn)化?，F(xiàn)在是3頁(yè)\一共有22頁(yè)\編輯于星期一B可逆原始單純形法的基本思路：現(xiàn)在是4頁(yè)\一共有22頁(yè)\編輯于星期一關(guān)于可行基B的典則形式檢驗(yàn)數(shù)現(xiàn)在是5頁(yè)\一共有22頁(yè)\編輯于星期一XBXN常數(shù)項(xiàng)檢驗(yàn)行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b初始單純形表：原始單純形法的迭代過(guò)程：現(xiàn)在是6頁(yè)\一共有22頁(yè)\編輯于星期一對(duì)偶單純形法的基本思路：XBXN常數(shù)項(xiàng)檢驗(yàn)行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b作對(duì)偶單純形表：現(xiàn)在是7頁(yè)\一共有22頁(yè)\編輯于星期一基B的典則形式X1X2X3X4X5檢-2-1000ZX3-3-1100-3X4-4-3010-6X5120013不可行檢驗(yàn)行≤0分析：若X3或X4所在的行的aij均非負(fù)，則問(wèn)題一定無(wú)可行解否則，做換基迭代現(xiàn)在是8頁(yè)\一共有22頁(yè)\編輯于星期一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現(xiàn)在是9頁(yè)\一共有22頁(yè)\編輯于星期一現(xiàn)在是10頁(yè)\一共有22頁(yè)\編輯于星期一對(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)下一步現(xiàn)在是11頁(yè)\一共有22頁(yè)\編輯于星期一不是典則形式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現(xiàn)在是12頁(yè)\一共有22頁(yè)\編輯于星期一注意：對(duì)偶單純形法僅限于初始基B對(duì)應(yīng)的典則形式中目標(biāo)函數(shù)的系數(shù)（檢驗(yàn)數(shù)）均≤0的情形?？捎脤?duì)偶單純形法B的典則形式現(xiàn)在是13頁(yè)\一共有22頁(yè)\編輯于星期一為什么叫對(duì)偶單純形法？現(xiàn)在是14頁(yè)\一共有22頁(yè)\編輯于星期一X解檢驗(yàn)行Z-CBB-1bXBB-1b設(shè)B為可行基XBXN解檢驗(yàn)行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b原始單純形法的基本思路：現(xiàn)在是15頁(yè)\一共有22頁(yè)\編輯于星期一X解檢驗(yàn)行Z-CBB-1bXBB-1b設(shè)B為可行基原始單純形法的迭代過(guò)程：現(xiàn)在是16頁(yè)\一共有22頁(yè)\編輯于星期一對(duì)偶單純形法的基本思路：現(xiàn)在是17頁(yè)\一共有22頁(yè)\編輯于星期一如何用？現(xiàn)在是18頁(yè)\一共有22頁(yè)\編輯于星期一求解線性規(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法或兩階段法求解現(xiàn)在是19頁(yè)\一共有22頁(yè)\編輯于星期一對(duì)應(yīng)B1的基本解：可用對(duì)偶單純形法求解檢驗(yàn)數(shù)全部≤0不可行對(duì)應(yīng)B2的基本解用單純形法求解