第二章 對(duì)偶理論及靈敏度分析

第二章對(duì)偶理論及靈敏度分析第1頁，共146頁，2023年，2月20日，星期三返回繼續(xù)2.1.1線性規(guī)劃的對(duì)偶問題一、對(duì)偶問題的提出二、原問題與對(duì)偶問題的數(shù)學(xué)模型三、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系第2頁，共146頁，2023年，2月20日，星期三實(shí)例：某家電廠家利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：設(shè)備A

設(shè)備B調(diào)試工序利潤(rùn)（元）0612521115時(shí)24時(shí)5時(shí)產(chǎn)品Ⅰ產(chǎn)品ⅡD一、對(duì)偶問題的提出第3頁，共146頁，2023年，2月20日，星期三如何安排生產(chǎn)，使獲利最多？廠家設(shè)Ⅰ產(chǎn)量–––––Ⅱ產(chǎn)量–––––第4頁，共146頁，2023年，2月20日，星期三設(shè)：設(shè)備A——元／時(shí)設(shè)備B––––元／時(shí)調(diào)試工序––––元／時(shí)收購付出的代價(jià)最小，且對(duì)方能接受。出讓代價(jià)應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤(rùn)。第5頁，共146頁，2023年，2月20日，星期三設(shè)備A

設(shè)備B調(diào)試工序利潤(rùn)（元）0612521115時(shí)24時(shí)5時(shí)ⅠⅡD廠家能接受的條件：收購方的意愿：?jiǎn)挝划a(chǎn)品Ⅰ出租收入不低于2元單位產(chǎn)品Ⅱ出租收入不低于1元出讓代價(jià)應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤(rùn)。第6頁，共146頁，2023年，2月20日，星期三廠家對(duì)偶問題原問題收購廠家一對(duì)對(duì)偶問題第7頁，共146頁，2023年，2月20日，星期三3個(gè)約束2個(gè)變量2個(gè)約束3個(gè)變量原問題對(duì)偶問題一般規(guī)律第8頁，共146頁，2023年，2月20日，星期三特點(diǎn)：1．2．限定向量b價(jià)值向量C（資源向量）3．一個(gè)約束一個(gè)變量。4．的LP約束“”的

LP是“”的約束。5．變量都是非負(fù)限制。其它形式的對(duì)偶?第9頁，共146頁，2023年，2月20日，星期三二、原問題與對(duì)偶問題的數(shù)學(xué)模型1．對(duì)稱形式的對(duì)偶當(dāng)原問題對(duì)偶問題只含有不等式約束時(shí)，稱為對(duì)稱形式的對(duì)偶。原問題對(duì)偶問題情形一：第10頁，共146頁，2023年，2月20日，星期三原問題對(duì)偶問題化為標(biāo)準(zhǔn)對(duì)稱型情形二：證明對(duì)偶第11頁，共146頁，2023年，2月20日，星期三第12頁，共146頁，2023年，2月20日，星期三第13頁，共146頁，2023年，2月20日，星期三第14頁，共146頁，2023年，2月20日，星期三2、非對(duì)稱形式的對(duì)偶若原問題的約束條件是等式，則原問題對(duì)偶問題第15頁，共146頁，2023年，2月20日，星期三推導(dǎo):原問題第16頁，共146頁，2023年，2月20日，星期三

根據(jù)對(duì)稱形式的對(duì)偶模型,可直接寫出上述問題的對(duì)偶問題:第17頁，共146頁，2023年，2月20日，星期三令，得對(duì)偶問題為：證畢。第18頁，共146頁，2023年，2月20日，星期三三、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系

