Converting to Standard Form

Interactive Linear Programming

Conversion of a general linear program into a standard linear program

Reminder: The standard problem is formulated as follows:

*Min cX*
*Subject to:*
	and X0
with c =

It only contains positive variables, equality constraints and it must be a minimization problem.

Conversion of "less than" inequalities into equalities.

Conversion of "greater than" inequalities into equalities.

Non positive variables.

Maximization problems.

Conversion of "less than" inqualites to equalities

Suppose that the i^th constraint is a smaller than equality labeled as follows:

a_i,1x₁+a_i,2x₂+... +a_i,mx_mb_i
It is equivalent to say that:
a_i,1x₁+a_i,2x₂+... +a_i,mx_m=b_i-x_m+1
or
a_i,1x₁+a_i,2x₂+... +a_i,mx_m+x_m+1=b_i
with x_m+1, a positive slack variable.

*So, we must:*
Consider a new (m+1)*1 column-vector X=

Add a column to matrix A with zeros everywhere except on the i^th line (where we will put a 1, so as to the x_m+1 in the i^th constraint).

So, A was equal to:
and we add the new column, so that A becomes:

Add a column to vector C (simply one zero, since the new slack variable, x_m+1, must not affect the value of the objective function).
So, vector C was equal to:

and we add c_n+1=0

So that C becomes : ( c₁ c₂ ... c_n 0 )

So we have a new problem, with still n constraints, but m+1 variables. If we repeat this process with all the "smaller than" inequalities, and introduce one slack variable for each of them, then we obtain a new problem where all the "smaller than" inequalities are replaced by equalities.
Conversion of "greater than" inqualites to equalities
Suppose that the i^th constraint is a bigger than equality labeled as follows:

a_i,1x₁+a_i,2x₂+... +a_i,mx_mb_i
It is equivalent to say that:
a_i,1x₁+a_i,2x₂+... +a_i,mx_m=b_i+x_m+1
or
a_i,1x₁+a_i,2x₂+... +a_i,mx_m-x_m+1=b_i
with x_m+1, a positive slack variable.
- Add a column to matrix A with zeros everywhere except on the i^th line (where we will put a -1, so as to the x_m+1 in the i^th constraint).
  
  So, A was equal to:
  
  and we add the new column,
  so that A becomes:
- Add a column to vector C (simply one zero, since the new slack variable, x_m+1, must not affect the value of the objective function).
  So, vector C was equal to:
  
  and we add c_n+1=0
  
  So that C becomes : ( c₁ c₂ ... c_n 0 )
So we have a new problem, with still n constraints, but m+1 variables. If we repeat this process with all the "bigger than" inequalities, and introduce one slack variable for each of them, then we obtain a new problem where all the "bigger than" inequalities are replaced by equalities.
Conversion of non-positive variables
You have certainly noticed that the standard formulation of a linear program is quite restrictive, since it does only consider positive variables. In reality, it does not constitute a problem, since we can easily convert a problem where some variables are not required to be positive into a problem with only positive variables.
Indeed, suppose that the i^th variable x_i has no positivity constraint.
We the introduce two "artificial variables":
x'_i
x''_i
and replace x_i by
x_i = x'_i - x''_i
So, we can still have x_i either positive or negative, with x'_i and x''_i positive.
The new variable (n+1)*1 column-vector is:
x'_i and x''_i positive.

This duplication of variable x_i into two variables obliges us to update matrix A and vector C:
- In matrix A, we add a new column labeled A'_.,i between columns i and i+1, equal to the opposite of column i.
  So A, that was equal to
  
  and becomes:
  
  And we will have, in each constraint j:
  
  a_i,jx'_i+a'_i,jx''_i
  =a_i,j(x'_i-x''_i)
  =a_i,jx_i
- For vector C, we introduce a number c'_i between c_i and c_i+1 with c'_i = -c_i ,
  so that :
  
  c_ix'_i+c'_ix''_i
  =c_i(x'_i-x''_i)
  = c_ix_i
  
  The new vector C is the following:
So, the new problem after conversion of all the variables "non-positive" into two positive variables can be solved by our algorithm. Once it is solved and we have obtained the optimal value of the objective function, we can find the optimal value of the variables of the original problem by doing the following:
x_i = x'_i - x''_i

Maximization Problems
You have certainly noticed that the standard formulation of a linear program is quite restrictive, since it only considers minimization problems. In reality, it does not constitute a problem, and it is very easy to convert a maximization problem into a minimization problem.
Indeed, suppose that your problem is to

Maximize c₁x₁ + c₂x₂ +.....+ c_nx_n (Objective function)

This is strictly equivalent to:

Minimize -c₁x₁ - c₂x₂ -.....- c_nx_n

and take the opposite of the optimal value of the objective function for this minimization problem as the optimal value for the original (maximization) problem.

So, what you only need to do is:
- Take the opposite of vector C (i.e. (-c₁ ,-c₂ ,... ,-c_n) ).
- Solve the standard linear program minimize (-C)X, subject to the same constraints as the original problem.
- Take the opposite of the result as the optimal value of the objectif function for the original problem, and the same values of the variables x₁ ,x₂ ,... ,x_n as the optimal solution.
Go back to the project home page

Conversion of a general linear program into a standard linear program

Conversion of "less than" inqualites to equalities

Conversion of "greater than" inqualites to equalities

Conversion of non-positive variables

Maximization Problems