第二章 對(duì)偶問(wèn)題與靈敏度分析

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

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

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

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

XSCBXBB-1bⅠB-1NB-1ⅠCj-ZjCBCN0項(xiàng)目非基變量基變量XBXNXS0XSbBN

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

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

表2.5項(xiàng)目基變量非基變量XBXN

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

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

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

x1+x2+2x3+x4+3x5

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

≥3xj

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

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

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

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

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

（j=1,2…n）B-1最終單純形表：系數(shù)列向量：B-1Pj右端項(xiàng)：B-1b檢驗(yàn)數(shù)：σj=Cj-CBB-1pj第85頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月1將參數(shù)的改變通過(guò)計(jì)算反映到最終單純形表上來(lái)：2檢查原問(wèn)題是否仍為可行解3檢查對(duì)偶問(wèn)題是否仍為可行解靈敏度分析的三把尺子第86頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月4按下表所列的情況得出結(jié)論或者決定繼續(xù)計(jì)算的步驟原問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解問(wèn)題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引入人工變量，編制新的單純行表重新計(jì)算第87頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月靈敏度分析背景例子美佳公司計(jì)劃制造I、II兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用A、B的臺(tái)時(shí)、調(diào)試時(shí)間及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如下表所示。問(wèn)該公司每天應(yīng)制造兩種家電各多少件，使獲利最大項(xiàng)目ⅠⅡ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤(rùn)（元）21第88頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月其數(shù)學(xué)模型為：Cj→21000CB基bx1x2x3x4x50x315051000x424620100x5511001Cj-Zj21000初始單純形表第89頁(yè)，課件共114頁(yè)，創(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頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月一、分析Cj的變化線性規(guī)劃目標(biāo)函數(shù)中變量系數(shù)Cj的變化僅僅影響到檢驗(yàn)數(shù)（Cj-Zj）的變化。Cj的變化不會(huì)影響到解的可行性，我們只需要判斷解的最優(yōu)性（對(duì)偶問(wèn)題的可行性）即可。①若該解最優(yōu)，則最優(yōu)解不變②若該解不是最優(yōu)，則使用單純形法迭代直到得到最優(yōu)解第91頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月下面舉例說(shuō)明：（1）若家電I的利潤(rùn)2－>1.5，而家電II的利潤(rùn)1－>2，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化(2)若家電I的利潤(rùn)不變，則家電II的利潤(rùn)在什么范圍內(nèi)變化時(shí)，則該公司的最優(yōu)生產(chǎn)計(jì)劃不發(fā)生變化第92頁(yè)，課件共114頁(yè)，創(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的檢驗(yàn)數(shù)大于零，故需繼續(xù)用單純形法迭代第93頁(yè)，課件共114頁(yè)，創(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即美佳公司隨家電利潤(rùn)的變化應(yīng)調(diào)整為生產(chǎn)I2件，生產(chǎn)II3件第94頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月分析：(2)設(shè)家電II的利潤(rùn)為(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的利潤(rùn)c2的變化范圍應(yīng)滿足：2/3≤c2≤2第95頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月二、分析bi的變化右端項(xiàng)bi的變化在實(shí)際問(wèn)題中反映為可用資源數(shù)量的變化。由于bi變化反映到最終單純形表上僅引起b列數(shù)字的變化，故解的最優(yōu)性不受影響（對(duì)偶問(wèn)題可行），我們只需要判斷解的可行性即可。①若該解可行，則最優(yōu)基不變②若該解不可行，則使用對(duì)偶單純形法迭代直到找到最優(yōu)解第96頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月在上述美佳公司的例子中：（1）若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32h，分析公司最優(yōu)計(jì)劃的變化（2）若設(shè)備A和設(shè)備B每天可用能力不變，則調(diào)試工序能力在什么范圍變化時(shí)，問(wèn)題的最優(yōu)基不變第97頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月分析：(1)因?yàn)?，于是有：將?jì)算結(jié)果反映到最終單純形表中去,有：第98頁(yè)，課件共114頁(yè)，創(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由于原問(wèn)題為非可行解，故用對(duì)偶單純形法繼續(xù)計(jì)算得下表第99頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月Cj→21000CB基bx1x2x3x4x50x315051002x15110010x420-401-6Cj-Zj0-100-2由此，美佳公司的最優(yōu)計(jì)劃改變?yōu)橹簧a(chǎn)家電Ⅰ5件第100頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月分析：（2）設(shè)調(diào)試工序每天可用能力為（5+λ）h,因此有：當(dāng)b≥0時(shí)問(wèn)題的最優(yōu)基不變，解得-1≤λ≤1由此，此調(diào)試工序的能力應(yīng)在4～6h之間第101頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月三、增加一個(gè)變量xj的變化增加一個(gè)變量在實(shí)際問(wèn)題中反映為增加一種新的產(chǎn)品，其分析步驟為：1、計(jì)算2、計(jì)算3、若，則原最優(yōu)解不變，只需將計(jì)算得到的直接寫(xiě)入最終單純形表中即可；若存在,則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)解。第102頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月美佳公司又計(jì)劃推出新型號(hào)的家電III，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序的時(shí)間分別為3h,4h,2h，該產(chǎn)品的預(yù)期盈利為3元/件，試分析該種產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，對(duì)該公司的最優(yōu)生產(chǎn)計(jì)劃有何變化。分析：設(shè)該公司生產(chǎn)家電IIIx6件，有C6=3,P6=(3,4,2)T第103頁(yè)，課件共114頁(yè)，創(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)計(jì)劃應(yīng)為每天生產(chǎn)家電I7/2件；家電III3/4件第104頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月四、分析參數(shù)aij的變化aij的變化使線性規(guī)劃的約束系數(shù)矩陣A發(fā)生變化。①若變量Xj在最終單純形表中為非基變量，其約束條件中系數(shù)aij的變化分析步驟可以參照前面小節(jié)（增加一個(gè)變量xj的變化）。②若變量xj在最終單純行表中為基變量，則在計(jì)算反映到最終單純形表后，需要對(duì)其作高斯消元，已保證得到恰當(dāng)?shù)男问剑╬roperformfromGaussianelimination）第105頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月注：對(duì)第二種情況，高斯消元后可能出現(xiàn)原問(wèn)題和對(duì)偶問(wèn)題均無(wú)可行解的情況。出現(xiàn)這種情況時(shí)，需要引進(jìn)人工變量先將原問(wèn)題轉(zhuǎn)化為可行解，再用單純形法求解。第106頁(yè)，課件共114頁(yè)，創(chuàng)作于2023年2月例在美佳公司的例子中，若家電II每件需設(shè)備A,B和調(diào)試工時(shí)變?yōu)?h,4h,1h，該產(chǎn)品的利潤(rùn)變?yōu)?元/件，試重新確定該公司最優(yōu)生產(chǎn)計(jì)劃解：先將生產(chǎn)工時(shí)變化后的家電II看作時(shí)一種新產(chǎn)品，仿照前面小節(jié)的計(jì)算步驟，計(jì)算出并反映到最終單純形表中，其中第107頁(yè)，課件共114頁(yè)，創(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頁(yè)，課件共114頁(yè)，創(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