原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）第19頁，共146頁，2023年，2月20日，星期三例:第20頁，共146頁，2023年，2月20日，星期三對(duì)偶問題為第21頁，共146頁，2023年，2月20日，星期三解：對(duì)偶規(guī)劃：例2寫出下列線性規(guī)劃的對(duì)偶問題第22頁，共146頁，2023年，2月20日，星期三例3寫出下列線性規(guī)劃的對(duì)偶問題解：上述問題的對(duì)偶規(guī)劃：第23頁，共146頁，2023年，2月20日，星期三返回結(jié)束線性規(guī)劃的對(duì)偶問題第24頁，共146頁，2023年，2月20日，星期三返回繼續(xù)2.1.2對(duì)偶問題的基本性質(zhì)引例對(duì)稱性弱對(duì)偶性最優(yōu)性對(duì)偶性（強(qiáng)對(duì)偶性）互補(bǔ)松弛性第25頁，共146頁，2023年，2月20日，星期三對(duì)偶問題原問題收購廠家引例第26頁，共146頁，2023年，2月20日，星期三（）原問題的變量原問題松弛變量對(duì)偶問題剩余變量對(duì)偶問題的變量化為極小問題原問題化為極小問題，最終單純形表：第27頁，共146頁，2023年，2月20日，星期三原問題的變量原問題松弛變量對(duì)偶問題剩余變量對(duì)偶問題的變量對(duì)偶問題用兩階段法求解的最終的單純形表第28頁，共146頁，2023年，2月20日，星期三（）原問題的變量原問題松弛變量對(duì)偶問題剩余變量對(duì)偶問題的變量化為極小問題原問題最優(yōu)解對(duì)偶問題最優(yōu)解原問題化為極小問題，最終單純形表：32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxx---第29頁，共146頁，2023年，2月20日，星期三兩個(gè)問題作一比較:1.兩者的最優(yōu)值相同2.變量的解在兩個(gè)單純形表中互相包含原問題最優(yōu)解（決策變量）對(duì)偶問題最優(yōu)解（決策變量）

對(duì)偶問題的松弛變量原問題的松弛變量第30頁，共146頁，2023年，2月20日，星期三從引例中可見：原問題與對(duì)偶問題在某種意義上來說，實(shí)質(zhì)上是一樣的，因?yàn)榈诙€(gè)問題僅僅在第一個(gè)問題的另一種表達(dá)而已。理論證明：原問題與對(duì)偶問題解的關(guān)系第31頁，共146頁，2023年，2月20日，星期三

單純形法的矩陣描述不妨設(shè)基為基變量非基變量設(shè)線性規(guī)劃問題則第32頁，共146頁，2023年，2月20日，星期三

單純形法的矩陣描述其中令得當(dāng)前的基解為：當(dāng)前基解約束方程組第33頁，共146頁，2023年，2月20日，星期三當(dāng)前目標(biāo)值目標(biāo)函數(shù)令得當(dāng)前的目標(biāo)函數(shù)值為：

單純形法的矩陣描述第34頁，共146頁，2023年，2月20日，星期三當(dāng)前檢驗(yàn)數(shù)

單純形法的矩陣描述檢驗(yàn)數(shù)其中當(dāng)前對(duì)應(yīng)的系數(shù)列第35頁，共146頁，2023年，2月20日，星期三矩陣單純形法計(jì)算的描述線性規(guī)劃問題化為標(biāo)準(zhǔn)型，引入松弛變量第36頁，共146頁，2023年，2月20日，星期三初始單純形表非基變量基變量初始基變量矩陣單純形法計(jì)算的描述第37頁，共146頁，2023年，2月20日，星期三基變量非基變量當(dāng)基變量為時(shí)，新的單純形表矩陣單純形法計(jì)算的描述當(dāng)前檢驗(yàn)數(shù)當(dāng)前基解第38頁，共146頁，2023年，2月20日，星期三第39頁，共146頁，2023年，2月20日，星期三對(duì)偶問題的基本性質(zhì)一、對(duì)稱定理：定理：對(duì)偶問題的對(duì)偶是原問題。設(shè)原問題（1）對(duì)偶問題（2）第40頁，共146頁，2023年，2月20日，星期三二、弱對(duì)偶性定理：

——若和分別是原問題（1）及對(duì)偶問題（2）的可行解，則有證明：對(duì)偶問題的基本性質(zhì)第41頁，共146頁，2023年，2月20日，星期三從弱對(duì)偶性可得到以下重要結(jié)論：（1）極大化問題（原問題）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是對(duì)偶問題最優(yōu)目標(biāo)函數(shù)值的下界。（2）極小化問題（對(duì)偶問題）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是原問題最優(yōu)目標(biāo)函數(shù)值的上界。（3）若原問題可行，但其目標(biāo)函數(shù)值無界，則對(duì)偶問題無可行解。第42頁，共146頁，2023年，2月20日，星期三（4）若對(duì)偶問題可行，但其目標(biāo)函數(shù)值無界，則原問題無可行解。（5）若原問題有可行解而其對(duì)偶問題無可行解，則原問題目標(biāo)函數(shù)值無界。（6）對(duì)偶問題有可行解而其原問題無可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。原問題對(duì)偶問題第43頁，共146頁，2023年，2月20日，星期三三、最優(yōu)性定理：

——若和分別是（1）和（2）的可行解，且有則分別是（1）和（2）的最優(yōu)解。

