[其他] TC題 (18) 線性規劃/整數

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