第五章整数规划(第7讲)

1、 第五章第五章 整数规划整数规划 Optimizing Methods第五章第五章 整数规划整数规划1 整数规划问题及其数学模型整数规划问题及其数学模型2 整数规划的解法整数规划的解法3 整数规划的应用举例整数规划的应用举例第五章第五章 整数规划整数规划 在在 LP 问题的讨论中，有些最优解是小数问题的讨论中，有些最优解是小数 . 但对但对于某些具体问题常有要求最优解是整数于某些具体问题常有要求最优解是整数( 即整数解即整数解) . 如决策变量为机器的台数、人数、车辆数如决策变量为机器的台数、人数、车辆数 etc. 如果在问题中所有决策变量有整数限制，称为如果在问题中所有决策变量有整数限制，称

2、为 纯纯整数规划整数规划( Pure IP ) 或或 全整数规划全整数规划 ( All IP )； 如果在问题中仅部分决策变量有整数限制，称为如果在问题中仅部分决策变量有整数限制，称为 混合整数规划混合整数规划( Mixed IP ) ； 如果在问题中决策变量仅取如果在问题中决策变量仅取 0 、1，称为，称为 0-1 (整整数数) 规划规划 .Integer Programming1 整数规划问题及其数学模型整数规划问题及其数学模型1 整数规划问题及其数学模型整数规划问题及其数学模型 货货 物物每箱体积每箱体积（m3）每箱重量每箱重量（kg）每箱利润每箱利润（百元）（百元） 甲甲5220 乙乙

3、4510托运限制托运限制2413Example 1 （装载问题）（装载问题） 某厂拟用集装箱托运甲、乙某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运限制两种货物，每箱的体积、重量、可获利润及托运限制如表，问两种货物各托如表，问两种货物各托运几箱，可获利润最大？运几箱，可获利润最大？Solution: 设设 x1、x2 分分别为甲、乙两种货物托别为甲、乙两种货物托运箱数运箱数.则1212121212max2010. . 54242513,0,Zxxstxxxxx xx xI这是一个这是一个 Pure IP 问题问题.第五章第五章 整数规划整数规划1232yyy1231 3ii

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

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

6、设呢？1231 3iiiiixxxa yi客户端需求满足：客户端需求满足：目标（每月的费用）：目标（每月的费用）：111213212223313233123111213121222323132333112131122232132333123min4532344510090120. .70809040604520,01,1,2,3ijiZxxxxxxxxxyyystxxxyxxxyxxxyxxxxxxxxxyyyxyori j这是一个这是一个 Mixed IP 问题问题.可用于设计分配系统、新生活小区的设置可用于设计分配系统、新生活小区的设置 etc.1 整数规划问整数规划问题及其数学模型题及其

7、数学模型1niiyj123123256180 ,437240 xxxxxx 在在 Ex.2 中，引进中，引进 01 变量给出了在变量给出了在 n 件任务中件任务中,选择选择 j 项的约束项的约束1mijiijxa y又用又用 来刻画不设来刻画不设第第 i 项任务，则项任务，则 xij j = 1n 都不起作用，为零都不起作用，为零.可应用于选择性可应用于选择性约束条件中约束条件中 某工厂生产第某工厂生产第 j 种产品的数量为种产品的数量为 xj ( j =1,2,3) 其使其使用的材料在甲、乙中选择一种，其消耗约束分别为：用的材料在甲、乙中选择一种，其消耗约束分别为：其他资源约束条其他资源约束

8、条件未列出件未列出引进引进 01 变量变量 y 11nijjija xbip01y选择材料甲选择材料甲选择材料乙选择材料乙123123256180,437240(1)xxxMyxxxMyM 为充分大的为充分大的正数正数一般地，假定要在一般地，假定要在 p个约束条件个约束条件 中中至少要选择至少要选择 q 个约束条件得到满足，可引进个约束条件得到满足，可引进0-1变量变量 y11101.nijjiijpiiia xbMyipypqyor第五章第五章 整数规划整数规划71maxjjjZc x71. .3501,1 7jjjjsta xxorjExample 3 （背包问题）（背包问题） 假设有人要

