※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1587838357.A.9B2.html