OR MIDTERM NOTES - Management science is a recognized and

Made By: Trisha POGIIII established discipline in business.

INTRODUCTION - Management science encompasses a logical
What is Operations Research? approach to problem solving.
Operations - Management science can be used in a variety
The activities carried out in an organization. of organizations to solve many different types of
Research problems.
The process of observation and testing
characterized by the scientific
method. Situation, problem statement, model
construction, validation,
experimentation, candidate solutions.

Operations Research is the scientific approach

to execute decision making, which consists of:
• The art of mathematical modeling of complex
situations
• The science of the development of solution
techniques used to solve these models
• The ability to effectively communicate the
results to the decision maker.

Operation Research (OR) is an analytical

approach of problem solving and decision Problem Solving Process
making. -Goal: solve a problem
• In OR, the problem is broken down into steps • Model must be valid
then solved using a mathematical model • Model must be tractable
• It is sometimes also known as Management • Solution must be useful
Science (MS) or Industrial Engineering (IE) or
Decision Science (DS) (1) Observation
The first step in the management science
What Do We Do process is the identification of a problem that
exists in the system (organization).
1. OR professionals aim to provide rational Problems can often be identified by a
bases for decision making by seeking to management scientist, a person skilled in
understand and structure complex situations the techniques of management science and
and to use this understanding to predict system trained to identify problems, who has been hired
behavior and improve system performance. specifically to solve problems using
management science techniques.
2. Much of this work is done using analytical and • May involve current operations or proposed
numerical techniques to develop and expansions due to expected market shifts
manipulate mathematical and computer models • May become apparent through consumer
of organizational systems composed of complaints or through employee suggestions
people, machines, and procedures. • May be a conscious effort to improve efficiency
or response to an unexpected crisis.
Terminology
 British/Europeans refer to “Operational (2) Definition of Problem
Research" Once it has been determined that a problem
 the Americans to “Operations Research" exists, the problem must be clearly and
or "OR". concisely defined.
 Another term used for this field is Therefore, the limits of the problem and the
“Management Science (MS)" In U.S. OR degree to which it pervades other units of the
and MS are combined together to form organization must be included in the problem
"OR/MS" or "ORMS". definition.
• Describe system
 Yet other terms sometimes used are
