Transcript Introducing a New Product

INTRODUCTION TO OPERATIONS
RESEARCH
Linear Programming
WHAT IS LINEAR PROGRAMMING?

Linear Programming provides methods for allocating
limited resources among competing activities in an
optimal way.



Linear → All mathematical functions are linear
Programming → Involves the planning of activities
A linear program is a mathematical optimization
model that has a linear objective function and a set
of linear constraints
EXAMPLE - WYNDOR GLASS CO.
The company produces glass products and
owns 3 plants. Management decides to
produce two new products.
Product 1
Product 2
1 hour production time in Plant 1
3 hours production time in Plant 3
$3,000 profit per batch
Production time available each week
Plant 1:
Plant 2:
Plant 3:
4 hours
12 hours
18 hours
2 hours production time in Plant 2
2 hours production time in Plant 3
$5,000 profit per batch
WYNDOR GLASS CO.
Plant
Product 1
Product 2
Production
Time
1
1
0
4
2
0
2
12
3
3
2
18
$3,000
$5,000
Profit
Maximize
Z = 3x1 + 5x2
Subject to:
x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 ≥ 0, x2 ≥ 0
WYNDOR GLASS CO.
Graph the equations
to determine
relationships
Maximize
Z = 3x1 + 5x2
Subject to:
x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 ≥ 0, x2 ≥ 0
GENERAL LINEAR PROGRAMMING
Allocating resources to activities
General
Example
Resources
Production capacities of plants
m resources
3 plants
Activities
Production of products
n activities
2 Products
Level of activity j, xj
Production rate of product j, xj
Overall measure of performance Z Profit Z
GENERAL LINEAR PROGRAMMING
Objective Function
c1 x1 + c2 x2 + ... + cn xn
Constraints
a11 x1 + a12 x2 + ... + a1n xn ≤ b1
a21 x1 + a22 x2 + ... + a2n xn ≤ b2
.....
am1 x1 + am2 x2 + ... + amn xn ≤ bm
x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0 ,
Non-negativity
Constraints
Z = Value of overall measure of performance
xj = Level of activity j
= Decision variables
cj = Increase in Z resulting from increase in j
= Parameters
bi = Amount of available resources
= Parameters
aij = Amount of resource i consumed by each unit of j
= Parameters
Functional Constraints
GENERAL LINEAR PROGRAMMING
Resource
1
2
…
m
Contribution to
Z
Resource Usage per
Unit of Activity
Activity
1
2
…
n
a11 a12 … a1n
a21 a22 … a2n
…
…
…
…
am1 am2 … amn
c1
c2
…
cn
Amount of
Resource
Available
b1
b2
…
bm
LINEAR PROGRAMMING SOLUTIONS





Solution – Any specification of values for the
decision variables (xj)
Feasible solution – A solution for which all
constraints are satisfied
Infeasible solution – A solution for which at least
one constraint is violated
Feasible region – The collection of all feasible
solutions
Optimal solution – A feasible solution that has the
most favorable value of the objective function
LINEAR PROGRAMMING SOLUTIONS

No Feasible Solution

Multiple Optimal Solutions

No Optimal Solution

Corner-point Feasible (CPF) Solution
LINEAR PROGRAMMING ASSUMPTIONS

Proportionality – The contribution of each activity to Z or
a constraint is proportional to the level of activity xj

Z = 3x1 + 5x2

Additivity – Every function is the sum of the individual
contributions of the activities

Divisibility – Decision variables are allowed to have any
value, including non-integer values

Certainty – The value assigned to each parameter is
assumed to be a known constant