求解一类线性规划问题的原始贪婪算法和对偶贪婪算法-兰州交通大学.pdfVIP

第26 卷　第 1期 兰 州 交 通 大 学 学 报 (自 然 科 学 版 ) Vol.26 No.1 2007 年2 月 Journal of Lanzhou Jiaotong University (Natural Sciences) Feb.2007 　　文章编号:1001 4 7 (2007)01 0149 04 求解一类线性规划问题的 始贪婪算法和 对偶贪婪算法及其相互关系＊ 黄　辉, 　梁国宏, 　张　生, 　何尚录 (兰州交通大学 数理与软件工程学院, 甘肃 兰州　7 0070) 摘　要:给出了求解一类线性规划问题的一种贪婪算法和求解其对偶问题的一种贪婪算法, 并讨论了这两种算法 的若干性质及其相互关系. 关键词:线性规划问题;对偶问题;贪婪算法;下模函数. 中图分类号:O221.1　　　　　文献标识码:A 贪婪算法), 并讨论用这两种贪婪算法求出的解是相 0　引言 应问题的最优解时,f (X )必须满足的条件.另外, I 设I ={1, 2, …, n }, 其中n 为正整数, Ψ=2 = 本文还讨论上述两种贪婪算法之间的相互关系.结 {X |X I }, 即Ψ是由I 的所有子集组成的集合, 论表明, 在一定条件下求解问题(LP)的 始贪婪算 f (X )为定义在 Ψ上的实值函数;对x = (x (1), 法和求解问题(DP)的对偶贪婪算法是等价的. T n x (2), …, x (n )) ∈ R 及 X ∈ Ψ, 记 x (X )= 1　 始贪婪算法和对偶贪婪算法及其性质 ∑x (i ).给定非负向量 w = (w (1), w (2), …, i ∈X 为给出求解问题(LP)的 始贪婪算法和求解 T n w (n )) ∈ R , 考虑如下线性规划问题: 问题(DP)的对偶贪婪算法, 并讨论它们的若干性 max∑w (i)x (i) (LP) i ∈I 质, 首先引入下模函数的概念:设f :Ψ※ R 为定义 s.t.　x (X )≤f (X ), X ∈ Ψ. 在 Ψ上的实值函数, 若对任何X ,Y ∈ Ψ, 都有 此问题的对偶问题是 f (X )+f (Y )≥f (X ∪ Y )+f (X ∩ Y ), 则称f :Ψ※ R 为定义在 Ψ上的下模函数. min f (X )λ(X ) ∑ x ∈Ψ 1.1　 始贪婪算法及其性质 (DP)s.t.　 ∑ λ(X )=w (i), i ∈ I, 对问题(LP), 给出如下的贪婪算法, 称为 始 X :i∈X ∈Ψ 贪婪算法: 　　λ(X )≥0, X ∈ Ψ. (i)置I0 = ,f ( )=0, 令k =1; 近年来, 人们逐渐发现上述线性规划问题及其