Linear programming standard form example

It only contains positive variables, equality constraints and it must be a minimization problem.
Conversion of "less than" inequalities into equalities.

Conversion of "less than" inqualites to equalities

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

So, we must:

Consider a new (m+1)*1 column-vector X=

So, A was equal to:

and we add the new column,
so that A becomes:

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:

So, we must:

Consider a new (m+1)*1 column-vector X=

So, A was equal to:

and we add the new column,
so that A becomes:

So, vector C was equal to:
and we add	c_n+1=0

So that C becomes :

( c₁

c₂

c_n

0 )

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.

_.,i

i+1

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

c_ix'_i+c'_ix''_i
=c_i(x'_i-x''_i)
= c_ix_i

The new vector C is the following:

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.

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.