七、标准型、基、基解、基可行解、可行基

线性规划问题的标准形式一般情况下，min Z / max Z对于一般的线性规划问题，容易得到：通过恒等变形，将一般形式写为标准形式，从而方便之后的求解（1）目标函数统一为： max Z令求（2）：原问题中当“ < ”,等式两边同时添“负号”当 “ = ”，表示出现了退化（3）...

skycrygg

13841人浏览 · 2021-03-03 16:30:13

skycrygg · 2021-03-03 16:30:13 发布

原视频：https://www.bilibili.com/video/BV194411y7sA?p=7

线性规划问题的标准形式

一般情况下， Z=f(x,y ) min Z / max Z

对于一般的线性规划问题，容易得到：

$Z=f(x_1,x_2,\cdots,x_n)=c_1x_1+c_2x_2+\cdots+c_nx_n(c_i\in R)x_i\in R\\$

$\left \{ \begin {matrix} a_{11}_x_1+a_{12}x_2+\cdots+a_{1n}x_n=(\leq,\geq)b_1\: \:\:\:\:\:\:a_i\in R\\ a_{21}_x_1+a_{22}x_2+\cdots+a_{2n}x_n=(\leq,\geq)b_2\:\:\:\:\:\:b_i\in R\\ \vdots\\ a_{n1}_x_1+a_{n2}x_2+\cdots+a_{nn}x_n=(\leq,\geq)b_n\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: \end {matrix}$

通过恒等变形，将一般形式写为标准形式，从而方便之后的求解

（1）目标函数统一为： max Z $min Z\Rightarrow$ 令 $Z^{'}=-Z$ 求

（2）：原问题中 $b_i\in R(b_i>0)$ $\left \{ \begin{matrix} b_i>0 \\ b_i<0 \\ bi=0 \end{matrix}$

当“ < ”, $\Rightarrow$ 等式两边同时添“负号”

当 “ = ”，表示出现了退化

（3）约束符号 “ $= \:\: \leq \:\:\geq$ ”

“ $\leq$ ” 加入新的变量 → 松弛变量 “ $\leq \:\Rightarrow \:=$ ”

“ $\geq$ ” 减去新的变量 → 剩余变量 “ $\geq \:\Rightarrow \:=$ ”

（4）统一“决策变量 $\geq$ 0” ： $\left \{ \begin{matrix} x_i\geq0 \\ x_i\leq0 \\ x_i=0 \\x_i\in R \end{matrix}$

当 “ = ”，直接写为“ $\geq$ ”

当 “ $\leq$ ” ，令 $x_i^{'} = -x_i,\:\:\:\:x_i^{'}\geq 0$ 带入约束方程

当“ $x_i \in R$ ”, $x_i = x_i^{'} - x_i^{''}$ , $x_i^{'} \geq0,\:\:\:\: x_i^{''}\geq0$

（5）形式上调整目标函数，将新引入的变量写回目标函数中去

线性规划解的讨论

$max Z=c_1x_1+c_2x_2+\cdots+c_nx_n(c_i\in R)x_i\geq0$

$\left \{ \begin {matrix} a_{11}_x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1\: \:\:\:\:\:\:a_i\in R\\ a_{21}_x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2\:\:\:\:\:\:b_i\in R\\ \vdots\\ a_{n1}_x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\\ x_i\geq0, b_i>0 \end {matrix}$

$\begin{bmatrix} a_{11} &a_{12} &\cdots &a_{1n} \\ a_{21}&a_{22} &\cdots &a_{2n} \\ \vdots& &\vdots &\vdots \\ a_{n1}& a_{n2} & \cdots & a_{nn} \end{bmatrix}$ $\begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix} =\begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{bmatrix}$ $max Z = c_1x_1+c_2x_2+\cdotsc_nx_n\\ = [c_1 \:\:\:c_2\:\:\:\cdots\:\:\:c_n] \begin{bmatrix} x_1\\x_2\\ \vdots\\x_n \end{bmatrix}$

$A \:\:\:X \:\:\:=b$ $max \:\:Z\:\:=\:C \:\:X$

将A矩阵的每一列看成一个整体，记做列P，即 $A=(p_1\:\:\:p_2\:\:\cdots \:\:p_n)$

（1）可行解（满足约束方程）

能使 AX=b 成立的所有 $X=(x_1,x_2,\cdots,x_n)^T$ （公式中，X为列向量，因此加转置T）

（2）提出更多的信息

基、基可行解、可行基

$\begin{bmatrix} a_{11} &a_{12} &\cdots &a_{1n} \\ a_{21}&a_{22} &\cdots &a_{2n} \\ \vdots& &\vdots &\vdots \\ a_{m1}& a_{m2} & \cdots & a_{mn} \end{bmatrix}$ （m < n）

假设 R（A）= m，从n列中选出 m列作为基：

$B = \begin{bmatrix} a_{11} \:\:\: \cdots \:\:\:a_{1m}\\ \vdots\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\vdots\\ a_m1\:\:\: \cdots \:\:\:a_{mm} \end{bmatrix} =(p_1,p_2,p_3,\cdots,p_m)$

$(p_1,\cdots,p_n) \begin{pmatrix} x_1\\\vdots\\x_n \end{pmatrix}=\begin{pmatrix} b_1\\\vdots\\b_m \end{pmatrix} \Rigtarrow \:\:\:\:\:\:p_1x_1+p_2x_2+\cdots+ p_nx_n = \begin{pmatrix} b_1\\\vdots\\b_m\end{pmatrix}$

$\Rightarrow \begin{pmatrix} a_{11}\\\vdots\\a_{m1} \end{pmatrix}x_1+ \begin{pmatrix} a_{12}\\\vdots\\a_{m2} \end{pmatrix}x_2+ \cdots+ \begin{pmatrix} a_{1m}\\\vdots\\a_{mm} \end{pmatrix}x_m+ \cdots+ \begin{pmatrix} a_{1n}\\\vdots\\a_{mn} \end{pmatrix}x_n= \begin{pmatrix} b_1\\\vdots\\b_m \end{pmatrix}$

$1\cdots m$ 基向量 $m+1 \cdots n$ 非基向量

$\begin{pmatrix} a_{11} \:\:\: \cdots \:\:\:a_{1m}\\ \vdots\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\vdots\\ a_{m1}\:\:\: \cdots \:\:\:a_{mm} \end{pmatrix} \begin{pmatrix} x_1\\ \vdots\\x_m \end{pmatrix} + \begin{pmatrix} a_{m+1,m+1} \:\:\: \cdots \:\:\:a_{m+1,n}\\ \vdots\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\vdots\\ a_{n,m+1}\:\:\: \cdots \:\:\:a_{n,n} \end{pmatrix} \begin{pmatrix} x_m+1\\ \vdots\\x_n \end{pmatrix} =\begin{pmatrix} b_1\\ \vdots\\b_m \end{pmatrix}$

$\Rightarrow \sum^m_{j=1}P_jx_j\:\:=b\:\:-\:\:\sum^n_{j=m+1}P_jx_j$

当非基向量对应的x取0时，方程组变为：

$\begin{pmatrix} a_{11}\\\vdots\\a_{m1} \end{pmatrix}x_1+ \begin{pmatrix} a_{12}\\\vdots\\a_{m2} \end{pmatrix}x_2+ \cdots+ \begin{pmatrix} a_{1m}\\\vdots\\a_{mm} \end{pmatrix}x_m = \begin{pmatrix} b_1\\\vdots\\b_m \end{pmatrix}$