数学建模整数规划学习教案.pptx

《数学建模整数规划学习教案.pptx》由会员分享，可在线阅读，更多相关《数学建模整数规划学习教案.pptx（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数学数学(shxu)建模整数规划建模整数规划第一页，共30页。第五章第五章 整数整数(zhngsh)规划规划1 整数规划整数规划(guhu)问题及其数问题及其数学模型学模型2 整数整数(zhngsh)规划的解规划的解法法3 整数规划的应用举例整数规划的应用举例第2页/共30页第二页，共30页。1 1 整数规划整数规划整数规划整数规划(guhu)(guhu)问题及其数学模型问题及其数学模型问题及其数学模型问题及其数学模型1 整数整数(zhngsh)规划问规划问题及其数学模型题及其数学模型 货货 物物每箱体积每箱体积（m3）每箱重量每箱重量（kg）每箱利润每箱利润（百元）（百元）甲甲522

2、0 乙乙4510托运限制托运限制2413Example 1 （装载（装载(zhungzi)问题）问题）某厂拟用集装箱托运甲、乙某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运限制两种货物，每箱的体积、重量、可获利润及托运限制如表，问两种货物各托如表，问两种货物各托运几箱，可获利润最大？运几箱，可获利润最大？Solution:设设 x1、x2 分分别为甲、乙两种货物托别为甲、乙两种货物托运箱数运箱数.则这是一个这是一个 Pure IP 问题问题.第3页/共30页第三页，共30页。第五章第五章第五章第五章 整数整数整数整数(zhngsh)(zhngsh)(zhngsh)(zhng

3、sh)规划规划规划规划Example 2 （工厂选址（工厂选址(xun zh)问题）问题）现准备从现准备从 A1、A2、A3 三个地点中选择两个开设三个地点中选择两个开设(kish)工厂，工厂建成后它每月的工厂，工厂建成后它每月的产量产量 ai(i=1,2,3)、三个客户、三个客户 B1、B2、B3 每月的需求量每月的需求量 bj(j=1,2,3)及及 Ai 至客户至客户 Bj 的单位运价的单位运价 cij 见表见表.BjAiB1B2B3aiA145370A223480A364590bj406045 已知三已知三工厂每月的经营费用工厂每月的经营费用 di(与与产量无关产量无关)分别为分别为 1

4、00、90、120.问如问如何选址使每月经营和运输费用最低何选址使每月经营和运输费用最低.Solution:因为只有三个厂址选两个，因为只有三个厂址选两个，所以简单的方法，所以简单的方法是任取两个厂用运输问题求解，再加上每月的经营是任取两个厂用运输问题求解，再加上每月的经营费用比较即可费用比较即可.设设选地点选地点 Ai 开设工厂开设工厂否则否则 i=1,2,3 ；xij 为为Ai 开设工厂时，从开设工厂时，从 Ai 至至 Bj 的运量的运量显然显然如果如果 Ai 处开设工厂，处开设工厂，则运量满足：则运量满足：不开设呢？不开设呢？客户端需求满足：客户端需求满足：目标（每月的费用）：目标（每月

5、的费用）：这是一个这是一个 Mixed IP 问题问题.可用于设计分配系统、新生活小区的设置可用于设计分配系统、新生活小区的设置 etc.第4页/共30页第四页，共30页。1 1 整数整数整数整数(zhngsh)(zhngsh)规划问题及其数学模型规划问题及其数学模型规划问题及其数学模型规划问题及其数学模型 在在 Ex.2 中，引进中，引进 01 变量给出了在变量给出了在 n 件任务中件任务中,选择选择(xunz)j 项的约束项的约束又用又用 来刻画不设来刻画不设第第 i 项任务项任务(rn wu)，则，则 xij j=1n 都不起作用，为零都不起作用，为零.可应用于选择性可应用于选择性约束条

