【运筹学】前言：基础知识

💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

💥个人主页：大耳朵土土垚的博客
💥 所属专栏：运筹学基础
这里将会不定期更新有关运筹学的内容，希望大家多多点赞关注收藏💖💖

线性代数是通过一系列的手段去”折腾“方程组，提取其系统信息；
而运筹学要解决一般视角下的最优化问题，寻求最好的解决办法，也就是寻找一般函数的最大最小值问题。
关于寻求最优解我们要记住两步：
第一步我们要数学建模，第二步求解这个数学模型

在学习运筹学之前我们先要储备一些高数相关知识，比如极值最值，通过拉格朗日乘数法求解极值等。

高数基础

1.最值和极值

最值：整体性
极值：局部性
设f(x)在$x_0$的邻域(附近)，若存在ɛ，使得在区间（$x_0$-ɛ，$x_0$+ɛ）上f(x)>=f($x_0$)(或者f(x)=<f($x_0$))，则f($x_0$)为极小值(或者极大值)

2.费马定理

这里定义是自己理解得出并不代表标准的定义：

f($x_0$)是极值并且f(x)在$x_0$处可导，则f’($x_0$) = 0；

注意这里不能反推:
例如f(x) = $x^3$ 在x=0处f’(0) = 0，但是f(0)并不是极值

3.利用费马定理求最值

条件：

f(x)定义域[a,b]，连续可导

解决思路：

找出所有极值点，在加上边界点a,b，代入f(x)，最后一起比较出最值

而找出所有极值点就可以利用费马定理，通过找出导数为0的点来规避求极值，先不管求出来的是不是极值点，反正最后和边界点一起代入原函数，找出最大最小值就行。
例题：
$f(x)=3x^2-6x+7$ 定义域[-10,50]

第一步：求导

①f’(x) = 6x-6

第二步：求导数为0时x值

f’(x) = 6x-6=0
②x=1

第三步将x=1和边界点-10和50带入f(x)中，求出最值

③f(1) = 4
④f(-10) = 367
⑤f(50) = 7207

最值为7207，这样就规避了先求极值再求最值

如果定义域为[10,20]就不需要求f(1)了，直接比较边界点就行

4.多元函数的极值与最值

✨拉格朗日乘数法

引例： 求最值

目标函数：

$w=f(x,y,z)=3x^2+2y^2-4z^2$

约束条件：

①$g_1:3x+4y-z=0$
②$g_2:6x^2+y-z^2=0$

拉格朗日乘数法求解

(1)构造新函数

几个约束条件就引入几个拉格朗日乘子，这里有两个约束条件$g_1$，$g_2$，就引入两个拉格朗日乘子${ʎ}_1$，${ʎ}_2$来构造一个新函数$F(x,y,z,{ʎ}_1,{ʎ}_2)=f(x,y,z)+{ʎ}_1\ast g_1+{ʎ}_2\ast g_2$

(2)求偏导，并令偏导等于0

