The Simplex Algorithm
The Simplex Algorithm
声明：
看不懂怎么办？那就别看了。应试而抄的笔记而已，网上有很多教程。
Construct the problem
我们来回忆一下Linear Programming Problems
- Define your decision variables
- write down the objective
- write down the constraints
举个例子
……..
x_1 + 3x_2 + 5x_3 <= 23
……….
Inequalities can be transformed into equations using slack variables
Slack variables so called because they represent the amount of slack between an actual quantity and the maximum possible value of that quantity
也就是这样
x_1 + 3x_2 + 5x_3 + r = 23
r就是slack variables
The Simplex Method
-> Determine if a particular vertex, on the edge of the feasible region, is optimal
-> Decide which adjacent vertex you should move to in order to increase the value of the objective function
Use of Simplex Tableau
Simplex Algorithm is performed by creating matrices or tables, showing the values of each decision variable, each slack variable and the objective function until an optimal solution is found.
跟着例子来吧
Maximise P = 3x + 2y
5x + 7y + r = 70
10x + 3y + s = 60
x, y, r, s >= 0
P = 3x + 2y ==> P - 3x - 2y = 0
首先，我们需要Initial Tableau
| Basic Variable | x | y | r | s | Value | $\theta-Value$ |
|---|---|---|---|---|---|---|
| r | 5 | 7 | 1 | 0 | 70 | 70 / 5 = 14 |
| s | 10 | 3 | 0 | 1 | 60 | 60 / 10 = 6 |
| P | -3 | -2 | 0 | 0 | 0 |
然后， 我们需要计算每一行的$\theta-value$
先找到Pivot column, by looking for the most negative entry， 在例子里，是‘X’这一列
然后$\theta-value = Value - (XColumn)$, 写在表格里了
选取 Pivot 列和 Pivot 行：
- 找 Pivot 列：选取最负的值， 这里是 x 列 (−3)。
- 计算 θ-Value：θ=Value对应的Pivot列值θ=对应的Pivot列值Value。
- 对于 r，θ=70 / 5=14。
- 对于 s，θ=60 / 10=6。
- 找 Pivot 行：最小正 θ-Value 是 6，所以 Pivot 行是 s 这一行，Pivot 元素是 10。
然后，我们将s行每个值都除以Pivot值，也就是
| Basic Variable | x | y | r | s | Value | $\theta-Value$ | Row Operation |
|---|---|---|---|---|---|---|---|
| r | 0 | 5.5 | 2 | -0.5 | 40 | R1 - 5R2 | |
| x | 10/10=1 | 3/10=0.3 | 0 | 1/10=0.1 | 60/10=6 | R2 / 10 | |
| P | 0 | -1.1 | 0 | 0.3 | 18 | R3 + 3R2 |
要让Pivot列的值都变成0, 我们要进行一些操作。
第一行，R1 - 5R2 = 0; 第三行，R3 + 3R2 = 0
写进表格里
重复以上步骤，直到objective row里没有负数
| Basic Variable | x | y | r | s | Value |
|---|---|---|---|---|---|
| x | 0 | 1 | 2/11 | -1/11 | 80/11 |
| y | 1 | 0 | -3/55 | 7/55 | 42/11 |
| P | 0 | 0 | 0.2 | 0.2 | 26 |
这下我们知道了，Max P = 26, x = 80/11, y = 42/11, r = 0, s = 0
大功告成
Minimising
刚刚的例子里，给的是Maximise P
那么， 如何Minimise呢？我们需要定义一个新的Objective Function, that is the negative of the original objective function
举个例子
Minimise P = 3x + 2y
那么 Maximise就是
Maximise P = -3x - 2y
Integer Results
如果题目要求x, y, z得是整数，那么该怎么办呢？
举个栗子
Max P = 10x + 12y + 8z
subject to:
2x + 2y <= 5
5x + 3y + 4z <= 15
x, y, z >= 0
我们先得到答案，P= 45, x = 0, y = 2.5, z = 1.875
怎么找到整数解呢？
| Point | 2x + 2y <= 5 | 5x + 3y + 4z <= 15 | In feasible region? | P = 10 x + 12y + 8z |
|---|---|---|---|---|
| (0, 2, 1) | 0 + 4 < 5 | 0 + 6 + 4 < 15 | Yes | 32 |
| (0, 2, 2) | 0 + 4 < 5 | 0 + 6 + 8 < 15 | Yes | 40 |
| (0, 3, 1) | 0 + 6 > 5 | No | ||
| (0,. 3, 2) | 0 + 6 > 5 | No |
所以答案是P = 40, x = 0, y = 2, z = 2
Two-stage simplex method
当他的constraint是>= 或者 = 的时候， 没有明显的initial basic feasible solution.
那怎么办呢?
x + 3y >= 10
这个时候，我们需要个surplus variable, 变成x + 3y - s = 10
s就是超出右边值的“剩余量”，所以我们减去他
但是，x = 0, y = 0, 会得到s = -4， 违反s >= 0
这个时候我们需要一个人工变量a1, 构造新的等式
x + y - s + a1 = 4
通过设定a1 >= 0, 我们能得到x = 0, y = 0, s = 0, a = 4