a*********y
发帖数: 63 | 1 【 以下文字转载自 Mathematics 讨论区 】
发信人: anmitbbsguy (a bbs guy), 信区: Mathematics
标 题: Re: 请教万能的买买提一个数学建模问题
发信站: BBS 未名空间站 (Thu Apr 18 09:30:06 2019, 美东)
实际上我有14个不同的计划，从 250KB/mon 到 20GB/mon。 而且我有几百张手机卡，
将来可能会有上千张卡。从你的解释来看，找到最优解是不可能的啦。
我开始的想法是先把数据使用量排序，然后从小到大，从最低可能的计划开始一张一张
的加卡。等到不合适的时候就转到更高一级的计划。 后来发现这样不行。 因为根据使
用量的不同，有时候把使用量小的卡和一个或几个使用量大的卡合起来会更合算。我用
15张卡的具体数据做过穷举实验，最后的结果大体上是按使用量排列的，但的确会出现
我上面描述的情况。 而且我发现从使用量最大的卡开始往小走结果会更合理一些。
我现在不希望能找到最优解了。 但是如何能找到近似（局部）最优解呢？就像你说的
把解空间分类。
一会儿我把这个问题转到编程版，看看他们怎么说。
----------------------------------------------------------------
-----------------------------------------------------------------
发信人: TheMatrix (TheMatrix), 信区: Mathematics
标 题: Re: 请教万能的买买提一个数学建模问题
发信站: BBS 未名空间站 (Wed Apr 17 23:54:53 2019, 美东)
50部手机，分在5个计划里，假设没有一个计划最多允许的手机数量的限制，那么划分
方法有多少种？假设没有策略，那就要完全枚举，才能找到最优解。
如果手机数量和计划数量增加，如果还是完全枚举的话，那么划分方法的数量，随着手
机数和计划数呈指数增长。这就叫NP问题。
NP问题实际上就是说：没有方法，笨办法。然而每个问题都有简化的方法，用上一个，
枚举的数量就减不少。但是虽然减了不少，可能还有一个指数增长的硬核简化不了，那
么总体还是指数增长，还是NP问题。
NP=P是说每个问题都一定有方法，把指数增长的硬核打散，也就是该方法枚举的数量不
再是指数增长了，也就是幂次方增长，那这个问题就可以说是解决了。
NP=P到底成立不成立，这是一个问题，我个人认为这是一个公理。也就是说我认为，每
个问题都一定有方法，使枚举数量随问题的尺度小于指数增长。可能不容易找到，但是
一定有，找不到还得继续找。
-----------------------------------------------------------------
发信人: TheMatrix (TheMatrix), 信区: Mathematics
标 题: Re: 请教万能的买买提一个数学建模问题
发信站: BBS 未名空间站 (Wed Apr 17 11:31:52 2019, 美东)
这是NP问题。应该也能解，肯定很难了。
------------------------------------------------------------------------
相信大家都听说过share-everything手机计划。对于企业来说，手机服务商可以提供这
样一种计划方式。
比如说我购买了下面5种计划：
计划1. Share 1 MB for $2.25 (overage rate 5c/MB)
计划2. Share 5 MB for $2.50 (overage rate 5c/MB)
计划3. Share 10 MB for $3.75 (overage rate 5c/MB)
计划4. Share 50 MB for $5.00 (overage rate 5c/MB)
计划5. Share 100 MB for $6.50 (overage rate 5c/MB)
然后我买了50部手机给大家用。由于每人消耗的数据不同，到月底，我可以把50部手机
分配到不同的计划里。在每一个计划里的所有手机共享全部的数据流量。比如说我放5
部手机在计划1里面，那么这5部手机共享5MB数据。
我的问题是，现在我已经知道每一部手机使用的数据量，那么怎么把50部手机分配到不
同的计划里使得总费用最小？
一开始我觉得这是个线性规划的问题，不过研究了半天也写不出约束条件来。
请教各位高手，怎么建立这个数学模型 |
T*******x
发帖数: 8565 | 2 你这个想法挺好，一动手能发现不少结构。转编程是对的，这个问题我觉得不能指望数
学办法了，编程版搞搜索的人可能有经验。
【在 a*********y 的大作中提到】
: 【 以下文字转载自 Mathematics 讨论区 】
: 发信人: anmitbbsguy (a bbs guy), 信区: Mathematics
: 标 题: Re: 请教万能的买买提一个数学建模问题
: 发信站: BBS 未名空间站 (Thu Apr 18 09:30:06 2019, 美东)
: 实际上我有14个不同的计划，从 250KB/mon 到 20GB/mon。 而且我有几百张手机卡，
: 将来可能会有上千张卡。从你的解释来看，找到最优解是不可能的啦。
: 我开始的想法是先把数据使用量排序，然后从小到大，从最低可能的计划开始一张一张
: 的加卡。等到不合适的时候就转到更高一级的计划。 后来发现这样不行。 因为根据使
: 用量的不同，有时候把使用量小的卡和一个或几个使用量大的卡合起来会更合算。我用
: 15张卡的具体数据做过穷举实验，最后的结果大体上是按使用量排列的，但的确会出现
|
m******r
发帖数: 1033 | 3 没看太明白。 多得多用的少都是手机公司告诉你的， 你们家用电多，就多交钱； 用
的少，就少交钱。 水费也一样。 为什么手机就不一样？
flex spending是你投1000块钱，一年用光了，就用光了， 用不了，就充公了。
我又想了一下，似乎应该
1.事先估算每部手机大概流量
2.从大到小排列，降序排列
原文作者写‘我开始的想法是先把数据使用量排序，然后从小到大，从最低可能的计划
开始一张一张的加卡。’
看来我的直觉和作者直觉相反。 |
p***o
发帖数: 1252 | 4 搞那么复杂干什么，matlab里找个ILP/MILP solver，跟着网上的tutorial学着用就好。
【在 a*********y 的大作中提到】
: 【 以下文字转载自 Mathematics 讨论区 】
: 发信人: anmitbbsguy (a bbs guy), 信区: Mathematics
: 标 题: Re: 请教万能的买买提一个数学建模问题
: 发信站: BBS 未名空间站 (Thu Apr 18 09:30:06 2019, 美东)
: 实际上我有14个不同的计划，从 250KB/mon 到 20GB/mon。 而且我有几百张手机卡，
: 将来可能会有上千张卡。从你的解释来看，找到最优解是不可能的啦。
: 我开始的想法是先把数据使用量排序，然后从小到大，从最低可能的计划开始一张一张
: 的加卡。等到不合适的时候就转到更高一级的计划。 后来发现这样不行。 因为根据使
: 用量的不同，有时候把使用量小的卡和一个或几个使用量大的卡合起来会更合算。我用
: 15张卡的具体数据做过穷举实验，最后的结果大体上是按使用量排列的，但的确会出现
|
a*********y
发帖数: 63 | 5 看来我对问题的描述还不够清楚，这里我再进一步解释一下。
因为是企业计划，所以服务商提供的计划是一种多卡共享流量的计划。 比如说我有5张
卡，都在“计划1. Share 1 MB for $2.25 (overage rate 5c/MB)”里，意思是说每张
卡都有 1MB/mon 的流量，而且5张卡是共享 5MB 流量。 到了月底算帐的时候，有四张
卡一点儿也没用，第5张卡自己就用了5MB数据。由于这5张卡share-everything，那么
它们合起来流量并没有超。所以我只需要付5 * $2.25 而不用付 overage charge。 这
样就会省很多费用。 比如说有一张卡一个月用了80GB流量，我就可以把另外7张流量使
用非常小的卡和这张卡都放在 10GB/mon 计划。 这样我就不需要付出 overage charge
for 70GB。 尽管我需要多付7张 10GB/mon 的计划钱，但总体来说还是合算。
我一开始是想从小卡往大走，后来发现从大往小走更合理一些，因为我需要小卡去抵消
大卡的流量。
不知道这样说没说清楚。
【在 m******r 的大作中提到】
: 没看太明白。 多得多用的少都是手机公司告诉你的， 你们家用电多，就多交钱； 用
: 的少，就少交钱。 水费也一样。 为什么手机就不一样？
: flex spending是你投1000块钱，一年用光了，就用光了， 用不了，就充公了。
: 我又想了一下，似乎应该
: 1.事先估算每部手机大概流量
: 2.从大到小排列，降序排列
: 原文作者写‘我开始的想法是先把数据使用量排序，然后从小到大，从最低可能的计划
: 开始一张一张的加卡。’
: 看来我的直觉和作者直觉相反。
|
m******r
发帖数: 1033 | 6 如果我算这个命， 我就得用历史数据， 看每个人 （ 也许是你企业的员工 ？） 每个
月的流量， 从而得到均值与方差 。 然后照着那个什么流量计划，拼拼凑凑。 然后可
以算算有一半人流量超过一个标准差， 贵公司要付多少钱 。 压力测试。
现实是流量用多少都是实时显示的， 你看员工用的太多，马上快到计划上限了，就发
个消息给他。 超出本月流量员工自己承担。 不就行了。 |
t**s
发帖数: 4026 | 7 用Genetic algorithm试试吧，有这个功夫问，早就算出结果了
: 看来我对问题的描述还不够清楚，这里我再进一步解释一下。
: 因为是企业计划，所以服务商提供的计划是一种多卡共享流量的计划。 比如说
我有5张
: 卡，都在“计划1. Share 1 MB for $2.25 (overage rate 5c/MB)”里，意思是
说每张
: 卡都有 1MB/mon 的流量，而且5张卡是共享 5MB 流量。 到了月底算帐的时候，
有四张
: 卡一点儿也没用，第5张卡自己就用了5MB数据。由于这5张卡share-everything
，那么
: 它们合起来流量并没有超。所以我只需要付5 * $2.25 而不用付 overage
charge。 这
: 样就会省很多费用。 比如说有一张卡一个月用了80GB流量，我就可以把另外7张
流量使
: 用非常小的卡和这张卡都放在 10GB/mon 计划。 这样我就不需要付出 overage
charge
: for 70GB。 尽管我需要多付7张 10GB/mon 的计划钱，但总体来说还是合算。
: 我一开始是想从小卡往大走，后来发现从大往小走更合理一些，因为我需要小卡
去抵消
【在 a*********y 的大作中提到】
: 看来我对问题的描述还不够清楚，这里我再进一步解释一下。
: 因为是企业计划，所以服务商提供的计划是一种多卡共享流量的计划。 比如说我有5张
: 卡，都在“计划1. Share 1 MB for $2.25 (overage rate 5c/MB)”里，意思是说每张
: 卡都有 1MB/mon 的流量，而且5张卡是共享 5MB 流量。 到了月底算帐的时候，有四张
: 卡一点儿也没用，第5张卡自己就用了5MB数据。由于这5张卡share-everything，那么
: 它们合起来流量并没有超。所以我只需要付5 * $2.25 而不用付 overage charge。 这
: 样就会省很多费用。 比如说有一张卡一个月用了80GB流量，我就可以把另外7张流量使
: 用非常小的卡和这张卡都放在 10GB/mon 计划。 这样我就不需要付出 overage charge
: for 70GB。 尽管我需要多付7张 10GB/mon 的计划钱，但总体来说还是合算。
: 我一开始是想从小卡往大走，后来发现从大往小走更合理一些，因为我需要小卡去抵消
|
