※ 引述《yi0313ru (Liver)》之铭言： : 大家好 小妹有三题线性规划实在解不出 : 每题赠第一位正解出的高手税前1,000P聊表心意 共3,000P : 希望在星期三以前 红包将於星期六统一赠出 : 谢谢各位 跪求前辈相助 : 3. https://imgur.com/CpapWmL (本文可能有许多运算排版，建议手机使用者横向阅读) 2020/05/07 更新 感谢 illousion大 所提出的问题，以下错误均已修正～ ---------------------------------------------------------------------------- 我以为第三题被解掉了，所以就没仔细看，原来解错了吗XD？ 不确定有没有理解错，有错请网友们多多指教XD 直接见图，我的单形法是用 Excel 跑的 https://imgur.com/1BTV5zU 首先因为要周休二日，所以只有七种排班 假设变数 Xi 为第 i 种排班所需要的人数，i = 1, 2, 3, 4, 5, 6, 7 排班与星期数对应的储存格，如果是 1 则表示那一天要上班，0 则表示休假 依照此逻辑完成整张表单，该星期栏位我命名为 day_j, j = 1, 2, ..., 7 再来先看第 I 直栏位，储存格 I2:I8 放的就是 X1~X7，我整个栏位命名为 value 最後 o.f. 在 I9 加总求最小，I9 = SUM(I2:I8) 接着看第十横列，放的数值是原本题目中对於每一天的人力需求，我这里设为"下限" 也就是每一天至少需要有那麽多人在上班，f.c.'s 对应到 >= 最後看第九横列，是 I2:I8 与每一个星期数排班的规则做阵列乘法的加总 举例看星期一，上班的人来自排班 1, 4, 5, 6, 7 的人，总数要大於或等於 B9 {=SUM(value*day_1)}，其余天数的情况以此类推 最後来看规划求解参数框，目标在 I9 栏位 https://imgur.com/6yIoPze 变数储存格就是刚刚的 value 下面的 f.c.'s 就是上述刚说的，不过因为最後的单位是"人数" 所以我多把每个变数调成 整数 (int) 求解 线性规划的问题完整写出来就是 o.f. min Z = X1 + X2 + X3 + X4 + X5 + X6 + X7 s.t. X1 + X4 + X5 + X6 + X7 >= 12 X1 + X2 + X5 + X6 + X7 >= 8 X1 + X2 + X3 + X6 + X7 >= 6 X1 + X2 + X3 + X4 + X7 >= 9 X1 + X2 + X3 + X4 + X5 >= 10 X2 + X3 + X4 + X5 + X6 >= 12 X3 + X4 + X5 + X6 + X7 >= 10 n.c.'s X1, X2, X3, X4, X5, X6, X7 are nonnegative integers 最佳解为 (X1, X2, X3, X4, X5, X6, X7) = (1, 2, 0, 6, 1, 3, 1) 总共最小值 14 人，且其星期三、四、日均高於下限一人，其余刚好 最後是，我们可以看到排班三不需要有人上班，如果题目额外要求每排班都有人(Xi>0) 就直接做转换 Xi' = Xi - 1 >= 0，最後把所有的 f.c.'s 换掉求完之後再换回去 我另外换了一个线性规划的 solver 来求解，有弄出许多不同的解，但最小值依然为 14 以下举其中三组为例： (X1, X2, X3, X4, X5, X6, X7) = (1, 1, 1, 5, 3, 2, 1) 其星期五高於下限一人、星期日高於下限两人，其余刚好 (X1, X2, X3, X4, X5, X6, X7) = (2, 2, 0, 5, 3, 2, 0) 其星期二高於下限一人、星期五高於下限两人，其余刚好 (X1, X2, X3, X4, X5, X6, X7) = (０, 2, 0, 6, 2, 2, 2) 其星期四高於下限一人、星期日高於下限两人，其余刚好 如果要仔细研究解在高维度 多胞体 (polytope) 上的实际行为 你可以另外去看这些 可行基解 (Basic Feasible solution) 的 defining equations 用每一个限制式的 指标变数 (对应的人工变数 减去 对应的多余变数) 来看是否为零 以上作法请 原PO 参考，有错的话也请网友们提出讨论～ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 60.250.230.253 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1588775223.A.F9D.html ※ 编辑: cuylerLin (60.250.230.253 台湾), 05/08/2020 20:41:15