文档介绍：整数规划及其数学模型
例:某工厂用集装箱托运甲、乙两种货物,每箱的体积、重量、可获得的利润
及托运所受限制如表所示:
货物
体积(m3/每箱)
重量(百斤/每箱)
利润(百元/每箱)
甲
5
2
20
乙
4
5
10
托运限制
24
13
问:两种货物各托运多少箱,可使利润最大?
解:设甲乙两种货物托运的箱数分别为,则
为整数
这是一个整数线性规划问题。
不考虑(4)时,其最优解为:
将取整
是可行解,但不是最优解。
不是可行解;
整数规划及其数学模型
整数规划的类型
连续规划:线性规划问题中决策变量是连续变量。
整数规划:部分或全部决策变量取整数值的数学规划问题,属于离散规划。
整数规划问题分为以下几类:
1. 纯整数规划:全部决策变量取整数值的整数规划。
2. 混合整数规划:决策变量中有一部分必须取整数值的整数规划。
3. 0-1型整数规划:决策变量只能取值0或1的整数规划。
按照目标函数和约束条件中是否包含非线性,将整数规划分成整数线性规划和
整数非线性规划。本章的整数规划都是整数线性规划。
整数规划的数学模型及其特点
1. 整数线性规划的数学模型一般形式为:
整数规划及其数学模型
整数规划的数学模型及其特点
2. 整数线性规划的特点
不考虑整数条件,由余下的约束条件和目标函数构成的规划问题为该整数规
划问题的松弛问题。
整数规划问题的可行解一定是其松弛问题的可行解,但松弛问题的最优解取
整所得到的解不一定是整数规划的最优解,甚至也不一定是整数规划的可行解。
例:背包问题
设一个背包的容积为,现有种物品可装,物品的重量为,体积为,
问如何配装物品,不超过背包体积,并且使装物品的总重量最大?
解:设
物品被装入背包
物品不装入背包
数学模型为:
分枝定界法
对于整数规划问题,当可行域有界,可用穷举法(枚举法)。穷举变量所有可行的整数组合,再比较其目标函数值以找到最优解。对于小型问题,变量少,该方法可行;对于大型问题,可行的整数组合很多,穷举法不可取。
分枝定界法仅检查可行的整数组合的一部分,找到最优整数解。
分枝与定界
若整数规划的松弛问题的最优解不符合整数要求,设,不符合整数
要求, 是不超过的最大整数,则构造两个约束条件:
分别将其并入上述松弛问题中,形成两个分枝后继问题,两个后继问题中的
可行域包含原整数规划问题的所有可行解。
根据需要,各个后继问题可以类似产生自己的分枝后继问题,如此不断,直
到获得整数规划问题的最优解,就是所谓的“分枝”。
分枝定界法
分枝与定界
在分枝过程中,某个后继问题获得一个整数可行解,则其目标函数值为
一个“界限”,可作为衡量其他分枝的一个依据。对于对应松弛问题最优解
目标函数值小于上述“界限”值的后继问题,可删除不予以考虑。当以后的
分枝出现更好的“界限”,就以它来取代原来的界限。
将可行域分成子区域(分枝),逐步减小松弛问题的目标函数值(上界)
增大整数规划问题的目标函数值(下界)。
分枝:为整数规划最优解出现创造新条件。
定界:提高搜索的效率。
分枝定界法
分枝与定界
例:
解:记整数规划问题为IP,松弛问题为LP
不考虑条件(4),求解LP问题的最优解为:
不符合整数要求
(1)任选一变量如进行分枝,构造两个约束条件:
加入到LP问题中,得到后继问题LP1、LP2。
LP1最优解为:
不符合整数要求
LP2最优解为:
不符合整数要求
分枝定界法
分枝与定界
LP11无可行解
不符合整数要求
LP12最优解为:
(2)
优先选择LP1分枝
构造两个约束条件:
加入到LP1中,得到两个分枝LP11、LP12。
(3)
在LP2、LP12中优先选择LP12分枝
构造两个约束条件:
加入到LP12中,得到两个分枝LP121、LP122。
LP121最优解为:
LP122最优解为:
这两个解为IP问题的可行解且目标函数值
相等,是IP最优解目标函数值的一个下界。
分枝定界法
分枝与定界
对于LP2,
不必再对LP2进行分枝搜索
该IP问题的两个最优解为:
LP
LP1
LP2
LP11
LP12
LP121
LP122
(3)这两个解为IP问题的可行解且目标函数值相等,是IP最优解目标函数值的
一个下界。
分枝定界法
分枝定界法的基本步骤
:
(1