※ 引述《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/cn.aspx?n=bbs/Math/M.1679984942.A.D69.html ※ 编辑: illousion (104.187.117.98 美国), 03/28/2023 14:34:41