對偶理論ppt課件(編輯修改稿)
2025-05-26 00:32 本頁面
【文章內容簡介】 1 zy1y2l1l234定理 4：互補松馳定理35證明：（必要性）36證明：（充分性） 37定理 4’ ：互補松馳定理 (非對稱形式）38例 6 考慮下面問題39解 :則，40定義對偶問題的經濟學解釋：影子價格含義考慮在最優(yōu)解處 ,右端項 bi的微小變動對目標函數(shù)值的影響 .41?若把原問題的約束條件看成是廣義的資源約束 ,則右端項的值表示每種資源的可用量 .?對偶解的經濟含義 :資源的單位改變量引起目標函數(shù)值的增加量 .?通常稱對偶解為影子價格 .?影子價格的大小客觀地反映了資源在系統(tǒng)內的稀缺程度 .資源的影子價格越高 ,說明資源在系統(tǒng)內越稀缺 ,而增加該資源的供應量對系統(tǒng)目標函數(shù)值貢獻越大 .42? 木門 木窗? 木工 4小時 3小時 120小時 /日? 油漆工 2小時 1小時 50小時 /日? 收入 56 30? 解：設該車間每日安排 x1 x2 x3 x4? 生產木門 x1扇，木 窗 x2。 x3 4 3 1 0 120? max z=56 x1 +30 x2 x4 2 1 0 1 50? . 4 x1 +3 x2≤120 56 30 0 0 0? 2 x1 + x2 ≤50 x3 0 1 1 2 20? x1 x2 ≥0 x1 1 1/2 0 1/2 25? 0 2 0 28 1400? x2 0 1 1 2 20? x1 0 0 1/2 1/2 15? 0 0 2 24 1440對偶問題的解為 :w*=(2, 24)43 （ 2）告訴管理者花多大代價購買進資源或賣出資源是合適的 影子價格的作用（ 1）告訴管理者增加何種資源對企業(yè)更有利 （ 3） 為新產品定價提供依據44對偶單純形法?定義：設 x(0)是 (L)的一個基本解（不一定是可行解），它對應的矩陣為 B， 記w=cBB1，若 w是 (L)的對偶問題的可行解，即對任意的 j, wPjcj ≤0， 則稱 x(0)為原問題的 對偶可行的基本解 。?結論：當對偶可行的基本解是原問題的可行解時，由于判別數(shù) ≤0， 因此，它就是原問題的最優(yōu)解。45所以， x(0)為對偶可行的基本解。 46?基本思想：?從原問題的一個對偶可行的基本解出發(fā)；?求改進的對偶可行的基本解：每個對偶可行的基本解 x=(xBT,0)T對應一個對偶問題的可行解 w=cBB1， 相應的對偶問題的目標函數(shù)值為 wb=cBB1b， 所謂改進的對偶可行的基本解，是指對于原問題的這個基本解，相應的對偶問題的目標函數(shù)值 wb有改進（選擇離基變量和進基變量，進行主元消去）；?當?shù)玫降膶ε伎尚械幕窘馐窃瓎栴}的可行解時，就達到最優(yōu)解。47?與原單純形法的區(qū)別：?原單純形法保持原問題的可行性，對偶單純形法保持所有檢驗數(shù) wPjcj ≤0， 即保持對偶問題的可行性。?特點：先選擇出基變量，再選擇進基變 量。48換基迭代1. 化標準型 ,建立初始單純形表回到第 2步(若所有 yrj≥0,則該 LP無可行解）步驟：495051x1 x2 x3 x4 x53 1 1 1 01 4 1 0
教學課件相關推薦
鄂ICP備17016276號-1