管理運(yùn)籌學(xué)第3章對(duì)偶規(guī)劃課件

第3章對(duì)偶規(guī)劃2/6/20231課件教學(xué)目標(biāo)與要求【教學(xué)目標(biāo)】通過對(duì)本章的學(xué)習(xí)，理解對(duì)偶定義和性質(zhì)及影子價(jià)格的含義；了解對(duì)偶單純形法；會(huì)根據(jù)最終單純形表對(duì)于資源項(xiàng)、目標(biāo)系數(shù)變動(dòng)進(jìn)行敏感性分析。【知識(shí)結(jié)構(gòu)】2/6/20232課件本章主要內(nèi)容3.1線性規(guī)劃的對(duì)偶模型3.1.1對(duì)偶問題3.1.2線性規(guī)劃對(duì)偶模型3.1.3對(duì)偶問題的基本性質(zhì)3.2對(duì)偶單純形法簡介3.3影子價(jià)格3.4靈敏度分析3.4.1價(jià)值系數(shù)的變化分析3.4.2右端常數(shù)的變化分析3.4.3增加一個(gè)新變量的分析3.4.4增加新的約束條件的分析3.5如何看計(jì)算機(jī)求解報(bào)告本章小結(jié)2/6/20233課件3.1.1對(duì)偶問題原始規(guī)劃設(shè)：兩種設(shè)備單位臺(tái)時(shí)租金分別為y1,y2由于承租方是理智的，會(huì)把租金壓至最低。故出租方在滿足上述二約束情況下，至少出租總收入（目標(biāo)函數(shù)）為約束一：生產(chǎn)甲產(chǎn)品的利潤不大于放棄生產(chǎn)而出租的租金收入約束二：生產(chǎn)乙產(chǎn)品的利潤不大于放棄生產(chǎn)而出租的租金收入對(duì)偶規(guī)劃稱（2）為（1）的對(duì)偶，也稱（1）為（2）的對(duì)偶。2/6/20235課件3.1.2對(duì)偶問題的數(shù)學(xué)模型（1）對(duì)稱形式對(duì)偶問題原問題對(duì)偶問題2/6/20236課件3.1.2對(duì)偶問題的數(shù)學(xué)模型（2）非對(duì)稱形式對(duì)偶問題【例3.1】寫出下列線性規(guī)劃的對(duì)偶規(guī)劃。對(duì)偶模型：2/6/20237課件3.2對(duì)偶單純形法簡介2/6/20239課件3.2對(duì)偶單純形法簡介標(biāo)準(zhǔn)化（若≥乘-1）計(jì)算檢驗(yàn)數(shù)所有σ≤0?Yes所有b≥0?不符合對(duì)偶單純形法條件，改用大M法No結(jié)束Yes找到最優(yōu)解No找出最小bk

xk為離去變量所有akj≥0?θs=min{akj/σj|σj<0}，xs入基，迭代得新單純形表No無可

