最优化——单纯形法
步骤一：求广义基本可行解
已知一个可逆方阵 B = ( P j ( 1 ) , P j ( 2 ) , ⋯ , P j ( m ) ) B=\left(P_{j(1)}, P_{j(2)}, \cdots, P_{j(m)}\right) B=(Pj(1),Pj(2),⋯,Pj(m)) 满足
B − 1 b ⃗ ≥ 0 B^{-1} \vec{b} \geq 0 B−1b≥0
其中 1 ≤ j ( i ) ≤ n , ∀ 1 ≤ i ≤ m , 1 \leq j(i) \leq n, \forall 1 \leq i \leq m, 1≤j(i)≤n,∀1≤i≤m, 即 B B B 是线性规划标准型 的可行基阵
由 B B B可以把线性约束(1) P 1 x 1 + P 2 x 2 + ⋯ + P n x n = b ⃗ P_{1} x_{1}+P_{2} x_{2}+\cdots+P_{n} x_{n}=\vec{b} P1x1+P2x2+⋯+Pnxn=b改写为
⇔ ( P j ( 1 ) , ⋯ , P j ( m ) ) ( x j ( 1 ) ⋮ x j ( m ) ) + P j ( m + 1 ) x j ( m + 1 ) + ⋯ + P j ( n ) x j ( n ) = b ⃗ ⇔ ( x j ( 1 ) ⋮ x j ( m ) ) + ( B − 1 P j ( m + 1 ) ) x j ( m + 1 ) + ⋯ + ( B − 1 P j ( n ) ) x j ( n ) = B − 1 b ⃗ \begin{array}{l} \Leftrightarrow\left(P_{j(1)}, \cdots, P_{j(m)}\right)\left(\begin{array}{c} x_{j(1)} \\ \vdots \\ x_{j(m)} \end{array}\right)+P_{j(m+1)} x_{j(m+1)}+\cdots+P_{j(n)} x_{j(n)}=\vec{b} \\ \Leftrightarrow \quad\left(\begin{array}{c} x_{j(1)} \\ \vdots \\ x_{j(m)} \end{array}\right)+\left(B^{-1} P_{j(m+1)}\right) x_{j(m+1)}+\cdots+\left(B^{-1} P_{j(n)}\right) x_{j(n)}=B^{-1} \vec{b} \end{array} ⇔(Pj(1),⋯,Pj(m))⎝⎜⎛xj(1)⋮xj(m)⎠⎟⎞+Pj(m+1)xj(m+1)+⋯+Pj(n)xj(n)=b⇔⎝⎜⎛xj(1)⋮xj(m)⎠⎟⎞+(B−1Pj(m+1))xj(m+1)+⋯+(B−1Pj(n))xj(n)=B−1b
可以得到一个基本可行解 X = ( x 1 . . . x n ) T X=(x_1…x_n)^T X=(x1...xn)T的表达式：
X B = ( x j ( 1 ) ⋮ x j ( m ) ) , ( x j ( m + 1 ) . . . x j ( n ) ) = 0 X_{B}=\left(\begin{array}{c}x_{j(1)} \\ \vdots \\ x_{j(m)}\end{array}\right),(x_{j(m+1)}…x_{j(n)})=0 XB=⎝⎜⎛xj(1)⋮xj(m)⎠⎟⎞,(xj(m+1)...xj(n))=0
步骤二：求检验数
记 C B = ( c j ( 1 ) , ⋯ , c j ( m ) ) T , C_{B}=\left(c_{j(1)}, \cdots, c_{j(m)}\right)^{T}, CB=(cj(1),⋯,cj(m))T,
用 C B C_{B} CB左乘(3) 得 C B T X B + C B T P ^ j ( m + 1 ) x j ( m + 1 ) + ⋯ + C B T P ^ j ( n ) x j ( n ) = C B T P ^ n + 1 − − − ( 4 ) C_{B}^{T} X_{B}+C_{B}^{T} \hat{P}_{j(m+1)} x_{j(m+1)}+\cdots+C_{B}^{T} \hat{P}_{j(n)} x_{j(n)}=C_{B}^{T} \hat{P}_{n+1}—(4) CBTXB+CBTP^j(m+1)xj(m+1)+⋯+CBTP^j(n)xj(n)=CBTP^n+1−−−(4)
目标函数(2)用 C B C_{B} CB可以写成： C B T X B + c j ( m + 1 ) x j ( m + 1 ) + ⋯ + c j ( n ) x j ( n ) = z − − − ( 5 ) C_{B}^{T} X_{B}+c_{j(m+1)} x_{j(m+1)}+\cdots+c_{j(n)} x_{j(n)}=z—(5) CBTXB+cj(m+1)xj(m+1)+⋯+cj(n)xj(n)=z−−−(5)
步骤三：得到单纯形表
其中 ( P ^ j ( 1 ) , ⋯ , P ^ j ( m ) ) = I m , z ^ = C B T P ^ n + 1 = C B T B − 1 b ⃗ \left(\hat{P}_{j(1)}, \cdots, \hat{P}_{j(m)}\right)=I_{m}, \hat{z}=C_{B}^{T} \hat{P}_{n+1}=C_{B}^{T} B^{-1} \vec{b} (P^j(1),⋯,P^j(m))=Im,z^=CBTP^n+1=CBTB−1b
σ j = c j − C B T P ^ j = c j − C B T B − 1 P j , ∀ 1 ≤ j ≤ n \sigma_{j}=c_{j}-C_{B}^{T} \hat{P}_{j}=c_{j}-C_{B}^{T} B^{-1} P_{j}, \quad \forall 1 \leq j \leq n σj=cj−CBTP^j=cj−CBTB−1Pj,∀1≤j≤n
称 σ 1 , ⋯ , σ n \sigma_{1}, \cdots, \sigma_{n} σ1,⋯,σn 为检验数，可看出基变量检验数等于0
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/232442.html原文链接：https://javaforall.net
