数学优化模型
wangzf / 2023-01-07
最优化算法
最优化算法，即最优计算方法，也是运筹学。最优化同运筹学一样，是利用现代数学、系统科学、计算机科学及其他学科的最新成果， 来研究人类从事的各种活动中处理事务的数量化规律，使有限的人、物、财、时空、信息等资源得到充分和合理的利用， 以期获得尽可能满意的经济和社会效果。
最优化算法的内容包括：
- 规划论
- 线性规划
- 整数规划
- 多目标规划
- 非线性规划
- 动态规划
- 库存论
- 图论
- 排队论
- 可靠性理论
- 对策论
- 决策论
- 搜索论
规划论
规划论（数学规划） 是运筹学的一个重要分支， 早在 1939 年苏联的康托罗维奇和美国的希奇柯克等人就在生产组织管理和编制交通运输方案时研究和应用了线性规划的方法。 1947 年美国的旦茨格等人提出了求解线性规划问题的单纯形法， 为线性规划的理论与计算奠定了基础。 非线性规划的基础性工作是在 1951 年由库恩和塔克等人完成的， 到了 20 世纪 70 年代，数学规划无论是在理论上还是方法上，还是在应用的深度和广度上都得到了进一步的发展。
数学规划的研究对象是计划管理工作中有关安排和估值的问题，即在给定条件下， 按某个衡量指标来寻找安排的最佳方案。它可以表示为求函数在满足约束条件下的极大值或极小值问题。
数学规划中最简单的一类问题就是线性规划。 如果约束条件和目标函数都属于线性关系就叫线性规划。要解决线性规划问题，从理论上讲要解线性方程组。
非线性规划是线性规划的进一步发展和延伸。 非线性规划扩大了数学规划的应用范围，同时也给数学工作者提出了许多基本的理论问题，是数学中的如凸分析、数值分析等也得到了发展。
还有一种规划问题和时间有关，即动态规划， 它已经成为在工程控制、技术物理和通信中最佳控制问题的重要工具。
库存论
库存论（存贮论）是运筹学中发展较早的分支。 早在 1915 年，哈里斯就针对银行货币的储备问题进行了详细的研究，建立了一个确定性的存贮费用模型，并求得了 最佳批量公式。 1934 年，威尔逊重新得出经济订购批量公式（EOQ 公式）。
物资的存贮按其目的的不同可分为以下三种：
- 生产存贮
- 它是企业为了维持正常生产而储备的原材料或半成品
- 产品存贮
- 它是企业为了满足其他部门的需要而存贮的半成品或成品
- 供销存贮
- 它是指存贮在供销部门的各种物资，可直接满足顾客的需要
库存论中研究的主要问题可以概括为何时订货（补充存贮）和每次订多少货（补充多少库存）这两个问题。
图论
图论既是拓扑学的一个分支，也是运筹学的重要分支，它是建立和处理离散数学模型的有用工具。
排队论
排队论（随机服务系统理论）是在 20 世纪由丹麦工程师爱尔朗对电话交换机的效率研究开始的， 在第二次世界大战中为了对飞机跑道的容纳量进行估算，该理论得到了进一步的发展，其相应的学科更新论、可靠性理论等也发展了起来。
排队论主要研究各种系统的排队长度、排队的等待时间及所提供的服务等各种参数，以便求得更好的服务，它是研究系统随机聚散现象的理论。 排队论的研究目的是要回答如何改进服务机构或组织所服务的对象，使某种指标达到最优的问题。
因为排队现象是一个随机现象，因此在研究排队现象时，主要采用将研究随机现象的概率论作为主要工具。此外，还涉及微分和微分方程的相关内容。
可靠性理论
可靠性理论是研究系统故障，以提高系统可靠性问题的理论。可靠性理论研究的系统一般分为以下两类：
- 不可修复系统：这种系统的参数是寿命、可靠度等，如导弹。
- 可修复系统：这种系统的重要参数是有效度，其值为系统的正常工作时间与正常工作时间加上事故修理时间之比，如一般的机电设备等。
对策论
对策论（博弈论）是指研究多个个体或团队之间在特定条件制约下的对局中，利用相关方的策略而实施对应策略的学科， 如田忌赛马、智猪博弈就是经典的博弈论问题。它是应用数学的一个分支，既是现代数学的一个新分支，也是运筹学的一个重要学科。
决策论
决策论是研究决策问题的，所谓决策就是根据客观可能性， 借助一定的理论、方法和工具，科学地选择最优方案的过程。决策问题由 决策者和 决策域构成，而决策域则由决策空间、状态空间和结果函数构成。研究决策理论与方法的科学就是决策科学。
决策所要解决的问题是多种多样的，不同角度有不同的分类方法。按决策者所面临的自然状态的确定与否可分为确定型决策、不确定型决策和风险型决策， 按决策所依据的目标个数可分为 单目标决策与 多目标决策，按决策问题的性质可分为 战略决策与 策略决策，以及按不同准则划分成的种种决策问题类型。 不同类型的决策问题应采用不同的决策方法。
决策的基本步骤如下：
- 确定问题，提出决策的目标；
- 发现、探索和拟定各种可行方案；
- 从多种可行方案中，选出最佳方案；
- 决策的执行与反馈，以寻求决策的动态最优。
如果对方决策者也是人（一个人或一群人），双方都希望取胜，这类具有竞争性的决策称为 对策或博弈型决策。 构成决策问题的三个根本问题是：局中人、策略和 一局对策的得失。对策问题按照局中人数分类可分成两人对策和多人对策， 按局中人赢得函数的代数和是否为零可分成零和对策和非零和对策，按解的表达形式可分成纯策略对策和混合策略对策，按问题是否静态形式可分成动态对策和静态对策。
搜索论
搜索论主要研究在资源和探测手段受到限制的情况下，如何设计寻找某种目标的最优方案，并加以实施的理论和方法。
在第二次世界大战中，同盟国的空军和海军在研究如何针对轴心国的潜艇活动、舰队运输和兵力部署等进行甄别的过程中产生的。 搜索论在实际应用中也取得了不少成效，如 20 世纪 60 年代，美国寻找在大西洋失踪的核潜艇“蝎子号”，以及在地中海寻找丢失的氢弹， 都是依据搜索论获得成功的。
数学模型
数学模型(mathematical model)是一个包含变量及问题相关特征之间关系的集合体。
优化及运筹学方法的步骤
所谓运筹学，就是通过构建及分析数学模型，将问题特征用数学语言合理表示并分析， 用以处理各类决策问题(decision problem)。下图展示了运筹学处理问题的一般步骤。
- 一般步骤开始于建模，即我们首先要定义相关变量，以及量化用于描述问题相关行为的一些关系。
- 之后是分析。我们需要应用数学方法与技术去找到模型建议的结论， 注意这些结论源自于模型而非最初的实际问题。
- 最后我们需要做出推论，以表明这些源自于模型的结论对于解决实际问题的合理性。
- 当然，推论也可能证明这些源自于模型的结论对于解决问题不是充分的或者难以执行的， 这时我们需要修正模型并重新进行上述步骤。
决策-约束-目标
通常在建模前，需要从三个维度：决策、约束与目标去关注问题。
三个建模的基本关注点为：
- 决策者需要做出决策(decision)
- 限制决策选择的约束(constraint)
- 人们偏好的决策所产生的目标(objective)
优化与数学规划
用语言描述的模型虽然可以帮助分析者组织思路，却不便于进行数学分析。 因此这里引入优化模型(也称为数学规划)。
优化模型(也称为数学规划)将问题的决策用决策变量描绘， 其目标为寻求能够最大化或者最小化目标函数的决策变量的取值。 当然，这些决策变量的取值要满足限制问题决策选择的约束。
可行解与最优解
建模的最终目的是帮助决策者做决策。即需要找到决策变量(decision variable)的合适取值， 这样才能帮助做决策。
可行解(feasible solution) 是满足所有约束条件的决策变量的取值。
最优解(optional solution) 是能够使目标函数值优于其他任意可行解的可行解。
系统边界
建模涉及很多“数量”。这些“数量”既有已经给定的，又有等待被确定的。 给定的参数以及等待被确定的变量之间的界限构成了系统边界。
下图展示了如何用参数(parameter, 即给定的“数量”)定义适用于系统内部模型的目标函数以及约束， 然后，通过对决策变量进行分析，进而输出系统结果：输出变量(output variable)。
敏感性分析
敏感性分析用于评价某个参数取值变化对数学模型结果的影响。
任何完整的运筹学研究都包含参数敏感性分析。
解析解
能够基于输入参数用公式表达出来的用于描述决策变量选择的解被称为解析解(closed-form solution)。
解析解代表着数学模型的最终分析，因为解析解不但能提供直接的模型结果， 而且能提供丰富的敏感性分析。
易处理性及有效性
**易处理性(tractability)**是指模型便于分析的程度，即有多少分析是可操作的。
**有效性(validity)**是指由模型推断得到的结果适用于真实系统的程度。
描述性模型与规范性模型
数值搜索、精确解与启发解
确定模型与随机模型
确定性优化模型
搜索算法
运筹学中的确定性优化模型
确定性模型中假设所有关于问题的输入数据都是确定的。这种假设有时并不太符合现实情况， 因为运筹模型中的输入常量通常都是估算出来的，有一些甚至相当粗略。 之所以采用确定模型，一方面因为确定模型通常能够得到足够有效而且有用的结果， 另一方面因为它们相对于随机模型而言更加容易分析。
确定性优化模型通常被称为数学规划(mathematical program)， 这是因为它们决定了如何计划或者“规划”现实生活中的各项活动。
决策变量
阐述任何优化模型的第一步都是要先识别决策变量。
优化模型中描绘决策的变量即为决策变量。建模时需要给出每个变量的含义及单位。
变量类型约束
描述优化模型的下一步是确定约束条件，即明确什么限制了我们的决策。 最基本的约束是明确变量的类型。
变量类型约束详细说明了决策变量的定义域，即在什么样的取值集合中决策变量才有实际意义。
例如，决策变量可以被限制为非负值或非负整数，或者决策变量直接被设定为无约束。 总之，只有当约束条件被明确地在模型中表达出来时，解决该模型的方法才能被有效执行。
主约束
除了变量类型约束外，其他所有决策变量的限制条件构成了主约束。
主约束(main constraint)是优化模型中除变量类型的约束外， 其他所有表明对决策变量的限制以及表示决策变量之间关系的约束条件。
目标函数
目标函数用以衡量我们所做决策的结果。
目标函数是在优化模型中量化决策结果的函数，决策的目的通常是最大化或者最小化目标函数。
标准形式
一旦定义了决策变量，列举出约束条件，并量化了目标函数，就可以得到一个完整的数学优化模型。 通常，将其总结成一个标准模式，即优化模型的标准形式。
优化模型的标准形式如下：
$$\text{min 或 max} \space [\text{目标函数(可以是多个)}]$$$$\text{s.t.}\begin{align} (主约束) \\ (变量类型约束) \end{align}$$其中，“
$\text{s.t.}$” 代表 “使服从(subject to)”。
图解法
图解法是一种非常简单的分析方法。这种方法虽然简单，但足以解决一些简单模型， 同时，图解法能够提供“图形”，这有助于更直观地理解模型的性质及求解方法。
除了图解法的求解技术，图解法也有强大的探索优化问题解（包含唯一最优解、 多个最优解、无可行解、以及无界解）的能力。
图解法介绍
图解法主要用于解决具有两个或三个决策变量的优化模型， 它能够将模型的要素呈现在与决策变量相对应的坐标系中， 以此来探索优化模型的最优解。
可行域
图解法的首要问题是确定可行域（也被称为可行解、可行空间）。
优化模型的可行域(feasible set)是满足所有模型约束条件的决策变量的取值集合。
绘制约束及可行域
图解法首先要在由决策变量定义的坐标系中绘制出满足变量类型约束的区域。
满足等式约束的点集形成一条直线或者曲线。
满足不等式约束的点集包含一条边界线及该边界线某侧区域内的所有点； 其中边界线为直线或者曲线，在该边界线上不等式约束中的等号成立， 而在边界线某侧区域内不等式约束中的不等号成立（我们通常在边界线上增加一个小箭头， 箭头所指的一侧是可行区域的方向）。
优化模型的可行域需要通过逐步引入约束条件进行绘制， 最终满足所有约束条件的区域即为模型的可行域。
绘制目标函数
为了找到最优的可行点，必须将目标函数引入可行域图形中。
优化模型的目标函数通常以等值线（通常用虚线表示）的形式被绘制在可行域所在的坐标中， 等值线是通过选择不同的决策变量使目标函数取值相同的直线或曲线， 它们垂直于目标函数值改进的梯度方向（即目标函数值增长或者下降最快的方向）。
最优解
用图解法分析优化模型的最终目的是找到模型的最优解（注意前提为最优解存在）。
最优解(optimal solution)是可行域内的决策变量某个（些）取值组合， 这个（组）决策变量值能使目标函数值不差于其他可行解所能达到的目标函数值。
最优解位于目标函数最优等值线与可行域相交的部分。
最优值
优化模型的最优值是最优解对应的目标函数取值。
唯一最优解与多个最优解
一个优化模型有最优解，则该模型存在唯一最优解或者多个最优解。
注意：所有的最优解都对应相同的最优值。
不可行解
不可行模型没有最优解。
如果一个优化模型不存在满足所有约束条件的决策变量取值， 则该模型不可行。
无界模型
另外一种没有最优解的优化模型的情形是该模型无界。
如果一个优化模型存在可行域内的点，可以使目标函数值朝改进的方向一致平移， 则该模型无界。
无界模型在图解法中表现为在可行域中总存在能使目标函数更优的点。
优化模型分类
优化模型的使用者在实际生活中面对的是一些有着特定决策变量、约束以及目标函数的实际问题， 这些实例通常有明确的模型参数（常数形式）而非简单的负号。此外，优化问题的类型如线性或者非线性、 连续或者离散、单目标或者多目标，会对解决一个实际问题的难易程度、用何种方法解决产生巨大的影响。 因此，对于模型应用者而言，首要问题便是识别出要解决的实际问题所对应的模型类型。
- LP（线性规划）最易处理，其变量类型为连续变量，只有一个目标函数，且目标函数和约束均为线性形式；
- NLP(非线性规划)的目标函数或约束中存在非线性形式，其余均与 LP 形同；
- 如果模型中存在离散变量，则 LP 就变成了 ILP（整数线性规划），同样，NLP 就变成了 INLP（整数非线性规划）。
决策变量、约束条件、目标函数的情况：
- 决策变量
- 连续
- 离散
- 约束条件
- 有或无
- 线性
- 非线性
- 目标函数
- 单个或多个
- 线性
- 非线性
分类：
- LP: 单目标线性规划
- NLP 单目标非线性规划
- ILP: 单目标整数线性规划
- INLP: 单目标整数非线性规划
- MLP: 多目标线性规划
- MNLP: 多目标非线性规划
- MILP: 多目标整数线性规划
- MINLP: 多目标整数非线性规划
- MILP: 混合整数线性规划
- MINLP: 混合整数非线性规划
- 组合优化
数学规划的一般形式
如何区分数学规划类型？其主要依据为包含决策变量的方程的类型。方便起见，首先， 写出数学规划的一般形式。
数学规划或者（单目标）优化模型的一般形式如下：
$$\text{min 或 max}\space f_{1}(x_{1}, \cdots, x_{n})$$
$$\text{s.t.}\space g_{i}(x_{1}, \cdots, x_{n})\begin{cases}
\leq b_{i} \\
= b_{i} \\
\geq b_{i}, i=1, \cdots, m
\end{cases}$$
其中 $f$，$g_{1}, \cdots, g_{m}$ 是关于决策变量 $x_{1},\cdots, x_{n}$，
以及常数参数 $b_{1}, \cdots, b_{m}$ 的方程，
每一个约束都可以是 $\leq$、$=$ 或者 $\geq$ 的形式。
线性规划与非线性规划
如果上述优化模型形式中的（单一）目标函数方程
$f$以及约束方程$g_{1}, \cdots, g_{m}$均为关于决策变量的线性方程， 则该优化模型为线性规划(linear program, LP)，其中目标函数值可以为满足约束的任意整数或分数。
如果上述优化模型形式中的（单一）目标函数方程
$f$以及约束方程$g_{1}, \cdots, g_{m}$均为关于决策变量的非线性方程， 则该优化模型为非线性规划(nonlinear program, NLP)，其中目标函数值可以为满足约束的任意整数或分数。
离散或整数规划
在数学规划中，变量即意味着决策，现实中充满各种各样的决策，因此对变量类型也存在各种各样的需求。 离散优化模型是一种有着特殊变量类型的优化模型。离散优化模型在变量类型上不同于线性或非线性规划， 其通常也被称为整数（线性或非线性）规划、混合整数（线性或非线性）规划、组合优化问题。
如果一个变量的取值范围为某一区间的一些特定的或者可数的取值的集合， 则该变量为离散变量。0-1 变量（取值为 0 或者 1 的变量）是一种常用的离散变量。
对于一些实际中应该为离散变量的决策变量，当最优决策变量的量级足够大以至于分数对于实际应用没有太大影响时， 我们相对于离散变量更应该采用连续变量，因为连续变量相对于离散变量会大大降低优化问题处理的难度。
一个优化模型，如果它的决策变量中存在离散变量，则该优化模型为整数规划（integer program, IP）。 如果整数规划的所有决策变量均为离散变量，则该整数规划为纯整数规划（pure integer program）； 否则，为混合整数规划(mixed-integer program)。
多目标优化模型
搜索算法
一些优化模型的最优解能够通过显示表达式明确刻画出来， 但绝大多数优化模型却只能通过数值搜索(numerical search)的方法来求解， 即以此尝试不同的决策变量取值，直到得到一个满意的结果。 事实上，大多数的优化过程都可以看作是搜索算法的衍生方法。
搜索算法(improving search)通过检查邻域来寻找比当前更好的解，若有改进，则替换当前解，继续迭代， 直到邻域中没有更好的解为止。搜索算法又称为局部改进(local improvement)、爬山算法(hillclimbing)、 局部搜索(local search)或领域搜索(neighborhood search)。
搜索算法
在搜索算法中，我们系统的尝试不同决策变量的取值，直到找到一个足够好的结果时停止搜索。
解
将搜索中尝试过的一系列点称为“解”。
解是一组决策变量的取值。
局部和全局最优
寻找初始可行解
上面已经讨论了搜索算法是如何从一个可行解转移到另一个更好的可行解的。 那么，第一个初始可行解是怎样产生的？一些复杂的的优化问题有着成千上万的约束和变量， 往往没有明显可行的解决方案。因此，分析的首要任务是确定是否存在可行解。 这里将介绍两种人工变量法来寻找初始解，即两阶段法(two-phase)和大 M 法(big-M)。