※ 引述《cuylerLin (cuylerLin)》之铭言： : ※ 引述《yi0313ru (Liver)》之铭言： : : 大家好 小妹有三题线性规划实在解不出 : : 每题赠第一位正解出的高手税前1,000P聊表心意 共3,000P : : 希望在星期三以前 红包将於星期六统一赠出 : : 谢谢各位 跪求前辈相助 : : 3. https://imgur.com/CpapWmL : 我以为第三题被解掉了，所以就没仔细看，原来解错了吗XD？ : 不确定有没有理解错，有错请网友们多多指教XD : 直接见图，我的单形法是用 Excel 跑的 : https://imgur.com/o6Kkp5F : 首先因为要周休二日，所以只有六种排班 : 假设变数 Xi 为第 i 种排班所需要的人数，i = 1, 2, 3, 4, 5, 6 : 排班与星期数对应的储存格，如果是 1 则表示那一天要上班，0 则表示休假 : 依照此逻辑完成整张表单，该星期栏位我命名为 day_j, j = 1, 2, ..., 7 : 再来先看第 I 直栏位，储存格 I2:I7 放的就是 X1~X6，我整个取名为 value : 最後 o.f. 在 I8 加总求最小，I8 = SUM(I2:I7) : 接着看第九横列，放的数值是原本题目中对於每一天的人力需求，我这里设为"下限" : 也就是每一天至少需要有那麽多人在上班，f.c.'s 对应到 >= : 最後看第八横列，是 I2:I7 与每一个星期数排班的规则做阵列乘法的加总 : 举例看星期一，上班的人来自排班 1, 4, 5, 6 的人，总数要大於或等於 : B8 {=SUM(value*day_1)}，其余天数的情况以此类推 : 最後来看规划求解参数框，目标在 I8 栏位 : https://imgur.com/CLryQox : 变数储存格就是刚刚的 value : 下面的 f.c.'s 就是上述刚说的，不过因为最後的单位是"人数" : 所以我多把每个变数调成 整数 (int) 求解 : 线性规划的问题完整写出来就是 : o.f. min Z = X1 + X2 + X3 + X4 + X5 + X6 : s.t. X1 + X4 + X5 + X6 >= 12 : X1 + X2 + X5 + X6 >= 8 : X1 + X2 + X3 + X6 >= 6 : X1 + X2 + X3 + X4 >= 9 : X1 + X2 + X3 + X4 + X5 >= 10 : X2 + X3 + X4 + X5 + X6 >= 12 : X3 + X4 + X5 + X6 >= 10 : n.c.'s : X1, X2, X3, X4, X5, X6 are nonnegative integers : 最佳解为 (X1, X2, X3, X4, X5, X6) = (2, 1, 0, 6, 1, 4) : 总共最小值 14 人 : 最後是，我们可以看到排班三不需要有人上班，如果题目额外要求每排班都有人(Xi>0) : 就直接做转换 Xi' = Xi - 1 >= 0，最後把所有的 f.c.'s 换掉求完之後再换回去 : 以上作法请 原PO 参考，有错的话也请网友们提出讨论～ 我对於这题的理解跟你不一样，题目是说规划周休连续二日的人力计画 令 x_i = 星期 i 开始上班的人 i = 1,2,3,...,7 且为整数 min Z= x1 + x2 + x3 + x4 + x5 + x6 + x7 对於星期一这一天来说，只有从星期二跟星期三开始上班的人不会在星期一出现 因为星期二开始上班五天之後 连续周休两天 跳过周日跟周一 星期三开始上班五天之後 连续周休两天 跳过周一周二 所以周一的人力需求是 x1 + x4 + x5 + x6 + x7 >= 12 後面以此类推得到 周二 - 周日的人力需求 x2 + x5 + x6 + x7 + x1 >= 8 x3 + x6 + x7 + x1 + x2 >= 6 x4 + x7 + x1 + x2 + x3 >= 9 x5 + x1 + x2 + x3 + x4 >= 10 x6 + x2 + x3 + x4 + x5 >= 12 x7 + x3 + x4 + x5 + x6 >= 10 这题 x_i 求解时一定要限制为整数 得到解 (x1, x2, x3, x4, x5, x6, x7) = (1,2,0,6,2,3,0) 总需求=14 这是我看过题目之後的理解，因为题目没有说周日不能排人开始上班 而且周日也有人力的需求，周休连续二日是指不管从哪天开始上班 连续上班之後五天一定要连续休两天 不过得到解之後发现 星期天不用排人上班 所以上面那一篇的解也是正确的 本题有多重解 只是如果等式右边的数字 也就是人力需求的量改变的话 上面那一篇这样的建模方法未必会得到正确的答案 因为周日不一定都是不用排人上班 只是在这组数据刚好是这样 比方说把周日的人力需求由10个人改成12个人 我上面的模型跑出来的答案会是 (1,1,0,6,2,3,1) 只需要14人依然满足每天的需求 但是上面一篇忽略x7变数的限制式会得到 (2,0,0,7,2,4) 需要15人 很明显是一个比较不好的解 而在上上一篇用矩阵跟Matlab的解是错误的 不满足周四跟周五的人力需求 有不同见解欢迎提出 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 50.88.209.128 (美国) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1588809299.A.F14.html ※ 编辑: illousion (50.88.209.128 美国), 05/07/2020 08:07:27