Linear Programming Special Cases PDF

Preview

Summary

Summary of linear programming - special case...

Description

On linear programming method, there are several requirements which have to be fulfilled, one of them is the objective function. The objective function, on linear programming method, usually seek to either maximized or minimized the resource allocation. The different objective function, also make different treatment to be given to solve the problem. Not all of the resource should be maximized, in real life situation, the managers also seek the best way how to minimize the use of the money in most of the company. The company usually seek the best way how to minimized the outcome of the company, but still, they get the best result and benefit of every money they have spent. Minimizing cost, minimizing employees, and minimizing time to produce and even other real life problem on business, can be done with the linear programming method. We can identify how to minimize or maximize method, with only looking on the inequalities sign. After we graph the inequalities or the equalities, we have to find the feasible region. After that; There are two ways to solve the minimize method on linear programming: 1. Isocost method. 2. Corner point method.

FOUR SPECIAL CASES IN LINEAR PROGRAMMING In doing Linear Programming, sometimes there can be several cases and difficulties when using the problems. Here we are discussing about 4 special cases that can happen everywhen. 1. No feasible approach This cases happen when there is no solution to our Linear Programming problem because there is no solution that can satisfy all of the constraints. It can indicates some errors in formulating the problem or in entering the data. It can also exist when the management’s expectation is too high or because of too many constraints being placed in the problem. Example = Maximize

Z = 3X1 + 2X2

Constraints

X1+ X2 ≤ 1 X1+ X2 ≥ 3 X 1 ≥ 0 , X2 ≥ 0

Put X1 =0, then X2 = 1 on the first constraint. Then put X2 =0, then X1 = 1 The coordinates are (0, 1) and (1,0). Write the second constraint in a form of equation X 1+ X2 = 3 Put X1 =0, then X2 = 3 Put X2 =0, then X1 = 3 The coordinates are (0, 3) and (3, 0) 5

by

There is no feasible region generated

4 3

is

two constraints together, hence there

2 1

no optimal solution. 1

2

3

4

5

6

7

2. Unboundedness This case happens when there come an infinite solution or open ended solution. Example =

Maximize

Z = 3X1 + 5X2

Constraints

2X1+ X2 ≥ 7 X1+ X2 ≥ 6 X1+ 3X2 ≥ 9 X 1 ≥ 0 , X2 ≥ 0

Write the first constrain in a form of equation 2X1+ X2 = 7 Put X1 =0, then X2 = 7 Put X2 =0, then X1 = 3.5 The coordinates are (0, 7) and (3.5, 0) Write the second constarint in a form of equation X 1+ X2 = 6 Put X1 =0, then X2 = 6 Put X2 =0, then X1 = 6 The coordinates are (0, 6) and (6, 0) Write the third constraint in a form of equation X1+ 3X2 = 9 Put X1 =0, then X2 = 3 Put X2 =0, then X1 = 9 The coordinates are (0, 3) and (9, 0)

7

Because this maximation problem and the 6

Feasible region extends infinitely to the

5 4

right, there is unbounded solutions.

3 2 1 1

2

3

4

5

6

7

8

9

3. Redundancy A redundant constraint is the one that does not affect the feasible solution region in the graph. Example = Minimize

4X + 5Y

Constraint

X + 3Y ≥ 30 3X + 4Y ≥ 120 X ≥ 10

X, Y ≥ 0

40 30 20 10

10

20 30 40 50 60

Redundant Constraint. It is overshadowed by the other constraint. Thus this constraint do not touch the feasible region at all. 4. Alternate Optimal Solutions This case occurs when the objective function line is parallel to a binding constraints. Example = Maximization 2X + 6Y Constraints

X + 3Y ≤ 60 3X + 4Y ≤ 120 X ≥ 10 X, Y ≥ 0

In this case, the objective functions and the first constraint line have the same slope (parallel). 40

2X + 6Y = 2 (X + 3Y)

30

X + 3Y ≤ 60

20

These same slope then make the objective function

10

line coincides with the constraint line.

10

20 30 40 50 60

Sensitivity Analysis Finding the optimal solution that has been found under deterministic assumptions to a linear programming model is important, so that we can assume certainty in the variables’ condition regarding their data and relationships. But, it is not the only information available. There is a tremendous amount of sensitivity information, or information about what happens when data values are changed. Decision making is an integral part of operations management. It may be useful to a decision maker to have some indication of how sensitive an alternative choice might be to the changes in one or more of those values. Analyses are used to examine the effects of changes in three areas: 1. Contribution rates for each variable 2. Technological coefficients 3. Available resources

Unfortunately, it is not possible to explore all the possible combinations of all the variables in a typical problem. In spite of this, there are some elements that a decision maker can use to assess the sensitivity of assumption probabilities. One of the tools useful for the analysis in some decision making problems is sensitivity analysis. It provides a range of feasibility over which the choice of alternative remains the same. Sensitivity analysis offers

a better understanding of

the problem, different effects

of

limitations and “what if” questions. There are two approaches to conduct sensitivity analysis in order to determine how sensitive an optimal solution is to changes. 1. Trial-and-error approah

Usually involves resolving the entire problem, preferably by computer, each time one input data item or parameter is changed. It can take long time to test a series of possible changes in this way. 2. Analytic postoptimality method Done without resolving the whole problem, examines changes after the optimal solution has been reached. Changes in the Objective Function Coefficient 

Current optimal solution may remain optimal if the changes in the coefficient is not too large. However, if the changes in the coefficient is significant, the optimal solution might move to another corner point.



Eventhough the feasible region remains the same, the slope of isocost and isoprofit will change in the graph.



QM for Windows & Excel provides answer for how much the objective function coefficient be changed before another corner point becomes optimum.

Changes in the Technological Coefficients 

Technological coefficient often reflects changes in the state of technology



If fewer or more resources are needed to produce a product coefficient in the constraint equation will change



These change will have no effect on the objective function of an LP problem



But they can produce a significant change in the shape of the feasible solution region, and

Changes in the Resources or Right-Hand-Side Values 

The right-hand-side values of the constraints often represent resources available to the firm.





If the right-hand side of a constraint is changed: -

The feasible region will change (unless the constraint is redundant),

-

The optimal solution mostly will change.

The amount of a change in the objective function that results from a unit change in one of the resources available is called the dual price or dual value.



The dual price for a constraint is the improvement in the objective function value that results from a one-unit increase in the right-hand side of the constraint.



The dual price of a resource indicates the amount the objective function can be increased (or decreased) given another unit of the resource.



If the number of hours increased beyond the upper bound, then the objective function would no longer increase.



-

There would simply be excess (slack) hours of a resource.

-

Thus, the dual price is relevant only within limits.

Both QM for Windows and Excel Solver provide these limits.



Dual prices will change if the amount of the resource (the right-hand side, RHS, of the constraint) goes :  above the upper bound or  below the lower bound given in the Ranging section of the QM for Windows output.



Solver gives the shadow price instead of the dual price.



The shadow price in the Excel output is the equivalent to the dual price for a maximization problem in QM for Windows.

Prima Putri Citra Wardhani

041511333012

Ghassani Awasnis

041511333013

Elshabyta Auditya Bintarto

041511333029

Meta Yunita Pramasetio

041511333166...