9、出发旅行，考虑带七假设有人要出发旅行，考虑带七种物品，每件物品的重量与价值如表种物品，每件物品的重量与价值如表. 现在假设他最多带现在假设他最多带 35kg 物品，问该带物品，问该带哪几件物品使总价值最大？哪几件物品使总价值最大？ 物品物品重量重量 aj价值价值 cj 1 3 12 2 4 12 3 3 9 4 3 15 5 15 90 6 13 26 7 16 112Solution:10jx如果带第如果带第 j 件物品件物品否则否则 j = 17这是一个这是一个 0-1 规划问题规划问题. 一般整数规划中的变量一般整数规划中的变量 x , 也可用也可用 0-1 变量替代，如变量替代，如0

10、x15 ，x=x020+x121+x222+x323 其中其中 x0,x1,x2,x3 为为0-1 变量变量 .1 整数规划问题及其数学模型整数规划问题及其数学模型125424xx12121212max2010. . 54242513,0,Zxxstxxxxx x 参见参见 Ex.1, 去掉整数约束，得去掉整数约束，得舍入化整舍入化整o 1 2 3 4 5 x14321x2122513xx由图解法得最优由图解法得最优解为：解为：x1= 4.8, x2= 0 Zmax = 96显然，显然，x1 不是整数不是整数. 是否可以根据化整的原问题的解？是否可以根据化整的原问题的解？x1=5、x2=0 不

11、是可行解，不是可行解， x1=4、x2=0 Z=80 . 但是但是 x1=4、x2=1 也可行也可行 且且 Z=90 .所以，所以，“舍入化整舍入化整”的结果：的结果： 1、化整后未必可行；、化整后未必可行；2、即使是可行解，也未必是最优解；、即使是可行解，也未必是最优解；3、用这个方法即使能得到最优解，但如果有、用这个方法即使能得到最优解，但如果有n 个变个变 量，则取舍方案有量，则取舍方案有 2n 种，计算量也是很大的种，计算量也是很大的.Go back第五章第五章 整数规划整数规划125424xxo 1 2 3 4 5 x14321x2122513xx 有人在研究在建立模型中，什么条件下

12、有人在研究在建立模型中，什么条件下 LP 问题的问题的解一定是整数解？解一定是整数解？ 如：如： 运输问题运输问题从从 Ex.1 的讨论，可得到一些启迪的讨论，可得到一些启迪1、是否能在是否能在 LP 的约束区域中的约束区域中, 切切去去 n 块不含整数解的可行域使整数块不含整数解的可行域使整数解作为顶点，则解作为顶点，则 LP 的最优解即为的最优解即为整数解整数解 ；如增加约束如增加约束 x14, 则则 LP 问题的解即为整数解问题的解即为整数解;2、在在 LP 的可行域中，整数点不多，的可行域中，整数点不多，（12个）个）是否可以用穷举法是否可以用穷举法.2 整数规划的解法整数规划的解法一

13、、割平面法一、割平面法 1959年由年由 R.E.Gomory 首先提出，从此使首先提出，从此使 IP 逐渐逐渐形成为一个独立的运筹学分支形成为一个独立的运筹学分支. 割平面法的实质割平面法的实质是用解是用解 LP 问题的方法求解问题的方法求解 IP 问题；问题；割平面法的割平面法的基本思想基本思想是通过对是通过对 LP 问题的求解，如果最问题的求解，如果最优解是整数解，则就是优解是整数解，则就是 IP 的解；否则设法对的解；否则设法对 LP 问题问题增加约束增加约束(割平面割平面)，把，把 LP 问题的可行域中去掉一部分问题的可行域中去掉一部分不含整数解的，再求不含整数解的，再求 LP 问题

