线性规划 单纯形 Linear Programming, Simplex Algorithm
线性规划就是给一堆变量的限制,然后求目标函数的最大值。
标准形式就是:
给定A[n][m], C[n], B[m]
Max ∑C[i]X[i]
并且 ∑A[j][i]X[i] ≤ B[j] , X[i]>=0
所有的线性规划都可以转换为标准形式。通过两边乘以负一,一个变量变成两个,一条式子变成两条。
解决线性规划的一个经典非多项式算法就是单纯形算法(Simplex Algorithm),那么单纯形是究竟是神马东西来的呢? 其实单纯形就是一个简单的图形(没有边与边相交的凸的图形)。线性......
阅读全文