Linear Programming Problem (LPP)


Operations Research is concerned with scientifically designing how to best design and operate man-machine systems usually under conditions requiring the allocation of source resources.

Linear Programming is such a mathematical modelling technique designed to optimize the usage of limited resources.

Example: A company produces both interior and exterior paints from two raw materials M1 and M2. The following table provides basic data on the problem.

A market survey restricts the maximum daily demand for interior paints of 2 tons. Additionally, the daily demand for interior paints cannot exceed that of exterior paints by more than 1 ton. The company wants to determine the optimum product mix of the two paints that maximize the total daily profit.

 

 

Terminology: The LP model included three basic elements:

  • Decision variables that we seek to determine.
  • Objective function that we seek to optimize.
  • Constraints that we need to satisfy.

Thus in the example problem, let

  • x_1= Tons of exterior paints produced daily.
  • x_2= Tons of interior paint produced daily.
  • x_3=The total daily profit.

Then objective is to maximize: x_0=5x_1+4x_2, subject to:

  • 6x_1+4x_2 \leq 24
  • x_1+2x_2
  • x_2 \leq 2
  • -x_1+x_2 \leq 1
  • x_1, x_2 \geq 0

Assumptions: Intrinsic in the linearity assumption are the following two topics:

  • Proportionality:  Contribution of each precision variable in both objective function, and the constraints to be directly proportional to the value of the variable
  • Additivity: Speculates that total contribution of all the variables in the objective functions, and in the constraints be the direct sum of individual contribution of each variable.

 

Notations:  Here are some common notations used in this context:

  • Slack Variable: For constraints of the \leq type, the RHS normally represents the limit on the availability of a resource, and the LHS represents the usage of this limited resource by different activities (variables of the model). A slack thus represents the amount by which the available amount of the resources exceeds it’s usage by the activities.
  • Surplus Variable: Constraints of the type \geq normally set minimum specification requirements. This case, a surplus variable represents the excess of the LHS over a minimum requirements.
  • Unrestricted Variables: In some situation it becomes necessary to introduce a variable with both positive and negative values. For example, consider an investment problem where an investor has 50$ cash on hand, and borrow money if necessary for investment. The investment constraint can be written as x_1+s_1=50, where s_! is positive or negative depending on whether it represents money saved or money borrowed. This type of variables are called unrestricted variables.

Standard LP Form: The standard LP form has the following proerties.

  • All the constraints (except the non-negativity constraints) are equations with non-negative RHS.
  • All variables are non-negative.
  • The objective function may be of minimization or maximization type.

Example: 

  • x_1+x_2 \leq 3 \Rightarrow x_1+2x_2+s_1=3, where s_1 \geq 0 is a slack variable
  • 5x_1+8x_2 \geq 5 \Rightarrow 5x_1 +8x_2 -s_2  =5, where s_2 \geq 0 is a surplus variable.
  • If x_j is an unrestricted variable, we can write: x_j=x_j^+-x_j^-, where x_j^+, x_j^- \geq 0.
  • For restricted variables, if x_j \geq p, \Rightarrow x_j'=x_j-p \geq 0 , and if x_j \leq p, \Rightarrow x_j''=-x_j+p \geq 0.

We can write a Linear Programming Problem as:

Max(x_0)=cx \textrm{         such that           }Ax=b  \textrm{    } (x \geq 0)

  • A feasible solution is a non-negative vector x satisfying the constraints Ax=b
  • Feasible region denoted by \mathbb{S} is the set of all feasible solution such that \mathbb{S} = \left \{ x:Ax=b | x \geq 0 \right \}. If the feasible set is empty, then the LP is said to be infeasible.
  • An optimal solution is a vector x_0 such that it is feasible and it’s value of the objective function cx_0 is larger than that of any other feasible solution. Thus,  x_0 is optimal iff x_0 \in \mathbb{S} \textrm{   and   } cx_0 \geq cx \forall x \in \mathbb{S}.
  • Optimal value of the LP is the value of the objective function corresponding to the optimal solution.
  • When the LP has more than one optimal solution, it is said to have alternative optimal solution.
  • When a LP does not process a finite optimum, it is said to have unbounded solution.
  • A variable is said to be a basic variable in a given equation if it appears with an unit coefficient in the equation and 0 in all other equations. The variables which are not basic are called non-basic variables.
  • A pivot operation is a sequence of elementary operations that reduce a given system to an equivalent system in which a specified variable has a unit coefficient in one equation and 0 elsewhere.
  • The solution obtained by setting the non-basic variables to 0 and solving for the basic variables is called the basic solution.
  • A Basic Feasible Solution (BFS) is a basic solution in which the values of the basic variables are non-negative.
  • So, with m constraints and n variables, the maximum number of basic solutions to a standard LP is finite and given by _{m}^{n}\textrm{C}.  Naturally, this also gives an upper bound for the number of BFS.

Solving a Linear Programming Problem:

On inspection, it can be seen that whenever there is an optimal solution to a linear program, one of the corner points of the feasible regions is always optimal. Also, every corner point of the feasible region corresponds to BFS of the constrained equations. This means that an optimal solution to a linear program can be found by merely examining the BFS’s. The simplex method does this in a very efficient manner. I will discuss the Simplex method in further details in my next post.

 

Leave a comment

Your email address will not be published. Required fields are marked *