Linear Programming also called linear optimization is a method to use to achieve the best outcomes (Such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by Linear relationship.

It is a special case of mathematical optimization.

Let us take some examples from real world-

(i) in a military operation.

(ii) in an industry

(iii) Salaried class.

In all the above cases -

(i) Constraints are represented by linear equations/inequations (in one, two or more variables)

(ii) a particular plan of action from several alternatives is to be chosen (Programming)

(i) & (ii) steps together is called linear programming. So, Linear Programing is a method to determining optimum values of a linear function subject to constraints as linear equations or inequations.

OABC is called feasible region satisfied by given constraints.

Unbounded feasible region

The following theorems are fundamental in solving L.P.P.

Theorem 1:

Let $R$ be the feasible region for an LPP and $z=a x+b y$ be the objective function, when $z$ has an optimal value (Max./Min.), subject to the constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.

Theorems 2:

Let $R$ be the feasible region for an LPP and $z=a x+b y$ be the objective function If $R$ is bounded, then the objective function $z$ has both a maximum and a minimum value on $R$ and each of these occurs at a corner point (vertex) of $R$.

Remark: If $R$ is unbounded, then a max. or a min. value of the objective function may not exist, if it exist, it must occur at a corner point of $R$(by Th-1).

Corner Point:

Corner point of a feasible region is a point in the region which is the intersection of two boundary lines.

Bounded Region:

A feasible region of a system of linear inequalities is said to be bounded if it can be enclosed within a circle.

Otherwise, it is called unbounded.

(i) Simplex method

(ii) Corner Point method

Corner Point Method:

It is method of solving $L P P$.

STEPS:

1. Find the feasible region of the LPP and determine its corner points either by inspection or by solving the two equations of the lines.

2. Evaluate $z=a x+b y$ at each coner point. Let $M$ and $m$ respectively denote the largest and smallest values.

$Z = ax + by$

$Z_A = p$ (smallest value)

$Z_B = q$

$Z_C = r$ (largest value)

3.(i) When the feasible region is bounded, $M$ and $m$ are the maximum and minimum values of $z$.

(ii) In case, the feasible region is unbounded, we have

(a) $M$ is the maximum value of $z$, if the open half plane determined by $a x+b y > M$ has no point in common with the feasible region.

otherwise $z$ has no maximum value.

$z_c=r \quad(\text { Maximum } )$

if $a x+b y>r$ have no point in common with feasible region then $z_c=r$ is the maximum value.

ie. $Z_{\text {max }}=r$ at $c$

If $a x+b y>r$ have comman points with feasible region then

$z=a x+b y$ have no maximum value.

ax + by < p

$Z_A=p$ (Minimum value).

$a x$ + $b y<p$ have common value with feasible region

then $Z_A=p$ will not be the min. value.

Solve the LPP graphically.

Maximize $z=4 x+y$

Subject to the constraints

$x+y \leqslant 50 \text { (i) }$

$3 x+y \leqslant 90 \text { (ii) }$

x$\geqslant 0, y \geqslant 0$

Associated eq.

$x+y=50$

&$3 x+y=90$

from (i) $x+y=50$

put $y=0 \Rightarrow x=50$

$x=0 \Rightarrow y=50$

$\therefore$ points on $x+y=50$are

(50,0)&(0,50)

Corner points are

O(0,0), A(30,0), B(20,20) & C(0,50)

$Z_0=0$

$Z_A=4 \times 30+0=120 \text { (largest value) }$

$Z_B=4 \times 20+30=110$

$Z_C=4 \times 0+50=50$

feasible region is bounded region

$\therefore Z_{\text {max }}=120$ at $A(30,0)$.

Corner points are

O(0,0), A(30,0), B(20,20) & C(0,50)

$Z_0=0$

$Z_A=4 \times 30+0=120 \text { (largest value) }$

$Z_B=4 \times 20+30=110$

$Z_C=4 \times 0+50=50$

$Z_{max}=120$ at A(30,0)