“Industrial Engineering" ("IE") and • Define boundaries
“Decision Science" ("DS"). • State assumptions
• Select performance measures
Management Science • Define variables
-scientific approach to solving management • Define constraints
problems. • Data requirements
(3) Model Construction • Generally, stochastic models are more difficult
A management science model is an abstract to analyze.
representation of an existing problem situation. • The values of the decision variables that
It can be in the form of a graph or chart, but most provide the mathematically-best output are
frequently a management science model referred to as the optimal solution for the
consists of a set of mathematical model.
relationships.
-made up of numbers and symbols. Computer Software:
A variety of software packages are available for
Ex: The product costs $5 to produce and sells solving mathematical models, some are:
for $20. A model that computes the total profit • Spreadsheet packages such as Microsoft
that will accrue from the items sold is Excel
Z=+20x-5x • The Management Scientist (MS)
-x represents the number of units of the • Quantitative system for business (QSB)
product that are sold (independent variable) • LINDO, LINGO
-Z represents the total profit that results from • Quantitative models (QM)
the sale of the product. (dependent variable) • Decision Science (DS)
-x & Z are variables
-The numbers $20 and $5 in the equation are Example for Model Solution:
referred to as parameters. For the example model developed in the
-Parameters are constant values that are previous section,
generally coefficients of the variables (symbols) maximize: Z = $20x - 5x
in an equation. subject to: 4x = 100
-The equation as a whole is known as a The solution technique is simple algebra.
functional relationship (also called function and Solving the constraint equation for x, we have:
relationship). 4x = 100
Ex: (continuation) x= 100/4
Let us assume that the product is made from x= 25 units
steel and that the business firm has 100 Substituting the value of 25 for x into the profit
pounds of steel available. If it takes 4 pounds function results in the total profit:
of steel to make each unit of the product, we Z = $20x - 5x
can develop an additional mathematical = 20 (25) -5(25)
relationship to represent steel usage: = 500 – 125
4x = 100 lb. of steel = $375
(This equation indicates that for every unit Thus, if the manager decides to produce 25
produced, 4 of the available 100 pounds of steel units of the product and all 25 units sell, the
will be used.) business firm will receive $375 in profit.
Z = $20x - 5x
4x = 100 (5) Implementation
(We say that the profit equation in this new The final step in the management science
model is an objective function, and the resource process for problem is implementation.
equation is a constraint.) Implementation is the actual use of the model
once it has been developed or the
To signify this distinction between the two solution to the problem the model was
relationships in this model, we will add the developed to solve.
following notations: • A solution to a problem usually implies
maximize: Z = $20x - 5x changes for some individuals in the organization
subject to: 4x = 100 • Often there is resistance to change, making
the implementation difficult
(4) Model Solution • User-friendly system needed
• Those affected should go through training
Mathematical Models:
Relate decision variables (controllable inputs) Implementation and Follow-Up
with fixed or variable parameters • Successful implementation of model results is
(uncontrollable inputs). of critical importance.
• Frequently seek to maximize or minimize • Secure as much user involvement as possible
some objective function subject to throughout the modeling process.
constraints. • Continue to monitor the contribution of the
• Are said to be stochastic, if any of the model.
uncontrollable inputs (parameters) is subject • It might be necessary to refine or expand the
to variation (random), otherwise are said to be model.
deterministic. Operations Research Models:
Deterministic Models 1920
• Linear Programming •William Shewart - [Control Charts]
• Network Optimization •[Link] – [Link] - [Quality Theory]
• Integer Programming 1930
• Nonlinear Programming •Jon Von Neuman - Oscar Morgenstern
• Inventory Models [Game Theory]
Stochastic Models 1940
• Discrete-Time Markov Chains •World War 2
• Continuous-Time Markov Chains •George Dantzig - [Linear Programming]
• Queuing Theory (waiting lines) •First Computer
• Decision Analysis 1950
• Game Theory •[Link] - [Link] - [Non-Linear Prog.]
• Inventory models •Ralph Gomory - [Integer Prog.]
• Simulation •PERT/CPM
•Richard Bellman - [Dynamic Prog.]
Deterministic models ORSA and TIMS
-assume all data are known with certainty 1960
-involve optimization •John D.C. Litle - [Queuing Theory]
Stochastic models •Simscript – GPSS - [Simulation]
-explicitly represent uncertain data via 1970
random variables or stochastic processes. •Microcomputer
-characterize / estimate system performance. 1980
•H. Karmarkar - [Linear Prog.]
HISTORY OF OPERATIONS RESEARCH •Personal computer
• Before the World War II (1936) British •OR/MS Softwares
observed that there is a need of a technique 1990
which can help in finding the best way to •Spreadsheet Packages
utilize the available resources. •INFORMS
• They comes with a operation analysis to utilize 2006
their military resources in a best possible way, •You are here
this was time when concept of OR was first
developed. Quantitative Analysis and Decision Making
• First equipment developed utilizing OR was a Potential Reasons for a Quantitative Analysis
radar for tracking and detecting an aircraft. Approach to Decision Making
What is the need of OR • The problem is complex.
• To efficiently analyze the available data • The problem is very important.
• To improve forecasting for better prediction of • The problem is new.
future (in terms of output). • The problem is repetitive.
• To find out best techniques
• To find the best inventory level Data Preparation
• To improve the scheduling and time • Data preparation is not a trivial step, due to
management the time required and the possibility of data
• To manage the risk collection errors.
HISTORY OF OR • A model with 50 decision variables and 25
• OR is a relatively new discipline. constraints could have over 1300 data
• 70 years ago it would have been possible to elements!
study mathematics, physics or engineering at • Often, a fairly large data base is needed.
university it would not have been possible to • Information systems specialists might be
study OR. needed.
• It was really only in the late 1930's that
operation as research began in a systematic Report Generation
way. • A managerial report, based on the results of
1890 the model, should be prepared.
Frederick Taylor Scientific Management • The report should be easily understood by the
[Industrial Engineering] decision maker.
1900 • The report should include:
•Henry Gannt - [Project Scheduling] • the recommended decision
•Andrey A. Markov - [Markov Processes] • other pertinent information about the results
•Assignment - [Networks] (for example, how sensitive the model solution
1910 is to the assumptions and data used in the
•F. W. Harris - [Inventory Theory] model)
•E. K. Erlang - [Queuing Theory]
Components of OR-Based Decision Support original price, age, and mileage (not condition,
System rarity, or other factors).
• Data base (nurse profiles, external resources, Also, it is assumed that age and mileage
rules) devalue a car in a linear manner and without
• Graphical User Interface (GUI); web enabled limit. (Note, the starting bid for a very
using java or VBA old car might be negative!)
• Algorithms, pre- and post-processor
• What-if analysis Iron Works, Inc. (IWI) manufactures two
• Report generators products madefrom steel and just received this
month's allocation of b pounds of steel. It takes
Examples of OR Applications a1 pounds of steel to make a unit of
• Rescheduling aircraft in response to product 1 and it takes a2 pounds of steel to make
groundings and delays a unit of product 2.
• Planning production for printed circuit board
assembly Let x1 and x2 denote this month's production
• Scheduling equipment operators in mail level of product 1 and product 2, respectively.
processing & distribution centers Denote by p1 and p2 the unit profits for products
• Developing routes for propane delivery 1 and 2, respectively.
• Adjusting nurse schedules in light of daily
fluctuations in demand The manufacturer has a contract calling for at
least m units of product 1 this month. The firm's
Example: Austin Auto Auction facilities are such that at most u units of product
An auctioneer has developed a simple 2 may be produced monthly.
mathematical model fordeciding the starting bid
he will require when auctioning a used Mathematical Model
automobile. Essentially, he sets the starting bid • The total monthly profit = (profit per unit of
at seventy percent of what he predicts the final product 1)
winning bid will (or should) be. He predicts the x (monthly production of product 1)
winning bid by starting with the car's original + (profit per unit of product 2)
selling price and making two deductions, one x (monthly production of product 2)
based on the car's age and the other based on = p1x1 + p2x2
the car's mileage. We want to maximize total monthly profit:
The age deduction is $800 per year and the Max : p1x1 + p2x2
mileage deduction is $.025 per mile.
• The total amount of steel used during monthly
Question: production =
Develop the mathematical model that will give (steel required per unit of product 1)
the starting bid (B) for a car in terms of the car's x (monthly production of product 1)
original price (P), current age (A) and mileage + (steel required per unit of product 2)
(M). x (monthly production of product 2)
Answer: = a1x1 + a2x2
The expected winning bid can be expressed as: This quantity must be less than or equal to the
P - 800(A) - .025(M) allocated b pounds of steel:
The entire model is: a1x1 + a2x2 ≤ b
B = .7(expected winning bid) or
B = .7(P - 800(A) - .025(M)) or • The monthly production level of product 1 must
B = .7(P)- 560(A) - .0175(M) be greater than or equal to m:
x1 ≥ m
Question: • The monthly production level of product 2 must
Suppose a four-year old car with 60,000 miles be less
on the odometer is up for auction. If its original than or equal to u:
price was $12,500, what starting bid should the x2 ≤ u
auctioneer require? • However, the production level for product 2
Answer: cannot be
B = .7(12,500) - 560(4) - .0175(60,000) = $5460. negative:
x2 ≥ 0
Question: Max p1x1 + p2x2
The model is based on what assumptions? s.t. a1x1 + a2x2 < b
Answer: x1 ≥ m
The model assumes that the only factors x2 ≤ u
influencing the value of a used car are the x2 ≥ 0
• Question: cv = variable cost per unit
Suppose b = 2000, a1 = 2, a2 = 3, m = 60, u = v = volume (number of units) sold.
720, p1 = 100, p2 = 200. Rewrite the model with
these specific values for the uncontrollable The total cost of an operation is computed by
inputs. summing total fixed cost and total variable cost,
• Answer: as follows:
Substituting, the model is: total cost = total fixed cost + total variable
Max 100x1 + 200x2 cost
s.t. 2x1 + 3x2 < 2000 or, TC = cf + vcv
x1 ≥ 60 cf = Fixed cost.
x2 ≤ 720
x2 ≥ 0 Profit - is the difference between total
revenue and total cost. Total revenue is the
volume multiplied by the price per unit,
total revenue =vp
p = price per unit.
Now that we have developed relationships for
total revenue and total cost, profit (Z) can be
computed as follows:

