對(duì)偶單純性法精品課件

1、對(duì)偶單純性法第1頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三可知：第2頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三單純形方法：從初始基可行解出發(fā)，保證解一直是可行的，進(jìn)行迭代。通過檢驗(yàn)數(shù)進(jìn)行判別，可得最優(yōu)解，或得出結(jié)論，不存在最優(yōu)解。由前面分析，現(xiàn)在考慮：能否從一檢驗(yàn)數(shù)大于等于0的基解（對(duì)偶規(guī)劃的可行解）出發(fā)，保證檢驗(yàn)數(shù)都大于等于0，迭代，直至得到一基可行解。該解自然是基最優(yōu)解。第3頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三二、對(duì)偶單純形法定義1 對(duì)偶可行基：若B是線性規(guī)劃（LP）的一個(gè)基，并且滿足第4頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期

2、三考慮如下形式的線性規(guī)劃xBxNxBI0第5頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三作代換，由對(duì)偶可行基B變成B。第6頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三第7頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三第8頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三第9頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三無(wú)界，所以原規(guī)劃無(wú)可行解。第10頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三結(jié)論：1、利用單純形方法求解線性規(guī)劃時(shí)，若得到最優(yōu)解，同時(shí)可得對(duì)偶問題的最優(yōu)解。反之亦然。2、求解線性規(guī)劃時(shí)，寫出其對(duì)偶規(guī)劃，可以從一對(duì)對(duì)偶問

3、題中選一個(gè)較簡(jiǎn)單進(jìn)行求解。第11頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三例如，給定線性規(guī)劃約束條件都是小于等于的不等式約束，通過添加松弛變量，系數(shù)矩陣中可得一單位子陣，利用單純形方法求解即可。給定線性規(guī)劃約束條件都是大于等于的不等式約束，目標(biāo)函數(shù)中系數(shù)為正。通過添加剩余變量，系數(shù)矩陣中可得一負(fù)單位子陣，方程組兩邊同乘以1，利用對(duì)偶單純形方法求解。第12頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三給定線性規(guī)劃約束條件是混合的，通過添加剩余變量、松弛變量以及最少的人工變量，用大M法或兩階段法進(jìn)行求解。第13頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三例：求解

4、線性規(guī)劃第14頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三解：顯然（P1，P2）是一對(duì)偶可行基，應(yīng)用對(duì)偶單純形方法，代入單純形表：0011100 x1x21001-1-11-1-11-21檢驗(yàn)數(shù)001 1 1第15頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三迭代，得：0011110 x3x2-1-10110-1-21223檢驗(yàn)數(shù)100 2 0最優(yōu)解為（0，3，2，0，0）T，最優(yōu)值為2。第16頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三該問題的對(duì)偶問題為第17頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三上例中對(duì)偶變量的解為（1，0）T。第18頁(yè)，

5、共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三迭代步驟：得到初始對(duì)偶基可行解。置s:=0判別常數(shù)項(xiàng)是否大于等于0。若是，停止迭代，所得解為最優(yōu)解。若否，轉(zhuǎn)3。確定若第19頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三確定迭代置s：=s+1,轉(zhuǎn)2。注：l，k的選取是為了避免循環(huán)的出現(xiàn)。第20頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三21例2 用對(duì)偶單純形法求解下列線性規(guī)劃 min z=5x1+2x2+6x32x1 +4x2 +8x3 244x1 + x2 + 4x38x1、x2，x30解 將問題改寫成如下形式 min z=5x1+2x2+6x32x1 4x2 8x3

6、 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x50顯然，p4、p5可以構(gòu)成現(xiàn)成的單位基，此時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，因此p4、p5構(gòu)成的就是初始正則基。第21頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三22Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5-4-1-401-8526000-5/-2-2/-4-6/-8002x21/212-1/4060 x5-7/20-2-1/41-24021/20-120-4/(-7/2)0-2/-2(-1/2)/(-1/4)02x2-310-1/2146x37/4011

7、/8-1/211/2001/40-32第22頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三23最后一個(gè)單純形表中，已得到一個(gè)可行的正則解，因而得到問題的最優(yōu)解為 X*=（0，4，1）T最優(yōu)值為z*=14對(duì)于形如min z=CX，AXb，X0，且C0的線性規(guī)劃問題。因?yàn)閷⑵涓膶憺閙ax (z) =CX，AX+XS=b，X0，則立即可以得到初始正則解； 對(duì)偶單純形法在以下情況下較為方便。第23頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三思考題判斷下列結(jié)論是否正確.1）任何線性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃.2）原問題第i個(gè)約束是“”約束，則對(duì)偶變量yi0.3）互為對(duì)偶問題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無(wú)最優(yōu)解.4）對(duì)偶問題有可行解，則原問題也有可行解.5）原問題有多重解，對(duì)偶問題也有多重解.6）對(duì)偶問題有可行解，原問題無(wú)可行解，則對(duì)偶問題具有無(wú)界解.7）原問題無(wú)最優(yōu)解，則對(duì)偶問題無(wú)可行解.8）對(duì)偶問題不可行，原問題可能無(wú)界解.9）原問題與對(duì)偶問題都可行，則都有最優(yōu)解.10）原問題具有無(wú)界解，則對(duì)偶問題不可行.11）對(duì)偶問題具有無(wú)界解，則原問題無(wú)最優(yōu)解.12）若X*、Y*是原問題與對(duì)偶問題的最優(yōu)解，則X*=Y*.第24頁(yè)，共25頁(yè)，2022年，5月20日，1點(diǎn)56分，星期三