6、件中约束条件中 某工厂生产第某工厂生产第 j 种产品的数量为种产品的数量为 xj(j=1,2,3)其使其使用的材料在甲、乙中选择一种，其消耗约束分别为：用的材料在甲、乙中选择一种，其消耗约束分别为：其他资源约束条其他资源约束条件未列出件未列出引进引进 01 变量变量 y 选择材料甲选择材料甲选择材料乙选择材料乙M 为充分大的正为充分大的正数数一般地，假定要在一般地，假定要在 p个约束条件个约束条件 中中至少要选择至少要选择 q 个约束条件得到满足，可引进个约束条件得到满足，可引进0-1变量变量 y第5页/共30页第五页，共30页。第五章第五章第五章第五章 整数整数整数整数(zhngsh)(zh

7、ngsh)(zhngsh)(zhngsh)规划规划规划规划Example 3 （背包（背包(bibo)问题）问题）假设假设(jish)有人要出发旅行，考虑带七有人要出发旅行，考虑带七种物品，每件物品的重量与价值如表种物品，每件物品的重量与价值如表.现在假设现在假设(jish)他最多带他最多带 35kg 物品，问该带物品，问该带哪几件物品使总价值最大？哪几件物品使总价值最大？物品物品重量重量 aj价值价值 cj 1 3 12 2 4 12 3 3 9 4 3 15 5 15 90 6 13 26 7 16 112Solution:如果带第如果带第 j 件物品件物品否则否则 j=17这是一个这是一

8、个 0-1 规划问题规划问题.一般整数规划中的变量一般整数规划中的变量 x,也可用也可用 0-1 变量替代，如变量替代，如0 x15，x=x020+x121+x222+x323 其中其中 x0,x1,x2,x3 为为0-1 变量变量.第6页/共30页第六页，共30页。1 1 整数整数整数整数(zhngsh)(zhngsh)规划问题及其数学模型规划问题及其数学模型规划问题及其数学模型规划问题及其数学模型 参见参见 Ex.1,去掉去掉(q dio)整数约束，得整数约束，得舍入化整舍入化整o 1 2 3 4 5 x14321x2由图解法得最优解为：由图解法得最优解为：x1=4.8,x2=0 Zmax

9、=96显然，显然，x1 不是整数不是整数.是否可以根据是否可以根据(gnj)化整的原问题的解？化整的原问题的解？x1=5、x2=0 不是可行解，不是可行解，x1=4、x2=0 Z=80.但是但是 x1=4、x2=1 也可行也可行 且且 Z=90.所以，所以，“舍入化整舍入化整”的结果：的结果：1、化整后未必可行；、化整后未必可行；2、即使是可行解，也未必是最优解；、即使是可行解，也未必是最优解；3、用这个方法即使能得到最优解，但如果有、用这个方法即使能得到最优解，但如果有n 个变个变 量，则取舍方案有量，则取舍方案有 2n 种，计算量也是很大的种，计算量也是很大的.Go back第7页/共30

10、页第七页，共30页。第五章第五章第五章第五章 整数整数整数整数(zhngsh)(zhngsh)(zhngsh)(zhngsh)规划规划规划规划o 1 2 3 4 5 x14321x22 2 整数规划整数规划整数规划整数规划(guhu)(guhu)的解法的解法的解法的解法 有人在研究在建立模型中，什么条件有人在研究在建立模型中，什么条件(tiojin)下下 LP 问题的问题的解一定是整数解？解一定是整数解？如：如：运输问题运输问题从从 Ex.1 的讨论，可得到一些启迪的讨论，可得到一些启迪1、是否能在是否能在 LP 的约束区域中的约束区域中,切切去去 n 块不含整数解的可行域使整数块不含整数解的

11、可行域使整数解作为顶点，则解作为顶点，则 LP 的最优解即为的最优解即为整数解整数解；如增加约束如增加约束 x14,则则 LP 问题的解即为整数解问题的解即为整数解;2、在在 LP 的可行域中，整数点不多，的可行域中，整数点不多，（12个）个）是否可以用穷举法是否可以用穷举法.第8页/共30页第八页，共30页。2 整数(zhngsh)规划的解法一、割平面一、割平面(pngmin)法法 1959年由年由 首先提出首先提出(t ch)，从此使，从此使 IP 逐渐逐渐形成为一个独立的运筹学分支形成为一个独立的运筹学分支.割平面法的实质是用解割平面法的实质是用解 LP 问题的方法求解问题的方法求解 I

