运筹学课件06-整数规划.ppt

《运筹学课件06-整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整数规划IntegerLinearProgramming整数规划的难度远大于一般线性规划1整数规划的模型分支定界法割平面法0－1整数规划指派问题本章主要内容2一、整数规划的模型1、案例：某财团有万元的资金，经初期考察选中个投资项目，每个项目只能投资一个。其中第个项目需投资金额为万元，预计5年后获利万元，问应如何选择项目使得5年后总收益最大？3变量—每个项目是否投资约束—总金额不超过限制目标—总收益最大45某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am，它们的生产能力分别是a1,

2、a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi(i=1.2…m),又有n个地点B1,B2,…Bn需要销售这种产品，其销量分别为b1.b2…bn。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？6设：xij表示从工厂运往销地的运量(i=1.2…m；j=1.2…n),1在Ai建厂又设yi＝（i=1.2…m）0不在Ai建厂模型：7某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需

3、带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。物品12345678910体积200350500430320120700420250100价格15451007050752009020308变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果

4、增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中9约束包裹容量限制必带物品限制选带物品限制10目标函数—未带物品购买费用最小11122、总结：特征—变量整数性要求来源—问题本身的要求；引入逻辑变量需要性质—可行域是离散集合一般整数规划模型13依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划纯整

5、数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数和常数也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。143、IP与LP关系：设整数规划问题如下首先不考虑整数约束，得到线性规划问题且为整数15用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3

6、)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)，(2，3)，(1，4)，(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。16因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：分枝定界法割平面法对于特别的0－1规划问题采用隐枚举法和匈牙利法。170－1整数

7、规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，一般的解法为隐枚举法。例1、求解下列0－1规划问题二、0－1整数规划18对于0－1规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1组合找出，使目标函数达到极值要求就可求得最优解。x1.x2.x3约束条件满足条件Z值(1)(2)(3)(4)是∨否×(0.0.0)0000∨0(0.0.1)－1101∨5(0.1.0)2414∨－2(1.0.0)1110∨3(0.1.1)15×(1.0.1)0211∨8(1.1.0)

8、3×(1.1.1)26×但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。19由上表可知，问题的最优解为X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1是一个可行解，为尽快找到最优解，可将3x1－2x2＋5x3≥5作为一个约束，凡是目标函数值小于5的组合不必讨论，如下表。x1.x2.x3约束条件满足条件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)00000∨0(