排序问题的数学规划松弛方法最新章节_张峰著

2.1　问题1｜ prec｜∑w _j C _j

设有 n 个工件 J ＝｛1，2，…， n ｝，工件 j （ j ＝1，2，…， n ）的加工时间为 p _j ，权为 w _j ，工件具有前后约束关系，工件之间的前后约束关系用表示，即 i j 表示工件 j 必须在工件 i 加工结束之后才能开始加工，这一节我们讨论工件具有前后约束关系的排序问题1｜prec｜ ∑w _j C _j 。

应用线性规划松弛方法设计排序问题的近似算法最为关键的是引入合适的决策变量，对于目标函数是带权总完工时间 ∑w _j C _j 的排序问题，其决策变量的定义有多种方式，包括工件完工时间变量、工件加工次序变量、时间指标变量等。

首先讨论决策变量是工件完工时间变量的线性规划松弛方法（Hall et al.，1997）。为了得到排序问题 1｜prec｜∑w _j C _j 的线性规划松弛，先给出下列引理。

引理2.1 设有 n 个工件 J ＝｛1，2，…， n ｝，工件 j （ j ＝1，2，…， n ）的完工时间为 C _j ，设 S ＝｛ i ₁ ，i ₂ ，…，i _s ｝ J 是任意工件集合，则对于排序问题1｜prec｜ ∑w _j C _j 的任何可行排序成立

其中，。

证明不失一般性，不妨假设 S 中工件加工次序为 i ₁ ，i ₂ ，…，i _s ，则，所以

根据引理2.1，引入表示工件完工时间的决策变量｛ C _j ｜ j ＝1，2，…， n ｝，得到下列工件具有前后约束关系的排序问题1｜prec｜ ∑w _j C _j 的线性规划松弛：

显然排序问题1｜prec｜ ∑w _j C _j 的任意可行解，其工件的完工时间｛ C _j ｜ j ＝1，2，…， n ｝是线性规划（LP 2.1）的可行解，因此，线性规划（LP 2.1）的最优值是排序问题1｜prec｜ ∑w _j C _j 的一个下界。由数学规划的一个最优解，反过来如何得到排序问题的一个可行排序是数学规划松弛方法的另一个关键内容，下面给出相应求解排序问题1｜prec｜ ∑w _j C _j 的近似算法。

算法2.1（Schedule-by- 算法）

步骤1：求解线性规划（LP 2.1）得到其最优解｛｜ j ＝1，2，…， n ｝。

步骤2：按｛｜ j ＝1，2，…， n ｝的非降次序确定工件的加工次序。

若工件 j 与 k 之间具有前后约束关系 j k ，即工件 k 必须在工件 j 完工之后才能开始加工，线性规划（LP 2.1）中的约束条件 C _k ≥C _j ＋p _k （若 j k ）则保证了，这样由算法2.1的步骤2所得到的工件加工次序满足工件前后约束关系，即算法2.1得到的排序是排序问题 1｜prec｜∑w _j C _j 的可行解。下面证明算法2.1是求解排序问题 1｜prec｜∑w _j C _j 的2-近似算法。

定理2.1 设是线性规划（LP 2.1）的最优解，不妨假设是由算法2.1所得到排序问题1｜ prec｜∑w _j C _j 可行排序的工件完工时间，则

成立，即算法2.1是求解排序问题 1｜prec｜∑w _j C _j 的2-近似算法。

证明显然根据假设，可得到由算法2.1所得到的工件加工次序为（1，2，…， n ），工件 j 的完工时间

设 S ＝｛1，2，…， j ｝，根据线性规划（LP 2.1）的约束得到

因为，所以

即，所以，因为 w _j ≥0（j＝1，2，…，n），得

线性规划（LP 2.1）中的约束条件

的个数是原排序问题规模的指数级大小，可以证明这一约束定义了超模多面体（Queyranne，1993），应用椭球算法可以在多项式时间求解线性规划（LP 2.1）。本章下面若干线性规划松弛中也有约束定义了超模多面体，我们不再说明。

Potts（1980）最早应用线性规划松弛方法讨论排序问题1｜prec｜ ∑w _j C _j ，其引入的决策变量是刻画工件加工次序的变量｛ δ _{i j} ｜ i，j ＝1，2，…， n；i≠j ｝。对于排序问题1｜prec｜ ∑w _j C _j 的一个可行排序，如果工件 i 在工件 j 之前加工，则定义 δ _{i j} ＝1，否则定义 δ _{i j} ＝0，同时为了使表达式简练，引入记号 δ _{j j} （j＝1，2，…，n） ，并且规定 δ _{j j} ＝0。这样由排序问题1｜prec｜ ∑w _j C _j 的一个可行排序而得到的｛ δ _{i j} ｜ i，j ＝1，2，…， n；i≠j ｝的取值是下列整数线性规划的可行解：

上述整数线性规划（ILP 2.2）中的约束条件

是为了限制当工件 k 在工件 i 之前加工且工件 j 在工件 k 之前加工时，又出现工件 i 在工件 j 之前加工的情况，将整数线性规划（ILP 2.2）的整数性约束 δ _{i j} ∈｛0，1｝（i，j＝1，2，…，n；i≠j） 松弛为 δ _{i j} ≥0 得到下列排序问题 1｜prec｜∑w _j C _j 的线性规划松弛：

下面的定理证明线性规划（LP 2.3）的可行解也一定是线性规划（LP 2.1）的可行解（Hall et al.，1997），所以线性规划（LP 2.3）的最优值一定不会小于线性规划（LP 2.1）的最优值，这样算法2.1的步骤1中所求解线性规划（LP 2.1）的最优解可改为求解线性规划（LP 2.3）得到其最优解｛｜ i ， j ＝1，2，…， n ； i≠j ｝，也是求解排序问题1｜prec｜∑ w _j C _j 的2-近似算法，同时，线性规划（LP 2.3）规模是原排序问题的多项式级大小。