多元函数极值的解法.ppt

5. 整数规划Integer Programming 整数规划模型 整数规划的解法 分支定界法 割平面法 0-1规划的隐枚举法 整数规划模型 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。 整数规划模型 整数线性规划问题的种类： 纯整数线性规划：指全部决策变量都是整数变量的整数线性规划。 混合整数线性规划：决策变量中有一部分是整数变量，另一部分是连续变量的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。 整数规划模型 整数规划模型 解：这是一个选址问题(Location Model)，关键是要确定在A3和A4中哪一个。为此，引入两个0-1变量： 整数规划模型 整数规划模型 整数规划模型 例5.3 指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 整数规划模型 5.4 固定成本问题。某公司制造大、中、小三种尺寸的容器，所需要的资源、可用量及各容量的利润如下表所示。若进行生产，每种容量都需要支付一笔固定成本，大号为200万元，中号为150万元，小号为100万元；若不进行生产，则不需要支付固定成本。问如何安排生产才能使利润最大化？ 整数规划模型 5.5 互斥约束。某产品有A1和A2两种型号，需要经过B1、B2和B3三道工序，其中B3有B31、B32和B33三种加工方法，可选择其中之二。产品利润、加工工时、工时限制如下表所示，问如何安排生产才能使利润最大化？ 整数规划模型 5.6 分段函数。某公司使用两种原油（A和B）合成两种汽油（甲和乙）。甲、乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现在有原油A和B的库存量分别为500吨和1000吨，还可以从市场上买到不超过1500吨的原油A。设原油A的购买量为x，则购买价为： 整数规划模型 5.7 面试顺序问题。有4名同学到一家公司参加3个阶段的面试：每个同学先找秘书初试，之后到部门主管处复试，最后到经理处面试，各个阶段都不允许插队。由于4名同学的专业背景不同，所以每个人在3个阶段的面试时间也不同，如下表所示。这4名同学约定他们全部面试完毕后一起离开公司，假定早上8:00开始面试，问他们最早何时能离开公司？ 整数规划模型 5.8 下料问题。某钢管零售商从钢管厂进货，将钢管按照顾客要求切割后输出，从钢管厂进货时原料钢管长度都是19m。现有一客户需要50根4m长、10根5m长、20根6m长、15根8m长的钢管。此外，零售商为避免生产过程复杂化，只会采用最多3种切割模式。问零售商如何下料，才能使耗费的原料钢管最少？ 整数规划的解法 整数规划模型的可行域不是凸集，因此无法借鉴线性规划理论的结论，需要另寻他途。 一种自然的想法是：先求解整数规划对应的松弛问题，然后再将所得最优解取整。但取整法所得的结果可能不是可行解，即使所得的是可行解，也不一定还是最优的。 整数规划的解法 整数规划的解法 对于可行域是有界的整数规划模型，由于其可行解是有限的，因此容易想到用穷举法求解。穷举法对于规模小的整数规划问题是有效、可行的，但是对于稍大规模的整数规划问题就无能为力了。 例如，对于有10个员工、10个岗位的指派问题，会有100个0－1变量。假设用一台计算机来穷举所有的2100个解，每秒检查10000亿个解，完成穷举工作将需要： 4.01969×1010年 这样长的时间显然是不能接受的。 分支定界法 分支定界法 分支定界法 分支定界法 分支定界法 分支定界法 分支定界法 在分支树中，分支问题有四种情况： ①分支问题无解 → 剪支 ②分支问题有整数解 → 剪支 ③分支问题有非整数解 目标函数值小于等于当前下界 → 剪支 目标函数值大于当前下界 → 分支 分支定界法 割平面法 割平面法也称为Gomory法，是一种逐次逼近方法，但用割平面法解题时经常会遇到收敛很慢的情形，因此很少单独使用。 割平面法的基本思路是：从整数规划的松弛问题开始，每次向松弛问题增加一个约束条件，从可行域中切割掉一个区域（被割掉的区域不包含整数解，但包含当前松弛问题的最优解），直到得到的最优解是整数解为止。 割平面法 割平面法 割平面法 割平面法 0-1规划的隐枚举法 对0-1整数规划问题，除可以用前面的分支定界法和割平面法求解之外，还可以用隐枚举法求解。隐枚举法是一种比较“聪明”的枚举方