則為（1）的最優(yōu)解，反過來可知：也是（2）的最優(yōu)解。證明：因?yàn)椋?）的任一可行解均滿足對(duì)偶問題的基本性質(zhì)第44頁，共146頁，2023年，2月20日，星期三證明：原問題與對(duì)偶問題的解一般有三種情況：一個(gè)有有限最優(yōu)解另一個(gè)有有限最優(yōu)解。一個(gè)有無界解另一個(gè)無可行解。兩個(gè)均無可行解。四、對(duì)偶定理（強(qiáng)對(duì)偶性）：

——若原問題及其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。對(duì)偶問題的基本性質(zhì)第45頁，共146頁，2023年，2月20日，星期三五、互補(bǔ)松弛性：

——若分別是原問題（1）與對(duì)偶問題（2）的可行解，分別為（1）、（2）的松弛變量，則：即：為最優(yōu)解原問題第i條約束

A的第i行第46頁，共146頁，2023年，2月20日，星期三

說明：在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件去嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。另一方面：對(duì)偶問題的第j條約束第47頁，共146頁，2023年，2月20日，星期三互補(bǔ)松弛定理應(yīng)用：（1）從已知的最優(yōu)對(duì)偶解，求原問題最優(yōu)解，反之亦然。（2）證實(shí)原問題可行解是否為最優(yōu)解。（3）從不同假設(shè)來進(jìn)行試算，從而研究原始、對(duì)偶問題最優(yōu)解的一般性質(zhì)。（4）非線性的方面的應(yīng)用。以上性質(zhì)同樣適用于非對(duì)稱形式。第48頁，共146頁，2023年，2月20日，星期三【例】已知線性規(guī)劃的最優(yōu)解是求對(duì)偶問題的最優(yōu)解。2.2對(duì)偶性質(zhì)Dualproperty第49頁，共146頁，2023年，2月20日，星期三【解】對(duì)偶問題是因?yàn)閄1≠0，X2≠0，所以對(duì)偶問題的第一、二個(gè)約束的松弛變量等于零，即解此線性方程組得y1=1,y2=1,從而對(duì)偶問題的最優(yōu)解為Y=（1，1），最優(yōu)值w=26。2.2對(duì)偶性質(zhì)Dualproperty第50頁，共146頁，2023年，2月20日，星期三【例2-5】已知線性規(guī)劃的對(duì)偶問題的最優(yōu)解為Y=（0，－2），求原問題的最優(yōu)解?！窘狻繉?duì)偶問題是2.2對(duì)偶性質(zhì)Dualproperty第51頁，共146頁，2023年，2月20日，星期三解方程組得：x1=－5,x3=－1,所以原問題的最優(yōu)解為X=（－5，0，－1），最優(yōu)值Z=－12。因?yàn)閥2≠0，所以原問題第二個(gè)松弛變量=0，則y1=0、y2=2知，松弛變量故x2=0，則原問題的約束條件為線性方程組：2.2對(duì)偶性質(zhì)Dualproperty第52頁，共146頁，2023年，2月20日，星期三【例2-6】證明下列線性規(guī)劃無最優(yōu)解：【證】容易看出X=（4，0，0）是一可行解，故問題可行。對(duì)偶問題將三個(gè)約束的兩端分別相加得而第二個(gè)約束有y2≥1，矛盾，故對(duì)偶問題無可行解，因而原問題具有無界解，即無最優(yōu)解。

2.2對(duì)偶性質(zhì)Dualproperty第53頁，共146頁，2023年，2月20日，星期三【例2-7】線性規(guī)劃（1）用單純形法求最優(yōu)解；（2）寫出每步迭代對(duì)應(yīng)對(duì)偶問題的基本解；（3）從最優(yōu)表中寫出對(duì)偶問題的最優(yōu)解；（4）用公式Y(jié)=CBB-1求對(duì)偶問題的最優(yōu)解。【解】（1）加入松弛變量x4、x5后，單純形迭代如表2-2所示。2.2對(duì)偶性質(zhì)Dualproperty第54頁，共146頁，2023年，2月20日，星期三XBx1x2x3x4x5b表（1）x4x5[2]1－102410012→4λj6↑－2100表（2）x1x510－1/2[1/2]131/2－1/20113→λj01↑－5－30表（3）x1x21001460－11246λj00－11－2－2表2-22.2對(duì)偶性質(zhì)Dualproperty第55頁，共146頁，2023年，2月20日，星期三最優(yōu)解X=（4，6，0），最優(yōu)值Z=6×4－2×6=12；（2）設(shè)對(duì)偶變量為y1、y2,松弛變量為y3、y4、y5,Y=（y1、y2、y3、y4、y5），由性質(zhì)6得到對(duì)偶問題的基本解（y1、y2、y3、y4、y5）

