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