整数规划精美管理学习教案.pptx

一、整数规划的一般形式
1、实例：
例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5－1：
货物
体积
每箱（米3）
重量
每箱（百斤）
利润
每箱（百元）
问题 目标函数值的初始上界
因为问题 的最优解不满足整数条件,因此 不是问题
的最优解,又因为 的可行域 问题 的可行域 ,
故问题 的最优值不会超过问题 的最优值. 即有
因此可令 作为 的初始上界
即
一般说来,若问题 无可行解,则问题 也无可行解,停止计
算。若问题 的最优解 满足问题 的整数
第14页/共99页
第十四页，共100页。
条件,则 也是问题 的最优解,停止计算.
2. 计算原问题 目标函数值的初始下界
若能从问题 的约束条件中观察到一个整数可行解,则可将
其目标函数值作为问题 目标函数值的初始下界,否则可令
初始下界Z=-∞.给定下界的目的,是希望在求解过程中寻找
比当前 更好的原问题的目标函数值 .
对于本例,很容易得到一个明显的可行解X=(0,0)T,Z=0. 问
题 的最优目标函数值决不会比它小,故可令 =0.
第15页/共99页
第十五页，共100页。
3. 增加约束条件将原问题分枝
当问题 的最优解 不满足整数条件时,在 中任选一个
显然问题 的
整数最优解只能是 或 ,而绝不会在5与6之间.
因此当将可行域 切去 部分时,并没有切去 的
及 来达
到在 切去 部分的目的. 切去 后就分
为 及 两部分,即问题 分为问题 及问题 两枝子
规划.
第16页/共99页
第十六页，共100页。
问题
问题
作出问题 的伴随规划 则问题 的可行
域为 见图2(b). 以下我们将由同一问题分解出的两
个分枝问题称为"一对分枝".
第17页/共99页
第十七页，共100页。
4. 分别求解一对分枝
在一般情况下,对某个分枝问题(伴随规划)求解时,可能出现
以下几种可能:
(a)
(a)
(b)
图2
第18页/共99页
第十八页，共100页。
(1 ) 无可行解
若无可行解,说明该枝情况己查明,不需要由此分枝再继续
分枝,称该分枝为 “树叶”，剪枝。
(2) 得到整数最优解
若求得整数最优解，则该枝情况己查明,不需要再对此继续
分枝，该分枝也是 "树叶".
(3) 得到非整数最优解
若求得某个分枝问题得到的是不满足整数条件的最优解，
第19页/共99页
第十九页，共100页。
①该最优解的目标函数值Z小于当前的下界 ，则该
枝内不可能含有原问题的整数最优解，称为“枯枝”，需
剪掉。
②该最优解的目标函数值Z大于当前的下界 ，则仍需对该枝继续分枝，以查明该分枝内是否有目标函数值比当前的 更好的整数最优解。
本例中问题 及问题 的模型及求解结果如下：
还要区分两种情况：
第20页/共99页
第二十页，共100页。
问题
问题
解为:
解为:
第21页/共99页
第二十一页，共100页。
问题 的解 是整数最优解,它当然也是问题
的整数可行解,故 的整数最优解
即此时可将 修改为:
同时问题 也被查清, 成为“树叶”。
因为 ,不满足整数条件, 故问题 分别增加约
束条件： 及 。分为 与 两枝, 建立相应的
伴随规划——问题 与
第22页/共99页
第二十二页，共100页。
问题
问题
它们的可行域分别为
见图3。
第23页/共99页
第二十三页，共100页。
图3
因为 ，问题
无可行解，此问题已
是"树叶", 已被查清.
求解问题 , 得到最优解
5. 修改上、下界 与
(l) 修改下界
修改下界的时机是:每求出一个整数可行解时,都要作修改
下界 的工作.
第24页/共99页
第二十四页，共100页。
修改下界 的原则:在至今所有计算出的整数可行解中,选
目标函数值最大的那个作为最新下界 。
因此在用分枝定界法的求解全过程中,下界 是不断增大的.
(2) 修改上界
上界