[Mathematical Modeling] Integer Programming

司守奎 《数学建模算法与应用》 第二版

0-1型

相互排斥的约束条件

5x1+4x2≤24 或 7x1+3x2≤45

如果有m个互相排斥的约束条件

指派问题
拟分配n人去做n项工作,每人做且仅做一项工作,若分配第i人去做第j项工作,需花费c单位时间,Ask how work should be distributed so that workers spend the least total time？

蒙特卡洛法（随机取样法）
y=x²、y=12-x与x轴在第一象限围成一个曲边三角形.设计一个随机实验,求该图形面积的近似值.

在矩形区域[0,12]×[0,9]上产生服从均匀分布的10⁷个随机点,统计随机点落在曲边三角形的频数,则曲边三角形的面积近似为上述矩形的面积乘以频率.

clc,clear
×=unifrnd(0,12,[1,10000000]);
y=unifrnd(0,9,[1,10000000]);
pinshu =sum(y<x.^2 &x<=3)+sum(y <12-x&x>=3);
area_appr =12 *9 *pinshu/10^7

编写文件mengte.m,目标函数fand constraint vectorg

function[f,g]=mengte(x);
f=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);
g=[
    sum(x)-400
    x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800
    2*x(1)+x(2)+6*x(3)-200
    x(3)+x(4)+5*x(5)-200
    ];　

主函数

format compact;
rand('state',sum(clock)); % 初始化随机数发生器
p0=0;
tic % 计时开始
for i=1:10^6
    x=randi([0,99],1,5); % 产生1行5列的区间[0,99]上的随机整数
    [f,g]=mengte(x);
    if all(g<=0)
        if p0<f
            x0=0;p0=f; % Record the current best solution
        end
    end
end
x0,p0
toc % 计时结束