total profit = total revenue - total cost

Z = vp - (cf + vcv)
= vp - cf + vcv

Computing the Break-Even Point:

For our clothing company example, we have
MODEL BUILDING: BREAK-EVEN determined total revenue and total cost to be
ANALYSIS $9,200 and $13,200, respectively. With these
values, there is no profit but, instead, a loss of
The purpose of break-even analysis is to $4,000:
determine the number of units of a product (i.e., total profit = total revenue - total cost
the volume) to sell or produce that will equate = $9,200 - 13,200 = -$4,000
total revenue with total cost.
We can verify this result by using our total
Components of Break-Even Analysis: profit formula,
Volume - is the level of sales or production by a Z = vp – (cf + vcv)
company. It can be expressed as the number of and the values v = 400, p = $23, cf = $10,000,
units (i.e., quantity) produced and sold, as the and cv = $8:
dollar volume of sales, or as a percentage of
total capacity available. Z = vp – (cf + vcv)
Cost (Fixed and Variable) Z = vp – cf – vcv
-Fixed Cost are generally independent of the = $(400)(23) – 10,000 – (400)(8)
volume of units produced and sold. (remains = $9,200 – 10,000 – 3,200
constant) include such items as rent on plant = -$4,000 (Obviously, the clothing company
and equipment, taxes, staff and does not want to operate with a monthly loss of
management salaries, insurance, $4,000 because doing so might eventually
advertising, depreciation, heat and light, and result in bankruptcy.)
plant maintenance. Taken together, these
items result in total fixed costs. At the break-even point, where total revenue
equals total cost, the profit, Z, equals zero.
-Variable Cost are determined on a per-unit Thus, if we let profit, Z, equal zero in our total
basis. Thus, total variable costs depend on the profit equation and solve for v, we can
number of units produced. Variable costs determine the break-even volume:
include such items as raw materials and Z = vp – cf – vcv
resources, direct labor, packaging, material 0 = v(23) – 10,000 – v(8)
handling, and freight. 0 = 23v – 10,000 – 8v
15v = 10,000
Total variable costs are a function of the v = 666.7 pairs of jeans (In other words, if the
volume and the variable cost per unit. company produces and sells 666.7 pairs of
Total variable cost = vcv jeans, the profit (and loss) will be zero and
the company will break even.)
 reduces the break-even point from 666.7 pairs