14、，反复进行问题，反复进行 .割平面法的割平面法的关键关键在于如何寻找适当的切割约束条件在于如何寻找适当的切割约束条件. 用割平面法求解用割平面法求解 IP 问题常常会计算量大、收敛速度问题常常会计算量大、收敛速度慢的情况，但在理论上是重要的，被认为是慢的情况，但在理论上是重要的，被认为是 IP 的核心的核心.第五章第五章 整数规划整数规划二、分支定界法二、分支定界法分支与定界分支与定界法的基本思想是对有约束条件的最优化问法的基本思想是对有约束条件的最优化问题的所有可行解（其数目为有限集）空间适当地进行题的所有可行解（其数目为有限集）空间适当地进行搜索搜索 . 具体执行时，把可行解空间不断分割为

15、越来越小具体执行时，把可行解空间不断分割为越来越小的子集（称为分支），并确定每个分支内的解值的下的子集（称为分支），并确定每个分支内的解值的下界或上界（称为定界）界或上界（称为定界）. . 在每次分支后，对凡是界超在每次分支后，对凡是界超出已知可行解值的子集被剪去，从而不断缩小搜索范出已知可行解值的子集被剪去，从而不断缩小搜索范围围. . 这个过程一直进行到找出最优解为止，该可行解这个过程一直进行到找出最优解为止，该可行解的值不大于或不小于任何子集的界的值不大于或不小于任何子集的界 .优点：优点：1、适用面广、适用面广 2、可检查较少的解（运、可检查较少的解（运气好）气好）3、可获得最优解、可

16、获得最优解缺点：本质是穷缺点：本质是穷举，复杂性大于穷举法举，复杂性大于穷举法2 整数规划的解法整数规划的解法设设min( )(1)x Af xmin( )(2)x Bf xAB如果如果 则称问题（则称问题（2）是问题（）是问题（1）的松弛问题）的松弛问题. .Note : 1、松弛问题未必比原问题难解；、松弛问题未必比原问题难解；如：如：整数规划与线性规划；整数规划与线性规划；TSP 与指派问题与指派问题 etc. 如：如： A：寻找全国：寻找全国18 岁百米最快的运动员岁百米最快的运动员.B：寻找：寻找全国所有百米最快的运动员全国所有百米最快的运动员. .显然，显然，B 问题是问题是 A

17、问题的松弛问题，且问题的松弛问题，且B 问题更易解问题更易解 .2、如果松弛问题易解，则先解松弛问题是有益的如果松弛问题易解，则先解松弛问题是有益的 .1）设设 x0 是松弛问题的最优解，且是松弛问题的最优解，且 则原问题已解则原问题已解0 xA0 xA2）即使即使 给出了原问题最优值的界给出了原问题最优值的界 f(x0) .x0BABAx0第五章第五章 整数规划整数规划分枝与定界法为什么能少检查一些解？分枝与定界法为什么能少检查一些解？B10sB1B210.2s*10sB3B410.3s*几点注意：几点注意：确定问题（子问题）的最优值的确定问题（子问题）的最优值的界界 通常是通过求解松弛问题

18、，通常是通过求解松弛问题，用松弛问题的解作为界，也可用松弛问题的解作为界，也可以用启发式算法得到以用启发式算法得到 .Note 松弛问题选择的松弛问题选择的原则原则、松弛问题要与原问题的、松弛问题要与原问题的 最优值尽量接近；最优值尽量接近；松弛问题要尽量容易解松弛问题要尽量容易解 . .这两个原则不易统一，所以可选择不同的松弛问题这两个原则不易统一，所以可选择不同的松弛问题2 整数规划的解法整数规划的解法划分方法的选择划分方法的选择原则是希望分出来的子问题容易被查清，可加快计算原则是希望分出来的子问题容易被查清，可加快计算.选哪个活问题先检查选哪个活问题先检查先检查最大上界（极大化问题）的活

19、问题先检查最大上界（极大化问题）的活问题优点：优点：检查子问题较其他规则为少；检查子问题较其他规则为少；缺点：缺点：计算机储存量较大计算机储存量较大先检查最新产生的最大上界的活问题先检查最新产生的最大上界的活问题优点：优点：计算机储存量较少计算机储存量较少 ；缺点：缺点：需要更多的分支运算需要更多的分支运算选择的不同，提供了发挥的余地选择的不同，提供了发挥的余地 分枝与定界法的重要在于它提出了一类新的思分枝与定界法的重要在于它提出了一类新的思路（隐枚举法），使得许多原来不好解决的问题有路（隐枚举法），使得许多原来不好解决的问题有了解决的可能性了解决的可能性. （具有普适性）（具有普适性）第五章

