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

申子慧,陳玉松,申培萍

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

1.引言

2.問題的等價轉(zhuǎn)化

3.算法理論基礎(chǔ)

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

5.計算復(fù)雜度

6.數(shù)值算例

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

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