第二章 對偶問題與靈敏度分析

第二章對偶問題與靈敏度分析第1頁，課件共114頁，創(chuàng)作于2023年2月2.1線性規(guī)劃的對偶問題一、問題的提出回顧例題1例1某工廠在計劃期內(nèi)要安排生產(chǎn)A、B兩種產(chǎn)品（假定產(chǎn)品暢銷）。已知生產(chǎn)單位產(chǎn)品的利潤與所需的勞動力、設(shè)備臺時及原材料的消耗，如表1.1所示問該廠應(yīng)如何安排生產(chǎn)使獲利最大？表1-1產(chǎn)品A產(chǎn)品B資源限量勞動力設(shè)備原材料9434510360200300利潤元/kg70120第2頁，課件共114頁，創(chuàng)作于2023年2月其對應(yīng)的數(shù)學(xué)模型為：現(xiàn)從另一個角度提出問題。假定有某個公司想把該工廠的資源收買過來，它至少應(yīng)付出多大代價，才能使這個工廠放棄生產(chǎn)活動，出讓自己的資源。顯然該工廠愿出讓自己資源的條件是，出讓價格應(yīng)不低于用同等數(shù)量資源由自己組織生產(chǎn)活動時獲取的盈利。－－價格底線第3頁，課件共114頁，創(chuàng)作于2023年2月表1-1產(chǎn)品A產(chǎn)品B資源限量勞動力設(shè)備原材料9434510360200300利潤元/kg70120設(shè)單位勞動力出讓價格y1元，單位設(shè)備臺時出讓價格y2元，單位原材料出讓價格y3元。出讓收入應(yīng)不低于自己生產(chǎn)收入：該公司希望用最小代價把這個工廠的全部資源收買過來：第4頁，課件共114頁，創(chuàng)作于2023年2月綜上所述，我們得到如下數(shù)學(xué)模型：原問題對偶問題第5頁，課件共114頁，創(chuàng)作于2023年2月二、對稱形式下對偶問題的一般形式定義：滿足下列條件的線性規(guī)劃問題稱為具有對稱形式：其變量均具有非負約束，其約束條件當(dāng)目標函數(shù)求極大時取“≤”號，當(dāng)目標函數(shù)求極小時均取“≥”號。下面是對稱形式下線性規(guī)劃原問題的一般形式：第6頁，課件共114頁，創(chuàng)作于2023年2月用yi(i=1,..,m)代表第i種資源的估價，則其對偶問題的一般形式為：第7頁，課件共114頁，創(chuàng)作于2023年2月若用矩陣表示：對稱形式下的原問題對稱形式下的對偶問題第8頁，課件共114頁，創(chuàng)作于2023年2月項目原問題對偶問題A約束系數(shù)矩陣其約束系數(shù)矩陣的轉(zhuǎn)置b約束條件的右端項向量目標函數(shù)中的價格系數(shù)向量C目標函數(shù)中的價格系數(shù)向量約束條件的右端項向量目標函數(shù)MaxZ=CXMinW=Yˊb約束條件Ax≤bAˊY≥Cˊ決策變量X≥0Y≥0將上述對稱形式下線性規(guī)劃的原問題與對偶問題進行比較，可列出下表所示的對應(yīng)關(guān)系第9頁，課件共114頁，創(chuàng)作于2023年2月寫出下面線性規(guī)劃的對偶規(guī)劃模型課堂練習(xí)第10頁，課件共114頁，創(chuàng)作于2023年2月解：按照對稱形式的對偶關(guān)系，其對偶模型為第11頁，課件共114頁，創(chuàng)作于2023年2月原問題有m個約束條件，對偶問題有m個變量原問題有n個變量，對偶問題有n個約束條件原問題的價值系數(shù)對應(yīng)對偶問題的右端項原問題的右端項對應(yīng)對偶問題的價值系數(shù)原問題的系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣原問題的約束條件與對偶問題方向相反原問題與對偶問題優(yōu)化方向相反小結(jié)第12頁，課件共114頁，創(chuàng)作于2023年2月相關(guān)證明：對偶問題的對偶即原問題令ωˊ=－ω對偶問題對偶問題令Z=－Zˊ第13頁，課件共114頁，創(chuàng)作于2023年2月三、非對稱形式下原－對偶問題關(guān)系原問題和對偶問題有很多內(nèi)在聯(lián)系，它們之間存在著嚴格的對應(yīng)關(guān)系：目標函數(shù)類型之間的對應(yīng)關(guān)系目標函數(shù)系數(shù)與右邊項的對應(yīng)關(guān)系約束系數(shù)矩陣之間的對應(yīng)關(guān)系約束類型與變量類型之間的對應(yīng)關(guān)系并非所有線性規(guī)劃問題具有對稱形式，故下面討論一般情況下線性規(guī)劃問題如何寫出其對偶問題：第14頁，課件共114頁，創(chuàng)作于2023年2月由于前面三個對應(yīng)關(guān)系與對稱形式下的對應(yīng)關(guān)系一致，故我們只需討論約束類型與變量類型之間的對應(yīng)關(guān)系:原問題(對偶問題)對偶問題（原問題）目標函數(shù)maxmin目標函數(shù)約束條件≤≥=≥0變量≤0無約束≥0變量≤0無約束≥≤約束條件=LableSensibleOddBizarreSensibleOddBizarre第15頁，課件共114頁，創(chuàng)作于2023年2月綜上所述，其變換形式歸納如下：原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標函數(shù)max目標函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項第16頁，課件共114頁，創(chuàng)作于2023年2月例寫出下列線性規(guī)劃問題的對偶問題解：SSSSSSOOBBSSOOBB第17頁，課件共114頁，創(chuàng)作于2023年2月例寫出下列線性規(guī)劃問題的對偶問題課堂練習(xí)第18頁，課件共114頁，創(chuàng)作于2023年2月答案：第19頁，課件共114頁，創(chuàng)作于2023年2月課堂練習(xí)第20頁，課件共114頁，創(chuàng)作于2023年2月第21頁，課件共114頁，創(chuàng)作于2023年2月對偶理論與靈敏度分析線性規(guī)劃的對偶問題對偶問題的基本性質(zhì)影子價格對偶單純形法靈敏度分析第22頁，課件共114頁，創(chuàng)作于2023年2月2.2對偶問題的基本性質(zhì)一、單純形法計算的矩陣描述對稱形式線性規(guī)劃問題的矩陣表達式加上松馳變量X后為：單純行法計算時，總選?、駷槌跏蓟?，對應(yīng)基變量Xs舉例：第23頁，課件共114頁，創(chuàng)作于2023年2月設(shè)迭代若干步后，基變量為XB,XB在初始單純行表中的系數(shù)矩陣為B。將B在初始單純行表中單獨列出，而A中去掉B的若干列后剩下的列組成N。于是其初始單純行表可表示成如下形式項目非基變量基變量XBXNXS0XSbBN

