對(duì)偶單純性法第1頁，課件共25頁，創(chuàng)作于2023年2月可知：第2頁，課件共25頁，創(chuàng)作于2023年2月單純形方法：從初始基可行解出發(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頁，課件共25頁，創(chuàng)作于2023年2月二、對(duì)偶單純形法定義1對(duì)偶可行基：若B是線性規(guī)劃（LP）的一個(gè)基，并且滿足第4頁，課件共25頁，創(chuàng)作于2023年2月考慮如下形式的線性規(guī)劃xBxNxBI0第5頁，課件共25頁，創(chuàng)作于2023年2月作代換，由對(duì)偶可行基B變成B'。第6頁，課件共25頁，創(chuàng)作于2023年2月第7頁，課件共25頁，創(chuàng)作于2023年2月第8頁，課件共25頁，創(chuàng)作于2023年2月第9頁，課件共25頁，創(chuàng)作于2023年2月無界，所以原規(guī)劃無可行解。第10頁，課件共25頁，創(chuàng)作于2023年2月結(jié)論：1、利用單純形方法求解線性規(guī)劃時(shí)，若得到最優(yōu)解，同時(shí)可得對(duì)偶問題的最優(yōu)解。反之亦然。2、求解線性規(guī)劃時(shí)，寫出其對(duì)偶規(guī)劃，可以從一對(duì)對(duì)偶問題中選一個(gè)較簡(jiǎn)單進(jìn)行求解。第11頁，課件共25頁，創(chuàng)作于2023年2月例如，

給定線性規(guī)劃約束條件都是小于等于的不等式約束，通過添加松弛變量，系數(shù)矩陣中可得一單位子陣，利用單純形方法求解即可。給定線性規(guī)劃約束條件都是大于等于的不等式約束，目標(biāo)函數(shù)中系數(shù)為正。通過添加剩余變量，系數(shù)矩陣中可得一負(fù)單位子陣，方程組兩邊同乘以－1，利用對(duì)偶單純形方法求解。第12頁，課件共25頁，創(chuàng)作于2023年2月

給定線性規(guī)劃約束條件是混合的，通過添加剩余變量、松弛變量以及最少的人工變量，用大M法或兩階段法進(jìn)行求解。第13頁，課件共25頁，創(chuàng)作于2023年2月例：求解線性規(guī)劃第14頁，課件共25頁，創(chuàng)作于2023年2月解：顯然（P1，P2）是一對(duì)偶可行基，應(yīng)用對(duì)偶單純形方法，代入單純形表：0011100x1x21001[-1]-11-1-11-21檢驗(yàn)數(shù)00111第15頁，課件共25頁，創(chuàng)作于2023年2月迭代，得：0011110x3x2-1-10110-1-21223檢驗(yàn)數(shù)10020最優(yōu)解為（0，3，2，0，0）T，最優(yōu)值為2。第16頁，課件共25頁，創(chuàng)作于2023年2月該問題的對(duì)偶問題為第17頁，課件共25頁，創(chuàng)作于2023年2月上例中對(duì)偶變量的解為（－1，0）T。第18頁，課件共25頁，創(chuàng)作于2023年2月迭代步驟：得到初始對(duì)偶基可行解。置s:=0判別常數(shù)項(xiàng)是否大于等于0。若是，停止迭代，所得解為最優(yōu)解。若否，轉(zhuǎn)3。確定若第19頁，課件共25頁，創(chuàng)作于2023年2月確定迭代置s：=s+1,轉(zhuǎn)2。注：l，k的選取是為了避免循環(huán)的出現(xiàn)。第20頁，課件共25頁，創(chuàng)作于2023年2月21例2用對(duì)偶單純形法求解下列線性規(guī)劃

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0解將問題改寫成如下形式

minz=5x1+2x2+6x3－2x1

－4x2

－8x3+x4=－24－4x1

－x2

－4x3+x5=－8x1、x2，x3，x4，x5≥0顯然，p4、p5可以構(gòu)成現(xiàn)成的單位基，此時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，因此p4、p5構(gòu)成的就是初始正則基。第21頁，課件共25頁，創(chuàng)作于2023年2月22Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ-5/-2-2/-4-6/-8002x21/212-1/4060x5-7/20[-2]-1/41-24021/20-120θ-4/(-7/2)0-2/-2(-1/2)/(-1/4)02x2-310-1/2146x37/4011/8-1/211/2001/40-32第22頁，課件共25頁，創(chuàng)作于2023年2月23最后一個(gè)單純形表中，已得到一個(gè)可行的正則解，因而得到問題的最優(yōu)解為

X*=（0，4，1）T最優(yōu)值為z*=14對(duì)于形如minz=CX，AX≥b，X≥0，且C≥0的線性規(guī)劃問題。因?yàn)閷⑵涓膶憺閙ax(－z)=－CX，－AX+XS=－b，X≥0，則立即可以得到初始正則解；

對(duì)偶單純形法在以下情況下較為方便。第23頁，課件共25頁，創(chuàng)作于2023年2月思考題判斷下列結(jié)論是否正確.1）任何線性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃.2）原問題第i個(gè)約束是“≤”約束，則對(duì)偶變量yi≥0.3）互為對(duì)偶問題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無最優(yōu)解.4）對(duì)偶問題有可行解，則原問題也有可行解.5）原問題有多重解，對(duì)偶問題也有多重解.6）對(duì)偶問題有可行解，原問題無可行解，則對(duì)偶問題具有無界解.7）原問題無最優(yōu)解，則對(duì)偶問題無可行解.8）對(duì)偶問題不可行，原問題可能無界解.9）原問題與對(duì)偶問題都可行，則都有最優(yōu)解.10）原問題具有無界解，則對(duì)偶問題不可行.11）對(duì)偶問題具有無界解，則原問題無最優(yōu)解.12）若X*、Y*是原問題與對(duì)偶問題的最優(yōu)解，則X*=Y*.第24頁，課件共25頁，創(chuàng)作于20