20、第五章 整数规划整数规划1212121212max58. .65945,0,Zxxstxxxxx xx xI125945xxExample 4 用分支定界法求解如右用分支定界法求解如右 IP 问题问题12121212max58. .65945,0,Zxxstxxxxx x126xxSolution:解松弛问题解松弛问题 P0得：得：x1=2.25、x2=3.75 Zmax=41.25去掉整数约束为去掉整数约束为原原问题的松弛问题问题的松弛问题41.25是原问题最优值的上界是原问题最优值的上界进行分支，任选一个不是整数的变量进行分支，任选一个不是整数的变量,如取如取 x2 则可认为则可认为最优解

21、最优解 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 Z5=37*x1=0、x2=5 Z6=40* 此时已没有活问题，所以最此时已没有活问题，所

22、以最优解为优解为 x1=0、x2=5 Zmax=40 .2 整数规划的解法整数规划的解法1232312313123max20816. .42552743753601,1 3jZxxxstxxxxxxxxxxxorjExample 5 （投资方案的最优选择）（投资方案的最优选择） 背包问题可以看成为一个一次性的投资问题，简背包问题可以看成为一个一次性的投资问题，简单的扩展：单的扩展：1、分几次投资；、分几次投资；2、虽然一次性投资，但、虽然一次性投资，但不同的项目有一些政策上的限制不同的项目有一些政策上的限制 etc. 某公司欲对三个项目进行投资，某公司欲对三个项目进行投资，根据预算四年内的投资

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