ⅠCj-ZjCBCN0表2.4第24頁，課件共114頁，創(chuàng)作于2023年2月當(dāng)?shù)舾刹胶?，基變量為XB時，該步的單純行表中由XB系數(shù)組成的矩陣為Ⅰ(單位矩陣)。又因單純行法的迭代是對增廣矩陣進行的初等變換，對應(yīng)Xs的系數(shù)矩陣在新表中應(yīng)為B-1;對應(yīng)XN的系數(shù)矩陣在新表中應(yīng)為B-1N于是迭代后的單純行表可表示成如下形式：表2.5項目基變量非基變量XBXN

XSCBXBB-1bⅠB-1NB-1ⅠCj-Zj0CN－CBB-1N-CBB-1

第25頁，課件共114頁，創(chuàng)作于2023年2月項目基變量非基變量XBXN

XSCBXBB-1bⅠB-1NB-1ⅠCj-ZjCBCN0項目非基變量基變量XBXNXS0XSbBN

ⅠCj-ZjCBCN0初始單純行表:B-1第26頁，課件共114頁，創(chuàng)作于2023年2月項目基變量非基變量XBXN

XSCBXBB-1bⅠB-1NB-1ⅠCj-Zj0CN－CBB-1N-CBB-1

表2.5項目基變量非基變量XBXN

XSCBXBB-1bⅠB-1NB-1ⅠCj-ZjCBCN0－CB第27頁，課件共114頁，創(chuàng)作于2023年2月課堂練習(xí)CjCBXBb檢驗數(shù)jx1x2x3x4x5x62-1100060311100101-120102011-1001x4x5x6000 2 -1 1 000CBXBb檢驗數(shù)jx1x2x3x4x5x61-1-201/21/20-1/21/2x4x1x202-1第28頁，課件共114頁，創(chuàng)作于2023年2月由可知：第29頁，課件共114頁，創(chuàng)作于2023年2月檢驗數(shù)的求解：第30頁，課件共114頁，創(chuàng)作于2023年2月CBXBb檢驗數(shù)jx1x2x3x4x5x6100011-1-215101/201/21/2501-3/20-1/21/2x4x1x202-1Cj

