整数规划（蒙特卡洛）若在线性规划模型中，变量限制为整数，则称为整数线性规划。 对于整数线性规划模型⼤致可分为两类：变量全限制为整数时，称纯（完全）整数规划。
变量部分限制为整数的，称混合整数规划。
原线性规划有优解，当⾃变量限制为整数后，其整数规划解会出现： 原线性规划优解全是整数，则整数规划优解与线性规划优解⼀致。
整数规划⽆可⾏解。
有可⾏解（当然就存在优解），但优解值变差。
求解⽅法分类：
分枝定界法—可求纯或混合整数线性规划。
割平⾯法—可求纯或混合整数线性规划。
隐枚举法—求解“0-1”整数规划：过滤隐枚举法；分枝隐枚举法。
洛伦兹力匈⽛利法—解决指派问题（“0-1”规划特殊情形）。
蒙特卡洛法—求解各种类型规划。
蒙特卡洛最经典的应⽤就是求圆周率。
#include <iostream>
#include <stdlib.h>
#include <time.h>
#define MAX_BASE 10000000
surfer8.0float Rand(float L, float R)
{
return L + (R - L) * rand() * 1.0 / RAND_MAX;拉萨尔
}
float GetPi()
{
srand(time(NULL));
int count = 0;
for (int i = 0; i < MAX_BASE; ++i) {
float x = Rand(-1, 1);
float y = Rand(-1, 1);
if (x * x + y * y <= 1)
count++;
}
红阳药业return count * 4.0 / MAX_BASE;
}
退火温度int main ()
{
for (int i = 0; i < 10; ++i)
std::cout << GetPi() << std::endl;
return0;
}
蒙特卡洛积分的应⽤，如求⾃然常数。
积分：
即求阴影部分的⾯积。
假设满⾜
⽽⽤⽜顿莱布尼兹公式可得：
两种⽅法得到的结果相同，即
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define MAX_BASE 10000000
struct Point {
float x;
float y;
};
inline float Rand(float L, float R)
{
变异系数法return L + (R - L) * rand() * 1.0 / RAND_MAX; }
Point GetPoint()
{
Point t;
t.x = Rand(1.0, 2.0);
t.y = Rand(0.0, 1.0);
return t;
}
float GetResult()
{
int m = 0;
int n = MAX_BASE;
srand(time(NULL));
for (int i = 0; i < n; ++i) {
Point t = GetPoint();
float result = t.x * t.y;
if (result <= 1.0)
m++;
}
return pow(2.0, 1.0 * n / m);
}
int main ()
{
for (int i = 0; i < 10; ++i)
std::cout << GetResult() << std::endl; return0;
}
参考：。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议