In general, the break-even volume can be of jeans to 454.5 pairs of jeans:
determined using the following formula:
𝑐𝑓
𝑣=
Z = vp – cf – vcv 𝑝 − 𝑐𝑣
0 = v(p-cv)-cf 10000
𝑣=
v(p – cv) = cf 30 − 8
Break-even Volume: v = 454.5 pairs of denim jeans
𝑐𝑓
𝑣=
𝑝 − 𝑐𝑣

Ex:
𝑐𝑓
𝑣=
𝑝 − 𝑐𝑣

10000
𝑣=
23 − 8

v = 666.7 pairs of jeans

Graphical Solution
Graphical models also have the advantage of
providing a “picture” of the model that can When we increased price, we mentioned the
sometimes help us understand the modeling possibility of raising the quality of the product to
process better than mathematics alone can. offset a potential loss of sales due to the price
increase. For example, suppose the stitching on
the denim jeans is changed to make the jeans
more attractive and stronger. This change
results in an increase in variable costs of $4 per
pair of jeans, thus raising the variable cost per
unit, cv, to $12 per pair. This change (in
conjunction with our previous price change to
$30) results in a new break-even volume:
𝑐𝑓
𝑣=
𝑝 − 𝑐𝑣
10000
=
30 − 12
= 555.5 pairs of denim jeans

