對偶問題與靈敏度分析-在線瀏覽
2025-07-18 07:19本頁面
【正文】 x2+3x3+x4+x5≥3 xj ≥0,j=1,… ,5 Max w=4y1+3y2 . y1+2y2≤2 y12y2 ≤3 2y1+3y2 ≤5 y1+y2 ≤2 3y1+y2 ≤3 y1,y2 ≥0 對偶問題 y1*=4/5,y2*=3/5 對偶問題的最優(yōu)解 4/52*3/5=2/53 約束條件是松的 也即 ys0,由互補松弛定理知 X(0)ys=0 所以 x2=0 同理， x3=0,x4=0 又 y1*0,而 Y(0)xs=0, 知 xs＝ 0，即原問題第一個約束取等式 同理，第 2個約束也取等式 定理 6 若原問題最優(yōu)解存在，則原問題最優(yōu)單純形表的檢驗數(shù)行中， 松弛變量的檢驗數(shù) 和 剩余變量的檢驗數(shù)的相反數(shù) 即為對偶問題最優(yōu)解 對偶最優(yōu)解的經(jīng)濟含義 —— 影子價格 由對偶定理 ??????miiinjjj ybxcZ1*1**求 z*對 bi的偏導(dǎo)數(shù) **iiybz ???所以對偶最優(yōu)解為原問題各資源的 影子價格 影子價格非資源的市場價格，而是指系統(tǒng) 達(dá)到 最優(yōu)狀態(tài)時 ，資源的單位變化引起目標(biāo)最優(yōu)值的變化 對偶單純形法是求解線性規(guī)劃的另一的基本方法。即： Min w=360y1+200y2+300y3 . 9y1+4y2+3y3≥70 4y1+5y2+10y3≥120 y1,y2≥0 該線性規(guī)劃問題與 原問題 互為 對偶問題 m a x z = 7 0 x 1 + 1 2 0 x 2s . t . 9 x 1 ＋ 4x 2 ≤ 3 6 04x 1 + 5 x 2 ≤ 2 0 03x 1 + 1 0 x 2 ≤ 300x 1 ,x 2 ≥ 0對偶的定義 (LP) Max z = CX ? (DP) Min w = Yb . AX ≤ b . YA ≥ C X ≥ 0 Y ≥ 0 若一個問題的某約束為等式， 那么對應(yīng)的對偶問題的相應(yīng)變量無非負(fù)限制； 反之， 若一個問題的某變量無非負(fù)限制， 那么對應(yīng)的對偶問題的相應(yīng)約束為等式。運籌學(xué) —— 第 3章 對偶問題與靈敏度分析 湖南大學(xué)工商管理學(xué)院 本講內(nèi)容 ? 什么是對偶問題 ? 單純形法的矩陣描述 ? 對偶問題的性質(zhì) ? 線性規(guī)劃的靈敏度分析 什么是對偶問題？ 對偶問題的提出 考慮上一講的 生產(chǎn)計劃問題 ，若設(shè)備和原料都用于對外加工，工廠收取加工費。試問：該廠設(shè)備工時、勞動力和原料該如何定價？ P需求供給Q均衡點供給 需求函數(shù)顯然，工廠給這些生產(chǎn)要素定價，既要 保證自己的利益 ，又要使自己的價格 具有競爭力 價格越高越好 價格越低 越好 一個合理的定價是：收取的加工費不能低于自己生產(chǎn)所得收益，在此前提下使總加工費盡量小。 原問題（或?qū)ε紗栴}） 對偶問題（或原問題） 目標(biāo)函數(shù) max 目標(biāo)函數(shù) min 約 束 條 件 m個 m個 變 量 ≤ ≥0 ≥ ≤0 = 無約束 變 量 n個 n個 約 束 條 件 ≥0 ≥ ≤0 ≤ 無約束 = 約束條件右端項 目標(biāo)函數(shù)變量的系數(shù) 目標(biāo)函數(shù)變量的系數(shù) 約束條件右端項 建立對偶問題的規(guī)則 約束條件 變量 右端項 價值系數(shù) 對于上表，特別把握以下要點： max min 求 max的對偶問題時， 變量 反號 求 min的對偶問題時， 約束 反號 ＝ 無限制 例 1： 寫出下列規(guī)劃問題的對偶問題 Max z=2x1
法律信息相關(guān)推薦
鄂ICP備17016276號-1