KIM算法的最優(yōu)性

研究工件的就緒時間可以不相同、但是與交貨期有"一致性"關(guān)系的誤工問題.1978年Kise,Ibaraki,Mine提出算法(簡稱為KIM算法),證明他們提出的KIM算法可以得到這個誤工問題的最優(yōu)解.最近李杉林、陳志龍、唐國春用反例指出Kise,Ibaraki,Mine 證明最優(yōu)性時提出的引理2是錯誤的,并用新的方法證明KIM算法的最優(yōu)性.越民義則給出一個非常簡潔的證明.本文分析引理2的錯誤所在,給出修改后的引理2',由此似乎應(yīng)該相應(yīng)修改KIM算法,然而我們證明原來的KIM算法仍然可以得到最優(yōu)解.

作 者： 孫葉平 唐國春 Sun Yeping Tang Guochun   作者單位： 孫葉平,Sun Yeping(重慶師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,重慶,400047)

唐國春,Tang Guochun(上海第二工業(yè)大學(xué)管理工程研究所,上海,200041) 

刊 名： 運籌學(xué)學(xué)報  ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS  年，卷(期)： 2007 11(4)  分類號： O22  關(guān)鍵詞： 運籌學(xué)   排序   最優(yōu)性   算法  

【KIM算法的最優(yōu)性】相關(guān)文章：

數(shù)學(xué)算法04-28

(h, φ)多目標(biāo)規(guī)劃的鞍點最優(yōu)性條件04-26

SSDA的改進算法04-26

算法崗位職責(zé)03-15

手指快算法簡介04-28

算理和算法04-28

Fuzzy推理的Mamdani算法04-27

乘法的簡便算法教案04-28

算理與算法的關(guān)系－我對算理與算法統(tǒng)一的感悟04-28

算法工程師的職責(zé)06-09