Re: 请教万能的买买提一个数学建模问题 (转载)# Programming - 葵花宝典
a*y
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部手机分配到不
同的计划里使得总费用最小？
一开始我觉得这是个线性规划的问题，不过研究了半天也写不出约束条件来。
请教各位高手，怎么建立这个数学模型
发信人: 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部手机分配到不
同的计划里使得总费用最小？
一开始我觉得这是个线性规划的问题，不过研究了半天也写不出约束条件来。
请教各位高手，怎么建立这个数学模型
