公司网站设计要求最新疫情消息
上篇文章：整数规划
文章摘要：非线性规划的Python实现。
参考书籍：数学建模算法与应用(第3版)司守奎 孙玺菁。
PS：只涉及了具体实现并不涉及底层理论。学习底层理论以及底层理论实现：可以参考1.最优化模型与算法——基于Python实现 渐令 粱锡军2.算法导论(原书第3版)Thomas H.Cormen Charles E.Leiserson、Ronald L.Rivest Clifford Stein
文章声明：如有发现错误，还望批评指正。
文章目录
- 非线性规划简述
- 非线性规划典例
- 蒙特卡洛随机模拟
非线性规划简述
线性规划可行域内一定有解并且可以通过单纯形法或内点法找到。由于线性规划是凸问题所以第一篇文章使用ECOS第二篇文章使用GLOK_ML是合理的。非线性规划由于没有通用的求解方法从而难以优化。但是某些特定形式的非线性规划问题可被优化或者可以找到一些近似的解。
非线性规划典例
这应该是最优化的内容范畴，我们这里不作讨论。我们这里介绍蒙特卡洛随机模拟。
蒙特卡洛随机模拟
参考书籍例2.9
目标函数
max y = x 1 2 + x 2 2 + 3 x 3 2 + 4 x 4 2 + 2 x 5 2 − 8 x 1 − 2 x 2 − 3 x 3 − x 4 − 2 x 5 \max y=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 maxy=x12+x22+3x32+4x42+2x52−8x1−2x2−3x3−x4−2x5
约束条件
0 ≤ x i ≤ 99 , i = 1 , 2 , … , 5 0\leq x_i\leq99,i=1,2,\dots,5 0≤xi≤99,i=1,2,…,5
x 1 + x 2 + x 3 + x 4 + x 5 ≤ = 400 x_1+x_2+x_3+x_4+x_5\leq=400 x1+x2+x3+x4+x5≤=400
x 1 + 2 x 2 + 2 x 3 + x 4 + 6 x 5 ≤ 800 x_1+2x_2+2x_3+x_4+6x_5\leq800 x1+2x2+2x3+x4+6x5≤800
2 x 1 + x 2 + 6 x 3 ≤ = 200 2x_1+x_2+6x_3\leq=200 2x1+x2+6x3≤=200
x 3 + x 4 + 5 x 5 ≤ 200 x_3+x_4+5x_5\leq200 x3+x4+5x5≤200
from random import randint
def fun():lt=[randint(0,99) for _ in range(5)]if lt[0]+lt[1]+lt[2]+lt[3]+lt[4]>400:return Noneif lt[0]+2*lt[1]+2*lt[2]+lt[3]+6*lt[4]>800:return Noneif 2*lt[0]+lt[1]+6*lt[2]>200:return Noneif lt[2]+lt[3]+5*lt[4]>200:return Nonereturn lt[0]**2+lt[1]**2+3*lt[2]**2+4*lt[3]**2+2*lt[4]**2-8*lt[0]-2*lt[1]-3*lt[2]-lt[3]-2*lt[4]
n=pow(10,6);x=-float("inf")
for _ in range(n):f=fun()if f and f>x:x=f
print(x)
PS：30秒以内可以跑完。