第四讲 非线性规划和多目标规划模型

数学建模 讲义 NUDT 2023SP

---

---

4.1 非线性规划

目标函数或约束条件中至少有一个是决策变量的非线性函数的规划问题，称为非线性规划 (Nonlinear Programming，缩写 NLP).

非线性规划问题的一般形式：

$$\boxed{\begin{array}{rl} \min & f(\boldsymbol{x}) \\ \mbox{s.t.} & h_i(\boldsymbol{x})=0,\ i=1,\ldots,m \\ & g_j(\boldsymbol{x})\leqslant 0,\ j=1,\ldots,n \\ & \boldsymbol{x}\in D \subset \mathbb{R}^n \\ \end{array}}$$

---

例： 非线性规划

$$\begin{array}{rl} \min & f(\boldsymbol{x})=x_1+x_2\\ \mbox{s.t.} & 1\leq x_1^2+x_2^2\leq 2\\ & \boldsymbol{x}\geq\boldsymbol{0} \end{array}$$

---

例： 非线性规划

$$\begin{array}{rl} \min & f(\boldsymbol{x})=x_1x_2+x_2x_3 \\ \mbox{s.t.} & x_1^2-x_2^2+x_3^2\leq 2 \\ & x_1^2+x_2^2+x_3^2\leq 10 \end{array}$$

---

非线性规划问题的求解

• 迭代法是 NLP 的主要求解方法：从一个初始解出发，在可行域中沿着使得目标函数降低的方向前进到下一个解，不断迭代，优化最优函数的值.
  
  • 很多时候只能求得局部最优解（极值），而非全局最优解（最值）.
• 常见求解方法：Lagrange 乘子法、罚函数法、近似规划法 等.
• 尽可能建立线性模型，避免使用非线性模型.

---

非线性规划转化为线性规划

• 很多看起来不是线性规划的问题可以转化为线性规划问题来解决.

• 例： 考虑如下的优化问题

  • $\min |x_1|+|x_2|+...+|x_n|$
  • $\mbox{s.t.}\; \boldsymbol{A}\boldsymbol{x}\leqslant \boldsymbol{b}$
• 其中 $\boldsymbol{x}={[x_1\ \cdots \ x_n ]}^\mathrm{T}$，$\boldsymbol{A}$ 和 $\boldsymbol{b}$ 为相应维数的矩阵和向量.

---

分析：

