Re: [其他] 三題線性規劃（作業研究/管理科學）贈P幣-第三題

[illousion (Es tut mir Leid)]

※ 引述《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 我來修改一下
→ cuylerLin   : 我跑過之後答案為(1,2,0,6,1,3,1)，不過換一種線性
→ cuylerLin   : 規劃的solver反而跑出另一種解(0,1,1,5,3,2,2)
→ cuylerLin   : 前者的星期三四日均高過下限一個人，其餘剛好；後者
→ cuylerLin   : 則是只有星期日高過下限三個人，其餘均剛好
→ cuylerLin   : 這應該就無法直接從題目來判斷何者排班優劣了
推 cuylerLin   : 感謝illousion大的指教XD，我修改後又多補了幾組解
→ illousion   : 原問題如果對於不同天招聘的人有不同的成本
→ illousion   : 那可能就會有唯一的最佳解 這樣的cover問題
→ illousion   : 在polyhedral的概念來說 對稱性很嚴重 symmetric
→ illousion   : 所以有多重最佳解是很常見的 問題難度也是NP-hard
推 cuylerLin   : 我當初看就覺得奇怪XD原本以為是Hungarian或Russell
→ cuylerLin   : 方法就可以解掉了，後來才發現有少條件，還是乖乖
→ cuylerLin   : 列模式求解