Linear programming is defined as a method of either maximizing or minimizing linear functions which are subjected to equality or inequality constraints. The linear inequalities which are formed are on the basis of certain situations of the problem and the objective of the linear programming is to optimize the solution finding out the best possible solution to the problem. The constraints are the limitations of the problem. For example we can take up the limitations of resources in terms of materials and labour and then finding out the best possible way to maximize the profit of the organization under the constraints or limitations of material and labour. The steps to solve linear programming are to graph the linear inequalities first which is known as the constraints. The linear inequalities then bounds an area known as the feasibility region and the points at which each of the constraints crosses each other are known as the corner points. The coordinates of the corner points are found out and then plugged into each of the linear inequality or optimization equation to find out the maximum or minimum values.

## Definition

Linear programming is defined as a technique of mathematics whose objective is to find out the best possible solution of linear inequalities. These linear inequalities are the cost function and the optimization equation involves achieving the maximum profit or minimum cost. The resources could be energy, time, man power, finance, and materials etc which are limited in nature.
Few of the applications of linear programming are as follows:

a) Production Management – Linear programming method is used to determine the optimal usage of resources so as to maximize the revenue or minimize the cost.

b) Personnel Management – Linear programming is used to determine the optimal allocation of labor or manpower in various divisions so as to achieve the production level within deadline.

c) Inventory Management – Linear programming is used to determine the minimal inventory cost included in successfully working under the limitations of raw materials, space or the product demand.

d) Marketing Management – Linear programming is used to determine the optimal distribution of finished products from the factories to the shops so that the total transportation cost is minimum.

## Standard Form

A linear program is said to be in standard form if it satisfies the following conditions:

a) All variables in the linear program should be non-negative in nature

b) All the constraints be $t$ greater than or equal to, less than or equal to $r$ any other remaining constraints should be expressed as equality constraints

c) The right hand side should always be positive

Let us take up an example to point out the mistakes are as follows:

Max: $x_1\ +\ x_2\ -\ 3x_3\ –\ 2x_4$ (Optimization equation)

Subjected to constraints:

$x_1\ +\ x_2\ +\ 2x_3\ -\ x_4\ \leq\ 8$ (not equality)

$-2x_1\ –\ 3x_2\ +\ x_3\ +\ x_4\ \leq\ -2$ (not equality and having negative right hand side)

$x_1\ \geq\ 0,\ x_2\ \leq\ 0$ ($x_2$ has $t$ be negative and $x_3,\ x_4$ should either be positive or negative)

Let us step by step convert the linear program into standard form

Step 1:

To convert “$\leq$” into standard form

$x_1 + x_2 + 2x_3 – x_4 \leq 8$

When we convert a less than or equal to into equality_ we need to add a slack variable. The resource which remains unused is known as slack variable. That is

$x_1 + x_2 + 2x_3 – x_4 + s_1$ = $8$

Step 2:

To convert “$\geq$” into standard form

To convert “$\geq$” into standard form

$-2x_1 – 3x_2 + x_3 + x_4 \geq -2$

To convert the negative right hand side into positive we need to multiply, the whole function by $-1$ and then to convert the constraint into standard form we subtract a surplus variable. The value of difference of the left hand side and the right hand side is known as the surplus variable.

$2x_1 + 3x_2 - x_3 - x_4 – s_2$ = $2$

Step 3:

Remove the negative variables

The negative variable is converted to standard form with the help of substitution method, that is $–x_2$ = $y_2$ so that $y_2\ \geq\ 0$

Step 4:

Variable unconstrained in sign

Variables which are unconstrained in sign that is either positive or negative can be get rid off by making it subject to equality

$x_3$ = $2x_1 + 3x_2 + x_4 + s_2 - 2$

## Duality

Every linear programming has a second linear programming related to it. This other linear programming is actually derived from the original one. The original linear programming is known as the primal and the derived linear programming is known as the dual.

Steps to be followed to create dual linear programming are as follows:

Number of constraints in the primal is equal to the number of variables in the dual and vice versa.

Objective function of the dual linear programming is the same as the right hand side values of the constraints of the primal.

When the primal linear programming is a maximization objective function the duality of it is a minimization objective function and vice versa.

The coefficients of the first constraint of the dual linear programming are derived from the coefficients of the first variable of all the constraints present in the primal. Similarly, the coefficients of the second constraint of the dual linear programming are derived from the coefficients of the second variable of all the constraints present in the primal and so on.

The right hand side of the dual linear programming is derived from the coefficients of the objective function of the primal.
Example:

$\left.\begin{matrix} Maximize\ profit\ 70x_1\ +\ 20x_2\\ Subjected\ to\ constraints,\\ x_1\ +\ 5x_2\ \leq\ 150\ (raw\ material)\\ 2x_1\ +\ 3x_2\ \leq\ 120\ (man\ power)\\ x_1,\ x_2\ \geq\ 0\end{matrix}\right\} Primal$

$\left.\begin{matrix}Minimize\ cost\ 150y_1\ +\ 120y_2\\ Subjected\ to\ constraints,\\ y_1\ +\ 2y_2\ \geq\ 70\\ 5y_1\ +\ 3y_2\ \geq\ 20\\ y_1,\ y_2\ \geq\ 0\end{matrix}\right\} Dual$

## Graphing

Graphing of linear programming includes plotting the constraints or the inequalities on the graph. The inequalities intersect each other and the points of intersection of the constraints are called the corner points. The area bounded within the corner points is called the feasibility region. The coordinates of the corner points are then plugged into the objective function to find out the maximization value or the minimization value as required. Coordinates of those corner point which satisfies the objective function is the solution of the linear programming and the value we get on solving the objective function is the maximize or minimize value we get.

## Example

Jady wants to buy cabinet and wooden desk for his study room. The cost per cabinet is $\$ 10$and covers a floor area of$6$square feet and$8$cubic feet. The cost per wooden desk is$ \$20$ and covers a floor area of $8$ square feet and $12$ cubic feet. Budget allotted for shopping was $\$ 140$and space has a limitation of$72$square feet. How many cabinets could be bought to maximize the volume? Solution: As per the given information the objective function is Maximize volume$Z$=$8x\ +\ 12y$Subjected to constraints,$10x\ +\ 20y\ \leq\ 140$(Cost)$6x\ +\ 8y\ \leq\ 72$(Space)$x\ \geq\ 0,\ y\ \geq\ 0$where$x$= number of cabinets purchased and$y$= number of wooden desks purchased On solving$10x\ +\ 20y$=$140$and$6x\ +\ 8y$=$72$simultaneously, we get$x\ +\ 2y$=$14,\ x$=$14\ -\ 2y$So,$6(14\ -\ 2y)\ +\ 8y$=$7284\ -\ 12y\ +\ 8y$=$724y$=$12y$=$3$, so$x$=$14\ -\ 2(3)$=$14\ -\ 6$=$8$On solving$x$=$0$and$x\ +\ 2y$=$14$we get$y$=$7$, and on solving$y$=$0$and$6x\ +\ 8y$=$72$we get$6x\ +\ 8(0)$=$72,\ x$=$12$Therefore the corner points are$(8,\ 3),\ (0,\ 7)$and$(12,\ 0)$On plugging the corner points in the objective function we get,$Z$=$8(8)\ +\ 12(3)$=$100Z$=$8(0)\ +\ 12(7)$=$84Z$=$8(12)\ +\ 12(0)$=$96$Therefore, the maximum volume is$100\$ cubic feet