Standard form of LPP
In this tutorial, we will discuss about what is the standard form of linear programming problem?, what are the characteristics of standard form of linear programming problem?, how to convert LPP to its standard form?.
Important Definitions
Unrestricted Variables
Many times one encounter problems of the LPP in which some or all of the variables can have any sign. Variables which can be positive, negative or zero are called unrestricted variables.
Suppose that in a given LPP the variable $x_j$ is unrestricted in sign (i.e., it can take any value). Then $x_j$ can be written as
$$x_j = x^\prime_j - x^{\prime\prime}_j,$$
where $x^\prime_j,x^{\prime\prime}_j\geq 0$.
Slack Variable
If a constraint has $\leq$ sign, then in order to make it an equality, we have to add something positive to the left hand side. The non-negative variable which is added to the left side of the constraint to convert it to equation is called slack variable.
e.g. Consider the constraint $x_1+3x_2 \leq 6$. We add a non-negative variable $s_1$ to the left side of the inequality to convert it into equation $x_1+3x_2 +s_1 =6$.
Surplus Variable
If a constraint has $\geq$ sign, then in order to make it an equality, we have to subtract something positive from the left hand side. The non-negative variable which is subtracted from the left side of the constraint to convert it to equation is called surplus variable.
e.g. Consider the constraint $x_1+3x_2 \geq 6$. We subtract a non-negative variable $s_2$ from the left side of the inequality to convert it into equation $x_1+3x_2 - s_2 =6$
What are the characteristics of Standard form of LPP?
The standard form of the LPP is used to develop the procedure for solving general linear programming problem. The characteristics of the standard form of a LPP are as follows :
- Objective function should be of maximization form. Minimization function is equivalent to maximization of negative expression of that function, i.e. $\min\; z = -\max\; [-z]$. e.g. $\min\; z =2x_1+3x_2$ is equivalent to $\max\; z^\ast=-2x_1-3x_2$.
- The right side elements of each constraint should be made non-negative (if not). The right side can always be made positive on multiplying both sides of the inequality by (-1) whenever it is necessary. e.g. $-3x_1+4x_2\leq -2$ can be written as $3x_1-4x_2\geq 2$.
- All the constraint should be converted to equations except for the non-negativity restrictions.
- Constraints of the inequality type can be changed to equality by adding or subtracting the left side of each such constraints by non-negative variables. For example
- The constrain $3x_1+2x_2 \leq 4$ can be written in equation form as $3x_1 +2x_2 +s_1 = 4$, where $s_1>0$. Here $s_1$ is called Slack Variable.
- The constraint $4x_1+3x_2 \geq 3$ can be written in equation form as $4x_1 +4x_2 -s_2 = 3$, where $s_2>0$. Here $s_2$ is called Surplus Variable.
- All the decision variables should be non-negative.
- Suppose that in a given LPP the decision variable $x_j$ is unrestricted in sign (i.e., it can take any value). Then $x_j$ can be written as
$$x_j = x^\prime_j - x^{\prime\prime}_j,$$
where $x^\prime_j,x^{\prime\prime}_j\geq 0$.
Standard Form of General LPP
The standard form of General LPP with all $(\leq$) constraints can be obtained as follows :
$$ \begin{equation*} \max z = c_1 x_1 + c_2 x_2 + \ldots + c_n x_n + 0x_{n+1} + \ldots + 0x_{n+m} \end{equation*} $$
subject to
$$ \begin{eqnarray*} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1j}x_j + \ldots + a_{1n}x_n + x_{n+1}& = & b_1 \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2j}x_j + \ldots + a_{2n}x_n +x_{n+2} & =& b_2 \\ \vdots \qquad\qquad \vdots \qquad\qquad \vdots & = & \vdots \\ a_{i1} x_1 + a_{i2} x_2 + \ldots + a_{ij}x_j + \ldots + a_{in}x_n +x_{n+i} & = & b_i \\ \vdots \qquad\qquad \vdots \qquad\qquad \vdots & = & \vdots \\ a_{m1} x_1 + a_{m2} x_2 + \ldots + a_{mj}x_j + \ldots + a_{mn}x_n+x_{n+m} & = & b_m \end{eqnarray*} $$
and
$$ \begin{equation*} x_j \geq 0,\; j = 1,2,\ldots,n+m \end{equation*} $$
In the objective function the coefficient of slack variables $x_{n+1}, x_{n+2}, \ldots, x_{n+m}$ are assumed to be zero so that conversion does not change the function to be optimized.
Standard form of LPP Example 1
Convert the following LPP into standard form.
$$ \begin{eqnarray*} Max\; z= 28x_1 +30x_2 & & \\ \mbox{s.t. } 6x_1+ 3x_2&\leq& 18 \\ 3x_1 +x_2 &\leq & 8 \\ 4x_1 +5x_2 &\leq & 30 \\ \mbox{and }x_1 , x_2 & \ge & 0 \end{eqnarray*} $$
Solution
The given LPP is
$$ \begin{eqnarray*} Max\; z= 28x_1 +30x_2 & & \\ \mbox{s.t. } 6x_1+ 3x_2&\leq& 18 \\ 3x_1 +x_2 &\leq & 8 \\ 4x_1 +5x_2 &\leq & 30 \\ \mbox{and }x_1 , x_2 & \ge & 0 \end{eqnarray*} $$
Here the objective function is maximization type, all the constraints are of less than or equal to type and all the decision variables are non-negative.
Adding slack variable to the left side of each constraints, the standard form of given LPP is
$$ \begin{eqnarray*} Max\; z= 28x_1 +30x_2 +0s_1 + 0 s_2 + 0s_3& & \\ \mbox{s.t. } 6x_1+ 3x_2+ s_1&=& 18 \\ 3x_1 +x_2 +s_2&= & 8 \\ 4x_1 +5x_2+s_3&= & 30 \\ \mbox{and }x_1 , x_2,s_1,s_2,s_3 & \ge & 0 \end{eqnarray*} $$
where $x_1,x_2$ are the decision variables and $s_1,s_2, s_3$ are the slack variables.
Standard form of LPP Example 2
Convert the following LPP into standard form.
$$ \begin{eqnarray*} Max\; z= 3x_1 +2x_2 & & \\ \mbox{s.t. } x_1 -x_2&\leq& 1 \\ x_1 +x_2 &\geq & 3 \\ \mbox{and }x_1 , x_2 & \ge & 0 \end{eqnarray*} $$
Solution
The given LPP is
$$ \begin{eqnarray*} Max\; z= 3x_1 +2x_2 & & \\ \mbox{s.t. } x_1 -x_2&\leq& 1 \\ x_1 +x_2 &\geq & 3 \\ \mbox{and }x_1 , x_2 & \ge & 0 \end{eqnarray*} $$
Here the objective function is maximization type. First constraint is less than or equal to type. So to make the inequality constraint to equality, we add a slack variable $s_1$ to the left hand side of the inequality.
$$x_1 -x_2+s_1= 1$$
The the second constraint is greater than or equal to type. So to make the inequality constraint to equality, we subtract a surplus variable $s_2$ from the left hand side of the inequality.
$$x_1 +x_2 -s_2 = 3$$
The standard form of given LPP is
$$ \begin{eqnarray*} Max\; z= 3x_1 +2x_2+0 s_1 +0 s_2 & & \\ \mbox{s.t. } x_1 -x_2+s_1&=& 1 \\ x_1 +x_2 -s_2 &=& 3 \\ \mbox{and }x_1 , x_2, s_1, s_2 & \ge & 0 \end{eqnarray*} $$
where $x_1,x_2$ are the decision variables and $s_1$ is slack variable and $s_2$ is surplus variables.
Standard form of LPP Example 3
Convert the following LPP into standard form.
$$ \begin{eqnarray*} Min\; z= 2x_1 -10x_2 & & \\ \mbox{s.t. } x_1 -x_2&\geq& 2 \\ x_1 -5x_2 &\geq & -5 \\ \mbox{and }x_1 , x_2 & \ge & 0 \end{eqnarray*} $$
Solution
The given LPP is
$$ \begin{eqnarray*} Min\; z= 2x_1 -10x_2 & & \\ \mbox{s.t. } x_1 -x_2&\geq& 2 \\ x_1 -5x_2 &\geq & -5 \\ \mbox{and }x_1 , x_2 & \ge & 0 \end{eqnarray*} $$
Here the objective function is minimization type. Convert it to maximization type as
$$Max \quad z^\prime =-2x_1 + 10x_2$$
The first constraint is $\geq$ type. To convert this constraint to equality, subtract a surplus variable $s_1$ from the left hand side of the inequality.
$$-x_1-x_2 -s_1 =2$$
The right hand side of the second constraint is negative. To convert it to a positive quantity, multiply the constraint by (-1). That is $-x_1 +5x_2 \leq 5$. Now add slack variable $s_2$ to the left hand side of the constraint, we have
$$-x_1 +5x_2+s_2 = 5$$
Thus the standard form of the given LPP is
$$ \begin{eqnarray*} Max\; z^\prime= -2x_1 +10x_2+0s_1 +0s_2 & & \\ \mbox{s.t. } -x_1 -x_2-s_1&=& 2 \\ -x_1 +5x_2 +s_2&= & 5 \\ \mbox{and }x_1 , x_2, s_1,s_2 & \ge & 0 \end{eqnarray*} $$
Standard form of LPP Example 4
Convert the following LPP into standard form.
$$ \begin{eqnarray*} Min\; z= -3x_1 -5x_2 & & \\ \mbox{s.t. } 2x_1 -3x_2&\leq& 15 \\ x_1 +x_2 &\leq & 3 \\ 4x_1+x_2 &\geq& 2\\ \mbox{and }x_1 & \ge & 0\\ x_2 & & \text{ unrestricted}. \end{eqnarray*} $$
Solution
The given LPP is
$$ \begin{eqnarray*} Min\; z= -3x_1 -5x_2 & & \\ \mbox{s.t. } 2x_1 -3x_2&\leq& 15 \\ x_1 +x_2 &\leq & 3 \\ 4x_1+x_2 &\geq& 2\\ \mbox{and }x_1 & \ge & 0\\ x_2 & & \text{ unrestricted}. \end{eqnarray*} $$
Here the objective function is minimization type. Convert it to maximization type as
$$Max\quad z^\prime =3x_1 + 5x_2$$
The first constraint is $\leq$ type. To convert this constraint to equality, add a slack variable $s_1$ to the left hand side of the inequality.
$$2x_1-3x_2 +s_1 =15$$
The second constraint is $leq$ type. To convert it to equality add a slack variable $s_2$ to the left hand side of the constraint, we have
$$x_1 +x_2+s_2 = 3$$
The third constraint is $\geq$ type. To convert it to equality subtract a surplus variable $s_3$ from the left hand side of the constraint, we have
$$4x_1 +x_2-s_3 = 2$$
As the decision variable $x_2$ is unrestricted in sign, we introduce two extra non-negative variables $x_2^\prime$ and $x_2^{\prime\prime}$ such that
$$x_2 = x_2^\prime - x_2^{\prime\prime}$$
Thus the standard form of the given LPP is
$$ \begin{eqnarray*} Max\; z^\prime= 3x_1 +5(x_2^\prime - x_2^{\prime\prime})+0s_1+0s_2+0s_3 & & \\ \mbox{s.t. } 2x_1 -3(x_2^\prime -x_2^{\prime\prime}) +s_1&=& 15 \\ x_1 +(x_2^\prime -x_2^{\prime\prime}) +s_2&= & 3 \\ 4x_1+(x_2^\prime -x_2^{\prime\prime}) -s_3&=& 2\\ \mbox{and }x_1,x_2^\prime,x_2^{\prime\prime},s_1,s_2,s_3 & \ge & 0 \end{eqnarray*} $$
Important Definitions
The standard form of General LPP with all $(\leq$) constraints is as follows :
$$ \begin{equation*} \max z = c_1 x_1 + c_2 x_2 + \ldots + c_n x_n + 0x_{n+1} + \ldots + 0x_{n+m} \end{equation*} $$
subject to
$$ \begin{eqnarray*} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1j}x_j + \ldots + a_{1n}x_n + x_{n+1}& = & b_1 \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2j}x_j + \ldots + a_{2n}x_n +x_{n+2} & =& b_2 \\ \vdots \qquad\qquad \vdots \qquad\qquad \vdots & = & \vdots \\ a_{i1} x_1 + a_{i2} x_2 + \ldots + a_{ij}x_j + \ldots + a_{in}x_n +x_{n+i} & = & b_i \\ \vdots \qquad\qquad \vdots \qquad\qquad \vdots & = & \vdots \\ a_{m1} x_1 + a_{m2} x_2 + \ldots + a_{mj}x_j + \ldots + a_{mn}x_n+x_{n+m} & = & b_m \end{eqnarray*} $$
and
$$ \begin{equation*} x_j \geq 0,\; j = 1,2,\ldots,n+m \end{equation*} $$
Solution
A set of values $\{x_1, x_2, \ldots , x_{n+m}\}$ which satisfy the constraints of linear programming problem is called a solution of the LPP.
Feasible Solution
A solution of a LPP which also satisfies the non-negativity restrictions of the problem is called its feasible solution.
Basic Solution
A basic solution to the set of constraints is a solution obtained by setting any $n$ variables (among $n+m$ variables) equal to zero and solving for remaining $m$ variables, provided the determinant of the coefficient of these $m$ variables is non-zero. Such $m$ variables are called basic variables and remaining $n$ zero-valued variables are called non-basic variables.
The number of basic solutions thus obtained will be at the most $\binom{m+n}{n}$.
Basic Feasible Solution
A basic solution which also satisfies the non-negativity restrictions of the problem is called basic feasible solution.
Degenerate Basic Feasible Solution
If one or more of the basic variables are zero then such a basic feasible solution is called Degenerate Basic Feasible Solution.
Non-degenerate Basic Feasible Solution
If all the basic variables are strictly greater than zero, then such basic feasible solution is called Non-degenerate Basic Feasible Solution.
Optimal Solution
A feasible solution which optimizes (maximizes or minimizes) the objective function of a linear programming problem is called an optimal solution (i.e., maximal solution or minimal solution) of the LPP.
Endnote
In this tutorial you learn about characteristics of standard form of LPP, some important terms related to linear programming problem and how to convert LPP to its standard form by illustrated examples.
To learn more about linear programming problem, please refer to the following tutorials:
Let me know in the comments if you have any questions on standard form of linear programming problem and your thoughts on this article.
