對偶理論ppt課件(參考版)
2025-05-02 00:32本頁面
【正文】 73計算步驟7475限定原始問題目標函數值對偶問題可行解為 w時所有的 wpjcj對偶問題函數值 f=wb限定原始問題的判別數76用原始 對偶算法解下列問題解：對偶問題為77限定原始問題為：78△ △794230218005235103123012112121321yyyyxxx △ △ △804230212021012111023012112221321yxyyxxx △ △ △81△ △ △ △△ △△△１82解：它的對偶規(guī)劃是83限定原始問題為84△ △ △85△ △ △△ △ △8687△ △△ △ △8889。 66原始 對偶算法?基本思想：?從對偶問題的一個可行解開始，同時計算原問題和對偶問題，試圖求出原問題的滿足互補松弛條件的可行解。48換基迭代1. 化標準型 ,建立初始單純形表回到第 2步(若所有 yrj≥0,則該 LP無可行解）步驟：495051x1 x2 x3 x4 x53 1 1 1 01 4 1 0 11 1 1 0 0x4x5120413/4 0 3/4 1 1/41/4 1 1/4 0 1/45/4 0 3/4 0 1/4x4x21/21/21/213/41 0 3/13 4/13 1/130 1 4/13 1/13 3/130 0 6/13 5/13 2/13x1x22/137/139/1352用對偶單純形法求解下列 LP問題解：原問題變形為53x1 x2 x3 x4 x5 x61 1 1 1 0 01 1 2 0 1 00 1 1 0 0 1x4x5x61 2 3 0 0 048201 1 1 1 0 00 2 1 1 1 00 1 1 0 0 1x1x5x60 3 2 1 0 0442411 0 0 1 0 10 0 3 1 1 20 1 1 0 0 1x1x5x20 0 5 1 0 36021054關于初始對偶可行的基本解? min cx? . Ax=b? x ≥0?若初始對偶可行的基本解不易直接得到，則解一個擴充問題，通過這個問題的求解，給出原問題的解答。47?與原單純形法的區(qū)別：?原單純形法保持原問題的可行性，對偶單純形法保持所有檢驗
教學課件相關推薦
鄂ICP備17016276號-1