Linear Programming: Preparation for Simplex Method

Linear Programming: Preparation for Simplex MethodRodion ChachuraBlockedUnblockFollowFollowingFeb 16This is part of the course “Optimization for Programmers”.

all code hereBefore we go to the simplex method, we need to learn how to represent the linear program in an equational form and what are basic feasible solutions.

Equational FormThe simplex method requires an equational form of linear program representation.

It looks like this:Maximize cᵀx subject to Ax=b, x≥0x is the vector of variables, A is a given m×n matrix, c∈ Rⁿ, b∈ Rᵐ are given vectors, and 0 is the zero vector, in this case with n components.

All variables in the equational form have to satisfy the nonnegativity constraints.

Transform to equational formLet’s grab the linear program from the previous part and represent it in equational form.

Maximize the value x₁ + x₂ among all vector (x₁, x₂) ∈ R², satisfying the constraints:x₁ ≥ 0x₂ ≥ 04x₂ – x₁ ≤ 13x₂ + 2x₁ ≤ 10In order to convert the inequality 4x₂ -x₁ ≤ 13 we introduce a new variable x₃, together with the nonnegativity constraint x₃ ≥ 0, and we replace the considered inequality by the equation -x₁ + 4x₂ + x₃ = 13.

The additional variable(slack variable) x₃, which won’t appear anywhere else in the transformed linear program, represents the difference between the right-hand side and the left-hand side of the inequality.

We need to do the same with x₂ + 2x₁≤ 10.

We introduce a new slack variable x₃, together with the nonnegativity constraint x₄ ≥ 0.

As a result, we have this equation 2x₁ + x₂ + x₄ = 10.

The resulting equational form of our linear program looks this way:Maximize x₁ + x₂ subject to-x₁ + 4x₂ + x₃ = 132x₁ +x₂ + x₄ = 10x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0GeometryAs is derived in linear algebra, the set of all solutions of the system Ax = b is an affine subspace F of the space Rⁿ.

Hence the set of all feasible solutions of the linear program is the intersection of F with the nonnegative orthant, which is the set of all points in Rⁿ with all coordinates nonnegative.

2DLet’s come back to the previous example.

We have two equations that describe lines.

In such case after solving system, we will obtain the only solution — point.

Let’s take a look at another example.

Maximize x₁ + x₂ subject tox₁ + x₂ = 3x₁ ≥ 0, x₂ ≥ 0In this linear program we have only one equation and therefore the set of all solutions — line(red) and the set of all feasible solutions — segment(green).

3DIf we have n=3 variables and m=1 equation, for example x₁ + x₂ + x₃ = 3 we will have this picture:The set of all possible solutions of Ax = b in this example is a plane.

If we apply nonnegativity rule(x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0), we will obtain the set of all feasible solutions(orange triangle).

With an understanding of what is the equational form, we can state the requirements for a linear program.

We will consider only linear program in equational form such that1.

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

2.

The rows of the matrix A are linearly independent.

If the system Ax = b has no solution linear program has no feasible solution either.

If some raw of A is a linear combination of the other rows, then the corresponding equation is redundant and it can be deleted from the system without changing the set of equations.

Basic Feasible SolutionsAmong all feasible solutions of a linear program, a privileged status is granted to basic feasible solutions.

Expressed geometrically a basic feasible solution is a tip (corner, spike) of the set of feasible solutions.

A basic feasible solution of the linear program maximize cᵀx subject to Ax=b, x≥0is a feasible solution x∈ Rⁿ for which there exists an m-element set S ⊆ {1, 2, .

.

.

, n} such that1.

The (square) matrix Aₛ is nonsingular, i.

e.

, the columns indexed by B are linearly independent.

2.

xⱼ=0 for all J ∉ S.

If such a S is fixed, we call the variables xⱼ with j ∈ S the basic variables, while the remaining variables are called nonbasic.

Next part is coming soon.

Stay tuned!.