運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格-文庫吧資料
2025-05-22 22:18本頁面
【正文】 5 0 [2/3] 1/3 1 CjZj 15 0 1 4 0 24 y2 1/4 5 y3 1/2 5/4 1 0 1/ 4 1/4 15/2 0 1 1/2 3/2 CjZj 15/2 0 0 7/2 3/2 運(yùn)籌學(xué)教程 對偶單純形法求解線性規(guī)劃問題時，當(dāng)使用約束條件為“大于等于”，不必引進(jìn)人工變量，計(jì)算簡化。?????????????????????????rsssrjjjrjrsssrsrjjjrjrjrsssrjjjrjssrsrjjjjjazcazcaazcaazcaaazcazcazcaazczc????，主元素，；，分析：運(yùn)籌學(xué)教程 ?按主元素進(jìn)行換基迭代 ， 將主元素變成1， 主元列變成單位向量 ， 得到新的單純形表 。 如果 rsssrjrjjjj azcaazc ??????????????? 0m i n?（最小比值原則） ，則選 為換入變量，相應(yīng)的列為 主元列 ，主元行和主元列交叉處的元素 為主元素 。 bi≥ 0—— 原始單純形法； bi至少一個元素 0,另外處理； (原問題 、 對偶問題均無可行解， 引進(jìn)人工變量 ) 檢驗(yàn)數(shù)全部 ≤ 0 （ 非基變量檢驗(yàn)數(shù) 0） 至少一個檢驗(yàn)數(shù) 0 運(yùn)籌學(xué)教程 ? 基變換： 先確定換出變量 —— bi中的負(fù)元素 （ 一般選最小的負(fù)元素 ） 對應(yīng)的基變量 出基 ； 即 ? ? 出基，則選 riiir xbbb ,0m i n ??相應(yīng)的行 為主元行 。 運(yùn)籌學(xué)教程 二 、 對偶單純形法的計(jì)算步驟 ： ① 建立初始單純形表 ， 計(jì)算檢驗(yàn)數(shù)行 。 對偶單純形法思想： 換個角度考慮 LP求解過程 ： 保持 對偶可行的前提下 （ 檢驗(yàn)數(shù)行保持 ≤0） ， 通過逐步迭代 實(shí)現(xiàn)原問題可行 （ b列 ≥0， 從非可行解變成可行解 ） 。 補(bǔ)充定理 B是線性規(guī)劃的最優(yōu)基 的 充要條件 是 ， B是可行基 ， 同時也是對偶可行基 。 運(yùn)籌學(xué)教程
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1