2-11000第31頁，課件共114頁，創(chuàng)作于2023年2月當(dāng)B為最優(yōu)基時，其所有檢驗數(shù)應(yīng)小于零（σj≤0)于是對應(yīng)于表2.5有：而對于XB的檢驗數(shù)可寫為：由此，（1）（2）（3）式可重新表示為：第32頁，課件共114頁，創(chuàng)作于2023年2月若令Yˊ=CBB-1,則上式可表達為：這時可以看出檢驗數(shù)行,若取其相反數(shù)恰好是其對偶問題的可行解。為什么？由于對偶問題的限制條件是≥的形式，則標準形式是在左邊減去一個剩余變量的基礎(chǔ)上得到的，這個剩余變量為第33頁，課件共114頁，創(chuàng)作于2023年2月可以看出，當(dāng)原問題為最優(yōu)解時，其對偶問題為可行解，且兩者具有相同的目標函數(shù)值。后面我們將看到，這時對偶問題的解也為最優(yōu)解將這個解代入對偶問題的目標函數(shù)，有:第34頁，課件共114頁，創(chuàng)作于2023年2月項目系數(shù)x1x2···xnxn+1xn+2···xn+mZj-Cjy1y2···ym

由上面的推導(dǎo)知，我們可以從線性規(guī)劃問題的最終單純中直接讀出其對偶問題的最優(yōu)解。注：Cj–Zj為檢驗數(shù)，需對其取反z1-c1z2-c2···zn-cnym+1ym+2···ym+n松弛變量Xs第35頁，課件共114頁，創(chuàng)作于2023年2月更一般的結(jié)論：用單純形法求解線性規(guī)劃問題時，迭代的每一步在得到原問題一個基可行解的同時，其檢驗行（行0）中的yi和zj－cj值是其對偶問題的一個基解第36頁，課件共114頁，創(chuàng)作于2023年2月舉例：下面是兩個互為對偶的線性規(guī)劃問題：原問題對偶問題第37頁，課件共114頁，創(chuàng)作于2023年2月將上面兩個線性規(guī)劃問題加入松弛和剩余變量后，得到如下形式：y1y2y3對偶變量對偶變量x1x2第38頁，課件共114頁，創(chuàng)作于2023年2月用單純形法和對偶單純型法求得兩個問題的最終單純形表如下：項目－jy4y5y1y2y3x1x2x3x4x5原問題變量原問題松弛變量x3x1x215/20015/4-15/27/21001/4-1/23/2010-1/43/20001/41/2對偶問題的剩余變量對偶問題變量原問題最終單純形表第39頁，課件共114頁，創(chuàng)作于2023年2月項目－jx3x4x5x1x2對偶問題最終單純形表y1y2y3y4y5對偶問題變量對偶問題剩余變量y2y31/4-5/410-1/41/41/215/2011/2-3/215/2007/23/2原問題松弛變量原問題變量從上面兩個表可以清楚的看出兩個問題變量之間的對應(yīng)關(guān)系。同時看出只需求解其中一個問題，從最優(yōu)的單純形表中同時得到另一個問題的最優(yōu)解第40頁，課件共114頁，創(chuàng)作于2023年2月二、對偶問題的基本性質(zhì)第41頁，課件共114頁，創(chuàng)作于2023年2月【定義2.1】（弱對偶性）如果xj(j=1,….n)是原問題的可行解，yi(i=1,…m)是其對偶問題的可行解，則恒有證明：第42頁，課件共114頁，創(chuàng)作于2023年2月由弱對偶性，可得出以下結(jié)論：1、原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界2、如原問題有可行解且目標函數(shù)值無界（具有無界解），則其對偶問題無可行解；反之對偶問題有可行解且目標函數(shù)值無界，則其原問題無可行解。注意：本點性質(zhì)的逆不成立，即當(dāng)對偶問題無可行解時，其原問題或具有無界解或無可行解；反之亦然第43頁，課件共114頁，創(chuàng)作于2023年2月3、若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界；反之對偶問題有可行解而其原問題無可行解，則對偶問題的目標函數(shù)值無界。第44頁，課件共114頁，創(chuàng)作于2023年2月【定理2.2】（最優(yōu)性）如果xj(j=1,…,n)是原問題的可行解，yi(i=1,…,m)是其對偶問題的可行解，且有則xj(j=1,…,n)是原問題的最優(yōu)解，yi(i=1,…,m)是其對偶問題的最優(yōu)解第45頁，課件共114頁，創(chuàng)作于2023年2月證明：設(shè)xj*(j=1,…,n)是原問題的最優(yōu)解，yi*(i=1,..,m)是對偶問題的最優(yōu)解。由弱對偶性質(zhì)有：又知：第46頁，課件共114頁，創(chuàng)作于2023年2月【定理2.3】（強對偶性）若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等證明：由于兩者均有可行解，根據(jù)弱對偶性，對原問題的目標函數(shù)具有上界，對偶問題的目標函數(shù)具有下界，因此兩者具有最優(yōu)解。由矩陣描述一節(jié)可知，當(dāng)原問題為最優(yōu)解時，其對偶問題的解為可行解，且有Z=ω,由定理2.2可知，這時兩者均為最優(yōu)解第47頁，課件共114頁，創(chuàng)作于2023年2月PrimalproblemDualproblemOptimalZ*OptimalW*第48頁，課件共114頁，創(chuàng)作于2023年2月【定理2.4】（互補松弛性）在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之，如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零，也即：第49頁，課件共114頁，創(chuàng)作于2023年2月以前面例子說明互補松弛定理：y1y2y3對偶變量y1y2y3第50頁，課件共114頁，創(chuàng)作于2023年2月互補松弛定理（說明續(xù)）：項目－jy4y5y1y2y3x1x2x3x4x5原問題變量原問題松弛變量x3x1x215/20015/4-15/27/21001/4-1/23/2010-1/43/20001/41/2對偶問題的剩余變量對偶問題變量原問題最終單純形表第51頁，課件共114頁，創(chuàng)作于2023年2月已知線性規(guī)劃問題minω=2x1+3x2+5x3+2x4+3x5

