Linear Programming

Question 1

Infeasibility

Answer 1

The LP if the program to maximise the auxiliary variables has a non-zero optimum.

Question 2

Degeneracy

Answer 2

Pivots do not change the value of the objective function; only its composition

Question 3

Primal program
Max t(c) * x
St
Ax = 0

Answer 3

Dual program
Min t(b)*y
St
t(A)*y >= c
y>= 0

Question 4

Lemma: Weak Duality

Answer 4

If x is feasible for the primal and y is feasible for the dual, then
t(c) * x

Question 5

Theorem: Strong duality

Answer 5

If the primal linear program is feasible and bounded, then the dual linear program is feasible with the same optimum value as the primal.

Question 6

Theorem: Complementary Slackness
If P has a solution x* and D has a solution y* and
-x[j]>0, then //
-y[i]> 0, then

Answer 6

• the jth constraint in D is an equality
• the ith constraint in P is an equality

The converse is also true!

Question 7

The optimal dual solution y* is equal to

Answer 7

The negative of the coefficients of the slack variables of the final objective function

Question 8

If the primal is unbounded, the dual is

Answer 8

Infeasible

And vice versa

Question 9

We say a game has value w if

Answer 9

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.

Question 10

The expected payoff for player one from a game is

Answer 10

t(p) %% A %% q

Question 11

Unboundedness

Answer 11

There is no variable restricting the increase of an entering variable; all the coefficients corresponding to it are non-negative.

Question 12

Von Neumann Theorem:

Answer 12

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.

Question 13

Turning a game into a linear program:

Answer 13

1. Add a constant to all entries of A so that there are no negative entries.
2. Let u = p/w and v = q/w.
3. New conditions are
   - sum(u[i] * a[i,j]) >= 1, sum(a[i,j]*v[j])

Question 14

Solution to a zero-sum game as an LP:

Answer 14

p = wu and q = vw

Question 15

A game is symmetric if the payoff matrix satisfied

Answer 15

t(B) = -B

Question 16

Theorem: zero-sum symmetric games

Answer 16

The value of a zero-sum symmetric game is zero, and an optimal strategy for one player is also optimal for the other player

Question 17

Every solvable linear program is equivalen to

Answer 17

a symmetric, zero-sum, two-person game

Question 18

Standard form for a linear program:

Answer 18

1 the RHS of the constraints must be non-negative
2 constraints are expressed as equalities
3 non-negativity constraints for all variables

Question 19

Converting to standard form:

Answer 19

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

Question 20

How to deal with free variables, method 1:

Answer 20

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

Question 21

How to deal with free variables, method 2:

Answer 21

Replace x = y - w, where y and w must both be non-negative.

Question 22

Assumptions for the Simplex algorithm

Answer 22

The system of equations Ax = b has at least one solution

The rows of A are linearly independent

Question 23

A basic feasible solution of Ax = b (definition):

Answer 23

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

Question 24

Lemma: If B is an m-element set of indices with A[B] non-singular, then…

Answer 24

…there exists at most one feasible solution x with x[j] = 0 for all j is not an element of B.

Question 25

Fundamental Theorem of Linear Programming, part 1:

Answer 25

If there is at least one feasible solution and the objective function is bounded from above, then there exists an optimal solution.

Question 26

Fundamental Theorem of Linear Programming, part 2:

Answer 26

If an optimal solution exists, then there is a basic feasible solution that is optimal.

Question 27

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

Answer 27

v is a basic feasible solution of the linear program.

Question 28

How to find a basic feasible solution if your constraints are equalities

Answer 28

1. Add in ‘auxiliary variables’ - by how much do variables fail to hit their target?
2. Maximise the negative of their sum