Sensitivity Analysis
We have now developed a general relationship
for determining the break-even volume, which
was the objective of our modeling process. This
relationship enables us to see how the level of
profit (and loss) is directly affected by changes
in volume.

Sensitivity analysis can be performed on all

management science models in one form or
another. In fact, sometimes companies develop
models for the primary purpose of Next let’s consider an increase in advertising
experimentation to see how the model will react expenditures to offset the potential loss in sales
to different changes the company is resulting from a price increase. An increase in
contemplating or that management might advertising expenditures is an addition to fixed
expect to occur in the future. costs.
Ex: For example, if the clothing company increases
The first thing we will analyze is price. As an its monthly advertising budget by $3,000, then
example, we will increase the price for denim the total fixed cost, cf, becomes $13,000.
jeans from $23 to $30. As expected, this
increases the total revenue, and it therefore
Using this fixed cost, as well as the increased The selling price of $115,000 is the
variable cost per unit of $12 and the increased marginal revenue per house.
price of $30, we compute the break-even
volume as follows: Question:
𝑐𝑓 Write the monthly cost function c(x), revenue
𝑣=
𝑝 − 𝑐𝑣 function r(x), and profit function p(x).
13000 Answer:
=
30 − 12 c(x) = variable cost + fixed cost = 105,000x +
=722.2 pairs of denim jeans 40,000
r(x) = 115,000x
p(x) = r(x) - c(x) = 10,000x - 40,000

Question:
What is the breakeven point for monthly sales of
the houses?
Answer:
r(x) = c(x) or 115,000x = 105,000x + 40,000
Solving, x = 4.

Question:
Generally, it is not sufficient to consider a What is the monthly profit if 12 houses per
change in one model component without month are built and sold?
considering the overall effect. Answer:
p(12) = 10,000(12) - 40,000 = $80,000 monthly
Ex: profit
Ponderosa Development Corp.
Ponderosa Development Corporation
(PDC) is a small real estate developer operating
in the Rivertree Valley. It has seven permanent
employees whose monthly salaries are given in
the table on the next slide.
PDC leases a building for $2,000 per
month. The cost of supplies, utilities, and leased
equipment runs another $3,000 per month.
PDC builds only one style house in the
valley. Land for each house costs $55,000 and
lumber, supplies, etc. run another $28,000 per
house. Total labor costs are figured at $20,000
per house. The one sales representative of PDC
is paid a commission of $2,000 on the sale of
each house. The selling price of the house is LINEAR PROGRAMMING (LP): PROBLEM
$115,000. FORMULATION
(A MAXIMIZATION MODEL)
-One of the most frequent objectives of
business firms is to gain the most profit
possible or, in other words, to maximize
profit.
-The objective of individual organizational units
within a firm (such as a production or
packaging department) is often to minimize
Question: cost.
Identify all costs and denote the marginal cost -When a manager attempts to solve a general
and marginal revenue for each house. type of problem by seeking an objective that is
Answer: subject to restrictions, the management
The monthly salaries total $35,000 and science technique called linear programming
monthly office lease and supply costs total is frequently used.
another $5,000. This $40,000 is a monthly fixed
cost.

The total cost of land, material, labor, and

sales commission per house, $105,000, is the
marginal cost for a house.
There are three steps in applying the linear into a single model. The steps in this formulation
programming technique. process are summarized as follows:
First, the problem must be identified as being
solvable by linear programming.
Second, the unstructured problem must be
formulated as a mathematical model.
Third, the model must be solved by using
established mathematical techniques.