x1+x2+2x3+x4+3x5

≥42x1?x2+3x3+x4+x5

≥3xj

≥0(j=1,2,···,5)對偶問題的最優(yōu)解為y1*=4/5,y2*=3/5,Z=5,試找出原問題的最優(yōu)解。課堂舉例st.第52頁，課件共114頁，創(chuàng)作于2023年2月分析：先寫出其對偶問題maxZ=4y1+3y2y1+2y2

≤2y1-y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3x1x2x3x4x5將y1*、y2*的值帶入約束條件，得到2～4個約束條件為嚴格不等式；由互補松弛性得x2*=x3*=x4*=0.因y1*、y2*>0;原問題的兩個約束條件應(yīng)取等式：x1*+3x5*=42x1*+x5*=3求解后得到x1*=1,x5*=1,故原問題最優(yōu)解x*=(1,0,0,0,0,1)T;ω*=5第53頁，課件共114頁，創(chuàng)作于2023年2月課堂練習(xí)已知原問題的最優(yōu)解為X*=(0,0,4)T,最優(yōu)值為Z*=12.試用對偶理論求對偶問題的最優(yōu)解第54頁，課件共114頁，創(chuàng)作于2023年2月將X*=(0,0,4)T,代入原問題的三個約束條件可知：由松弛互補定理可知，必有y1*=y2*=0，代入對偶問題得y3*=3y1y2y3對偶變量解：原問題的對偶問題為：Y*=(0,0,3),最優(yōu)值為W*=12第55頁，課件共114頁，創(chuàng)作于2023年2月對偶理論與靈敏度分析線性規(guī)劃的對偶問題對偶問題的基本性質(zhì)影子價格對偶單純形法靈敏度分析第56頁，課件共114頁，創(chuàng)作于2023年2月當(dāng)線性規(guī)劃原問題求得最優(yōu)解xj*(j=1,2…n)時，其對偶問題也得到最優(yōu)解yi*(i=1,..,m),代入各自的目標函數(shù)后有：3.3.1其中，bi代表第i種資源的擁有量，對偶變量yi*的意義代表在資源最優(yōu)利用條件下對單位資源i的估價。這種估計不是資源的市場價格，而是根據(jù)在生產(chǎn)中做出的貢獻而作的估價，為區(qū)別一般意義的價格，我們將其（yi*）稱為影子價格（shadowprice）2.3影子價格（對偶最優(yōu)解的經(jīng)濟解釋）第57頁，課件共114頁，創(chuàng)作于2023年2月影子價格的幾點說明1資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。2影子價格是一種邊際價格，在3.31式中對Z求bi的偏導(dǎo)數(shù)得這說明yi*的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，bi每增加一個單位時目標函數(shù)Z的增量第58頁，課件共114頁，創(chuàng)作于2023年2月關(guān)于第2點的說明檢驗數(shù)jx3x2x10532100-1/31/360101/2020011/3-1/3-36000-3/2-1最終單純形表y1y2y3對偶變量y1y2y3第59頁，課件共114頁，創(chuàng)作于2023年2月關(guān)于第2點的說明(2,6)(5/3,13/2)Z1=3(2)+5(6)=362x2=122x2=13Z2=3(5/3)+5(13/2)=37.5△Z=Z2–Z1=3/2=y*2第60頁，課件共114頁，創(chuàng)作于2023年2月3資源的影子價格實際上又是一種機會成本。在純市場經(jīng)濟條件下，當(dāng)某一資源的市場價格低于該影子價格時，可以買進這種資源；相反，當(dāng)市場價格高于影子價格時，就會賣出這種資源。隨著資源的買進賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。4、在上一節(jié)對偶問題的互補松弛性質(zhì)中有第61頁，課件共114頁，創(chuàng)作于2023年2月這表明生產(chǎn)過程中如果某資源bi未得到充分利用，則該種資源的影子價格為零；又當(dāng)某資源的影子價格不為零時，表明該種資源已消耗完畢。(互補松弛定理的經(jīng)濟解釋)5對單純形表的檢驗數(shù)Cj代表第j種產(chǎn)品的單位產(chǎn)值，∑aijyi是生產(chǎn)單位該種產(chǎn)品所消耗各項資源的影子價格的總和。當(dāng)產(chǎn)品單位產(chǎn)值大于隱含成本時，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排生產(chǎn)，否則用這些資源來生產(chǎn)別的產(chǎn)品更為有利，就不安排生產(chǎn)。（檢驗數(shù)的經(jīng)濟解釋）第62頁，課件共114頁，創(chuàng)作于2023年2月6一般說來，對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價，這種估計直接涉及資源的最有效利用。例如，在一個大公司內(nèi)部，可借助資源的影子價格確定一些內(nèi)部結(jié)算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。又如，在社會上可對一些最緊缺的資源，借助影子價格規(guī)定使用這種單位資源時必須上交的利潤額，以控制一些經(jīng)濟效益低的企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大的經(jīng)濟效益。第63頁，課件共114頁，創(chuàng)作于2023年2月對偶理論與靈敏度分析線性規(guī)劃的對偶問題對偶問題的基本性質(zhì)影子價格對偶單純形法靈敏度分析第64頁，課件共114頁，創(chuàng)作于2023年2月2.4對偶單純形法一、對偶單純形法的基本思路對原問題的一個基可行解，判別是否所有檢驗數(shù)，若是，又基變量中無非零人工變量，即找到了問題的最優(yōu)解；若為否，再找出相鄰的目標函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進行到找出最優(yōu)解為止。求解線性規(guī)劃的單純形法的思路是：第65頁，課件共114頁，創(chuàng)作于2023年2月對偶單純形法的基本思路是：從原問題的一個基本解出發(fā)，此基本解不一定可行（即b中有負數(shù)），但它對應(yīng)著一個對偶可行解（檢驗數(shù)非正），所以此時也可以說是從一個對偶可行解出發(fā)；然后檢驗原問題的基本解是否可行，即b是否有為負的分量,若是，則進行迭代，求解另一個基本解，此基本解對應(yīng)著另一個對偶可行解（保持檢驗數(shù)非正）。如果得到的基本解的分量皆非負，則該基本解為最優(yōu)解。根據(jù)對偶問題的性質(zhì)，因為Cj–Zj=Cj–CBB-1Pj,當(dāng)Cj–Zj≤0(j=1,2,…n),即有YˊPj≥Cj或∑aijyi≥Cj(j=1,2,…n)也即其對偶問題的解為可行解。i=1m第66頁，課件共114頁，創(chuàng)作于2023年2月也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原問題的基本解由不可行逐步變?yōu)榭尚?。?dāng)同時得到對偶問題與原問題的可行解時，便得到了原問題的最優(yōu)解。第67頁，課件共114頁，創(chuàng)作于2023年2月單純形法與對偶單純形法之間的比較單純形法對偶單純形法前提條件所有bi≥0所有σj≤0最優(yōu)解檢驗所有σj≤0所有bi≥0換入、換出變量的確定先確定換入變量后確定換出變量先確定換出變量后確定換入變量基解的變化可行→最優(yōu)非可行→可行（最優(yōu)）第68頁，課件共114頁，創(chuàng)作于2023年2月二、對偶單純形法的計算步驟1根據(jù)線性規(guī)劃問題，列出初始單純形表，檢查b列的數(shù)字，若都為非負，檢驗數(shù)都為非正，則已得到最優(yōu)解，停止計算。若檢查b列的數(shù)字時，至少有一個負分量，所有檢驗數(shù)保持非正，那么進行以下計算2確定換出基的變量按對應(yīng)的基變量xr為換出基的變量第69頁，課件共114頁，創(chuàng)作于2023年2月確定換入變量在單純形表中檢查xr所在行的各系數(shù)arj(j=1,2,…n)①若所有arj≥0，則原問題無可行解xr+ar,m+1xm+1+…arnxn=br因為arj≥0(j=m+1,..,n),又br<0,故不可能存在xj≥0(j=1,2..n)，故原問題無可行解。②若存在arj<0(j=1,2…n),則按最小比值原則計算稱ars為主元素（樞軸元素），xs為換入基的變量第70頁，課件共114頁，創(chuàng)作于2023年2月4以ars為主元素，進行高斯消元，得到新的計算表重復(fù)1～4的步驟第71頁，課件共114頁，創(chuàng)作于2023年2月解：將模型轉(zhuǎn)化為三、對偶單純形法舉例第72頁，課件共114頁，創(chuàng)作于2023年2月cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001Cj–Zj0-9-12-15000(-9/-1,-12/-1,-15/-5)cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5Cj–Zj42-6-9000-3(-30/-9,-45/-14,-15/-1)第73頁，課件共114頁，創(chuàng)作于2023年2月cj-9-12-15000cBxBbx1x2x3x4x5x60x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14-15x315/71/140101/14-3/14Cj–Zj501/7-3/14000-45/14-33/14(-3/-9,-45/-9,-33/-1)cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9Cj–Zj72000-1/3-3-7/3第74頁，課件共114頁，創(chuàng)作于2023年2月四、對偶單純形法的應(yīng)用時機1對偶單純形法的優(yōu)點是，初始解可以是非可行解，不需要加入人工變量2對一個線性規(guī)劃問題，即可以用單純形法求解，也可以用對偶單純形法求解。具體采用那種方法，由當(dāng)前情況（計算表）決定。使用那種方法比較方便，就使用那種方法第75頁，課件共114頁，創(chuàng)作于2023年2月3求目標函數(shù)最大化時，在單純形表中：①如果檢驗數(shù)均非正，而b列中有負值，這時使用對偶單純形法；②如果所有bi≥0,檢驗數(shù)有正值，使用單純形法③如果b列中有負值，且檢驗數(shù)中有正值，這時必須引入人工變量，建立新的單純形表，重新計算第76頁，課件共114頁，創(chuàng)作于2023年2月用對偶單純法求解下述線性規(guī)劃問題：分析：先將問題改寫為最大化形式，然后在約束條件兩端乘“－1”后，加入相應(yīng)的松弛變量得：課堂練習(xí)第77頁，課件共114頁，創(chuàng)作于2023年2月列出單純形表，并用上述對偶單純形法求解步驟進行計算Cj→-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101Cj-Zj-15-24-500-24/-6<-5/-1(最小比值原則)樞軸元素第78頁，課件共114頁，創(chuàng)作于2023年2月Cj→-15-24-500CB基by1y2y3y4y5-24y21/3011/6-1/600y5-1/3-50-2/3-1/31Cj-Zj-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2Cj–Zj-15/200-7/2-3/2因為所有bi≥0且所有σj保持非正，故該問題得到最優(yōu)解，停止計算第79頁，課件共114頁，創(chuàng)作于2023年2月對偶理論與靈敏度分析線性規(guī)劃的對偶問題對偶問題的基本性質(zhì)影子價格對偶單純形法靈敏度分析第80頁，課件共114頁，創(chuàng)作于2023年2月2.5靈敏度分析為什么進行靈敏度分析？

