LINEAR PROGRAMMING

2.Model Formulation
• Problem identified with decision variables
• How many units to buy/sell...
• How much time to spend on a task...
• Measure of performance is the objective function
• What is the goal?
• Usually: Max/Min profit/cost/time/units
• A function of the decision variables
• Restrictions of values of decision variables set in constraints
• Min acceptable production
• Max available resources
• Parameters are the constants of the objective function and the
constraints
• Sensitivity analysis: How solution affected by values of
parameters
 3

Model Formulation (cont.)

• Variety of models will be covered

Objective function: Maximize 𝑍 = 3𝑥1 + 5 𝑥2

subject to constraints
𝑥1 ≤4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
and
𝑥1 ≥ 0, 𝑥2 ≥ 0
 4

Linear Programming
• Ranked among the most important scientific advances in the
mid-20th century
• Most common type of application involves the general type of
allocating limited resources among competing activities in a
best possible (optimal) way
• Definition: Linear
• The objective function is linear
• The constraint set is a set of linear equations

• Definition: Programming
• Programming here means planning (not a computer program)
• Definition: Linear Programming
• Planning of activities to obtain an optimal results among all feasible
alternatives, where all relationships are of linear form.
Linear Programming
• If the objective function and constraints of an
optimization model are all linear then it will be
defined as a linear programming
• There are many readily available computer
programs one can use to find their solutions.
• These programs are very powerful, and unlike
many other optimization methods, they can be
applied successfully to very large optimization
problems.
Linear Programming (LP) Overview
• LP is a special form of mathematical programming
• LP features
• Equations must be linear
• Uses simple solution procedures
• Linear algebra
• Very powerful
• Can handle extremely large problems (100,000 variables, 1000's of
constraints)
• Useful design information through sensitivity analysis
• Answers to "what if" questions
 7

Introduction to Linear Programming

• A Linear Programming model seeks to maximize or
minimize a linear function, subject to a set of linear
constraints.
• The linear model consists of the following
components:
• A set of decision variables.
• An objective function.
• A set of constraints.
 Standard Form of LP
• LP involves 3 parts
1.Objective function (maximize or minimize)
Max c1x1 + c2x2 + ... + cnxn
Xj known as decision variables
2.Constraints
Subject to:
a11x1 + a12x2 + ... < = > b1
a21x1 + a22x2 + ... < = > b2
a31x1 + a32x2 + ... < = > b3

ai1x1 + ai2x2 + ... < = > bi

am1x1 + am2x2 + ... < = > bm

3. Non-Negativity
xj >= 0 for all i
LP Assumptions
There are three main assumptions of LP
1. Linearity
2. Additivity
3. Non-Negativity
1. Linearity
• Linearity of Objective Function and Constraints
–Essential Condition is:
f(kX) = k f(X)
• Implies
–Constant returns to scale (only first order terms)
–No "fixed charges" (no constants)
2. Additivity
• f(X1, X2, ... , Xn) = f(X1) + f(X2) + ... + f(Xn)
• No interactive effects among Xi terms
• Assumes that individual segments of the problem operate
as well independently as together

3. Non-Negativity
• Xj >= 0
• No fundamental difficulties except in particular situations
 LP Summary
• Linear programming is applicable to optimization
problem with linear objective function and linear
constraints set:
𝑛

𝑀𝑎𝑥𝑍 = 𝑓(𝑥)
lj = ෍ 𝑐𝑗 𝑥𝑗
j=1,2,….,n
𝑗=1
n
S.t. a
j =1
ij x j  bi i=1,2,….,m

xj  0 j=1,2,….,n
Another form in matrix and vector notations is as follows:

M ax Z = C T X
S.t. AX  b
X 0
Or M in Z = C T X
AX  b
X 0
Where
 c1   x1   b1  0
c  x  b  0
C =  2 , X =  2 , b = 2  , 0= 
       
       
cn   xn  bm 0
  a1,1 a1, n ...... a1, n 
 
 a2 ,1 a2, 2 ...... a2 , n 
A=
 ...... 
 
 a m ,1 am , 2 ...... am , n 
 16

First Example: The Industries Production

Problem
• An industry produces water fittings products and
owns 3 plants
• Company decides to produce two new Products

• Definition of the problem:

Determine what the production rates should be for each of
the two products in order to maximize their total profit, subject
to restrictions imposed by the limited production capacities
available in the three plants
 17

First Example: The Industries Production

Problem
• WGC produces glass products and owns 3 plants

• Company decides to produce two new Products

• Definition of the problem:

Determine what the production rates should be for each of
the two products in order to maximize their total profit, subject
to restrictions imposed by the limited production capacities
available in the three plants
 18

Relevant Data
• Product 1
• 1 hour production time in Plant 1 per batch
• 3 hours production time in Plant 3 per batch
• $3,000 profit per batch
• Product 2
• 2 hours production time in Plant 2 per batch
• 2 hours production time in Plant 3 per batch
• $5,000 profit per batch
• Production time available each week
• Plant 1: 4 hours
• Plant 2: 12 hours
• Plant 3: 18 hours
 19

First Example (cont.)

 20

Model Formulation
• Identify the decision variables:
x1 – Number of batches of product 1 produced per week.
x2 – Number of batches of product 2 produced per week.

• Identify the problem constraints and express the constraints

as a series of linear equations.
1x1 + 0 x2  4
0 x1 + 2 x2  12
3x1 + 2 x2  18
• Identify the objective function as a linear equation, and
state whether the objective is maximization or minimization.
max Z = 3x1 + 5x2
 21

Mathematical Formulation

Maximize 𝑍 = 3𝑥1 + 5 𝑥2

