1.线性规划

在这节中我们规定线性规划的标准型为：

其中：

• 是一个 矩阵，且 。

规定：

其中：

• 是 的一个 满秩子矩阵，并且其列向量记作 。称 为基。

定理1-1：如果一个线性规划的的可行域不是空集，那么这个可行域是凸集。

凸集定义为：

设 是 维欧几里得空间 中的一个集合。如果对于所有 和所有 ，都有：

那么 就是一个凸集。

证明：

若 和 是可行域 中任意的两个点
则有

设

则显然有

故 即 是凸集。

引理1-1：设 D 是有界凸多面体集，那么对于 D 中的任意 X 可以表示为顶点的凸组合。

证明：

设 是一个有界凸集。我们要证明对于任意 ，存在 的顶点 和标量 且 ，使得

我们采用数学归纳法来证明这一结论。

基础情况：当 是 的顶点时，结论显然成立（取 , ）。

归纳步骤：假设对于所有能用不超过 个顶点的凸组合表示的 ，结论成立。现在考虑一个点 ，它不能表示为少于 个顶点的凸组合。

由于 不是顶点，存在 ，，和 ，使得

考虑通过 的任意直线 。由于 有界， 是一个有界线段。设其端点为 和 ，则存在 使得

根据归纳假设， 和 都可以表示为 的顶点的凸组合：

因此，

令 为系数， 为对应的顶点，则

且所有 。因此， 可以表示为顶点的凸组合。

终止条件：由于 有界，根据 Carathéodory 定理，任何 可以表示为最多 个顶点的凸组合，其中 是空间的维数。

综上，我们证明了对于任意 ，它可以表示为 的顶点的凸组合。

定理1-2：如果一个线性规划的可行域有界，则最优解必定可以在可行域的顶点上取得。

证明：
利用反证法，假设最优解 不可在可行域顶点处取得，记最优值为 ，根据引理1-1， 可以被顶点的凸组合表示，则有

代入最优值中：

于是矛盾产生，故线性规划的最优值点至少可以在某个顶点处取得。

引理1-2：线性规划的可行解 X 是基可行解的充要条件是： X 的非零分量对应的系数列向量线性独立。

证明：

• 必要性：由基可行解的定义可知。
• 充分性：设 的非零分量对应的系数列向量线性独立，记这些列向量组成的矩阵为 ，则 是满秩矩阵，且 的非零分量个数不超过 个，故 是基可行解。

定理1-3：线性规划问题的基可行解刚好对应于可行域的顶点。

证明：
该命题等价于其逆否命题：如果 不是基可行解的充要条件是 不是可行域的顶点。

• 必要性：设 不是基可行解，则 的非零分量对应的系数列向量线性相关，记这些列向量组成的矩阵为 ，则 不是满秩矩阵，且 的非零分量个数多于 个，故 不是可行域的顶点。
• 充分性：设 不是可行域的顶点，则 可以表示为可行域中两个不同点的凸组合，即存在 和 ，使得

则有

设 的非零分量个数为 ，则 和 的非零分量个数均不超过 个，且 ，故 和 的非零分量对应的系数列向量线性相关，记这些列向量组成的矩阵为 ，则 不是满秩矩阵，且 ，故 不是基可行解。

综上，线性规划问题的基可行解刚好对应于可行域的顶点。

单纯形法的原理

单纯形法的基本思想是从一个基可行解出发，沿着可行域的边界移动到另一个基可行解，直到找到最优解为止。具体步骤如下：

1. 选择一个初始基可行解。
2. 计算当前基可行解的目标函数值。
3. 检查是否存在一个非基变量，其目标函数系数大于零
   • 如果不存在，则当前基可行解即为最优解，算法终止。
   • 如果存在，选择一个非基变量进入基。
4. 计算允许进入基的变量的最大增量，确定一个基变量离开基。
5. 更新基可行解，返回步骤2。
   通过不断迭代上述步骤，单纯形法能够有效地找到线性规划问题的最优解。

以下给出单纯形法的矩阵形式：

对于一个线性规划问题的标准型：

• 设 ，其中 是基矩阵， 是非基矩阵。
• 设 ，其中 是基变量， 是非基变量。
• 设 ，其中 是基变量的目标函数系数， 是非基变量的目标函数系数。
• 基可行解的计算：

• 目标函数值的计算：

• 检查非基变量的目标函数系数：

• 选择进入基的变量：选择一个使得 的非基变量。
• 计算允许进入基的变量的最大增量：

• 更新基可行解：

其中 是允许进入基的变量的最大增量。

为确保 保持非负，选择 满足：

通过上述矩阵形式的单纯形法步骤，可以系统地求解线性规划问题，确保在每一步迭代中都沿着可行域的边界前进，最终找到最优解。

