運籌學(xué)對偶問題ppt課件-在線瀏覽
2025-06-20 18:35本頁面
【正文】 0 1/4 1/4 y3 1/2 15/2 0 1 1/2 3/2 σj 15/2 0 0 7/2 3/2 原問題松弛變量 原問題變量 x3 x4 x5 x1 x2 原問題最終單純形表 對偶問題最終單純形表 例 1 最大化問題檢驗數(shù)的相反數(shù)給出了對偶問題的解 原本在對偶關(guān)系中，原問題的變量對應(yīng)著對偶問題的約束條件，原問題的約束條件對應(yīng)著對偶變量。第二章 LP的對偶理論與靈敏度分析 線性規(guī)劃的對偶問題 I II 每天可用能力 設(shè)備 A（ h） 設(shè)備 B（ h） 調(diào)試工序（ h） 0 6 1 5 2 1 15 24 5 利潤（元） 2 1 問公司應(yīng)每天制造兩種家電各多少件，使獲取的利潤最大。 例 1 ???????????????0,52426155s . t .2m a x212121221xxxxxxxxxz問題 美佳公司愿意以多大的代價出讓自己所擁有的生產(chǎn)資源？ 設(shè) y1,y2和 y3分別表示出讓資源 A， B和調(diào)試工序的單價，則美佳公司同意出讓的條件將是 同意出讓生產(chǎn)產(chǎn)品 I的資源 同意出讓生產(chǎn)產(chǎn)品 II的資源 購買者希望用最少的代價獲得這些資源 ，因此 26 32 ?? yy125 321 ??? yyy321 52415m i n yyyz ???這樣得到一個新的線性規(guī)劃問題 ??????????????0,1252652415m i n32132132321yyyyyyyyyyyw稱這一問題是原來的 LP問題的 對偶線性規(guī)劃問題 或 對偶問題 ，原來的 LP問題也稱為原問題 。但 在分別添加了松弛變量和剩余變量后，也可以建立原問題變量與對偶問題變量之間的對應(yīng)關(guān)系 原問題 對偶問題 第 i個約束條件中添加的松弛變量 第 i個對偶變量 第 j個變量 第 j個約束條件中添加的松弛變量 注 上表中我們將松弛變量與剩余變量統(tǒng)稱為松弛變量 對偶問題的基本性質(zhì) ? 弱對偶性 原問題可行解的目標(biāo)函數(shù)不超過對偶問題可行解的目標(biāo)函數(shù) 弱對偶性的推論 （ 1）原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之對偶問題任一可行解的目標(biāo)函數(shù)值是原問題目標(biāo)函數(shù)值的上界。注意該推論的逆命題不成立。 ?最優(yōu)性 若原問題一個可行解目標(biāo)函數(shù)等于對偶問題的某個可行解的目標(biāo)函數(shù) ,則這兩個可行解分別是原問題和對偶問題的最優(yōu)解 ?強對偶性 若原問題和對偶問題都有可行解 ,則它們都有最優(yōu)解 ,且最優(yōu)解的目標(biāo)函數(shù)值相等 ?互補松弛性 在線性規(guī)劃問題的最優(yōu)解中 ,如果對應(yīng)某一約束條件的對偶變量值非零 ,則其對應(yīng)的約束條件取等式 。反之若一個約束條件中松弛變量非零 ,則其對應(yīng)的對偶變量為零。這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見，稱為 影子價格 。 例 1 Max z=2x1+x2 . 5x2≤15 6x1+2x2 ≤24 x1+x2 ≤5 x1,x2≥0 x2=3 6x1+2x2 =24 x1+x2 =5 最優(yōu)解 可行域 最優(yōu)目標(biāo)函數(shù)值的變化： 變到 ，增加 1/4 資源的變化：設(shè)備 B的可用時間從增加一小時 參考文獻： 李慧：資源影子價格分析與經(jīng)營管理決策，系統(tǒng)工程理論與實踐 ， 2022年 4月號， 2226 第四節(jié) 對偶單純形法 按對偶問題與原問題之間的關(guān)系，對最大化問題，在用單純形法求解原問題時，最終表不但給出了原問題的最優(yōu)解，而且其檢驗數(shù)的相反數(shù)就是對偶問題的最優(yōu)解。 ? 要求： 初始單純形表中的檢驗數(shù)滿足最優(yōu)性條件 對滿足上述條件的 LP問題，對偶單純形法的步驟是： ?旋轉(zhuǎn)運算。 ?作出初始單純形表（注意要求） ?檢查 b列的數(shù)據(jù)是否非負(fù)，若是，表中已經(jīng)給出最優(yōu)解；否則轉(zhuǎn)下一步 ?確定換出變量 ：取
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1