0-1整数规划.ppt

第12章 0-1整数规划
*
1
第一章 Matlab入门
1 预备知识:整数线性规划基本理论
2 整数线性规划MATLAB程序
3 0-1型整数线性规划
4 0-1型线性规划Matlab命令
5 建模与计算实验
Date
2
第一章 Matlab入门
整数线性规划的提法:
在一般的线性规划中,增加限定:决策变量是整数,即为所谓ILP问题:
整数线性规划基本理论
Date
3
第一章 Matlab入门
整数线性规划问题的标准形式为:
整数线性规划MATLAB程序
Date
4
第一章 Matlab入门
Matlab没有整数线性规划求解命令
算法:分支定界法
工具箱yalmip(可网上下载)
可求解全整数线性或混合整数线性规划
Date
5
第一章 Matlab入门
补充工具箱应用
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(变量)
Date
6
第一章 Matlab入门
Yalmip工具箱应用举例
目标函数:max z=4x1+6x2+2x3
    .      -x1+3x2<=8
               -x2+3x3<=10
               5x1-x3<=8
               x1、x2、x3>=0,x1、x2、x3为整数
  具体代码如下:
  x=intvar(1,3);
  f=[4 6 2]*x’;
  F=set(x>0)+set([-1 3 0]*x’<=8)+set([0 -1 3]*x’<=10)+set([5 0 -1]*x’<=8);
  solvesdp(F,-f)
  double(f)
  double(x)
Date
7
第一章 Matlab入门
非线性整数规划举例
Max z=x1^2+x2^2+3*x3^2+4*x4^2+2*x5^2-8*x1-2*x2-3*x3-x4-2*x5
.
x1+x2+x3+x4+x5<=400
x1+2*x2+2*x3+x4+6*x5<=800
2*x1+x2+6*x3<=800
x3+x4+5*x5<=200
0<=xi<=99 (i=1,2,...,5)
xi为整数
Date
8
第一章 Matlab入门
在matlab中输入
x=intvar(1,5);
f=[1 1 3 4 2]*(x'.^2)-[8 2 3 1 2]*x';F=set(0<=x<=99);
F=F+set([1 1 1 1 1]*x'<=400)+set([1 2 2 1 6]*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) 80199
double(x) 53 99 99 99 0
Date
9
第一章 Matlab入门
0-1型整数线性规划
0-1型整数线性规划
Date
10
第一章 Matlab入门