Scribd
Upload
20 views

Group 5 Linear Programming Minimization Model

This document discusses linear programming minimization models. It explains how to formulate a minimization model, which is similar to a maximization model but seeks to minimize an objective function rather than maximize it. Slack and surplus variables are introduced, which are added to inequality constraints to convert them to equations. These variables represent unused resources or excess above a requirement. An example minimization problem is presented about a farmer choosing fertilizer to minimize costs. The model is constructed and graphically solved to find the optimal solution.

Uploaded by

Kaila B. Agna
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views

Group 5 Linear Programming Minimization Model

This document discusses linear programming minimization models. It explains how to formulate a minimization model, which is similar to a maximization model but seeks to minimize an objective function rather than maximize it. Slack and surplus variables are introduced, which are added to inequality constraints to convert them to equations. These variables represent unused resources or excess above a requirement. An example minimization problem is presented about a farmer choosing fertilizer to minimize costs. The model is constructed and graphically solved to find the optimal solution.

Uploaded by

Kaila B. Agna
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

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

You might also like