0-1整数规划

第12章0-1整数规划2020/4/191预备知识：整数线性规划基本理论2整数线性规划MATLAB程序30-1型整数线性规划40-1型线性规划Matlab命令5建模与计算实验2020/4/19整数线性规划的提法：在一般的线性规划中，增加限定：决策变量是整数，即为所谓ILP问题:取整数或或),,2,1(),,2,1(0),(..'minnjxnjxbAxtsxcfjj12.1整数线性规划基本理论2020/4/19整数线性规划问题的标准形式为：)(..min的某些分量取整数xuxlhxGhGxtsxfzbbeqeq12.2整数线性规划MATLAB程序2020/4/19Matlab没有整数线性规划求解命令算法：分支定界法工具箱yalmip(可网上下载）可求解全整数线性或混合整数线性规划2020/4/19补充工具箱应用yalmip用法(1)定义变量：sqdvar（）实型；intvar（）整型；binvar（）0-1型；(2)设定目标函数:f=目标函数；(3)设定限定条件：F=set（限定条件）；多个限定条件用加号相连：F=set（限定条件）+set（限定条件1）+set（限定条件2）……；(4)求解：solvesdp（F,f）；这里解得是F条件下目标函数f的最小值，要求最大值f前面加个负号。求解之后查看数值:double（f）double（变量）2020/4/19Yalmip工具箱应用举例目标函数：maxz=4x1+6x2+2x3s.t.-x1+3x2=8-x2+3x3=105x1-x3=8x1、x2、x3=0,x1、x2、x3为整数具体代码如下：x=intvar(1,3);f=[462]*x’;F=set(x0)+set([-130]*x’=8)+set([0-13]*x’=10)+set([50-1]*x’=8);solvesdp(F,-f)double(f)double(x)2020/4/19非线性整数规划举例Maxz=x1^2+x2^2+3*x3^2+4*x4^2+2*x5^2-8*x1-2*x2-3*x3-x4-2*x5s.t.x1+x2+x3+x4+x5=400x1+2*x2+2*x3+x4+6*x5=8002*x1+x2+6*x3=800x3+x4+5*x5=2000=xi=99(i=1,2,...,5)xi为整数2020/4/19在matlab中输入x=intvar(1，5)；f=[11342]*(x'.^2)-[82312]*x';F=set(0=x=99);F=F+set([11111]*x'=400)+set([12216]*x'=800)+set(2*x(1)+x(2)+6*x(3)=800);F=F+set(x(3)+x(4)+5*x(5)=200);solvesdp(F,-f)double(f)80199double(x)5399999902020/4/1912.30-1型整数线性规划0-1型整数线性规划10),,2,1(),,2,1(0),(..'min或取或或njxnjxbAxtsxcfjj2020/4/1912.40-1型线性规划Matlab命令0-1规划问题的标准形式为：10..min或取jeqeqxbxAbAxtsxfz2020/4/19Matlab命令x=bintprog(f,A,b)求解0-1型整数线性规划，用法类似于linprog。x=bintprog(f,A,b,Aeq,beq)求解下面线性规划：minz=f’x,Ax≤b,Aeqx=beq，x分量取值0或1。x=bintprog(f,A,b,Aeq,beq,x0)指定迭代初值x0如果没有不等式约束，可用[]替代A和b表示缺省，如果没有等式约束，可用[]替代Aeq和beq表示缺省；用[x,Fval]代替上述各命令行中左边的x，则可得到最优解处的函数值Fval。2020/4/19例3例3求解下列0-1型整数规划10,,6434422..523max3213221321321321或为xxxxxxxxxxxxxtsxxxf2020/4/19求解首先化为标准形式，转换求max为求min–f=3x1-2x2+5x3c=[3,-2,5];a=[1,2,-1;1,4,1;1,1,0;0,4,1];b=[2;4;3;6];[x,fval]=bintprog(c,a,b);xmax=x,zmax=-fval2020/4/1912.5建模与计算实验例5某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表：货物体积重量利润每箱（米3）每箱（百斤）每箱（百元）甲5220乙4510托运限制24132020/4/19建模设x1和x2分别为甲和乙两种货物的托运箱数为整数21212121,)2,1(013522445..1020maxxxjxxxxxtsxxfj2020/4/19求解化为min问题,用yalmip求解2020/4/19例6一架货运飞机，有效载重量为24吨，可运输物品的重量及运费收入如下表所示，其中各物品只有一件可供选择。物品123456重量（吨）8136957收入(万元)3524232020/4/19建模种物品时当不选运第种物品时当选运第iixi0110,,,,,247596138..324253max654321654321654321或为xxxxxxxxxxxxtsxxxxxxf2020/4/19求解化为min问题,用bintprog求解c=-[3,5,2,4,2,3];a=[8,13,6,9,5,7];b=24;[x,g]=bintprog(c,a,b)f=-g2020/4/19