=（－λ4，－λ5，－λ1，－λ2，－λ3），即表2－2（1）中λ=（6，－2，1，0，0），則Y（1）=（0，0，-6，2，－1）表2－2（2）中λ=（0，1，－5，－3，0），則Y（2）=（3，0，0，－1，5）表2－2（3）中λ=（0，0，－11，－2，－2），則Y（3）=（2，2，0，0，11）2.2對(duì)偶性質(zhì)Dualproperty第56頁，共146頁，2023年，2月20日，星期三（3）因?yàn)楸?－2（3）為最優(yōu)解，故

Y（3）=（2，2，0，0，11）為對(duì)偶問題最優(yōu)解；（4）表2－2（3）中的最優(yōu)基

B-1為表2－2（3）中x4，x5兩列的系數(shù)，即CB=（6，－2），因而2.2對(duì)偶性質(zhì)Dualproperty第57頁，共146頁，2023年，2月20日，星期三已知線性規(guī)劃問題:其對(duì)偶問題的最優(yōu)解。試用互補(bǔ)松弛定理找出原問題的最優(yōu)解。解：原問題的對(duì)偶問題為：由對(duì)偶問題最優(yōu)解可知，由互補(bǔ)松弛定理，解方程組所以原問題最優(yōu)解第58頁，共146頁，2023年，2月20日，星期三本節(jié)您學(xué)了六個(gè)對(duì)偶性質(zhì)；這些性質(zhì)是研究原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系；表2－6也許對(duì)您了解這些性質(zhì)有幫助。表2－6一個(gè)問題max另一個(gè)問題min有最優(yōu)解有最優(yōu)解性質(zhì)4無無最優(yōu)解無最優(yōu)解性質(zhì)4最優(yōu)無界解（有可行解）無可行解性質(zhì)2解無可行解無界解（有可行解）應(yīng)用已知最優(yōu)解通過解方程求最優(yōu)解性質(zhì)5已知檢驗(yàn)數(shù)檢驗(yàn)數(shù)乘以－1求得基本解性質(zhì)62.2對(duì)偶性質(zhì)Dualproperty第59頁，共146頁，2023年，2月20日，星期三返回結(jié)束對(duì)偶問題的基本性質(zhì)第60頁，共146頁，2023年，2月20日，星期三

假設(shè)計(jì)劃期內(nèi)甲乙兩種產(chǎn)品各生產(chǎn)噸，設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤(rùn)（元/噸）3230用圖解法或單純形法可求得最優(yōu)解

(元)

即在計(jì)劃期內(nèi)甲產(chǎn)品生產(chǎn)噸，乙產(chǎn)品生產(chǎn)8噸，可以使總利潤(rùn)達(dá)到最大，為元。例１：對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋—影子價(jià)格

第61頁，共146頁，2023年，2月20日，星期三第62頁，共146頁，2023年，2月20日，星期三

由強(qiáng)對(duì)偶定理可知，如果原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解，而且它們的目標(biāo)函數(shù)值相等，即有：其中是線性規(guī)劃原問題約束條件的右端數(shù)據(jù)向量，它代表各種資源的擁有量。為對(duì)偶問題最優(yōu)解，它代表在資源最優(yōu)利用條件下對(duì)各種單位資源的估價(jià)，這種估計(jì)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中所作出的貢獻(xiàn)（如創(chuàng)造利潤(rùn)，產(chǎn)值等）而作出估價(jià)，為區(qū)別起見，稱之為影子價(jià)格(shadowprice)。第63頁，共146頁，2023年，2月20日，星期三

影子價(jià)格的大小客觀地反映了各種不同資源在系統(tǒng)內(nèi)的稀缺程度。如果第i種資源供大于求，即在達(dá)到最優(yōu)解時(shí)，該種資源沒有用完，或松弛變量，由互補(bǔ)松弛定理，在對(duì)偶最優(yōu)解中，第i種資源的影子價(jià)格。反之如果第i種資源的影子價(jià)格，那么由互補(bǔ)松弛定理，原問題的第i個(gè)約束為嚴(yán)格等式，即，這表明第i種資源已經(jīng)用完，成為稀缺資源。

資源的影子價(jià)格同時(shí)也是一種機(jī)會(huì)成本，在市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn)這種資源用于擴(kuò)大生產(chǎn)；相反當(dāng)某種資源的市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，企業(yè)應(yīng)賣出這種資源。隨著資源的買進(jìn)賣出，企業(yè)資源的影子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。