定理1-4: 对可行基解，若所有非基变量的检验数均小于等于零，则该基可行解即为最优解。

证明：
根据以上单纯形法的原理，设当前基可行解为 ，其目标函数值为 。若所有非基变量的检验数均小于等于零，即：

则表示没有非基变量可以进入基以提高目标函数值。因此，当前基可行解 已经是最优解。

定理1-5: 如果某个非基变量的检验系数大于0，但其对应系数列向量所有元素非正，则该线性规划无有界最优解。

证明：
设某个非基变量 的检验系数大于0，即：

且其对应的系数列向量 的所有元素均非正，即：

考虑将 增加一个正数 ，则基变量 的变化为：

由于 ，则 ，即基变量 不会变为负数。因此，可以无限制地增加 ，使得目标函数值：

无限增大，导致线性规划无有界最优解。

定理1-6: 经过换基迭代后得到的新解是一个可行解，且新解的目标函数值不小于旧解的目标函数值。

证明：
设当前基可行解为 ，其目标函数值为 。选择一个非基变量 进入基，基变量 中的某个变量 离开基。设允许进入基的变量的最大增量为 ，则新的基可行解为：

其中 。
由于 的选择确保 ，因此新的解 是一个可行解。新的目标函数值为：

由于 ，则有：

综上，经过换基迭代后得到的新解是一个可行解，且新解的目标函数值不小于旧解的目标函数值。

2.对偶问题

以下涉及对偶问题的证明中，我们在一个这样的问题中进行讨论：

• 原问题：
  

• 对偶问题：
  

定理2-1: （对偶问题的对称性）对偶问题的对偶问题是原问题。

证明： 略

定理2-2: （弱对偶性）若X是一个原问题的可行解，Y是其对偶问题的可行解，则有C X ≤ b Y。

证明：

由于 是原问题的可行解，则有：

得证。

定理2-3: （最优性） 若X和Y分别是原问题和对偶问题的可行解，且C X = b Y，则X和Y分别是原问题和对偶问题的最优解。

证明：
设 分别是原问题和对偶问题的可行解，且 。根据定理1-8，有：

由于 ，则 和 分别是取到了目标值的上下界，是原问题和对偶问题的最优解。

定理2-4: （互补松弛性）X和Y分别是原问题和对偶问题的可行解，则X和Y分别是原问题和对偶问题的最优解的充分必要条件是：

证明：

• 必要性：

设 分别是原问题和对偶问题的最优解，则有 。根据定理1-9有：

则有：

即满足互补松弛性条件。

• 充分性：

设 分别是原问题和对偶问题的可行解，且满足互补松弛性条件，则有：

则有：

根据定理1-9，有 分别是原问题和对偶问题的最优解。

定理2-5: （最优对偶定理）如果原问题有最优基B，则对偶问题的最优解存在，且对偶问题的一个最优解为Y = C_B B^(-1)。

证明：
设 是原问题的一个最优基可行解，基变量为 ，非基变量为 。则有：

其目标函数值为：

设 ，则有：

且 ，因此 是对偶问题的一个可行解。其目标函数值为：

根据定理1-9， 是对偶问题的最优解。

3.整数规划

整数规划问题是指在优化问题中，某些或所有决策变量被要求取整数值的线性规划问题。整数规划问题可以分为以下几类：

1. 纯整数规划（Pure Integer Programming）：所有决策变量都必须取整数值。
2. 混合整数规划（Mixed Integer Programming）：只有部分决策变量必须取整数值，其他变量可以是连续的。
3. 二进制整数规划（Binary Integer Programming）：所有决策变量只能取0或1的整数值。

分支定界法

分支定界法是一种用于求解整数规划问题的算法。其基本思想是通过系统地分割问题的可行域（分支）并计算每个子问题的界限（定界），以逐步缩小搜索空间，最终找到最优整数解。
分支定界法的主要步骤如下：

1. 初始化：从原始整数规划问题开始，计算其线性松弛解（即忽略整数约束），得到一个初始解和目标函数值。
2. 分支：如果当前解不是整数解，则选择一个非整数变量进行分支，创建两个子问题：一个子问题将该变量向下取整，另一个子问题将该变量向上取整。
3. 定界：对于每个子问题，计算其线性松弛解的目标函数值。如果该值小于当前已知的最优整数解，则该子问题可以被舍弃（剪枝）。否则，将该子问题加入待处理队列。
4. 迭代：重复步骤2和3，直到所有子问题都被处理或舍弃。
5. 终止：当没有更多子问题需要处理时，当前已知的最优整数解即为原始整数规划问题的最优解。

割平面法的原理

割平面法是一种用于求解整数规划问题的算法。其基本思想是通过添加额外的线性约束（割平面）来逐步缩小线性松弛解的可行域，从而逼近整数解。割平面法的主要步骤如下：

