Formulation of Linear Programming Problem

FORMULATION OF LINEAR PROGRAMMING PROBLEM (LPP):

Formulation of a Linear Programming Problem involves constructing a mathematical model from the given data. This can be done only if the following requirements are met:

• There should be a clearly identifiable objective and it should be measurable in quantitative terms. E.g. In a manufacturing problem the objective can be maximisation of profit or minimisation of cost.
• The resources to be allocated in the problem should be identifiable and quantitatively measurable. E.g. The use of labour time, or raw material in the manufacturing process should be clearly stated.
• The relationships representing the objective function and the constraints equations must be linear.
• There should be a series of feasible alternative courses of action available to the decision maker. These are determined by the resource constraints.

When all the above mentioned conditions are satisfied the problem can be expressed as L.P. problem. Then solve it for an optimal solution.

Let us first illustrate the formulation of LPP.

We have seen that a typical LPP. has three components:

1. Objective function
2. Constraints
3. Non-negativity restrictions

Formulation of LPP therefore implies translating the given descriptive problem into these three sets of linear relationships between the decision variables.

METHODS OF SOLUTION:

Solving an Linear Program problem involves:

• Selection of appropriate method of solution and
• Then obtain a solution to the problem with the help of selected method
• Test whether this solution is optimal.

The problem can be solved by using:

• Graphical method: This method can be used if there are only two decision variables in the LPP.
• Simplex method: This method is useful in solving LP problems with two or more than two decision variables.

The Graphical method of solution: This method can be used in case where LPP has only two decision variables. But there is no restriction on the number of constraints. The method uses the familiar graphical presentation with two axes. The method becomes unwieldy when there are three variables since we then need a three dimensional graph. The method cannot be used if the number of decision variables is more than three. In such a case we have to use a non graphical method to obtain a solution. The graphical method of solution to L.P. problem uses all the equations in a given problem, namely the equation expressing objective unction the constraints imposed in achieving the objective. These constraints can be of (i) greater than (ii) less than or (iii) strict equality type. There is also a non-negativity restriction on the values of the decision variables. It implies that the solution of the problem lies in the first quadrant of the graph. All these relations are linear.

The Simplex method of solution: The simplex method uses a simplex algorithm; which is an iterative, procedure for finding, in a systematic manner the optimal solution to a linear programming problem. The procedure is based on the observation that if a feasible solution to a linear programming exists; it is located at a corner point of the feasible region determined by the constraints of the problem. The simplex method, selects the optimal solution from among the set of feasible solution to the problem. The algorithm is very efficient as it considers only those feasible solutions, which are provided by the corner points. Thus, we need to consider a minimum number of feasible solutions to obtain an optimal one. The method is quite simple and the first step requires the determination of basic feasible solution. Then, with the help of a limited number of steps the optimum solution can be determined.