排序最佳化

**排序最佳化**（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 年代起，排序最佳化在其理論及應用上都有許多的擴展。其中的 antimatroid 及 max-plus 代數已應用在網絡分析及等候理論中，特別是在等候網路中。排序最佳化也應用在離散事件仿真上。

## 相關條目

* 隨機最佳化
* 計算複雜性理論
* 啟發式搜索
* 測量尺度（Ordinal data）

## 參考文獻

## 延伸閱讀

* Fujishige, Satoru _Submodular functions and optimization_. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp. ISBN 0-444-52086-4
* 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. ISBN 978-0-387-75449-9
* 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. ISBN 0-89871-540-7
* Topkis, Donald M. _Supermodularity and complementarity_. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
* 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. ISBN 0-471-16015-6
* 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. ISBN 3-540-09113-0
* Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre. Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. 1992: xx+489. ISBN 0-471-93609-X. MR 1204266.
* Glasserman, Paul; Yao, David D. Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. 1994: xiv+297. ISBN 0-471-58041-4. MR 1266839.
* Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob. Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. 2006: xii+213. ISBN 978-0-691-11763-8. MR 2188299.
* 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. ISBN 978-1-85233-069-9

## 外部連結

* Annotated bibliography on ordinal optimization （頁面存檔備份，存於網際網路檔案館） by 何毓琦