1. 初始化：从原始整数规划问题开始，计算其线性松弛解，得到一个初始解和目标函数值。
2. 检查整数性：如果当前解是整数解，则该解即为最优解，算法终止。
3. 生成割平面：如果当前解不是整数解，则根据当前解生成一个割平面。割平面是一个新的线性约束，它将当前非整数解排除在可行域之外，同时不排除任何整数解。
4. 更新问题：将生成的割平面添加到原始问题中，形成一个新的线性规划问题。
5. 迭代：计算新的线性规划问题的解，返回步骤2，直到找到整数解或无法生成新的割平面。

定理3-1: （割平面定理）对于一个整数规划问题，如果其线性松弛解不是整数解，则存在一个割平面，可以将该非整数解排除在可行域之外，同时不排除任何整数解。

证明：
设原始整数规划问题为：

设其线性松弛解为 ，且 不是整数解。

则最终单纯形表中存在一个等式：

其中 和 是常数。

现在考虑整数约束，则 为整数解，将上式中的 和 分别取整数部分和小数部分，记为 和 ， 和 ，则有：

将整数部分和小数部分分开，得到：

其中 是整数， 和 也是整数，因此右边的结果是一个整数。
由于 和 都在 范围内，左边的结果必须小于1。考虑到整数约束，左边的结果只能取小于等于0，即：

因为对于所有整数解，（1）式都成立，而对于非整数解 ，由于 ，则有：

因此，式（1）构成了一个割平面，将非整数解 排除在可行域之外，同时不排除任何整数解。

得证。

4. 图论

定理4-1: 图G中， 所有顶点的度数之和等于图中边数的两倍。

证明：
设图 有 个顶点和 条边。每条边连接两个顶点，因此每条边贡献2个度数。设顶点 的度数为 ，则有：

因此，图 中所有顶点的度数之和等于图中边数的两倍。

定理4-2: 图G中，奇度数顶点的个数为偶数。

证明：
设图 有 个顶点和 条边。根据定理3-1，所有顶点的度数之和为 ，这是一个偶数。

设奇度数顶点的个数为 ，偶度数顶点的个数为 。则有：

其中， 是奇数个奇数的和，因此是奇数； 是偶数个偶数的和，因此是偶数。

因此，奇数个奇数的和加上偶数个偶数的和必须是偶数，这意味着 必须是偶数。

定理4-3: 图G是一个树，G的点数大于等于2, 则G至少有两个度数为1的顶点（悬挂点）。

证明：

设图 是一棵树，具有 个顶点和 条边。设图中存在一条最长的链 ，其端点为 和 。由于 是最长链， 和 不能有其他相邻顶点，否则可以通过这些相邻顶点延长链 ，这与 是最长链的假设矛盾。因此， 和 的度数均为1。

定理4-4: 图G是一个树的充要条件是G不含有回路，且G的边数等于顶点数减1。

树的定义：若图G是一个连通图，且不含有回路，则称G为一棵树。

证明：

• 必要性：

使用数学归纳法证明。对于 ，图 只有一个顶点和零条边，满足条件。假设对于 的情况成立，即一棵有 个顶点的树有 条边。现在考虑 的情况。

根据定理3-3, 图 至少有两个度为1的点，将其中一个顶点从图中删去，并删除与之相连的边，得到一个新的图 。图 仍然是连通的且不含回路，因此 是有k个点的一棵树。根据归纳假设， 有 个顶点和 条边。即：

所以在删除顶点和一条边之前的原图 有 个顶点和 条边，即 和 ，满足 。

• 充分性：

即证明：如果图 不含有回路，且 ，则 是连通图。

设 是非连通图，则有连通分量 ，且每个连通分量都是不含回路的连通图，即每个连通分量是一个树。

根据定理3-4, 有：

与 相悖，故 是连通图。

定理4-5: 图G是一个树的充要条件是G是连通图，且G的边数等于顶点数减1。

证明：

• 必要性：

根据定理3-4可知。

• 充分性：

即证明 是连通图，且 的边数等于顶点数减1时， 是无环图。

根据点数归纳，若 有环，则边数等于顶点数减1的图非连通，即可证明。

定理4-6: 图G是一个树的充要条件是两点之间恰有一条链。

• 必要性：

因为树的定义知 是连通图，则任意两点之间存在一条链。且由于 无环，故只存在一条链。

• 充分性：

由于任意两点之间可以找到一条链，故 是连通图。由于只有一条链，可知 无环，故 是一个树。

5. 网络流问题

定理5-1: f是可行最大流，当且仅当f中不存在增广链。

增广链的定义：在残留网络中，若存在一条从源点 到汇点 的链，其中每条正向边的剩余容量均大于0，每条反向边的流量均大于0，则称该链为增广链。