在前面討論線性規(guī)劃時，假定aij、bi、cj都是常數(shù)（回憶前面線性規(guī)劃問題的四個假設(shè)－確定性）。但實際上這些系數(shù)往往是估計值和預(yù)測值。如市場條件一變，cj值就會發(fā)生變化；aij往往是因工藝條件的改變而改變；bi是根據(jù)資源投入后的經(jīng)濟效果決定的一種決策選擇。第81頁，課件共114頁，創(chuàng)作于2023年2月因此提出這樣的兩個問題：①當(dāng)這些系數(shù)一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解是否會發(fā)生變化（確定敏感參數(shù)）②對于非敏感參數(shù)在什么范圍內(nèi)變化，線性規(guī)劃問題的最優(yōu)解不變第82頁，課件共114頁，創(chuàng)作于2023年2月靈敏度分析采用的方法：對于上述兩個問題，如果將問題從頭計算求解，當(dāng)然是一種方法，但是這樣不僅麻煩、沒有必要，而且也得不到更多有用的信息。靈敏度分析采用的方法是從已得到的最優(yōu)解出發(fā)，通過對變化數(shù)據(jù)進行一些簡單的計算，便可迅速得到所需要的結(jié)果以及變化后的最優(yōu)解。因此，靈敏度分析也稱優(yōu)化后分析。第83頁，課件共114頁，創(chuàng)作于2023年2月靈敏度分析的步驟：將參數(shù)的改變通過計算反映到最終單純形表上來：（難點、關(guān)鍵）初始單純行表：項目非基變量基變量XBXNXS0XSbBNICj-ZjCBCN0迭代若干步后的單純行表：（最終單純形表）項目基變量非基變量XBXN

