排序最佳化

排序最佳化（ordinal optimization）也稱為序最佳化，是最优化中的一種，是針對在偏序集（poset）上取值函數的最佳化。排序最佳化可以應用在等候网络的理論中。

數學基礎
偏序是指在集合P內的二元关系 "≤"，是自反关系、反对称关系及传递关系。針對集合P內的所有a, b及c，會有以下的關係：

*a ≤ a（自反關係）;
若 a ≤ b 且 b ≤ a ，則 a = b*（反對稱關係）;
if a ≤ b and b ≤ c，則 a ≤ c*（傳遞關係）.

偏序關係也可以說是预序关系。具有偏序關係的集合稱為偏序集（poset）。

針對偏序集P內的兩個相異元素a, b，若a ≤ b或b ≤ a，則a和b 是可比較的，否則是不可比較的。若偏序集中任兩個元素都是可比較的，此偏序集稱為全序关系或「chain」（也就是依順序排列的自然數）。若任兩個元素都是不可比較的，則稱為反链。

以下是一些數學中偏序集的例子：

計算機科學及統計學中的排序最佳化
在許多領域都有排序最佳化的問題。计算机科学中會研究选择算法，這種算法比排序算法要簡單

决策论會研究选择算法，會要識別出「最佳」的子群體，或是識別出「近乎最佳」的子群體。

應用
自1960年代起，排序最佳化在其理論及應用上都有許多的擴展。其中的及已應用在网络分析及等候理論中，特別是在等候網路中。排序最佳化也應用在离散事件仿真上。

相關條目
*

参考文献
延伸閱讀

Fujishige, Satoru Submodular functions and optimization. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp.
Gondran, Michel; Minoux, Michel Graphs, dioids and semirings. New models and algorithms. Operations Research/Computer Science Interfaces Series, 41. Springer, New York, 2008. xx+383 pp.
Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. IBM J. Res. Dev. 47 (2003), no. 1, 25–30.
Murota, Kazuo Discrete convex analysis. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. xxii+389 pp.
Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp.
Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp.
Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
Zimmermann, U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. 10 (1981), viii+380 pp.
Cuninghame-Green, Raymond Minimax algebra. Lecture Notes in Economics and Mathematical Systems, 166. Springer-Verlag, Berlin-New York, 1979. xi+258 pp.

*
*
*

Ho, Y.C., Sreenivas, R., Vakili, P.,"Ordinal Optimization of Discrete Event Dynamic Systems", J. of DEDS 2(2), 61-88, (1992).
Allen, Eric, and Marija D. Ilic. Price-Based Commitment Decisions in the Electricity Market. Advances in industrial control. London: Springer, 1999.

外部連結