12、P 问题；问题；割平面法的割平面法的基本思想基本思想是通过对是通过对 LP 问题的求解，如果最问题的求解，如果最优解是整数解，则就是优解是整数解，则就是 IP 的解；否则设法对的解；否则设法对 LP 问题问题增加约束增加约束(割平面割平面)，把，把 LP 问题的可行域中去掉一部分问题的可行域中去掉一部分不含整数解的，再求不含整数解的，再求 LP 问题，反复进行问题，反复进行.割平面法的割平面法的关键关键在于如何寻找适当的切割约束条件在于如何寻找适当的切割约束条件.用割平面法求解用割平面法求解 IP 问题常常会计算量大、收敛速度问题常常会计算量大、收敛速度慢的情况，但在理论上是重要的，被认为是慢

13、的情况，但在理论上是重要的，被认为是 IP 的核心的核心.第9页/共30页第九页，共30页。第五章第五章第五章第五章 整数整数整数整数(zhngsh)(zhngsh)(zhngsh)(zhngsh)规划规划规划规划二、分支二、分支(fnzh)定界法定界法分支与定界分支与定界(dn ji)法的基本思想是对有约束条件的最优化问法的基本思想是对有约束条件的最优化问题的所有可行解（其数目为有限集）空间适当地进行题的所有可行解（其数目为有限集）空间适当地进行搜索搜索.具体执行时，把可行解空间不断分割为越来越小具体执行时，把可行解空间不断分割为越来越小的子集（称为分支），并确定每个分支内的解值的下的子集（

14、称为分支），并确定每个分支内的解值的下界或上界（称为定界）界或上界（称为定界）.在每次分支后，对凡是界超在每次分支后，对凡是界超出已知可行解值的子集被剪去，从而不断缩小搜索范出已知可行解值的子集被剪去，从而不断缩小搜索范围围.这个过程一直进行到找出最优解为止，该可行解这个过程一直进行到找出最优解为止，该可行解的值不大于或不小于任何子集的界的值不大于或不小于任何子集的界.优点：优点：1、适用面广、适用面广 2、可检查较少的解（运、可检查较少的解（运气好）气好）3、可获得最优解、可获得最优解缺点：本质是穷缺点：本质是穷举，复杂性大于穷举法举，复杂性大于穷举法第10页/共30页第十页，共30页。2

15、整数规划(guhu)的解法设设如果如果(rgu)则称问题（则称问题（2）是问题（）是问题（1）的松弛问题）的松弛问题.Note:1、松弛问题、松弛问题(wnt)未必比原问题未必比原问题(wnt)难解；难解；如：如：整数规划与线性规划；整数规划与线性规划；TSP 与指派问题与指派问题 etc.如：如：A：寻找全国：寻找全国18 岁百米最快的运动员岁百米最快的运动员.B：寻找：寻找全国所有百米最快的运动员全国所有百米最快的运动员.显然，显然，B 问题是问题是 A 问题的松弛问题，且问题的松弛问题，且B 问题更易解问题更易解.2、如果松弛问题易解，则先解松弛问题是有益的如果松弛问题易解，则先解松弛问

16、题是有益的.1）设设 x0 是松弛问题的最优解，且是松弛问题的最优解，且 则原问题已解则原问题已解2）即使即使 给出了原问题最优值的界给出了原问题最优值的界 f(x0).x0BABAx0第11页/共30页第十一页，共30页。第五章第五章第五章第五章 整数整数整数整数(zhngsh)(zhngsh)(zhngsh)(zhngsh)规划规划规划规划分枝分枝(fn zh)与定界法为什么能少检查一些解？与定界法为什么能少检查一些解？B10sB1B210.2s*10sB3B410.3s*几点注意几点注意(zh y)：确定问题（子问题）的最优值的确定问题（子问题）的最优值的界界 通常是通过求解松弛问题，通

