LINEAR
PROGRAMMING
MINIMIZATION MODEL
LEARNING
OUTCOMES:
a. Formulate Linear Programming – Minimization Model
ADDITIONAL TO
MAXIMIZATION MODEL
SLACK VARIABLE
Is added to a ≤ constraint to convert it to an equation (=).
Represents unused resources.
For the pottery company example, the model constraints are:
x + 2y ≤ 40 hrs of labor
4x + 3y ≤ 120 lb of clay
The addition of a unique slack variable, s1 to the labor constraint and
s2 to the constraint for clay:
x + 2y + S1 ≤ 40 hrs of labor
4x + 3y + S2 ≤ 120 lb of clay
ADDITIONAL TO
MAXIMIZATION MODEL
The slack variables in these equations, S1 and S2 , will take on
any value necessary to make the left-hand side of the equation
equal to the right-hand side.
For example, x = 5 and y = 10
x + 2y + S1 = 40 hrs of labor
5 + 2(10) + S1 = 40 hrs of labor
S1 = 15 hrs of labor
and
4x + 3y + S2 = 120 lb of clay
4(5) + 3(10) + S2 = 120 lb of clay
S2 = 70 lb of clay
ADDITIONAL TO
MAXIMIZATION MODEL
Slack in Objective Function
Contributes nothing to profit because they represent
unused resources. Profit is only made after the resources
are used in production.
Maximize Z = 40x + 50y + 0s1 + 0S2
Slack in decision variable
Slack can only have non negative values because negative
resources are not possible.
x, y, S1, S2 ≥ 0
Slack in decision variable
The complete linear programming model can be written in what
referred to as standard form with slack variables as follows:
Maximize Z = 40x + 50y + S1 + S2
Subject to
x + 2y + S1 = 40
4x + 3y + S2 = 120
x, y, s1, S2 ≥ 0
Solution Summary with Slack
Point Solution Values Z Slack
A X = 0 bowls, Y = 20 mugs P1,000 S1 = 0 hr, S2 = 60 lb
B X = 24 bowls, Y = 8 mugs P1,360 S1 = 0 hr, S2 = 0 lb
C X = 30 bowls, Y = 0 mugs P1,200 S1 = 10 hr, S2 = 0 lb
MINIMIZATION MODEL
Formulated the same basic way as a maximization problem,
except for a few minor differences
A minimization model looks for the optimal solution to
decrease the objective value and involves some ≥ constraints.
The opposite of maximization is the minimization model.
Refers to the study of problems in which one seeks the
minimization of an objective function by systematically
choosing the values of real integer variables from within an
allowed set.
The minimization model starts with an objective function
with the purpose of minimizing a goal which can be in the
form of expenses or cost, travel time, distance, energy, or any
variable wherein less is desired.
MODEL CONSTRUCTION
A farmer is preparing to plant a crop in the spring and needs to
fertilize a field. There are two brands of fertilizer to choose from,
Super-gro and Crop-quick. Each brand yields a specific amount of
nitrogen and phosphate per bag, as follows:
Chemocal Contribution
Nitrogen
Phosphate
(lb./bag)
Brand (lb./bag)
Super-gro 2 4
Crop-quick 4 3
MODEL CONSTRUCTION
The farmer’s field requires at least 16 pounds of nitrogen and at
least 24 pounds of phosphate. Super-gro costs $6 per bag, and Crop-
quick costs $3. The farmer wants to know how many bags of each
brand to purchase in order to minimize the total cost of fertilizing.
Summary pf LP Model Formulation Steps
Step 1: Define the decision variables
How many bags of Super-gro and Crop-quick to buy
Step 2: Define the objective function
Minimize cost
Step 3: Define the constraints
The field requirements for nitrogen and phosphate
DECISION VARIABLES
x = bags of Super-ego
y = bags of crop-quick
THE OBJECTIVE FUNCTION
minimize Z = P6x + 3y
where
6x = cost of bags of Super-ego
3y = cost of crop-quick
MODEL CONSTRAINTS
2x + 4y ≥ 16 lb
4x + 3y ≥ 24 lb
where
2x and 4x = the nitrogen contribution per bag of Super-gro
4y and 3y = the phosphate contribution per bag of Crop-quick
The complete model formulation for this minimization problem is
Min z = 6x + 3y
subject to
2x + 4y ≥ 16 lb of nitrogen
4x + 3y ≥ 24 lb of phosphate
x,y ≥ 0
GRAPHICAL METHOD
We follow the same basic steps in the graphical solution of a minimization model as in a
maximization model
GRAPH THE CONSTRAINTS
THE OPTIMAL SOLUTION
a maximization problem, the optimal solution is on the boundary of the feasible
solution area that contains the point(s) farthest from the origin.
The optimal solution point in a minimization problem is also on the boundary of
the feasible solution area; however, the boundary contains the point(s) closest to
the origin (zero being the lowest cost possible)
As the objective function edges toward the origin, the last point it touches in the feasible
solution area is A.
In other words, point A is the closest the objective function can get to the origin without
encompassing infeasible points.
Thus, it corresponds to the lowest cost that can be attained
The final step in the graphical solution approach is to solve for the values of and at point
A. Because point A is on the axis, ; thus,
4(0) + 3y = 24
3y = 24
y=8
z = 6x + 3y
z 6(0) + 3(8)
z = 24
This means the farmer should not purchase any Super-gro but, instead, should purchase
eight bags of Crop-quick, at a total cost of $24.
SURPLUS VARIABLES
is subtracted from a ≥ constraint to convert it to an equation (=).
It represents an excess above a constraint requirement level.
2x + 4y – m = 16
Hypothetical example: x = 0 and y = 10
Substituting these values into previous equation yields.
2(0) + 4(10) – m = 16
- m = 16 – 40
m = 24 lb of nitrogen
24 is the extra amount of nitrogen above the minimum requirement of 16 pounds that
would be obtained by purchasing 10 bags of Crop-quick fertilizer.
4x + 3y – n = 24
As in the case with slack variables, surplus variables contribute nothing to the overall cost
of a model.
Putting additional nitrogen or phosphate on the field will not affect the farmer’s cost.
Affected → number of fertilizer purchased
Minimize Z = 6x + 3y + m + n
Subject
2x + 4y – m = 16
4x + 3y –n = 24
x,y,m,n ≥ 0
REFERENCES:
Introduction to Management Science by Taylor III
GROUP 5
Kaila Agna
Jasmin Alamer
Riziel Lasangue
Norria Shella Madeja
Mariza Montanez
Jasmin San Juan
