※ 引述《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://webptt.com/m.aspx?n=bbs/Math/M.1679984942.A.D69.html ※ 編輯: illousion (104.187.117.98 美國), 03/28/2023 14:34:41