第八章-整数规划-《管理运筹学》课件.pptx

1、 1整数规划的图解法整数规划的图解法例 1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表。甲种货物至多托运 4 件，问两种货物各托运多少件，可使获得利润最大。货物每件体积/立方英尺每件重量/百千克每件利润/百元甲19542乙273403托运限制1365140 1整数规划的图解法整数规划的图解法解：设 x1、x2 分别为甲、乙两种货物托运的件数，建立模型目标函数：max z=2x1+3x2约束条件：s.t.195 x1+273 x21 365 (体积限制)x14 4x1+40 x2140 (重量限制)x1,x20,去掉最后一个约束，是一个线性规划问

2、题。为整数x2 1整数规划的图解法整数规划的图解法利用图解法 32101234x12x1+3x2=62x1+3x2=14.662x1+3x2=14线性规划的最优解为 x1=2.44，x2=3.26，目标函数值为 14.66。由图可看出，整数规划的最优解为 x1=4，x2=2，目标函数值为 14.整数规划的最优解不都是相应的线性规划的最优解，通过“四舍五入”、“进一法”或“去尾法”获得。1整数规划的图解法整数规划的图解法 性质 1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值

3、大于或等于相应的线性规划的最小目标函数值。2整数规划的计算机求解整数规划的计算机求解例 2max z=3x1+x2+3x3s.t.x1+2x2+x344x2 3x32 x1 3x2+2x33x1,x2,x30 x1,x2,x3 为整数 2整数规划的计算机求解整数规划的计算机求解用管理运筹学软件求解 2整数规划的计算机求解整数规划的计算机求解 max z=3x1+x2+3x3s.t.x1+2x2+x34 4x2 3x32 x1 3x2+2x33 x1,x2,x30 x1 为整数,x3 为 01 变量例 3 2整数规划的计算机求解整数规划的计算机求解用管理运筹学软件求解 3整数规划的应用整数规划的

4、应用一、投资场所的选择例 4京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有 10 个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由 A1，A2，A3 三个点至多选择两个；在西区由 A4，A5 两个点中至少选一个；在南区由 A6，A7 两个点中至少选一个；在北区由 A8，A9，A10 三个点中至少选两个。3整数规划的应用整数规划的应用 Aj 各点的设备投资及每年可获利润由于地点不同而不同，预测情况如（单位：万元）。但投资总额不超过 720 万元，问应选择哪几个销售点，可使年利润最大？A1A2A3A4A5A6A7A8A9