XSCBXBB-1bIB-1NB-1ICj-Zj0CN-CBB-1N-CBB-1

第84頁，課件共114頁，創(chuàng)作于2023年2月初始單純形表：系數(shù)列向量：Pj（j=1,2…n）右端項：b價值系數(shù):Cj

（j=1,2…n）B-1最終單純形表：系數(shù)列向量：B-1Pj右端項：B-1b檢驗數(shù)：σj=Cj-CBB-1pj第85頁，課件共114頁，創(chuàng)作于2023年2月1將參數(shù)的改變通過計算反映到最終單純形表上來：2檢查原問題是否仍為可行解3檢查對偶問題是否仍為可行解靈敏度分析的三把尺子第86頁，課件共114頁，創(chuàng)作于2023年2月4按下表所列的情況得出結(jié)論或者決定繼續(xù)計算的步驟原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引入人工變量，編制新的單純行表重新計算第87頁，課件共114頁，創(chuàng)作于2023年2月靈敏度分析背景例子美佳公司計劃制造I、II兩種家電產(chǎn)品。已知各制造一件時分別占用A、B的臺時、調(diào)試時間及每天可用于這兩種家電的能力、各售出一件時的獲利情況，如下表所示。問該公司每天應(yīng)制造兩種家電各多少件，使獲利最大項目ⅠⅡ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤（元）21第88頁，課件共114頁，創(chuàng)作于2023年2月其數(shù)學(xué)模型為：Cj→21000CB基bx1x2x3x4x50x315051000x424620100x5511001Cj-Zj21000初始單純形表第89頁，課件共114頁，創(chuàng)作于2023年2月Cj→21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2Cj-Zj000-1/4-1/2最終單純形表：第90頁，課件共114頁，創(chuàng)作于2023年2月一、分析Cj的變化線性規(guī)劃目標函數(shù)中變量系數(shù)Cj的變化僅僅影響到檢驗數(shù)（Cj-Zj）的變化。Cj的變化不會影響到解的可行性，我們只需要判斷解的最優(yōu)性（對偶問題的可行性）即可。①若該解最優(yōu)，則最優(yōu)解不變②若該解不是最優(yōu)，則使用單純形法迭代直到得到最優(yōu)解第91頁，課件共114頁，創(chuàng)作于2023年2月下面舉例說明：（1）若家電I的利潤2－>1.5，而家電II的利潤1－>2，美佳公司最優(yōu)生產(chǎn)計劃有何變化(2)若家電I的利潤不變，則家電II的利潤在什么范圍內(nèi)變化時，則該公司的最優(yōu)生產(chǎn)計劃不發(fā)生變化第92頁，課件共114頁，創(chuàng)作于2023年2月分析：(1)Cj→21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2Cj-Zj000-1/4-1/2最終單純形表σjˊ=Cjˊ-CBˊB-1pj,其中B-1pj可從最終單純形表讀得Cj→3/2

