線性分式多乘積問題的?-近似算法

申子慧,陳玉松,申培萍

(1.商丘工學院基礎教學部,河南商丘476000;2.華北水利水電大學數學與統計學院,河南鄭州450000)

1.引言

2.問題的等價轉化

3.算法理論基礎

4.(1+?)-近似算法

5.計算復雜度

6.數值算例

給定ε= 0.12,τ= 3,本文計算結果:最優解為(0.0000;1.3866;7.2004;2.8519;4.6240;0.0000;0.0000;5.6716;0.0923;4.2396;4.5181;5.3483),近似最優值0.2687,最優值上界為0.2687,運算時間為7.1930秒.

給定ε=0.12,τ=3,文[6]計算結果:最優解為(0.0052;1.3800;7.1955;2.8451;4.6285;0.0000;0.0000;5.6634;0.0975;4.2355;4.5208;5.3534),近似最優值0.2687,最優值上界為0.2716,運算時間為293.3500秒.