线性规划整理
线性规划
by AmanoKumiko
1.两种形式
? (1)
\[min\ z=\sum c_ix_i \]\[\sum a_{i,j}x_j\ge b_i \]\[x_i\ge 0 \]? (2)
\[max\ z=\sum y_ib_i \]\[\sum a_{i,j}y_i\le c_j \]\[y_i\ge 0 \]根据对偶原理等价
2.单纯形法
形如
\[max\ z=\sum c_ix_i \]\[x_{n+i}=b_i-\sum a_{i,j}x_j \]\[x_i\ge 0 \]? (1)对于存在\(b_l\)为负的，找到任意一个\(a_{l,e}\)为负的进行\(pivot\)操作，若不存在则无解
? (2)找到一个\(e\)使得\(c_e>0\)，若不存在则退出
? (3)找到满足\(a_{l,e}>0\)的最小的\(\frac{b_l}{a_{l,e}}\)，若不存在则答案为无穷大
? (4)对\(l,e\)进行\(pivot\)操作
3.Trick
? (1)与连通性相关的网络流题一般无法直接上线性规划
? (2)选某个变量的前提条件是另一个变量被选可用不等式表示