※ 引述《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/m.aspx?n=bbs/Math/M.1588775223.A.F9D.html ※ 編輯: cuylerLin (60.250.230.253 臺灣), 05/08/2020 20:41:15