03(7页).doc

第3章 整 数 规 划 3.1 整数规划问题举例 前面介绍的数学规划问题，决策变量是连续变量，但在有些实际问题中，决策变量只能取整数值，这类问题称为整数规划问题，其中整数线性规划是最常遇到的。 【例3-1】钢铁厂板坯物流管理。为防止连铸的板坯降温，要用保温罩保温并迅速送 热轧厂，因此，准时配车很有必要。为制定最优的配车计划，设为i车装载j板坯的决策变量，它是0-1变量，=1表示i车装j板坯；=0表示i车不装j板坯。则可构成如下优化模型： s.t. i=1，2，…，m j=1，2，…，s 式中 ——在第k阶段用车i装载j板坯的运行时间； 第一个约束式表示一辆车只装一类板坯；第二个约束式表示对一类板坯只分配一辆车。这是一个线性0-1规划问题，是典型的指派问题。 【例3-2】氧气生产计划问题。设有N台制氧机，在计划周期T内，各个时段上的 氧气需求量已知，要求在满足各种需求条件下，机组的组合与负荷的分配，使总电能消耗最少。 设xit为第i台制氧机在第t时段的状态变量，xit=1表示运行，xit=0表示不运行。 设yit为第i台制氧机在第t时段的决策变量，yit=1表示启动，yit=0表示不启动。 则可构造如下数学模型 s.t. i=1，2，…，T i=1，2，…，T i=1，2，…，T 式中 ——第i台制氧机产量为下限时的耗电量； ——第i台制氧机起动时的耗电量； ——第i台制氧机可调部分的耗电函数，为可调产量； ，——第i台制氧机产量的调节范围的下限和上限； ——第t时段的氧气需求量； ，——0-1变量。 第一个约束式表示氧气需求约束；第二个约束式表示制氧机可调部分产量应在生产设备能力范围内；第三个约束式表示制氧机运行状态逻辑关系。 这是一个非线性0-1规划问题。 如果将这一非线性特性分段线性化，取 = 式中 J——非线性特性分段数； ——第j段的耗电系数。 引进新的变量，且有 =， 0≤≤1 当Zjit=0时，Pjit=0；当Pjit =1时，Pjit = Mji，Zjit为连续变量，则问题变为混合整数规划问题。例如当T=30，N=7，J=4时，这一模型含有420个0-1整数变量，840个连续变量。 3.2 分支定界方法 整数规划问题的一般形式是 （IP） （3-1a） s.t. ≤0，i=1，2，…，m （3-1b） xj≥0，j=1，2，…，n （3-1c） xj为整数 （3-1d） 当xj只取0或1时，称为0-1整数规划。当变量xj中除了整数以外，若还有取连续量的，则称为混合整数规划。 当f (x)和为线性函数时，称为线性整数规划。如果f (x)或或二者取非线性函数，称为非线性整数规划。在这里只讨论线性整数规划，其一般形式为 （ILP） （3-2a） s.t ≤，i=1，2，…，m （3-2b） xj≥0，j=1，2，…，n （3-2c） 为整数 （3-2d） 目前已提出几种求解整数规划的比较成熟的方法，如分支定界法、隐枚举法、割平面法等。这里只介绍分支定界法。 分支定界法是一种搜索算法，用它解题的过程是对可行域进行系统的搜索的过程。 一个整数规划可以看作是一个线性规划，见式（3-2a）和（3-2c），再加上整数约束（式3-2d），其可行域只是相应线性规划（称为伴随线性规划）问题的可行域一部分，即可行域比线性规划问题的可行域小，因此，应用伴随线性规划求出的极小解，应优于或等于整数规划问题的极小解，其目标函数值是整数规划问题的下界，即≤（对极大问题，应是上界）。这是分支定界法的一个重要基础。 分支定界法的思想是把可行域反复进行分割，分割为越来越小的子集，称为分支；对每个子集的线性规划问题求解，其目标函数的最优值是该子集整数规划的下界：1）如果这个下界比某个已知的可行整数解对应的目标函数值大，那么最优整数解不可能在这一子集中，对这一子集就不用再进行分支；2）如果这个线性规划解满足整数要求，是所得到的最好的整数规划解，这个解的目标函数值就成为整数规划问题的上界，即原问题的最优目标函数值一定小于或等于这个值≤。这称为定界。 我们通过下面的例子来说明上述解题思想。 【例3-3】 min s.t．≤18； ≥20 x1，x2≥0； x1，x2为整数 求解过程如图3-1所示。 图3-1 分支定界的解题步骤 （1）定界 首先，不考虑整数约束，这时伴随线性规划的可行域为，如图3-2a所示，其最优解