第64頁，共146頁，2023年，2月20日，星期三設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤(rùn)（元/噸）3230例１：對(duì)偶最優(yōu)解其中為設(shè)備A的影子價(jià)格，在資源最優(yōu)利用的條件下，設(shè)備A每增加一個(gè)單位臺(tái)時(shí)，可以使總利潤(rùn)增加元。若設(shè)備Ａ可供臺(tái)時(shí)數(shù)＝３７，則第65頁，共146頁，2023年，2月20日，星期三返回結(jié)束影子價(jià)格第66頁，共146頁，2023年，2月20日，星期三2.1.4對(duì)偶單純形法

對(duì)偶單純形法的基本思路對(duì)偶單純形法的計(jì)算步驟返回繼續(xù)第67頁，共146頁，2023年，2月20日，星期三對(duì)偶單純形法的基本思路單純形法的基本思路：原問題基可行解最優(yōu)解判斷對(duì)偶問題的可行解對(duì)偶問題最優(yōu)解判斷對(duì)偶單純形法基本思路第68頁，共146頁，2023年，2月20日，星期三對(duì)偶單純形法的計(jì)算步驟線性規(guī)劃問題不妨設(shè)為對(duì)偶問題的初始可行基，則。若，即表中原問題和對(duì)偶問題均為最優(yōu)解，否則換基。第69頁，共146頁，2023年，2月20日，星期三換基方法：確定換出基變量

對(duì)應(yīng)變量為換出基的變量確定換入基變量為主元素，為換入基變量第70頁，共146頁，2023年，2月20日，星期三初始可行基例、用對(duì)偶單純形法求解線性規(guī)劃問題：對(duì)偶問題的初始可行基第71頁，共146頁，2023年，2月20日，星期三例、用對(duì)偶單純形法求解線性規(guī)劃問題：使對(duì)偶問題基變量可行,換出

換出換出第72頁，共146頁，2023年，2月20日，星期三例、用對(duì)偶單純形法求解線性規(guī)劃問題：第73頁，共146頁，2023年，2月20日，星期三最優(yōu)解例、用對(duì)偶單純形法求解線性規(guī)劃問題：第74頁，共146頁，2023年，2月20日，星期三2.5對(duì)偶單純形法由于單純表中同時(shí)反映原問題與對(duì)偶問題的最優(yōu)解，故可以從求對(duì)偶問題最優(yōu)解角度求解LP模型。例：

minz=2x1+3x2maxz'=-2x1-3x2+0x3+0x4 s.tx1+x23標(biāo)準(zhǔn)化s.tx1+x2-x3=3 x1+2x24 x1+2x2-x4=4 x10,x20 xj0,(j=1,2,3,4)

maxz'=-2x1-3x2+0x3+0x4

s.t-x1-x2+x3=-3 -x1-2x2+x4=-4 xj0,(j=1,2,3,4)2006/3--第2章對(duì)偶問題--第75頁，共146頁，2023年，2月20日，星期三Cj→x1x2x3x4XBbCB-1 -1 1 0-1 -2 01-2 -3 0 0-3-4x3x400cj-zj-2-300-1/2 0 1 -1/21/2 1 0-1/2x3x2-12cj-zj-1/2 00-3/2

0-31 0 -2 10 1 1-1x1x221cj-zj0 0 -1 -1-2-3列單純表計(jì)算：2006/3--第2章對(duì)偶問題--第76頁，共146頁，2023年，2月20日，星期三對(duì)偶單純形法步驟：1.列初始單純形表，使得所有檢驗(yàn)數(shù)j0

；2.出基變量：取min{bi<0

}=bl