行解Yes2/6/202310課件3.2對(duì)偶單純形法簡介【例3.2】用對(duì)偶單純形法解解標(biāo)準(zhǔn)化初始單純形表第1次迭代第2次迭代最優(yōu)解最優(yōu)值202/6/202311課件3.3影子價(jià)格導(dǎo)入案例原問題的解如圖.對(duì)偶問題的解2/6/202313課件3.3影子價(jià)格原問題bi代表第i種資源擁有量yi代表第i種資源的估價(jià)，該估價(jià)并非市價(jià)格，而是在生產(chǎn)中的單位貢獻(xiàn)所做的估價(jià),稱為影子價(jià)格。其含義：（1）資源的市場價(jià)格由供求關(guān)系決定，而它的影子價(jià)格則有賴于資源的利用情況。（2）影子價(jià)格是一種邊際價(jià)格。（3）資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本。（4）當(dāng)影子價(jià)格為0時(shí)，表明該種資源未得到充分利用；當(dāng)影子價(jià)格不為0時(shí)，表明該種資源已耗費(fèi)完畢。（5）在一個(gè)大公司內(nèi)部，可借助資源的影子價(jià)格確定一些內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。對(duì)偶問題2/6/202314課件3.4靈敏度分析線性規(guī)劃的各個(gè)參數(shù)A，C，b往往是根據(jù)統(tǒng)計(jì)數(shù)據(jù)測算的，不可能完全準(zhǔn)確，而且隨著實(shí)際情況變化。靈敏度分析是指各參數(shù)變化對(duì)最優(yōu)解的影響。2/6/202315課件3.4.2右端項(xiàng)bi的變化分析設(shè)由式3-8，若則最優(yōu)基保持不變.【例3.5】由[例3.4]最終單純形表求最優(yōu)基不變的b3允許變化范圍。初始基最優(yōu)基即b3的允許變化范圍：[40,50]2/6/202317課件3.4.3增加一個(gè)新變量的分析2/6/202318課件3.4.3增加一個(gè)新變量的分析在操作上：由若大于0應(yīng)安排生產(chǎn)?！纠?.6】在例3.4中增加一個(gè)新產(chǎn)品是否可行。其消耗系數(shù)列向量p6=（3/2，1，1/2）及價(jià)值系數(shù)c6=3.2/6/202319課件3.5如何看計(jì)算機(jī)求解報(bào)告【例3.8】Globaloptimalsolutionfound.Objectivevalue: 35.00000Totalsolveriterations: 2Variable Value ReducedCostX(1) 5.000000 0.000000X(2) 0.000000 2.000000X(3) 5.000000 0.000000Row SlackorSurplus DualPrice1 35.00000 1.0000002 0.000000 0.20000003 0.000000 0.6000000Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRanges

Current Allowable AllowableVariable Coefficient Increase DecreaseX(1) 3.000000 1.800000 0.6000000X(2) 1.000000 2.000000 INFINITYX(3) 4.000000 1.000000 1.500000

RighthandSideRangesRowCurrent Allowable AllowableRHS Increase Decrease2

55.00000 25.00000 15.000003

40.00000 15.00000 12.50000最優(yōu)值迭代次數(shù)最優(yōu)解縮減成本（ReducedCost）指在資源總量不變的情況下，某一個(gè)變量在最優(yōu)解的基礎(chǔ)上增加1個(gè)單位時(shí)，目標(biāo)成本增加量。由求解結(jié)果可見，X(2)=0，其縮減成本為2，表示如果X(2)入基后，每增加1個(gè)單位，成本將增加2個(gè)單位。松弛或剩余變量（SlackorSurplus）反映了資源的利用情況。若松弛變量為0，表示該資源已耗費(fèi)完畢，若大于0，表示尚有剩余。本例2個(gè)約束的松弛變量（第2、3行）均為0，表示兩種資源均已耗費(fèi)完畢。而第1行是生產(chǎn)一個(gè)單位產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和，稱為產(chǎn)品的隱含成本。影子價(jià)格（DualPrice）的含義見節(jié)3.3。當(dāng)松弛變量為0時(shí)，影子價(jià)格大于0。目標(biāo)系數(shù)當(dāng)前值保持最優(yōu)基不變時(shí)允許增量保持最優(yōu)基不變時(shí)允許減量2/6/202321課件本章小結(jié)本章主要內(nèi)容包括線性規(guī)劃對(duì)偶問題；線性規(guī)劃原模型與對(duì)偶模型之間的結(jié)構(gòu)關(guān)系；基于線性規(guī)劃對(duì)偶問題的資源影子價(jià)格的含義；各參數(shù)變化的敏感性分析；對(duì)偶單純形法。原始規(guī)劃的解與對(duì)偶規(guī)劃的解之間有一些重要的關(guān)系，這些基本性質(zhì)統(tǒng)稱為對(duì)偶定理，包括對(duì)稱性定理，弱對(duì)偶定理，最優(yōu)性準(zhǔn)則定理，主對(duì)偶定理。對(duì)偶變量表示一個(gè)單位第i種資源的估價(jià)，這種估價(jià)不是資源的市場價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)，為區(qū)別起見，稱為影子價(jià)格（Shadowprice），線性規(guī)劃的靈敏度分析就是研究參