※ 引述《fish890315 (小瑜瑜;D)》之銘言： : Simplex method 就我的認知是 : (沒有很會） : 目標函數要是max(或乘-1) : 限制式都要是小於等於 : 不是的話後面要加上a像這樣 : https://i.imgur.com/VRMjv1E.jpg : 但像24題這樣 : https://i.imgur.com/JQkagfA.jpg : 這個題目應該要先把表格解到最後一步才知道是不是有alternative solution吧 : 但是這個有大約等於的限制式 : 表格上不是應該要有假設a1 a2 a3的位子嗎 : https://i.imgur.com/ykW7day.jpg : 有辦法不用到a未知數就可以直接解嗎 : 還是是什麼意思 : 先謝過看得懂我敘述的大大了 前一節 17.6 中有個 Summary of the steps to Create Tableau Form Step 3. 說遇到 ≧ 的限制式，先剪掉剩餘變數 (surplus variable) 使其變成等式 然後加上人工變數 (artificail variable) 使其還是等式， 所以你想的沒錯，的確要有 a1, a2, a3 的位子，但這些幾個變數後面會消失。 簡單解釋以下，這邊有兩個等價的觀點來了解人工變數的意義。 第一個是從使用表格法本身的條件，我們知道，使用表格法時需要下面兩個條件； a) 將每個限制式變成等式， b) 每個限制式要有能當作基底變數的變數 ≦ 的情況，透過加上剩餘變數 s，能同時滿足上面兩個需求。 ≧ 的情況比較討厭，因為剩餘變數是減掉的，因此，係數是 -1， 此時，s 不滿足基底變數係數要是 1 的條件 所以我們透過加上一個應該要是零的人工變數，想辦法讓限制式bang出一個基底變數 由於人工變數是無中生有的，所以這傢伙要是有值就糟糕了 因此，我們會在目標式加上對人工變數的懲罰項 M 來強迫讓人工變數消失為首要目標 同時，當人工變數離開基底時，你可以發現該人工變數在目標式的係數也不見了 此時，離開人工變數已經完成任務，所以下一個表格就把對應的那一行整個拿掉 這點可以從你第一張圖的下半部發現 a1 不在表格中了。 如果你接著看一下，第三個表格中連 a2 都掰了 這也是為什麼24題的解答中，最後一個表格沒有任何人工變數 a 的原因。 另一個看法是，做單形法 (simplex method) 需要有一個起始解 (initial solution)。 理想狀況下，我們可以透過剩餘變數的幫助來確保起始解會在原點。 難而，當原點是不可行解 (infeasible solution) 時，就必須透過某種手段， 來確保能找到起始解，而人工變數的引進及刪除的過程， 就是確保我們可以逐漸往可行解區域內前進。 如果把圖一那個範例的三個表格看完，就會發現 (x1, x2, x3) 的變化是 (0, 0, 0) -> (125, 0, 0) -> (250, 100, 0) 前兩個點的狀況下，a2 都還在，這也告訴我們前兩個點再原始問題中不是可行解 而且都違反了第二個限制式，這你可以檢查一下。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.169.80.112 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1587838357.A.9B2.html