→x(l) 3.入基變量：min{——|alk<0}=→xk 4.主元素：[alk]5.迭代：同單純形法，新單純表中pk化為單位向量cj-zjalj說明：10使用對(duì)偶單純形法時(shí)，初始表中檢驗(yàn)數(shù)必須全部為j0，即使得其對(duì)偶問題為可行解，20為便于說明，這里采取從原問題角度敘述迭代步驟。2006/3--第2章對(duì)偶問題--第77頁，共146頁，2023年，2月20日，星期三【例2-8】用對(duì)偶單純形法求解【解】先將約束不等式化為等式，再兩邊同乘以（－1），得到x4、x5為基變量，用對(duì)偶單純形法，迭代過程如表2-7所示。2.3對(duì)偶單純形法DualSimplexMethod第78頁，共146頁，2023年，2月20日，星期三XBx1x2x3x4x5b表(1)x4x5-1-1[-1]1-141001－5→－3λj41↑300表（2）x2x51[-2]1013-11015－8→λj3↑0210表（3）x2x101105/2-3/2-1/2-1/21/2－1/214λj0013/25/23/2表2-72.3對(duì)偶單純形法DualSimplexMethod最優(yōu)解：X＝(4，1，0)T；Z=17第79頁，共146頁，2023年，2月20日，星期三應(yīng)當(dāng)注意：（1）用對(duì)偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對(duì)偶問題的最優(yōu)解；（2）初始表中一定要滿足對(duì)偶問題可行，也就是說檢驗(yàn)數(shù)滿足最優(yōu)判別準(zhǔn)則；（3）最小比值中的絕對(duì)值是使得比值非負(fù)，在極小化問題時(shí)λj≥0，分母aij<0這時(shí)必須取絕對(duì)值。在極大化問題中，λ≤j0分母aij<0，總滿足非負(fù)，這時(shí)絕對(duì)值符號(hào)不起作用，可以去掉。如在本例中將目標(biāo)函數(shù)寫成這里λj≤0在求θk時(shí)就可以不帶絕對(duì)值符號(hào)。2.3對(duì)偶單純形法DualSimplexMethod第80頁，共146頁，2023年，2月20日，星期三（6）對(duì)偶單純形法在確定出基變量時(shí)，若不遵循規(guī)則，任選一個(gè)小于零的bi對(duì)應(yīng)的基變量出基，不影響計(jì)算結(jié)果，只是迭代次數(shù)可能不一樣．

（4）對(duì)偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進(jìn)基變量后確定出基變量，對(duì)偶單純形法是先確定出基變量后確定進(jìn)基變量；（5）普通單純形法的最小比值是其目的是保證下一個(gè)原問題的基本解可行，對(duì)偶單純形法的最小比值是其目的是保證下一個(gè)對(duì)偶問題的基本解可行；2.3對(duì)偶單純形法DualSimplexMethod第81頁，共146頁，2023年，2月20日，星期三【例2-9】用對(duì)偶單純形法求解【解】取x3、x4為初始基變量，用對(duì)偶單純形法迭代如表2-8所示。表2－8XBx1x2x3x4

b表（1）x3x42－1[－1]21001－2→－2λj－7－3↑00

表（2）x2x4－2310－12012－6λj－130－30

第二張表中x4=－6<0且第二行的系數(shù)全部大于等于零，說明原問題無可行解。2.3對(duì)偶單純形法DualSimplexMethod第82頁，共146頁，2023年，2月20日，星期三例2-9可用性質(zhì)2.6及性質(zhì)2.2來說明，表（2）的第2行對(duì)應(yīng)于對(duì)偶問題的第2列（相差一個(gè)負(fù)號(hào)），檢驗(yàn)數(shù)行對(duì)應(yīng)于對(duì)偶問題的常數(shù)項(xiàng)（相差一個(gè)負(fù)號(hào)），比值對(duì)應(yīng)于對(duì)偶問題的比值失效，也說明即對(duì)偶問題具有無界解，由性質(zhì)2.2知原問題無可行解．2.3對(duì)偶單純形法DualSimplexMethod第83頁，共146頁，2023年，2月20日，星期三本節(jié)利用對(duì)偶性質(zhì)6：原問題的檢驗(yàn)數(shù)與對(duì)偶問題的基本解的對(duì)應(yīng)關(guān)系，介紹了一種特殊線性規(guī)劃的求解方法—對(duì)偶單純形法。1.對(duì)偶單純形法的應(yīng)用條件；2.出基與進(jìn)基的順序；3.如何求最小比值；4.最優(yōu)解、無可行解的判斷。2.3對(duì)偶單純形法DualSimplexMethod下一節(jié)：靈敏度分析與參數(shù)分析第84頁，共146頁，2023年，2月20日，星期三對(duì)偶單純形法的優(yōu)點(diǎn)：不需要人工變量；當(dāng)變量多于約束時(shí)，用對(duì)偶單純形法可減少迭代次數(shù)；在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡(jiǎn)化。對(duì)偶單純形法缺點(diǎn)：在初始單純形表中對(duì)偶問題是基可行解，這點(diǎn)對(duì)多數(shù)線性規(guī)劃問題很難做到。因此，對(duì)偶單純形法一般不單獨(dú)使用。第85頁，共146頁，2023年，2月20日，星期三練習(xí)用對(duì)偶單純形法求解線性規(guī)劃問題：第86頁，共146頁，2023年，2月20日，星期三返回結(jié)束

對(duì)偶單純形法第87頁，共146頁，2023年，2月20日，星期三2.2.1靈敏度問題及其圖解法靈敏度問題靈敏度分析——圖解法第88頁，共146頁，2023年，2月20日，星期三

