Re: [線代] 作業研究 simplex method 一題請問
※ 引述《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://www.ptt.cc/bbs/Math/M.1587838357.A.9B2.html
→
04/26 13:41,
4年前
, 1F
04/26 13:41, 1F
推
04/26 21:47,
4年前
, 2F
04/26 21:47, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 4 篇)：