• 对于任意 $x_i$，令：$u_i =\dfrac{x_i +\vert x_i \vert }{2},\quad v_i =\dfrac{\vert x_i \vert -x_i }{2}$.
• 则 $x_i =u_i -v_i$，$\vert x_i \vert =u_i +v_i$ 且 $u_i,v_i \geqslant 0$.
• 记 $\boldsymbol{u}={[u_1\ \cdots \ u_n ]}^{\mathrm{T}}$，$\boldsymbol{v}={[v_1\ \cdots \ v_n ]}^{\mathrm{T}}$，于是上述问题可改写为
  
  • $\min \;\bbox[lightgreen]{\sum\limits_{i=1}^n {(u_i +v_i )}}$
  • $\mbox{s.t.} \left\{ {\begin{array}{l} \boldsymbol{A}\bbox[lightgreen]{(\boldsymbol{u}-\boldsymbol{v})}\leqslant \boldsymbol{b} \\ \boldsymbol{u},\boldsymbol{v}\geqslant \boldsymbol{0} \\ \end{array}} \right.$

---

例： 最小最大问题

$$\begin{array}{rl} \min & \max\{x_1-x_2+x_3, x_1+x_2, x_1-x_3\}\\ \mathrm{s.t.} & \left\{ \begin{array}{l} x_1+x_2-x_3=1\\ 2x_1-x_2=2\\ x_1-2x_2+x_3\leqslant 1\\ x_1,x_2,x_3\geqslant 0 \end{array} \right. \end{array}$$

---

分析：

• 令 $\bbox[lightgreen]{x_0=\max\{x_1-x_2+x_3, x_1+x_2, x_1-x_3\}}$，
• 则有 $x_0\geqslant x_1-x_2+x_3$, $x_0\geqslant x_1+x_2$,$x_0\geqslant x_1-x_3$.
• 上述模型可转化为：$\min\;\; x_0, \quad \begin{equation*} \mathrm{s.t.}\left\{ \begin{array}{l} x_1+x_2-x_3=1\\ 2x_1-x_2=2\\ x_1-2x_2+x_3\leqslant 1\\ \bbox[lightgreen]{-x_0+x_1-x_2+x_3\leqslant 0}\\ \bbox[lightgreen]{-x_0+x_1+x_2\leqslant 0}\\ \bbox[lightgreen]{-x_0+x_1-x_3\leqslant 0}\\ x_1,x_2,x_3\geqslant 0 \end{array} \right. \end{equation*}$

---

例：飞行管理问题（CUMCM 1995A）

• 在高空中一个边长为 160 公里的正方形区域内，经常有若干架飞机作水平飞行.
• 区域内每架飞机的位置和速度均由计算机记录其数据.
• 当一架欲进入该区域的飞机到达区域边缘时，要立即计算并判断其是否会与区域内的飞机碰撞.
• 如果会碰撞，则要计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞.

---

现假定条件如下：

1. 不碰撞的标准为任意两架飞机的距离大于 8 公里；
2. 每架飞机飞行方向角调整的幅度不应超过 30 度；
3. 所有飞机飞行速度均为 800 公里/小时；
4. 欲进入飞机在到达区域边缘时，与区域内飞机的距离应在 60 公里以上；
5. 最多需考虑 6 架飞机；
6. 不必考虑飞机离开此区域后的状况.

---

请你建立数学模型，基于给定的数据进行计算（方向角误差不超过 0.01 度），要求飞机飞行方向角调整的幅度尽量小.

---

假设：

1. 飞机的方向角调整，只在新到的飞机刚进入时，所有飞机（包括正进入的飞机）调整一次后，就不再调整，飞机在该区域内沿固定方向匀速飞行；
2. 两架飞机之间的距离采用欧式距离，即
   
   • $d_{ij}=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2}$.

---

模型一

• 设第 $i$ 架飞机在调整时的方向角为 $\theta_i$，调整角度为$\Delta \theta_i\ (i=1,2,\ldots,6)$.

• 设任意两架飞机在区域内 $t$ 时刻最短距离为 $d_{ij}(\theta_i,\theta_j)$, 规划模型为

  • $\boxed{\begin{array}{rl} \min & \sum_{i=1}^6 |\Delta \theta_i|\\ \mathrm{s.t.} & d_{ij}(\theta_i+\Delta\theta_i, \theta_j+\Delta\theta_j, t)>8,\; i,j = 1,\ldots,6,\ i\neq j\\ & |\Delta\theta_i|\leqslant \frac{\pi}{6},\quad i,j=1,2,\ldots,6 \end{array}}$

• 目标函数也可以定义为 $\min z = \min \max\limits_{1\leqslant i \leqslant 6}|\Delta\theta_i|$.

---

飞机在区域内的飞行时间

• 对第 $i$ 架飞机，记
  
  • 初始位置：$(x_i^0,y_i^0)$
  • 飞行方向：$\theta_i' = \theta_i + \Delta\theta_i$
  • 飞行速度：$v$
  • 在指定区域内飞行的总时间：$T_i$
• 设区域的边长为 $D$.

$$T_i = \left\{ \begin{array}{ll} \frac{D-x_i^0}{v\cos \theta_i'}, & 0\leqslant \theta_i' < \frac{\pi}{2}, \tan \theta_i'\leqslant \frac{D-y_i^0}{D-x_i^0}, \\ & \mbox{or}\ \frac{3\pi}{2}< \theta_i' < 2\pi, -\tan \theta_i'\leqslant \frac{y_i^0}{D-x_i^0} \\ \frac{D-y_i^0}{v\sin \theta_i'}, & 0< \theta_i' \leqslant \frac{\pi}{2}, \tan \theta_i'\geqslant \frac{D-y_i^0}{D-x_i^0}, \\ & \mbox{or}\ \frac{\pi}{2}\leqslant \theta_i' < \pi, -\tan \theta_i'\geqslant \frac{D-y_i^0}{x_i^0} \\ \frac{-x_i^0}{v\cos \theta_i'}, & \frac{\pi}{2}< \theta_i' \leqslant \pi, -\tan \theta_i'\leqslant \frac{D-y_i^0}{x_i^0}, \\ & \mbox{or}\ \pi\leqslant \theta_i' < \frac{3\pi}{2}, \tan \theta_i'\leqslant \frac{y_i^0}{x_i^0} \\ \frac{-y_i^0}{v\sin \theta_i'}, & \pi < \theta_i' \leqslant \frac{3\pi}{2}, \tan \theta_i'\geqslant \frac{y_i^0}{x_i^0}, \\ & \mbox{or}\ \frac{3\pi}{2}\leqslant \theta_i' < 2\pi, -\tan \theta_i'\geqslant \frac{y_i^0}{D-x_i^0} \\ \end{array} \right.$$

---

任意两架飞机间的距离

在 $t$ 时刻，

$$\begin{array}{rl} &d_{ij}^2(\theta_i+\Delta\theta_i,\theta_j+\Delta\theta_j, t) \\ & \quad= {(x_i^0+vt\cos(\theta_i+\Delta\theta_i)-x_j^0-vt\cos(\theta_j+\Delta\theta_j))}^2 \\ & \quad\;\;+{(y_i^0+vt\sin(\theta_i+\Delta\theta_i)-y_j^0-vt\sin(\theta_j+\Delta\theta_j))}^2 \\ \end{array}$$

---

不碰撞约束

• 令 $f_{ij}(t) = d_{ij}^2(t)-64 = u_{ij}^2+b_{ij}u_{ij}+c_{ij}$，其中
  
  • $u_{ij} = 2vt\sin\frac{\theta_i+\Delta\theta_i-\theta_j-\Delta\theta_j}{2}$,
  • $b_{ij} = 2\left[(x_j^0-x_i^0)\sin\frac{\theta_i+\Delta\theta_i+\theta_j+\Delta\theta_j}{2}+(y_i^0-y_j^0)\cos\frac{\theta_i+\Delta\theta_i+\theta_j+\Delta\theta_j}{2}\right]$,
  • $c_{ij} = {(x_i^0-x_j^0)}^2+{(y_i^0-y_j^0)}^2-64$.
• 不碰撞约束可表达为 $f_{ij}(t) \geqslant 0,\ t<\min(T_i,T_j);\ i,j=1,2,\ldots,6;\ i\neq j$.

---

模型二

• 两飞机不相撞的条件为，两架飞机的飞行方向相对角大于其内公切线与圆心连线的夹角，即：$|\beta_{ij}| \geqslant \alpha_{ij}$
• 内公切线与圆心连线的夹角$\alpha_{ij}$ 满足 $\sin \alpha_{ij} = \frac{8}{\sqrt{{(x_i^0-x_j^0)}^2+{(y_i^0-y_j^0)}^2}}$

---

新的非线性规划模型

$$\begin{array}{rl} \min & z = \sum\limits_{i=1}^6 |\Delta\theta_i|\\ \mbox{s.t.} & \left\{ \begin{aligned} & |\beta_{ij}+\Delta \beta_{ij}| \geqslant \alpha_{ij}, & i,j=1,2,\dots,6,i\neq j \\ & \Delta \beta_{ij} = \frac{\Delta \theta_i + \Delta \theta_j}{2}, & i,j=1,2,\dots,6,i\neq j \\ & |\Delta \theta_i| \leqslant \frac{\pi}{6}, & i=1,2,\dots,6 \\ \end{aligned} \right. \end{array}$$

---

相对速度的角度调整量

相对速度

$$\begin{align*} \boldsymbol{v} & = (v\cos\theta_j-v\cos\theta_i, v\sin\theta_j-v\sin\theta_i)\\ & =2v\sin\frac{\theta_i-\theta_j}{2}\left(\cos\left(\frac{\pi}{2}+\frac{\theta_i+\theta_j}{2}\right),\sin\left(\frac{\pi}{2}+\frac{\theta_i+\theta_j}{2}\right)\right) \end{align*}$$

• 两架飞行方向分别为 $\theta_i$ 和 $\theta_j$ 的飞机的相对速度方向角为$\frac{\pi}{2}+\frac{\theta_i+\theta_j}{2}$，
• 当这两架飞机的各自调整角度 $\Delta \theta_i$ 和 $\Delta \theta_j$ 时，其相对速度方向角调整量为 $\frac{\Delta \theta_i + \Delta \theta_j}{2}$.

---

两架飞机飞行方向的夹角

$$\beta_{ij} = \arctan \frac{\sin \theta_i-\sin \theta_j}{\cos \theta_i - \cos \theta_j} - \arctan \frac{y_i-y_j}{x_i-x_j}$$

• 可以通过初始时刻的位置和飞行方向直接计算得到 $\beta_{ij}$.
• 但上式中计算得到的 $\beta_{ij}$ 一般属于 $[-\pi,\pi]$，可将其变换到 $[0,2\pi]$ 内，即 $\beta_{ij}' = (\beta_{ij}+2\pi)\pmod{2\pi}$

---

模型的比较

• 进一步考虑到角度的周期性，不碰撞的约束条件可写成：$\alpha_{ij} \leqslant \beta_{ij}' + \Delta \beta_{ij} \leqslant 2\pi - \alpha_{ij}$，
• 进而模型可转化为
  
  • $\min z = \sum\limits_{i=1}^6 |\Delta\theta_i|$
  • $\mbox{s.t.}\ \left\{ \begin{aligned} & \alpha_{ij} \leqslant \beta_{ij}' + \frac{1}{2}(\Delta \theta_i + \Delta \theta_j) \leqslant 2\pi - \alpha_{ij}, & i,j=1,\dots,6,i\neq j \\ & \beta_{ij}' = (\beta_{ij}+2\pi) \pmod{2\pi}, & i,j=1,\dots,6,i\neq j \\ & |\Delta \theta_i| \leqslant \frac{\pi}{6}, & i=1,\dots,6 \\ \end{aligned} \right.$

---

转变为线性规划完成求解

令

$$u_i = \frac{\Delta\theta_i+|\Delta\theta_i|}{2},\quad v_i = \frac{\Delta\theta_i-|\Delta\theta_i|}{2}$$

即

$$\Delta\theta_i = u_i-v_i,\quad |\Delta\theta_i| = u_i+v_i$$

带入上述模型可以转化为线性规划模型求解.

• 解得 $\Delta \theta_3=2.839^\circ$，$\Delta \theta_6=0.791^\circ$.

---

小结

• 非线性规划中非线性部分的处理是问题求解最关键的部分也体现创新的源头；
• 巧妙地设计决策变量或充分挖掘问题中隐藏的约束条件往往会有效果；
• 充分利用模型特点，制定有针对性的求解方法能有效缓解非线性所带来的困难.

---

求解工具：Lingo

• a comprehensive tool designed to make building and solving Linear, Nonlinear (convex & nonconvex/Global), Quadratic, Quadratically Constrained, Second Order Cone, Semi-Definite, Stochastic, and Integer optimization models faster, easier and more efficient.
• 语法简单，程序语言与模型贴近，编程效率高
• 费用高

---

求解工具：Gurobi

• 主要支持整数规划和平方规划
• 性能优异，价格高昂（高校免费）
• 提供各种语言的接口，包括：C/C++、Java、R、Python、Matlab 等

---

求解工具：杉树求解器 COPT

• 国内自主研发的针对大规模优化问题的数学规划求解器套件
• 适用于大规模混合整数规划、线性规划（单纯形法和内点法）、半定规划、（混合整数）二阶锥规划、（混合整数）凸二次规划、（混合整数）凸二次约束规划问题
• 支持各种主流编程接口：C++、C#、Python、Julia、Java、AMPL、GAMS、Pyomo、PuLP、CVXPY
• 学术用户 1 年试用

---

优化求解器

• 商用工具
  
  • IBM ILOG CPLEX
  • FICO Xpress
  • MINOS
  • CONOPT
  • SNOPT
  • KNITRO
  • MOSEK
  • BARON
  • 阿里MindOPT
  • 华为天筹AI求解器OPTV
• 开源工具
  
  • SCIP (Solving Constraint Integer Programs)
  • Coin-OR 开源项目套件 CLP/CBC/CGL/SYMPHONY
  • lpsolve
  • glpk (GNU Linear Programming Kit)
  • CMIP (中国科学院)
  • LEAVES (上海财经大学)
  • OR-Tools (Google)
• 集成工具
  
  • MATLAB Optimization Toolbox
  • Python Scipy
  • SAS
  • Excel

---

4.2 多目标规划问题

多目标规划问题 （Multi-Objective Programming，缩写：MOP）的一般形式：

$$\boxed{\begin{array}{rl} \min & F(\boldsymbol{x}) =\min\{f_1(\boldsymbol{x}),\ldots,f_p(\boldsymbol{x})\}, \quad p \geqslant 2\\ \mbox{s.t.} & \left\{ \begin{aligned} & g_i(\boldsymbol{x})\geqslant 0, & i=1,2,\ldots,m \\ & h_j(\boldsymbol{x})=0, & j=1,2,\ldots,l \\ & \boldsymbol{x}\in \mathbb{R}^n \end{aligned} \right. \end{array}}$$

---

多目标规划的应用

• 经济学
  
  • 消费行为的研究：受收入能力的限制，消费者购买更多的某一种商品，可能要以牺牲其他商品的消费为代价.
  • 产能边界的研究：受生产资料的限制，更多地生产一种商品，只能以减少其他商品的生产为代价.
  • 宏观经济政策制定：货币政策需要平衡一些相互竞争的目标，例如：低通货膨胀、低失业率、低贸易逆差，等等.
• 金融学
  
  • 投资组合问题：一方面投资组合收益的预期越高越好，另一方面希望风险越低越好.

---

• 设计制造
  
  • 能源系统规划：总是需要在性能和成本之间进行权衡.
  • 产品和工艺设计：好的设计通常涉及多个标准（目标），如投资、运营成本、利润、产品质量、生产效率、工艺安全、操作时间等.
  • 飞机设计：综合考虑成本、飞行性能、可靠性、燃油经济性、乘坐舒适性等.
  • 太阳能灌溉系统设计：综合考虑建造成本、灌溉效率、环境污染、生态效益等.

---

例：设计一个造纸厂

• 目标：
  
  • 产能开发
  • 纸张的质量
    
    • 质量参数与标称值的偏差最小化
    • 预期断纸时间最小化
  • 环境友好
  • 减少对周边环境的持续影响
• 约束：资金投入、人力资源、建造时间

---

多目标规划问题的求解

• 处理多目标规划问题的关键在于对多个目标进行权衡处理，求解的主要思路是转化为单目标规划问题.
• 为此，需要综合考虑多个目标的以下特点或关系：
  
  1. 优先级/重要性的高低先后
  2. 是否存在冲突或矛盾
  3. 量纲是否相同
  4. 数量级是否一致

---

多目标规划转为单目标规划的方法

1. 评价函数法
2. 功效系数法
3. 约束法
4. 分层序列法
   
   • ...

---

1. 评价函数法

• 构造一个评价函数来集中反映不同目标的重要性等因素，并极小化此评价函数.
• 构造评价函数的常见方法：
  
  • 线性加权法
  • 理想点法
  • 平方和加权法
  • min-max 法（极小极大法）
  • 乘除法

---

评价函数法——线性加权法

• 按目标函数 $f_j(\boldsymbol{x})$ 的重要程度给出一组权重 $\lambda_j$，满足：
  
  • $\sum\limits_{j=1}^p\lambda_j=1$ 且 $\lambda_j\geqslant 0,\ j=1,2,\ldots,p$.
• 评价函数：$\bbox[yellow]{h(F(\boldsymbol{x}))=\sum\limits_{j=1}^p\lambda_j f_j(\boldsymbol{x})}$
• 求解单目标规划问题：$\min\limits_{\boldsymbol{x}\in D} h(F(\boldsymbol{x}))$

---

权重的计算：层次分析法

• 层次分析法（Analytic Hierarchy Process, AHP）对同一层次上的要素，依据其相对重要性，建立比较矩阵，求出该矩阵的最大特征值对应的特征向量，以该特征向量的分量作为每个要素的权重.
• 相对重要性的评估往往依赖于专家的经验或主观判断，总体上是主观判断的体现.

$$\begin{array}{c|cl} \text{评价尺度} & \text{定义} & \text{说明}\\\hline 1 & \text{同等重要} & \text{两要素的贡献程度具同等重要性}\\ 3 & \text{稍微重要} & \text{经验与判断稍微偏好某一要素}\\ 5 & \text{颇为重要} & \text{经验与判断强烈偏好某一要素}\\ 7 & \text{极为重要} & \text{实际显示强烈偏好某一要素}\\ 9 & \text{绝对重要} & \text{有足够证据肯定绝对偏好某一要素}\\ 2,4,6,8 & \text{相邻尺度之中间值} & \text{介于两种判断之间} \end{array}$$

---

权重的计算：熵权法

• 熵是系统无序程度的一个度量.
• 对于某项指标（要素），可以用熵值来判断某个指标的离散程度.
• 信息熵值越小，指标的离散程度越大，该指标对综合评价的影响（即权重）就越大.
  
  • 如果某项指标的值全部相等，则该指标在综合评价中不起作用.
• 具体来说，利用熵权法确定权重的大致过程如下：
  
  • 给定样本 $X_1,X_2,...,X_n$，记 $X_{ij}$ 为 $X_{i}$ 的第 $j\;(j=1,...,m)$ 个指标（要素）的值.
  • 对数据进行标准化 $Y_{ij}=\dfrac{X_{ij}-\min_i X_{ij}}{\max_i X_{ij}-\min_i X_{ij}}$
  • 经验分布 $p_{ij}=\dfrac{Y_{ij}}{\sum_iY_{ij}}\;\left(\begin{array}{c}i=1,...,n\\ j=1,...,m\end{array}\right)$
  • 每个指标的信息熵 $\bbox[yellow]{E_j=-\dfrac{1}{\ln n}\sum_ip_{ij}\ln p_{ij}}$
  • 各个指标的权重 $w_j=\dfrac{1-E_j}{\sum_j(1-E_j)}$

---

评价函数法——理想点法

• 令 $f_j^*=\min\limits_{\boldsymbol{x}\in D}f_j(\boldsymbol{x}),\quad j=1,2,\ldots,p$.
• 评价函数：$\bbox[yellow]{h(F(\boldsymbol{x}))=\sqrt{\sum\limits_{j=1}^p{(f_j(\boldsymbol{x})-f_j^*)}^2}}$
• 求解单目标规划问题：$\min\limits_{\boldsymbol{x}\in D}h(F(\boldsymbol{x}))$
• 原理：距理想点最近的点作为最优解！

---

评价函数法——平方和加权法

• 设定单目标规划的下界（想象中的最好值）：$f_j^0\leqslant\min\limits_{\boldsymbol{x}\in D}f_j(\boldsymbol{x}), \; j=1,2,\dots,p$
• 定义评价函数：$\bbox[yellow]{h(F(\boldsymbol{x}))=\sum\limits_{j=1}^p\lambda_j{(f_j(\boldsymbol{x})-f_j^0)}^2}$
• 其中 $\lambda_j$ 为事先给定的一组权系数，满足：$\lambda_j>0,\ j=1,2,\ldots,p;\ \sum\limits_{j=1}^p\lambda_j=1$
• 求解单目标规划问题：$\min\limits_{\boldsymbol{x}\in D} h(F(\boldsymbol{x}))$

---

评价函数法——min-max 法（极小极大法）

• 悲观主义决策： 在最不利的情况下找出一个最有利的策略！
• 评价函数：$\bbox[yellow]{h(F(\boldsymbol{x}))=\max\limits_{\boldsymbol{x}\in D}\{f_j(\boldsymbol{x})\}}$
• 非线性规划问题：$\min\limits_{\boldsymbol{x}\in D}h(F(\boldsymbol{x})) =\min\limits_{\boldsymbol{x}\in D}\left\{\max\limits_{1\leqslant j \leqslant p}f_j(\boldsymbol{x})\right\}$
• 该问题可以转化为线性规划问题来求解.

---

评价函数法——乘除法

• 目标的规划问题：$f_1(\boldsymbol{x})\rightarrow\min$ 且 $f_2(\boldsymbol{x})\rightarrow\max$
  
  • 其中 $f_1(\boldsymbol{x})>0,\ f_2(\boldsymbol{x})>0,\ \boldsymbol{x}\in\ D$.
• 评价函数：$\bbox[yellow]{h(F(\boldsymbol{x}))=f_2(\boldsymbol{x})/f_1(\boldsymbol{x})}$
• 非线性规划问题：$\max\limits_{\boldsymbol{x}\in D}h(F(\boldsymbol{x}))=\max\limits_{\boldsymbol{x}\in D}f_2(\boldsymbol{x})/f_1(\boldsymbol{x})$
• 如 $f_1(\boldsymbol{x})$ 为投资金额，而 $f_2(\boldsymbol{x})$ 为投资后的总收益，则最优结果应是单位投资的总收入最大！（性价比最高）

---

2. 功效系数法

• 对不同类型的目标函数统一量纲，分别得到一个功效函数，然后求所有功效系数乘积或和的最优解.
• 例如，线性型功效系数法：
  
  • 令 $f_{j\min}=\min\limits_{\boldsymbol{x}\in D}f_j(\boldsymbol{x}),\;f_{j\max}=\max\limits_{\boldsymbol{x}\in D}f_j(\boldsymbol{x}),\; j=1,2,\dots,p.$
  • 定义功效 $d_j(\boldsymbol{x})=\frac{f_{j\max}-f_j(\boldsymbol{x})}{f_{j\max}-f_{j\min}}\in [0,1],\; j=1,2,\dots,p$
  • 求解规划问题 $\max\limits_{\boldsymbol{x}\in D}\prod\limits_{j=1}^p d_j(\boldsymbol{x})$ 或 $\max\limits_{\boldsymbol{x}\in D}\sum\limits_{j=1}^p d_j(\boldsymbol{x})$
• 还有其他类型的方法，如指数型功效系数法.

---

3. 约束法

• 在多个目标中选定一个主要目标，而对其他目标设定一个期望值，在要求结果不比此期望值坏的条件下（相当于增加了新的约束条件），求主要目标的最优值.
• 例： 对优化问题 $\min\limits_{\boldsymbol{x}\in D}\{f_1(\boldsymbol{x}),f_2(\boldsymbol{x}),\ldots,f_p(\boldsymbol{x})\}$，选定 $f_1$ 为主要目标，则可将其转化为类似如下的形式：
  
  • $\left\{\begin{array}{l} \min\limits_{\boldsymbol{x}\in D} f_1(\boldsymbol{x}) \\ \bbox[yellow]{f_2(\boldsymbol{x})\leqslant f_2^0,\ \ldots,\ f_p(\boldsymbol{x})\leqslant f_p^0} \end{array}\right.$

---

4. 分层序列法

• 将优化问题 $\min_{\boldsymbol{x}\in D}\{f_1(\boldsymbol{x}),f_2(\boldsymbol{x}),\ldots,f_p(\boldsymbol{x})\}$ 转化为如下的序列
  
  • $(1):f_1^*=\min\limits_{\boldsymbol{x}\in D}f_1(\boldsymbol{x})$
  • $(2):f_2^*=\min\limits_{\boldsymbol{x}\in D\cap\{x|f_1(\boldsymbol{x})\leqslant f_1^*\}}f_2(\boldsymbol{x})$，
  • $\quad\quad ...$，
  • $(p):f_p^*=\min\limits_{\boldsymbol{x}\in D\cap\{x|f_{p-1}(\boldsymbol{x})\leqslant f_{p-1}^*\}}f_p(\boldsymbol{x})$.
• 本质上是把多个目标按其重要程序排序，逐个求解.
• 缺点：当前面的问题最优解唯一时，后面的求解将失去意义！
• 改进：宽容分层序列法：给前面的最优值设定一定的宽容值 $\varepsilon>0$，即此目标值再差~$\varepsilon$ 也是可以接受的.

---

MCM2021A：FAST主动反射面的形状调节

$$\begin{array}{rl} \min & \sum\limits_{i=1}^n\left[(x_i'-x_i^p)^2+(y_i'-y_i^p)^2+(z_i'-z_i^p)^2\right]\\ \mathrm{s.t.} & [(x_i'-x_j')^2+(y_i'-y_j')^2+(z_i'-z_j')^2-e_{ij}^2]\leq u^2e_{ij}^2,\\ & \quad i,j=1,...,n, c_{ij}=1.\\ & (x_i'-x_j^d)^2+(y_i'-y_j^d)^2+(z_i'-z_j^d)^2=l_i^2,\\ & \quad i=1,...,n.\\ & -d_i^c\leq \delta_i\leq d_i^c,\;i=1,...,n. \end{array}$$

---

约束规模与求解策略

• 该模型的的等式和不等式约束共有 2661 个
  
  • 反射面板边长应满足变化幅度不超过 0.07%: 共包括 1973 个约束(不等式约束)
  • 下拉索长度保持不变约束: 共有 688 个约束(等式约束)
  • 促动器伸缩量约束: 共有 688 × 2 = 1376 个
• 模型是一个目标函数和约束条件均为二次函数的非线性规划模型，采用序列二次规划算法求解，将该问题转化为多个二次规划问题求解
• 特别的，分析发现，促动器的伸缩量与目标函数无关，当主索节点确定后，实际上促动器的顶端位置也确定了，计算时采取先确定主索节点，在检验促动器是否满足要求方式简化计算.

---

4.3 综合案例：投资的收益与风险-CUMCM 98A

• 市场上有 $n$ 种资产（如股票、债券等）$S_i(i=1,2,\ldots,n)$ 供投资者选择.
• 某公司有数额为 $M$ 的一笔相当大的资金可用作一个时期内的投资.
• 公司财务分析人员对这 $n$ 种资产进行了评估，估算出在这一时期内购买 $S_i$ 的平均收益率为 $r_i$，并预测出购买 $S_i$ 的风险损失率为 $q_i$.
• 考虑到投资越分散，总的风险越小，公司确定：当用这笔资金购买若干种资产时，总体风险可用所投资的 $S_i$ 中最大的风险来度量.

---

• 设购买 $S_i$ 所付交易费费率为 $p_i$，并且当购买额不超过给定值 $u_i$ 时，交易费按购买 $u_i$ 计算.
• 另外假定同期银行存款利率为 $r_0=5\%$，且既无交易费又无风险.
• 请设计一种投资组合方案（用给定的资金购买若干种资产或存银行生息），使得净收益尽可能大，而总体风险尽可能小.

---

当 $n=4$ 时，财务分析人员已经分析得到了一些数据，如下表所示：

$$\begin{array}{c|cccc} \hline S_i & r (\%) & q (\%) & p (\%) & u (\text{RMB}) \\ \hline S_1 & 28 & 2.5 & 1 & 103 \\ S_2 & 21 & 1.5 & 2 & 198 \\ S_3 & 23 & 5.5 & 4.5 & 52 \\ S_4 & 25 & 2.6 & 6.5 & 40 \\ \hline \end{array}$$

---

模型建立与求解

• 设购买 $S_i$ 的投资比例为 $x_i$，所需的交易费为 $c_i(x_i)$，
• 则 $c_i(x_i) = \left\{ \begin{array}{ll} 0, & x_i=0 \\ p_i u_i, & 0<Mx_i<u_i \\ p_i x_i M, & Mx_i \geqslant u_i \\ \end{array} \right.$
• 当然，若存银行的资金比例为 $x_0$，则 $c_0(x_0)=0$，即银行没有手续费.
• 投资净收益目标 可表达为 $R(\boldsymbol{x}) = \sum_{i=0}^n R_i(x_i) = \sum_{i=0}^n\left(r_i Mx_i-c_i(x_i)\right)$.

---

• 由题意可知，投资风险为 $Q(\boldsymbol{x}) = \max_{0\leqslant i\leqslant n}q_i x_i M$
• 相应的约束为投资所用总额不能超过总资金：$F(\boldsymbol{x}) = \sum_{i=0}^n (Mx_i+c_i(x_i)) = M$
• 则该问题对应的优化模型：
  
  • $\max R(\boldsymbol{x}), \min Q(\boldsymbol{x})$
  • $\mbox{s.t.}\ \left\{ \begin{aligned} & F(\boldsymbol{x}) = \sum_{i=0}^n (Mx_i+c_i(x_i)) = M \\ & x_i \geqslant 0,\ i=0, 1,2,\dots,n \\ \end{aligned} \right.$

---

• 由于最低投资额 $u_i,i=1,2,3,4$ 较小，假设投资额度总会大于 $u_i$，
• 则第一个约束条件可变为 $\sum_{i=0}^n x_i(1+p_i) = 1.$
• 相应的目标函数可表达为
  
  • $\begin{align*} & \max\ R(\boldsymbol{x})=M\sum_{i=0}^n x_i(r_i-p_i) \\ & \min\ Q(\boldsymbol{x})=M\max_{0\leqslant i \leqslant n}q_i x_i \\ \end{align*}$

---

1. 线性权和法

新的目标函数为 $\min \lambda (-R(\boldsymbol{x}))+(1-\lambda)Q(\boldsymbol{x})$，结果如下表所示

$$\begin{array}{cccccc} \hline \lambda & S_1 & S_2 & S_3 & S_4 & \text{Bank} \\ \hline 0 & 0 & 0 & 0 & 0 & 1 \\ 0.1 & 0.2376 & 0.3959 & 0.1079 & 0.2284 & 0 \\ 0.2 & 0.3689 & 0.6149 & 0 & 0 & 0 \\ \geqslant 0.3 & 0.99 & 0 & 0 & 0 & 0 \\ \hline \end{array}$$

---

2.约束法

1）固定风险水平，优化收益：$\max R(\boldsymbol{x})$，$\mbox{s.t.}\ \left\{ \begin{aligned} & Q(\boldsymbol{x}) \leqslant k \\ & F(\boldsymbol{x}) = 1 \\ \end{aligned} \right.$，结果如下：

$$\begin{array}{cccccc} \hline k & S_1 & S_2 & S_3 & S_4 & Bank \\ \hline 0.005 & 0.1999 & 0.333 & 0.09 & 0.1923 & 0.1581 \\ 0.01 & 0.4 & 0.584 & 0 & 0 & 0 \\ 0.02 & 0.8 & 0.1882 & 0 & 0 & 0 \\ \geqslant 0.03 & 0.99 & 0 & 0 & 0 & 0 \\ \hline \end{array}$$

---

2）固定收益，最小化风险，即 $\min Q(\boldsymbol{x})$，$\mbox{s.t.}\ \left\{\begin{aligned} & R(\boldsymbol{x}) \geqslant k \\ & F(\boldsymbol{x}) = 1 \\ \end{aligned}\right.$
结果如下：

$$\begin{array}{cccccc} \hline k & S_1 & S_2 & S_3 & S_4 & Bank \\ \hline 0.05 & 0 & 0 & 0 & 0 & 1 \\ 0.1 & 0.0783 & 0.1306 & 0.0356 & 0.0753 & 0.6702 \\ 0.2 & 0.2350 & 0.3917 & 0.1068 & 0.2259 & 0.0107 \\ >0.3 & - & - & - & - & - \\ \hline \end{array}$$

---

3. 分层序列法

根据不同的目标优先原则，可考虑采用四种方案，相应的结果分别为：

$$\begin{array}{cccccc} \hline \text{方案} & S_1 & S_2 & S_3 & S_4 & Bank \\ \hline \text{不考虑利润，最小风险为}0 & 0 & 0 & 0 & 0 & 1 \\ \text{最小风险控制在 0-0.05，最大利润} & 1 & 0 & 0 & 0 & 0 \\ \text{不考虑风险，最大利润 0.2673267} & 1 & 0 & 0 & 0 & 0 \\ \text{最大利润控制在 0.2-0.27，最小风险} & 0.23 & 0.39 & 0.11 & 0.22 & 0.01 \\ \hline \end{array}$$

---

课后思考题

($\star\star\star$) 洗衣机洗衣过程通常由加水、洗涤、脱水等若干个环节构成，试为洗衣机设计一种程序，如，共需多少轮、每轮加多少水等，使得既能保证洗涤效果，又节约用水？