整数规划和0-1规划.ppt
《整数规划和0-1规划.ppt》由会员分享,可在线阅读,更多相关《整数规划和0-1规划.ppt(25页珍藏版)》请在启牛文库网上搜索。
1、,整数规划制作:傅明睿,Mathematical modeling,整数规划是什么?,规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。,Mathematical modeling,整数规划的分类,变量全限制为整数时,称纯(完全)整数规划。变量部分限制为整数的,称混合整数规划。变量只能取0或1时,称之为0-1整数规划。,Mathematical modeling,整数规划模型的建立整数规划模型的求解 完全枚举法 分支定界法 割平面法0
2、-1数规划模整型,Mathematical modeling,例1 集装箱运货问题:已知甲乙两种货物的装运和获利情况如下表所示,问:甲乙两货物各托运多少箱,可使获得利润最大?,Mathematical modeling,解:设 为甲乙两货物各托运箱数,Mathematical modeling,(1)原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:a原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。b原线性规划最优解不全是整数,则整数规划最优解小于原线性规划最优解(max)或整数规划最优解大于原线性规划最优解(min)。,Mathematical modeli
3、ng,例2 今有一台机器将一周生产的两种型号的冷饮杯存储在150立方米的储藏室 里,并同时进行出售.已知这台机器能在6小时内生产一百箱号杯,5小时内生产一百箱号杯,生产以百箱为单位计算,预计每周生产60小时.如果号杯每百箱占体积10立方米,每百箱可获利润500元,每周售出数量不会超过800箱;号杯每百箱占体积20立方米,每百箱可获利润450元,每周售出数量不受限制.为保证总收益为最大,每周应安排生产、号杯各多少百箱?,Mathematical modeling,解:设每周生产、号杯各 百箱,则有如下数学模型,返回,Mathematical modeling,例3:设整数规划问题如下,完全枚举法
4、,Mathematical modeling,现求整数解(最优解):如用“舍入取整法”可得到4个点即(1,3)(2,3)(1,4)(2,4)。显然,它们都不可能是整数规划的最优解。故按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集,如图所示。,求得(2,2)(3,1)点为最大值,。在求解整数规划问题时,可将集合内的整数点一一找出,其最大目标函数的值为最优解,此法为完全枚举法。,返回,Mathematical modeling,对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系统搜索,这就是分枝与定界内容。通常,把全部
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 整数 规划