運(yùn)籌學(xué)——3單純形矩陣描述與改進(jìn)單純形法(參考版)
2024-08-16 17:28本頁(yè)面
【正文】 21m in xxz ????????????0,3742212121xxxxxx? 作業(yè) 4： 4. 課本 P76. (1)(5) 。 作業(yè) 3： 1. 課本 P74. (2)、 (3) ? 寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 。 c j → 1 3 0 0 C B X B b x 1 x 2 x 3 x 4 1 3 x 1 x 2 2 t 4 1 0 0 1 2/3 1/3 1/3 1/3 c j z j 0 0 5/3 2/3 57 參數(shù) b的變化分析 在表 225中進(jìn)行分析 ，當(dāng) t增大至 t≥2時(shí)， 則 b≤0；即 0≤t≤2時(shí)，最優(yōu)解為 (2?t,4,0,0)T。 解 將上述模型化為標(biāo)準(zhǔn)型 ???????????????????0,626)(03m a x43214213214321xxxxtxxxtxxxxxxxz56 c j → 1 3 0 0 C B X B b x 1 x 2 x 3 x 4 1 3 x 1 x 2 2 4 1 0 0 1 2/3 1/3 1/3 1/3 c j z j 0 0 5/3 2/3 然后計(jì)算 ?????? ???????? ??????? ????03/13/13/13/21 tttbB 令 t=0， 用單純形法迭代兩次 ， 求解的結(jié)果 ， 見(jiàn)表 224。 c j → 3+2t 5 t 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 0 3+2t x 4 x 5 x 1 12 6 4 0 0 1 2 2 0 0 3 1 1 0 0 0 1 0 c j z j 0 5 t 3 2t 0 0 t繼續(xù)增大時(shí) ， 在檢驗(yàn)數(shù)行恒有 σ 2， σ 3＜ 0， 故當(dāng) t≥ 5時(shí) ，最優(yōu)解為 (4， 0， 0， 12， 6)T。 t=5為第二臨界點(diǎn)。用單純形法迭代一步，得表 222。 t=9/7為第一臨界點(diǎn)。 將 c的變化直接反映到最終表 220中，得表 221。 當(dāng)參數(shù) t≥0時(shí)的最優(yōu)解變化 。 若在檢驗(yàn)數(shù)行首先出現(xiàn)某正值時(shí) ， 則將它對(duì)應(yīng)的變量為換入變量；用單純形法迭代一步； ? (4) 在經(jīng)迭代一步后得到的新表上 ， 令參變量 t繼續(xù)變大或變小 ， 重復(fù)步驟 (3)， 直到 b列不能再出現(xiàn)負(fù)值 ， 檢驗(yàn)數(shù)行不能再出現(xiàn)正值為止 。 先令 t=0， 用單純形法求出最優(yōu)解； ? (2) 用靈敏度分析法 ， 將參變量 t直接反映到最終表中； ? (3) 當(dāng)參變量 t連續(xù)變大或變小時(shí) ， 觀察 b列和檢驗(yàn)數(shù)行各數(shù)字的變化 。 ? 因此仍可用單純形法和對(duì)偶單純形法分析參數(shù)線性規(guī)劃問(wèn)題 。 ? 參數(shù)線性規(guī)劃研究這些參數(shù)中某一參數(shù)連續(xù)變化時(shí) ， 使最優(yōu)解發(fā)生變化的各臨界點(diǎn)的值 。 321 422m i n xxxz ????????????????????無(wú)約束321321321321,0,534332243xxxxxxxxxxxx? ?試用對(duì)偶單純形法求解下列線性規(guī)劃問(wèn)題。 ?對(duì)偶單純形法的 主要局限性 ：對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始基。 ?(2) 當(dāng) 變量多于約束條件 ，對(duì)這樣的線性規(guī)劃問(wèn)題用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此 對(duì)變量較少，而約束條件很多的線性規(guī)劃問(wèn)題，可先將它變換成對(duì)偶問(wèn)題 ，然后用對(duì)偶單純形法求解。 故重復(fù)上述迭代步驟，得表 2 8 。按單純形法計(jì)算步驟進(jìn)行迭代，得表 27。 12234,22m i n ?????????? ???????故 x1為換入變量。 按上述對(duì)偶單純形法計(jì)算步驟 (2)， 即按 min｛ (B1b)i｜ (B1b)i＜ 0＝ (B1b)l對(duì)應(yīng)的基變量 xi為換出變量 。 43 ? 換出變量的確定： ? 換入變量的確定：按上述對(duì)偶單純形法計(jì)算步驟 (3)，即在單純形表中檢查 xl所在行的各系數(shù) α lj(j=1,2,… ， n)。 c j → 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 0 x 4 x 5 3 4 1 [ 2] 2 1 1 3 1 0 0 1 c j z j 2 3 4 0 0 從表 26看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問(wèn)題的解是可行解。 重復(fù)步驟 (1)～ (4)。若存在 αlj＜ 0 (j=1,2,… ， n), 計(jì)算 lkkkljljjjj azcaazc ????????????? 0m i n?40 按 θ規(guī)則所對(duì)應(yīng)的列的非基變量 xk為換入變量，這樣才能保持得到的對(duì)偶問(wèn)題解仍為可行解。在單純形表中檢查 xl所在行的各系數(shù)αlj(j=1,2,… ， n)。 (2) 確定 換出變量 。停止計(jì)算。 39 對(duì)偶單純形法的計(jì)算步驟： (1) 把線性規(guī)劃轉(zhuǎn)化為 “近似標(biāo)準(zhǔn)形式” ，列出初始單純形表。 38 c j → 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 0 x 4 x 5 3 4 1 [ 2] 2 1 1 3 1 0 0 1 c j z j 2 3 4 0 0 從該表看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問(wèn)題的解是可行解。 即原問(wèn)題與對(duì)偶問(wèn)題都是最優(yōu)解 。 37 第 6節(jié) 對(duì) 偶單純形法 ? 在單純形表中進(jìn)行迭代時(shí) ， 在 b列中得到的是原問(wèn)題的基可行解 ， 而在檢驗(yàn)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1