5、A10投资额 100 12015080709080140160180利润36405022203025485861 3整数规划的应用整数规划的应用解：设：01 变量 xi=1(Ai 点被选用）或 0(Ai 点没被选用）。建立数学模型：max z=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t.100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1+x2+x3 2 x4+x5 1 x6+x7 1 x8+x9+x10 2 xi 0,且 xi

6、为 0-1 变量,i=1,2,3,10在东区由 A1，A2，A3 三个点至多选择两个在西区由 A4，A5 两个点中至少选一个在南区由 A6，A7 两个点中至少选一个在北区由 A8，A9，A10 三个点中至少选两个投资额约束 3整数规划的应用整数规划的应用应用“管理运筹学软件”求解：最优目标函数值为 245。最优解为:x1=1,x2=1,x3=0,x4=0,x5=1,x6=1,x7=0,x8=0,x9=1,x10=1 3整数规划的应用整数规划的应用二、固定成本问题例 5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表。不考虑固

7、定费用，每种容器单位利润分别为 4 万元、5 万元、6 万元，可使用的金属板 500 吨，劳动力 300 人/月，机器100 台/月，此外只要生产，须支付固定费用：小号是 l00 万元，中号为 150 万元，大号为 200 万元。制定一个生产计划，使获利最大。3整数规划的应用整数规划的应用 资源 小号容器中号容器大号容器金属板/t248劳动力/（人/月）234机器设备/（台/月）123 3整数规划的应用整数规划的应用解：整数规划问题 设 x1，x2，x3 分别为小号、中号和大号容器的生产数量。固定费用：设 yi=1（当生产第 i 种容器，即 xi0 时）或 0（当不生产第 i种容器即 xi=0

8、 时）。引入约束 xi M yi ，i=1，2，3，M 充分大。3整数规划的应用整数规划的应用建立数学模型：max z=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3 500 （金属板约束）2x1+3x2+4x3 300（劳动力约束）x1+2x2+3x3 100（机器设备约束）xi M yi ，i=1，2，3，M 充分大 xi 0，yi 为 0-1 变量，i=1,2,3软件计算：最大目标函数值为300，最优解为x1=100，x2=0，x3=0。3整数规划的应用整数规划的应用三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人

9、特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使完成 n 项任务的总效率最高，即指派问题。3整数规划的应用整数规划的应用例 6有四个工人，分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如表，应如何指派工作，才能使总消耗时间最少。工作所需时间/小时工人ABCD甲15182124乙19232218丙26171619丁19212317 3整数规划的应用整数规划的应用解：引入 01 变量 xij，令xij =1(指派第 i 人去完成第 j 项工作)xij =0（不指派第 i 人去完成第 j 项工作）构建01 整数规划问题。

10、3整数规划的应用整数规划的应用Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24 +26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t x11+x12+x13+x14=1 （甲只能干一项工作）x31+x32+x33+x34=1 （丙只能干一项工作）x41+x42+x43+x44=1 （丁只能干一项工作）x21+x22+x23+x24=1 （乙只能干一项工作）x11+x21+x31+x41=1 （A 工作只能一人干）x12+x22+x32+x42=1 （B 工作只能一人干）x13+x23+x

11、33+x43=1 （C 工作只能一人干）x14+x24+x34+x44=1 （D 工作只能一人干）xij 为 01 变量，i,j=1,2,3,4 3整数规划的应用整数规划的应用 应用“管理运筹学软件”：最优解为x21=1，x12=1，x33=1，x44=1.最小目标函数值为70.3整数规划的应用整数规划的应用 m个人n项任务的一般的指派问题：设 Xij=1，第i人去完成j项工作；Xij=0，第i人不去完成j项工作；cij为第i人去完成j项任务的成本（如时间、费用）一般指派问题的模型为：约束条件：也可以使用“管理运筹学软件”中“整数规划”子程序中的“指派问题”来求解 3整数规划的应用整数规划的应

12、用四、分布系统设计例 7某企业在 A1 地有一工厂，其产品的生产能力为 30 千箱，为扩大生产，打算在 A2，A3，A4，A5 地中再选择几个地方建厂。已知在 A2，A3，A4，A5 地建厂的固定成本分别为 175 千元、300 千元、375 千元、500 千元，另外，A1 产量及 A2，A3，A4，A5 建成厂的产量，销地的销量以及产地到销地的单位运价（每千箱运费）如表。3整数规划的应用整数规划的应用(1)该在哪几个地方建厂，在满足销量的前提下，使总固定成本和运输费用之和最小?(2)若政策要求必须在 A2，A3 地建一个厂，应在哪几个地方建厂？3整数规划的应用整数规划的应用。销地 运费单价/

13、元产地B1B2B3产量/千箱A184330A252310A343420A497530A5104240销量/千箱302020 3整数规划的应用整数规划的应用解：（1）设 xij 为从 Ai 运往 Bj 的运输量（单位：千箱）yk=1（Ak 被选中）yk=0（Ak 没被选中），k=2,3,4,5 3整数规划的应用整数规划的应用min z=175y2+300y3+375y4+500y5+8x11+4x12+3x13 +5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42 +5x43+10 x51+4x52+2x53 构建整数规划问题：3整数规划的应用整数规划的应用s.t x

14、11+x12+x13 30 (A1 厂的产量限制)x21+x22+x23 10y2(A2 厂的产量限制)x31+x32+x33 20y3 (A3 厂的产量限制)x41+x42+x43 30y4 (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 为 01 变量，k=2,3,4,5。注：求解可用“管理运筹学”

15、软件中整数规划子程序。3整数规划的应用整数规划的应用最优解：y5=1,x52=20,x53=20,x11=30,最优值为 860（千元）。3整数规划的应用整数规划的应用（2）加入约束条件：y2+y3=1，得到问题（2）的数学模型s.t x11+x12+x13 30 (A1 厂的产量限制)x21+x22+x23 10y2(A2 厂的产量限制)x31+x32+x33 20y3 (A3 厂的产量限制)x41+x42+x43 30y4 (A4 厂的产量限制)x51+x52+x53 40y5 (A5 厂的产量限制)x11+x21+x31+x41+x51=30 (B1 销地的限制)x12+x22+x32+

16、x42+x52=20 (B2 销地的限制)x13+x23+x33+x43+x53=20 (B3 销地的限制)y2+y3=1 xij 0,且为整数，i=1,2,3,4,5；j=1,2,3，yk 为 01 变量，k=2,3,4,5。3整数规划的应用整数规划的应用最优解：y2=1,y4=1,x22=10,x41=30,x12=10,x13=20,其余变量均为零。最优值为 940（千元）。3整数规划的应用整数规划的应用五、投资问题例 8某公司在今后五年内考虑给以下的项目投资。已知：项目 A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为 4 万元，第二、三、四

17、年不限；项目 B：第三年初需要投资，到第五年末能回收本利 128%，但规定最低投资金额为 3 万元，最高金额为 5 万元；项目 C：第二年初需要投资，到第五年末能回收本利 140%，但规定其投资额或为 2 万元或为 4 万元，或为 6 万元或为 8 万元。项目 D：五年内每年初可购买公债，于当年末归还，并加利息 6%，此项投资金额不限。该部门现有资金 10 万元，问应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大？3整数规划的应用整数规划的应用解：（1）设 xiA、xiB、xiC、xiD（i1，2，3，4，5）分别表示第 i 年年初给项目 A，B，C，D 的投资额；设 y

18、iA，yiB，是 01 变量，取 1 时分别表示第 i 年给 A、B 投资，否则取 0（i=1,2,3,4,5）。设 y2C 是非负整数变量，X2c=20000y2c：当y2c=4，则第 2 年投资 C 项目 8 万元；当y2c=3，则第 2 年投资 C 项目 6 万元；当y2c=2，则第 2 年投资 C 项目 4 万元；当y2c=1，则第 2 年投资 C 项目 2 万元；当y2c=0，则第 2 年不投资 C 项目。3整数规划的应用整数规划的应用建立决策变量：年份 投资额项目12345Ax1Ax2Ax3Ax4ABx3BCX2c=20000y2cDx1Dx2Dx3Dx4Dx5D 3整数规划的应用

19、整数规划的应用（3）目标函数及模型：max z=1.15x4A+1.40 x2C+1.28x3B+1.06x5Ds.t x1A+x1D=100 000，1.06x1D+x2A+x2C+x2D=0，1.15x1A1.06x2D+x3A+x3B+x3D=0，1.15x2A1.06x3D+x4A+x4D=0，1.15x3A1.06x4D+x5D=0，x1A40 000y1A0，x1A200 000y1A0，x3B30 000y3B 0，x3B50 000y3B 0，x2C20 000y2C=0，y2C4，xiA，xiB，xiC，xiD 0 (i=1、2、3、4、5)，y2C 为非负整数，y1A，y3

20、B 为 01 变量。第一年：年初有 100 000 元，D 项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+x1D=100 000；第二年：A 的投资第二年末才可收回，故第二年年初的资金为 1.06x1D，于是 x2A+x2C+x2D=1.06x1D；第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A+x4D=1.15x2A+1.06x3D；第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D=1.15x3A+1.06x4D。关于

21、项目 A 的投资额规定：x1A40 000y1A，x1A200 000y1A，200 000是足够大的数；保证当 y1A=0 时，x1A=0；当 y1A=1 时，x1A40 000。关于项目 B 的投资额规定:x3B30 000y3B，x3B50 000y3B ；保证当 y3B=0 时，x3B=0；当 y3B=1 时，50 000 x3B30 000。关于项目 C 的投资额规定：x2C=20 000y2C，y2C=0，1，2，3，4。3整数规划的应用整数规划的应用应用“管理运筹学”软件：最优值为 147 879.234。最优解为 x2C=60 000，x3B=49 905.641，x1A=43

22、 396.23，x1D=56 603.777，y3B=1，y2C=3，y1A=1.3整数规划的应用整数规划的应用六、0-1整数变量在构建模型中的一些特殊作用 引入整数变量，尤其是0-1变量，可将实际管理中无法归结为线性规划模型的问题，构建整数规划模型。3整数规划的应用整数规划的应用六、0-1整数变量在构建模型中的一些特殊作用1、解决固定成本问题(例5）生产成本最小的整数规划模型：0,0或1jjjjxMyxy约束条件：其他原始限制条件 3整数规划的应用整数规划的应用六、0-1整数变量在构建模型中的一些特殊作用2、解决选择取值问题（例7）约束条件的右端项可能是n个值中的某一个n11nii112f(

23、x,x,.,x)b,.1.1,当约束右端项为0.否则iniiyyyyby 3整数规划的应用整数规划的应用六、0-1整数变量在构建模型中的一些特殊作用3、解决n个变量中选取k个变量的问题（例4、例6）nj11,0或1jjxxn个取1个：n个取k个：nj1,0或1jjxkxn个至少取k个：nj1,0或1jjxkxn个至多取k个：nj1,0或1jjxkx 3整数规划的应用整数规划的应用六、0-1整数变量在构建模型中的一些特殊作用4、解决变量离散值的问题（例8）11x,y0或11mjjjjmjjc yy 3整数规划的应用整数规划的应用六、0-1整数变量在构建模型中的一些特殊作用5、解决部分约束的问题m

24、个约束只有k个起作用m个约束条件：nj1(i1,2,.m)ijjax1y0i设：假定第i个约束条件不起作用假定第i个约束条件起作用(i1,2,.m)则：nj112bMy(i1,2,.m)ijjiimaxyyymk 3整数规划的应用整数规划的应用六、0-1整数变量在构建模型中的一些特殊作用6、解决逻辑关系约束的问题若f(x)0成立，则g(x)0必须成立；若f(x)0不成立，则g(x)无限制。引入一个0-1变量y来解决这一逻辑关系：f(x)-M(1-y)g(x)My 3整数规划的应用整数规划的应用七、关于灵敏度分析的讨论 在整数规划中，某个参数很小的变化可能会使最优值产生相对较大的变化。max 5

25、0 x1+80 x2+100 x3+150 x4约束条件：31x1+50 x2+70 x3+90 x4120 xi为0-1变量 i=1,2,3,4最优解：x1=0,x2=1,x3=1,x4=0,最优值z=180.当预算资金由当预算资金由120120万元变为万元变为121121万元时，最优解？万元时，最优解？最优解：x1=1,x2=0,x3=0,x4=1,最优值z=200.3整数规划的应用整数规划的应用七、关于灵敏度分析的讨论 解决整数规划问题的灵敏度分析，通常需要高速计算机的帮助。通常建议在实施最优解前对参数稍加修改，多解几次。4整数规划的分枝定界法整数规划的分枝定界法 分枝定界法是求解整数规

26、划的一种常用的有效的方法。多数求解整数规划的商用软件基于分枝定界法。4整数规划的分枝定界法整数规划的分枝定界法分枝定界法计算过程：整数规划整数规划整数规划上、下界整数规划上、下界线性规划线性规划整数规划整数规划最优解最优解是是否否解为整数，且解为整数，且上界上界=下界下界线性规划分枝线性规划分枝可行解可行解有有整数规划整数规划无可行解无可行解无无剪枝剪枝比较比较 4整数规划的分枝定界法整数规划的分枝定界法例 9.用分枝定界法求解整数规划 max 2x1+3x2s.t.195x1+273x21 365 4x1+40 x2140 x1 4 x1,x2 0 且 x1,x2 为整数 4整数规划的分枝定

27、界法整数规划的分枝定界法求解过程与结果线性规划1Z1=14.66X1=2.44X2=3.26z=13,z=14.58线性规划2Z2=13.90X1=2X2=3.30线性规划3Z3=14.58X1=3X2=2.86z=13,z=14.66z=14,z=14线性规划4Z4=14.00X1=4X2=2线性规划5无可行解 x13x12x22x23选择目标函数较优者解：（1）先求出以下线性规划的解。max 2x1+3x2 s.t.195x1+273x21 365 4x1+40 x2140 x1 4 x1,x20 得 z1=14.66，x1=2.44，x2=3.26确定整数规划的最优目标函数值 z*初始上

28、界 和下界。分析后，知道 上界为14.66，由观察法得下界 为13（当 x1=2,x2=3 时）。将线性规划 1 分解为两支：线性规划 2：max 2x1+3x2 s.t.195x1+273x21 365 4x1+40 x2140 x1 4 x1 2 x1,x20解得 z2=13.90,x1=2,x2=3.30线性规划 3：max 2x1+3x2 s.t.195x1+273x21 365 4x1+40 x2140 x1 4 x13 x1，x20解得 z3=14.58,x1=3,x2=2.86线性规划 4：max 2x1+3x2s.t.195x1+273x21365 4x1+40 x2140 x

29、14 x13 x22 x1,x20解得 z4=14,x1=4,x2=2 线性规划 5：max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x14 x13 x23 x1,x20线性规划 5 无可行解。整数规划最优解 4整数规划的分枝定界法整数规划的分枝定界法性质 2：当整数规划的最优目标函数值 z*的上界 z 等于其下界 z 时，该整数规划的最优解已经被求出。整数规划的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。50-1规划的解法规划的解法 求解0-1规划问题的方法：2.隐枚举法 检查全部变量组合的一部分，求得问题的最优解。1.穷举法 检查每个

30、变量取值为0或1的所有组合，找出满足全部约束条件的所有组合，并比较目标函数的值，求得最优解。分支定界法也是一种隐枚举法。50-1规划的解法规划的解法 例10.有以下0-1规划 max z=4x1+x2+5x3约束条件：2x1+3x2-x33 （1）x1+3x2+2x32 （2）x1+2x22 （3）3x1+2x2+x32 （4）xi=1或0,i=1,2,3.50-1规划的解法规划的解法 解：可行解：X1=(0,1,1)，z1=6.增加约束条件：4x1+x2+5x36 （0）(过滤条件)50-1规划的解法规划的解法 max z=4x1+x2+5x3约束条件：4x1+x2+5x36 （0）按照（0

31、）-（4)顺序对约束条件进行排列 2x1+3x2-x33 （1）x1+3x2+2x32 （2）x1+2x22 （3）3x1+2x2+x32 （4）xi=1或0,i=1,2,3.可行解：X1=(0,1,1)，z1=6.增加约束条件：4x1+x2+5x36 （0）(过滤条件)50-1规划的解法规划的解法 解：应用穷举法，将解依次带入约束条件，求出目标函数值并检验是否符合过滤条件。解约束条件左边值是否满足条件z值（x1,x2,x3）(0)(1)(2)(3)(4)是（）否（）4x1+x2+5x39 （0）(过滤条件)4x1+x2+5x36 （0）(过滤条件)（1，1，1）104（1，1，0）5（1，0

32、，1）913149（1，0，0）4（0，1，1）6（0，1，0）1（0，0，1）5（0，0，0）0 50-1规划的解法规划的解法 求最大值问题时，可按目标函数系数的大小依次递减排列。50-1规划的解法规划的解法问题改写：max z=5x3+4x1+x2约束条件：5x3+4x1+x26 （0）-x3+2x1+3x23 （1）2x3+x1+3x22 （2）x1+2x22 （3）x3+3x1+2x22 （4）xi=1或0,i=1,2,3.50-1规划的解法规划的解法解约束条件左边值是否满足条件z值（x3,x1,x2）(0)(1)(2)(3)(4)是（）否（）（1，1，1）（1，1，0）1049131

33、494x1+x2+5x36 （0）(过滤条件)-x3+2x1+3x23 （1）从最大值点开始取 50-1规划的解法规划的解法 例11.有以下0-1规划 min z=5x1+3x2+x3约束条件：3x1-2x2+5x36 （1）4x1+4x2+3x33 （2）2x1+x2+x32 （3）xi=1或0,i=1,2,3.50-1规划的解法规划的解法 解：目标函数的最小值。按照目标函数系数的大小依次递减排列。目标函数下限为z=0 逐渐增加过滤条件的右边值，只要找到可行解，该解即为最优解。50-1规划的解法规划的解法 解约束条件左边值是否满足条件z值（x1,x2,x3）(0)(1)(2)(3)是（）否（）从最小值点开始取5x1+3x2+x3 0（0）(过滤条件)3x1-2x2+5x36 （1）4x1+4x2+3x33 （2）2x1+x2+x32 （3）（0，0，0）（0，0，1）（0，1，0）（0，1，1）00015313-24143724最优解为X=(0,1,1)，z=4.