17、常是通过求解松弛问题，用松弛问题的解作为界，也可用松弛问题的解作为界，也可以用启发式算法得到以用启发式算法得到.Note:松弛问题选择的松弛问题选择的原则原则1 1、松弛问题要与原问题的、松弛问题要与原问题的 最优值尽量接近；最优值尽量接近；2 2、松弛问题要尽量容易解松弛问题要尽量容易解 .这两个原则不易统一，所以可选择不同的松弛问题这两个原则不易统一，所以可选择不同的松弛问题第12页/共30页第十二页，共30页。2 整数规划(guhu)的解法 划分方法划分方法划分方法划分方法(fngf)(fngf)的选择的选择的选择的选择原则是希望分出来的子问题容易原则是希望分出来的子问题容易(rngy)

18、被查清，可加快计算被查清，可加快计算.选哪个活问题先检查选哪个活问题先检查1 1、先检查最大上界（极大化问题）的活问题先检查最大上界（极大化问题）的活问题优点：优点：检查子问题较其他规则为少；检查子问题较其他规则为少；缺点：缺点：计算机储存量较大计算机储存量较大 .2 2、先检查最新产生的最大上界的活问题先检查最新产生的最大上界的活问题优点：优点：计算机储存量较少计算机储存量较少；缺点：缺点：需要更多的分支运算需要更多的分支运算 .选择的不同，提供了发挥的余地选择的不同，提供了发挥的余地 分枝与定界法的重要在于它提出了一类新的思分枝与定界法的重要在于它提出了一类新的思路（隐枚举法），使得许多原

19、来不好解决的问题有路（隐枚举法），使得许多原来不好解决的问题有了解决的可能性了解决的可能性.（具有普适性）（具有普适性）第13页/共30页第十三页，共30页。第五章第五章第五章第五章 整数整数整数整数(zhngsh)(zhngsh)(zhngsh)(zhngsh)规划规划规划规划Example 4用分支定界法求解用分支定界法求解(qi ji)如右如右 IP 问题问题Solution:解松弛解松弛(sn ch)问题问题 P0得：得：x1=2.25、x2=3.75 Zmax=41.25去掉整数约束为去掉整数约束为原原问题的松弛问题问题的松弛问题41.25是原问题最优值的上界是原问题最优值的上界进行

20、分支，任选一个不是整数的变量进行分支，任选一个不是整数的变量,如取如取 x2 则可认为则可认为最优解最优解 x24 或或 x23.原问题分为两个子问题原问题分为两个子问题.3x24 之间无整数解之间无整数解0 1 2 3 4 5 6 7 8 9 x1x254321P1P2再分别求解两个松弛问题再分别求解两个松弛问题 P1、P2P0 x1=2.25x2=3.75Z0=41.25P1(x23)P2（x24）x1=3、x2=3Z1=39*x1=1.8、x2=4Z2=41P3（x12）P4(x11)不可行不可行*x1=1、x2=40/9Z4=365/9P5（x24）P6(x25)x1=1、x2=4 Z

21、5=37*x1=0、x2=5 Z6=40*此时已没有活问题，所以最此时已没有活问题，所以最优解为优解为 x1=0、x2=5 Zmax=40.第14页/共30页第十四页，共30页。2 整数(zhngsh)规划的解法Example 5（投资（投资(tu z)方案的最优选择）方案的最优选择）背包背包(bibo)问题可以看成为一个一次性的投资问题，简问题可以看成为一个一次性的投资问题，简单的扩展：单的扩展：1、分几次投资；、分几次投资；2、虽然一次性投资，但、虽然一次性投资，但不同的项目有一些政策上的限制不同的项目有一些政策上的限制 etc.某公司欲对三个项目进行投资，某公司欲对三个项目进行投资，根据