证明：

• 必要性：
  设 是可行最大流，若存在增广链 ，则可以通过增大 上的流量来得到一个更大的流量，这与 是最大流矛盾。因此，增广链不存在。

• 充分性：
  设 不是最大流，则存在一个更大的流量 ，则 是一个从 到 的流量，且其值大于0。根据流量守恒条件， 在每个顶点的流入量等于流出量，因此在残留网络中存在一条从 到 的链，即增广链。这与增广链不存在矛盾。

因此， 是可行最大流当且仅当增广链不存在。

定理5-2: （最大流最小割定理）网络中的最大流值等于其最小割的容量。

割的定义：在网络中，若将顶点集 分为两个不相交的子集 和 ，且源点 ，汇点 ，则称边集 为一个割。割的容量定义为从 到 的所有边的容量之和。

证明：

设网络中的最大流为 ，最小割的容量为 。根据定理5-1，若 是最大流，则残留网络中不存在增广链。

设 为在残留网络中从源点 可达的所有顶点的集合， 为其补集。则 是一个割。

由于残留网络中不存在增广链，所有从 到 的边在原网络中都已满流，即这些边的流量等于其容量。因此，割的容量 等于从 到 的所有边的容量之和。

根据流量守恒条件，流量 等于从 到 的所有边的流量之和。因此，有：

因此，网络中的最大流值等于其最小割的容量。

6. 一笔画

定理6-1: 连接多重图G有欧拉圈， 当且仅当G中无奇点。

欧拉圈的定义：在图 中，经过每条边恰好一次且起点和终点相同的闭合路径称为欧拉圈。

证明：

• 必要性：

设图 有欧拉圈，则欧拉圈经过每条边恰好一次。对于每个顶点 ，每次进入 都必须有一次离开 ，因此 的度数必须是偶数。由于图 中的所有顶点都满足这一条件，故图 中无奇点。

• 充分性：

设图 中无奇点，则所有顶点的度数均为偶数。选择任意一个顶点 作为起点，沿着未经过的边进行遍历，直到无法继续为止。由于每个顶点的度数均为偶数，故在遍历过程中，每次进入一个顶点时，都有一条未经过的边可以离开该顶点。因此，最终会回到起点 ，形成一个闭合路径。

定理6-2: 连接多重图G有欧拉链， 当且仅当G中恰有两个奇点。

欧拉链的定义：在图 中，经过每条边恰好一次但起点和终点不同的路径称为欧拉链。

证明：

• 必要性：

设图 有欧拉链，则欧拉链经过每条边恰好一次。对于起点 和终点 ，它们的度数均为奇数，因为起点 进入一次但离开一次，终点 进入一次但离开一次。对于其他顶点 ，每次进入 都必须有一次离开 ，因此 的度数必须是偶数。由于图 中只有两个顶点 和 的度数为奇数，故图 中恰有两个奇点。

• 充分性：

设图 中恰有两个奇点 和 ，则其他顶点的度数均为偶数。选择奇点 作为起点，沿着未经过的边进行遍历，直到无法继续为止。由于每个非奇点的顶点的度数均为偶数，故在遍历过程中，每次进入一个非奇点时，都有一条未经过的边可以离开该顶点。因此，最终会到达另一个奇点 ，形成一条路径。

7. 非线性规划

定理7-1: 设R是一个n维空间中的开集，f在R上有连续的偏导数，x*是R中的一点，则f在x*处取得极值的必要条件是：

证明：

设 在 上有连续的偏导数， 是 中的一点，且 在 处取得极值。则存在一个邻域 ，使得对于所有 ，都有：

或

考虑 在 处的泰勒展开式：

其中， 是 在 处的梯度向量， 表示高阶无穷小。

由于 在 处取得极值， 必须为零，否则可以通过选择适当的 使得 大于或小于 ，这与 在 处取得极值矛盾。

得证。

定理17-2: 设R是一个n维空间中的开集，f在R上有连续的二阶偏导数，x*是R中的一点，且：

则f在x*处取得极小值的充分条件是：

其中， 是 在 处的海森矩阵。

证明：
设 在 上有连续的二阶偏导数， 是 中的一点，且 。则 在 处的泰勒展开式为：

其中， 是 在 处的海森矩阵。

由于 是正定矩阵，即对于所有非零向量 ，都有：

因此，对于足够小的 ，有：

这表明 在 处取得极小值。

得证。

---

以上是线性规划、对偶问题、整数规划、图论、网络流问题、一笔画和非线性规划中一些重要定理的陈述及其证明。

希望这些内容对你有所帮助！如果你有任何进一步的问题或需要更详细的解释，请随时告诉我。

如果你喜欢本站，可以收藏网址：https://blog.thanafox.com 或分享给你的朋友们，谢谢支持！