為什麼這篇管理科學題目鄉民發文收入到精華區：因為在管理科學題目這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者illousion (Es tut mir Leid)看板Math標題Re: [其他] 三題線性...
管理科學題目 在 窮瘋流ChuiKaLok Instagram 的最佳解答
2021-08-16 23:14:19
💁🏽♀️💁🏽♀️💁🏽♀️學員真情剖白💁🏽♀️💁🏽♀️💁🏽♀️ 「計算一下我接受體能訓練已持續有5年多了。起初是為了減肥，塑身，等我可以靚靚地穿起貼身運動服。在開始後3個月已見成績，亦可算是目標達到。同時發現自己愛上了體能訓練。原因係它除了幫我減肥控制體重之外，還幫助我練成強壯嘅身體，不...
※ 引述《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://www.ptt.cc/bbs/Math/M.1588809299.A.F14.html
※ 編輯: illousion (50.88.209.128 美國), 05/07/2020 08:07:27
推 cuylerLin : 原來我眼殘少考慮到第七種排班方式XD 我來修改一下 05/07 08:25
→ cuylerLin : 我跑過之後答案為(1,2,0,6,1,3,1)，不過換一種線性 05/07 08:38
→ cuylerLin : 規劃的solver反而跑出另一種解(0,1,1,5,3,2,2) 05/07 08:39
→ cuylerLin : 前者的星期三四日均高過下限一個人，其餘剛好；後者 05/07 08:40
→ cuylerLin : 則是只有星期日高過下限三個人，其餘均剛好 05/07 08:41
→ cuylerLin : 這應該就無法直接從題目來判斷何者排班優劣了 05/07 08:41
推 cuylerLin : 感謝illousion大的指教XD，我修改後又多補了幾組解 05/07 09:03
→ illousion : 原問題如果對於不同天招聘的人有不同的成本 05/07 09:31
→ illousion : 那可能就會有唯一的最佳解 這樣的cover問題 05/07 09:32
→ illousion : 在polyhedral的概念來說 對稱性很嚴重 symmetric 05/07 09:32
→ illousion : 所以有多重最佳解是很常見的 問題難度也是NP-hard 05/07 09:32
推 cuylerLin : 我當初看就覺得奇怪XD原本以為是Hungarian或Russell 05/08 01:14
→ cuylerLin : 方法就可以解掉了，後來才發現有少條件，還是乖乖 05/08 01:15
→ cuylerLin : 列模式求解 05/08 01:15