The linear programming technique derives its

name from the fact that the functional
relationships in the mathematical model are
linear, and the solution technique consists of
predetermined mathematical steps—that is, a
program. Decision Variables
The decision confronting management in this
A linear programming model consists of certain problem is how many bowls and mugs to
common components and characteristics. The produce.
model components include decision The two decision variables represent the
variables, an objective function, and model number of bowls and mugs to be produced on a
constraints, which consist of decision daily basis.
variables and parameters.
X1 = number of bowls to produce
-Decision variables are mathematical symbols X2 = number of mugs to produce
that represent levels of activity by the firm.
-The final values of x1, x2, and x3, as determined The Objective Function
by the firm, constitute a decision. The objective of the company is to maximize
-Objective function is a linear mathematical total profit. The company’s profit is the sum of
relationship that describes the objective of the the individual profits gained from each bowl
firm in terms of the decision variables. The and mug. Profit derived from bowls is
objective function always consists of either determined by multiplying the unit profit of each
maximizing or minimizing some value (e.g., bowl, $40, by the number of bowls produced,
maximize the profit or minimize the cost of x1.
producing radios). Likewise, profit derived from mugs is derived
-Model constraints are also linear relationships from the unit profit of a mug, $50, multiplied by
of the decision variables; they represent the the number of mugs produced, x2.
restrictions placed on the firm by the operating Thus, total profit, which we will define
environment. The restrictions can be in the form symbolically as Z, can be expressed
of limited resources or restrictive guidelines. mathematically as $40x1 + $50x2. By placing
-The actual numeric values in the objective the term maximize in front of the profit function,
function and the constraints, such as the 40 we express the objective of the firm—to
hours of available labor, are parameters. maximize total profit:
maximize = $40x1 + 50x2
-Linear Programming was conceived in 1947 by Z = $40x1 + 50x2
George B. Dantzig Where:
Z= total profit per day
$40x1 = profit from bowls
A Maximization Model Example $50x2 = profit from mugs

Model Constraints
The “less than or equal to” ( < ) inequality is
employed instead of an equality (=) because
the 40 hours of labor is a maximum limitation
that can be used, not an amount that must be
used. The constraint for clay is formulated in
the same way as the labor constraint.

There are 40 hours of labor and 120 pounds of 1x1 + 2x2 ≤ 40 hrs (labor)
clay available each day for production. We will 4x1 + 3x2 ≤120 lb. (clay)
formulate this problem as a linear programming
model by defining each component of the model A final restriction is that the number of bowls
separately and then combining the components and mugs produced must be either zero or a
positive value because it is impossible to
produce negative items. These restrictions are
referred to as nonnegativity constraints and
are expressed mathematically as:
x1 ≥ 0, x2 ≥ 0
complete linear programming model:
maximize = $40x1 + 50x2
1x1 + 2x2 ≤ 40 hrs
4x1 + 3x2 ≤120 lb.
x1 ≥ 0, x2 ≥ 0

RC1: 1x+2y ≤ 40
x y 1x+2y≤40 4x+3y≤120 Z=40x+50y The shaded area is referred to as the feasible
0 20 40≤40 60≤120 Z= $1000 solution area because all the points in this area satisfy
40 0 40≤40 160≤120 Z= $1600 both constraints.

Summary of the Graphical Solution Steps

The steps for solving a graphical linear programming
model are summarized here:
1. Plot the model constraints as equations on the graph;
then, considering the inequalities of the constraints,
indicate the feasible solution area.
2. Plot the objective function; then, move this line out from
the origin to locate the optimal solution point.
3. Solve simultaneous equations at the solution point to
find the optimal solution values.

