下载此文档

第10讲:整数规划(一).ppt


文档分类:高等教育 | 页数:约14页 举报非法文档有奖
1/14
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/14 下载此文档
文档列表 文档介绍
第10讲整数规划(一)
浙江工业大学经贸管理学院曹柬
一、整数规划的概念及其应用
整数规划(Integer Program):决策变量取整 数的LP问题,简称IP问题
纯整数规划(Pure IP):全部整数取整
0-1规划(Zero-One IP):变量只能取0或1
混合整数规划(Mixed IP):部分整数取整
运筹学第10讲:整数规划(一)
篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高以及擅长的位置如下表所示。
队员
1
2
3
4
5
6
7
8
身高(m)








位置
中锋
中锋
前锋
前锋
前锋
后卫
后卫
后卫
出场阵容应满足以下条件:
只能有一名中锋上场;
至少有一名后卫;
如1号和4号均上场,则6号不出场;
2号和8号至少有一个不在场。
问应选择哪5名队员上场,使队员身高最高。
例1(P148-)
0-1规划问题
解:设 0-1变量xi 表示第 i 个队员是否上场,当xi =0时表示该队员不上场;当xi =1时表示该队员上场,建立如下的线性规划模型:
目标函数: min ∑cixi (ci为第i位队员的身高)
约束条件: s. t. x1 + x2 = 1
x6 + x7 + x8 ≥ 1
x1 + x4 + x6 ≤ 2
x2 + x8 ≤ 1
∑xi = 5
xi=0或1, i =1,2,…,8
最优值:
最优解:
x2 = x3= x4= x5= x6=1
其余xi = 0.
例2 (P125-例3)
工厂A1 和 A2生产某种物资。由于该物资供不应求,故需再建一家工厂。相应的建厂方案有 A3和 A4两个。这种物资的需求地有B1, B2, B3和B4四个。各厂年生产能力、各地年需求量、各厂到各需求地的单位物资运费如下表所示。
Bj
B1
B2
B3
B4
生产能力
(kt/年)
Ai
A1
2
9
3
4
400
A2
8
3
5
7
600
A3
7
6
1
2
200
A4
4
5
2
5
200
需求量(kt/年)
350
400
300
150
运费
工厂A3 或 A4开工后,每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3 还是 A4,才能使今后每年的总费用(即全部物资运费和新工厂生产费用之和)最少。
混合整数规划问题
二、Ip问题的求解
松弛问题(slack problem):去掉整数性约束的LP问题,或称原问题的LP问题
例:max z = 6x1 + 5x2 (1) —目标函数
. 2x1 + x2 ≤ 9 (2)
5x1 + 7x2 ≤ 35 (3)
x1 , x2 ≥ 0 (4) —非负条件
x1 , x2 为整数(5) —整数性约束
LP约束
运筹学第10讲:整数规划(一)
上述IP问题的LP问题的解为:
,
当松弛问题的所有非整变量值都较大时,例如xj ≥100,圆整LP问题的方法是有效的
运筹学第10讲:整数规划(一)
max z = 6x1 + 5x2
. 2x1 + x2 ≤ 9,5x1 + 7x2 ≤ 35
x1 , x2 ≥ 0, x1, x2为整数
图解法
5x1 + 7x2 = 35
2x1 + x2 = 9
A
B
A为该问题的松弛问题的最优解
B为该问题的最优解,x1*=4, x2*=1, z*=29
x1
x2
9
9
3
3
6
6
z = 6x1 + 5x2
三、0-1规划问题的求解
将各变量按系数绝对值由大到小的顺序进行排列,并令系数为负的变量 xj=1-xj’;在max型中,从变量最大值开始求算;在min型中,从变量最小值开始求算,并验证约束条件是否成立
max Z = 3x1 - 2x2 + 5x3
. x1 + 2x2 - x3 ≤ 2
x1 + 4x2 + x3 ≤ 4
x1 + x2 ≤ 3
4x2 + x3 ≤ 6
x1, x2, x3 = 0 或 1
例4 (P141-例10)
min Z = 3x1 + 7x2 - x3 + x4
.
运筹学第10讲:整数规划(一)
例5 (P141-例11)
注意可行域是否存在!

第10讲:整数规划(一) 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数14
  • 收藏数0 收藏
  • 顶次数0
  • 上传人xwhan100
  • 文件大小0 KB
  • 时间2015-06-02