Re: [其他] 關於作業研究BIP的branch-and-bound的提
※ 引述《max12345t (馬克斯)》之銘言：
: 我有兩題問題想請問大家，因為老師真的教的很不清楚
蠻想知道你哪個學校還有教作業研究的老師是哪位
: 1.
: 題目如下：
: https://i.imgur.com/cu2US52.jpg
: 第一步驟不是要simplex把答案算出來嗎？
: 但是教科書跟老師的答案都是這樣（下圖）
: https://i.imgur.com/um306Re.jpg
: 但我跟電腦的計算機算出來答案卻是這樣（下圖）
: https://i.imgur.com/jUavFz8.jpg
Branch-and-bound (B&B)的第一步是要對原IP問題作Linear Programming Relaxation
就是把整數的限制放寬成連續 進而取得一個值 作為算法起始的上界或下界
(看原問題是max or min) 而當所有變數都是連續的時候 就成為線性規劃
怎麼求解線性規劃？就是用simplex 這就是為什麼第一步驟要用到simplex
你的題目是一個BIP, binary integer programming 也就是所有整數的限制都是二元
要求解linear programming relaxation 要把 {0,1}的限制變成 [0,1]
你在做simplex的時候少了 0<= x_j <=1 j=1~4的限制
只要在你的simplex矩陣加上 x_1 <=1, x_2<=1, x_3<=1, x_4<=1 然後去算
就會得到(5/6, 1, 0, 1)的答案
你算的因為少了x_j<=1的限制 你的x_2的值是 8/3 這個已經超出[0,1]了
完全違反問題一開始的限制 不覺得怪怪的嗎 :-P
: 2.
: 一樣是上面那題
: 我不太會在分支出去知道x1之後應該要怎麼繼續用simplex算，因為知道x1之後他限制式就變成三個變數四個限制式了
: https://i.imgur.com/DC88qG2.jpg
由於LP-relaxation的答案是 (5/6, 1, 0, 1) 但是我們知道原問題需要每個變數不是0
就是1，所以x_1的值違反了這個限制，我們從x_1分支 x_1=1 跟 x_1=0
意思就是你第一題的simplex設定中分成兩個 一個加入 x_1=1這個限制式
另外一個加入x_1=0這個限制是 兩邊再去做一次 simplex
這邊不要傻傻的把限制式加到矩陣中
一邊x_1=0在矩陣中移除掉x_1 因為x_1=0 我simplex起始矩陣根本不用管它了
另一個問題則是直接在x_1=1的情況下改寫目標式跟限制式
這樣每分支一次我就要算一次simplex？ 是的沒有錯 但是！！！
B&B算法每算完一個點要做的事情有哪些？
1. branching 分支 2. bounding 更新界限 3. Fathoming 測量評估這個點
而第3點 Fathoming的結果又有三種
1. 得到整數點 停止分支 2. 得到更好的界限 停止分支 3.此子問題無解 停止分支
麻煩複習一下這些規則就知道不需要無限的分支算simplex下去
: 3.
: 題目如下
: https://i.imgur.com/kTczzAE.jpg
: 這是我們的考古題
: 他五個變數但卻只有兩個限制式，我不管怎麼算都算不出解答圖的每個解
: https://i.imgur.com/tQHQBlE.jpg
: 想問問大家，BIP的branch-and-bound每個iteration的解到底應該怎麼算才對
: -----
: Sent from JPTT on my iPhone
有了我上面的講解 你要算第3題應該沒問題
不要再忘了加那些"放寬"的限制式們
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 104.187.117.98 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1679984942.A.D69.html
※ 編輯: illousion (104.187.117.98 美國), 03/28/2023 14:34:41
推
03/28 19:59,
1年前
, 1F
03/28 19:59, 1F
→
03/28 19:59,
1年前
, 2F
03/28 19:59, 2F
→
03/28 19:59,
1年前
, 3F
03/28 19:59, 3F
→
03/28 19:59,
1年前
, 4F
03/28 19:59, 4F
討論串 (同標題文章)
