下载此文档

运筹学5-整数规划(天津理工大学经管系)课件.ppt


文档分类:高等教育 | 页数:约101页 举报非法文档有奖
1/101
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/101 下载此文档
文档列表 文档介绍
该【运筹学5-整数规划(天津理工大学经管系)课件 】是由【iluyuw9】上传分享,文档一共【101】页,该文档可以免费在线阅读,需要了解更多关于【运筹学5-整数规划(天津理工大学经管系)课件 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。第三章整数规划
整数规划问题的概念
分枝定界解法
割平面解法
0—1型整数规划
整数规划问题的概念
在前面讨论过的线性规划问题中,某些最优解是分数或小数,但对有些具体问题常要求解答必须是整数的情形(称为整数解)。我们称这样的问题为整数规划(Integer,Programming),简称IP。整数规划是近二十年发展起来的规划论中一个重要分枝。
纯整数规划:整数规划中如果所有的变量都限制为(非负)整数;
混合整数规划:如果仅一部分变量限制为整数;
0—1整数规划:所有决策变量取值仅限于0或1。
分枝定界解法
,解(IP)的相应线性规划问题(LP),可能有以下情况:
(1)若(LP)没有可行解,则(IP)也没有可行解。
(2)若(LP)有最优解,并符合(IP)的整数条件,则(LP)的最优解即为(IP)的最优解。
(3)若(LP)有最优解,但不符合(IP)的整数
条件,记(LP)最优解为Z0,转入下一步。
:记(IP)的目标函数最优值为Z*,以Z0为的Z*上界,记为Ẑ,再用观察法找(IP)一个整数可行解,其目标函数值作为下界,记为Z,则有:Ẑ≤Z*≤Z
:各分枝的目标函数值中,若有小于下界Z者,则剪掉此枝,以后不再考虑。若大于Z,且不符合整数条件,则重复以上步骤,直到最后
Ẑ=Z*=Z
例:MaxZ=3x1+2x2 2x1+x2≤9; 2x1+3x2≤14; x1,x2≥0;且为整数。
先不考虑整数约束的条件,解相应的线性规划问题,得最优解为
x1=,x2=,z0= 则:Ẑ=;由题意取Z=0; 0≤Z*≤
MaxZ=3x1+2x2;2x1+x2≤9; 2x1+3x2≤14; x1,x2≥0;
MaxZ=3x1+2x2;
2x1+x2≤9;
2x1+3x2≤14;
x2≤2;
x1,x2≥0;
MaxZ=3x1+2x2;
2x1+x2≤9;
2x1+3x2≤14;
x2≥3;
x1,x2≥0;
MaxZ=3x1+2x2;
2x1+x2≤9;
2x1+3x2≤14;
x2≤2;
x1≤3;
x1,x2≥0;
MaxZ=3x1+2x2;
2x1+x2≤9;
2x1+3x2≤14;
x2≤2;
x1≥4;
x1,x2≥0;

14/3
3
0
2
3
4
x1
x2
问题B
X1=,X2=,Z0=
0≤Z*≤
问题B1
X1=,X2=2,Z1=
问题B2
X1=,X2=3,Z2=
问题B4
X1=4,X2=1,Z4=14
问题B3
X1=3,X2=2,Z3=13
X2≤2
X2≥3
X1≤3
X1≥4
Z*=14
0≤Z*≤
14≤Z*≤14
例:MaxZ=x1+x2 -x1+x2≤1; 3x1+x2≤4; x1,x2≥0;且为整数。
如不考虑整数约束,可求得相应的线性规划的最优解为:x1=3/4,x2=7/4,maxz=10/4
现考虑整数条件,要求x1、x2都是非负整数,于是由条件可知x3、x4也都是非负整数。在上式中(其实只考虑一式即可)从等式左边看是整数;在等式右边的()内是正数;整个等式右边不可能大于1,那么只能小于或等于零,所以等式右边必是负数。就是说,整数条件约束条件可由下式所代替,有:
即:-3x3-x4≤-3
这就得到一个切割方程,将它作为增加约束条件,再解。
引入松弛变量x5,得到等式-3x3-x4+x5=-3
将这新的约束方程加到最终表中,用对偶单纯形法计算:
z
x1
x2
x3
x4
x5
x6
RHS
z
1
-5
0
0
-2
0
0
-8
x3
0
1/2
0
1
3/2
-1/2
0
17/2
x2
0
-1/2
1
0
1/2
-1/2
0
9/2
x6
0
-1/2
0
0
1/2
1/2
1
-5/2

运筹学5-整数规划(天津理工大学经管系)课件 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数101
  • 收藏数0 收藏
  • 顶次数0
  • 上传人iluyuw9
  • 文件大小1.91 MB
  • 时间2022-11-30