$$\{\begin{array}{l}\frac{əF}{əx}=6x+3{ʎ}_{1}x+12{ʎ}_{2}x=0\\ \frac{əF}{əy}=0\\ \frac{əF}{əz}=0\\ \frac{əF}{ə{ʎ}_1}=0\\ \frac{əF}{ə{ʎ}_2}=0\end{array}$$

求出偏导将其等于0，求出解，代入原函数f(x,y,z)中，求出最值

以上就是拉格朗日乘数法的使用，接下来我们做一道例题巩固一遍

例题：
在抛物面$z=(x+2{)}^2+\frac{1}{4}{y}^2$上求到点(3,0,-1)的最近距离

(1)建模

通过读题，我们发现最近距离题目中没给出，我们需要自己写，此外在抛物面$z=(x+2{)}^2+\frac{1}{4}{y}^2$上这是一个约束条件所以建模如下：

目标函数

距离$d=f(x,y,z)=\sqrt{(x-3{)}^2+(y-0{)}^2+(z+1{)}^2}$

约束条件

$g_1:z=(x+2{)}^2+\frac{1}{4}{y}^2$

这里需要转换成一边等于0的形式:

$g_1:(x+2{)}^2+\frac{1}{4}{y}^2-z=0$

(2)引入拉格朗日乘子ʎ_1，构建新函数$F(x,y,z,{ʎ}_1)$

$F(x,y,z,{ʎ}_1)=f(x,y,z)+{ʎ}_1{g}_1$

= $\sqrt{(x-3{)}^2+(y-0{)}^2+(z+1{)}^2}+{ʎ}_1[(x+2{)}^2+\frac{1}{4}{y}^2-z]$

(3)求偏导

我们发现这里有根号求导不是很简单所以我们可以换个方法，求最小的距离和求最小距离的平方本质上都可以得出解，所以我们就可以将F变一下再求偏导：
$F^{\prime }=(x-3{)}^2+(y-0{)}^2+(z+1{)}^2+{ʎ}_1[(x+2{)}^2+\frac{1}{4}{y}^2-z]$

$$\{\begin{array}{l}\frac{əF}{əx}=6x+3{ʎ}_{1}x+12{ʎ}_{2}x=0\\ \frac{əF}{əy}=2y+\frac{{ʎ}_1}{2}y=0\\ \frac{əF}{əz}=2(z+1)-{ʎ}_1=0\\ \frac{əF}{ə{ʎ}_1}=(x+2{)}^2+\frac{1}{4}{y}^2-z=0\end{array}$$

(4)求解

有唯一解x = -1,y =0;z = 1,ʎ_1=4

说明：拉格朗日乘数法只适用于强约束条件，也就是约束条件是=的情况，而弱约束条件<=或者>=则可以使用KKT定理

5.求极值

✨海森(Hessian)矩阵

对于n元$f(x_1,x_2...x_n)$在点$M_0(a_1,a_2...a_n)$的领域内有二阶连续偏导，若$\frac{əF}{əx_i}{|}_{M_0(a_1,a_2...a_n)}=0$且
矩阵$$A_{M_0}=\left[\begin{array}{cccc}\frac{{ə}^{2}F}{əx_1^2}& \frac{{ə}^{2}F}{əx_1əx_2}& \cdots & \frac{{ə}^{2}F}{əx_1əx_n}\\ \frac{{ə}^{2}F}{əx_2əx_1}& \frac{{ə}^{2}F}{əx_2əx_2}& \cdots & \frac{{ə}^{2}F}{əx_2əx_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{ə}^{2}F}{əx_nəx_1}& \frac{{ə}^{2}F}{əx_nəx_2}& \cdots & \frac{{ə}^{2}F}{əx_nəx_n}\end{array}\right]|M_0(a_1,a_2...a_n)$$

并将点$M_0$代入该矩阵中

$\frac{{ə}^{2}F}{əx_nəx_1}$表示F先对$x_n$求偏导，然后再对$x_1$求偏导

如果矩阵$A_{M_0}$是正定的，则F在$M_0$处取得极小值.
如果矩阵$A_{M_0}$是负定的，则F在$M_0$处取得极大值.
如果矩阵$A_{M_0}$都不是，则$M_0$不是极值点.
如果矩阵$A_{M_0}$是半正(负)定，则$M_0$是可疑点(该法失效，另寻他法).

这里了解一下就行：正定矩阵是指一个矩阵的所有特征值都为正数的方阵。换句话说，对于一个n阶方阵A，如果所有特征值λi都满足λi > 0，则A是正定矩阵。
更具体地说，对于一个n阶实对称矩阵A，如果对于任意非零向量x，都有x^T * A * x > 0，则A是正定矩阵。在这种情况下，A的所有特征值都是正数。
正定矩阵具有很多重要的性质和应用。例如，在优化问题中，正定矩阵可以保证目标函数的二次型部分是凸函数，从而保证最优解的存在性和唯一性。在数值计算中，正定矩阵也可以用于解线性方程组和最小二乘问题，提高计算的稳定性和效率。

解题方法

对于n元$f(x_1,x_2...x_n)$，直接求每一个的偏导然后得出若干个点，对于每个点求其海森矩阵，进行判断

例题

$f(x,y)=2x^2+6xy+y^2$ 在自然定义域内，求极值点
①求偏导
$$\{\begin{array}{l}\frac{əF}{əx}=4x+6y\\ \frac{əF}{əy}=2y+6x\end{array}$$
②令偏导为0
$$\{\begin{array}{l}4x+6y=0\\ 2y+6x=0\end{array}$$
求出点M(0,0)
③求二次偏导得出海森矩阵

$$\{\begin{array}{l}\frac{{ə}^{2}F}{əx^2}=4\\ \frac{{ə}^{2}F}{əxəy}=6\\ \frac{{ə}^{2}F}{əyəx}=6\\ \frac{{ə}^{2}F}{əy^2}=2\end{array}$$

$$A_m=\left[\begin{array}{cc}4& 6\\ 6& 2\end{array}\right]$$
④判断是否为极值点

矩阵$A_m$是正定矩阵所以在$M_0$处取得极小值