Linear Programming

• The general form of linear programming problem is

Optimize (Maximize or Minimize) Z = c₁x₁ + c₂x₂ + …... + c_nx_n

subject to

a₁₁x₁ + a₁₂x₂ + …. + a_1nx_n (≤, =, ≥) b₁

a₂₁x₁ + a₂₂x₂ + …. + a_2nx_n (≤, =, ≥) b₂

_{….. …...  ….…..}

a_m1x₁ + a_m2x₂ + …. + a_mnx_n (≤, =, ≥) b_m

x₁, x₂, …. , x_n ≥ 0

• If c₁, c₂, …. , c_n are constants and x₁, x₂, …. , x_n are variables, then the linear function Z = c₁x₁ + c₂x₂ + …. + c_nx_n which is to be maximized or minimized is called the objective function.

• Algorithm for formulation of linear programming problem:

Step 1: Identify the decision variables and denote them by x₁, x₂, x₃, ….… .

Step 2: Identify the objective function and express it as a linear function of the variables introduced in the previous step.

Step 3: The objective function may be either in the form of maximizing profits or minimizing costs. So, once you express the objective function as a linear function of decision variables, we must find the type of optimization i.e. maximization or minimization. Identify the type of objective function.

Step 4: Identify the set of constraints, stated in terms of decision variables and express them as linear inequations or equations as the case may be.

• A set of values of variables x₁, x₂, x₃, ….… , x_n is called a solution of LPP, if it satisfies the constraints of LPP.

• A set of values of variables x₁, x₂, x₃, ….… , x_n is called a feasible solution of LPP, if it satisfies the constraints and non-negativity restrictions of the problems.

• A solution of LPP is an infeasible solution if the system of constraints has no point which satisfies all the constraints and non-negativity restrictions.

• The common region determined by all the constraints of LPP is called feasible region and every point of this region is a feasible solution of the given LPP.

• A feasible solution of an LPP is called an optimal feasible solution if it also optimizes the objective function.

• A set is said to be a convex set if every point on the line segment joining any two points in it lies in it.

In the above figure, while the second one is convex, the first one is not since the line segment joining its two points does not completely lie inside the set.

• The set of all feasible solutions of a LPP is a convex set.

• Fundamental Extreme Point Theorem: An optimal solution of a LPP if it exists occurs at one of the extreme points i.e. corner points of the convex polygon of the set of all feasible solutions.

• Slack and Surplus Variables: The positive variables which are generally added on the left side of the constraints to convert them into equalities are termed as slack variables while the positive variables which are subtracted from the left side of constraints to convert them into equalities are termed as surplus variables.

• If the value of an objective function can be increased or decreased indefinitely, such solutions are called unbounded solutions.

• Graphical method of solving a linear programming problem:

• Corner-Point Method:

This method is based on the fundamental extreme point theorem and the algorithm for solving a LPP using this method is stated below:

Step 1: Firstly, formulate the given LPP in mathematical form if it is not given in mathematical form originally.

Step 2: Convert all inequations into equations and draw their graphs. 

Step 3: Determine the region represented by each inequation. The common region thus obtained after satisfying all the inequations and non-negativity restrictions is called feasible region. It is a convex polygon.

Step 4: Identify the vertices or the corner points of the convex polygon. These vertices are also called as the extreme points of the feasible region.

Step 5: Now, compute the values of the objective function at each of the extreme point. The point at which the value of the objective function is optimum (i.e. maximum or minimum depending on the requirement) is the optimal solution of the given LPP.

• Iso-profit / iso-cost method:

The given algorithm should be used for solving a LPP using the iso-cost method:

Step 1: Each constraint is to be considered as an equation.

Step 2: Now, each constraint is to be plotted on the graph as each one will represent a straight line.

Step 3: The common region so obtained satisfying all constraints and non-negativity restrictions is in the form of a polygon and is termed as the feasible region of the given LPP.

Step 4: Next, identify the extreme points of the feasible region so obtained in the last step.

Step 5: In this step, we try to assume some convenient value ‘t’ for the objective function Z and plot the corresponding straight line in the xy-plane.

Step 6: In case, the problem is of maximization type, then draw lines parallel to line Z = t, and the line which is farthest from the origin but has at least one point common to the feasible region. In case of minimization problems, draw lines parallel to the line Z = t and identify the line which is nearest to the origin and has at least one point common to the feasible region.

This common point so obtained is the feasible solution of the given LPP.

• Algorithm for identifying the feasible region:

We shall discuss the two cases separately i.e. ax + by ≤ c and ax + by ≥ c, c > 0

First let us consider the case ax + by ≤ c, c > 0

Firstly, draw the line ax + by = c by joining any two points on it. For this, you will be required to identify two points satisfying the equation. With this straight line, the xy-plane gets divided into two parts. The inequation ax + by ≤ c represents the part of xy-plane lying on that side of ax + by = c in which origin lies.

Next, consider the case ax + by ≥ c, c > 0

Firstly, draw the line ax + by = c by joining any two points on it. For this, you will be required to identify two points satisfying the equation. With this straight line, the xy-plane gets divided into two parts. The inequation ax + by ≥ c represents the part of xy-plane lying on that side of ax + by = c in which origin does not lie.

• Basic feasible solution is a basic solution which satisfies the non-negativity restrictions.

• Every basic feasible solution of the system Ax = b, x ≥ 0 is an extreme point of the convex set of all feasible solutions. The converse also holds good.

• A basic feasible solution which optimizes the objective function is called as the optimum basic feasible solution.

• A hyperplane is defined as the set of points satisfying c₁x₁ + c₂x₂ + ….. + c_nx_n = z (provided not all c_i are zero) which may also be written as cx = z, for given values of c₁, c₂, …... ,c_n and z.

• The entire Eⁿ is divided into three mutually disjoint sets by a hyperplane which are given by 

X₁ = {x: cx > z}

X₂ = {x: cx = z}

X₃ = {x: cx < z}

Here, X₁ and X₃ are open half spaces. The sets {x: cx ≥ z} and {x: cx ≤ z} are closed half spaces.

• A convex combination of a finite number of points x₁, x₂, x₃, ….… , x_n is defined as the point x = a₁x₁ + a₂x₂ + …. + a_nx_n, where all a_i are real and positive and Σa_i = 1.

• The set of all convex combinations of a set of points of X is termed to be the convex hull of the set of points of X.

• The set of all convex combinations of a finite number of points is called convex polyhedron generated by these points.

• Hyperplane, open and closed half spaces are all convex sets.

• Arbitrary intersection of convex sets is a convex set.

• A non-empty set of all feasible solutions of a LPP is a convex set.

• If the optimal value of a LPP is attained at more than one extreme points, then every convex combination of these points is also an optimal solution of the given LPP.