運(yùn)籌學(xué)-8對(duì)偶問題概念+轉(zhuǎn)換方法

Lec.8OperationalResearch

對(duì)偶問題dualZHUTongChang’anUniversityE-mail:zhutongtraffic@Oct.2012HomeHome提綱引入對(duì)偶問題對(duì)偶問題的實(shí)際意義原問題如何轉(zhuǎn)化為對(duì)偶問題2引入對(duì)偶問題前面的問題：自己用設(shè)備生產(chǎn)最大效益對(duì)偶問題：把設(shè)備租賃出去最低費(fèi)用3引入對(duì)偶問題對(duì)偶問題不能從字面理解為鏡像問題

更好的翻譯方法是伴隨問題4引入對(duì)偶問題：舉例某汽車配件廠生產(chǎn)甲、乙兩種產(chǎn)品。兩種產(chǎn)品都需要在A、B兩種不同的設(shè)備上加工，每種產(chǎn)品在不同的設(shè)備上加工的工時(shí)、設(shè)備工時(shí)限制、這些產(chǎn)品銷售收入如下表：每生產(chǎn)1個(gè)甲產(chǎn)品，需要A設(shè)備工作15個(gè)單位時(shí)間，B設(shè)備工作9個(gè)單位時(shí)間。每生產(chǎn)1個(gè)乙產(chǎn)品，需要A設(shè)備工作6個(gè)單位時(shí)間，B設(shè)備工作9個(gè)單位時(shí)間。

1個(gè)甲產(chǎn)品利潤(rùn)200元/個(gè)；1個(gè)乙產(chǎn)品利潤(rùn)150元/個(gè)A設(shè)備最多工作540小時(shí);B設(shè)備最多工作405小時(shí)甲乙有效工時(shí)A156540B99405利潤(rùn)（元/個(gè)）2001505引入對(duì)偶問題：舉例某汽車配件廠生產(chǎn)甲、乙兩種產(chǎn)品。兩種產(chǎn)品都需要在A、B兩種不同的設(shè)備上加工，每種產(chǎn)品在不同的設(shè)備上加工的工時(shí)、設(shè)備工時(shí)限制、這些產(chǎn)品銷售收入如下表：甲乙有效工時(shí)A156540B99405利潤(rùn)（元/個(gè)）200150解為（30,15,0,0），最優(yōu)值為82506引入對(duì)偶問題：舉例第一個(gè)問題：生產(chǎn)問題另一個(gè)問題：出租問題將A、B設(shè)備出租，在合理的利潤(rùn)條件下，消耗的資源至少是？（1）變量：y1、y2為A、B兩種設(shè)備對(duì)外加工時(shí)，單位工時(shí)的價(jià)格。（2）約束條件（生產(chǎn)者接受）：“合理”的利潤(rùn)條件是指，如果把A、B設(shè)備租出去生產(chǎn)甲，所得收入不應(yīng)少于200元；把A、B設(shè)備租出去生產(chǎn)乙，所得收入不應(yīng)小于150元。（3）目標(biāo)函數(shù)（收購(gòu)方意愿）：要租A、B設(shè)備，收購(gòu)費(fèi)用最少是多少。解為（50/9，350/27，0，0），值為82507對(duì)偶問題的實(shí)際意義：影子價(jià)格Y*為影子價(jià)格，用于估計(jì)設(shè)備資源轉(zhuǎn)讓的費(fèi)用。當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，應(yīng)該買進(jìn)當(dāng)某種資源的市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，可以賣出8對(duì)偶問題的形式總結(jié)：優(yōu)化目標(biāo)大變小，常數(shù)－價(jià)值互相換，系數(shù)矩陣要轉(zhuǎn)置，約束－變量捉對(duì)變。9對(duì)偶問題的形式原問題對(duì)偶問題原目標(biāo)函數(shù)maxZ對(duì)偶目標(biāo)函數(shù)minw原約束條件變量個(gè)數(shù)m個(gè)第i個(gè)約束≤≥＝對(duì)偶變量變量個(gè)數(shù)m個(gè)第i個(gè)約束yi≥0yi≤0yi自由變量原變量變量個(gè)數(shù)n個(gè)第j個(gè)約束Xj≥0Xj≤0Xj自由變量對(duì)偶約束條件變量個(gè)數(shù)n個(gè)第j個(gè)約束≥≤＝優(yōu)化目標(biāo)大變小，常數(shù)－價(jià)值互相換，系數(shù)