排队论也称随机服务系统理论，它研究的内容有三部分：

• 形态问题：各种排队系统的概率规律性，如队长分布、等待时间分布、忙期分布等；
• 最优化问题：分静态最优 (最优设计) 和动态最优 (最优运营)；
• 排队系统的统计推断：判断一个给定的排队系统符合于哪种模型。

排队论的一般模型如图：

graph LR

arrive[顾客随机到达]
subgraph 排队系统
queue[顾客排队]
srv["服务机构(服务时间随机)"]
end
leave[顾客离去]
arrive --> queue
queue --> srv
srv --> leave

• 无向图：一个非空有限集合 和 中的某些元素的无序对集合 ​ 构成的二元组，记 其中 称顶点集或结点集， 称边集，​ 中的每个元素 ​ 为 ​ 中某两个元素 的无序对，记 称从 ​ 到 的边；

  • 有限图：结点集和边集都有限的图；
  • 简单图：没有环也没有两条边连接同一对结点。

动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。

动态规划是求解某类问题的一种方法，而不是一种特殊算法，没有标准的数学表达式和明确定义的一组规则。

动态规划的基本概念有：

• 阶段：对整个过程的自然划分，阶段变量一般用 表示；

• 状态：每个阶段开始时过程所处的自然状况，用 表示第 阶段的状态变量，用 表示第 阶段的允许状态集合；

• 决策：一个阶段的状态确定后，作出各种选择从而演变到下一阶段的某个状态，用 ​ 表示第 ​ 阶段处于状态 ​ 时的决策变量，用 表示 的允许决策集合；

• 策略：决策组成的序列。由第 到第 ​ 阶段的子过程策略记

• 状态转移方程：表示状态和决策确定下一状态的演变规律，记

• 指标函数：衡量过程优劣的数量指标，记

• 最优值函数：使指标函数达到最优，记 其中 可取 或 。

03. 非线性规划

定义

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。

非线性规划目前还没有适于各种问题的一般算法。

非线性规划模型描述如：

其中 ，而 都是实值函数。

一般非线性规划只能得到局部最优解，不能保证是全局最优解。

规划中的变量 (部分或全部) 限制为整数时，称为整数规划。

若在线性规划模型中变量限制为整数，则称为整数线性规划。

分类：

• 变量全限制为整数时，称纯 (完全) 整数规划；
• 变量部分限制为整数时，称混合整数规划。

线性规划，就是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

线性规划由三部分组成：

• 决策变量
• 目标函数
• 约束条件

形式

编程中，线性规划的标准形式为：

其中 为 ​ 维列向量， 为适当维数的矩阵， 为适当维数的列向量。