Linear Programming线性规划(Introduction to Algorithms, 算法导论,CLRS)学习笔记
Linear Programming
1. Fundamentals
-
objective function and constraints:
m i n / m a x 3 x 1 + 24 x 2 + 13 x 3 + 9 x 4 . . . s . t l i n e a r c o n s t r a i n t s min/max\quad 3x_1+24x_2+13x_3+9x_4...\\s.t\quad\;\; linear\; constraints min/max3x1+24x2+13x3+9x4...s.tlinearconstraints
-
optimal solution: a feasible solution that has the min(or max) objective value
-
convex property: the optimal solution must fall in the corner of the feasible region(decided by constraints)
-
geometric interpretation:
-
each constraint defines a half-space, the solutions are the intersection of half-spaces and are called simplex;
-
objective functions form a hyperplane.
-
2. Standard and Slack forms
-
LP to standard form:
-
convert a minimization into a maximization;
-
add nonnegative constraints: all x x x variables are greater than zero;
-
convert some variables that do not have nonnegative constraints;
-
replace x j x_j xj with x j ′ − x j ′ ′ x_j'-x_j'' xj′−xj′′
-
-
convert equality constraints into inequality constraints; by replacing = = = with ≤ \le ≤ and ≥ \ge ≥
-
convert ≥ \ge ≥ into ≤ \le ≤;
-
-
Standard form to slack form
-
For example: 2 x 1 + 3 x 2 + x 3 ≤ 5 − > 2 x 1 + 3 x 2 + x 3 + x 4 = 5 2x_1+3x_2+x_3\le 5\quad->\quad 2x_1+3x_2+x_3+x_4=5 2x1+3x2+x3≤5−>2x1+3x2+x3+x4=5, where x 4 x_4 x4 is the slack.
-
Put all the slacks to right hand side and get the slack form, for example:
-
-
Basic Solutions: in slack form, set all RHS variables to 0, and the LHS variables are called basic, RHS variables are nonbasic.
3. Simplex algorithm
-
Convert into slack form;
-
find the variable in “z row” with biggest coefficient;
-
Do min test and replace the basic value with its corresponding non-basic value;
-
Repeat step 2 and 3 until all variables in “z row” become negative or sometimes LP is obviously unbounded.
-
Why would it terminate? If the number of basic solution( m m m) is finite then iterations would be: ( m + n m ) \binom{m+n}{m} (mm+n)
-
LP is Unbounded: when one variable increase, then all of other variables also increase. Non constraints are binding; LP is unbounded.
4. Degeneracy
The objective function’s value doesn’t change between iterations.
- 1.we need two out of three lines to find a corner which means that one line(constraint) is extra.
- 2.the reason why one of variable is equal to zero.
5. Cycling
- If Simplex fails to terminate then it cycles;
- two or more basic variables compete for leaving, then choose the one with smallest subscript to leave.
6. Infeasible First Basic Solution
-
Example:
7. Auxiliary Linear Programming
-
If original LP is feasible, then the slack form of the auxiliary LP
will yield a feasible basic solution to the original LP (and the
corresponding slack form).
8. Duality
-
LP in standard form and its dual
-
Weak Duality: x ∗ x^* x∗ feasible solution to the primal LP; y ∗ y* y∗ feasible solution to the dual LP.
-
If
∑ j = 1 n c j x j ∗ = ∑ i = 1 m b i y i ∗ \sum_{j=1}^nc_jx_j^*=\sum_{i=1}^mb_iy_i^* j=1∑ncjxj∗=i=1∑mbiyi∗
then x ∗ x^* x∗ and y ∗ y^* y∗ are optimal solutions to the primal and to the
dual LPs, respectively.
9. Upper Bounds on Maximization LP
10. Additional Proof
10.1 If S IMPLEX fails to terminate in at most ( n + m m ) \binom{n+m}{m} (mn+m)iterations, then it cycles.
Proof Given a set B B B of basic variables(Lemma 29.4), the associated slack form is uniquely determined. There are n + m n+m n+m variables and ∣ B ∣ = m |B|=m ∣B∣=m, and therefore, there are at most ( n + m m ) \binom{n+m}{m} (mn+m) ways to determine B B B. Thus, there are at most ( n + m m ) \binom{n+m}{m} (mn+m) unique slack forms.