作者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/cn.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