管理运筹学-整数规划.ppt

《管理运筹学-整数规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学-整数规划.ppt（20页珍藏版）》请在三一办公上搜索。

1、第八章 整数规划,1 整数规划的图解法 2整数规划的计算机求解 3整数规划的应用 4整数规划的分枝定界法,1 整数规划的图解法,例1.某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备需要A、B两种材料的消耗以及资源的限制，如右表。问题：工厂应分别生产多少件甲、乙种仪器设备才能使工厂获利最多？,解、目标函数：Max z=x1+x2 约束条件：s.t.3 x1+2 x2 10 2 x2 5 x1，x2 0 为整数不考虑整数约束得到最优解：x1=1.667，x2=2.5；z=4.167,考虑整数约束得到最优解：x1=2，x2=2；z=4整数规划的最优目标值小于相应线性规划的最优目标值

2、(相当于附加一个约束),2整数规划的计算机求解,例2：Max z=15x1+10 x2+7x3 s.t.5x1-10 x2+7x3 8 6x1+4x2+8x3 12-3x1+2x2+2x3 10 x1,x2,x3 0 为整数,例2：Max z=15x1+10 x2+7x3 s.t.5x1-10 x2+7x3 8 6x1+4x2+8x3 12-3x1+2x2+2x3 10 x1,x2,x3 0 x3 为整数 x1 为0-1变量,用管理运筹学软件求解得：x1=0 x2=3 x3=0 z=30,用管理运筹学软件求解得：x1=1 x2=1.5 x3=0 z=30,3整数规划的应用(1),一、投资场所的

3、选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj(j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3 三个点至多选择两个；在西区由A4，A5 两个点中至少选一个；在南区由A6，A7 两个点中至少选一个；在北区由A8，A9，A10 三个点中至少选两个。Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见右表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,解：设：0-1变量 xi=1(Ai 点被选用）或 0(Ai 点没被选用）。这样我们

4、可建立如下的数学模型：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 xj 0 xj 为0-1变量，i=1,2,3,10,二、固定成本问题 例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如右表所示。不考虑固定费用，每种容器售出一

5、只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器有100台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,解：这是一个整数规划的问题。设x1，x2，x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi=1(当生产第 i种容器,即 xi 0 时)或0（当不生产第 i种容器即 xi=0 时）引入约束 xi M yi，i=1，2，3，M充分大，以保证当 yi

6、=0 时，xi=0。这样我们可建立如下的数学模型：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充分大 xj 0 yj 为0-1变量，i=1,2,3,3整数规划的应用(2),例6有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如右表所示，问应如何指派工作，才能使总的消耗时间为最少。,解：引入01变量 xij，并令 xij=1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)这可以表示为

7、一个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+x33+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工作

8、只能一人干)x14+x24+x34+x44=1(D工作只能一人干)xij 为0-1变量，i,j=1,2,3,4*求解可用管理运筹学软件中整数规划方法。,3整数规划的应用(3),三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。,四、分布系统设计例7某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2，A3，A4

9、，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如右表所示。a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?b)如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?,解：a)设 xij为从Ai 运往Bj 的运输量(单位千箱)，yi=1(当Ai 被选中时)或0（当Ai 没被选中时)这可以表示为一个整数规划问题：Min z=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x

10、22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t.x11+x12+x13 30(A1 厂的产量限制)x21+x22+x23 10y2(A2 厂的产量限制)b）增加约束：y2+y3=1 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+

11、x33+x43+x53=20(B3 销地的限制)xij 0 yi为0-1变量，i=1,2,3,4,5；j=1,2,3*求解可用管理运筹学软件中整数规划方法。,3整数规划的应用(4),3整数规划的应用(5),五、投资问题 例8某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年未能回收本利128，但规定最低投资金额为3万元，最高金额为5万元；项目 C：第二年初需要投资，到第五年未能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为

12、8万元。项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?,解：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万元时，取值为2；2年投资C项目2万元时，取值为1；2年不

13、投资C项目时，取值为0；这样我们建立如下的决策变量：第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C(=20000y2C)D x1D x2D x3D x4D x5D,3整数规划的应用(6),2）约束条件：第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+x1D=100000；第二年：A次年末才可收回投资故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D=1.15x1A+1.06x2D；

