这貌似是运筹学的一个比较有趣的问题类型
不过介于我水平太低（只会背背板子）
在此记录

单纯形法

一般oi中遇到的线性规划问题都长这样

比如某一些网络流问题，以及二分图最大权匹配啥的，结合对偶定理，可以有很多很强的结论

以及一个最小费用流的线性规划式子

现在考虑怎么做这类问题

不妨先引入一个基变量（松弛变量）

比如说现在的系数矩阵是
比如说现在的系数矩阵是

\[\left\{ \begin{matrix} x_{11} & x_{12} & x_{13} & x_{14} & ... &x_{1n + 1}\\ x_{21} & x_{22} & x_{23} & x_{24} & ... &x_{2n + 1}\\ x_{31} & x_{32} & x_{33} & x_{34} & ... &x_{3n + 1}\\ x_{41} & x_{42} & x_{43} & x_{44} & ... &x_{4n + 1}\\ . ..\\ x_{m1} & x_{m2} & x_{m3} & x_{m4} & ... &x_{mn + 1}\\ \end{matrix} \right\}\\ 对于第i行\\ x_{i,n+1} = b_i - \sum_{j = 1}^nx_{i , j} * a_{i , j}\\ 不妨将第x_{i , k}表示出来\\ x_{i , k} = \frac{x_{i , n + 1} + \sum_{j\ !=\ k}x_{i , j} * a_{i , j} - b_i}{-a_{i , k}}\\ 给你要最大化的式子带来的价值是\\ \frac{x_{i , n + 1} + \sum_{j\ !=\ k}x_{i , j} * a_{i , j} - b_i}{-a_{i , k}} * val_k\\ \]

这样可以吧\(x_{i , n + 1}\)的值给去\(x_{i , k}\),这样的操作叫做转轴

之后就可以用这个过程来时目标函数有最大值

有一个例题吧

很容易列出线性规划式子

\[\left\{ \begin{matrix} max:c_1 * x_1 + c_2 * x_2 + ... + c_n *x_n\\ a_{11} * x_1 + a_{12} * x_2 + ... + a_{1n} * x_n <= b_1\\ .\\ .\\ a_{m1} * x_1 + a_{m2} * x_2 + ... + a_{mn} * x_n <= b_m\\ \end{matrix} \right. \]

就是一个板子题

#include<bits/stdc++.h>
#define MAXN 500
#define eps 1e-7
typedef double ll;
const ll inf  = 1e18;
using namespace std;

int n,m;
ll a[MAXN][MAXN];
int id[MAXN];

void out(){
	for(int i = 1 ; i <= n ; i++)printf("%.2f " , a[0][i]);
	puts("");
	for(int i = 1 ; i <= m ; i++){
		for(int j = 1 ; j <= n ; j++){
			printf("%.2f " , a[i][j]);
		}
		printf("%.2f " , a[i][0]);
		puts("");
	}
}

void plot(int x , int y){
	swap(id[x + n] , id[y]);
	double t = a[x][y];	a[x][y] = 1;
	for(int j = 0 ; j <= n ; j++)a[x][j] /= t;
	for(int i = 0 ; i <= m ; i++){
		if(i == x || a[i][y] < eps)continue;
		t = a[i][y] , a[i][y] = 0;
		for(int j = 0 ; j <= n ; j++)a[i][j] -= a[x][j] * t;
	}
}

bool simplex(){
	for(int i = 1 ; i <= n ; i++)id[i] = i;
	int x = 0, y = 0;
	int cnt = 0;
	ll minl;
	while(1){
		x = y = 0 , minl = inf;
		cnt++;
		for(int i = 1 ; i <= n ; i++)if(a[0][i] > eps){x = i;break;}
		if(!x)break;
		for(int i = 1 ; i <= m ; i++)if(a[i][x] > eps && minl > a[i][0] / a[i][x])minl = a[i][0] / a[i][x] , y = i;
		if(!y) {puts("Unbounded"); return false;}
		plot(y , x);
	}
	return true;
}

int main(){
	while(scanf("%d%d",&n,&m) == 2){
		memset(a , 0 ,sizeof(a));
		for(int i = 1 ; i <= n ; i++)cin>>a[0][i];
		for(int i = 1 ; i <= m ; i++){
			for(int j = 1 ; j <= n ; j++)cin>>a[i][j];
			cin>>a[i][0];
		}
		simplex();
		printf("Nasa can spend %d taka.\n",(int)ceil(-a[0][0]*m));	
	}
}

---

对偶定理

很容易写出线性规划的模型，及其对偶
其系数矩阵为原系数矩阵的转置

原问题有*解等价于对偶问题无可行解

但是对偶问题无可行解时，原问题可能为*解或者无可行解

剩下的很多扩展内容可以看这个
https://www.cnblogs.com/TianyiQ/p/linear-programming.html