對偶問題三對偶單純形法

對偶問題三對偶單純形法第1頁，共16頁，2023年，2月20日，星期一單純形法與對偶單純形法比較第2頁，共16頁，2023年，2月20日，星期一單純形法的步驟第3頁，共16頁，2023年，2月20日，星期一對偶單純形法的步驟第4頁，共16頁，2023年，2月20日，星期一如何用？第5頁，共16頁，2023年，2月20日，星期一基B的典則形式X1X2X3X4X5檢-2-1000ZX3-3-1100-3X4-4-3010-6X5120013不可行檢驗(yàn)行≤0分析：若X3或X4所在的行的aij均非負(fù)，則問題一定無可行解否則，做換基迭代第6頁，共16頁，2023年，2月20日，星期一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-1

000-3/5-2/5Z+12/5001-1-100101/54/56/5100-2/5-3/53/5第7頁，共16頁，2023年，2月20日，星期一第8頁，共16頁，2023年，2月20日，星期一不是典則形式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第9頁，共16頁，2023年，2月20日，星期一注意：對偶單純形法僅限于初始基B對應(yīng)的典則形式中目標(biāo)函數(shù)的系數(shù)（檢驗(yàn)數(shù)）均≤0的情形?？捎脤ε紗渭冃畏˙的典則形式第10頁，共16頁，2023年，2月20日，星期一如何用？第11頁，共16頁，2023年，2月20日，星期一求解線性規(guī)劃問題的方法與步驟：1、把原問題化為標(biāo)準(zhǔn)型2、找初始基，轉(zhuǎn)第3步，轉(zhuǎn)第4步3、把問題寫成關(guān)于基B的典則形式，用單純形法，對偶單純形法，轉(zhuǎn)第4步4、增加人工變量，用大M法或兩階段法求解第12頁，共16頁，2023年，2月20日，星期一對應(yīng)B1的基本解：可用對偶單純形法求解檢驗(yàn)數(shù)全部≤0不可行對應(yīng)B2的基本解用單純形法求解可行第13頁，共16頁，2023年，2月20日，星期一對應(yīng)B的基本解：存在檢驗(yàn)數(shù)>0不可行單純形法對偶單純形法？××第14頁，共16頁，2