Operations Research 1
Sinta R Sulistyo, ST, MSIE
sinta.sulistyo@ugm.ac.id
Materials
1. Optimization concepts
2. Linear programming
3. Simplex algorithm
4. Transportation and assignment problem
5. Network models
6. Integer programming
References
◉ Hillier, F.S. and Lieberman, G.J., 2010, Introduction to Operations
Research, 9th ed., McGraw-Hill International Edition.
◉ Taha, H.A., 2007, Operations Research: an Introduction., 8th ed.
Prentice Hall.
◉ Winston, W.L and Venkataramanan, M., 2003, Introduction to
Mathematical Programming. Operations Research: Volume one, 4th
edition, Brooks/Cole, Cengage Learning.
Grading
◉ Homework 20%
◉ Quiz 40%
◉ Final exam 40%
Introduction
Introduction to Modeling
Operation research is a scientific approach to decision making that
seeks to best design and operate a system, usually under conditions
requiring the allocation of scarce resource.
Mathematical model is a mathematical representation of an actual
situation that may be used to make better decision or simply to
understand the actual situation better.
Optimization models
A prescriptive model prescribes behavior for an organization that will
enable it to best meet its goal(s). The component of a model include:
objective function(s), decision variables, constraints
An optimization model seeks to find values of the decision variables
that optimize (maximize or minimize) an objective function among the
set of all values for the decision variables that satisfy the given
constraints.
Optimization
Optimization is a scientific methods to solve problems in order to find
solutions which best serve the purposes
The desired goal may not be achievable so we try to get as close as
possible to it
The application of optimization in business and industry: finance,
purchasing, procurement, distribution, facilities planning,
manufacturing, maintenance, project scheduling, marketing, personnel,
military, and so on.
Definitions
Objective function is a function that we wish to optimize (maximize or
minimize)
Decision variables are the variables whose values under our control
and influence the performance of the system. It is always involved with
a trade off. The variables type can be continuous, discrete/integer,
binary.
Constraints are the restriction on values of decision variables
Example: diet problem
Mary wants to find the cheapest diet in a such a way as to obtain all the
nutritional ingredients she needs per day. Her nutritional requirements
are 55 gr of protein per day and 400 mg of calcium per day. She can
obtain the nutrients from:
Name Serving Protein Calcium Serving Price
Size (gr) (mg)
Oatmeal 28 gr 4 2 3
Eggs 2 13 50 10
Milk 237 cc 8 120 8
Also, she can have at most 4 servings of oatmeal per day, 2 servings of
eggs per day, and 5 servings of milk per day.
Linear
Programming
Definitions
A function 𝑓(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) of 𝑥1 , 𝑥2 , … , 𝑥𝑛 is a linear function if and only
if for some of set constants 𝑐1 , 𝑐2 , … , 𝑐𝑛 , 𝑓 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 𝑐1 𝑥1 + 𝑐2 𝑥2 +
⋯ + 𝑐𝑛 𝑥𝑛
For any linear function 𝑓(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) and any number of 𝑏, the
inequalities 𝑓 𝑥1 , 𝑥2 , … , 𝑥𝑛 ≤ 𝑏 and 𝑓 𝑥1 , 𝑥2 , … , 𝑥𝑛 ≤ 𝑏 are linear
inequalities
Definitions
A linear programming problem (LP) is an optimization problem for which
we do the following:
1. We attempt to maximize (or minimize) a linear function of the decision
variables. The function that is to be maximized or minimized is called the
objective function.
2. The values of the decision variables must satisfy the a set of constraints.
Each constraint must be a linear equation or linear inequality.
3. A sign restriction is associated with each variable. For any variable 𝑥𝑖 ,
the sign restriction specifies that 𝑥𝑖 must be either nonnegative (𝑥𝑖 ≥ 0)
or unrestricted in sign (urs).
LP model
Max (Min): 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 (objective function)
Subject to
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1 (constraint 1)
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2 (constraint 2)
…
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚 (constraint m)
𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0
LP assumptions
1. Proportionality
The criterion and the constraints expand or contract proportionally
to the level of each activities
2. Additivity
The total contribution of all activities is identical to the sum of the
contribution for each activity individually
3. Certainty
Each parameter is known with certainty
4. Divisibility
Each decision variable is allowed to assume fractional values
Formulation: diet problem
Mary wants to find the cheapest diet in a such a way as to obtain all the
nutritional ingredients she needs per day. Her nutritional requirements
are 55 gr of protein per day and 400 mg of calcium per day. She can
obtain the nutrients from:
Name Serving Size Protein (gr) Calcium (mg) Serving Price
Oatmeal 28 gr 4 2 3
Eggs 2 13 50 10
Milk 237 cc 8 120 8
Also, she can have at most 4 servings of oatmeal per day, 2 servings of
eggs per day, and 5 servings of milk per day.
Formulation: blending problem
A drug company uses two chemicals C1 and C2 to produce two drugs
D1 and D2.
Drug D1 must contain at least 70% of C1 and drug D2 must contain at
least 60% of C2.
Also, up to 45 oz of C1 can be purchased at 6/oz and up to 40 oz of C2
can be purchased at 4/oz.
Moreover, up to 40 oz of D1 can be sold at 6/oz and up to 30 oz of D2
can be sold at 5/oz.
Goal: maximize the company’s profit.
Formulation: production process
RC manufactures B and C perfumes. The raw material needed to
manufacture each type of perfume can be purchased for $3 per pound.
Processing 1 lb of raw material requires 1 hour of laboratory time. Each
pound of processed raw material yields 3 oz of Regular B Perfume and
4 oz of Regular C Perfume. Regular B can be sold for $7/oz and
Regular C for $6/oz.
RC also has the option of further processing Regular B and Regular C
to produce Luxury B, sold at $18/oz, and Luxury C, sold at $14/oz.
Formulation: production process (2)
Each ounce of Regular B processed further requires an additional 3
hours of laboratory time and $4 processing cost and yields 1 oz of
Luxury B. Each ounce of Regular C processed further requires an
additional 2 hours of laboratory time and $4 processing cost and yields
1 oz of Luxury C.
Each year, RC has 6,000 hours of laboratory time available and can
purchase up to 4,000 lb of raw material.
Formulate an LP that can be used to determine how RC can maximize
profits.
Definition
The feasible region for an LP is the set of all points that satisfies all
the LP’s constraints and sign restrictions.
For a maximization (minimization) problem, an optimal solution to an
LP is a point in the feasible region with the largest (smallest) objective
function value.
Graphical solution - 1
The LP has a unique optimal solution
min 𝑧 = 50 𝑥1 + 100𝑥2
Subject to
7𝑥1 + 2𝑥2 ≥ 28
2𝑥1 + 12𝑥2 ≥ 24
𝑥1 , 𝑥2 ≥ 0
Graphical solution - 2
The LP has an infinite number of optimal solutions
max 𝑧 = 3 𝑥1 + 2𝑥2
Subject to
1 1
𝑥 + 60 𝑥2 ≤ 1
40 1
1 1
𝑥 + 50 𝑥2 ≤ 1
50 1
𝑥1 , 𝑥2 ≥ 0
Graphical solution - 3
The LP has no feasible solution (infeasible LP)
max 𝑧 = 3 𝑥1 + 2𝑥2
Subject to
1 1
𝑥 + 60 𝑥2 ≤ 1
40 1
1 1
𝑥 + 50 𝑥2 ≤ 1
50 1
𝑥1 ≥ 30
𝑥2 ≥ 20
Graphical solution - 4
The LP is unbounded
max 𝑧 = 2𝑥1 − 𝑥2
Subject to
𝑥1 − 𝑥2 ≤ 1
2𝑥1 + 𝑥2 ≥ 6
𝑥1 , 𝑥2 ≥ 0
thankyou
