LINEAR PROGRAMMING
Mathematical
LINEAR PROGRAMMING technique that permits the
determination of the best or
optimum use of the
available resources
namely, money, personnel,
materials, facilities and
time.
Two aspects:
Formulation of LP model
Solution part
SPECIFIC APPLICATIONS OF LP 3
Determination of the product mix to maximize
contribution margin
Selection of an investment mix
Determination of materials mix to minimize costs
Assignment of jobs to machine
Determination of transportation routes
FORMULATION OF LP MODEL 4
Define the decision variables
Express the objective function and
constraints in terms of these decision
variables
COMPONEMTS OF LINEAR
PROGRAMMING 5
Decision Variables- mathematical symbols
representing level of activity of a firm
Objective Function- a linear mathematical
relationship describing an objective of the firm, in terms
of a decision variables, that is maximized or minimized
Constraints- restrictions placed on the firm by the
operating environment stated in linear relationships of
the decision variables.
Non-negativity constraints
EXAMPLE
A firm produces two products, A and B. Product A requires two
hours of grinding and four hours of polishing. Product B requires five
hours of grinding and two hours of polishing. The manufacturer has three
grinders and two polishers; therefore in a 40-hour week there are 120
hours of grinding capacity and 80 hours of polishing capacity . There is a
ready market for both products and the contribution margin per unit of
Product A and Product B are P3 and P4, respectively.
To maximize the total contribution margin, the management
must decide on
The allocation of the available production capacity to product A and B
The number of units of each product to produce.
7
hr/unit
PRODUCTS CM per unit
GRINDING POLISHING
A 2 4 3
B 5 2 4
MACHINE CAPACITY 120 80
FORMULATION OF LP MODEL
STEPS:
DECISION VARIABLES:
Let A = the number of units of product A to be produced
B = the number of units of product B to be produced
OBJECTIVE FUNCTION:
Total CM = 3A + 4B
CONSTRAINTS:
Explicit constraints
Grinding = 2A + 5B ≤ 120
Polishing = 4A + 2B ≤ 80
Implicit/non-negativity constraints
A, B ≥ 0
METHODS OF LINEAR PROGRAMMING 9
Graphic Method
Algebraic Method
Simplex Method
GRAPHICAL METHOD
11
LP MODEL
DECISION VARIABLES:
Let A = the number of units of product A to be produced
B = the number of units of product B to be produced
OBJECTIVE FUNCTION:
Total CM = 3A + 4B
CONSTRAINTS:
Explicit constraints
Grinding = 2A + 5B ≤ 120
Polishing = 4A + 2B ≤ 80
Implicit/non-negativity constraints
A, B ≥ 0
Grinding (2A + 5B ≤ 120) Polishing (4A + 2B ≤ 80) 13
if A = 60 B =0 if A = 20, B = 0
A = 0, B = 24 A = 0, B = 40
2A+5B = 120 2A+5B = 120 4A+2B = 80 4A+2B = 80
2(0)+5B = 120 2A+5(0) = 120 4(0)+2B = 80 4A+2(0) = 80
2A = 120 4A = 80
5B = 120 2B = 80
2 2
5 A = 60 2 A = 20
B = 24 B = 40
GRAPHICAL METHOD
A 14
Feasible Region
60 A = 0:; B = 0
A = 20; B= 0
50 A = 0; B = 24
A= 10; B = 20
40
30
20
10
0 B
10 20 30 40 50 60
OBJECTIVE FUNCTION:
Total CM = 3A + 4B 15
A = 0; B = 0 Answer:
= 3(0) + 4(0) = P0 Produce 10 units of A
and 20 units of B. the total
A = 20; B= 0 contribution margin associated
= 3(20) + (0) = 60 with this combination is P110
which is the highest among the
A = 0; B = 24 four combinations.
= 3(0) + 4(24) = 96
A = 10; B = 20
= 3(10) + 4(20) = 110
ALGEBRAIC METHOD
ALGEBRAIC METHOD 17
4A + 2B = 80 4A + 2(20) = 80
2A + 5B = 120 4A = 40 = 80
4A = 80 – 40
4A + 2B = 80 4A = 40
4A + 10B = 240 4
8B = 160 A = 10
B = 20
Total CM = 3A + 4B
= 3(10) + 4(20)
Total CM = P110
SIMPLEX METHOD
SIMPLEX METHOD 19
Objective Function STEP 1:
Total CM = P3A + Grinding = 2A + 5B + S1
P4B + OS2 = 120
Polishing = 4A + 2B +
Constraints: OS1 + S2 = 80
Grinding = 2A +
5B ≤ 120 Maximize CM = 3A + 4B
Polishing = 4A + + OS1 + OS2
2B ≤ 80
A, B, ≥ 0
STEP 2:
0 3 4 0 0 Objective20
Cj Mix Row
Quantity A B S1 S2
Variable Row
0 S1 120 2 5 1 0
Problem Row
0 S2 80 4 2 0 1
Index Row
Zj 0 0 0 0 0
Cj - Zj 0 3 4 0 0
1. Check if it satisfies the constraints and objective.
2. It is the rule in simplex method that the optimum solution for maximization problem
has not been reached if the index row still carries positive values at the completion
of the iteration.
3. To determine the outgoing row, compute for the lowest positive ratio.
S1: 120/5 = 24 S2; 80/2 = 40, therefore S1 should be replaced.
4. The incoming variable is the highest possible value in the index row , i.e. B.
STEP 3:
0 3 4 0 0
Cj Mix B Row
Quantity A B S1 S2
120/5 = 24 21
0 S1 120 2 5 1 0 2/5 = 0.4
0 S2 80 4 2 0 1 5/5 = 1
Zj 0 0 0 0 0 1/5 = 0.2
C j - Zj 0 3 4 0 0 0/5 = 0
0 3 4 0 0 S2 Row
Cj Mix
Quantity a b S1 s2 80 – 2(24) = 32
4 B 24 0.4 1 0.2 0 4 – 2(0.4) = 3.20
0 S2 32 3.2 0 -0.4 1 2 – 2(1) = 0
Zj 96 1.6 4 0.8 0 0 – 2(0.2) = -0.4
Cj - Zj -96 1.4 0 -0.8 0 1 – 2(0) = 1
1. Optimum solution for maximization problem has not been reached if the index row
still carries positive values at the completion of the iteration.
2. To determine the outgoing row, compute for the lowest positive ratio.
B: 24/50.4 = 60 S2; 32/3.2 = 10 therefore S2 should be replaced.
4. The incoming variable is the highest possible value in the index row , i.e. A
STEP 4:
0 3 4 0 0 A Row
Cj Mix 22
Quantity A B S1 S2 32/3.2 = 10
4 B 24 0.4 1 0.2 0 3.20/3.2 = 1
0 S2 32 3.2 0 -0.4 1 0/3.2 = 0
Zj 96 1.6 4 0.8 0 -0.4/3.2 = -0.125
1/3.2 = 0.3125
Cj - Zj -96 1.4 0 -0.8 0
Cj Mix
0 3 4 0 0 B Row
Quantity A B S1 S2 24 – 0.4(10) = 20
4 B 20 0 1 0.25 -0.125 0.4 – 0.4(1) = 0
3 A 10 1 0 -0.125 0.3125 0.2 – 0.4(-0.125)
Zj 110 3 4 0.625 0.4375 = 0.25
Cj - Zj -110 0 0 -0.625 -0.4375 0 – 0.4(0.3125) =
-0.125
1. There is no positive figures anymore in the index row.
2. The optimum strategy therefore is 10 units of A and 2 units of B for a contribution margin of
P110.
SHADOW PRICE 23
The opportunity cost or the monetary
value of the contribution margin that would
be lost by not adding an additional hour of
capacity
ASSIGNMENT
24
A company manufactures and sells two types
of products, A and B. the cost of production of each
unit of A and B is P200 and P150 respectively. Each
unit of A yields a profit of P20 and each unit of B
yields a profit of P15 on selling. Company estimates
the monthly demand of A and B to be at maximum
of 500 units in all. The production budget for the
month is set at P50,000. how many units should the
company manufacture in order to earn maximum
profit from its monthly sales of A and B?
Use Graphical and Algebraic method to solve the
25
END!
