应用数学与计算数学学报
應用數學與計算數學學報
응용수학여계산수학학보
COMMUNICATION ON APPLIED MATHEMATICS AND COMPUTATION
2000年
2期
77-82
,共6页
排序%数学规划%指派问题
排序%數學規劃%指派問題
배서%수학규화%지파문제
本文把单机排序问题1‖∑wjCj表述成一个二次规划,并把不带权的问题1‖∑Cj进一步转化成指派问题,从而用指派问题的匈牙利算法证明SPT序是问题1‖∑Cj的最优解.这个结论似乎很平凡,但对于用数学规划来研究排序问题是一个很有意义的进展.这为我们用二次规划和半定规划来研究NP困难的排序问题的近似算法打下基础.
本文把單機排序問題1‖∑wjCj錶述成一箇二次規劃,併把不帶權的問題1‖∑Cj進一步轉化成指派問題,從而用指派問題的匈牙利算法證明SPT序是問題1‖∑Cj的最優解.這箇結論似乎很平凡,但對于用數學規劃來研究排序問題是一箇很有意義的進展.這為我們用二次規劃和半定規劃來研究NP睏難的排序問題的近似算法打下基礎.
본문파단궤배서문제1‖∑wjCj표술성일개이차규화,병파불대권적문제1‖∑Cj진일보전화성지파문제,종이용지파문제적흉아리산법증명SPT서시문제1‖∑Cj적최우해.저개결론사호흔평범,단대우용수학규화래연구배서문제시일개흔유의의적진전.저위아문용이차규화화반정규화래연구NP곤난적배서문제적근사산법타하기출.
