线性规划学习笔记

线性规划综述


一般线性规划

在一般线性规划问题中,我们希望优化一个满足一组线性不等式约束的线性函数。已知一组实数$a_1,a_2,\cdots,a_n$和一组变量$x_1,x_2,\cdots,x_n$。我们定义在这些变量上的一个线性函数 $f$:

不等式 线性不等式

栗子

下面我们举一个具体的栗子🌰。
 考虑具有两个变量的线性规划:
 最大化

 满足约束

我们称所有满足约束式的变量$x_1$和$x_2$的取值为一个线性规划的一个可行解。这些可行解在二维空间中构成一个凸区域。这个凸型区域称为可行区域,希望最大化的函数称为目标函数

单纯型算法

学过中学线性规划的同学都知道:

  1. 线性规划的最优解是在可行区域的一个顶点上。
  2. 如果一个顶点所代表的值比与他相邻的所有顶点的值优,该顶点即为最优解。【局部最优即为全局最优】

这样的结论在超过两个变量的线性规划中也成立。单纯性算法就是一个一直沿着单纯型的一条边从当前顶点移动到一个目标值不小于当前顶点的相邻顶点的算法。

标准型


松弛型


代码


模板题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class LinearProgramming {
public:
LinearProgramming(int n, int m) : n_(n), m_(m) {
int k;
for (int i = 1; i <= n; ++i) {k = read(); a_[0][i] = k;}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {k = read(); a_[i][j] = k;}
k = read(); a_[i][0] = k;
}
}
void simplex() {
for (int i = 1; i <= n_; ++i) nonbasic_vars_[i] = i;
for (int i = 1; i <= m_; ++i) basic_vars_[i] = i+n_;
int x, y;
while (1) {
x = y = 0;
for (int i = 1; i <= m_; ++i)
if (a_[i][0] < -kEps) {y = i; break;}
if (!y) break;
for (int i = 1; i <= n_; ++i)
if (a_[y][i] < -kEps) {x = i; if (rand()%3 == 0) break;}
if (!x) {puts("Infeasible"); return;}
pivot(x, y);
}
while (1) {
x = 0; for (int i = 1; i <= n_; ++i) if (a_[0][i] > kEps) {x = i; break;}
if (!x) break;
double k = kInf;
for (int i = 1; i <= m_; ++i)
if (a_[i][x] > kEps && a_[i][0]/a_[i][x] < k) {
y = i; k = a_[i][0]/a_[i][x];
}
if (k == kInf) {puts("Unbounded"); return;}
pivot(x, y);
}
printf("%.8lf\n", -a_[0][0]);
if (!type) return;
for (int i = 1; i <= n_; ++i) a_[0][i] = 0;
for (int i = 1; i <= m_; ++i)
if (basic_vars_[i] <= n_)
a_[0][basic_vars_[i]] = a_[i][0];
for (int i = 1; i <= n_; ++i) printf("%.8lf ", a_[0][i]);
}
private:
int n_, m_, basic_vars_[kM], nonbasic_vars_[kN];
double a_[kM][kN];
void pivot(int x, int y) {
for (int i = 0; i <= n_; ++i)
if (i != x) a_[y][i] /= a_[y][x];
a_[y][x] = 1/a_[y][x];
for (int i = 0; i <= m_; ++i) {
if (i == y) continue;
for (int j = 0; j <= n_; ++j)
if (j != x) a_[i][j] -= a_[i][x]*a_[y][j];
a_[i][x] *= -a_[y][x];
}
std::swap(nonbasic_vars_[x], basic_vars_[y]);
}
};

版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 许可协议。转载请注明出处!

~感谢投食~