作者TimcApple (肥鵝)
看板Math
標題[其他] TC題 (18) 線性規劃/整數
時間Mon May 25 20:53:21 2020
Problem 18
如圖
絕不偷工減料的師傅ow o
https://i.imgur.com/mFNbepg.png
=================================================================
不太會編故事...
說個題外話，一般數學題目的詳解，寫錯不是什麼大不了的事情
除了typo之外，即使答案甚至解法偶爾錯了，那都是小事
但如果幾乎每個類似題解法都錯，那就很嚴重了
是說 FB 上有人回應 應該全都做黃金起司蛋糕
因為在台灣 黃金起司蛋糕的價格完勝蜂蜜起司蛋糕
所以後者根本就賣不出去
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.167.239 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1590411203.A.721.html
1F：推 cuylerLin : 兩種蛋糕厚度皆為3"立方"單位（？ 05/25 22:11
2F：→ TimcApple : 厚度算長度吧XD 05/25 22:16
3F：→ cuylerLin : 阿沒事，我一時頭暈QQ 05/25 22:21
4F：→ cuylerLin : 不知道是不是有誤會題目，體積都可以算出來了，為什 05/25 22:26
5F：→ cuylerLin : 麼還可以"等體積"？ 05/25 22:26
6F：→ Ricestone : 因為沒講清楚的話材料不一定等於成品體積 05/25 22:29
7F：→ cuylerLin : 原來是偷工減料的部分阿www 05/25 22:29
8F：→ cuylerLin : 不知道有沒有錯，我跑程式偷偷告訴我答案是(24,5) 05/25 22:32
答案不是(24,5) 根號3真的很討厭XD
10F：推 Vulpix : 我覺得檸檬起司蛋糕比較讚/也可以換其他水果口味。 05/25 22:51
我很愛起司 但沒很愛起司蛋糕其實
11F：→ cuylerLin : 我稍微在邊界土了一下，好像找到了(7,22)總利潤5793 05/25 23:01
100P
12F：推 mack : 16*3^0.5*x+28y<=810可得28.多<=x+y<=29.多 05/25 23:17
13F：→ mack : 故目標函數的x+y=29 05/25 23:17
14F：→ mack : 題目變成在滿足x+y=29求y的最大值發生在什麼時候 05/25 23:18
這個觀察不錯 我確實是用類似的想法在出題
但要是換了一個斜率好像還是蠻難搞的
15F：推 tyz : 同cu大土的 (7,22) 5793 05/25 23:25
10P
16F：推 mack : y<=(810-16*3^0.5*29)/(28-16*3^0.5)=22.035多 05/25 23:33
17F：→ mack : 得(x,y)=(7,22) 05/25 23:33
18F：→ mack : (7,22)要再帶入另一條件不等式 剛好也滿足 05/25 23:34
有算法給 30P 吧 畢竟我連土都懶 我是 Desmos 出來的XD
嘛既然很多人解出來了 那我說一下為什麼要出這題
我想要表達 當題目為線性規劃的時候
「整數解可以在實數解附近找出來」這個解法
完全是錯的
幹一大堆補習班的詳解都寫錯，馬的我超想砍人
本題線性規劃區域有四個節點(以下為估計值)
(0, 0), (0, 28.929), (28.75, 0), (24.07, 5.105)
實數解是 (24.07, 5.105)，最近的整數點是 (24, 5)
但整數解是遠在天邊的 (7, 22)，甚至不在任何一個節點附近
這個點是區域內，離直線 810 = 16√3 + 28y 最近的整數點
實際距離不到 0.0003
會發生這種事的主因是斜率(不取負號的量值)
16√3 / 28 = 0.9897 非常接近 1
所以該直線旁邊會有一大串越來越靠近的整數點
偏偏目標函數 199/200 = 0.995 更接近 1 卻又沒超過 1
所以它會先碰到最邊緣但最靠近直線的整數點 即 (7, 22)
另一條線 24/22 = 1.0909 是幌子，但也至少要大於 1
並且要把更大的整數解 block 在規畫區域外
只是本題 16√3/28 太過優秀，下一個更大的整數點是 (105, -75)
https://www.desmos.com/calculator/cii9u3hqd0
藍線旁邊有一大串格子點，我放大好幾倍才看出誰在哪邊XD
最後再順帶一提 16√3 : 28 來自 √3 連分數近似值 7/4
19F：→ cuylerLin : 話說我剛剛重新調整誤差之後，確實找到(7,22)了XD 05/26 00:12
20F：→ cuylerLin : 原本預設誤差有1%(因為原本不適用整數規劃，而是普 05/26 00:12
21F：→ cuylerLin : 通的LP) 05/26 00:12
22F：→ cuylerLin : 不過不管怎樣，這題剛好二維空間可作圖，也許有人空 05/26 00:14
23F：→ cuylerLin : 間感特優，三維空間也可以，但實際問題通常變數都不 05/26 00:15
24F：→ cuylerLin : 是能夠給你慢慢作圖找點的... 05/26 00:15
嗯 我在猜 最低需求精度應該跟直線的斜率差有關
這題的目標函數和某直線的斜率差太小 對精度的要求很高
發現了精度問題 給 20P 吧XD
25F：推 Vulpix : 我也覺得高中參考書都把整數線性規劃寫得太簡單。 05/26 00:27
26F：推 Vulpix : 實際上找解的方法應該也要用上連分數吧。 05/26 00:33
27F：→ Vulpix : 這題要把√3近似到[1;1,2,1,2,1,2,1]=97/56才第一次 05/26 00:34
28F：→ Vulpix : 有整數解。 05/26 00:34
問題不是無理數 我之前在 FB 上有給過另一組題目
x, y 是整數，且滿足
x >= 0
y >= 0
11x+9y <= 200
10x+13y <= 224
試問 7x+6y 的最大值
https://reurl.cc/oLmx2V
※ 編輯: TimcApple (49.216.167.239 臺灣), 05/26/2020 00:54:16
29F：推 Eric6411 : 推！之前在課堂上有聽老師說過這個觀念，確實是在解 05/26 01:22
30F：→ Eric6411 : 線性規劃的題目時很容易遺漏的觀念 05/26 01:22
31F：推 KomiShousuke: convex hull 05/26 09:07
32F：推 LPH66 : 來給個豆知識: 限定在整數的線性規劃問題的一個特例 05/26 11:51
33F：→ LPH66 : "0-1 規劃問題" (0-1 programming) 變數都是 0 或 1 05/26 11:51
34F：→ LPH66 : 然後要找出有沒有符合所有限制式的取值這樣的問題 05/26 11:52
35F：→ LPH66 : 是 Karp 的 21 個 NP 完全問題當中的一個 05/26 11:52
36F：→ LPH66 : 這是當年 NP 完全這概念剛提出來時, Richard Karp 05/26 11:54
37F：→ LPH66 : 的一篇 paper 裡證明出來的 05/26 11:54
38F：→ LPH66 : 他用的技巧就是我當年那篇踩地雷文裡提到的 05/26 11:56
39F：→ LPH66 : 從那第一個 NP 完全問題出發進行歸約來證明 05/26 11:56
跑去看了一次踩地雷文
以上P幣已轉
40F：推 sunev : LPH66 那篇也被sneak的廣告貼文汙染了，真的是毒瘤 05/26 13:02
41F：推 DLHZ : 長知識推 05/26 13:10
42F：→ DLHZ : 其實可以把他推文修掉了 我公告有開放大家處理 05/26 13:10
43F：推 sunev : 版主好像也可以刪推文，但若要全面性的情理還是得 05/26 13:30
44F：→ sunev : 請站方用程式掃 05/26 13:30
45F：推 LPH66 : 噢那個...我去刪一下好了 (之前有注意到但就沒處理) 05/26 17:40
※ 編輯: TimcApple (49.216.167.239 臺灣), 05/26/2020 19:48:03
46F：推 illousion : 在求「整數線型規劃」時，線型規劃的目標函數（放 05/27 09:10
47F：→ illousion : 鬆整數限制）只能是一個bound，以本題來說，是上界 05/27 09:10
48F：→ illousion : 。整數線型規劃的解不能從放鬆後的線性規劃來推論 05/27 09:10
49F：→ illousion : ，也跟目標函數斜率無關。上面推文沒有錯，(mixed) 05/27 09:10
50F：→ illousion : integer (linear) programming 的最佳化都是NP-ha 05/27 09:10
51F：→ illousion : rd問題。再來求整數規劃的演算法是Branch-and-boun 05/27 09:10
52F：→ illousion : d，是一種divide and conquer approach，求解放鬆 05/27 09:10
53F：→ illousion : 線型規劃後再去針對有整數限制的變數分枝，然後upd 05/27 09:10
54F：→ illousion : ate bound或是fathom。上面推文有人說convex hull 05/27 09:10
55F：→ illousion : 這是一個非常正確的觀念，當我們知道整數線型規劃 05/27 09:10
56F：→ illousion : 的convex hull之後，最佳化可以reduce to線型規劃 05/27 09:10
57F：→ illousion : 進而變成一個簡單的問題，因為此時所有extreme poi 05/27 09:10
58F：→ illousion : nts都是整數，只要使用線型規劃的算法(interior po 05/27 09:10
59F：→ illousion : int method, which is polynomial，而simplex則不 05/27 09:10
60F：→ illousion : 是)找解就可以。但是convex hull只有在二維的時候 05/27 09:10
61F：→ illousion : 有可能看出來，高維度一般都是未知。做整數線型規 05/27 09:10
62F：→ illousion : 劃研究的人，一般都是做cutting plane method或是s 05/27 09:10
63F：→ illousion : trong formulation，讓可行區間越小越靠近包含所有 05/27 09:10
64F：→ illousion : 的整數點集合，也就是convex hull。 05/27 09:10
65F：→ TimcApple : 噢噢 大神出現了XD 05/27 09:42
66F：→ TimcApple : 關鍵字好多 這是哪個領域的內容啊qw q 05/27 09:44
67F：推 illousion : 這是作業研究中的整數規劃內容，任何一本作業研究 05/27 10:07
68F：→ illousion : 的書都會講到整數規劃跟branch-and-bound，就是因 05/27 10:07
69F：→ illousion : 為整數規劃跟線型規劃性質完全不同所以要獨立出來 05/27 10:07
70F：→ illousion : 講，而我說到的cutting plane那些是屬於碩博等級的 05/27 10:07
71F：→ illousion : 知識，而且是要專門做整數規劃的人才會去研究，小 05/27 10:07
72F：→ illousion : 弟我剛好博士研究就是整數規劃。另外數學系跟CS也 05/27 10:07
73F：→ illousion : 可能會有人研究這些。整數規劃因為NP-hard，如何設 05/27 10:07
74F：→ illousion : 計有效率的精確或近似算法很重要，或是怎麼把一個 05/27 10:07
75F：→ illousion : 很大的問題分解做decomposition method，因此也必 05/27 10:07
76F：→ illousion : 須具備動態規劃dynamic programming 還有CS中的算 05/27 10:07
77F：→ illousion : 法知識，至少要了解時間複雜度，我老闆都叫我們組 05/27 10:07
78F：→ illousion : 去上幾門CS或數學系的課。 05/27 10:07
79F：推 KomiShousuke: ><~ 05/27 12:14
80F：推 LPH66 : 推一個, 然後我可以簡單補充一下 CS 方面的東西 05/28 16:43
81F：→ LPH66 : Karp 的 21 個 NP 完全問題可以說是為 P = NP 問題 05/28 16:44
82F：→ LPH66 : 做了開路先鋒, 因為那是實際有人找出一系列「難」題 05/28 16:44
83F：→ LPH66 : 出來, 並且證明了它們的「難」 05/28 16:45
84F：→ LPH66 : 我之前提過 NP 完全這個概念是在 1971 年提出的 05/28 16:45
85F：→ LPH66 : Karp 這篇論文是在 1972, 也就是表示他跟人們講說 05/28 16:46
86F：→ LPH66 : 這些個「難」題的難是其來有自的 05/28 16:46
87F：→ LPH66 : 而那個「難」可以用「NP 完全」的概念來描述 05/28 16:47
88F：→ LPH66 : 這才會在將近五十年後的現在能有上千條問題 05/28 16:48
89F：→ LPH66 : 都被證明是 NP 完全而使人們可以把心力放在它們的 05/28 16:49
90F：→ LPH66 : 近似演算法或只適用大部份狀況的演算法上 05/28 16:49