靈敏度問題背景：線性規(guī)劃問題中，都是常數(shù)，但這些系數(shù)是估計(jì)值和預(yù)測(cè)值。市場(chǎng)的變化值變化；工藝的變化值變化；資源的變化值變化。第89頁，共146頁，2023年，2月20日，星期三問題：當(dāng)這些系數(shù)中的一個(gè)或多個(gè)發(fā)生變化時(shí)，原最優(yōu)解會(huì)怎樣變化？當(dāng)這些系數(shù)在什么范圍內(nèi)變化時(shí)，原最優(yōu)解仍保持不變？若最優(yōu)解發(fā)生變化，如何用最簡(jiǎn)單的方法找到現(xiàn)行的最優(yōu)解？第90頁，共146頁，2023年，2月20日，星期三研究?jī)?nèi)容：

研究線性規(guī)劃中，的變化對(duì)最優(yōu)解的影響。研究方法：圖解法對(duì)偶理論分析僅適用于含2個(gè)變量的線性規(guī)劃問題在單純形表中進(jìn)行分析第91頁，共146頁，2023年，2月20日，星期三

MaxZ=34x1+40x24x1+6x2

482x1+2x2

182x1+x2

16x1、x2

0線性規(guī)劃模型靈敏度分析——圖解法

第92頁，共146頁，2023年，2月20日，星期三x218—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)最優(yōu)解(3,6)4x1+6x2=482x1+2x2=18靈敏度分析——圖解法

第93頁，共146頁，2023年，2月20日，星期三靈敏度分析—圖解法

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2

482x1+2x2

182x1+x2

16ABCDE目標(biāo)函數(shù)的系數(shù) 34x1 + 40x2 =Z 40x2 = -34x1 + Z x2 =- + 34x1

Z 40 40第94頁，共146頁，2023年，2月20日，星期三靈敏度分析—圖解法

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2

482x1+2x2

182x1+x2

16ABCDE目標(biāo)函數(shù)的系數(shù) 34x1 + 40x2 =Z 40x2 = -34x1 + Z x2 =- +

c1x1

Z

c2

c2若c1增加（c2不變）新的最優(yōu)解第95頁，共146頁，2023年，2月20日，星期三靈敏度分析—圖解法

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2

482x1+2x2

182x1+x2

16ABCDE目標(biāo)函數(shù)的系數(shù) 34x1 + 40x2 =Z 40x2 = -34x1 + Z x2 =- +

c1x1

Z

c2

c2若c1減少新的最優(yōu)解第96頁，共146頁，2023年，2月20日，星期三18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2

482x1+2x2

182x1+x2

16ABCDE(斜率=-1)(斜率=-2/3)

靈敏度分析—圖解法

最優(yōu)解不變的范圍（設(shè)c1固定c2可變）第97頁，共146頁，2023年，2月20日，星期三2.2.1靈敏度問題及其圖解法結(jié)束第98頁，共146頁，2023年，2月20日，星期三2.2.2靈敏度分析一、分析的變化二、分析的變化三、增加一個(gè)變量的分析四、增加一個(gè)約束條件的分析五、分析的變化第99頁，共146頁，2023年，2月20日，星期三研究?jī)?nèi)容：

研究線性規(guī)劃中，的變化對(duì)最優(yōu)解的影響。常用公式：第100頁，共146頁，2023年，2月20日，星期三實(shí)例：某家電廠家利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：設(shè)備A

設(shè)備B調(diào)試工序利潤(rùn)（元）0612521115時(shí)24時(shí)5時(shí)ⅠⅡD第101頁，共146頁，2023年，2月20日，星期三如何安排生產(chǎn)，使獲利最多？廠家設(shè)Ⅰ產(chǎn)量–––––Ⅱ產(chǎn)量–––––第102頁，共146頁，2023年，2月20日，星期三原問題最優(yōu)解對(duì)偶問題最優(yōu)解（相差負(fù)號(hào)）原問題的最終單純形表：第103頁，共146頁，2023年，2月20日，星期三一、分析的變化

的變化僅影響的變化。設(shè)備A

設(shè)備B調(diào)試工序利潤(rùn)（元）0612521115時(shí)24時(shí)5時(shí)ⅠⅡD1.52問題1：當(dāng)該公司最優(yōu)生產(chǎn)計(jì)劃有何變化？第104頁，共146頁，2023年，2月20日，星期三最終單純形表0×5/41.5×1/4+2×（-1/4）-1/80-（-1/8）=第105頁，共146頁，2023年，2月20日，星期三最終單純形表第106頁，共146頁，2023年，2月20日，星期三換基后單純形表為最優(yōu)解第107頁，共146頁，2023年，2月20日，星期三問題2：設(shè)產(chǎn)品II利潤(rùn)為，求原最優(yōu)解不變時(shí)的范圍。

