·252· 工程科学学报，第37卷，第2期 即为可行的.记厂为该可行概率分布的集合.于是， 集Q二{1,2，…，m}可以分为两个子集Q和Q2,且 问题转为 Q=QUQ2,Q1nQ2=☑，并满足 m'arg maxP(E=mll). (6) j=1,2,…,n, 点1点 ge{-1,0,1. 若E是条件独立的，严给定，则等式(6)的最优 (19) 化问题可表述为 定理1若由0、±1组成的m×n约束矩阵A是 m`=arg maxlogΠf(Ea=d.Ir） (7) 全单模的，则由单纯形法求解线性规划可得原整数规 =ag呼Σloef(E=dI） (8) 划的最优解 证明：将A分成Q,和Q两个行子集，如图2 =agmΣ1-)lef(E.=01）+ 所示 ai logP(E=1r) (9) P(E:=1l) -argo (= (10) 0-···-1···-11···1···1 -i (11) 、 01.1。,·10。。 其中，由式(3)可知a为0或1，故式(9)成立.忽略 -1 一个不依赖于m的项，得式(10).式(11)的目标函数 即为a的线性表述. 2整数规划的线性化 图2约束矩阵的简要示意图 转化上述公式为整数规划： Fig.2 Sketch of the constraint matrix A of the LP Maximize Q,和Q2分别代表流的上限和流的守恒： (a)i (12) Q,{i≤l} (20) Subject to t,ijn9il≥0： (13) V,i,∑.、pi≤l: (14) (21) u ,i,∑pi≤∑p: (15) 是p-AmPi≤0. LEML) LLEV) 定义中为一个包含所有流值的向量，将非平凡约 足AnP≤0 (16) 束(13)~(16)以矩阵形式表示 转换后的公式与原问题表述相同.为了避免在某 电=4以l92p], 个非跟踪位置上的目标突然消失，流守恒需满足式 (16),且不等式不等显著.由式(12)~(16)，整数规 A重≤1，…，1,0，…，0] (22) 划可转换为线性规划求解，设边©吃4的流费用 设A、是由约束矩阵A中任意S行子集构成的子 c(e)为 矩阵，A。的每列最多有三个非零项.将行子集再分成 两个子集：一个满足S=Q,∩S,如非平凡约束(20)所 c(e=-log ( (17) 述；另一子集S2=Q2∩S对应于集合(21).对A,的每 列共有八种不同情况，如表1. 则目标跟踪轨迹（的全费用C,为 所有可能情况中，除1仅在S,且-1仅在S,（如 G=∑c(e). (18) 表1情况7)外，均满足引理的条件.对于这种情况，可 因为是单调递增的，所以当C.:≥C,≤C1时可 将S,包含非零项的行变换到S2,使列与所变换行中的 获得最优解，即此时的目标跟踪轨迹（接近目标的真 非零项相对应，即{入Ii∈S}是{0，…，0}，{入gIi∈S2} 实运动轨迹.用单纯形法迭代求解得到的最优解只有 为{0，…，0,1}或{0，…，0,1，-1}，亦可满足引理.因 在满足引理1时才收敛于原整数规划问题的最优解. 此约束矩阵A满足引理，且是全单模的 本文模型的约束矩阵可满足引理1. 事实上，单纯形法计算最优解是通过线性规划基 引理1令A是由0、±1组成的m×n矩阵， 本可行解的逐步迭代实现的，而约束矩阵A的全单模 那么矩阵A=,]。xn是全单模的，当且仅当A的行子 性则保证了在此过程中的每个基本可行解都是整数工程科学学报，第 37 卷，第 2 期 即为可行的． 记 Γ 为该可行概率分布的集合． 于是， 问题转为 m* = arg max e∈Γ ^ P( E = m| I) ． ( 6) 若 Et，i是条件独立的，I t 给定，则等式( 6) 的最优 化问题可表述为 m* = arg max m∈Γ log ∏t，i ^ P( Et，i = αt lt，i | I t ) ( 7) = arg max m∈Γ∑t，i log ^ P( Et，i = αt lt，i | I t ) ( 8) = arg max m∈Γ∑t，i ( 1 － αt lt，i ) log ^ P( Et，i = 0 | I t ) + αt lt，i log ^ P( Et，i = 1 | I t ) ( 9) = arg max m∈Γ∑t，i αt lt，i log ^ P( Et，i = 1 | I t ) ^ P( Et，i = 0 | I t ) ( 10) = arg max m∈Γ∑t， ( i log ρ t t，i 1 － ρ t t， )i αt lt，i ． ( 11) 其中，由式( 3) 可知 αt lt，i 为 0 或 1，故式( 9) 成立． 忽略 一个不依赖于 m 的项，得式( 10) ． 式( 11) 的目标函数 即为 αt lt，i 的线性表述． 2 整数规划的线性化 转化上述公式为整数规划: Maximize ∑t，i ( log ρ t t，i 1 － ρ t t， )i lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j ． ( 12) Subject to t，i，j，φt lt，i ，lt + 1，j ≥0; ( 13) t，i， lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j ≤1; ( 14) t，i， lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j ≤ lt－1，k: l ∑t，i ∈N( lt－1，k) φt － 1 lt － 1，k，lt，i ; ( 15) j∈ ∑N( vsource) φvsource，j － k: v ∑sink∈N( k) φk，vsink ≤0． ( 16) 转换后的公式与原问题表述相同． 为了避免在某 个非跟踪位置上的目标突然消失，流守恒需满足式 ( 16) ，且不等式不等显著． 由式( 12) ～ ( 16) ，整数规 划可 转 换 为 线 性 规 划 求 解，设 边 e t lt，i ，lt + 1，j 的 流 费 用 c( e t lt，i ，lt + 1，j ) 为 c( e t lt，i ，lt + 1，j ) ( = － log ρ t t，i 1 － ρ t t， )i ， ( 17) 则目标跟踪轨迹 fl 的全费用 Cl 为 Cl = e ∑t lt，i ，lt+1，j ∈fl c( e t lt，i ，lt + 1，j ) ． ( 18) 因为 fl 是单调递增的，所以当 Cl － 1≥Cl≤Cl + 1时可 获得最优解，即此时的目标跟踪轨迹 fl 接近目标的真 实运动轨迹． 用单纯形法迭代求解得到的最优解只有 在满足引理 1 时才收敛于原整数规划问题的最优解． 本文模型的约束矩阵可满足引理 1． 引理 1 ［13］ 令 A 是由 0、± 1 组成的 m × n 矩阵， 那么矩阵 A =［λij］m × n是全单模的，当且仅当 A 的行子 集 Q{ 1，2，…，m} 可以分为两个子集 Q1 和 Q2，且 Q = Q1∪Q2，Q1∩Q2 = ，并满足 j = 1，2，…，n，∑i∈Q1 λij － ∑i∈Q2 λij∈{ － 1，0，1} ． ( 19) 定理 1 若由 0、± 1 组成的 m × n 约束矩阵 A 是 全单模的，则由单纯形法求解线性规划可得原整数规 划的最优解． 证明: 将 A 分 成 Q1 和 Q2 两 个 行 子 集，如 图 2 所示． 图 2 约束矩阵的简要示意图 Fig． 2 Sketch of the constraint matrix A of the LP Q1 和 Q2 分别代表流的上限和流的守恒: Q1 : t，i，{ lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j ≤1 } ， ( 20) Q2 : t，i，{ lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j － lt－1，k: l ∑t，i ∈N( lt－1，k) φt － 1 lt － 1，k，lt，i ≤0 } ， ( 21) j∈ ∑N( vsource) φvsource，j － k: v ∑sink∈N( k) φk，vsink ≤0． 定义 Φ 为一个包含所有流值的向量，将非平凡约 束( 13) ～ ( 16) 以矩阵形式表示 Φ =［φ1 l1，1，l2，1 ，φ2 l2，1，l3，1 ，…，φT － 1 lT － 1，K，lT，K ］T ， A·Φ≤［1，…，1，0，…，0］T ． ( 22) 设 AS 是由约束矩阵 A 中任意 S 行子集构成的子 矩阵，AS 的每列最多有三个非零项． 将行子集再分成 两个子集: 一个满足 S1 = Q1∩S，如非平凡约束( 20) 所 述; 另一子集 S2 = Q2∩S 对应于集合( 21) ． 对 AS 的每 列共有八种不同情况，如表 1． 所有可能情况中，除 1 仅在 S1 且 － 1 仅在 S2 ( 如 表 1 情况 7) 外，均满足引理的条件． 对于这种情况，可 将 S1 包含非零项的行变换到 S2，使列与所变换行中的 非零项相对应，即{ λij | i∈S1 } 是{ 0，…，0} ，{ λij | i∈S2 } 为{ 0，…，0，1} 或{ 0，…，0，1，－ 1} ，亦可满足引理． 因 此约束矩阵 A 满足引理，且是全单模的． 事实上，单纯形法计算最优解是通过线性规划基 本可行解的逐步迭代实现的，而约束矩阵 A 的全单模 性则保证了在此过程中的每个基本可行解都是整数 · 252 ·