Wednesday, February 13, 2013

How to solve linear programming problems

Linear Programming is one of the operations research techniques. It is one of the best mathematical techniques for finding the limited use of resources of a concern in a best way. Complex problems can be modeled using linear functions in a presentable way by the management. The linear programming technique is used in solving a wide range of operations management problems.

Definition of linear programming problems:

Linear Programming is defined as a technique which allocates the available resources in an optimum manner for achieving the company’s objective which is for maximizing the overall profit or to minimize the overall cost under conditions of certainty.

Linear Programming can be applied to areas which are given below:

Allocation of resources to various activities of the concern, for example: man power, machine etc.
Production scheduling.
The common characteristics in the above mentioned areas are to allocate limited resources to the activities of the concern.

I like to share this First Order Linear Differential Equation with you all through my article.

How to solve Linear Programming Problems: Mathematical Formulation

Linear Programming can be used in a variety of situations. In most of the business or economic situations, the resources will be limited, the problem there will be to make use of the available resources in such a way as to maximize the production or to maximize the profit or to minimize the expenditure. This can be formulated as linear programming models.

Mathematical Formulation of the problem:

How to solve linear programming problems?? here are the steps which you need to follow:

Step 1:

Write down the decision variables of the problem.

Step 2:

Formulate the objective function to be optimized as a linear function of the decision variables.

Step 3:

Formulate the other conditions of the problem as Linear equations or In equations in terms of the decision variables.

Step 4:

Add the non negativity constraint from the consideration that negative values of the decision variables do not have any valid physical interpretation.

The objective function, the set of constraints, and the non negative constraints together form an LPP.

Steps to solve linear programming problems using Graphical Method:

When a LPP has only two variables in the objective function and constraints, it can be easily solved using the graphical method. The given information of a LPP can be plotted on the graph and the optimal solution can be obtained from the graph.

The steps to solve an Linear Programming Problem using Graphical method is given below:

Step 1:

Identify the decision variables, the objective function and the restrictions for the given Linear Programming Problem (LPP).

Step 2:

Write the Mathematical Formulation of the problem.

Step 3:

Plot the points on the graph representing all the constraints of the problem. Find the feasible region or solution space. The intersection of all the regions represented by the constraints of the problem is called the feasible region and is restricted to the first quadrant only.

Step 4:

The Feasible region obtained in the step 3 may be bounded or un bounded. Determine the Co-ordinates (x, y) values of all the corner points of the feasible region.

Step 5:

Find the value of the objective function at each corner points (solution) determined in step 3.

Step 6:

Select a point from all the corner points that optimizes (Maximizes or Minimizes) the values of the objective function. It gives the Optimum Feasible Solution.

Understanding graphing systems of linear equations is always challenging for me but thanks to all math help websites to help me out.

Some Exceptional Cases of Linear Programming Problem:

There may be an LPP for which no solution exists or for which the only solution obtained is an unbounded one. The exceptional cases arise in the application of graphical method are

  • Alternative Optima
  • Unbounded Solution
  • Infeasible Solution or Non existing Solution
Alternative Optima:

When the objective function is parallel to the binding constraint, the objective function will assume the same optimal value at more than one solution point, because of this reason, they are called as Alternative Optima.

Unbounded Solution:

When the values of the decision variables may be increased in definitely without violating any of the constraints, the feasible region is unbounded. In such cases, the value of the objective function may increase (for maximisation) or decrease (for minimisation) in definitely. Thus, both the solution space and the objective function value are unbounded.

Infeasible Solution:

When the constraints are not satisfied simultaneously, the LPP has no feasible solution. This solution can never occur, if all the constraints are of less than or equal to type.

Example for some exceptional cases:

The general form of the LPP is used to develop the procedure for solving a common programming problem.

A standard LPP Some exceptional cases is of the form
Max (or min) Z = c1x1 + c2x2 + … +cnxn
x1, x2, ....xn these are called decision variable.

Ex: Show graphically that the model

Maximize Z = -5y

Subject to

x+y<span style="font-family: Serif;">?</span> 1

0.5x-5y<span style="font-family: Serif;">?</span> -10

x<span style="font-family: Serif;">?</span> 0

y<span style="font-family: Serif;">?</span> 0 has no feasible solution.


Draw the graphs x + y = 1

- 0.5 -5y = - 10

Shade the half planes of the constraints x + y 1 …(1)

-0.5x - 5y -10 …(2)

Points are (0,1)(0,2)(1,0)(20,0)

Note that the origin (0, 0) does not satisfy the in 2nd equation hence the required region is the upper half plane.

From the graph, that the intersection of the constraints is empty. Therefore the given problem has no feasible solution. So, the some exceptional cases of given LPP has no solution.

Having problem with conservation of linear momentum equation Read my upcoming post, i will try to help you.

No comments:

Post a Comment