Slack Variables (wala ni nadiscuss ni sir pero giapil nalang

nko kay part man gihapon siya sa maximization)
Here is a standard procedure for transforming inequality constraints
into equations. This transformation is achieved by adding a new
RC2: 4x+3y ≤ 120 variable, called a slack variable, to each constraint. For the pottery
x y 1x+2y≤40 4x+3y≤120 Z=40x+50y company example, the model constraints are
0 40 80≤40 120≤120 Z= $2000
30 0 30≤40 120≤120 Z= $1200
A slack variable represents unused resources.
The addition of a unique slack variable, s1, to the labor constraint and
to the constraint for clay results in the following equations:

The slack variables in these equations, s 1 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, consider a hypothetical solution of x1 = 5 and
x2 = 10. Substituting these values into the foregoing
equations yields

-4(1x+2y=40)
4x+3y=120
-4x-8y=-160
4x+3y+120

−5𝑦 −40
= −5
−5

Y=8

1x+2(8) = 40
X = 40-16
X = 24

x y 1x+2y≤40 4x+3y≤120 Z=40x+50y

24 8 40≤40 120≤120 Z= $1360

Optimal Solution:
X=24
Y=8
 Summary of 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
This problem contains two decision variables,
representing the number of bags of each brand
of fertilizer to purchase:

x1 = bags of Super-gro
x2 = bags of Crop-quick

The Objective Function

The farmer’s objective is to minimize the total
cost of fertilizing. The total cost is the sum of the
individual costs of each type of fertilizer
purchased. The objective function that
represents total cost is expressed as:

minimize (Z) = $6x1 + 3x2

where;
$6x1 = bags of Super-gro
$3x2 = bags of Crop-quick

Model Constraints
LINEAR PROGRAMMING (LP): PROBLEM
FORMULATION The requirements for nitrogen and phosphate
(A MINIMIZATION MODEL) represent the constraints of the model. Each
bag of fertilizer contributes a number of pounds
A minimization problem is formulated the
of nitrogen and phosphate to the field.
same basic way as a maximization problem, except
for a few minor differences. The following sample
problem will demonstrate the formulation of a 2x1 + 4x2 ≥ 16 lb.
minimization model. where;
A farmer is preparing to plant a crop in the 2x1 = the nitrogen contribution (lb.) per bag of
spring and needs to fertilize a field. There are two Super-gro
brands of fertilizer to choose from, Super-gro and 4x2 = the nitrogen contribution (lb.) per bag of
Crop-quick. Each brand yields a specific amount of Crop-quick
nitrogen and phosphate per bag, as follows:
Rather than a ≤ (less than or equal to) inequality,
as used in the Beaver Creek Pottery Company
model, this constraint requires a ≥ (greater than
or equal to) inequality. This is because the
nitrogen content for the field is a minimum
requirement specifying that at least 16 pounds
of nitrogen be deposited on the farmer’s field.

The constraint for phosphate is constructed like

the constraint for nitrogen:
4x1 + 3x2 ≥ 24 lb.
The farmer’s field requires at least 16 pounds of
nitrogen and at least 24 pounds of phosphate. With this example, we have shown two of the
Super-gro costs $6 per bag, and Crop-quick costs three types of linear programming model
$3. The farmer wants to know how many bags of constraints, ≤ and ≥. The third type is an
each brand to purchase in order to minimize the total exact equality, ═ . This type specifies that a
cost of fertilizing. constraint requirement must be exact.
 The optimal solution of a minimization
problem is at the extreme point closest to
the origin.

The final step in the graphical solution approach

is to solve for the values of x1 and x2 at point A.
Because point A is on the x2 axis, x1 = 0, thus,

4(0) + 3x2 = 24
x2 = 8

Given that the optimal solution is x1 = 0, x2 = 8,

As in our maximization model, there are also the minimum cost, Z, is
nonnegativity constraints in this problem to Z = $6x1 + $3x2
indicate that negative bags of fertilizer cannot be Z = 6(0) + 3(8)
purchased: = $24
x1, x2 ≥ 0
This means the farmer should not purchase any
The complete model formulation for this Super-gro but, instead, should purchase eight
minimization problem is bags of Crop-quick, at a total cost of $24.

