数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 2082|回复: 3

MATLAB 的 MonteCarlo 太慢了

[复制链接]
发表于 2020-11-15 00:07 | 显示全部楼层 |阅读模式
本帖最后由 Ysu2008 于 2020-11-15 00:35 编辑

求解如下非线性整数规划问题:

\(max \quad z = x_1^2+x_2^2+3x_3^2+4x_4^2+2x_5^2-8x_1-2x_2-3x_3-x_4-2x_5\)

\[s.t.\begin{cases}
\sum_{i=1}^5x_i \le 400 \\
x_1+2x_2+2x_3+x_4+6x_5 \le 800 \\
2x_1+x_2+6x_3 \le 200 \\
x_3+x_4+5x_5 \le 200\\
0 \le x_i \le 99, \; i = 1, \cdots , 5 \end{cases}\]


这是在网上看到的一例算题,作者用 MATLAB 编了一段 Monte Carlo 程序求解该问题, 运行了10个小时,找到的最优解是[41 99 3 99 17],最大值是 50623;然后他给出了用某优化软件算得的精确解为 [50 99 0 99 20],最大值是 51568。


我用 MonteCarlo 重做了此题,发现一般6~10分钟就能找到精确解 [50 99 0 99 20]。我的程序平均每 910 毫秒投点 1500 万次,题目有 5 个变量,每个变量选中最优值的概率为 1/100 ,同时选中 5 个都是最优值的概率为 (1/100)^5 , 投掷10分钟,可投掷大约 98 亿次,选中至少一次最优值的概率大约为 63%;如果投掷 1 个半小时,选中至少一次最优值的概率不小于 99% ,根本不用投掷 10 个小时之多。只能说 MATLAB 太慢了。
发表于 2020-11-15 09:04 | 显示全部楼层
本帖最后由 Nicolas2050 于 2020-11-15 09:06 编辑

脑子有问题?这类问题用单纯形算法不好?,方法不合适,与工具有啥必然关系?
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-11-15 09:39 | 显示全部楼层
Nicolas2050 发表于 2020-11-15 09:04
脑子有问题?这类问题用单纯形算法不好?,方法不合适,与工具有啥必然关系?

我喜欢用 MonteCarlo 求解各种问题,不管它们是否真的需要 MonteCarlo .

点评

好吧,你厉害!  发表于 2020-11-15 13:29
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 18:44 , Processed in 0.079102 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表