subject to constraints
𝑥1 ≤4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
and
𝑥1 ≥ 0, 𝑥2 ≥ 0
 22

Graphical Solution
• This simple problem has only two variables, and thus has
two dimensions only
• Graphical solution can be used to solve it:
1. Identify values of x1 and x2 allowed by constraints (feasible
region)
2. Pick out point in the feasible region that maximizes the objective
function
 23

Graphical Solution (cont.)

𝑥1 ≥ 0

𝑥2 ≥ 0

𝑥1 ≤ 4

2𝑥2 ≤ 12
 24

Graphical Solution (cont.)

3𝑥1 + 2𝑥2 ≤ 18
 25

Graphical Solution (cont.)

𝑍 = 3𝑥1 + 5 𝑥2
 26

The Linear Programming Model (cont.)

• Common Symbols:

Z = value of overall measure of performance

xj = level of activity j (for j =1, 2, …, n) (Decision Variable)
cj = increase in Z that would result from unit increase
in level of activity j
bi = amount of resource i available for allocation to
activities (for i = 1, 2, …, m)
aij = amount of resource i consumed by each unit of
activity j
 27

Data Needed
 28

Standard Form of the LP Model

• Maximize 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + … + 𝑐𝑛 𝑥𝑛

• subject to the constraints

𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
:
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
• and
𝑥1 ≥ 0, 𝑥2 ≥ 0, … , 𝑥𝑛 ≥ 0
 29

Other Forms
• Minimize rather than maximize objective function

Minimize 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + … + 𝑐𝑛 𝑥𝑛
• Some function constraints with (≥)
𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 ≥ 𝑏𝑖 for some values of i
• Some functional constraints in equation form

𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 = 𝑏𝑖 for some values of i

• Deleting non-negativity constraints

xj unrestricted in sign for some value of j

 30

Terminology for Solution

• 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
• Corner Point Feasible (CPF) Solution – A solution that
lies at a corner of the feasible region
31
 32

No Feasible Solutions
33
 34

Multiple Optimal Solutions

35
 36

No Optimal Solution
 37

Corner-Point Feasible (CPF) Solutions

• Consider any LP problem with
feasible solutions and a bounded
feasible region
• The problem must possess CPF
solutions and at least one optimal
solution
• The best CPF solution must be
an optimal solution
• If the problem has one optimal
solution, it must be a CPF
solution
• If the problem has multiple
optimal solutions, at least two
must be CPF solutions
 38

Assumptions of Linear Programming

• Proportionality – The contribution of each activity to Z or
a constraint is proportional to the level of activity xj
• Additivity – Every function is the sum of the individual
contributions of the activities

Z = 3x1 + 5x2 + x1x2 

• 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
 39

Post-Optimality Analysis
• Reoptimization
• Real LP models may have hundreds, thousands, or
even millions of constraints and decision variables
• Many variations of the basic model may be of interest
for considering different scenarios
• After having found an optimal solution, may need to
solve again (often many times) for a slightly different
version of the model
• In this case, starting at the previously obtained solution
(if feasible) is much more efficient.
• New solution is usually much closer to prior optimal
solution, so usually a few iterations are needed.
 40

Post-Optimality Analysis (cont.)

• Shadow Prices
The shadow price for resource i (denoted yi*) measures the marginal
value of this resource, i.e., the rate at which Z could be increased by
(slightly) increasing the available amount of this resource (bi)
∗ ∗
3
𝑦1 = 0, 𝑦2 = , 𝑦3∗ = 1
2
 41

Post-Optimality Analysis (cont.)

• “Binding” and
“Unbinding”
constraints
• “Free” and
Maximize 𝑍 = 3𝑥1 + 5 𝑥2
“Scarce”
subject to constraints
resources 𝑥1 ≤4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
and
𝑥1 ≥ 0, 𝑥2 ≥ 0

𝑦1∗ = 0 → constraint (1) is not binding (there is surplus, x3 = 2) (free)

3
𝑦2∗ = , 𝑦3∗ = 1 → const. (2) and (3) are binding (slack vars. = 0) (scarce)
2
Shadow Price Definition
• Recall from Constrained Optimization:
• Shadow price = change objective function/ change in constraint
• at the optimum
• Complementary Slackness:

Either (Slack variable) or (shadow price) = 0

Sensitivity Analysis
• Sensitivity (or post optimality) analysis is an attempt to
study the manner in which the values of the decision
variables in a mathematical model change as the
parameters of the model change
• Sensitivity analysis is a method for dealing with
uncertainty
Why Sensitivity Analysis
• Math problem is an approximation
• optimum is an approximation
• we need to check
• Constraints often artificial
• Designer should question them
• Should we have different specifications?
• Situations always probabilistic
• Prices change
• Need to assess risk
Sensitivity Parameters
n

• Optimize C X
j =1
j j

ST. n

a
J =1
ij X j = bi i = 1,2,......m

• Changes in the objective-function coefficients (Cj)

• Change in in the technological coefficients (aij)
• Changes in the right-hand sides bi
 46

For 𝑐2 = 5:
0 ≤ 𝑐1 ≤ 7.5
For 𝑐1 = 3:
𝑐2 ≥ 2
In general:
𝑐1
0 ≤ ≤ 1.5
𝑐2
Maximize 𝒁 = 𝟑𝒙𝟏 + 𝟓 𝒙𝟐
Also,
subject to constraints 2 ≤ 𝑏1
𝒙𝟏 ≤𝟒 6 ≤ 𝑏2 ≤ 18
𝟐𝒙𝟐 ≤ 𝟏𝟐
𝟑𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟏𝟖 12 ≤ 𝑏3 ≤ 24
and
𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