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

大耳朵土土垚

发布于 2024-05-24 14:13:50

440

发布于 2024-05-24 14:13:50

文章被收录于专栏：c/c++c/c++

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

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

高数基础

1.最值和极值

最值：整体性极值：局部性设f(x)在

x_0

的邻域(附近)，若存在ɛ，使得在区间（

x_0

-ɛ，

x_0

+ɛ）上f(x)>=f(

x_0

)(或者f(x)=<f(

x_0

))，则f(

x_0

)为极小值(或者极大值)

2.费马定理

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

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*g_1 +ʎ_2*g_2

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

\begin{cases} \frac{əF}{əx} = 6x +3ʎ_1x + 12ʎ_2x = 0\\ \frac{əF}{əy} = 0\\ \frac{əF}{əz} = 0\\ \frac{əF}{əʎ_1} = 0\\ \frac{əF}{əʎ_2} = 0 \end{cases}

求出偏导将其等于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) + ʎ_1g_1

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

(3)求偏导

我们发现这里有根号求导不是很简单所以我们可以换个方法，求最小的距离和求最小距离的平方本质上都可以得出解，所以我们就可以将F变一下再求偏导：

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

\begin{cases} \frac{əF}{əx} = 6x +3ʎ_1x + 12ʎ_2x = 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{cases}

(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}=\begin{bmatrix} {\frac{ə^2F}{əx_1^2}}&{\frac{ə^2F}{əx_1əx_2}}&{\cdots}& {\frac{ə^2F}{əx_1əx_n}}\\ {\frac{ə^2F}{əx_2əx_1}}&{\frac{ə^2F}{əx_2əx_2}}&{\cdots}& {\frac{ə^2F}{əx_2əx_n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {\frac{ə^2F}{əx_nəx_1}}&{\frac{ə^2F}{əx_nəx_2}}&{\cdots}& {\frac{ə^2F}{əx_nəx_n}} \end{bmatrix}|M_0(a_1,a_2...a_n)

并将点

M_0

代入该矩阵中

\frac{ə^2F}{ə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)

，直接求每一个的偏导然后得出若干个点，对于每个点求其海森矩阵，进行判断