章整数规划.docVIP

  1. 1、本文档共20页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
章整数规划

整数规划 Chapter 3 Integer Programming 本章内容提要 本章介绍整数规划模型以及整数规划的求解方法。 学习本章要求掌握以下要点: 掌握整数规划模型的建模方法 1、变量为整数的简单整数规划模型; 2、变量为0-1值的0-1规划模型; 3、用0-1变量以及相应的约束条件,定义变量之间逻辑关系的整数规划模型。 了解求解整数规划的两种方法—分支定界法和割平面法。 §3.1 整数规划模型 变量取整数值的规划称为整数规划。所有变量都取整数的规划称为纯整数规划,部分变量取整数的规划称为混合整数规划。所有变量都取0、1两个值的规划称为0-1规划,部分变量取0、1两个值的规划称为0-1混合规划。 线性规划和整数规划的关系,我们用以下例子说明。 设线性规划问题为 max z= x1 +4x2 s.t. 14x1 +42x2 ≤196 -x1 +2x2 ≤ 5 x1 x2 ≥0 相应的整数规划问题为 max z= x1 +4x2 s.t. 14x1 +42x2 ≤196 -x1 +2x2 ≤ 5 x1 x2 ≥0 x1、x2为非负整数 线性规划的可行域如图3.1中阴影部分所示,由图解法可知,线性规划的最优解位于图中的A点,即(x1,x2)=(13/5,19/5)=(2.6,3.8),线性规划最优解的目标函数值为z=89/5=17.8。 而相应的整数规划的可行解是图中线性规划可行域中整数网格的交点。整数规划的最优解位于图的B点,即(x1,x2)=(5,3),整数规划最优解的目标函数值为z=17。 由以上例子可以看到,简单地将线性规划的非整数的最优解,用四舍五入或舍去尾数的办法得到整数解,一般情况下并不能得到整数规划的最优解。整数规划的求解方法要比线性规划复杂得多。 有以下几类整数规划模型:第一类是根据问题要求,定义模型中若干或者所有变量为整数变量;第二类是定义模型中若干或者所有变量为0-1变量;第三类是利用包含0-1变量的约束条件来定义变量之间的逻辑关系。下面是几个属于这两类问题的例子。 例3.1 背包问题 有一只背包,最大装载重量为W公斤,现有k种物品,每种物品数量无限。第i种物品每件重量为wi公斤,价值为vi元。每种物品各取多少件装入背包,使其中物品的总价值最高。 设取第i种物品xi件(i=1,2,…,k),则规划问题可以写为 max z= v1x1 +v2x2 +… +vkxk s.t. w1x1 +w2x2 +… +wkxk ≤W x1, x2, … xk ≥0 x1, x2, … xk为整数 如果忽略变量为整数的要求,这个问题成为线性规划问题,k个变量中将只有一个基变量大于0,其余k-1个非基变量都等于0,而且这个大于0的基变量一般情况下是非整数。这样的解显然是没有意义的。例如背包容量为50公斤,三种物品的重量和价值如下表: 表格 1 物 品 1 2 3 单件价值(元/件) 17 72 35 单件总量(公斤/件) 10 41 20 设三种物品分别取x1,x2,x3件,这个背包问题整数规划模型为 max z= 17x1 +72x2 +35x3 s.t. 10x1 +41x2 +20x3 ≤50 x1, x2, x3 ≥0 x1, x2, x3为整数 如果忽略变量的整数要求,以上问题是一个线性规划问题,它的最优解为 x1=0,x2=,x3=0,最优解的目标函数值为 z=72×50÷41=87.8 而整数规划的最优解是 x1=1,x2=0,x3=2,整数规划最优解的目标函数值为z=87。 例3.2 厂址选择问题 在5个地点中选3处建生产同一产品的工厂,在这5个地点建厂所需投资,占用农田,建成以后的生产能力等数据如下表所示。 表格 2 地点 1 2 3 4 5 所需投资(万元) 320 280 240 210 180 占用农田(亩) 20 18 15 11 8 生产能力(万吨) 70 55 42 28 11 现在有总投资800万元,占用农田指标60亩,应如何选择厂址,使建成后总生产能力最大。 设五个0—1变量x1,x2,x3,x4,x5,其中 i=1,2,3,4,5 整数规划模型为 max z= 70x1 +55x2 +42x3 +28x4 +11x5 s.t. 320x1 +280x2 +240x3 +210x4 +180x5 (800 20x1 +18x2 +15x3 +11x4 +8x5 ( 60 x1 +x2 +x3 +x4 +x5 =3 x1 x2 x3 x4 x5= 0,1 这是一个0—1规划问题。这个0-1规划问题的最优解为 x1=1,x2=0,x3=1,x4=

文档评论(0)

panguoxiang + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档