的變化僅影響的變化；在最后一張單純形表中求出變化的；原最優(yōu)解不變，即；由上述不等式可求出的范圍。方法：第108頁，共146頁，2023年，2月20日，星期三即產(chǎn)品II利潤(rùn)為時(shí)的最終單純形表第109頁，共146頁，2023年，2月20日，星期三二、分析的變化

的變化僅影響，即原最優(yōu)解的可行性可能會(huì)變化：可行性不變，則原最優(yōu)解不變。可行性改變，則原最優(yōu)解改變，用對(duì)偶單純形法，找出最優(yōu)解。第110頁，共146頁，2023年，2月20日，星期三問題3：設(shè)備B的能力增加到32小時(shí)，

原最優(yōu)計(jì)劃有何變化？第111頁，共146頁，2023年，2月20日，星期三代入單純形表中可行性改變，用對(duì)偶單純形法換基求解。主元第112頁，共146頁，2023年，2月20日，星期三新的最優(yōu)解換基迭代得：第113頁，共146頁，2023年，2月20日，星期三問題4：設(shè)調(diào)試工序可用時(shí)間為小時(shí)，求，原最優(yōu)解保持不變。原最優(yōu)解保持不變，則第114頁，共146頁，2023年，2月20日，星期三三、增加一個(gè)變量的分析增加一個(gè)變量相當(dāng)于增加一種產(chǎn)品。分析步驟：1、計(jì)算2、計(jì)算3、若，原最優(yōu)解不變；若，則按單純形表繼續(xù)迭代計(jì)算找出最優(yōu)解。第115頁，共146頁，2023年，2月20日，星期三問題5：設(shè)生產(chǎn)第三種產(chǎn)品，產(chǎn)量為件，

對(duì)應(yīng)的求最優(yōu)生產(chǎn)計(jì)劃。解：第116頁，共146頁，2023年，2月20日，星期三代入最終原單純形表中主元第117頁，共146頁，2023年，2月20日，星期三換基后有：第118頁，共146頁，2023年，2月20日，星期三四、增加一個(gè)約束條件的分析

增加一個(gè)約束條件相當(dāng)于增添一道工序。分析方法：將最優(yōu)解代入新的約束中（1）若滿足要求，則原最優(yōu)解不變；（2）若不滿足要求，則原最優(yōu)解改變，將新增的約束條件添入最終的單純形表中繼續(xù)分析。第119頁，共146頁，2023年，2月20日，星期三五、分析的變化若對(duì)應(yīng)的變量為基變量，B將改變。需引入人工變量求出可行解，再用單純形法求解。若對(duì)應(yīng)的變量為非基變量，參見三的分析。第120頁，共146頁，2023年，2月20日，星期三靈敏度分析的步驟歸納如下：（1）將參數(shù)的改變計(jì)算反映到最終單純形表上；（2）檢查原問題是否仍為可行解；（3）檢查對(duì)偶問題是否仍為可行解；（4）按下表所列情況得出結(jié)論和決定繼續(xù)計(jì)算的步驟。第121頁，共146頁，2023年，2月20日，星期三原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代非可行解可行解用對(duì)偶單純形法繼續(xù)迭代非可行解非可行解編制新的單純形表重新計(jì)算總之第122頁，共146頁，2023年，2月20日，星期三練習(xí)：

某廠計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品單位利潤(rùn)及生產(chǎn)產(chǎn)品所需材料、勞動(dòng)力如下表：?jiǎn)挝划a(chǎn)品甲乙丙可使用資源量勞動(dòng)力1/31/31/31材料1/34/37/33利潤(rùn)（元）231

第123頁，共146頁，2023年，2月20日，星期三（1）確定最優(yōu)的生產(chǎn)方案；（2）當(dāng)增大至多少時(shí)，丙產(chǎn)品安排生產(chǎn)；（3）增加3個(gè)勞動(dòng)力，最優(yōu)解是否改變？（4）勞動(dòng)力在哪個(gè)范圍內(nèi)變化，對(duì)利潤(rùn)值的改變有利；（5）增加新的產(chǎn)品丁，需1個(gè)勞動(dòng)力，1個(gè)單位原料，利潤(rùn)3元。確定最優(yōu)的生產(chǎn)方案。（6）