※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1587836723.A.F05.html ※ 编辑: illousion (50.88.209.128 美国), 04/26/2020 01:54:11