第四章整数规划讲解.ppt

对于求整数解的线性规划问题，能否采用四舍五入或者去尾的方法将求得的非整数解加以解决呢？如果不能，有无有效的解决方案呢？ 【例】 设整数规划问题如下 用图解法求出最优解为：x1＝3/2, x2 = 10/3，且有Z = 29/6 整数规划问题的求解方法： 例： 用分枝定界法求解 上述分枝过程可用下图表示： 作业： 课本P127 T6（2） 第三章 案例分析 1、6~10人一组，自由组合 2、完成课本P100，案例3.5.1 3、建立线性问题数学模型并利用软件求解 4、小组为单位上交word电子版求解结果 5、文件中请注明每个人的分工情况 4.2.2割平面方法 割平面法的思想是，求解不含整数条件的线性规划，然后不断增加适当的线性约束条件，割掉原可行域中不含整数可行解的一部分，最终得到一个具有整数坐标的极点的可行域，而该极点恰好是原整数规划问题的最优解。 换出基变量的确定规则。 一般单纯形方法是以最大检验数对应的非基变量作为换出基变量，然后将已得到的基变量的值与换入基变量所在的列的正分量相除，以最小比值对应的基变量作为换出基变量。 在对偶单纯形求解时，以基变量的负值中最小的对应的为换出基变量，将检验数与换出基变量所在行的负分量相除，然后选取最小比值对应的非基变量为换入基变量。 加入松弛变量 用对偶单纯形法求解 第四章 案例分析 1、6~10人一组，自由组合 2、完成课本P122，案例4.3.1 3、建立线性问题数学模型并利用软件求解 4、小组为单位上交word电子版求解结果 5、文件中请注明每个人的分工情况 作业 教材P127 第6题(2)。 首先注意其中一个非整数变量的解，如 ，在松弛问题中的解，于是原问题增加两个约束条件 将两个约束分别并入原问题的松弛问题（LP）中，形成两个分支，即后继问题（LP1）和(LP2)，这并不影响原问题的可行域。 解（LP1），得最优解为 继续对（LP1）进行分解。对（LP1）增加两个约束条件 解（LP11），得最优解为 继续对（LP12）进行分解。对（LP12）增加两个约束条件 将两个约束分别并入（LP12）中，形成两个分支，即后继问题（LP121）和（LP122），这并不影响（LP12）的可行域。解（LP121），得最优解为 表4－10 （4） 4 13 4 2 虚工作人员 13 16 14 9 丙 15 14 4 10 乙 4 13 15 2 甲 R G J E 任务 人员 在不平衡指派问题中，在工人数大于工作数情况下，则增加虚工作：某人必须被指派工作。则该人从事虚工作的时间花费为“M ”，表示工作花费时间无穷大，其余人从事该虚工作的时间花费为0。工人不能得到指派时存在一定赔偿损失费时，将各人得到的赔偿费作为从事该虚工作的时间花费。 当工作数大于工人数时，则增加虚工作人员：若某项工作必须完成，则该虚工作人员从事必须完成工作的时间花费为“M ”，表示该项工作不得由虚工作人员从事，虚工作人员从事其它工作的时间花费为0；若工作不能完成时存在惩罚损失费时，则直接将惩罚费作为虚工作人员从事各项工作的时间；若某人不能完成某项工作，则在系数矩阵中，相应位置处填入“M ”。 4.3案例分析 4.3.1分销中心选址问题 A公司在D1处经营一家年生产量为30万件产品的工厂，产品被运输到位于M1、M2、M3的地区分销中心。由于预期将有需求增长，该公司计划在D2，D3，D4，D5中的一个或多个城市建新工厂以增加生产能力，根据调查，被提议四个城市中建立工厂的固定成本和年生产能力如下表4－11所示： 40000 50000 D4 30000 375000 D3 20000 300000 D2 10000 175000 D1 年生产能力（万件） 年固定成本（万元） 目标工厂 该公司对3个地区分销中心的年需求量做了如下预测，见表4－12;根据估计，每件产品从每个工厂到各分销中心的运费（万元）见表4－13： 表4－12 表4－13 20000 M3 20000 M2 30000 M1 年需求量（万件） 分销中心 3 4 8 D5 2 4 10 D4 5 7 9 D3 4 3 4 D2 3 2 5 D1 M3 M2 M1 请问：公司是否需要在四个地区中建厂，若建厂后，分厂到各分销中心如何配送调运？ 解：引入0-1变量表示在Di处是否建立分厂, 设 表示从每个分厂到分销中心的运输量。年运输成本和经营新厂的固定成本之和为： 考虑被提议工厂的生产能力约束条件，以D1为例，有