相关文章推荐
很酷的跑步机  ·  羽球奥运积分赛提前终止 东京奥运赛场谁主沉浮 ...·  4 周前    · 
飞翔的大蒜  ·  [北京新闻]“夏季空调调高一度 ...·  1 年前    · 
刚毅的抽屉  ·  管理 Office 应用中的敏感度标签 | ...·  1 年前    · 
气势凌人的火龙果  ·  梅西将加盟美国职业足球大联盟迈阿密国际队-中新网·  1 年前    · 
成熟的橡皮擦  ·  少林秘谱：三十六抓解脱法释秘_敌人_对方_头发·  1 年前    · 
Code  ›  4. 最优化建模
目标函数 风险模型 建模软件 最优化方法
http://staff.ustc.edu.cn/~rui/ppt/modeling/modeling_4.html
淡定的斑马
2 年前
  • 最优化 是一门应用性很强的学科，它讨论的是为找出实际问题的最优解决策略而采取的模型化及其方法。
  • 其过程是，先把待解决的问题用最优化形式描述为在给定的约束条件下找出使某个目标函数达到最大（小）的解，然后再采用数学上严密的算法来求解。
  • 最优化方法在工业工程、经济管理、交通控制、金融、国防等重要领域中有 广泛的应用 ，并已受到政府部门、科研机构和产业界的高度重视。

    数学模型 ： 设该厂生产 $x_1$ 台甲机床， $x_2$ 台乙机床，利润为 $z$ ，则 $x_1$ 与 $x_2$ 应该满足

    \[\begin{aligned} \max\{ z=4000x_1+3000x_2 \}\\ s.t. \begin{cases} 2x_1+x_2 \leq 10 \\ x_1+x_2\leq 8 \\ x_2\leq 7 \\ x_1, x_2 \geq 0 \end{cases} \end{aligned}

    其中， $x_1$ , $x_2$ 为决策变量。

    最优化(optimization)一般是指在某种条件下作出最好的决策，或者是从众多的方案中选出最好的。 这种问题经常用下面的数学模型描述：

    在给定的约束条件(constraint)下，找出一个决策变量(decision variable)的值，使得被称为目标函数(objective function)的表达愿望尺度的函数值达到最小或最大。

    在解决实际问题时，把问题归结成一个最优化模型是很 重要 的一步，也是很困难的一步，模型建立得是否恰当，直接影响到求解。建立模型的 关键 之一是选择适当的决策变量。

    一般说来决策变量有多个，因此用 $n$ 维向量 $\mathbf{x}=(x_1,\dots,x_n)^T$ 来表示， 于是把 优化问题 写成如下形式

    \[\begin{array}{ll} \min & f(\mathbf{x}) \\ \mathrm{s.t.} & \mathbf{x}\in S \subset\mathbb{R}^n. \end{array} \label{optimization}

    在此， 目标函数 $f$ 是定义在包含 $S$ 的适当集合上的实值函数。

    进一步， $S$ 是该问题变量 $\mathbf{x}$ 的可取值之集合，称为问题的 可行域 (feasible region)。

    满足约束条件 $\mathbf{x}\in S$ 的 $\mathbf{x}$ 称为问题的 可行解 (feasible solution)。

    如果可行解 $\mathbf{x}^*\in S$ 进一步满足

    \[f(\mathbf{x}^*) \leqslant f(\mathbf{x}), \forall \mathbf{x}\in S.

    则称 $\mathbf{x}^*$ 为问题的 全局最优解 (global optimal solution).

    另外，在包含可行解 $\mathbf{x}^*\in S$ 的适当邻域 $U(\mathbf{x}^*)$ 里，成立

    \[f(\mathbf{x}^*) \leqslant f(\mathbf{x}), \forall \mathbf{x}\in S \cap U(\mathbf{x}^*).

    此时称 $\mathbf{x}^*$ 为问题的 局部最优解 (local optimal solution).

  • 不少问题的目标函数或约束条件可能很复杂，要找出全局最优解非常困难， 这时我们的目标就会是求出局部最优解。 \min & f(\mathbf{x}) \\ \mathrm{s.t.} & c_i(\mathbf{x})=0, & i\in E, \\ & c_i(\mathbf{x})\geqslant 0, & i\in I. \end{array} \label{constrained-opt} \] 这里 $c_i(\mathbf{x})$ 是约束函数， $E$ 和 $I$ 分别是 等式约束 的指标集和 不等式 约束的指标集。
  • 当目标函数和约束函数均为线性函数时，问题称为 线性规划 (Linear Programming)；
  • 当目标函数与约束函数中至少有一个是变量 $\mathbf{x}$ 的非线性函数时，问题称为 非线性规划 (Nonlinear Programming)。
  • 此外，根据决策变量、目标函数和要求的不同，最优化还分成了 整数规划 、 动态规划 、 网络规划 、 非光滑规划 、 随机规划 、 几何规划 、 多目标规划 等分支。
  • 一阶必要条件：设目标函数 $f(\mathbf{x})$ 在点 $\bar{\mathbf{x}}$ 处可微，若 $\bar{\mathbf{x}}$ 是局部极小点，则 $\nabla f(\bar{\mathbf{x}})=0$ .
  • 二阶必要条件：设目标函数 $f(\mathbf{x})$ 在点 $\bar{\mathbf{x}}$ 处二次可微，若 $\bar{\mathbf{x}}$ 是局部极小点，则 $\nabla f(\bar{\mathbf{x}})=0$ , 并且Hessian矩阵 $\nabla^2 f(\bar{\mathbf{x}})\ge 0$ .
  • 二阶充分条件：设目标函数 $f(\mathbf{x})$ 在点 $\bar{\mathbf{x}}$ 处二次可微，若 $\nabla f(\bar{\mathbf{x}})=0$ 且 $\nabla^2 f(\bar{\mathbf{x}})>0$ , 则 $\bar{\mathbf{x}}$ 是局部极小点。
  • 充要条件：设 $f(\mathbf{x})$ 是定义在 $\mathbb{R}^n$ 上的可微凸函数，则 $\bar{\mathbf{x}}$ 是整体极小点（全局最优解）的充要条件是 $\nabla f(\bar{\mathbf{x}})=0$ .

    约束问题的最优性条件

    Kuhn-Tucker必要条件 ：设 $\bar{\mathbf{x}}$ 为约束问题的可行点， 记 $I_e=\{i\in I \mid c_i(\bar{\mathbf{x}})=0\}$ , $f$ 和 $c_i(i\in I_e)$ 在点 $\bar{\mathbf{x}}$ 可微， $c_i(i\in I\setminus I_e)$ 在点 $\bar{\mathbf{x}}$ 连续， $c_i(i\in E)$ 在点 $\bar{\mathbf{x}}$ 连续可微， 向量集 $\{\nabla c_i(\bar{\mathbf{x}})\mid i\in E\cup I_e\}$ 线性无关。如果 $\bar{\mathbf{x}}$ 是局部最优解， 则存在数 $\lambda_i\ge 0(i\in I)$ 和 $\mu_i(i\in E)$ 使得

    \[\nabla f(\bar{\mathbf{x}})-\sum_{i\in I}\lambda_i \nabla c_i(\bar{\mathbf{x}})-\sum_{i\in E}\mu_i\nabla c_i(\bar{\mathbf{x}})=0.

    定义 Lagrange函数

    \[L(\mathbf{x},\lambda,\mu)=f(\mathbf{x})-\sum\limits_{i\in I}\lambda_i c_i(\mathbf{x})-\sum\limits_{i\in E}\mu_i c_i(\mathbf{x})

    若 $\bar{\mathbf{x}}$ 为问题局部最优解，则存在乘子向量 $\bar{\lambda}\ge0,\bar{\mu}$ 使得 $\nabla_{\mathbf{x}}L(\bar{\mathbf{x}},\bar{\lambda},\bar{\mu})=0$ .

    此时，一阶必要条件可以表达为

    \[\mathrm{(K-T)}\left\{\begin{array}{l} \nabla_{\mathbf{x}}L(\mathbf{x},\lambda,\mu)=0,\\ c_i(\mathbf{x})=0, i\in E, \\ c_i(\mathbf{x})\ge0, i\in I, \\ \lambda_i c_i(\mathbf{x})=0, i\in I, \\ \lambda_i\ge0, i\in I. \end{array}\right. \label{KT-cond}

    当目标函数和约束函数均为线性函数时，问题称为 线性规划 (Linear Programming)； 一个线性规划问题的 标准类型 为：

    \[\begin{aligned} & \min_x \{ f^T x \}\\ & s.t. \begin{cases} A\cdot x \leq b \\ A_{eq}\cdot x = b_{eq} \\ l_b \leq x \leq u_b \\ \end{cases} \end{aligned}

    其中 $f$ , $x$ , $b$ , $b_{eq}$ , $l_b$ , $u_b$ 均为列向量。 $x$ 为决策变量。 $l_b$ 和 $u_b$ 为对应决策变量的下界向量和上界向量； $A_{eq}$ 和 $b_{eq}$ 为线性等式约束； $A$ 和 $b$ 为不等式约束。

    线性规划问题的最优解的计算通常用 单纯形法 。

    其它线性规划问题，如

    \[\begin{aligned} \max_x \{ f^T x \}\\ s.t. A x \geq b \end{aligned}

    可以变为标准形

    \[\begin{aligned} \min_x \{ -f^T x \}\\ s.t. -A x \leq -b \end{aligned}
    \[\begin{aligned} \max\{ z=4000x_1+3000x_2 \}\\ s.t. \begin{cases} 2x_1+x_2 \leq 10 \\ x_1+x_2\leq 8 \\ x_2\leq 7 \\ x_1, x_2 \geq 0 \end{cases} \end{aligned}

    转换为标准形

    \[\begin{aligned} \min\{ z=-(4000,3000)\begin{pmatrix} x_1 \\ x_2\end{pmatrix} \}\\ s.t. \begin{cases} \begin{pmatrix} 2 & 1 \\ 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2\end{pmatrix} \leq \begin{pmatrix} 10 \\ 8 \\ 7 \end{pmatrix} \\ \begin{pmatrix} 0 \\ 0 \end{pmatrix} \leq \begin{pmatrix} x_1 \\ x_2\end{pmatrix} \end{cases} \end{aligned} 
    import numpy as np
z = np.array([4, 3])
a = np.array([[2, 1.0], [1,1], [0,1]])
b = np.array([10,8, 7])
x1_bound = x2_bound =(0, None)
from scipy import optimize
res = optimize.linprog(-z, A_ub=a, b_ub=b,bounds=(x1_bound, x2_bound))
print(res)
         fun: -26.0
 message: 'Optimization terminated successfully.'
     nit: 2
   slack: array([ 0.,  0.,  1.])
  status: 0
 success: True
       x: array([ 2.,  6.])

    规划问题为：

    \[\begin{aligned}
&\min\{ z=|x_1|+|x_2|+\cdots+|x_n|\} \\
&s.t. A x \leq b
\end{aligned}

    其中$x=(x_1,x_2,\cdots,x_n)^T$。

    \[u_i=\frac{x_i+|x_i|}2, v_i=\frac{|x_i|-x_i}2

    \[u_i\geq 0, v_i\geq 0, x_i=u_i-v_i, |x_i|=u_i+v_i

    这样，问题就可以转换成线性规划问题。





    

    \[\begin{aligned}
\min\{ z=\sum_{i=1}^n(u_i+v_i) \} \\
s.t. \begin{cases}
A(u-v)\leq b \\
u,v\geq 0
\end{cases}
\end{aligned}

    其中$u=(u_1,u_2,\cdots, u_n)^T$, $v=(v_1,v_2,\cdots,v_n)^T$。

    进一步可以写成

    \[\begin{aligned}
\min\{ z=\sum_{i=1}^n(u_i+v_i) \} \\
s.t. \begin{cases}
(A, -A)\begin{pmatrix}u\\v\end{pmatrix}\leq b \\
u,v\geq 0
\end{cases}
\end{aligned}

    例 2.  市场上的若干种投资产品$s_i$，$s_i$的收益率为$r_i$，交易的费率为$p_i$，当购买额不超过$u_i$时，交易费按$u_i*p_i$算，$s_i$的风险率为$q_i$。同时，假定同期的银行利率为$r_0$，没有风险和交易费。
现在，有资金$M$，应该怎么投资呢？收益大，风险低。
 产品  收益(%)  风险(%)  费率(%)  最低交易额(元) 
 $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 

  • 净收入和整体风险只受$r_i$, $p_i$, $q_i$的影响

  • 假定总投资额很大，每个产品投资总额会远大于$u_i$，这样，交易费简单地用$p_ix_i$来计算。

  • 总风险按投资产品中，风险最大的来算$\max\{q_ix_i | i=1,\cdots,n\}$。

  • 银行存款计为产品$s_0$

    使收益尽可能大，风险尽可能小，这是个多目标规划模型。

    目标函数：

    \[\begin{cases}
\displaystyle\max\sum_{i=0}^nx_i(r_i-p_i) \\
\displaystyle\min\{\max_{1\leq i\leq n}\{q_ix_i\}\}
\end{cases}

    约束条件：

    \[\begin{cases}
\displaystyle\sum_{i=0}^n(1+p_i)x_i=M, \\
x_i\geq 0, i=0,1,\cdots,n
\end{cases}

    模型一 固定风险水平。实际投资中，给出投资者的风险界限$a$，也就是说，最多可以承受$Ma$的资金损失，即${q_ix_i}\leq Ma$。因此，模型为

    \[\begin{aligned}
& \displaystyle\max\sum_{i=0}^nx_i(r_i-p_i) \\
& \begin{cases}
q_ix_i\leq M a , i=1,2,\cdots,n \\
\displaystyle\sum_{i=0}^n(1+p_i)x_i=M, \\
x_i\geq 0, i=0,1,\cdots,n
\end{cases}
\end{aligned}

    模型二 固定盈利水平，极小化风险。实际投资中，投资者希望总盈利达到$k$，找一个风险最小的组合。模型为

    \[\begin{aligned}
& \displaystyle \min| \max_{1\leq i\leq n}{q_ix_i}| \\
& \begin{cases}
\displaystyle \sum_{i=0}^n x_i(r_i-p_i)\geq k \\
\displaystyle\sum_{i=0}^n(1+p_i)x_i=M, \\
x_i\geq 0, i=0,1,\cdots,n
\end{cases}
\end{aligned}

    模型三 在风险和收益间，找一个平衡点。对风险、收益分别赋予权重$s$和$1-s$。模型为





    

    \[\begin{aligned}
& \displaystyle \min \left(s| \max_{1\leq i\leq n}{q_ix_i}|-(1-s)\sum_{i=0}^n x_i(r_i-p_i)\right) \\
& \begin{cases}
%\displaystyle \sum_{i=0}^n x_i(r_i-p_i)\geq k \\
\displaystyle\sum_{i=0}^n(1+p_i)x_i=M, \\
x_i\geq 0, i=0,1,\cdots,n
\end{cases}
\end{aligned}

    解模型一

    针对固定风险水平从$0$到$0.05$，每$0.001$获取一个结果，

    可以看到，在$0$到$0.006$，收益增加最快
    

    0.0 0.05
0.001 0.0755276107226
0.002 0.101055221445
0.003 0.126582832168
0.004 0.15211044289
0.005 0.177638053613
0.006 0.201907639778
0.007 0.206607426376
0.008 0.21124338118
0.009000000000000001 0.215519617225
0.010000000000000002 0.219019607843
0.011000000000000003 0.222294117647
0.012000000000000004 0.225568627451
0.013000000000000005 0.228843137255
0.014000000000000005 0.232117647059
    

    例 3.  农场有625亩地，可以种玉米、小麦和燕麦。预计有1000的灌溉用水，有每周300小时的人工。问怎么种植，才有最大的收益？
 条件（每亩）  玉米  小麦  燕麦 
 灌溉用水  3.0  1.0  1.5 
 人工/周  0.8  0.2  0.3 
 收益  400  200  250 

    设种玉米$x_1$亩，种小麦$x_2$亩，种燕麦$x_3$亩，则

    目标： $\max\{400 x_1+200 x_2+250 x_3\}$

    \[\begin{cases}
x_1+x_2+x_3 \leq 625 \\
0.8x_1+0.2x_2+0.3x_3\leq 300 \\
3.0x_1+1.0x_2+1.5x_3 \leq 1000 \\
x_1\geq 0 ,x_2 \geq0 , x_3\geq 0 
\end{cases}

    Mathematica

    Maximize[{400 x1 + 200 x2 + 150 x3, x1 + x2 + x3 <= 625, 
  0.8 x1 + 0.2 x2 + 0.3 x3 <= 300, 3.0 x1 + 1.0 x2 + 1.5 x3 <= 1000, 
  x1 >= 0, x2 >= 0, x3 >= 0}, {x1, x2, x3}]
    

    {162500., {x1 -> 187.5, x2 -> 437.5, x3 -> 0.}}
    

    例 4.  农场有625亩地，可以种玉米、小麦和燕麦。有5块120亩和1块25亩的地，每块地只种一种作物。预计有1000的灌溉用水，有每周300小时的人工。问怎么种植，才有最大的收益？
 条件（每亩）  玉米  小麦  燕麦 
 灌溉用水  3.0  1.0  1.5 
 人工/周  0.8  0.2  0.3 
 收益  400  200  250 

    设120亩地中，种玉米$x_1$亩，种小麦$x_2$亩，种燕麦$x_3$亩；25亩地中，种玉米$x_4$亩，种小麦$x_5$亩，种燕麦$x_6$亩；则

    \[\max\{120(400 x_1+200 x_2+250 x_3)+25(400 x_4+200 x_5+250 x_6)\}

    \[\begin{cases}
x_1+x_2+x_3 \leq 5 \\
x_4+x_5+x_6 \leq 1 \\
120(0.8x_1+0.2x_2+0.3x_3)+25(0.8x_4+0.2x_5+0.3x_6)\leq 300 \\
120(3.0x_1+1.0x_2+1.5x_3)+25(3.0x_4+1.0x_5+1.5x_6) \leq 1000 \\
x_1\geq 0 ,x_2 \geq0 , x_3\geq 0 ,
x_4\geq 0 ,x_5 \geq0 , x_6\geq 0 \\
x_i\in \mathbb{Z}
\end{cases}

    Mathematica

    Maximize[{120 (400 x1 + 200 x2 + 150 x3) + 
   25 (400 x4 + 200 x5 + 150 x6), x1 + x2 + x3 <= 5, 
  x4 + x5 + x6 <= 1, 
  120 (0.8 x1 + 0.2 x2 + 0.3 x3) + 25 (0.8 x4 + 0.2 x5 + 0.3 x6) <= 
   300, 120 (3.0 x1 + 1.0 x2 + 1.5 x3) + 
    25 (3.0 x4 + 1.0 x5 + 1.5 x6) <= 1000, x1 >= 0, x2 >= 0, x3 >= 0, 
  x4 >= 0, x5 >= 0, x6 >= 0, 
  Element[{x1, x2, x3, x4, x5, x6}, Integers]}, {x1, x2, x3, x4, x5, 

    {154000., {x1 -> 1, x2 -> 4, x3 -> 0, x4 -> 1, x5 -> 0, x6 -> 0}}
    

    规划中的决策变量（部分或全部）限制为整数时，称为整数规划(Integer Programming)。若在线性规划模型中的决策变量限制为整数，则称为整数线性规划。目前可以处理整数线性规划，还没有一种方法能有效地求解一切整数规划。

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

  • 整数规划问题的计算方法包括：分枝界定法，隐枚举法，匈牙利法，蒙特卡洛法等。
1.5x_1+3x_2+5x_3 \leq 600 \\
280x_1+250x_2+400x_3 \leq 60000 \\
x_1, x_2, x_3 \in \mathbb{N} \\
x_1\geq0, x_2\geq 0, x_3\geq 0
\end{cases}

    0-1型整数规划(binary integer programing)(BIP)

    例 6.  汽车厂可以生产小、中、大三种汽车。由于条件限制，某一类型的汽车，要么不生产，要么至少80辆。制定计划，使工厂利润最大。
 材料  小车  中型车  大型车  总量 
 钢材  1.5  3  5  600 
 人工  280  250  400  60000 
 利润  2  3  4  

    设生产小型车$x_1$辆，中型车$x_2$车，大型车$x_3$辆，则

    目标: $\max\{2x_1+3x_2+4x_3\}$

    \[\begin{cases}
1.5x_1+3x_2+5x_3 \leq 600 \\
280x_1+250x_2+400x_3 \leq 60000 \\
x_1, x_2, x_3 \in \mathbb{N} \\
x_1\geq80 | x_1=0, x_2\geq 80| x_2=0, x_3\geq 0| x_3=0
\end{cases}

    方法一： 将问题分解为8个线性规划子模型





    

    \[\begin{aligned}
x_1=0, x_2=0, x_3\geq 80 \\
x_1=0, x_2\geq 80, x_3 \geq 80 \\
x_1=0, x_2=0, x_3 =0 \\
x_1=0, x_2\geq80, x_3 =0 \\
x_1\geq80, x_2=0, x_3\geq 80 \\
x_1\geq80, x_2\geq 80, x_3 \geq 80 \\
x_1\geq80, x_2=0, x_3 =0 \\
x_1\geq80, x_2\geq80, x_3 =0 \\
\end{aligned}

    逐一求解这8个问题，取出最优解

    方法二：变为非线性规划。 把约束条件变为

    \[x_1(x_1-80)\geq 0, x_2(x_2-80)\geq 0, x_3(x_3-80)\geq 0

    引入0-1变量： 设$y_1$, $y_2$, $y_3$只取$0$或$1$两个值，则条件变为

    \[\begin{aligned}
x_1(x_1-80)\geq 0 \Longleftrightarrow & 80y_1\leq x_1 \leq M y_1 \\
x_2(x_2-80)\geq 0 \Longleftrightarrow & 80y_2\leq x_2 \leq M y_2 \\
x_3(x_3-80)\geq 0 \Longleftrightarrow & 80y_3\leq x_3 \leq M y_3
\end{aligned}

    其中$M$为充分大的数。

    Mathematica

    In[279]:= Maximize[{2 x1 + 3 x2 + 4 x3, 1.5 x1 + 3 x2 + 5 x3 <= 600, 
  280 x1 + 250 x2 + 400 x3 <= 60000, x1 <= 10^9*y1, x2 <= 10^9 y2, 
  x3 <= 10^9  y3, x1 >= 80 y1, x2 >= 80 y2, x3 >= 80 y3, x1 >= 0, 
  x2 >= 0, x3 >= 0, Element[{x1, x2, x3}, Integers], 
  y1 == 0 || y1 == 1, y2 == 0 || y2 == 1}, {x1, x2, x3, y1, y2, y3}]
Out[279]= {610., {x1 -> 80, x2 -> 150, x3 -> 0, y1 -> 1., y2 -> 1., 
  y3 -> 0.}}
    

    In[278]:= NMaximize[{2 x1 + 3 x2 + 4 x3, 1.5 x1 + 3 x2 + 5 x3 <= 600, 
  280 x1 + 250 x2 + 400 x3 <= 60000, x1 <= 10^9*y1, x2 <= 10^9 y2, 
  x3 <= 10^9  y3, x1 >= 80 y1, x2 >= 80 y2, x3 >= 80 y3, x1 >= 0, 
  x2 >= 0, x3 >= 0, Element[{x1, x2, x3}, Integers], 
  y1 == 0 || y1 == 1, y2 == 0 || y2 == 1, y3 == 1 || y3 == 0}, {x1, 
  x2, x3, y1, y2, y3}]
During evaluation of In[278]:= NMaximize::bcons: The following constraints are not valid: {1.5 x1+3 x2+5 x3<=600,280 x1+250 x2+400 x3<=60000,x1<=1000000000 y1,x2<=1000000000 y2,x3<=1000000000 y3,x1>=80 y1,x2>=80 y2,x3>=80 y3,x1>=0,x2>=0,x3>=0,(x1|x2|x3)\[Element]Integers,y1==0||y1==1,y2==0||y2==1,y3==1||y3==0}. Constraints should be equalities, inequalities, or domain specifications involving the variables. >>
Out[278]= NMaximize[{2 x1 + 3 x2 + 4 x3, 1.5 x1 + 3 x2 + 5 x3 <= 600, 
  280 x1 + 250 x2 + 400 x3 <= 60000, x1 <= 1000000000 y1, 
  x2 <= 1000000000 y2, x3 <= 1000000000 y3, x1 >= 80 y1, x2 >= 80 y2, 
  x3 >= 80 y3, x1 >= 0, x2 >= 0, 
  x3 >= 0, (x1 | x2 | x3) \[Element] Integers, y1 == 0 || y1 == 1, 
  y2 == 0 || y2 == 1, y3 == 1 || y3 == 0}, {x1, x2, x3, y1, y2, y3}]
    

    ref: https://reference.wolfram.com/language/guide/Optimization.html
    

    例 7.  (固定费用问题)假定生产某种产品，有几种方式可供选择。每种方式有固定成本$k_j$，和生产每件需要的变动成本$c_j$。即对生产方式$s_j$，生产$x_j$件产品，需要成本

    \[P_j=\begin{cases} k_j+c_jx_j , & x_j>0 \\
0, & x_j=0
\end{cases}

    如何选择，使成本最低呢？（假定共$s_1$, $s_2$, $s_3$三种方式）
    

    引入$0$-$1$变量$y_j$，$j=1,2,3$

    \[y_j=\begin{cases} 1, & x_j>0 \\
0, & x_j=0
\end{cases}

    用来表明使用了方法$s_j$。它等价于下面的约束条件

    \[y_j\epsilon\leq x_j\leq y_j M_j

    其中$\epsilon$是一个充分小的正数，$M$是充分大的正数。

    可以看到，当$x_j>0$时，必须有$y_j=1$；当$x_j=0$时，只有$y_j=0$才行。
    

    则模型可以写成：

    \[\min[z=(k_1y_1+c_1x_1)+(k_2y_2+c_2x_2)+(k_2y_2+c_2x_2)]

    \[\begin{cases}
y_j\epsilon\leq x_j\leq y_j M_j , & j=1,2,3 \\
y_j=0|1,& j=1,2,3 \\
x_j\geq 0 ,& j=1,2,3
\end{cases}

    其中$\epsilon$是一个充分小的正数，$M$是充分大的正数。
    

    例 8.  (约束条件中有相互排斥的) 有两种运输方式，只能选择其中的一种。用车运输时满足约束条件
$5x_1+4x_2\leq 24$，用船时满足约束条件 $7x_1+3x_2\leq 45$。




    

    

    为了统一在一个问题中，引入$0$-$1$变量

    \[y=\begin{cases} 1 , \mbox{ship} \\ 0 , \mbox{car}
\end{cases}

    则约束条件可以写成

    \[\begin{cases}
5x_1+4x_2\leq 24 + yM \\
7x_1+3x_2\leq 45 + (1-y)M \\
y=0 or 1
\end{cases}

    其中$M$为充分大的正数。
    

    若有$m$个互斥的约束条件

    \[a_{i1}x_1+\cdots+a_{in}x_n\leq b_i, i=1,2,\cdots,m

    则引入一个充分大的$M$和$m$个$0-1$变量$y_i$, $i=1,\cdots,m$，
组成如下约束条件

    \[\begin{cases}
a_{i1}x_1+\cdots+a_{in}x_n\leq b_i+(1-y_i)M, i=1,2,\cdots,m \\
y_1+y_2+\cdots+y_m=1 \\
y_0=1 \mbox{or} 0
\end{cases}

    可以看到，$y_i$中只能有一个取$1$，而$y_i=1$表示使用第$i$个条件。
    

    例 9.  (指派问题) 分配$n$个人去完成$n$项工作，第$i$个人完成第$j$项工作需要$c_{ij}$的单位时间。问如何工作才能使总的工作时间最小？
    

    解： 引入$0-1$变量$x_{ij}$，当第$i$人做工作$j$时，取值为$1$，否则为$0$。则指派问题的数学模型为：

    目标： $\displaystyle\min \sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij}$

    \[\begin{cases}
\displaystyle\sum_{j=1}^nx_{ij}=1 , i=1,\cdots,n \\
\displaystyle\sum_{i=1}^nx_{ij}=1, j=1,\cdots, n\\
x_{ij}=0\ \mbox{or}\ 1
\end{cases}

    Python中，可以使用

    scipy.optimize.linear_sum_assignment(cost_matrix)
    

    https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html#scipy.optimize.linear_sum_assignment
    

    例 10.  某学校规定，运筹专业的学生毕业时，必须至少学习2门数学课，3门运筹学课和2门计算机课。问，毕业时，学生最少可以学习这些课程的哪些？如果想课程数量少，学分多，他应该如何选修？
 序号  课程名称  学分  所属类别  先修课要求 
 1  微积分  5  数学  
 2  线性代数  4  数学  
 3  最优化方法  4  数学；运筹学  微积分；线性代数 
 4  应用统计  4  数学；运筹学  微积分；线性代数 
 5  数学实验  3  计算机；运筹学  微积分；线性代数 
 6  计算机编程  2  计算机  
 7  数据结构  3  数学；计算机  计算机编程 
 8  计算机模拟  3  运筹学；计算机  计算机编程 
 9  预测理论  2  运筹学  应用统计 

    用$x_i=1$表示选修课程$i$，$x_i=0$表示不选。

    目标: $\min( z=\sum_{i=1}^9 x_i)$

  • 至少学习的课程数

    \[\begin{cases}
x_1+x_2+x_3+x_4+x_7\geq 2 \\
x_3+x_4+x_5+x_8+x_9\geq 3 \\
x_5+x_6+x_7+x_8\geq 2 \\
\end{cases}

  • 课程的先修课程要求。如：“数据结构”的选修课是“计算机编程”，表示若$x_7=1$则必有$x_6=1$，若$x_7=0$，则对$x_6$的值没有限制，可以用$x_7\leq x_6$来表示。类似，“最优化方法”的先修课是“微积分”和“线性代数”，则有$x_3\leq x_2$, $x_3\leq x_1$，表示为$2x_3\leq x_1+x_2$。




    

    • 

    \[\begin{cases}
2x_3\leq x_1+x_2 \\
2x_4\leq x_1+x_2 \\
2x_5\leq x_1+x_2 \\
x_7\leq x_6 \\
x_8\leq x_6 \\
x_9\leq x_4
\end{cases}

    加上$x_i$是$0-1$变量的约束条件

    若有学生想课程少，而学分又多。则需要再加上目标:

    \[\max (w=5x_1+4x_2+4x_3+4x_4+3x_5+2x_6+3x_7+3x_8+2x_9)

    此时，目标多于一个，称这种多于一个目标的规划问题为多目标规划。要得到它的解，通常需要知道决策者对每个目标的重视程度（偏好程度）。
    

  • 更重视目标$w$，则以它为目标构建单目标规划

  • 课程数少是基本的前提，则可以先以前面的目标$z$为单目标规划，得到解为至少6门课。然后以目标$w$为目标函数，在约束中加入

    \[\sum_{i=1}^9x_i=6
\]
    来找一个学分最多的解(可能不唯一)。

  • 给两个目标$w$和$z$乘上不同的权重，组成新的目标函数。如：三七开的目标权重，

    \[\min (y=0.7z-0.3w)

    例 11.  有10个工件在一台机床上加工。这10个工件中,有些工件必须在另一些工件加工完毕之后才能加工。按规定,在工件运抵后266h内应加工完毕,否则要支付一定的赔款,赔款数正比于延误的时间。设由于机床的故障,10个工件运抵后 $T h$ 才开始加工。要安排一个加工次序,使得支付的赔款最少。
 工件号  1  2  3 4  5 6 7 8  9 
 加工时间/h  20  28  25  45  16  12  60  10  20 
 前期工件号  3  8  7  /  1,2,6  8  4  3  5 
 每小时赔款/元  12  14 15  10 10  11 12  8 6 

    例 12.  (搭配问题) 客户需要50根4m、20根6m、15根8m的钢管。而钢管零售商从钢管厂进化得到的原料是19m的，问应该如何切割最省？（问至少需要进多少钢管原料）
    

    19m的钢管切割成4m, 6m, 8m的钢管，有多种不同的切割模式。一个合理的切割模型应该保证废料要小于客户需要的最小尺寸。
 模式  4m钢管数  6m钢管数  8m钢管数  作料(m) 
 1  4  0  0  3 
2  3  101
32013
41203
51111
60301
70023

    目标: 切割废料最少

    \[\min(z_1=3x_1+x_2+3x_3+3x_4+x_5+x_6+3x_7)

    或者用的钢管数最少

    \[\min(z_2=x_1+x_2+x_3+x_4+x_5+x_6+x_7)

    \[\begin{cases}
4x_1+3x_2+2x_3+x_4+x_5\geq 50 \\
x_2+2x_4+x_5+3x_6\geq 20 \\
x_3+x_5+2x_7\geq 15
\end{cases}

    例 13.  (搭配问题) 客户需要50根4m、20根6m、15根8m和10根5m的钢管。而钢管零售商从钢管厂进化得到的原料是19m的。基于成本的要求，切割方式不能超过3种。问至少需要进多少钢管原料？
    

    模型： 同样，需要保证切割时的废料小于4m。由于切割方式不超过3种，用$x_i$表示按模型$i$切割的原料数，它们是非负整数。设第$i$种切割模式下生产4m, 5m, 6m, 8m的钢管数为$r_{i1}$,$r_{i2}$,$r_{i3}$,$r_{i4}$（非负整数）。

    目标：原料少

    \[\min (z=x_1+x_2+x_3)

    约束： 满足客户需要





    

    \[\begin{cases}
r_{11}x_1+r_{12}x_2+r_{13}x_3\geq 50 \\
r_{21}x_1+r_{22}x_2+r_{23}x_3\geq 10 \\
r_{31}x_1+r_{32}x_2+r_{33}x_3\geq 20 \\
r_{41}x_1+r_{42}x_2+r_{43}x_3\geq 15 \\
\end{cases}

    切割模型是合理的，废料小于4m，

    \[\begin{cases}
16\leq 4r_{11}+5 r_{21}+ 6r_{31}+8r_{41} \leq 19 \\
16\leq 4r_{12}+5 r_{22}+ 6r_{32}+8r_{42} \leq 19 \\
16\leq 4r_{13}+5 r_{23}+ 6r_{33}+8r_{43} \leq 19 \\
16\leq 4r_{14}+5 r_{24}+ 6r_{34}+8r_{44} \leq 19 \\
\end{cases}

    是整数非线性规划模型。求解困难。

    可以再加些约束条件，来帮助软件缩小范围。

  • 可以看到，至少需要

    \[\left[\frac{4\times50+5\times10+6\times20+8\times15}{19}\right]+1=26

  • 至多呢？可以取一种可用的模式（如：模式1只切割4m，模式2切割1根5m和2根6m，模式3只切割8m）下，需要的原料数（13+10+8=31根）作为上界

    \[26\leq x_1+x_2+x_3\leq 31

    例 14.  (投资决策) 企业有$n$个项目可供投资。企业拥有总资金$A$元，第$i$个项目需要投资$a_i$元，预计收益$b_i$元。试选择最佳投资方案
    

    模型： 用$x_i=1$表示投资项目$i$，$x_i=0$表示不投资这个项目，则

    目标: 总收益与总投入的比最大

    \[\max(Q=\frac{\sum_{i=1}^nb_ix_i}{\sum_{i=1}^na_ix_i})

    \[\begin{cases}
\sum_{i=1}^na_ix_i\leq A \\
x_i(1-x_i)=0
\end{cases}

    例 15.  某公司生产2种显示器，31英寸和27英寸。除了40000元的固定费用外，每台27英寸的成本1950元，31英寸的成本2250元，它们的售价分别为3990和3390。营销人员预测，每卖出一台显示器，价格就会下降0.1元。另外，每售出一台27英寸的会导致31英寸的降价0.04元，而每售出一台31英寸的会导致27英寸的降价0.03元。问应该如何生产，才能达到利润最大化？
    

    模型： 设生产31英寸的$x_1$台，生产27英寸的$x_2$台。则每台售价$P_i$为

    \[\begin{cases}
P_1=3990-0.1x_1-0.04x_2 \\
P_2=3390-0.1x_2-0.03x_1 \\
\end{cases}

    \[\min z=P_1 x_1+P_2 x_2-(40000+1950 x_2+2250 x_1)

    \[\min z=1440x_2-0.1x_2^2+1740x_1-0.1x_1^2-0.07x_1x_2-40000

    目标函数是一个二次函数（称为二次规划问题）。可以用最速下降梯度法。
    

    背包问题 (Knapsack problem)
    

    例 16.  
有$n$种物品，物品$j$的重量为$w_j$，价格为$p_j$。若背包所能承受的最大重量为$W$。则

    目标: $\displaystyle\max\left(\sum_{j=1}^n p_jx_j \right)$

    限制: $\displaystyle\sum_{j=1}^n w_jx_j\leq W$

  • 若限定每种物品只能最多1个，则问题为0-1背包问题

    \[x_j\in\{0,1\}

  • 若限定物品$j$只能最多$b_j$个，则问题为有界背包问题

    \[x_j\in\{0,1,\cdots,b_j\}

    若目标函数为

    \[\max\left(\sum_{j=1}^n p_j x_j+\sum_{i=1}^{n-1}\sum_{j=i+1}^n p_{ij} x_i x_j\right)

    \[\begin{cases}
\sum_{j=1}^n w_j x_j \leq W, \\
x_j \in \{0,1\}
\end{cases}

    则是背包问题的推广，二次背包问题
    

    Matlab解规划问题

  • 非线性规划  fmincon 

  • 无约束极值  fminunc ,  fminsearch 

  • 二次规划问题(目标函数是二次函数，约束条件全部是线性的)  quadprog ,

  • 其它 fseminf (半无穷约束条件), 

  •  fminimax  （$\min_x \max_i F_i(x)$）
    • 

    Mathematica
数值最优化

    NMinimize, NMaximize — 全局的非线性约束最优化
FindMinimum, FindMaximum — 局部无约束或约束的最优化
FindFit — 最优化的非线性的无约束或约束的数据拟合
    

    符号最优化

    Minimize, Maximize — 符号的全局最优化
    

    极限值和位置

    MinValue, MaxValue — 最小、最大数值
NMinValue ▪  NMaxValue ▪  FindMinValue ▪  FindMaxValue
ArgMin, ArgMax — 最小值、最大值的位置
NArgMin ▪  NArgMax ▪  FindArgMin ▪  FindArgMax
    

    LinearProgramming — 矩阵形式的实数和整数线性规划
LeastSquares — 矩阵形式的最小二乘问题
    

    Python

    scipy.optimize
    

    cvxpy (a Python-embedded modeling language for convex optimization problems)
https://stanford.edu/class/ee364a/lectures.html
    

    Pyomo is a Python-based, open-source optimization modeling language with 
  a diverse set of optimization capabilities.
    

    PuLP is an LP modeler written in python.
https://github.com/coin-or/pulp
    

    import numpy as np
z = np.array([2, 3, 1])
a = np.array([[1, 4, 2], [3, 2, 0]])
b = np.array([8, 6])
x1_bound = x2_bound = x3_bound =(0, None)
from scipy import optimize
res = optimize.linprog(z, A_ub=-a, b_ub=-b,bounds=(x1_bound, x2_bound, x3_bound))
print(res)
#output:
#     fun: 7.0
# message: 'Optimization terminated successfully.'
#     nit: 2
#   slack: array([0., 0.])
#  status: 0
# success: True
#       x: array([0.8, 1.8, 0. ])
    

    pulp在线性规划这一部分

    https://www.jianshu.com/p/9be417cbfebb
    

    import cvxpy
import numpy as np
# The data for the Knapsack problem
# P is total weight capacity of sack
# weights and utilities are also specified
P = 165
weights = np.array([23, 31, 29, 44, 53, 38, 63, 85, 89, 82])
utilities = np.array([92, 57, 49, 68, 60, 43, 67, 84, 87, 72])
# The variable we are solving for
selection = cvxpy.Bool(len(weights))
# The sum of the weights should be less than or equal to P
weight_constraint = weights * selection <= P
# Our total utility is the sum of the item utilities
total_utility = utilities * selection
# We tell cvxpy that we want to maximize total utility 
# subject to weight_constraint. All constraints in 
# cvxpy must be passed as a list
knapsack_problem = cvxpy.Problem(cvxpy.Maximize(total_utility), [weight_constraint])
# Solving the problem
knapsack_problem.solve(solver=cvxpy.GLPK_MI)
    

    1. 最优化建模
    

    1.1. 最优化
    

    1.2. 线性规划
    

    1.3. 投资组合
    

    1.4. 整数规划
    

    1.5. 背包问题 (Knapsack problem)
    

    1.6. 目录
    

    例 17.  谢
    •  
    推荐文章
    很酷的跑步机  ·  羽球奥运积分赛提前终止 东京奥运赛场谁主沉浮？--日本频道--人民网
    4 周前
    飞翔的大蒜  ·  [北京新闻]“夏季空调调高一度 畅享健康低碳生活”专项引导行动推介会举行_时政频道_央视网(cctv.com)
    1 年前
    刚毅的抽屉  ·  管理 Office 应用中的敏感度标签 | Microsoft Learn
    1 年前
    气势凌人的火龙果  ·  梅西将加盟美国职业足球大联盟迈阿密国际队-中新网
    1 年前
    成熟的橡皮擦  ·  少林秘谱：三十六抓解脱法释秘_敌人_对方_头发
    1 年前
    今天看啥   ·   Py中国   ·   codingpro   ·   小百科   ·   link之家   ·   卧龙AI搜索
    删除内容请联系邮箱 2879853325@qq.com
    Code - 代码工具平台
    © 2024 ~ 沪ICP备11025650号