24、合的一部分就求得最优解，即隐枚举法求得最优解，即隐枚举法.分支定界法是分支定界法是一种隐枚举一种隐枚举.给出一个重要思想给出一个重要思想:设门槛设门槛 (1、可行性、可行性2、目标函数值、目标函数值)第五章第五章 整数规划整数规划1232312313123max20816. .42552743753601,1 3jZxxxstxxxxxxxxxxxorj(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

25、1)(0 1 0)(0 1 1)(1 0 0)(1 0 1)(1 1 0)(1 1 1) 增加一个判别增加一个判别 A , 目标函目标函 数值小于已知可行解的值，数值小于已知可行解的值， 则不必继续计算则不必继续计算 .A 0162028可以改进吗？可以改进吗？(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第五章第五章 整数规划整数规划Example 6 （人员时间安排问题）（人员时间安排问题） 为了尽可能有效地利用劳动力，有必要

26、对一天各为了尽可能有效地利用劳动力，有必要对一天各个不同时刻需要人员的情况作一分析，特别是在一些个不同时刻需要人员的情况作一分析，特别是在一些大型服务性机构中，顾客的需要是重复性的，但不同大型服务性机构中，顾客的需要是重复性的，但不同时刻之间需要的服务量是有显著差别的时刻之间需要的服务量是有显著差别的. 如：电话接如：电话接线员、公交乘务员、护士等较长时间的服务机构，因线员、公交乘务员、护士等较长时间的服务机构，因而合理安排可提高效率，减少雇员而合理安排可提高效率，减少雇员. 如下是某航空公如下是某航空公司的售票员人数问题，假设每日工作司的售票员人数问题，假设每日工作 8 小时且连续工小时且连

27、续工作，由统计资料得各时段需要的最少人数作，由统计资料得各时段需要的最少人数 . 问该公司问该公司最少需雇佣多少售票员？最少需雇佣多少售票员？12345123451234512345. .10138895113013,1 5jstxxxxxxxxxxxxxxxxxxxxxj51minjjZx时段时段始末时间始末时间至少需要至少需要的售票员数的售票员数108：0010：0010210：0012：008312：0014：009414：0016：0011516：0018：0013618：0020：008720：0022：005822：0024：0033 整数规划的应用举例整数规划的应用举例Solut

28、ion: 由表中情况可知，只由表中情况可知，只需考虑时段需考虑时段15的上班人数即可的上班人数即可.因为因为1、9点、点、11点等上班人数不点等上班人数不影响需要人数；影响需要人数；2、时段时段 5 以后以后上班的人员工作时间不到上班的人员工作时间不到8小时小时. 设设 xj 表示第表示第 j 个时段开始工作的人数，个时段开始工作的人数，j =15 .可用可用0-1规划表示规划表示 进一步讨论进一步讨论, 售售票员的吃饭时间、票员的吃饭时间、工资等工资等.第五章第五章 整数规划整数规划各班工作时间及工资：各班工作时间及工资：班次班次上班时间上班时间休息时间休息时间月工资月工资108：0017：

29、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时段时段所需所需售票售票员数员数班班 次次12345678901（08：0011：30）1011100000002（11：3012：00）601100000003（12：0012：30）

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）1500011111113（18：3019：00）800011101114（19：0019：30）800011100115（19：3020：00）80001

31、1110016（20：0020：30）500011111017（20：3021：00）500011111118（21：0024：00）3000000111设设 xj (j=19)为第为第 j 班次的上班人数班次的上班人数.min Z = 800(x1+x2+x3)+850(x4+x5 +x6)+900(x7+x8+x9)s.t.x1+x2+x310 x2+x36共共18个约束条件个约束条件 .3 整数规划的应用举例整数规划的应用举例Example 7 （装配线平衡问题）（装配线平衡问题） 若某工厂的产品装配若某工厂的产品装配线由线由 6 道工序组成，各工序的加工时间及紧前工序见表道工序组成，各

32、工序的加工时间及紧前工序见表:工序工序加工时间加工时间(分分)紧前工序紧前工序1325322461，3582634 若这条装配线设若干个工作站，若这条装配线设若干个工作站，被装配的产品在这些编了号的工作站被装配的产品在这些编了号的工作站上流水移动时，每个工作站都要完成上流水移动时，每个工作站都要完成一道或几道工序，假设每个工作站加一道或几道工序，假设每个工作站加工被装配的产品时至多耗时工被装配的产品时至多耗时 10分钟分钟 .问最少应设几个工作站，每个工作站完成哪些工序问最少应设几个工作站，每个工作站完成哪些工序?流水节拍流水节拍Solution: 显然，需要的工作站不会多于显然，需要的工作站

33、不会多于 4 个个.设设10jw在装配线上有工作站在装配线上有工作站 j否则否则 j = 1410ijx工序工序i 在工作站在工作站 j上进行上进行否则否则 i = 16; j = 14第五章第五章 整数规划整数规划目标：目标： min Z = w1 + w2 + w3 + w4对工序对工序 i , 它应恰在某一工作站上它应恰在某一工作站上完成，即完成，即 xi1 + xi2 + xi3 + xi4 = 1 i = 16 对工作站对工作站 j ，如果设立则在该工作站上完成的各道工，如果设立则在该工作站上完成的各道工序所需的时间总和不超过序所需的时间总和不超过 10 分钟，即分钟，即3x1j +

34、 5x2j + 2x3j + 6x4j + 8x5j + 3x6j 10 j = 143x1j + 5x2j + 2x3j + 6x4j + 8x5j + 3x6j 10wj如果不设立，则不能将任何工序分配给该工作站，即如果不设立，则不能将任何工序分配给该工作站，即 wj = 0 则则 xij = 0 i = 16 所以，上式改为所以，上式改为3 整数规划的应用举例整数规划的应用举例工序工序加工时间加工时间(分分)紧前工序紧前工序1325322461，3582634 对于紧前约束，如工序对于紧前约束，如工序 2 必须在必须在工序工序 3 之前完成，如果工序之前完成，如果工序 3 在最后在最后一

35、个工作站一个工作站 4 上完成，显然，工序上完成，显然，工序 2 必在它之前完成必在它之前完成 . 如果工序如果工序 3 在工作站在工作站 3 上完成上完成 (x33 = 1)，则工序，则工序 2 必须在工作站必须在工作站 1、2、3 上完成，即上完成，即x21 + x22 + x23 x33类似类似 x21 + x22 x32 ，x21 x31其他其他x11 + x12 + x13 x43 ，x11 + x12 x42 ，x11 x41x31 + x32 + x33 x43 ，x31 + x32 x42 ，x31 x41 以上是以上是 6 道工序、道工序、4个工作站、个工作站、5个工序顺序约

36、束的装配线个工序顺序约束的装配线平衡问题，共有平衡问题，共有28个变量、个变量、29个约束条件个约束条件 .Zmin = 3x11=x21=x31=x42=x62=x53=1其余为其余为 0 紧前约束也可以用一个不等式描述：紧前约束也可以用一个不等式描述： x31 + 2x32 + 3x33 + 4x34 x21 + 2x22 + 3x23 + 4x24第五章第五章 整数规划整数规划Example 8 （排序问题）（排序问题）工艺路线工艺路线j # 机床加工时间（小时）机床加工时间（小时）123i #产产品品1 8 1 22 5 9 63 0 2 10 0 用编号为用编号为 1#、2#、3#、

37、4# 的的4种机床生产种机床生产3种产品种产品 1#、2#、3#，产品的工艺路线及，产品的工艺路线及工序加工时间见表工序加工时间见表. 一台机床一次只能加工一个产品一台机床一次只能加工一个产品, 现要求现要求 2# 产品从开始加工到完成经历时间不超过产品从开始加工到完成经历时间不超过 29 小小时时. 问如何确定各产品在机床上的加工顺序，使在最短问如何确定各产品在机床上的加工顺序，使在最短时间时间内制成全部产品内制成全部产品.Solution:设设 xij 为为 i # 产品在机床产品在机床 j # 上开始加工时间上开始加工时间.第一组约束为每一产品应按工艺路线进行：第一组约束为每一产品应按工

38、艺路线进行：#11131314#212222243233 1 : 8 12 : 5 9 3 :2xxxxxxxxxx 3 整数规划的应用举例整数规划的应用举例2111 5xx 1121121111 8 5(1 )xxMyxxMy2232232222133333313314244241449 2(1 )1 10(1 )2 6(1 )xxMyxxMyxxMyxxMyxxMyxxMy 第二组约束为一族选择性第二组约束为一族选择性的约束条件，以保证每一机床的约束条件，以保证每一机床同一时间只能加工一个产品：同一时间只能加工一个产品： 如对如对 1#有有：1121 8xx或或引进引进 0-1 变量变量

39、y1 , 上述选择性约束条件为：上述选择性约束条件为：类似类似 y2, y3, y4 为为 0-1 变量，对机床变量，对机床 2#、3#、4# 有有工艺路线工艺路线j # 机床加工时间（小时）机床加工时间（小时）123i #产产品品1 8 1 22 5 9 63 0 2 10 0M 为充分为充分大的正数大的正数第五章第五章 整数规划整数规划max142433max 2,6,10Cxxx142433 2, 6, 10CxCxCxminZC2421 621 xx 三个产品都完工的时间为：三个产品都完工的时间为：将它化为线性约束将它化为线性约束目标函数为目标函数为 2#产品从产品从 1# 机床开始加

40、工机床开始加工到到 4# 机床加工完成其经历时间机床加工完成其经历时间要求为：要求为：工艺路线工艺路线j # 机床加工时间（小时）机床加工时间（小时）123i #产产品品1 8 1 22 5 9 63 0 2 10 03 整数规划的应用举例整数规划的应用举例Example 9 (利润分段线性问题利润分段线性问题)工时定额工时定额(小时小时/件件)产品产品总有总有效效工时工时甲甲乙乙车间车间金工金工43480装配装配25500售价售价(元元/件件)300520 某厂生产甲、乙两种产品，需经某厂生产甲、乙两种产品，需经过金工和装配两个车间加工，相关数据如表所示：过金工和装配两个车间加工，相关数据如

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