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

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

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

行解Yes2/6/202310課件3.2對偶單純形法簡介【例3.2】用對偶單純形法解解標(biāo)準(zhǔn)化初始單純形表第1次迭代第2次迭代最優(yōu)解最優(yōu)值202/6/202311課件3.3影子價格導(dǎo)入案例原問題的解如圖.對偶問題的解2/6/202313課件3.3影子價格原問題bi代表第i種資源擁有量yi代表第i種資源的估價，該估價并非市價格，而是在生產(chǎn)中的單位貢獻(xiàn)所做的估價,稱為影子價格。其含義：（1）資源的市場價格由供求關(guān)系決定，而它的影子價格則有賴于資源的利用情況。（2）影子價格是一種邊際價格。（3）資源的影子價格實(shí)際上又是一種機(jī)會成本。（4）當(dāng)影子價格為0時，表明該種資源未得到充分利用；當(dāng)影子價格不為0時，表明該種資源已耗費(fèi)完畢。（5）在一個大公司內(nèi)部，可借助資源的影子價格確定一些內(nèi)部結(jié)算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。對偶問題2/6/202314課件3.4靈敏度分析線性規(guī)劃的各個參數(shù)A，C，b往往是根據(jù)統(tǒng)計(jì)數(shù)據(jù)測算的，不可能完全準(zhǔn)確，而且隨著實(shí)際情況變化。靈敏度分析是指各參數(shù)變化對最優(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增加一個新變量的分析2/6/202318課件3.4.3增加一個新變量的分析在操作上：由若大于0應(yīng)安排生產(chǎn)?！纠?.6】在例3.4中增加一個新產(chǎn)品是否可行。其消耗系數(shù)列向量p6=（3/2，1，1/2）及價值系數(shù)c6=3.2/6/202319課件3.5如何看計(jì)算機(jī)求解報告【例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）指在資源總量不變的情況下，某一個變量在最優(yōu)解的基礎(chǔ)上增加1個單位時，目標(biāo)成本增加量。由求解結(jié)果可見，X(2)=0，其縮減成本為2，表示如果X(2)入基后，每增加1個單位，成本將增加2個單位。松弛或剩余變量（SlackorSurplus）反映了資源的利用情況。若松弛變量為0，表示該資源已耗費(fèi)完畢，若大于0，表示尚有剩余。本例2個約束的松弛變量（第2、3行）均為0，表示兩種資源均已耗費(fèi)完畢。而第1行是生產(chǎn)一個單位產(chǎn)品所消耗的各項(xiàng)資源的影子價格的總和，稱為產(chǎn)品的隱含成本。影子價格（DualPrice）的含義見節(jié)3.3。當(dāng)松弛變量為0時，影子價格大于0。目標(biāo)系數(shù)當(dāng)前值保持最優(yōu)基不變時允許增量保持最優(yōu)基不變時允許減量2/6/202321課件本章小結(jié)本章主要內(nèi)容包括線性規(guī)劃對偶問題；線性規(guī)劃原模型與對偶模型之間的結(jié)構(gòu)關(guān)系；基于線性規(guī)劃對偶問題的資源影子價格的含義；各參數(shù)變化的敏感性分析；對偶單純形法。原始規(guī)劃的解與對偶規(guī)劃的解之間有一些重要的關(guān)系，這些基本性質(zhì)統(tǒng)稱為對偶定理，包括對稱性定理，弱對偶定理，最優(yōu)性準(zhǔn)則定理，主對偶定理。對偶變量表示一個單位第i種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價，為區(qū)別起見，稱為影子價格（Shadowprice），線性規(guī)劃的靈敏度分析就是研究參