minimize (Z) = $6x1 + 3x2 Surplus Variables (wala ni nadiscuss ni sir pero giapil nalang
nko kay part man gihapon siya sa minimization)
subject to; A surplus variable represents an excess above a constraint
2x1 + 4x2 ≥ 16 lb. requirement level.
4x1 + 3x2 ≥ 24 lb. Instead of adding a slack variable as we did with a ≥ constraint,
we subtract a surplus variable. Whereas a slack variable is
x1, x2 ≥ 0 added and reflects unused resources, a surplus variable is
subtracted and reflects the excess above a minimum
Graphical Solution of a Minimization Model resource requirement level.

We follow the same basic steps in the

graphical solution of a minimization model
as in a maximization model. The fertilizer
example will be used to demonstrate the
graphical solution of a minimization model.

As such, the standard form of this linear programming model is

summarized as
 LINEAR PROGRAMMING: DUALITY AND
SENSITIVITY ANALYSIS
> PRIMAL-DUAL RELATIONSHIP
>SIMPLEX METHOD

This discovery revealed that every linear

programming problem has associated with it
another linear programming problem called the
dual. The relationships between the dual
problem and the original problem (called the
primal) prove to be extremely useful in a variety
of ways.

One of the key uses of duality theory lies in the

interpretation and implementation of sensitivity Primal–Dual Relationships
analysis.

The Essence of Duality Theory

Furthermore, the dual problem uses exactly the
same parameters as the primal problem, but in
different locations, as summarized below.

1. The coefficients in the objective function of

the primal problem are the right-hand sides of
the functional constraints in the dual problem.
2. The right-hand sides of the functional
constraints in the primal problem are the
coefficients in the objective function of the dual
problem.
3. The coefficients of a variable in the functional
constraints of the primal problem are the
coefficients in a functional constraint of the dual
problem.
The Essence of Sensitivity Analysis
(example problem)
There is a small company in Melbourne which as recently
become engaged in the production of office furniture. The
company manufactures tables, desk, and chairs. The
production of table requires 8 kgs of woods and 5 kgs of
metal and is sold for $80; a desk uses 6 kgs of wood and
4 kgs of both metal and is sold for $60; and a chair
requires 4 kgs of both metal and wood and is sold for $50.
We would like to determine the revenue maximizing
strategy for this company given that their resources are
limited to 100 kgs of wood and 60 kgs of metal.
Primal–Dual Relationships

Let x1 = no of tables; x2 = no. of desks; x3 = no of chairs,

Z = profit
Objective Function: Max Z = $80x1 + $60x2 + $50x3
Subject to:
8x1 + 6x2 + 4x3 <= 100
5x1 + 4x2 + 4x3 <= 60
x1, x2, x3 >= 0

Now consider that there is a much bigger company in Melbourne

which has been the lone producer of this type of furniture for
many years. They do not appreciate the competition from this
new company; so, they have decided to tender an offer to buy
all of their competitor’s resources and therefore put them out of
business.

The challenge for this large company then is to develop a linear

program which will determine the appropriate amount of
money that should be offered for a unite of each type of
Summary of Primal-Dual Relationships
resource, such that the offer will be acceptable to the smaller
Duality Theorem
company while minimizing the expenditure of the larger
company.
The following are the only possible relationships between the
primal and dual problems.
1. If one problem has feasible solutions and a bounded
objective function (and so has an optimal solution), then so
does the other problem, so both the weak and strong duality
properties are applicable.
2. If one problem has feasible solutions and an unbounded
objective function (and so no optimal solution), then the other
problem has no feasible solutions.
3. If one problem has no feasible solutions, then the other
problem has either no feasible solutions or an unbounded
objective function
Let y1 = cost of wood; y2 = cost of metal; W = Cost in $
Objective Function: Min W = 100y1 + 60y2
Subject to:
8y1 + 5y2 >=80
6y1 + 4y2 >= 60
4y1 + 4y2 >= 50
y1, y2 >= 0