I. 什么是激活/绑定(active/binding)
考虑一个多面体 P ⊂ ℜ n P\subset \Re^n P⊂ℜn由以下约束定义：
a ′ i x ≥ b i , i ∈ M 1 a ′ i x ≤ b i , i ∈ M 2 a ′ i x = b i , i ∈ M 3 \pmb{a'}_i\pmb{x}\geq b_i,i\in M_1\\ \pmb{a'}_i\pmb{x}\leq b_i,i\in M_2\\ \pmb{a'}_i\pmb{x}=b_i, i\in M_3 a′ix≥bi,i∈M1a′ix≤bi,i∈M2a′ix=bi,i∈M3
其中， M 1 , M 2 , M 3 M_1,M_2,M_3 M1,M2,M3是有限下标集，每一个 a i ∈ ℜ n \pmb{a}_i\in\Re^n ai∈ℜn是一个向量， b i b_i bi是标量
【定义2.8】：如果 M 1 , M 2 , M 3 M_1,M_2,M_3 M1,M2,M3中某些下标 i i i同时满足 a ′ i x ∗ = b i \pmb{a'}_i\pmb{x^*}=b_i a′ix∗=bi，则称对应约束在 x ∗ \pmb{x^*} x∗处激活/绑定。
II. 什么是基本解(basic solution)
【定义2.9】：一个向量 x ∗ \pmb{x^*} x∗如果是基本解，则需满足：
（a）满足所有等式约束都激活
（b）在 x ∗ \pmb{x^*} x∗处激活的约束条件中，有 n n n 个约束条件是线性独立的
【例1】：
III. 退化(degeneracy)
【定义2.10】：如果在一个基本解 x ∈ ℜ n \pmb{x}\in\Re^n x∈ℜn处激活的约束超过 n n n个，则称 x \pmb{x} x为一个退化的基本解。
【例2】：考虑以下多面体
P
P
P
向量
x
=
(
2
,
6
,
0
)
\pmb{x}=(2,6,0)
x=(2,6,0)是一个非退化基本可行解，因为此处有三个激活且线性独立的约束：
x
1
+
x
2
+
2
x
3
≤
8
,
x
2
≤
6
x_1+x_2+2x_3\leq8,x_2\leq6
x1+x2+2x3≤8,x2≤6和
x
3
≥
0
x_3\geq0
x3≥0。而向量
x
=
(
4
,
0
,
2
)
\pmb{x}=(4,0,2)
x=(4,0,2)则是一个退化的基本可行解，因为此处有四个激活的约束，其中三个线性独立，分别是：
x
1
+
x
2
+
2
x
3
≤
8
,
x
2
+
6
x
3
≤
12
,
x
1
≤
4
x_1+x_2+2x_3\leq8,x_2+6x_3\leq12,x_1\leq4
x1+x2+2x3≤8,x2+6x3≤12,x1≤4和
x
2
≥
0
x_2\geq0
x2≥0。
IV. 标准型中的退化
在标准型多面体的基本解中， m m m个相等约束条件总是有效的。因此，如果有超过 n n n个激活的约束条件，这表明有超过 n − m n-m n−m个变量值为零。这就引出了标准型中退化的定义：
【定义2.11】：考虑一个标准型多面体 P = { x ∈ ℜ n ∣ A x = b , x ≥ 0 } P=\{\pmb{x}\in\Re^n|\pmb{Ax}=\pmb{b},\pmb{x}\geq\pmb{0}\} P={x∈ℜn∣Ax=b,x≥0}，设 x \pmb{x} x是一个基本解， m m m是 A \pmb{A} A的行数。如果基本解 x \pmb{x} x中有超过 n − m n-m n−m项等于0，则称 x \pmb{x} x是退化的。
我们可以从以下角度来考虑退化问题：我们选取一个基本解，选取 n n n个线性独立的约束条件，使其满足相等条件，然后我们会发现某些其他约束条件也满足相等条件。
在非退化基本解中，正好有 n − m n-m n−m个约束条件 x i > 0 \pmb{x}_i>0 xi>0是激活的，其对应的变量为非基变量。而在退化基本解的情况下，超过 n − m n-m n−m个约束 x i > 0 \pmb{x}_i>0 xi>0是激活的，这导致选择非基变量的选择有多种组合。在这种情况下，就会有同一个基本解对应多个基的情况。(本文讨论的是典型情况。不过，也有一些退化基本解的例子，它们只对应一个基。)
V. 单纯形法中处理退化问题——Bland’s rule
Bland法则
- 每一次循环，选择所有 c ˉ j < 0 \bar{c}_j<0 cˉj<0中 j j j最小的项作为新的入基变量。
- 在计算 θ ∗ \theta^* θ∗时，如果出现相同的比例，选择下标最小的变量出基：
i ∗ = arg min i ∈ B : v i , j > 0 x i / A i , j i^*=\arg \min_{i\in B:v_{i,j}>0}x_i/A_{i,j} i∗=argi∈B:vi,j>0minxi/Ai,j
标签：约束条件,基本,线性规划,bi,退化,pmb,激活,Degeneracy From： https://blog.csdn.net/m0_54713489/article/details/142027000