运筹学整数规划1ppt课件

.Chapter4整数规划、整数规划的性质和应用分支和边界方法分配问题和匈牙利法，本章主要内容：整数编程的特性和应用，整数编程(以下简称IP)中要求部分或全部决策变量作为整数值的计划问题称为整数编程。在不考虑整数条件的情况下，由剩馀目标函数和约束条件组成的计划问题称为该整数编程问题的缓解问题。松弛问题为线性配置时，整数编程称为整数线性配置。整数线性规划数学模型的一般形式：整数规划的性质和应用，整数线性规划问题的种类：纯整数线性规划：表示所有决定变量都必须具有整数值的整数线性规划。混合整数线性规划：决定变量的一部分采用整数值，另一部分不采用整数值的整数线性规划。类型0-1整数线性编程：决策变量只能使用值为0或1的整数线性编程。整数编程的特性和应用，整数编程的典型示例，示例4.1工厂A1和A2生产货物。这种物资供应不足，需要再建一座工厂。相应的工厂建设方案有A3和A4。这种物资的需求有B1、B2、B3和B4。各工厂的年生产能力，各地的年需求，各工厂到各需求地的单位物资运费cij见下表。工厂A3或A4开工后，年生产费分别估计为1200万或1500万韩元。只有建设工厂A3或A4，预计以后年度总费用才会降到最低。整数编程的特性和应用，解决方案：这是事先不知道要建设A3还是A4的材料运输问题，因此不知道新工厂运行后的实际生产材料。为此，请引入变量0-1:并将xij设置为从Ai运输到Bj的材质数，即千吨。z表示总成本，单位万元。这个计划问题的数学模型是，整数规划的性质和应用，混合整数规划问题，整数编程的特性和应用，示例4.2现有资金总额为b。有n个投资项目可供选择，项目j所需的投资额和预期收益分别为aj和CJ (j=1，2，n)，另外还有三个条件，如果由于各种原因选择项目1，则还必须选择项目2。相反，不需要在项目3和项目4中至少选择一个。选择项目5，6，7中正好2个。如何选择投资项目才能最大化总预计收益。整数编程的特征和应用，求解：对于每个投资项目，都有可选择的和不可选择的项目，因此分别用0和1表示，XJ表示对第j个项目的决策选择。注意：投资问题是，可以表示为整数规划的特征和应用、示例4.3分配问题或分配问题等。人事部门想从4人到4人的其他工作岗位各安排一人。在不同的岗位上检查了四个人的成绩(百分制)，从表中可以看出，如何安排他们的工作，使总成绩最好。整数编程的特点和应用，设置，数学模型如下：必须分别执行操作。约束包括：整数编程的特性和应用，每个作业只能部署一个人。约束包括：变量约束：整数规划的性质和应用，整数规划问题解决的特点：整数规划问题的可行解集是松弛问题的可行解集的子集。整数规划问题的可行解必须是缓解问题的可行解(不一定如此)，但最优解的目标函数值不高于最优解的目标函数值。整数编程的特性和应用，示例4.3将整数编程问题设置为：先不考虑整数约束，而是线性编程问题(通常称为松弛问题)。整数规划的性质和应用，使用图形方法导出最佳解决方案：x1=3/2，x2=10/3和Z=29/6，使用整数解决方案(最佳解决方案):舍入方法时为4点(1，3)，(显然，两者都不能是整数编程的最优解。，x1，x2，930；3，3，(3/2，10/3)，可能的解决方案在线性规划问题的可执行域内，是整数点。因此，整数规划问题的可行解集是有限集，如右图所示。其中，(2，2)，(3，1)点的目标函数值为Z=4。整数规划的性质和应用，整数规划问题解决方法：分支和切面方法匈牙利方法(分配问题)，分枝定界法，1)求整数规划松弛问题的最优解；当松弛问题的最优解满足整数要求时，得到整数规划的最优解。否则，请继续下一步。2)分支和边框：随机选择非整数变量Xi，为松弛问题添加约束。xixi和Xi 1构成了两个新的松弛问题：分支。新的松弛问题具有特性。如果原始问题找到最大值，则目标值是分支问题的上限。如果原始问题寻找最小值，则目标值是分支问题的下限。检查所有分支的解和目标函数值，如果分支为整数，目标函数值大于(max)其他分支的目标值，则剪切其他分支不再计算，如果存在非整数解，并且目标值大于(max)整数解的目标值，则需要继续分支，然后检查，直到得到最佳解。分支和边界方法故障排除步骤：分支和边界方法，示例4.4使用分支和边界方法解决整数编程问题。首先移除整数约束，然后是一般线性程式设计问题(原始整数程式设计问题的平滑问题)，LP，ip。分支和边界方法，如图所示，使用图形方法查找平滑问题的最佳解决方案。，x1，x2，330；3c 3，(18/11，40/11)，x1=18/11 1.64的值x11，x12的x2=40/113.64的值x23，x24的值首先，寻找分支分隔方式，分别为(LP1)和(LP2)的最佳解决方案。分支和边界方法，首先查找LP1，如图所示。现在从点b获得最佳解决方案。在X1=1，x2=3，z (1)