Question

线性规划问题 矩阵算法 检验数是怎么求出来的

Answer 1

【图解】换基迭代、检验数，非常直观！

1. 单纯形法基本思想

• 先找一个基可行解（顶点），判断是否为最优解。

• 如果是，那么找到啦，结束。

• 如果不是，则沿着可行域的边缘移动，保证这条边缘的移动方向 让目标函数值不断增大，直至挪到另一个顶点；判断该顶点是否最优解，不是则继续移动，直到找到最优解为止。

简而言之，找基解 → 验证最优性 → 换基迭代。

---

2. 转换到相邻基可行解（即 挪到下一个顶点）

首先，只变换一个基变量，可以得到两个相邻的基可行解（定理），即：

Pj 入基的具体方法：用原来的 m 个基向量，线性表示 Pj，即 Pj = Σ aiPi 。

🟡 为原来的基可行解，🟠 为线性表示 Pj 的系数。直观来说，原来 m 个基向量分别拿出自己的一部分，齐心协力组成了新向量 Pj。

随着它们拿出的分量越来越大，Pj 前面的系数越来越大，原来 m 个基向量的系数越来越小。随着它们不断拿出（绿色 ▲ 不断增大），原来 m 个基向量中的某个向量 Pi 会先耗尽（🟡 - ▲🟠 = 0 ），即 拿出了自己的所有。此时，Pi 出基，Pj 入基。

---

3. 检验数：判断是否最优解

首先，如果该顶点的目标函数 ≥ 两侧相邻顶点的目标函数，则该顶点是最优解（定理）。

我们引入检验数 σ，代表 Pi 出基、Pj 入基后的目标函数增益，计算方法如下：

红色方块为目标函数对决策变量的系数，直观理解为 每多造一个特定产品的收益。

如果该顶点移到两侧相邻顶点的检验数 σ 都 ≤ 0，则该顶点是最优解。

---

如果有帮助，请采纳回答吧~  :）

Answer 2

目标规划是将多目标问题，利用优先因子化成单目标问题，这样在用线性规划单纯形法求解时，将不同优先级对应的目标按优先级分开对待，即检验数按优先级高低来决定换入变量，这样就能保证优先级高的先满足。例子中P1.P2.P3三行检验数，即按优先级高低来寻找负检验数最大。
也可以理解为将检验数按照优先因子分解，保证优先因子高的变量先换入。
标准型求极大时，利用F（x）求，如果是求极小值就利用 - F（x）求，求出的极大值变符号就是极小值了，判断方法还是