文档介绍：整数规划(IP)问题
一、定义
规划中的变量(部分或全部)限制为整数时,称
为整数规划。若在线性规划模型中,变量限制为整
数,则称为整数线性规划。
二、整数规划(IP)分类
  
变量全限制为整数的,称纯(完全)整数规划。  
变量部分限制为整数的,称混合整数规划。
要求决策变量仅取0或1,称为0-1规划问题.
整数规划问题的提出
例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如下表:
货物
体积
每箱(米3)
重量
每箱(百斤)
利润
每箱(百元)
甲
乙
5
4
2
5
20
10
托运限制
24
13
问两种货物各托运多少箱,可使获得的利润为最大?
解:设托运甲、乙两种货物x1,x2箱,用数学式可表示为:
(ILP)
称为(ILP)的伴随规划
2、整数规划一般形式
(1)求解方法方面
3、与LP问题的区别
在例1中,
此IP问题的最优解(值)为:
求ILP问题的伴随规划的最优解(值)为:
例2 做图分析例1的最优解(直观)
IP 问题可行域不为凸集
(2)理论方面
x1
x2
4
8
4
0
Z=96
1
2
3
5
6
7
3
1
2
5x1+4x2=24
2x1+5x2=13
C(,0)
Z=90(最优解)
B(4,1)
Z=80
整数规划特点
伴随规划有最优解,当自变量限制为整数后, 其整数规划解出
现下述情况;
①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
③有可行解(当然就存在最优解),但最优解值变差。
第二节分枝定界法
一、几何解释
适用范围:
纯整数规划问题
0-1规划问题
混合整数规划问题