Quantitative Analysis for Management Decision

Lecture 3
Linear programing (LP)
Cost Minimization
Course leader : Shewayirga Assalf (Ass.Pro.)
 LP: Cost Minimization

 A minimization problem minimizes the value of the

objective function rather than maximizing it.
Minimization problems generally involve finding the least-
cost way to meet a set of requirements.
 Problem of Minimizing C

Minimize C= 50x1 + 20x2

Subject to
2x1 – x2> 0
x1 + 4x2 > 80
0.9x1 + 0.8x2 >40
Where x1 ,x2 > 0 non- negativity condition.
 Solution:
 The first step is skipped as LP problem is already
formulated. We will follow other steps simultaneously. In
constraint (i) 2x1 –x2 > 0 there is no constant value, hence
it must pass through the origin. First convert it into
equality.

2x1 –x2 > 0 . Now give x1 any arbitrary value.

When x1 =0, x2=0

x1 =1, x2=2

x1 =2, x2=4 and so on.

 nt

d and get line I drawn in the graph
We draw the line with these coordinates
passing through origin.
 Now, convert constraint (ii) in equality
x1 + 4x2 = 80
When x1 =0, x2=20
X2 =0, x1=80
 We draw the line II (80, 20) as shown in graph.
 Now, convert constraint (iii) in equality
0.9x1 + 0.8x2 =40
 When x1 =0, x2=50
X2 =0, x1=44.4
 We draw line III (44.4, 50) as shown in graph.
contd
 contd

 For feasible area we need to examine all the there constraints

equations (Note, all are > type)

 In equation (i) if we move vertically upward, meaning x1=o and

x2 increasing, the equation becomes negative or less than, which
is not permitted. Hence feasible area should be on RHS.

 In equation (ii), the feasible area should be above the line

because it is greater than the sum of x1 and x2.

 Similarly in equation (iii) it is on the RHS therefore feasible area

(region) is indicated by three rows or shading and extends upto
infinity.
 Contd
 Now we have to find out different values of Z at different corner
points, B,C,E by finding out their coordinates (x1, x2) then putting
them in objective function Z. The point which gives the minimum
value is the answer.

At corner B x1=16,x2=32 therefore Z= 1440

At corner C x1=34.4,x2=11.4 therefore Z= 1948

At corner E x1=80,x2=0 therefore Z= 4000

From the above we can see that minimum value of Z is at point B
where x1=16 and x2 =32 and hence it is the answer.
 Class exercise
feeding farm animals.

 Animals need:

 14 units of nutrient A, 12 units of nutrient B, and 18 units of nutrient C.

Two feed grains are available, X and Y.

 A bag of X has 2 units of A, 1 unit of B, and 1 unit of C.

 A bag of Y has 1 unit of A, 1 unit of B, and 3 units of C.

 A bag of X costs $2. A bag of Y costs $4.

 Required: 1. Minimize the cost of meeting the nutrient requirements.

2. Solve the problem graphically

3. Find the optimal solution in the graph

 Answer
Feed Nutrients cost
grains A B C
X 2 1 1 2
Y 1 1 3 4
Total 14 12 18
needs
 Change inequalities in to equalities


X1 X2 X1 X2
X1 X2
0 14 0 12
7 0 0 6
12 0
18 0

(7, 14) (12, 12) (18, 6)

 Plot the graph
X2
14 A 2X1+X2= 14

12

10
2X1+X2= 14
B
8

4 C
2X1+X2= 14
2
D
X1
0 2 4 6 8 7 10 12 14 16 18
Optimum solution
 Special Cases in Graphical solution
1. Redundant Constraint
• If a constraint when plotted on a graph doesn’t form part of the
boundary making the feasible region of the problem that constraint
is said to be redundant.
• Example:
 Cont ..
2. Multiple optimal Solutions
• /Alternative optimal solutions/
• -This is a situation where by a LPP has more than
one optimal solution.
• Multiple optimal Solutions will be found if two
corers give optimal solution, then the line segment
joining these points will be the solution.
 Cont….
• ==>We have unlimited number of optimal solution with out increasing or
decreasing the objective function.
•
• Example:
• The information given below is for the products A and B.
• __________________________________________________________________
___
Machine hours per week Maximum available
• Department Product A Product B
per week
• __________________________________________________________________
___
• Cutting 3 6 900
• Assembly 1 1 200
• Profit per unit $8 $16
• __________________________________________________________________
___
• Assume that the company has a marketing constraint on selling products B and
therefore it can sale a maximum of 125units of this product.
Cont…
• Required:
a. Formulate the LPP of this problem
b. Find the optimal solution
Solution:
• Let X1 =The No of units f product A produced per week
• X2 =The No of units f product B produced per week
• The LPP Model of the problem is:
Cont…
 cont.
Corners Coordinates MaxZ=8 X1 + 16X2

A (0, 0) 0

B (0, 125) 2000

C (50, 125) 2400

D (100, 100) 2400

E (200, 0) 1600

Interpretation:

Both C and D are optimal solutions. Any point on the line segment CD will also lead to the same optimal solution.

==>Multiple optimal solutions provide more choices for management to reach their objectives.

3. Infeasible Solution
A solution is called feasible if it satisfies all the constraints and the constraints and non-negativity condition.

However, it is sometimes possible that the constraints may be inconsistent so that there is no feasible solution to the problem. Such a situation is called infeasibility.

Example:

MaxZ=20X1 +30X2

St:

2X1 +X2 < 40

4X1 +X2 < 60

X1 > 30

X1 , X2 > 0

Solution:
cont