※ 引述《fish890315 (小瑜瑜;D)》之銘言： : Simplex method 就我的認知是 : (沒有很會） : 目標函數要是max(或乘-1) : 限制式都要是小於等於 : 不是的話後面要加上a像這樣 : https://i.imgur.com/VRMjv1E.jpg 目標是 min 或 max 都可以 只要記得 reduced cost c_j - z_j 的計算方式跟選取進入基底的準則要變就好 建議是只記一種規則：max的時候 reduced cost怎麼選 然後遇到 min的問題時 直接目標式乘-1 轉成max 限制是<=的原因是線性規劃的應用通常是實際問題 只考慮非負的解 （記得你的非負限制式 x>=0嗎） 而simplex method的第一步就是要創造起始可行解 給一個不違反任何限制的起點 通常會是 0 這是為什麼對於每一條限制式要加上額外變數的原因 額外變數又可以分成兩類：slack/surplus 還有 artificial variable 如果是 <= ， 加上 係數為正一的s 就可 比方說2x1+3x2 <= 10 變成 2x1+3x2+s1 = 10 如果是 >= 則加上係數為負一的s 比方說 5x1+6x2 >= 18 變成 5x1+6x2 -s2 = 18 slack/surplus代表為了要讓不等式變成等式要補上的差額 所以起始表格設定所有非基變數(Non-basic variables)為零 用上面例子來看 令x1, x2都=0 可以得到起始解 s1 = 10 and s2 = -18 咦？？？不是說好非負嗎？所以對於>=的不等式要再加入一個額外變數讓起始解為正 5x1 + 6x2 -s2 + a1 = 18 然後讓非基變數x1, x2, s2 = 0 可以得到起始解 s1 = 10, a1 = 18 然後就可以開始做迭代 看讓哪些非基變數進入基底把 s1 or a1取代掉 達到max的目標 同樣的方法也可以處理嚴格等式的限制式 在這個例子中 起始解(x1,x2,s1,s2,a1) =(0,0,10,0,18) 但是對應回原問題只有兩個變數可以看到起點是(x1,x2) = (0,0) 增加了這些額外的變數 我們保證simplex總是從0開始移動找尋更好的解 這裡跟slack/surplus的意義不太一樣的是 artificial variable的目的只是純粹 有起始可行解 所以我們不喜歡他 才會給他在目標式這麼大的懲罰係數M 使用M的Simplexe Method 叫做 Big-M Method 大M法 我不喜歡 因為計算M很麻煩 後面你會學到Two-phase雙階法 第一階段找到可行解後就可以把 a都丟掉 目標係數也不會有M的計算 : 但像24題這樣 : https://i.imgur.com/JQkagfA.jpg : 這個題目應該要先把表格解到最後一步才知道是不是有alternative solution吧 : 但是這個有大約等於的限制式 : 表格上不是應該要有假設a1 a2 a3的位子嗎 : https://i.imgur.com/ykW7day.jpg : 有辦法不用到a未知數就可以直接解嗎 首先要理解什麼時候有alternative solution Simplex 停止的準則是什麼？以你24題的例子來看 是否非基變數的reduced cost c_j - z_j 都是負數的時候就停止 假設是正數k的話 代表可以增加一單位的該非基變數 可以給目前的目標式利潤k 所以應該要置換基底 如果這時候有一個非基變數的rc 是 0 代表就算這個非基變數進入基底 也不會改變目前的目標式 因為利潤是0 就算置換也沒有關係 置換後的解 是alternative solution 如果是兩維問題 用畫圖的可以看出alternative solution 畫出可行解區域 看到有兩個角點跟目標式函數的線重合 那他們都是得到同個目標式利潤的alternative solution 但如果是高維問題 沒辦法畫圖 三維都很難畫了 我是覺得應該是沒有其他的方法不做simplex表格就可以偵測 要好好學習怎麼用表格偵測線性規劃的特殊情況喔 1. alternative solution 2. unboundedness 3. degeneracy （這個大學部不一定會談到） : 還是是什麼意思 : 先謝過看得懂我敘述的大大了 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 50.88.209.128 (美國) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1587836723.A.F05.html ※ 編輯: illousion (50.88.209.128 美國), 04/26/2020 01:54:11