# Preparation for Simplex Method With Python

February 17, 2019 Before 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 Form

The simplex method requires an equational form of linear program representation. It looks like this:

``Maximize cᵀx subject to Ax=b, x≥0``

x 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 form

Let’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₁ ≥ 0
x₂ ≥ 0
4x₂ - x₁ ≤ 13
x₂ + 2x₁ ≤ 10``````
1. In 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.

2. 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.

3. The resulting equational form of our linear program looks this way:

``````Maximize x₁ + x₂ subject to
-x₁ + 4x₂ + x₃ = 13
2x₁ +x₂ + x₄ = 10
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0``````

### Geometry

As 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.

### 2D

Let’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.

Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
view raw solution.ipynb hosted with ❤ by GitHub

Let’s take a look at another example.

``````Maximize x₁ + x₂ subject to
x₁ + x₂ = 3
x₁ ≥ 0, x₂ ≥ 0``````

In 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).

### 3D

If we have n=3 variables and m=1 equation, for example x₁ + x₂ + x₃ = 3 we will have this picture:

Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

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 that
1. 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 row 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 Solutions

Among 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≥0
is a feasible solution x∈ Rⁿ for which there exists an m-element set S *⊆ {1, 2, . . . , n} such that
1. 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.