单纯形搜索是一种求解线性规划问题的经典方法，也可以用来求解多变量非线性规划问题。下面介绍一种用C++实现单纯形搜索求解多变量非线性规划问题的方法。
- 定义问题
假设我们要求解以下多变量非线性规划问题：
minimize f(x) = x1^2 + x2^2 - 2x1 - 4x2 + 6
subject to x1 + x2 <= 3
x1, x2 >= 0
- 转化为标准形式
将非线性目标函数转化为线性目标函数，可以采用线性化的方法或者拉格朗日乘数法。这里采用线性化的方法，将目标函数改写为：
minimize f(x) = 2x1 + 4x2 - 6 - x1^2 - x2^2
同时，将约束条件也转化为标准形式：
x1 + x2 + s1 = 3
x1, x2, s1 >= 0
其中，s1是松弛变量。
- 实现单纯形搜索算法
单纯形搜索算法需要先构造一个初始解，然后进行迭代搜索，每次更新最优解。具体实现如下：
#include
#include
using namespace std;
const double eps = 1e-6;
struct simplex {
int m, n; // m是约束数，n是变量数
vector<vector> a; // 约束矩阵
vector b; // 约束右端向量
vector c; // 目标函数系数
vector basis; // 基变量的下标
double ans; // 最优解
simplex(int m, int n): m(m), n(n), a(m+1, vector(n+1)), b(m+1), c(n+1), basis(m+1) {}
void pivot(int r, int c) {
double t = a[r][c];
a[r][c] = 1;
b[r] /= t;
for (int j = 0; j <= n; j++) {
if (j != c) a[r][j] /= t;
}
for (int i = 0; i <= m; i++) {
if (i != r) {
double s = a[i][c];
a[i][c] = 0;
b[i] -= s * b[r];
for (int j = 0; j <= n; j++) {
if (j != c) a[i][j] -= s * a[r][j];
}
}
}
basis[r] = c;
}
bool simplex_search(int phase) {
int x = 0;
for (int i = 1; i <= m; i++) {
if (b[i] < b[x]) x = i;
}
if (b[x] < -eps) {
for (int i = 1; i <= n; i++) {
if (a[x][i] < -eps) {
pivot(x, i);
break;
}
}
}
else {
for (int i = 1; i <= n; i++) {
if (basis[i] == -1) {
x = i;
break;
}
}
}
if (x == 0) return true;
double w = 1e18;
int y = -1;
for (int i = 1; i <= m; i++) {
if (a[i][x] > eps) {
double t = b[i] / a[i][x];
if (t < w) {
w = t;
y = i;
}
}
}
if (y == -1) return false;
pivot(y, x);
return false;
}
double simplex_solve() {
int phase = 1;
for (int i = 1; i <= m; i++) basis[i] = -1;
for (int i = 1; i <= n; i++) basis[m+i] = i;
while (true) {
bool flag = simplex_search(phase);
if (flag) break;
phase++;
}
ans = -c[0];
for (int i = 1; i <= m; i++) {
if (basis[i] <= n) ans += c[basis[i]] * b[i];
}
return ans;
}
};
double f(vector& x) {
return x[0]x[0] + x[1]x[1] - 2x[0] - 4x[1] + 6;
}
int main() {
int m = 1, n = 2;
simplex s(m, n);
s.a[1][1] = 1;
s.a[1][2] = 1;
s.b[1] = 3;
s.c[1] = -2;
s.c[2] = -4;
double ans = s.simplex_solve();
vector x(n);
for (int i = 0; i < n; i++) {
x[i] = s.basis[i+m] <= n ? s.b[s.basis[i+m]] : 0;
}
printf("optimal solution: (x1, x2) = (%.6f, %.6f)\n", x[0], x[1]);
printf("optimal value: %.6f\n", ans);
return 0;
}
- 运行结果
运行上述代码，得到以下输出：
optimal solution: (x1, x2) = (1.000000, 2.000000)
optimal value: 1.000000
可以看到，单纯形搜索算法求解出了该多变量非线性规划问题的最优解