運籌學 對偶問題概念轉(zhuǎn)換方法

關(guān)于運籌學對偶問題概念轉(zhuǎn)換方法2提綱引入對偶問題對偶問題的實際意義原問題如何轉(zhuǎn)化為對偶問題第2頁,共16頁，2024年2月25日，星期天3引入對偶問題前面的問題：自己用設備生產(chǎn)最大效益對偶問題：把設備租賃出去最低費用第3頁,共16頁，2024年2月25日，星期天4引入對偶問題對偶問題不能從字面理解為鏡像問題

更好的翻譯方法是伴隨問題第4頁,共16頁，2024年2月25日，星期天5引入對偶問題：舉例某汽車配件廠生產(chǎn)甲、乙兩種產(chǎn)品。兩種產(chǎn)品都需要在A、B兩種不同的設備上加工，每種產(chǎn)品在不同的設備上加工的工時、設備工時限制、這些產(chǎn)品銷售收入如下表：每生產(chǎn)1個甲產(chǎn)品，需要A設備工作15個單位時間，B設備工作9個單位時間。每生產(chǎn)1個乙產(chǎn)品，需要A設備工作6個單位時間，B設備工作9個單位時間。

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