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
- = Tons of exterior paints produced daily.
- = Tons of interior paint produced daily.
- =The total daily profit.
Then objective is to maximize: , subject to:
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 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 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 , where 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.
- , where is a slack variable
- , where is a surplus variable.
- If is an unrestricted variable, we can write: , where .
- For restricted variables, if , and if .
We can write a Linear Programming Problem as:
- A feasible solution is a non-negative vector x satisfying the constraints
- Feasible region denoted by is the set of all feasible solution such that . If the feasible set is empty, then the LP is said to be infeasible.
- An optimal solution is a vector such that it is feasible and it’s value of the objective function is larger than that of any other feasible solution. Thus, is optimal iff .
- 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 . 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.