14、第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A+x4D=1.15x2A+1.06x3D；第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D=1.15x3A+1.06x4D；关于项目A的投资额规定:x1A 40000y1A，x1A 200000y1A，200000是足够大的数；保证当 y1A=0时，x1A=0；当y1A=1时，x1A 40000。关于项目B的投资额规定:x3B 30000y3B，x3B 50000y3B；保证当 y3B=0时，x3B=0；当y3B=1时，50000 x3B 30000。关于项目C的投资额规定:x2C=20000y2C，y2C=0

15、，1，2，3，4。3）目标函数及模型：Max z=1.15x4A+1.40 x2C+1.28x3B+1.06x5D s.t.x1A+x1D=100000；x2A+x2C+x2D=1.06x1D；x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A 40000y1A，x1A 200000y1A，x3B 30000y3B，x3B 50000y3B；x2C=20000y2C，yiA，yiB=0 或 1，i=1,2,3,4,5 y2C=0，1，2，3，4 xiA，xiB，xiC，xiD 0(i=1、2、3

16、、4、5）,4整数规划的分枝定界法(1),问题（A）Min z=c1 x1+c2 x2+cn xn 记 问题（B）为去掉整数约束的问题（A）s.t.a11 x1+a12 x2+a1n xn=b1 a21 x1+a22 x2+a2n xn=b2 am1 x1+am2 x2+amn xn=bm x1，x2，xn 0 为整数在分枝定界法过程中求解问题(B)，应有以下情况之一：(B)无可行解，则(A)亦无可行解，停止对此问题 的计算；(B)有最优解，并满足整数约束，即同时为(A)的最优解，那么z*同时是当前问题(A)最优目标值的上界和下界。停止对这个问题的计算；(B)有最优解 x 及最优值 z 但不符

17、合整数条件。这时得到当前问题(A)最优目标值的一个下界 z z,于是通过以下判断可对此问题进一步计算。分枝定界法的计算过程：1、对原问题(A)，求解松弛问题(B)。根据上面分析，若出现情况，则停机。若情况发生，得到(A)问题最优值的一个下界。我们任找(A)问题的一个可行解，那么对应的目标函数值是(A)最优值的一个上界 z。即得到 z z*z。(注：找(A)问题的可行解往往需要较大的计算量，这时可简单记 z+，而先不必费很大力量去求较好的上界。从以下分析可以看到，找到一个好的最优目标值上界，将对算法的快速求得目标非常有效。)，转2，进行以下一般步的迭代；,4整数规划的分枝定界法(2),2、对当前

18、问题进行分枝和定界：分技：无妨设当前问题为(A)，其松弛问题(B)的最优解不符合整数约束，任取非整数的分量 xr。构造两个附加约束：xr xr 和 xr xr+1，对(A)分别加入这两个约束，可得到两个子问题(A1)和(A2)，显然这两个子问题的可行解集的并是(A)的可行解集；定界：根据前面分析，对每个当前问题(A)可以通过求解松弛问题(B)，以及找(A)的可行解得到当前问题的上、下界 z和 z。对一般迭代步，设根据分枝定界方法得到了原问题(A)的一个同层子问题(AI)，i1，2，.，n 之和的分解。这里的同层子问题是指每个子问题(AI)都是(A)经过相同分枝次数得到的。3、比较与剪枝：对当前

19、子问题进行考察，若不需再进行计算，则称之为剪枝。一般遇到下列情况就需剪枝：(B)无可行解；(B)的最优解符合整数约束；(B)的最优值 z z。通过比较，若子问题不剪枝则返回 2。分枝定界法当所有子问题都剪枝了，即没有需要处理的子问题时，达到当前上界 z 的可行解即原问题的最优解，算法结束。,4整数规划的分枝定界法(3),分枝定界法是求整数规划的一种常用的有效的方法，既能解决纯整数规划的问题，也能解决混合整数规划的问题。例：Min f=-5x1-4x2s.t.3x1+4x2 24 9x1+5x2 45 x1,x2 0 整数,4整数规划的分枝定界法(4),隐枚举法是求解01规划最常用的方法之一 对

20、于 n 个决策变量的完全 01 规划，其可行点最多有 2n 个，当 n 较大时其计算量大得惊人。隐枚举法的基本思想是根据01规划的特点，进行分技逐步求解。1、用于隐枚举法的01规划标准形式：为了计算的方便，需要把一般的 01规划问题等价地化成下列标准形式 Min f=c1 x1+c2 x2+cn xn cj 0 j=1,2,n s.t.ai1 x1+ai2 x2+ain xn bi i=1,2,m x1，x2，xn=0 或 1下面说明一个完全的01规划问题可以化为等价的标准形式：(1)若目标函数求最大：Max z，可令 f=-z，变为求最小 Min f；(2)若目标函数的系数有负值时，如 cj

21、 0。那么，可以令相应的 yj=1-xj；(3)当某个约束不等式是“”时，只需两端同乘以-1，即变为“”；(4)当某个约束是等式约束时，可得到两个方向相反的不等式。,4整数规划的分枝定界法(5),隐枚举法的基本过程：1、将01规划问题化为标准形式，设其最优解为 x*，最优目标值为 f*。显然 x=0 时，目标值 f 0 是不考虑线性不等式约束的最小解，于是 f*0。若 x=0 是可行解，那末 f 0是该问题的最优解，结束计算。否则，置所有分量为自由变量。转2；2、任选一自由变量 xk，令 xk 为固定变量，分别固定为 xk=0 与 xk 1，令所有自由变量取零值，则得到两个分枝。对每个分枝的试

22、探解进行检验（把自由变量逐次定为固定变量的顺序可以是任意的，在不进行先验考察时，常按指标变量从小到大的顺序进行）。转3；3、检验当前试探解时，遇到下列4种情况就剪枝，即不必再向下分枝，在剪枝的子问题下方标记“”：情况一：若子问题的试探解可行，即满足所有线性不等式约束，则此问题的目标值是原问题最优目标值的一个上界记为 f 即 f*f。把 f 的值记在子问题框的旁边，并在下方标记上“”；,4整数规划的分枝定界法(6),情况二：若试探解不可行，且存在一个线性不等式约束，将所有固定变量值代入后，所得到的不等式中所有负系数之和大于右端项或若无负系数时，最小的系数大于右端项，那么此问题的任何分枝都是不可行

23、的问题。于是在此问题框的下方标记“”；情况三：若试探解不可行，且它的目标值与目标函数中对应当前自由变量的任一个系数之和大于所有已得到的上界中最小者时，说明在当前问题的基础上，固定任何自由变量都不可能对目标函数有改善，于是在该问题框的下方标记“”；情况四：若试探解不可行，但所有变量已被置为固定变量，也应剪枝，于是在该问题框的下方标记“”。把已标记“”的子问题，称为已探明的枝。转4。4、进一步考察。如果所有的枝均为已探明的枝，则停机结束计算。找出所有子问题框边标记 f 值的问题，比较得到其中最小者，其对应的试探解即原问题的最优解，相应值即原问题的最优目标值 f*；若没有标记 f 值的框，则说明原问

24、题无最优解，实际上原问题无可行解。如果仍存在尚未探明的分枝，则可任选一个未探明的分枝。转2。,4整数规划的分枝定界法(7),0-1规划的隐枚举法例：Max z=100 x1+30 x2+40 x3+45x4s.t.50 x1+30 x2+25x3+10 x495 7x1+2x2+3x3+4x411 2x1+x2+x3+10 x412 x4 x2+x3 xj=0 或 1，i=1,2,3,4标准化：取f=-z=-100 x1-30 x2-40 x3-45x4令 y1=1-x1,y2=1-x2,y3=1-x3,y4=1-x4f=100y1+30y2+40y3+45y4-215,记 f=f+215,得

25、到Min f=100y1+30y2+40y3+45y4s.t.-50y1-30y2-25y3-10y4-20-7y1-2y2-2y3-4y4-4-2y1-y2-y3-10y4-2 y2+y3-y4 1 yj=0 或 1，i=1,2,3,4,第九章 动态规划,1 多阶段决策过程最优化问题举例 2 基本概念、基本方程与最优化原理 3 动态规划的应用（见文本）,1 多阶段决策过程最优化问题举例,例1 最短路径问题右图表示从起点A到终点E之间各点的距离。求A到E的最短路径。,如果用穷举法，则从A到E一共有332=18条不同的路径，逐个计算每条路径的长度，总共需要进行418=72次加法计算；对18条路径的长度做两两比较，找出其中最短的一条，总共要进行181=17次比较。如果从A到C的站点有k个，则总共有3k-12条路径，用穷举法求最短路径总共要进行(k+1)3k-12次加法，3k-12-1次比较。当k的值增加时，需要进行的加法和比较的次数将迅速增加。例如当k=10时，加法次数为433026次，比较39365次。以上这求从A到E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径问题。记从Bi(i=1,2,3)到E的最短路径为S(Bi)，则从A到E的最短距离S(A)可以表示为：,