2000CB基bx1x2x3x4x50x315/20015/4-15/23/2x17/21001/4-1/22x23/2010-1/43/2Cj-Zj0001/8-9/4因變量x4的檢驗數(shù)大于零，故需繼續(xù)用單純形法迭代第93頁，課件共114頁，創(chuàng)作于2023年2月Cj→3/22000比值CB基bx1x2x3x4x50x315/20015/4-15/23/2x17/21001/4-1/22x23/2010-1/43/2Cj-Zj0001/8-9/4614－Cj→3/22000CB基bx1x2x3x4x50x46004/51-63/2x1210-1/5012x23011/500Cj-Zj00-1/100-3/2即美佳公司隨家電利潤的變化應(yīng)調(diào)整為生產(chǎn)I2件，生產(chǎn)II3件第94頁，課件共114頁，創(chuàng)作于2023年2月分析：(2)設(shè)家電II的利潤為(1+λ)元，反映到最終單純形表中，得下表：Cj→21+λ000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21+λx23/2010-1/43/2Cj-Zj000-1/4+1/4λ-1/2-3/2λ為使上表的解仍為最優(yōu)解，應(yīng)有：-1/4+1/4λ≤0;-1/2－2/3λ≤0解得：-1/3≤λ≤1即家電II的利潤c2的變化范圍應(yīng)滿足：2/3≤c2≤2第95頁，課件共114頁，創(chuàng)作于2023年2月二、分析bi的變化右端項bi的變化在實際問題中反映為可用資源數(shù)量的變化。由于bi變化反映到最終單純形表上僅引起b列數(shù)字的變化，故解的最優(yōu)性不受影響（對偶問題可行），我們只需要判斷解的可行性即可。①若該解可行，則最優(yōu)基不變②若該解不可行，則使用對偶單純形法迭代直到找到最優(yōu)解第96頁，課件共114頁，創(chuàng)作于2023年2月在上述美佳公司的例子中：（1）若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32h，分析公司最優(yōu)計劃的變化（2）若設(shè)備A和設(shè)備B每天可用能力不變，則調(diào)試工序能力在什么范圍變化時，問題的最優(yōu)基不變第97頁，課件共114頁，創(chuàng)作于2023年2月分析：(1)因為，于是有：將計算結(jié)果反映到最終單純形表中去,有：第98頁，課件共114頁，創(chuàng)作于2023年2月Cj→21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2Cj-Zj000-1/4-1/2原最終單純形表Cj→21000CB基bx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2－1/2010-1/43/2Cj-Zj000-1/4-1/2由于原問題為非可行解，故用對偶單純形法繼續(xù)計算得下表第99頁，課件共114頁，創(chuàng)作于2023年2月Cj→21000CB基bx1x2x3x4x50x315051002x15110010x420-401-6Cj-Zj0-100-2由此，美佳公司的最優(yōu)計劃改變?yōu)橹簧a(chǎn)家電Ⅰ5件第100頁，課件共114頁，創(chuàng)作于2023年2月分析：（2）設(shè)調(diào)試工序每天可用能力為（5+λ）h,因此有：當(dāng)b≥0時問題的最優(yōu)基不變，解得-1≤λ≤1由此，此調(diào)試工序的能力應(yīng)在4～6h之間第101頁，課件共114頁，創(chuàng)作于2023年2月三、增加一個變量xj的變化增加一個變量在實際問題中反映為增加一種新的產(chǎn)品，其分析步驟為：1、計算2、計算3、若，則原最優(yōu)解不變，只需將計算得到的直接寫入最終單純形表中即可；若存在,則按單純形法繼續(xù)迭代計算找出最優(yōu)解。第102頁，課件共114頁，創(chuàng)作于2023年2月美佳公司又計劃推出新型號的家電III，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序的時間分別為3h,4h,2h，該產(chǎn)品的預(yù)期盈利為3元/件，試分析該種產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，對該公司的最優(yōu)生產(chǎn)計劃有何變化。分析：設(shè)該公司生產(chǎn)家電IIIx6件，有C6=3,P6=(3,4,2)T第103頁，課件共114頁，創(chuàng)作于2023年2月將其反映到最終單純形表中得下表：Cj→210003CB基bx1x2x3x4x5

