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所示，其最优解