Optimization
MATH F212/AAOC C222
Department of Mathematics
BITS Pilani K K Birla Goa Campus
Dr. Manoj Kumar Pandey
Team of Instructors
Dr. Manoj Kumar Pandey
Dr. Mayank Goel (I/C)
Dr. Manoj Kumar Pandey
Text Book
Operations Research: An Introduction,
by H. [Link], Pearson Education, 9th Ed., 2012
Dr. Manoj Kumar Pandey
Reference Books
R1. Roland L. Radin, Optimization in Operations Research, Pearson
Education, 2nd Indian Reprint, 2003.
R2. F. S. Hillier and G. J. Lieberman, Introduction to Operations
Research, T M H, 8th Ed., 2005
R3. J. C. Pant, Introduction to Optimization: Operations Research,
Jain Brothers, New Delhi, 5th Ed, 2000
R4. Winston, Operations Research: Applications and Algorithms,
Thomson , 3rd Ed., 1996.
Dr. Manoj Kumar Pandey
R5. Saul I. Gass, Linear Programming Methods and Applications,
Dover Publications, 5th edn., 2003.
R6. G.C. Onwubolu and B.V. Babu, New Optimization Techniques
in Engineering, Springer, 1st Ed, 2004.
R7. A. Ravindran, D.T. Philips and J.J. Solberg, Operation
Research: Principles and Practice, John Wiley & Sons, 2nd Ed,
2004.
Dr. Manoj Kumar Pandey
Evaluation Components
Component Duration Weightage Date and Time Remarks
(%)
13/09/12
Test I 1 hour 25 2:00 p.m. 3:00 p.m. CB
18/10/12
Test II 1 hour 25 2:00 p.m. 3:00 a.m. CB
Quiz ** 10 ** **
Comprehensive 3 hours 40 01/12/11
Exam (FN) CB
** To be announced later.
Scopes and Objective of the Course:
An optimization problem in its simple form is one in
which some entity with or without being subjected to
certain constraints is minimized or maximized. The
entity to be optimized may be profit, cost, time,
product , consumer utility, etc.
The constraints involved may be manpower,
availability of space, raw materials, funds, machine
capabilities, etc.
Dr. Manoj Kumar Pandey
Objective of the course is to introduce certain
standard methods of solving optimization problems.
Dr. Manoj Kumar Pandey
Introduction to Linear Programming Problems (LPPs)
Historically, the first term for optimization was linear
programming ", which was due to George B. Dantzig, although
much of the theory had been introduced by Leonid Kantorovich
in 1939
George Dantzig Leonid Kantorovich
1914-2005 1912-1986
Dr. Manoj Kumar Pandey
Introduction to Linear Programming Problems (LPPs)
The term programming in this context does not refer to computer
programming. Rather, the term comes from the use of program by
the United States military to refer to proposed training and logistics
schedules, which were the problems Dantzig studied at that time.
Optimization is widely used in scientific applications,
engineering, and management.
Dr. Manoj Kumar Pandey
Introduction to Linear Programming Problems (LPPs)
Below is a table containing just a few classes of these applications ,
where optimization methods are used
Engineering Design : Process Control :
Aircraft and Spacecraft Chemical Mixing
Automobiles and Seacraft Aircraft and Missile Flights
Bridges and Buildings Petroleum Blending
Electric/ Electronic Circuits Diet Balancing
/////////////////////// ///////////////////////
Management : Applied Mathematics :
Manufacturing Schedules Curve Fitting
Resource Allocation Matrix Game Theory
Transportation Schedules Network Flows
Dr. Manoj Kumar Pandey
Mathematical programming problems
The mathematical formulation of a problem to optimize
profit, loss, production etc. , under a given set of
conditions is called mathematical programming
problem.
Dr. Manoj Kumar Pandey
Terminology
Decision Variables: That we seek to determine, help in
describing the decision to be made.
Objective function: Describes the main objective (or
purpose) of the problem. Depending on the nature of the
problem the objective function may be of type
maximization or minimization.
Constraints: Describe the various restrictions imposed
on the problem. In any Mathematical Programming
Problem, there are two types of constraints; variable
constraints and main constraints.
Dr. Manoj Kumar Pandey
The general form of the problem
Max. / Min. f (X)
subject to
gi (X) or = or 0, i=1,2,m
X 0, where X = ( x1, x2..xn)
Dr. Manoj Kumar Pandey
The Mathematical Programming problem is
classified into two classes:
1. Linear Programming Problems (LPP)
2. Nonlinear Programming Problems (NLPP)
Dr. Manoj Kumar Pandey
Linear Programming Problems (LPP)
An optimization problem is called a Linear
Programming Problem (LPP) when the
objective function and all the constraints are
linear functions of the decision variables, x1,
x2, , xn. We also include the non-negativity
restrictions, namely xj 0 for all j = 1,2, , n.
Dr. Manoj Kumar Pandey
A typical LPP is of the form:
Max. / Min. z = c1 x1 + c2 x2+ + cn xn
subject to the constraints:
a11 x1 + a12 x2 + + a1n xn b1
a21 x1 + a22 x2 + + a2n xn b2
. . .
am1 x1 + am2 x2 + + amn xn bm
x1, x2, , xn 0
Dr. Manoj Kumar Pandey
Non-Linear Programming Problems (NLPP)
An optimization problem of the form:
Max. / Min. f (X)
subject to
gi (X) or = or 0, i=1,2,m
X 0,
where X = (x1, x2, ..xn), is said to be NLPP if
either the objective function or the any of the
constraints or both are nonlinear function of X.
Dr. Manoj Kumar Pandey
Formulation of a Linear Programming
Problems
define the decision variables
define the objective function
define the constraints
Dr. Manoj Kumar Pandey
Example 1
Cycle Trends is introducing two new lightweight bicycle
frames, the Deluxe and the Professional, to be made from
aluminum and steel alloys. The anticipated unit profits are
Rs.10 for the Deluxe and Rs.15 for the Professional.
The number of units of each alloy needed per frame is
summarized on the next slide. A supplier delivers 100 units
of the aluminum alloy and 80 units of the steel alloy
weekly. How many Deluxe and Professional frames should
Cycle Trends produce each week in order to maximize the
profit.
Dr. Manoj Kumar Pandey
Units of each alloy needed per frame
ALUMINUM ALLOY STEEL ALLOY
DELUXE 2 3
PROFESSIONAL 4 2
Dr. Manoj Kumar Pandey
Formulation
Decision Variables
x1 = number of Deluxe frames produced weekly
x2 = number of Professional frames produced weekly
Objective
Maximize total weekly profit
Max z = 10x1 + 15x2
Dr. Manoj Kumar Pandey
Consraints
Main Constraints:
Availability of Aluminum Alloy
2x1 + 4x2 < 100
Availability of Steel Alloy
3x1 + 2x2 < 80
Variable Constraints:
Non negativity restrictions
x1 > 0, x2 > 0 on the decision variables
Dr. Manoj Kumar Pandey
LPP in Final Form
Max z = 10x1 + 15x2 (maximizing the profit)
Subject to
2x1 + 4x2 < 100 ( aluminum constraint)
3x1 + 2x2 < 80 ( steel constraint)
x1 , x2 > 0 (non-negativity constraints)
Dr. Manoj Kumar Pandey
Example 2
A manufacturer produces two types of models M1 and M2.
Each M1 model requires 4 hours of grinding and 2 hours of
polishing, where as M2 model requires 2 hours of grinding
and 5 hours of polishing. The manufacturer has 2 grinders
and 3 polishers. Each grinder works for 40 hours a week and
each polisher works for 60 hours a week. Profit on M1 is Rs.
3 per unit and profit on M2 is Rs. 4 per unit. whatever is
produced in a week is sold in the market. How should the
manufacturer allocate his production capacity to two types of
models so that the profit is maximum in a week
Dr. Manoj Kumar Pandey
Formulation
Decision Variables:
x1 = number of M1 model produced weekly
x2 = number of M2 model produced weekly
Objective:
Maximize total weekly profit
Max z = 3x1 + 4x2
Dr. Manoj Kumar Pandey
Consraints
Main constraints
For grinding
4x1 + 2x2 2*40
For polishing
2x1 + 5x2 3*60
Variable Constraints:
x1 > 0, x2 > 0
Dr. Manoj Kumar Pandey
Final form of the LPP
Max z = 3x1 + 4x2
Subject to
4x1 + 2x2 80
2x1 + 5x2 180
x1 0, x2 0
Dr. Manoj Kumar Pandey
Example 3
A Depo runs buses during the time period 5AM to 1AM. Each
bus can operate for 8 hours successively, and then it is
directed to workshop for maintenance and fuel. The minimum
number of buses required fluctuate with the time intervals.
The desired number of buses during different time interval
are given in the following table:
Time Intervals Minimum No. of buses required
5 AM 9 AM 5
9 AM 1 PM 13
1 PM 5 PM 11
5 PM 9 PM 14
9 PM 1 AM 4
Dr. Manoj Kumar Pandey
It is required to determine the number of buses to operate
during different shifts that will meet the minimum
requirement while minimizing the total number of daily
buses in operation.
Dr. Manoj Kumar Pandey
Formulation
Decision Variables
xi =number of buses starting at the
beginning of the i th period i = 1 to 5.
Objective function
Min z = x1+x2+x3+x4+x5
Remark : Each bus operates during two consecutive shifts.
Dr. Manoj Kumar Pandey
Constraints
x1 + x2 13
x2 + x3 11
x3 + x4 14 Main Constraints
x4 + x5 4
x5 + x1 5
x1 , x2 , x3 , x4 ,x5 0 Variable Constraints
Remark: Buses which join the crew at 5 AM and 9 AM will be
in operation between 9 AM and 1PM.
Dr. Manoj Kumar Pandey
LPP in Final Form
Min z = x1 + x2+ x3 + x4+ x5
Subject to x1 + x2 13
x2 + x3 11
x3 + x4 14
x4 + x5 4
x5 + x1 5
x1 , x2 , x3 , x4 ,x5 0
Dr. Manoj Kumar Pandey
Example 4
Paper cutting machines are available to cut standard news
print rolls into sub rolls. Each standard roll is of 180 cm width
and a number of them must be cut to produce smaller sub
rolls at the current orders for 30 of width 70 cm, 60 of width
50 cm and 40 of width 30 cm. Formulate the problem so as
to minimize the amount of wastes. Ignoring the recycling or
other uses for the trim, assume that the length of each
required sub roll is the same as that of the standard roll.
Dr. Manoj Kumar Pandey
A standard roll may be cut according to the
following patterns.
Number of sub rolls cut on different
patterns
Widths p1 p2 p3 p4 p5 p6 p7 p8
ordered in cm
30 6 4 3 2 2 1 1 0
50 0 1 0 1 2 0 3 2
70 0 0 1 1 0 2 0 1
Trim Loss 0 10 20 0 20 10 0 10
Dr. Manoj Kumar Pandey
Formulation
Decision Variables
Let xi be the number of the standard news print rolls pieces
to cut on the pattern pi , i = 1 to 8.
Objective Function
Min z = 10x2 +20x3+ 20x5+ 10x6+ 10x8
Dr. Manoj Kumar Pandey
Constraints
6x1 +4x2+ 3x3+ 2x4+ 2x5 + x6+ x7 = 40
x2 +x4+ 2x5+ 3x7+ 2x8 = 60
x3 +x4+ 2x6+ x7+ x8 = 30
xi 0, i = 1 to 8.
Dr. Manoj Kumar Pandey
LPP in Final Form
Min z = 10x2 +20x3+ 20x5+ 10x6+ 10x8
Subject to
6x1 +4x2+ 3x3+ 2x4+ 2x5 + x6+ x7 = 40
x2 +x4+ 2x5+ 3x7+ 2x8 = 60
x3 +x4+ 2x6+ x7+ x8 = 30
xi 0, i = 1 to 8.
Dr. Manoj Kumar Pandey
Example 5
A company has two grades of inspectors, I and II to undertake
quality control inspection. At least , 1500 pieces must be
inspected in an 8-hour day. Grade I inspector can check 20
pieces in an hour with an accuracy of 96% and, grade II
inspector can check 14 pieces in an hour with an accuracy of
92%. The wages of grade I inspectors are $ 5 per hour, while
the wages of grade II inspectors are $ 4 per hour. An error
made by an inspector cost $ 3 to the company. If there are,
in all, 10 grade I inspectors and 15 grade II inspectors in the
company, find the optimal assignment of inspectors that
minimizes the daily inspection cost.
Dr. Manoj Kumar Pandey
Formulation
Let x1 and x2 be the number of Grade I and II
inspectors assigned by the company.
Objective : minimize the daily cost of inspection
Wages paid to the inspectors and the cost of
their inspection errors.
The cost of grade I inspector/hour is
$ (5 + 3 0.04 20) = $ 7.40 per hour
The cost of grade II inspector/hour is
$ (4 + 3 0.08 14) = $ 7.36 per hour
Dr. Manoj Kumar Pandey
The objective function is
Minimize Z = 8(7.40 x1 + 7.36 x2)
= 59.20 x1 + 58.90 x2
subject to
x1 10
x2 15
20 8 x1 + 14 8 x2 1500.
x1 0, x2 0
Dr. Manoj Kumar Pandey
LPP in Final Form
Min. Z = 59.20 x1 + 58.90 x2
Subject to
x1 10
x2 15
160 x1 + 112 x2 1500
x1 0, x2 0
Dr. Manoj Kumar Pandey
Solving linear Programming
Problems
Dr. Manoj Kumar Pandey
Solutions
Any value of the decision variables that satisfy all the
constraints (Main as well as variable) is called as a
feasible solution.
Aim : The aim of the problem is to find the best (optimal)
feasible solution. We need a systematic procedure that will
locate the optimum solution in a finite number of steps.
Dr. Manoj Kumar Pandey
GRAPHICAL METHOD
Dr. Manoj Kumar Pandey
Steps for solving the LPP by Graphical method
Determination of the feasible solution space
Draw the variable constraints (for e.g. the non
negativity restrictions on the decision variables restrict
the solution space to the first quadrant only)
Draw the main constraints by changing the inequalities
into equations and graph the resulting straight lines.
Draw an arrow in the direction of the inequality.
Find the direction towards which the objective function
is optimum and hence find the optimum solution.
Dr. Manoj Kumar Pandey
Example 1:
Objective function
Maximize x+y
Subject to:
x+2y2
x3
Main constraints
y4
x0 y0 Non negativity restrictions
Dr. Manoj Kumar Pandey
Graphing 2-Dimensional LPs
Optimal
Solution
Example 1: y
4
Maximize x+y
3
Subject to: x + 2 y 2 Feasible
Region
x3 2
y4
1
x0 y0
0 x
0 1 2 3
Dr. Manoj Kumar Pandey
Graphing 2-Dimensional LPs
Example 2:
Minimize x + 1/3 y
Subject to: x + y 20
-2 x + 5 y 150
x5
x0 y0
Dr. Manoj Kumar Pandey
Graphing 2-Dimensional LPs
Example 2: y
40
Minimize x + 1/3 y
30
Subject to: x + y 20 Feasible
-2 x + 5 y 150 20 Region
x5
10
x0 y0
x
0
Optimal
Solution 0 10 20 30 40
Dr. Manoj Kumar Pandey
Steps for solving the LPP by Graphical method
(contd.)
Determination of the optimum solution
The optimum solution lies on one of the
corner points (vertices) of the feasible
region.
Dr. Manoj Kumar Pandey
A Fundamental Point
y
If an optimal y
4 solution 40
3 exists, there is 30
2 always a 20
1
corner point 10
0
0 1 2 3
x optimal 0
0 10 20 30 40
x
solution!
Dr. Manoj Kumar Pandey
Example 3
Maximize Z = x + 5y
Subject to: -x + 3y 10
x+y 6
x-y 2
x0 y0
Dr. Manoj Kumar Pandey
Graphical Solution:
y
8 Optimal
The Vertices are : Solution
6
(0, 0), (2, 0), (4, 2), (2, 4),
( 2, 4 )
(0,10/3) 4
( 0, 10/3 )
2 PF ( 4, 2 )
x
0
0 2 4 6 8
Dr. Manoj Kumar Pandey
The value of the objective function is computed at
these are:
Z=0 at (0, 0)
Z=2 at (2, 0)
Z = 14 at (4, 2)
Z = 22 at (2 ,4)
Z = 50/3 at (0, 10/3)
Obviously, the maximum occurs at vertex (2, 4) with the
maximum value 22. Hence,
Optimal Solution: x=2, y=4, z=22.
Dr. Manoj Kumar Pandey
Example 4
Minimize Z = x - 2y
Subject to:
-x + y 1
2x + y 2
x0 y0
Dr. Manoj Kumar Pandey
Graphical Solution:
y
The Vertices are :
3
(0, 0), (1, 0), (0, 1), (1/3, 4/3)
2
( 1/3, 4/3 )
1
PF
x
0
0 1 2 3
Dr. Manoj Kumar Pandey
The value of the objective function is computed at
these are:
Z=0 at (0, 0)
Z=1 at (1, 0)
Z = -7/3 at (1/3, 4/3)
Z = -2 at (0, 1)
Obviously, the minimum occurs at vertex (1/3, 4/3) with the
minimum value -7/3. Hence,
Optimal Solution: x=1/3, y=4/3, z=-7/3.
Dr. Manoj Kumar Pandey
Example 1
Cycle Trends is introducing two new lightweight bicycle
frames, the Deluxe and the Professional, to be made from
aluminum and steel alloys. The anticipated unit profits are
Rs.10 for the Deluxe and Rs.15 for the Professional.
The number of units of each alloy needed per frame is
summarized on the next slide. A supplier delivers 100 units
of the aluminum alloy and 80 units of the steel alloy
weekly. How many Deluxe and Professional frames should
Cycle Trends produce each week in order to maximize the
profit.
Dr. Manoj Kumar Pandey
Units of each alloy needed per frame
ALUMINUM ALLOY STEEL ALLOY
DELUXE 2 3
PROFESSIONAL 4 2
Dr. Manoj Kumar Pandey
LPP in Final Form
Max z = 10x1 + 15x2
Subject to
2x1 + 4x2 < 100
3x1 + 2x2 < 80
x1 , x2 > 0
Solve the above problem graphically.
Dr. Manoj Kumar Pandey
The Vertices are :
O (0, 0)
A (80/3, 0) Feasible
B (15, 35/2) Region
C (0, 25),
C B
O
A
Dr. Manoj Kumar Pandey
The value of the objective function is computed at
these are:
Z=0 (0, 0)
Z = 800/3 (80/3, 0)
Z = 825/2 (15, 35/2)
Z = 375 (0 , 25)
Z = 50/3 (0, 10/3)
Obviously, the maximum occurs at vertex (15, 35/2) with the
maximum value 825/2. Hence,
Optimal Solution: x1 =15, x2 =35/2, z=825/2.
Dr. Manoj Kumar Pandey
Graphical Solution to a 2-Variable LP
Special Cases:
Dr. Manoj Kumar Pandey
Some LPs have an infinite number of solutions
(alternative or multiple optimal solutions).
Some LPs have no feasible solutions (infeasible
LPs).
Some LPs are unbounded: There are points in the
feasible region with arbitrarily large (in a
maximization problem) z-values.
Dr. Manoj Kumar Pandey
(1) Max z = 3x1 + 2x2
Subject to
Infinitely many optimal solution
3x1 + 2x2 < 120
x1 + x2 < 50
x1 , x2 > 0
(2) Max z = 3x1 + 2x2
Subject to
3x1 + 2x2 < 120
x1 + x2 < 50
No feasible solution
x1 30
x2 20
x1 , x2 > 0
Dr. Manoj Kumar Pandey
(3) Max z = 2x1 - x2
Unbounded solution
Subject to
x1 - x2 < 1
2x1 + x2 6
x1 , x2 > 0
Dr. Manoj Kumar Pandey
Dr. Manoj Kumar Pandey
Dr. Manoj Kumar Pandey
Dr. Manoj Kumar Pandey
Dr. Manoj Kumar Pandey
Definitions
Set: A set is described as a well-defined collection of
objects. These objects are called the elements or
members of the set. Objects can be anything: numbers,
people, other sets, etc.
Example: A = {red, blue, yellow, green, purple} is well-defined since it is clear
what is in the set what is not.
Example:B The collection of good students at BITS is not a set.
Dr. Manoj Kumar Pandey
Definitions
Line: A line joining X1 and X2 in 2 is a set of points
given by the linear combination
L = { X 2 : X = (1-) X1+ X2, }
Dr. Manoj Kumar Pandey
Let
X1 =(x1, y1 )
X2=(x2 , y2 )
then, the line passing through these two points is the
collection of the points (x, y) given by
y y1
y y = 2
( x x )
1 1
x 2 x1
y y1 x x1
= = say ( )
y 2 y1 x 2 x1
x x 1 = ( x 2 x 1 ), x = (1 ) x 1 + x 2
y y 1 = ( y 2 y 1 ), y = (1 ) y 1 + y 2
Dr. Manoj Kumar Pandey
X = (1 ) X 1 + X 2 , X = ( x, y)
Hence,
L = { X 2 : X = (1-) X1+ X2, }
Line Segment : A line segment joining two points X1
and X2 is defined by
LS = { X 2 : X = (1-) X1+ X2, 0 1 }
Remark: These definitions can be extended to n.
Dr. Manoj Kumar Pandey
Convex Set: A set S n is said to be convex if the
line segment joining any two points in S lies in the set.
that is:
if X1 and X2 S
then
(1-) X1+ X2, 0 1 S.
Consider the figures (a) (d) below:
Dr. Manoj Kumar Pandey
Results:
(1) The intersection of two convex sets is a convex set.
(2) Union of two convex sets need not be convex.
(3) Using the definition show that the set
S={ X 2 : x2 + y2 a2 , a>0} is a convex set.
Dr. Manoj Kumar Pandey