22、预算四年内的投资额、三个项目根据预算四年内的投资额、三个项目每年所需投资额以及所创利润如表每年所需投资额以及所创利润如表.问应对哪几个项目进行投资，可获利最大？问应对哪几个项目进行投资，可获利最大？投资投资年度年度项目项目投资投资额度额度A1A2A310425251273403745136回报回报利润利润20816Solution:如果对项目如果对项目Aj 投资投资否则否则 j=13设设 对于对于0-1 规划的求解，首先会规划的求解，首先会想到枚举法，但变量取想到枚举法，但变量取0、1的所的所有组合有有组合有 2n.是否能设计一些方是否能设计一些方法，只检查所有组合的一部分就法，只检查所有组合

23、的一部分就求得最优解，即隐枚举法求得最优解，即隐枚举法.分支定界法是分支定界法是一种隐枚举一种隐枚举.给出一个重要思想给出一个重要思想:设门槛设门槛(1、可行性、可行性2、目标函数值、目标函数值)第15页/共30页第十五页，共30页。第五章第五章第五章第五章 整数整数整数整数(zhngsh)(zhngsh)(zhngsh)(zhngsh)规划规划规划规划(x1 x2 x3)约束条件约束条件Z值值(0 0 0)(0 0 1)(0 1 0)(0 1 1)(1 0 0)(1 0 1)(1 1 0)(1 1 1)01682028(x1 x2 x3)约约 束束 条条 件件Z值值(0 0 0)(0 0 1

24、)(0 1 0)(0 1 1)(1 0 0)(1 0 1)(1 1 0)(1 1 1)增加一个判别 A,目标函 数值(shz)小于已知可行解的值，则不必继续计算.A 0162028可以可以(ky)改进改进吗？吗？(x2 x3 x1)约约 束束 条条 件件Z值值(0 0 0)(0 0 1)(0 1 0)(0 1 1)(1 0 0)(1 0 1)(1 1 0)(1 1 1)A 02028还有想法吗？还有想法吗？Go back第16页/共30页第十六页，共30页。第五章第五章 整数整数(zhngsh)(zhngsh)规划规划3 3 整数整数整数整数(zhngsh)(zhngsh)规划的应用举例规划的

25、应用举例规划的应用举例规划的应用举例Example 6（人员（人员(rnyun)时间安排问题）时间安排问题）为了尽可能有效地利用劳动力，有必要对一天各为了尽可能有效地利用劳动力，有必要对一天各个不同时刻需要人员的情况作一分析，特别是在一些个不同时刻需要人员的情况作一分析，特别是在一些大型服务性机构中，顾客的需要是重复性的，但不同大型服务性机构中，顾客的需要是重复性的，但不同时刻之间需要的服务量是有显著差别的时刻之间需要的服务量是有显著差别的.如：电话接如：电话接线员、公交乘务员、护士等较长时间的服务机构，因线员、公交乘务员、护士等较长时间的服务机构，因而合理安排可提高效率，减少雇员而合理安排可

26、提高效率，减少雇员.如下是某航空公如下是某航空公司的售票员人数问题，假设每日工作司的售票员人数问题，假设每日工作 8 小时且连续工小时且连续工作，由统计资料得各时段需要的最少人数作，由统计资料得各时段需要的最少人数 .问该公司问该公司最少需雇佣多少售票员？最少需雇佣多少售票员？第17页/共30页第十七页，共30页。时段时段始末时间始末时间至少需要至少需要的售票员数的售票员数108：0010：0010210：0012：008312：0014：009414：0016：0011516：0018：0013618：0020：008720：0022：005822：0024：0033 整数(zhngsh)规

