第7章整数规划ppt课件.ppt

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

1、第七章整数规划§1整数规划的图解法§2整数规划的计算机求解§3整数规划的应用§4整数规划的分枝定界法§7.1引言在工程设计和企业管理中，常会遇到要求决策变量取离散的非负整数值的线性规划问题。例如，最优调度的车辆数，设置的销售网点数，指派工作的人数等。这类问题在形式上与线性规划类似，只是比线性规划增加了某些约束条件，来限制全部或部分决策变量必须取离散的非负整数值。我们称之为整数线性规划问题，也经常简称为整数规划问题。在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；如果有一部分变量为非负整数，则称之为混合整数规划问题。所有决策变量均要求为0或1，则称之为纯0—1

2、整数规划。部分决策变量要求为0或1，则称之为混合0—1整数规划。整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。例7-1求下列问题：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整数值§7.2整数规划的图解法O1234567891054321x1x2I(2,4)B(9.2,2.4)AD可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4)Z0=58.8，而原整数规划最优解I(2,

3、4)Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。EFGHIJO1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如把可行域分解成五个互不相交的子问题P1P2P3P4P5之和,P3P5的定义域都是空集,而放弃整数要求后P1最优解I(2,4),Z1=58P2最优解(6,3),Z2

4、=57,P4最优解(9,2),Z4=53P1P2P4X12X16X23X22X13X17X24X23P1P5P4P2P3P性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。例2：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x1,x2,x3≥0且为整数§7.3整数规划的计算机求解例3：Maxz=3x1+x2+3x3s.t.-x1+2x2+

5、x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0,x1，x3为整数,x3为0-1变量§7.4整数规划的应用一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北区由A8，A9，A10三个点中至少选两个。Aj各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万

6、元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?A1A2A3A4A5A6A7A8A9A10投资额10012015080709080140160180利润36405022203025485861解：设：0--1变量xi=1(Ai点被选用）或0(Ai点没被选用）。这样我们可建立如下的数学模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720x1+x2+x3≤2x4

7、+x5≥1x6+x7≥1x8+x9+x10≥2xj≥0且xj为0--1变量，i=1,2,3,……,100-1变量的概念0-1变量：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时是否取某个特定方案。x=1当决策取方案P时0当决策不取方案P时固定费用问题例：有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。产品资源ⅠⅡⅢ资源量A248500B234300C123100单件可变费用456固定费用100150200单价81