USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Introduction to Linear Programming Problems (LPP)

 

I. When a problem is identified then the attempt is to make an mathematical model. In decision making all the decisions are taken through some variables which are known as decision variables.

 

In engineering design, these variables are known as design vectors. So in the formation of mathematical model the following three phases are carried out :

 

(i)              Identify the decision variables.

(ii)            Identify the objective using the decision variables and

(iii)          Identify the constraints or restrictions using the decision variables.

 

Let there been decision variable x1, x2, .... , xn and the general form of the mathematical model which is called as Mathematical programming problem under decision making can be stated as follows : ·

 

Maximize | Minimize                                     z = j ( x1, x2, .... , xn )

Subject to,                                           gi (x1, x2, .... , xn) {≤ , ≥or =} bi

i = 1, 2, …. , m.

and the type of the decisions i.e.,       xj    0

or,                                                        xj    0 or Xj’s are unrestricted

or

decisions.                                                                                                        combination types

 

In the above, if the functions f and g; (i = 1, 2, .... , m) are all linear, then the model is called "Linear Programming Problem (LPP)". If any one function is non-linear then the model is called "Non-linear Programming Problem (NLPP)".

 

II.We define some basic aspects of LPP in the following :

 

(a) Convex set : A set X is said to be convex if

 

 x1, x2  = X, then for 0 ≤  λ ≤1,

x3 = λ .x1 + (1 - λ)x2  = X

 

Some examples of convex sets are :

       

 

 

Fig. 1.1 Convex sets

 

Some examples of non-convex sets are

Basically if all the points on a line segment forming by two points lies inside the set/geometric figure then it is called convex.

 

(b) Extreme point or vertex or corner point of a convex set : It is a point in the convex set which can not be expressed as A.x1 + (1 - A.}xz where x1 and x2 are any two points in the convex set.

 

For a triangle, there are three vertices, for a rectangle there are four vertices and for a circle there are infinite number of vertices.

 

(c) Let Ax = b be the constraints of an LPP. The set X = {x I Ax = b, x :2': 0} is a convex set.

 

Feasible Solution : A solution which satisfies all the constraints in LPP is called feasible solution.

 

Basic Solution : Let m = no. of constraints and n = no. of variables and m < n. Then the solution from the system Ax = b is called basic solution. In this system there are  ncm  number of basic solutions. By setting (n - m) variables to zero at a time, the basic solutions are obtained. The variables which is set to zero are known as 'non-basic' variables. Other variables are called basic variables.

 

Basic Feasible Solution (BFS) : A solution which is basic as well as feasible is called basic feasible solution.

 

Degenerate BFS : If a basic variable takes the value zero in a BFS, then the solution is said to be degenerate.

 

Optimal BFS : The BFS which optimizes the objective function is called optimal BFS.

:

Basically if all the points on a line segment forming by two points lies inside the set/geometric figure then it is called convex.

 

(b) Extreme point or vertex or corner point of a convex set : It is a point in the convex set which can not be expressed as A.x1 + (1 - A.}xz where x1 and x2 are any two points in the convex set.

 

For a triangle, there are three vertices, for a rectangle there are four vertices and for a circle there are infinite number of vertices.

 

(c) Let Ax = b be the constraints of an LPP. The set X = {x I Ax = b, x :2': 0} is a convex set.

 

Feasible Solution : A solution which satisfies all the constraints in LPP is called feasible solution.

 

Basic Solution : Let m = no. of constraints and n = no. of variables and m < n. Then the solution from the system Ax = b is called basic solution. In this system there are  ncm  number of basic solutions. By setting (n - m) variables to zero at a time, the basic solutions are obtained. The variables which is set to zero are known as 'non-basic' variables. Other variables are called basic variables.

 

Basic Feasible Solution (BFS) : A solution which is basic as well as feasible is called basic feasible solution.

 

Degenerate BFS : If a basic variable takes the value zero in a BFS, then the solution is said to be degenerate.

 

Optimal BFS : The BFS which optimizes the objective function is called optimal BFS.