Linear Programming Flashcards
Infeasibility
The LP if the program to maximise the auxiliary variables has a non-zero optimum.
Degeneracy
Pivots do not change the value of the objective function; only its composition
Primal program
Max t(c) * x
St
Ax = 0
Dual program Min t(b)*y St t(A)*y >= c y>= 0
Lemma: Weak Duality
If x is feasible for the primal and y is feasible for the dual, then
t(c) * x
Theorem: Strong duality
If the primal linear program is feasible and bounded, then the dual linear program is feasible with the same optimum value as the primal.
Theorem: Complementary Slackness
If P has a solution x* and D has a solution y* and
-x[j]>0, then //
-y[i]> 0, then
- the jth constraint in D is an equality
- the ith constraint in P is an equality
The converse is also true!
The optimal dual solution y* is equal to
The negative of the coefficients of the slack variables of the final objective function
If the primal is unbounded, the dual is
Infeasible
And vice versa
We say a game has value w if
sum(p[i] * a[i,j]) >= w for all j
Interpretation: if player one plays strategy p, his expected payoff is w whatever player two does.
The expected payoff for player one from a game is
t(p) %% A %% q
Unboundedness
There is no variable restricting the increase of an entering variable; all the coefficients corresponding to it are non-negative.
Von Neumann Theorem:
For any real matrix A, the zero-sum, two-person game has a value w satisfying sum(p[i]*a[i,j]) >= w for some mixed strategies p and q.
Turning a game into a linear program:
- Add a constant to all entries of A so that there are no negative entries.
- Let u = p/w and v = q/w.
- New conditions are
- sum(u[i] * a[i,j]) >= 1, sum(a[i,j]*v[j])
Solution to a zero-sum game as an LP:
p = wu and q = vw
A game is symmetric if the payoff matrix satisfied
t(B) = -B
Theorem: zero-sum symmetric games
The value of a zero-sum symmetric game is zero, and an optimal strategy for one player is also optimal for the other player
Every solvable linear program is equivalen to
a symmetric, zero-sum, two-person game
Standard form for a linear program:
1 the RHS of the constraints must be non-negative
2 constraints are expressed as equalities
3 non-negativity constraints for all variables
Converting to standard form:
1 Multiply any negative bits of the RHS by -1
2. Use slack variables to express constraints as equalities
3 Use y = -x for any var with non-positivity constraint
How to deal with free variables, method 1:
Use substitution; re-write one of the constraints as x = … (where x is the free var) and then substitute that into every appearance of x
How to deal with free variables, method 2:
Replace x = y - w, where y and w must both be non-negative.
Assumptions for the Simplex algorithm
The system of equations Ax = b has at least one solution
The rows of A are linearly independent
A basic feasible solution of Ax = b (definition):
A feasible solution x such that there exists an m-element set B such that if j is not an element of B, the x[j] = 0
and the matrix A[B] is non-singular, where A[B] is the matrix A indexed by the indices in B.
- m is the number of equations
Lemma: If B is an m-element set of indices with A[B] non-singular, then…
…there exists at most one feasible solution x with x[j] = 0 for all j is not an element of B.
Fundamental Theorem of Linear Programming, part 1:
If there is at least one feasible solution and the objective function is bounded from above, then there exists an optimal solution.
Fundamental Theorem of Linear Programming, part 2:
If an optimal solution exists, then there is a basic feasible solution that is optimal.
Theorem: Let P be the set of feasible solutions of a linear program in equational form. Then v is a vertex of the polyhedron P if and only if
v is a basic feasible solution of the linear program.
How to find a basic feasible solution if your constraints are equalities
- Add in ‘auxiliary variables’ - by how much do variables fail to hit their target?
- Maximise the negative of their sum
