Re: [線代] 作業研究 simplex method 一題請問
※ 引述《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://www.ptt.cc/bbs/Math/M.1587836723.A.F05.html
※ 編輯: illousion (50.88.209.128 美國), 04/26/2020 01:54:11
推
04/26 13:41,
5年前
, 1F
04/26 13:41, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 4 篇)：