Math of LP and simplex

Question 1

What is the fundamental theorem of linear programming?

Answer 1

The fundamental theorem of linear programming is the fact that if the feasible region X is bounded and non-empty, which means that there exists a bounded optimal solution to the problem, then this optimal value will be obtained in (at least) one extreme point x^(k) in X.

Question 2

Give the reasoning process behind the fundamental theorem of linear programming

Answer 2

It all starts with the theorem that says that the feasible region of an LP problem is a convex set. The proof of this sort of goes like this:

“we can take any two points that are feasible with respect to a constraint i, and then use the original definition of convexity to show that any point on the line between these two points are also feasible with respect to the constraint i.”. NB: requires standard form.

This proof builds on linearity.

Then the next major step is to understand what happens once we add multiple constraints. In fact, there is a proof (chapter 9) that results in the fact that the intersection of convex sets is also a convex set. Therefore, we know that the feasible region, constructed by individual convex sets, results in a convex set as well.

The next step is to understand that linear functions are convex and concave. Therefore, it does not matter if we max or min.

Now we know that every local optimum is also a global optimum.

The next step is about half spaces. In general, we say that hyperplanes split a space into half spaces. In R^3 the hyperplanes are called planes. In R^2 they are called lines.
Then, the intersection between a finite number of half spaces describes a polyhedron. In LP, we typically have the regular structural/functional constraints together with the non-negativity constraints to build the polyhedron.

With a polyhedron, or more precisely a bounded polyhedron, due to linearity of hyperplanes, we know that the polyhedron is actually a convex combination of the intersection points of the hyperplanes. A convex combination is a set of all points satisfying the equation

x = ∑lambda j x^(j) [j=1, p] and ∑lambda j = 1, and lambda j >= 0 for all j.

Why do we care about convex combination?
Because we can use it to prove that a point in the polyhedron is an extreme point or not. A point in polyhedron is an extreme point if it is not possible to express the point as a strict (0 < lambda < 1) convex combination of two points in X. In other words, only one point is included to describe it.

The last step is a proof by contradiction to show that if we have an optimal point, it must indeed be an extreme point.

This is a powerful result, since it allows simplex to efficiently explore only a very small subset of all the possible points in the feasible region. We say that the search is limited.

Question 3

what do we do if we have negative variables or free variables?

Answer 3

We need to perform a substitution. If the variable has a non-positive constraint, we can substitute x for (-x1).

if free, we substitute x for (x1 - x2).

the point is that all new variables are non-negative, which allows simplex to run.

Question 4

How many degrees of freedom is there in the system of equation?

Answer 4

Assuming that the ROWS of the matrix A are all linearly independent, there are n-m degrees of freedom.

Question 5

What is the matrix form of standard form LP problem?

Answer 5

every LP problem can be converted to:

min z = cx
s.t. Ax = b
and x >= 0

Question 6

Notation wise, how many variables and how many constraints do we consider as the size of the different vectors/matrices in the standard form?

Answer 6

Number of variables: n

Number of constraints: m

Size of matrix = rows x cols = m x n

this obviously includes slack variables, as we are in standard form.

Question 7

why do we need a mathematical description of the extreme points to use simplex?

Answer 7

Because simplex will systematically search among all vertices (extreme points) associated with the feasible region.

Question 7

how do we describe the extreme points mathematically?

Answer 7

We do it by using basic solutions.

The characterization of a vertex is that it lies in the intersection of a number of hyperplanes and that a number of constraints are active in the point. the question is: how many constraints are active in a vertex that we are interested in? Or more specifically, how many constraints need to be active to define a vertex uniquely?

Question 8

if no constraints are binding, what are we talking about?

Answer 8

An inner point.

Question 8

Define a basic solution

Answer 8

A basic solution (to a system of equaitons) to Ax = b is obtained if n-m variables are set to 0, the remaining variables are solved to find their value by solving the remaining m x m system of equations.

The variables that are set to 0 are called non-basic.
The remaining variables are called basic.

Question 9

What is required for a basic solution to exist?

Answer 9

The remaining m x m matrix we get from selecting n-m variables as non-basic, must have columns that are linearly independent. This will ensure that we can get a solution to all the remaining variables.

Question 9

“The simplex method searches for the basic that …”

Answer 9

… gives the best value according to the given objective function.

Question 10

Define adjacent vertices

Answer 10

two vertices are adjacent if the set of active constraints in the two points differ in only one element. This means that they share all but one constraints.

Question 10

Define adjacent basic solutions

Answer 10