x60x315/20015/4-15/2

-7

2x17/21001/4-1/201x23/2010-1/43/2

2Cj-Zj000-1/4-1/2

1Cj→210003CB基bx1x2x3x4x5

x60x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/4

1Cj-Zj0-1/20-1/8-5/40由此，美佳公司最優(yōu)生產(chǎn)計劃應(yīng)為每天生產(chǎn)家電I7/2件；家電III3/4件第104頁，課件共114頁，創(chuàng)作于2023年2月四、分析參數(shù)aij的變化aij的變化使線性規(guī)劃的約束系數(shù)矩陣A發(fā)生變化。①若變量Xj在最終單純形表中為非基變量，其約束條件中系數(shù)aij的變化分析步驟可以參照前面小節(jié)（增加一個變量xj的變化）。②若變量xj在最終單純行表中為基變量，則在計算反映到最終單純形表后，需要對其作高斯消元，已保證得到恰當(dāng)?shù)男问剑╬roperformfromGaussianelimination）第105頁，課件共114頁，創(chuàng)作于2023年2月注：對第二種情況，高斯消元后可能出現(xiàn)原問題和對偶問題均無可行解的情況。出現(xiàn)這種情況時，需要引進人工變量先將原問題轉(zhuǎn)化為可行解，再用單純形法求解。第106頁，課件共114頁，創(chuàng)作于2023年2月例在美佳公司的例子中，若家電II每件需設(shè)備A,B和調(diào)試工時變?yōu)?h,4h,1h，該產(chǎn)品的利潤變?yōu)?元/件，試重新確定該公司最優(yōu)生產(chǎn)計劃解：先將生產(chǎn)工時變化后的家電II看作時一種新產(chǎn)品，仿照前面小節(jié)的計算步驟，計算出并反映到最終單純形表中，其中第107頁，課件共114頁，創(chuàng)作于2023年2月將其反映到最終單純形表有：Cj→23000CB基bx1x2x3x4x50x315/2011/215/4-15/22x17/211/201/4-1/23x23/201/20-1/43/2Cj-Zj03/20-1/4-1/2不符合高斯消元形式Cj→23000CB基bx1x2x3x4x50x315/2011/215/4-15/22x17/211/201/4-1/23x23/201/20-1/43/2Cj-Zj03/20-1/4-1/2第108頁，課件共114頁，創(chuàng)作于2023年2月Cj→23000CB基bx1x2x3x4x50x315/2011/215/4-15/22x17/211/201/4-1/23x23/201/20-1/43/2Cj-Zj03/20-1/4-1/2Cj→23000CB基bx1x2x3x4x50x3-90014-242x121001/2