排序最佳化

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

數學基礎

参见：最优化、偏序关系、格_(数学)、组合优化和对偶_(数学) § 序逆对偶

偏序是指在集合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」（也就是依順序排列的自然數）。若任兩個元素都是不可比較的，則稱為反链。

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

• 实数的偏序關係是標準的小於等於關係 ≤ ，也是全序集。
• 特定集合子集形成的集合（冪集），偏序關係是包含。
• 向量空间子空間的集合，偏序關係也是包含。

計算機科學及統計學中的排序最佳化

参见：选择算法

在許多領域都有排序最佳化的問題。计算机科学中會研究选择算法，這種算法比排序算法要簡單^[5][6]

决策论會研究选择算法，會要識別出「最佳」的子群體，或是識別出「近乎最佳」的子群體^{[7][8][9][10][11]}。

應用

参见：网络流、等候理論和离散事件仿真

自1960年代起，排序最佳化在其理論及應用上都有許多的擴展。其中的antimatroid（英语：antimatroid）及max-plus代數（英语：max-plus algebra）已應用在网络分析及等候理論中，特別是在等候網路中。排序最佳化也應用在离散事件仿真上^[12][13][14]。

相關條目

• 隨機最佳化（英语：Stochastic optimization）
• 計算複雜性理論
• 启发式搜索
• 測量尺度（Ordinal data）