27、划的应用举例Solution:由表中情况由表中情况(qngkung)可知，只可知，只需考虑时段需考虑时段 15的上班人数即可的上班人数即可.因为因为1、9点、点、11点等上班人数不点等上班人数不影响需要人数；影响需要人数；2、时段、时段 5 以后以后上班的人员工作时间不到上班的人员工作时间不到 8小时小时.设设 xj 表示第表示第 j 个时段开始工作个时段开始工作(gngzu)的人数，的人数，j=15.可用可用0-1规划表示规划表示 进一步讨论进一步讨论,售售票员的吃饭时间、票员的吃饭时间、工资等工资等.第18页/共30页第十八页，共30页。第五章第五章 整数整数(zhngsh)(zhngsh

28、)规划规划各班工作时间各班工作时间(shjin)及工资：及工资：班次班次上班时间上班时间休息时间休息时间月工资月工资108：0017：0011：3012：30800208：0017：0012：0013：00800308：0017：0012：3013：30800412：0021：0015：3016：30850512：0021：0016：0017：00850612：0021：0016：3017：30850715：0024：0018：3019：30900815：0024：0019：0020：00900915：0024：0019：3020：30900时段时段所需售所需售票员数票员数班班 次次12345

29、678901（08：0011：30）1011100000002（11：3012：00）601100000003（12：0012：30）900111100004（12：3013：00）910011100005（13：0013：30）911011100006（13：3015：00）1111111100007（15：0015：30）1111111111108（15：3016：00）1111101111109（16：0016：30）1211100111110（16：3017：00）1311110011111（17：0017：30）1400011011112（17：3018：30）15000111111

30、13（18：3019：00）800011101114（19：0019：30）800011100115（19：3020：00）800011110016（20：0020：30）500011111017（20：3021：00）500011111118（21：0024：00）3000000111设设 xj(j=19)为第为第 j 班次班次(bnc)的的上班人数上班人数.min Z=800(x1+x2+x3)+850(x4+x5 +x6)+900(x7+x8+x9)s.t.x1+x2+x310 x2+x36共共18个约束条件个约束条件.第19页/共30页第十九页，共30页。3 整数规划的应用(yngyn

31、g)举例Example 7（装配线平衡（装配线平衡(pnghng)问题）问题）若某工厂的产品装配若某工厂的产品装配线由线由 6 道工序组成，各工序的加工道工序组成，各工序的加工(ji gng)时间及紧前工序见表时间及紧前工序见表:工序工序加工时间加工时间(分分)紧前工序紧前工序1325322461，3582634 若这条装配线设若干个工作站，若这条装配线设若干个工作站，被装配的产品在这些编了号的工作站被装配的产品在这些编了号的工作站上流水移动时，每个工作站都要完成上流水移动时，每个工作站都要完成一道或几道工序，假设每个工作站加一道或几道工序，假设每个工作站加工被装配的产品时至多耗时工被装配的产

32、品时至多耗时 10分钟分钟.问最少应设几个工作站，每个工作站完成哪些工序问最少应设几个工作站，每个工作站完成哪些工序?流水节拍流水节拍Solution:显然，需要的工作站不会多于显然，需要的工作站不会多于 4 个个.设设在装配线上有工作站在装配线上有工作站 j否则否则 j=14工序工序i 在工作站在工作站 j上进行上进行否则否则 i=16;j=14第20页/共30页第二十页，共30页。第五章第五章 整数整数(zhngsh)(zhngsh)规划规划目标目标(mbio)：min Z=w1+w2+w3+w4对工序对工序(gngx)i,它应恰在某一工作站上完成，即它应恰在某一工作站上完成，即 xi1+

33、xi2+xi3+xi4=1 i=16 对工作站对工作站 j，如果设立则在该工作站上完成的各道工，如果设立则在该工作站上完成的各道工序所需的时间总和不超过序所需的时间总和不超过 10 分钟，即分钟，即3x1j+5x2j+2x3j+6x4j+8x5j+3x6j 10 j=143x1j+5x2j+2x3j+6x4j+8x5j+3x6j 10wj如果不设立，则不能将任何工序分配给该工作站，即如果不设立，则不能将任何工序分配给该工作站，即 wj=0 则则 xij=0 i=16 所以，上式改为所以，上式改为第21页/共30页第二十一页，共30页。3 整数规划(guhu)的应用举例工序工序加工时间加工时间(

34、分分)紧前工序紧前工序1325322461，3582634 对于紧前约束，如工序对于紧前约束，如工序 2 必须在必须在工序工序 3 之前完成，如果工序之前完成，如果工序 3 在最后在最后(zuhu)一个工作站一个工作站 4 上完成，显然，工序上完成，显然，工序 2 必在它之前完成必在它之前完成 .如果如果(rgu)工序工序 3 在工作站在工作站 3 上完成上完成(x33=1)，则工序，则工序 2 必须在工作站必须在工作站 1、2、3 上完成，即上完成，即x21+x22+x23 x33类似类似 x21+x22 x32，x21 x31其他其他x11+x12+x13 x43，x11+x12 x42，

