Skip to main content

Graphical Method to Solve a Linear Programming Problem


The graphical method is applicable to solve the LPP involving two decision variables x1, and x2, we usually take these decision variables as x, y instead of x1, x2. To solve an LPP, the graphical method includes two major steps:

a)  The determination of the solution space that defines the feasible solution.  Note that the set of values of the variable x1, x2, x3,....xn which satisfy all the constraints and also the non-negative conditions are called the feasible solutions of the LPP.
b)  Finding the optimal solution from the feasible region.

a)To determine the feasible solutions of an LPP, we have the following steps:

Step 1: Consider only the first quadrant of xy-coordinate plane(because both the variables x1 and x2 are non-negative).

Step 2: Each equation is of the form ax+by≤c or ax+by≥c.
Draw the line ax+by=0.
For each equation, the line divides the first quadrant into two regions say R1 and R2. Suppose (x1, 0) is a point in R1. If this point satisfies the equation ax + by ≤ c or ax+by ≥ c, then shade the respective region i.e R1. If (x1, 0) does not satisfy the inequality, shade the other region i.e R2.

Step 3: Corresponding to each constant, we obtain a shaded region. The intersection of all these shaded regions is the feasible region or feasible solutions of the LPP.

b) The optimal solution to a LPP, if it exists, occurs at the corners of the feasible region. The method of finding the optimal solution includes the following steps :

Step 1: Find the feasible region of the LLP.

Step 2: Find the co-ordinates of each vertex of the feasible region. These co-ordinates can be obtained from the graph or by solving the equation of the lines.

Step 3: At each vertex (corner point), compute the value of the objective function.

Step 4: Identify the corner point at which the value of the objective function is maximum (or minimum depending on the LPP). The co-ordinates of this vertex is the optimal solution and the value of Z is the optimal value.

Special Cases

1.  Multiple Optimal Solutions
Situations may arise when the optimal solution obtained is not
unique. This happens when the line representing the objective
function is parallel to one of the lines bounding the feasible
region.

2.  Infeasible Solutions
In some case, there is no feasible solution area, i.e., there are no
points that satisfy all constraints of the problem. An infeasible
LPP with two decision variables can be identified through its
graph.

3.  Unbounded Solutions
In some cases, a solution might be obtained whose objective
function is infinite. If the feasible region is unbounded then one
or more decision variables will increase indefinitely without
violating feasibility, and the value of the objective function can be
made arbitrarily large.





Labels:

Comments

Post a Comment

Popular posts from this blog

Advantages and Disadvantages of EIS Advantages of EIS Easy for upper-level executives to use, extensive computer experience is not required in operations Provides timely delivery of company summary information Information that is provided is better understood Filters data for management Improves to tracking information Offers efficiency to decision makers Disadvantages of EIS System dependent Limited functionality, by design Information overload for some managers Benefits hard to quantify High implementation costs System may become slow, large, and hard to manage Need good internal processes for data management May lead to less reliable and less secure data
1 comment
Read more

Inter-Organizational Value Chain

The value chain of   a company is part of over all value chain. The over all competitive advantage of an organization is not just dependent on the quality and efficiency of the company and quality of products but also upon the that of its suppliers and wholesalers and retailers it may use. The analysis of overall supply chain is called the value system. Different parts of the value chain 1.  Supplier     2.  Firm       3.   Channel 4 .   Buyer
Post a Comment
Read more

Big-M Method and Two-Phase Method

Big-M Method The Big-M method of handling instances with artificial  variables is the “commonsense approach”. Essentially, the notion is to make the artificial variables, through their coefficients in the objective function, so costly or unprofitable that any feasible solution to the real problem would be preferred, unless the original instance possessed no feasible solutions at all. But this means that we need to assign, in the objective function, coefficients to the artificial variables that are either very small (maximization problem) or very large (minimization problem); whatever this value,let us call it Big M . In fact, this notion is an old trick in optimization in general; we  simply associate a penalty value with variables that we do not want to be part of an ultimate solution(unless such an outcome is unavoidable). Indeed, the penalty is so costly that unless any of the  respective variables' inclusion is warranted algorithmically, such variables will ...
Post a Comment
Read more