※ 引述《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/m.aspx?n=bbs/Math/M.1588809299.A.F14.html ※ 編輯: illousion (50.88.209.128 美國), 05/07/2020 08:07:27