35、x11 x41x31+x32+x33 x43，x31+x32 x42，x31 x41 以上是以上是 6 道工序、道工序、4个工作站、个工作站、5个工序顺序约束的装配线个工序顺序约束的装配线平衡问题，共有平衡问题，共有28个变量、个变量、29个约束条件个约束条件.Zmin=3x11=x21=x31=x42=x62=x53=1其余为其余为 0 紧前约束也可以用一个不等式描述：紧前约束也可以用一个不等式描述：x31+2x32+3x33+4x34 x21+2x22+3x23+4x24第22页/共30页第二十二页，共30页。第五章第五章 整数整数(zhngsh)(zhngsh)规划规划Example 8

36、 （排序（排序(pi x)问题）问题）工艺路线工艺路线j#机床加工时间（小时）机床加工时间（小时）1234i#产产品品1 8 1 22 5 9 63 0 2 10 0 用编号为用编号为 1#、2#、3#、4#的的4种机床生产种机床生产 3种产品种产品 1#、2#、3#，产品的工艺路线，产品的工艺路线(lxin)及及工序加工时间见表工序加工时间见表.一台机床一次只能加工一个产品一台机床一次只能加工一个产品,现要求现要求 2#产品从开始加工到完成经历时间不超过产品从开始加工到完成经历时间不超过 29 小小时时.问如何确定各产品在机床上的加工顺序，使在最短问如何确定各产品在机床上的加工顺序，使在最短

37、时间时间内制成全部产品内制成全部产品.Solution:设设 xij 为为 i#产品在机床产品在机床 j#上开始加工时间上开始加工时间.第一组约束为每一产品应按工艺路线进行：第一组约束为每一产品应按工艺路线进行：第23页/共30页第二十三页，共30页。3 整数(zhngsh)规划的应用举例 第二组约束为一族选择性第二组约束为一族选择性的约束条件，以保证每一机床的约束条件，以保证每一机床同一时间只能加工同一时间只能加工(ji gng)一个产品：一个产品：如对如对 1#有有：或或引进引进(ynjn)0-1 变量变量 y1,上述选择性约束条件为：上述选择性约束条件为：类似类似 y2,y3,y4 为为

38、 0-1 变量，对机床变量，对机床 2#、3#、4#有有工艺路线工艺路线j#机床加工时间（小时）机床加工时间（小时）1234i#产产品品1 8 1 22 5 9 63 0 2 10 0M 为充分大为充分大的正数的正数第24页/共30页第二十四页，共30页。第五章第五章 整数整数(zhngsh)(zhngsh)规划规划三个产品三个产品(chnpn)都完工的时间为：都完工的时间为：将它化为线性约束将它化为线性约束(yush)目标函数为目标函数为 2#产品从产品从 1#机床开始加工机床开始加工到到 4#机床加工完成其经历时间机床加工完成其经历时间要求为：要求为：工艺路线工艺路线j#机床加工时间（小时

39、）机床加工时间（小时）1234i#产产品品1 8 1 22 5 9 63 0 2 10 0第25页/共30页第二十五页，共30页。3 整数规划的应用(yngyng)举例Example 9 (利润利润(lrn)分段线性问题分段线性问题)工时定额工时定额(小时小时/件件)产品产品总有总有效效工时工时甲甲乙乙车间车间金工金工43480装配装配25500售价售价(元元/件件)300520 某厂生产甲、乙两种产品某厂生产甲、乙两种产品(chnpn)，需经，需经过金工和装配两个车间加工，相关数据如表所示：过金工和装配两个车间加工，相关数据如表所示：产品乙无论生产批量大小，每件产品生产成本总产品乙无论生产批

