《管理运筹学第8章整数规划ppt课件》由会员分享，可在线阅读，更多相关《管理运筹学第8章整数规划ppt课件（25页珍藏版）》请在金锄头文库上搜索。
1、管管 理理 运运 筹筹 学学第八章第八章 整数规划整数规划1整数规划的图解法2整数规划的计算机求解3整数规划的运用4整数规划的分枝定界法管管 理理 运运 筹筹 学学第八章第八章 整数规划整数规划求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处置都能处理的，而要用整数规划的方法加以处理。在整数规划中，假设一切的变量都为非负整数，那么称为纯整数规划问题；假设有一部分变量为负整数，那么称之为混合整数规划问题。在整数规划中，假设变量的取值只限于0和1，这样的变量我们称之为0-1变量。在纯整数规划和混合整数规划问题中，假设一切的变量都为0-1变量，那么称之为0-1规划。管管 理
2、理 运运 筹筹 学学1 1 整数整数规划的划的图解法解法例例1. 某公司某公司拟用集装箱托运甲、乙两种用集装箱托运甲、乙两种货物，物，这两种两种货物每件的体物每件的体积、分量、可分量、可获利利润以及托运所受限制如表所示。以及托运所受限制如表所示。甲种甲种货物至多托运物至多托运4件，件，问两种两种货物各托运多少件，可使物各托运多少件，可使获得利得利润最大。最大。解：解：设x1 、 x2分分别为甲、乙两种甲、乙两种货物托运的件数，建立模型物托运的件数，建立模型 目的函数：目的函数： Max z = 2x1 +3 x2 约束条件：束条件： s.t. 195 x1 + 273 x2 5 4 x1 +
3、40 x2 140 x1 4 x1，x2 0 为整数。整数。假假设去掉最后一个去掉最后一个约束，就是一个束，就是一个线性性规划划问题。利用。利用图解法，解法，货物每件体积立方英尺每件分量百千克每件利润百元甲乙19527344023托运限制5140管管 理理 运运 筹筹 学学得到线性规划的最优解为x1=2.44,x2=3.26,目的函数值为14.66。由图表可看出，整数规划的最优解为x1=4,x2=2,目的函数值为14。性质1：任何求最大目的函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目的函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目的函数值大于
4、或等于相应的线性规划的最小目的函数值。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=61 1 整数整数规划的划的图解法解法1 1 整数整数规划的划的图解法解法管管 理理 运运 筹筹 学学例例2 2： Max z = 3x1 + x2 + 3x3 Max z = 3x1 + x2 + 3x3 s.t. s.t. -x1 + 2x2 + x3 4 -x1 + 2x2 + x3 4 4x2 -3x3 2 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1 -3x2 + 2x3 3 x1,x2,x3 0 x1,x2,x3 0 为整整数数例3： Max z
5、= 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x3 1 x1,x2,x3 0 x1，x3 为整数 x3 为0-1变量用软件求解得：x1=5x2=2x3=2用软件求解得：x1=4x2=1.25x3=1z=16.252 2 整数整数规划的划的计算机求解算机求解管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用一、投资场所的选择例4、京成畜产品公司方案在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j1，2，3，10)可供选择，思索到各地域居民的消费程度及居民居住密集度，规定：在东区由
6、A1，A2，A3三个点至多项选择择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北区由A8，A9，A10三个点中至少选两个。Aj各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万元)。但投资总额不能超越720万元，问应选择哪几个销售点，可使年利润为最大?管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用解：解：设：0-1变量量 xi = 1 (Ai 点被点被选用或用或 0 (Ai 点没被点没被选用。用。 这样我我们可建立如下的数学模型：可建立如下的数学模型：Max z =36x1+40x2+50x3+22x4+20
7、x5+30x6+25x7+48x8+58x9+61x10s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 且且xj 为0-1变量，量，i = 1,2,3,10管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用二、固定本钱问题例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不思索固定费用，每种容器售出一只所得的利润
8、分别为4万元、5万元、6万元，可运用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不论每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。如今要制定一个消费方案，使获得的利润为最大。管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的消费数量。各种容器的固定费用只需在消费该种容器时才投入，为了阐明固定费用的这种性质，设yi=1(当消费第i种容器,即xi0时)或0当不消费第i种容器即xi=0时。引入约束xiMyi，i=1，2，3，M充
9、分大，以保证当yi=0时，xi=0。这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x35002x1+3x2+4x3300x1+2x2+3x3100xiMyi，i=1，2，3，M充分大xj0yj为0-1变量，i=1,2,3管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用三、指派问题三、指派问题 有有 n n 项不同的义务，恰好项不同的义务，恰好 n n 个人可分别承当这些义务，但由个人可分别承当这些义务，但由于每人专长不同，完成各项义务的效率等情况也不同。现假设必需于每人专长不同，完成各项义务的效率等情况
10、也不同。现假设必需指派每个人去完成一项义务，怎样把指派每个人去完成一项义务，怎样把 n n 项义务指派给项义务指派给 n n 个人，使个人，使得完成得完成 n n 项义务的总的效率最高，这就是指派问题。项义务的总的效率最高，这就是指派问题。 例例6 6有四个工人，要分别指派他们完成四项不同的任务，每有四个工人，要分别指派他们完成四项不同的任务，每人做各项任务所耗费的时间如下表所示，问应如何指派任务，才干人做各项任务所耗费的时间如下表所示，问应如何指派任务，才干使总的耗费时间为最少。使总的耗费时间为最少。管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用解：引入解：引入01变量量 x
11、ij，并令，并令 xij = 1(当指派第当指派第 i人去完成第人去完成第j项任任务时)或或0当不指派第当不指派第 i人去完成第人去完成第j项任任务时)这可以表示可以表示为一个一个0-1整数整数规划划问题：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一甲只能干一项任任务) x21+ x22+ x23+ x24= 1 (乙只能干一乙只能干一项任任务) x31+ x32+ x3
12、3+ x34= 1 (丙只能干一丙只能干一项任任务) x41+ x42+ x43+ x44= 1 (丁只能干一丁只能干一项任任务) x11+ x21+ x31+ x41= 1 ( A任任务只能一人干只能一人干) x12+ x22+ x32+ x42= 1 ( B任任务只能一人干只能一人干) x13+ x23+ x33+ x43= 1 ( C任任务只能一人干只能一人干) x14+ x24+ x34+ x44= 1 ( D任任务只能一人干只能一人干) xij 为0-1变量，量，i,j = 1,2,3,4 * * * 求解可用求解可用软件中整数件中整数规划方法。划方法。 管管 理理 运运 筹筹 学学
13、3 3 整数整数规划的运用划的运用四、分布系统设计四、分布系统设计例例7某企业在某企业在 A1 地已有一个工厂，其产品的消费才干为地已有一个工厂，其产品的消费才干为 30 千箱，为了千箱，为了扩展消费，计划在扩展消费，计划在 A2，A3，A4，A5地中再选择几个地方建厂。知在地中再选择几个地方建厂。知在 A2 ， A3，A4，A5地建厂的固定本钱分别为地建厂的固定本钱分别为175千元、千元、300千元、千元、375千千元、元、500千元，另外，千元，另外， A1产量及产量及A2，A3，A4，A5建成厂的产量，那时建成厂的产量，那时销地的销量以及产地到销地的单位运价销地的销量以及产地到销地的单位
14、运价(每千箱运费每千箱运费)如下表所示。如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定本问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定本钱和总的运输费用之和最小钱和总的运输费用之和最小? b) 假设由于政策要求必需在假设由于政策要求必需在A2，A3地建一个厂，应在哪几个地方建厂地建一个厂，应在哪几个地方建厂? 管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用解：解： a) 设 xij为从从Ai 运往运往Bj 的运的运输量量(单位千箱位千箱)， yk = 1(当当Ak 被被选中中时)或或0当当Ak 没被没被选中中时),k =2,3,4,5
15、这可以表示可以表示为一个整数一个整数规划划问题：Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53其中前其中前4项为固定投固定投资额，后面的，后面的项为运运输费用。用。s.t. x11+ x12+ x13 30 ( A1 厂的厂的产量限制量限制) x21+ x22+ x23 10y2 ( A2 厂的厂的产量限制量限制) x31+ x32+ x33 20y3 ( A3 厂的厂的产量限制量限制) x41+ x42+ x43 30y4
16、 ( A4 厂的厂的产量限制量限制) x51+ x52+ x53 40y5 ( A5 厂的厂的产量限制量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制地的限制) xij 0，i = 1,2,3,4,5； j = 1,2,3， yk 为0-1变量，量，k =2,3,4,5。 * * * 求解可用求解可用软件中整数件中整数规划方法。划方法。 管管 理理 运运 筹筹 学学3 3
17、 整数整数规划的运用划的运用五、投资问题五、投资问题 例例8 8某公司在今后五年内思索给以下的工程投资。知：某公司在今后五年内思索给以下的工程投资。知：工程工程A A：从第一年到第四年每年年初需求投资，并于次年末回收本利：从第一年到第四年每年年初需求投资，并于次年末回收本利115%115%， 但要求第一年投资最低金额为但要求第一年投资最低金额为4 4万元，第二、三、四年不限；万元，第二、三、四年不限；工程工程B B：第三年初需求投资，到第五年末能回收本利：第三年初需求投资，到第五年末能回收本利128128，但规定最低投，但规定最低投资金额为资金额为3 3万元，最高金额为万元，最高金额为5 5万
18、元；万元； 工程工程 C C：第二年初需求投资，到第五年末能回收本利：第二年初需求投资，到第五年末能回收本利140%140%，但规定其投，但规定其投资额或为资额或为2 2万元或为万元或为4 4万元或为万元或为6 6万元或为万元或为8 8万元。万元。 工程工程 D D：五年内每年初可购买公债，于当年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%6%，此项，此项投资金额不限。投资金额不限。 该部门现有资金该部门现有资金1010万元，问它应如何确定给这些工程的每年投资万元，问它应如何确定给这些工程的每年投资额，额，使到第五年末拥有的资金本利总额为最大使到第五年末拥有的资金本利总
19、额为最大? ?管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用解：解：1) 设xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分分别表示第表示第 i 年年初年年初给工程工程A，B，C，D的投的投资额； 设yiA， yiB，是，是01变量，并量，并规定取定取 1 时分分别表示第表示第 i 年年给A、B投投资，否那么取否那么取 0 i = 1, 2, 3, 4, 5。 设yiC 是非是非负整数整数变量，并量，并规定：第定：第2年投年投资C工程工程8万元万元时，取，取值为4；第第 2年投年投资C工程工程6万元万元时，取，取值3；第；第2年投年投资C工程工程4万元万元时，取，
20、取值2；第第2年投年投资C工程工程2万元万元时，取，取值1；第；第2年不投年不投资C工程工程时，取，取值0； 这样我我们建立如下的决策建立如下的决策变量：量： 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 A x1A x2A x3A x4A B x3B C x2C=20000y2C D x1D x2D x3D x4D x5D 管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用2 2约束条件：束条件：第一年：年初有第一年：年初有100000100000元，元，D D工程在年末可收回投工程在年末可收回投资，故第一年年初，故第一年年初应把全部把全部资金金投出去，于是投出去，
21、于是 x1A+ x1D = 100000 x1A+ x1D = 100000；第二年：第二年：A A的投的投资第二年末才可收回，故第二年年初的第二年末才可收回，故第二年年初的资金金为1.06x1D1.06x1D，于是，于是x2A+x2C+x2D = 1.06x1Dx2A+x2C+x2D = 1.06x1D；第三年：年初的第三年：年初的资金金为 1.15x1A+1.06x2D 1.15x1A+1.06x2D，于是，于是 x3A+x3B+x3D = 1.15x1A+ x3A+x3B+x3D = 1.15x1A+ 1.06x2D1.06x2D；第四年：年初的第四年：年初的资金金为 1.15x2A+1
22、.06x3D 1.15x2A+1.06x3D，于是，于是 x4A + x4D = 1.15x2A+ 1.06x3D x4A + x4D = 1.15x2A+ 1.06x3D；第五年：年初的第五年：年初的资金金为 1.15x3A+1.06x4D 1.15x3A+1.06x4D，于是，于是 x5D = 1.15x3A+ 1.06x4D x5D = 1.15x3A+ 1.06x4D。 关于工程关于工程A A的投的投资额规定定: x1A 40000y1A : x1A 40000y1A ，x1A 200000y1A x1A 200000y1A ，200000200000是是足足够大的数；保大的数；保证当
23、当 y1A = 0 y1A = 0时， x1A = 0 x1A = 0 ；当；当y1A = 1y1A = 1时，x1A 40000 x1A 40000 。 关于工程关于工程B B的投的投资额规定定: x3B 30000y3B : x3B 30000y3B ，x3B 50000y3B x3B 50000y3B ； 保保证当当 y3B = 0 y3B = 0时， x3B = 0 x3B = 0 ；当；当y3B = 1y3B = 1时，50000 x3B 30000 50000 x3B 30000 。 关于工程关于工程C C的投的投资额规定定: x2C = 20000y2C : x2C = 2000
24、0y2C ，y2C = 0y2C = 0，1 1，2 2，3 3，4 4。管管 理理 运运 筹筹 学学3 3 整数整数规划的运用划的运用3 3目的函数及模型：目的函数及模型： Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D s.t. x1A+ x1D = 100000 s.t. x1A+ x1D = 100000； x2A+x2C+x2D = 1.06x1D x2A+x2C+x2D = 1.06x1D； x3A+x3B+x3D = 1.15x1A+ 1.06x2D x
25、3A+x3B+x3D = 1.15x1A+ 1.06x2D； x4A+x4D = 1.15x2A+ 1.06x3D x4A+x4D = 1.15x2A+ 1.06x3D； x5D = 1.15x3A+ 1.06x4D x5D = 1.15x3A+ 1.06x4D； x1A 40000y1A x1A 40000y1A ， x1A 200000y1A x1A 200000y1A ， x3B 30000y3B x3B 30000y3B ， x3B 50000y3B x3B 50000y3B ； x2C = 20000y2C x2C = 20000y2C ， yiA yiA， yiB = 0 yiB
26、= 0 或或 1 1，i = 1,2,3,4,5i = 1,2,3,4,5 y2C = 0 y2C = 0，1 1，2 2，3 3，4 4 xiA xiA ，xiB xiB ，xiC xiC ，xiD 0 ( i = 1xiD 0 ( i = 1、2 2、3 3、4 4、5 5 管管 理理 运运 筹筹 学学4 4 整数整数规划的分枝定界法划的分枝定界法 分枝定界法是求解整数规划的一种常用的有效的方分枝定界法是求解整数规划的一种常用的有效的方法，它既能处理纯整数规划的问题，又能处理混合整数法，它既能处理纯整数规划的问题，又能处理混合整数规划的问题。大多数求解整数规划的商用软件就是基于规划的问题。
27、大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。分枝定界法而编制成的。 分枝定界法是先求解整数规划的线性规划问题。假分枝定界法是先求解整数规划的线性规划问题。假设其最优解不符合整数条件，那么求出整数规划的上下设其最优解不符合整数条件，那么求出整数规划的上下界，用添加约束条件的方法，把相应的线性规划的可行界，用添加约束条件的方法，把相应的线性规划的可行域分成子区域称为分枝，再求解这些子区域上的线域分成子区域称为分枝，再求解这些子区域上的线性规划问题，不断减少整数规划的上下界的间隔，最后性规划问题，不断减少整数规划的上下界的间隔，最后得整数规划的最优解。得整数规划的最优解。 下面以例下面
28、以例9 9予以阐明。予以阐明。管管 理理 运运 筹筹 学学4 4 整数整数规划的分枝定界法划的分枝定界法例9用分枝定界法求解整数规划Max2x1+3x2s.t.195x1+273x254x1+40x2140x14x1,x20且x1,x2为整数解:(一)先求出以下线性规划的解：Max2x1+3x2s.t.195x1+273x254x1+40x2140x14x1,x20得z1=14.66,x1=2.44,x2=3.26(二)确定整数规划的最优目的函数值z*初始上界和下界z。分析后，知道=14.66，由察看法得下界z=13当x1=2,x2=3时。管管 理理 运运 筹筹 学学4 4 整数整数规划的分枝
29、定界法划的分枝定界法(三)将一个线性规划问题分为两枝，并求解。 可由x12或x13中取值。将线性规划1分解为两支，如下： 线性规划2： Max 2x1+3x2 s.t. 195x1+273x25 4x1+ 40x2140 x1 4 x2 2 x1,x2 0 解得z2=13.90,x1=2,x2=3.30 线性规划3： Max 2x1+3x2 s.t. 195x1+273x25 4x1+ 40x2140 x1 4 x1 3 x1,x2 0 解得z3=14.58,x1=3,x2=2.86管管 理理 运运 筹筹 学学4 4 整数整数规划的分枝定界法划的分枝定界法(四)修正整数规划的最优目的函数的上下
30、界。 经分析，将上界 =14.66修正为 =14.58，z=13。(五)在线性规划2和线性规划3中选择一个上界最大的线性规划，即线性规划3，进行分枝。 线性规划3分解为线性规划4和线性规划5，如下： 线性规划4： Max 2x1+3x2 s.t. 195x1+273x25 4x1+ 40x2140 x1 4 x1 3 x2 2 x1,x2 0 解得z4=14,x1=4,x2=2 线性规划5： Max 2x1+3x2 s.t. 195x1+273x25 4x1+ 40x2140 x1 3 x2 3 x1,x2 0 无可行解管管 理理 运运 筹筹 学学4 4 整数整数规划的分枝定界法划的分枝定界法
31、(六)进一步修正整数规划最优目的函数值z*的上下界。 从线性规划2，4，5中修正上下界。分析后，可得 =14， z=14。都取线性规划2，4，5中的整数可行解的目的函数值的最大值。性质2： 当整数规划的最优目的函数值z*的上界 等于其下界z时，该整数规划的最优解曾经被求出。这个整数的最优解即为其目的函数值取此下界的对应线性规划的整数可行解。管管 理理 运运 筹筹 学学4 4 整数整数规划的分枝定界法划的分枝定界法用图8-2表例如9的求解过程与求解结果线性规划线性规划1Z1=14.66X1=2.44X2=3.26z=13, =14.66 z=13, =14.66 线性规划线性规划2Z2=13.9
32、0X1=2X2=3.30线性规划线性规划3Z3=14.58X1=3X2=2.86线性规划线性规划4Z4=14.00X1=4X2=2线性规划线性规划5无可行解无可行解X12X13X22X23z=13, =14.58 z=13, =14.58 z=14, =14z=14, =14图图8-28-2管管 理理 运运 筹筹 学学4 4 整数整数规划的分枝定界法划的分枝定界法 从以上解题过程可得用分枝定界法求解目的函数值最大的整数规划的从以上解题过程可得用分枝定界法求解目的函数值最大的整数规划的步骤，我们将求解的整数规划问题称为步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题，将与其相对应
33、的线性规划问题称为称为B： 第一步：求解问题第一步：求解问题B，可得以下情况之一：，可得以下情况之一： 1.B没有可行解，那么没有可行解，那么A也没有可行解，求解过程停顿。也没有可行解，求解过程停顿。 2.B有最优解，且符合问题有最优解，且符合问题A的整数条件，那么的整数条件，那么B的最优解即为的最优解即为A的最的最优解，求解过程停顿。优解，求解过程停顿。 3.B有最优解，但不符合有最优解，但不符合A的整数条件，记其目的函数值为的整数条件，记其目的函数值为z1。 第二步：确定第二步：确定A的最优目的函数值的最优目的函数值z*的上下界，其上界即为的上下界，其上界即为z1, =z1,再用察看法找到
34、再用察看法找到A的一个整数可行解，求其目的函数值作为的一个整数可行解，求其目的函数值作为z*的下界，记的下界，记为为z 。 第三步：判别第三步：判别 能否等于能否等于z 。假设相等，那么整数规划最优解即为其。假设相等，那么整数规划最优解即为其目的函数值等于目的函数值等于z的的A的那个整数可行解；否那么进展第四步。的那个整数可行解；否那么进展第四步。管管 理理 运运 筹筹 学学4 4 整数整数规划的分枝定界法划的分枝定界法 第四步：在第四步：在B的最的最优解中解中选一个最一个最远离整数要求的离整数要求的变量，无妨量，无妨设此此变量量为xj，以，以bj表示小于表示小于bj的最大整数，构造以下两个的
35、最大整数，构造以下两个约束条件，并参与束条件，并参与问题B，得到，得到B的两个分枝的两个分枝B1和和B2。xj bj和和xj bj+1 第五步：求解第五步：求解B1和和B2 。修正。修正A问题的最的最优目的函数目的函数值z*的上下界，的上下界， 和和z 。 第六步：比第六步：比较和剪枝。各分枝的最和剪枝。各分枝的最优目的函数目的函数值中假中假设有小于有小于z者，那者，那么剪掉么剪掉这枝用打枝用打表示，即以后不再思索了。假表示，即以后不再思索了。假设大于大于 ，那么不符合，那么不符合整数条件，那么反复第三步至第六步，直至整数条件，那么反复第三步至第六步，直至 =z，求出最，求出最优解解为止。止。 对于求目的函数于求目的函数值最小的整数最小的整数规划的求解步划的求解步骤与上述步与上述步骤根本根本类似。似。
