運籌學——3單純形矩陣描述與改進單純形法(編輯修改稿)
2024-09-01 17:28 本頁面
【文章內(nèi)容簡介】 2121684100214210112//bB29 第 2步計算結(jié)束后的結(jié)果 ? ?? ?? ?? ? ? ?),(),(C,CC。x,xX。x,x,xX。P,P,PBNBTNTB003022222532412412?????價值系數(shù)非基變量基變量基30 第 3步： 計算非基變量（ x3, x5）的檢驗數(shù) ? ?? ?? ? ? ?換入變量正檢驗數(shù)對應注意：535322124121000014100314210130200222x,x/,//),(,)P,PN(NBCCBNN????????????????????????????????31 確定換出變量 ? ?? ?4441328212051251212x/,/m i nPBPBbBm i nii對應????????????????????????32 新的基 ? ?主元素的系數(shù)向量是換入變量??????????? ???????????????????????????4/122/11004/1002142/101。,51252513PBxPPPB基變換： 33 計算 B的逆矩陣 ?????????????? ???????????????????18/1002/1004/118/12/14/133 E構造?????????????????????????????????????????08121121204104100214210118100210041112313/////////BEB34 計算非基變量的檢驗數(shù) ? ?? ?? ?已無正檢驗數(shù)注意：8/1,2/301000108/12/112/1204/10)3,0,2(0,0,433313333???????????????????????????????PPNNBCCBNN?35 得到最優(yōu)解： ?????????????????????????????????????244128/12/1162/1284/1013251*bBxxxX? ? 1424430213 ????????????? ? ,bBCz B*?目標函數(shù)的最優(yōu)值為： 36 改進單純形法步驟 1. 求線性規(guī)劃的標準形式，確定 1000000 , BBCCXX NBNB 及其逆矩陣和初始基。確定，從而計算，）求（。規(guī)則求出換出變量，根據(jù)，計算可得）從（。，確定換入變量，從而求出）求（11111111111110k10010010000010,321 2.NBNBlkBNNCCXXbBNBBExbBPBNBxNBCCNB???????? ????3. 重復第 2步（下標加 1），直至求出最優(yōu)解。 37 第 6節(jié) 對 偶單純形法 ? 在單純形表中進行迭代時 ， 在 b列中得到的是原問題的基可行解 ， 而在檢驗數(shù)行得到的是對偶問題的 基解 。 ? 通過逐步迭代 ， 當在檢驗數(shù)行得到對偶問題的解也是基可行解時 ， 已得到最優(yōu)解 。 即原問題與對偶問題都是最優(yōu)解 。 ? 根據(jù)對偶問題的對稱性 ， 可以這樣考慮：若保持對偶問題的解是基可行解 ， 即 cj?CBB1Pj≤0， 而原問題在非可行解的基礎上 ， 通過逐步迭代達到基可行解 ， 這樣也得到最優(yōu)解 。 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 從該表看到，檢驗數(shù)行對應的對偶問題的解是可行解。 因 b列數(shù)字為負，故需進行迭代運算。 39 對偶單純形法的計算步驟： (1) 把線性規(guī)劃轉(zhuǎn)化為 “近似標準形式” ，列出初始單純形表。檢查 b列的數(shù)字，若都為非負，檢驗數(shù)都為非正，則已得到最優(yōu)解。停止計算。若檢查 b列的數(shù)字時，至少還有一個負分量，檢驗數(shù)保持非正，那么進行以下計算。 (2) 確定 換出變量 。按 min｛ (B1b)i｜ (B1b)i＜ 0}＝ (B1b)l對應的基變量 xi為換出變量 (3) 確定 換入變量 。在單純形表中檢查 xl所在行的各系數(shù)αlj(j=1,2,… ， n)。若 所有 αlj≥0，則無可行解 ，停止 計算。若存在 αlj＜ 0 (j=1,2,… ， n), 計算 lkkkljljjjj azcaazc ????????????? 0m i n?40 按 θ規(guī)則所對應的列的非基變量 xk為換入變量，這樣才能保持得到的對偶問題解仍為可行解。 (4) 以 αlk為主元素 ， 按原單純形法在表中進行迭代運算 ， 得到新的計算表 。
公司管理相關推薦
鄂ICP備17016276號-1