云南农业大学经济管理学院主讲佘迎红课件.ppt
《云南农业大学经济管理学院主讲佘迎红课件.ppt》由会员分享,可在线阅读,更多相关《云南农业大学经济管理学院主讲佘迎红课件.ppt(66页珍藏版)》请在三一文库上搜索。
1、1,云南农业大学经济管理学院 主讲: 佘迎红,E-mail: Tel: 13888581179,3.1 整数规划数学模型 Mathematical Model of IP 3.2 整数规划的求解 Solving Integer Programming 3.3 01规划的求解 Solving Binary Integer Programming,第3章 整 数 规 划 Integer Programming,3,线性规划的决策变量取值可以是任意非负实数,但许多实际问题中,只有当决策变量的取值为整数时才有意义。 例如,产品的件数、机器的台数、装货的车数、完成工作的人数等,分数或小数解显然是不合理
2、的。 对某一个项目要不要投资的决策问题,可选用一个逻辑变量 x,当x=1表示投资,x=0表示不投资。,3.1 整数规划的数学模型,纯整数规划(IP):xj全部取整数 混合整数规划(MIP):xj部分取整数 0-1整数规划(BIP):整数变量只能取0或1,分类,4,【例3-1 】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品,每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件,才能使所装物品的总价值最大?,表3-1,【解】设甲、乙两种物品各装x1、x2件,则数学模型为:,(3-1),3.1 整数规划的数学模型,5,【补充例】投资决策问题。某公司有5个项
3、目被列入投资计划,各项目的投资额和期望的投资收益如下表,3.1 整数规划的数学模型,该公司只有600万元资金可用于投资,由于技术上的原因, 投资受到以下约束: (1)在项目1、2和3中必须且只有一项被选中; (2)项目3和项目4最多只能选中一项; (3)项目5被选中的前提是项目1必须被选中。 如何在上述条件下选择一个最好的投资方案,使投资收益最大?,6,【解】设xj 为选择第 j(j=1,2,3,4,5)个项目的决策,3.1 整数规划的数学模型,7,【例3-2 】在例3-1中,假设此人还有一只旅行箱,最大载重量为12公斤,其体积是0.02m3。背包和旅行箱只能选择其一,建立下列几种情形的数学模
4、型,使所装物品价值最大。 (1)所装物品不变; (2)如果选择旅行箱,则只能装载丙和丁两种物品,每件物品的重量、体积和价值如下表所示,3.1 整数规划的数学模型,8,【解】(1)引入01变量 yj,令,j=1,2分别是采用背包及旅行箱装载。,3.1 整数规划的数学模型,(3-2),此问题也可以建立两个整数规划模型。,9,(2)由于不同载体所装物品不一样,数学模型为,3.1 整数规划的数学模型,其中M为充分大的正数。 当使用背包时( y1=1, y2=0 ),式(b)和(d)是多余的; 当使用旅行箱时( y1=0, y2=1 ),式(a)和(c)是多余的。,10,(1)右端常数是k个值中的一个时
5、,类似式(3-2)的约束条件为,3.1 整数规划的数学模型,同样可以讨论对于有m个条件互相排斥、有m (m、m)个条件起作用的情形。,11,(2)对于m 个(组)条件中有k(m)个(组)起作用时,类似式(3-3)的约束条件写成,这里yi=1表示第 i 组约束不起作用(如y1=1式(3-3b)、(3-3d)不起作用),yi=0表示第 i个约束起作用。当约束条件是“”符号时右端常数项应为,3.1 整数规划的数学模型,12,【例3-3】试引入01变量将下列各题分别表达为一般线性约束条件 (1)x1+x26或4x1+6x210或2x1+4x220 (2)若x15,则x20,否则x28 (3)x2取值0
6、,1,3,5,7,【解】 (1)3个约束只有1个起作用,或,3.1 整数规划的数学模型,如果要求至少一个条件满足,模型如何改变?,13,(3)右端常数是5个值中的1个,(2)两组约束只有一组起作用,3.1 整数规划的数学模型,(1) (2) (3) (4),14,【例3-4】企业计划生产4000件某种产品,该产品可自己加工、外协加工任意一种形式生产。已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量(件)限制如表32所示,怎样安排产品的加工使总成本最小。,表 32,3.1 整数规划的数学模型,15,【解】设xj为采用第 j(j=1,2,3)种方式生产的产品数量,生产费用
7、为,3.1 整数规划的数学模型,其中kj是固定成本,cj是可变成本。 设01变量yj,16,(3-4),用WinQSB软件求解得到: X(0,2000,2000)T ,Y(0,1,1)T,Z=25400,3.1 整数规划的数学模型,配合目标,使得只有选用第j 种加工方式才产生相应成本,不选用第j 种加工方式就没有成本。,17,整数规划的一般形式:,称线性规划模型,(),(),(LP),为()的松弛问题。,每一个整数规划都对应一个松弛问题,整数规划比它的松弛问题约束得更紧。,部分或全部取整,3.1 整数规划的数学模型,18,3.1 整数规划的数学模型,习题3.4 【解】令运动员甲、乙、丙、丁、戊
8、编号为1、2、3、4、5,项目 高低杠、平衡木、鞍马、自由体操编号为1、2、3、4。 设,19,max=8.6x11+9.7x12+8.9x13+9.4x14+9.2x21+8.3x22+8.5x23+8.1x24 +8.8x31 +8.7x32+9.3x33+9.6x34+8.5x41+7.8x42+9.5x43+7.9x44+8x51+9.4x52 +8.2x53+7.7x54 x11+x12+x13+x143 x21+x22+x23+x243 x31+x32+x33+x343 x41+x42+x43+x443 x51+x52+x53+x543 x11+x21+x31+x41+x511 x
9、12+x22+x32+x42+x521 x13+x23+x33+x43+x531 x14+x24+x34+x44+x541 x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43 +x44+x51+x52+x53+x54=10 xij=0 或 1 (i=1,2,3,4,5;j=1,2,3,4),3.1 整数规划的数学模型,20,1. 整数规划模型的特征 2. 什么是纯(混合)整数规划 3. 01规划模型的应用,下一节:纯整数规划的求解,3.1 整数规划的数学模型,21,整数规划解的特点 整数规划()的可行解集是其松弛问题()的可行
10、解集的子集。线性规划问题的可行解集是一个凸集(稠密的),但整数规划的可行解集不是凸集(离散型)。 如果松弛问题()的最优解是整数解,则一定是整数规划()的最优解。 整数规划()的最优值不会优于松弛问题()的最优值。,3.2 整数规划的求解,22,3.2 整数规划的求解,图3-1,点B为最优解 X(3.57,7.14) Z35.7,用图解法求解例3-1的松弛问题,整数规划问题的可行解集是图中可行域内的整数点。,23,松弛问题的最优解 X(3.57,7.14), Z35.7 “四舍五入”得 X=(4,7) 不是可行解; 用“取整”法来解时,X=(3,7)虽属可行解,但代入目标函数得Z=33, 并非
11、最优。 该整数规划问题的最优解是X=(5,5),最优值是Z=35 即甲、乙两种物品各装5件,总价值35元。,由图31知,点(5,5)不是LP可行域的顶点,直接用图解法或单纯形法都无法求出整数规划问题的最优解,因此求解整数规划问题的最优解需要采用其它特殊方法。,3.2 整数规划的求解,24,【例3-5 】用分支定界法求解例3-1,【解】先求对应的松弛问题,用图解法得到最优解X(3.57,7.14), Z0=35.7,3.2.1 分支定界法,25,8.33,10,松弛问题LP0的最优解X=(3.57, 7.14), Z0=35.7,x1,x2,o,A,B,C,10,3.2.1 分支定界法,10,1
12、0,x1,x2,0,A,B,C,LP1,LP2,3,4,LP1:X=(3, 7.6), Z1=34.8,LP2:X=(4, 6.5), Z2=35.5,10,10,x1,0,A,C,LP1,3,4,LP1:X=(3, 7.6), Z1=34.8,x1,B,6,7,LP3:X=(4.33, 6), Z3=35.33,LP2,x1,x1,LP4:X=(4, 6), Z4=34,LP5:X=(5, 5), Z5=35 此为原IP最优解,5,29,尽管LP1的解中x2不为整数,但Z5Z1,因此LP5的最优解就是原整数规划的最优解。若Z5Z1 ,则要对LP1进行分支。,3.2.1 分支定界法,30,上述
13、分枝过程可用下图表示,LP0: X=(3.57, 7.14),Z0=35.7,LP1: X=(3, 7.6) Z1=34.8,LP2: X=(4, 6.5) Z2=35.5,x13,x14,LP3: X=(4.33, 6) Z3=35.33,x26,LP4: X=(4, 6) Z4=34,LP5: X=(5, 5) Z5=35,x14,x15,无可行解,x27,最优解,3.2.1 分支定界法,31,分支定界法的步骤:,1. 求整数规划的松弛问题最优解; 2. 若松弛问题的最优解满足整数要求,得到整数规划的最优解,否则转下一步;,3.2.1 分支定界法,3. 任意选一个非整数解的变量xi,在松弛
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 云南 农业大学 经济 管理学院 主讲 佘迎红 课件
链接地址:https://www.31doc.com/p-3108794.html