|
本帖最后由 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 太慢了。 |
|