Two basic solutions are adjacent if they share m-1 basic variables in common.

Question 11

Define change in basis

Answer 11

Change in basis refer to the process of moving from one vertex to an adjacent vertex by replacing the basis by removing the leaving basic variable, and adding the entering basic variable.

Question 12

What does reduced cost tell us?

Answer 12

Reduced cost tells us how much the objective function will improve in value by changing a variable by one unit.

Question 13

Why is it important to use canonical form?

Answer 13

there are several reasons, but the main reason is that it is very easy for us to then understand what happens if we were to select one of the various non-basic variables as the entering basic variable. This is because when the obj function is canonical, it is expressed as a function of only the non basic variables. Therefore, their coefficients represent reduced costs.

Question 14

Say we have the LP problem in matrix notation (standard form). how is a basic solution made?

Answer 14

A basic solution is made by selecting m basic variables and letting the remaining n-m variables be the non basic variables.

Question 14

Elaborate on the matrix notaiton procedure

Answer 14

First things first: Matrix notation gives us an insight in what happens to create the results we want. It is not a method that we use to compute the final result. it is a method we use to understand what the final values are and represent. The goal is to be able to understand what we can do with the values.

we begin with the initial tableau. Consists of a regular part and a slack part.
Then we select a basis and a non-basis. In practice, what this means is that we look at the initial tableau, and consider what variable we should choose as entering basic variable. This will form our new basis, and then our new non-basis.

With the new non basis, we select their values to be 0. This will reduce the system to a simpler one, where we essentially have the basic variables, the basic coeffiecnets and the basic values. Bx = b.
We solve this system by the inverse of B, and we get x = B^(-1)b.

Since the addition of the zero valued non basic variables does not alter anything, we can add them back. the point is that we perform the inverse B operaiton on the entire system so that we get our new constraint rows. it will look like this:
B^(-1)N, B^(-1)K, B^(-1)b

I say K instead of Identiy because sometimes we dont have a perfect identity matrix here (in the case of true equality or >= coinstraints).

Now, the constraints are canonical, because they express the basic variables as only dependent on the non basic variables. HOWEVER; the objective function row does not. So we need to remove (get to 0) the -c_b coefficients in that row. we do this by performing row oepraitons. This will remove the coefficents and make them 0. However, this will also alter the remaining part of the objective function row. The result is rows containing the reduced costs etc.

Various sources make the tableau different. Old book gives the tableau as consisting of two parts:
1) Regular part
2) Slack portion
it then descirbes changes as to those parts.
new book gives more detailed, yet more confusing parts:
1) Basic part
2) Non basic part
3) slack part
Here, there is overlap between slack poriton and whatever is currently selected as basic and non basic.

The poitn of the method is that we can use the initial tableau for every computaiton (theoretically) if we are given the current basis to explore/compute. We only have to change the columns we include so that the correct ones for B and N is represented.

Then, the real value is based on the hacks we can do in terms of sensitivity analysis.

Question 14

say we have 3 decision variables and 3 constraints, and to make the constraints work we need to add 4 variables (slack + surplus + 2 artificial). How many non basic and basic variables do we now have in a solution?

Answer 14

We have still 3 constraints. but we have 7 variables.
We select m=3 basic variables and let the remaining n-m = 7-3=4 be non basic variables.

Question 14

What happens if one of the original constraints is a >=?

Answer 14

The corresponding column in B^(-1) will have flipped signs in all of its coefficients.

Question 15

What happens if one of the original constraints have equality constraint?

Answer 15

The corresponding column in B^(-1) is not existing

Question 16

what is the goal of phase 1 in terms of the artificial variables?

Answer 16

Find a solution that is feasible, which means that no artificial variables should be in the basis. They must have the value 0 to indicate that they lie on the equality line.

How is this done?
We do it by using objective function that try to minimize the sum of artificial variables.

Question 16

what is the aim of phase 1?

Answer 16

The aim of phase 1 is to find any basic feasible solution that we can use as starting point for phase 2.

In essence, the phase 1 problem answers the question “is there a feasible solution to this problem?”

Question 17

When is the phase 1 problem a max problem?

Answer 17

it never is. It is always a min problem. It doesnt matter what the original objective is, when we use two-phase, the first phase is always min problem.

Question 17

what scenarios can happen in phase 1?

Answer 17

we say that there are two different cases:

1) the optimal solution shows a z-value of 0. In such case, we are good. We know that there exists a feasible solution that we can use to initiate phase 2.

2) the optimal solution shows a z-value > 0. In such case, the problem is infeasible.