40、量大小，每件产品生产成本总为为 400元，试根据产品甲生产成本的下列两种情况分别元，试根据产品甲生产成本的下列两种情况分别建立数学模型求利润最大建立数学模型求利润最大.1、产品甲的生产成本分段线性：第、产品甲的生产成本分段线性：第 1 30 件，每件件，每件 成本为成本为 200 元；第元；第 31 70 件，每件成本为件，每件成本为 190 元元;从第从第 71 件开始，每件成本为件开始，每件成本为 195 元元.2、产品甲的产量不超过、产品甲的产量不超过 40 件时，每件成本件时，每件成本 200 元，但元，但 超过超过 40 件，则甲的全部产品每件成本都为件，则甲的全部产品每件成本都为

41、195 元元.第26页/共30页第二十六页，共30页。第五章第五章 整数整数(zhngsh)(zhngsh)规划规划Solution:工时定额工时定额(小时小时/件件)产品产品总有总有效效工时工时甲甲乙乙车间车间金工金工43480装配装配25500售价售价(元元/件件)300520 设设 甲、乙产品的生产数量甲、乙产品的生产数量(shling)分别为分别为 x1，x2 件件.由条件由条件(tiojin)知产品甲知产品甲至多生产至多生产 120 件件.1、令、令 x1=x3+x4+x5 其中其中 x3、x4、x5 满足下列条件：满足下列条件：当当 0 x1 30 时，时，有有 0 x3 30，x

42、4=x5=0当当 30 x1 70 时，时，有有 x3=30，0 x4 40，x5=0当当 70 x1 120 时，有时，有 x3=30，x4=40，0 x5 50 此时，产品甲所获利润为此时，产品甲所获利润为 100 x3+110 x4+105x5，产品乙所获利润为产品乙所获利润为 120 x2.引进引进 0-1 变量变量 y1，y2，将上述条件化为如下约束条件：，将上述条件化为如下约束条件：30y1 x3 30，40y2 x4 40y1，0 x5 50y2 讨论讨论 y1、y2的取值，如果的取值，如果 y1=0，则必有，则必有 y2=0，情，情形形1 成立；成立；y1=1，y2=0，情形，

43、情形2 成立；成立；y1=1，y2=1,情形情形3 成立；成立；y1=0，y2=1 是不可行的是不可行的.max Z=100 x3+110 x4+105x5+120 x2 s.t.4x3+4x4+4x5+3x2 480 2x3+2x4+2x5+5x2 500 30y1 x3 30 40y2 x4 40y1 0 x5 50y2 xj I+0 j=2,3,4,5 yi=0 or 1 i=1,2.第27页/共30页第二十七页，共30页。3 整数规划(guhu)的应用举例2、令、令 x1=x3+x4 其中其中(qzhng)x3、x4 满足下列条件：满足下列条件：当当 0 x1 40 时，时，有有 0

44、x3 40，x4=0;当当 40 x1 120 时，时，有有 x3=40，0 x4 80;引进引进(ynjn)0-1 变量变量 y，将上述条件化为如下约束条件：，将上述条件化为如下约束条件：40y x3 40，0 x4 80y.如果如果 y=0，产品甲的利润为，产品甲的利润为 （300-200）x1=100 x3如果如果 y=1，产品甲的利润为，产品甲的利润为 105x3+105x4=100 x3 +105x4+5x3=100 x3+105x4+200综上产品甲的利润为综上产品甲的利润为 100 x3+105x4+200y max Z=100 x3+105x4+200y+120 x2 s.t.4x3+4x4+3x2 480 2x3+2x4+5x2 500 40y x3 40 0 x4 80y xj I+0 j=2,3,4 y=0 or 1.第28页/共30页第二十八页，共30页。第五章第五章 整数整数(zhngsh)(zhngsh)规划规划 完完第29页/共30页第二十九页，共30页。感谢您的观看感谢您的观看(gunkn)！第30页/共30页第三十页，共30页。