1. A general linear programming problem can be stated as follows:

Given a set of \displaystyle m linear inequalities or equations in \displaystyle n variables, we wish to find non-negative values of these variables which will satisfy these inequalities or equations and maximize or minimize some linear function of the variables.

The inequalities or equations are called the constraints and the function to be maximized or minimized is called the objective function which can be of maximization type or minimization type.

The general form of linear programming problem is maximize (minimize)

\displaystyle Z=c_{1}x_{1}+c_{2}x_{2}+\cdots+c_{n}x_{n}

Subjected to

\displaystyle a_{11}x_{1}+a_{12}x_{2}+\cdots+a_{1n}x_{n}\ {\le,=,\ge}\ b_{1}

\displaystyle a_{21}x_{1}+a_{22}x_{2}+\cdots+a_{2n}x_{n}\ {\le,=,\ge}\ b_{2}

\displaystyle \cdots

\displaystyle a_{m1}x_{1}+a_{m2}x_{2}+\cdots+a_{mn}x_{n}\ {\le,=,\ge}\ b_{m}

and \displaystyle x_{1},x_{2},x_{3},\ldots,x_{n}\ge0

where,

(i) \displaystyle x_{1},x_{2},\ldots,x_{n} are the variables whose values we wish to determine and are called the decision variables.

(ii) the linear function \displaystyle Z which is to be maximized or minimized is called the objective function.

(iii) the inequalities or equations in (ii) are called the constraints.

(iv) the set of inequalities in (iii) is known as the set of non-negativity restrictions.

(v) \displaystyle b_{i}\ (i=1,2,\ldots,m) represents the requirement or availability of the \displaystyle ith constraint and the column matrix

\displaystyle B=\begin{bmatrix}b_{1}\ b_{2}\ \vdots\ b_{m}\end{bmatrix}

is called the requirement vector.

(vi) \displaystyle c_{j}\ (j=1,2,\ldots,n) represents the profit or cost to the objective function of the \displaystyle jth variable \displaystyle x_{j} and the row matrix

\displaystyle C=[c_{1},c_{2},\ldots,c_{n}]

is called the profit (cost) matrix (vector).

(vii) the coefficients \displaystyle a_{ij}\ (i=1,2,\ldots,m;\ j=1,2,\ldots,n) are known as the technological or substitution coefficients.

(viii) the expression \displaystyle (\le,=,\ge) means that one and only one of the signs \displaystyle \le,=,\ge holds for a particular constraint but the sign may vary from constraint to constraint.

2. A set of values of the decision variables which satisfy the constraints of a linear programming problem (LPP) is called a solution of the LPP.

3. A solution of a LPP which also satisfies the non-negativity restrictions of the problem is called its feasible solution. The set of all feasible solutions of a LPP is called the feasible region.

4. A feasible solution which optimizes (maximize or minimize) the objective function of a LPP is called an optimal solution of the LPP. A linear programming problem may have many optimal solutions. In fact, if a LPP has two optimal solutions, then there are an infinite number of optimal solutions.

5. Let \displaystyle X_{1}=(x_{11},x_{12}) and \displaystyle X_{2}=(x_{21},x_{22}) be any two points in \displaystyle R^{2} (two dimensional plane).

Then \displaystyle X=\lambda X_{1}+(1-\lambda)X_{2}, \displaystyle \lambda\in R is any point on the line joining points \displaystyle X_{1} and \displaystyle X_{2}.

If \displaystyle 0\le\lambda\le1, then \displaystyle X is any point on the line segment joining \displaystyle X_{1} and \displaystyle X_{2}. Thus, the set of points

\displaystyle E={X\mid X=\lambda X_{1}+(1-\lambda)X_{2},\ \lambda\in R}

is the line joining point \displaystyle X_{1} and \displaystyle X_{2} and the set

\displaystyle E_{1}={X\mid X=\lambda X_{1}+(1-\lambda)X_{2},\ 0\le\lambda\le1}

is the line segment joining \displaystyle X_{1} and \displaystyle X_{2}.

6. A set \displaystyle E in \displaystyle R^{2} is said to be convex set if for any two points \displaystyle X_{1},X_{2} in \displaystyle E, the line segment joining \displaystyle X_{1},X_{2} is contained in the set i.e.

\displaystyle X=\lambda X_{1}+(1-\lambda)X_{2}\in E for \displaystyle 0\le\lambda\le1.

The set of all feasible solutions of a linear programming problem is a convex set.

7. The graphical method for solving linear programming problems is applicable to those problems which involve only two variables. This method is based upon a theorem, called extreme point theorem, which is stated as follows:

If a LPP admits an optimal solution, then at least one of the extreme (or corner) points of the feasible region gives the optimal solution.

8. There are two methods to solved a linear programming problem graphically.

(i) Corner-point method

(ii) Iso-profit or Iso-cost method.

9. To solve a linear programming problem by corner point method, we follow the following steps:

(i) Formulate the given LPP in mathematical form if it is not given in mathematical form.

(ii) Convert all inequalities into equations and draw their graphs. To draw the graph of a linear equation, put \displaystyle y=0 in it and obtain a point on X-axis. Similarly, by putting \displaystyle x=0 obtain a point on y-axis. Join these two points to obtain the graph of the equation.

(iii) Determine the region represented by each inequality. To determine the region represented by an inequality replace \displaystyle x and \displaystyle y both by zero, if the inequality reduces to a valid statement, then the region containing the origin is the region represented by the given inequality. Otherwise, the region not containing the origin is the region represented by the given inequality.

(iv) Obtain the region in \displaystyle xy-plane containing all points that simultaneously satisfy all constraints including non-negativity restrictions. The polygonal region so obtained is the feasible region and is known as the convex polygon of the set of all feasible solutions of the LPP.

(v) Determine the coordinates of the vertices (corner points) of the convex polygon obtained in step (ii). These vertices are known as the extreme points of the set of all feasible solutions of the LPP.

(vi) Obtain the values of the objective function at each of the vertices of the convex polygon. The point where the objective function attains its optimum (maximum or minimum) value is the optimal solution of the given LPP.

10. To solve a linear programming problem by Iso-profit or Iso-cost method, we follow the following steps:

(i) Formulate the given LPP in mathematical form, if it is not given so.

(ii) Obtain the region in \displaystyle xy-plane containing all points that simultaneously satisfy all constraints including non-negativity restrictions. The polygonal region so obtained is the convex set of all feasible solutions of the given LPP and it is also known as the feasible region.

(iii) Determine the coordinates of the vertices (Corner points) of the feasible region obtained in step (ii).

(iv) Give some convenient value to \displaystyle Z and draw the line so obtained in \displaystyle xy-plane.

(v) If the objective function is of maximization type, then draw lines parallel to the line in step (iv) and obtain a line which is farthest from the origin and has at least one point common to the feasible region.

If the objective function is of minimization type, then draw lines parallel to the line in step (iv) and obtain a line which is nearest to the origin and has at least one point common to the feasible region.

(vi) Find the coordinates of the common point(s) obtained in step (v). The point(s) so obtained determine the optimal solution(s) and the value(s) of the objective function at these point(s) give the optimal solution.

Discover more from ICSE / ISC / CBSE Mathematics Portal for K12 Students

Subscribe to get the latest posts sent to your email.