Chapter 3
Introduction to Linear
Programming
Frederick S. Hillier Gerald J. Lieberman
© 2015 McGraw-Hill Education. All rights reserved.
© 2015 McGraw-Hill Education. All rights reserved.
Introduction
• Linear programming
– Programming means planning
– Model contains linear mathematical functions
• An application of linear programming
– Allocating limited resources among competing
activities in the best possible way
– Applies to wide variety of situations
© 2015 McGraw-Hill Education. All rights reserved. 2
3.1 Prototype Example
• Wyndor Glass Co.
– Produces windows and glass doors
– Plant 1 makes aluminum frames and
hardware
– Plant 2 makes wood frames
– Plant 3 produces glass and assembles
products
© 2015 McGraw-Hill Education. All rights reserved. 3
Prototype Example
• Company introducing two new products
– Product 1: 8 ft. glass door with aluminum
frame
– Product 2: 4 x 6 ft. double-hung, wood-framed
window
• Problem: What mix of products would be
most profitable?
– Assuming company could sell as much of
either product as could be produced
© 2015 McGraw-Hill Education. All rights reserved. 4
Prototype Example
• Products produced in batches of 20
• Data needed
– Number of hours of production time available
per week in each plant for new products
– Production time used in each plant for each
batch of each new product
– Profit per batch of each new product
© 2015 McGraw-Hill Education. All rights reserved. 5
Prototype Example
© 2015 McGraw-Hill Education. All rights reserved. 6
Prototype Example
• Formulating the model
x1 = number of batches of product 1 produced
per week
x2 = number of batches of product 2 produced
per week
Z = total profit per week (thousands of dollars)
from producing these two products
• From bottom row of Table 3.1
© 2015 McGraw-Hill Education. All rights reserved. 7
Prototype Example
• Constraints (see Table 3.1)
• Classic example of resource-allocation
problem
– Most common type of linear programming
problem
© 2015 McGraw-Hill Education. All rights reserved. 8
Prototype Example
• Problem can be solved graphically
– Two dimensional graph with x1 and x2 as the
axes
– First step: identify values of x1 and x2
permitted by the restrictions
• See Figures 3.1 and Figure 3.2
– Next step: pick a point in the feasible region
that maximizes value of Z
• See Figure 3.3
© 2015 McGraw-Hill Education. All rights reserved. 9
Prototype Example
© 2015 McGraw-Hill Education. All rights reserved. 10
Prototype Example
© 2015 McGraw-Hill Education. All rights reserved. 11
Prototype Example
© 2015 McGraw-Hill Education. All rights reserved. 12
3.2 The Linear Programming Model
• General problem terminology and
examples
– Resources: money, particular types of
machines, vehicles, or personnel
– Activities: investing in particular projects,
advertising in particular media, or shipping
from a particular source
• Problem involves choosing levels of
activities to maximize overall measure of
performance
© 2015 McGraw-Hill Education. All rights reserved. 13
The Linear Programming Model
© 2015 McGraw-Hill Education. All rights reserved. 14
The Linear Programming Model
• Standard form
© 2015 McGraw-Hill Education. All rights reserved. 15
The Linear Programming Model
• Other legitimate forms
– Minimizing (rather than maximizing) the
objective function
– Functional constraints with greater-than-or-
equal-to inequality
– Some functional constraints in equation form
– Some decision variables may be negative
© 2015 McGraw-Hill Education. All rights reserved. 16
The Linear Programming Model
• Feasible solution
– Solution for which all constraints are satisfied
– Might not exist for a given problem
• Infeasible solution
– Solution for which at least one constraint is
violated
• Optimal solution
– Has most favorable value of objective function
– Might not exist for a given problem
© 2015 McGraw-Hill Education. All rights reserved. 17
The Linear Programming Model
• Corner-point feasible (CPF) solution
– Solution that lies at the corner of the feasible
region
• Linear programming problem with feasible
solution and bounded feasible region
– Must have CPF solutions and optimal
solution(s)
– Best CPF solution must be an optimal solution
© 2015 McGraw-Hill Education. All rights reserved. 18
3.3 Assumptions of Linear Programming
• Proportionality assumption
– The contribution of each activity to the value
of the objective function (or left-hand side of a
functional constraint) is proportional to the
level of the activity
– If assumption does not hold, one must use
nonlinear programming (Chapter 13)
© 2015 McGraw-Hill Education. All rights reserved. 19
Assumptions of Linear Programming
• Additivity
– Every function in a linear programming model
is the sum of the individual contributions of
the activities
• Divisibility
– Decision variables in a linear programming
model may have any values
• Including noninteger values
– Assumes activities can be run at fractional
values
© 2015 McGraw-Hill Education. All rights reserved. 20
Assumptions of Linear Programming
• Certainty
– Value assigned to each parameter of a linear
programming model is assumed to be a
known constant
– Seldom satisfied precisely in real applications
• Sensitivity analysis used
© 2015 McGraw-Hill Education. All rights reserved. 21
3.4 Additional Examples
• Example 1: Design of radiation therapy for
Mary’s cancer treatment
– Goal: select best combination of beams and
their intensities to generate best possible
dose distribution
• Dose is measured in kilorads
© 2015 McGraw-Hill Education. All rights reserved. 22
Example 1: Radiation Therapy Design
© 2015 McGraw-Hill Education. All rights reserved. 23
Example 1: Radiation Therapy Design
• Linear programming model
– Using data from Table 3.7
© 2015 McGraw-Hill Education. All rights reserved. 24
Example 1: Radiation Therapy Design
• A type of cost-
benefit tradeoff
problem
© 2015 McGraw-Hill Education. All rights reserved. 25
Example 2: Reclaiming Solid Wastes
• SAVE-IT company collects and treats four
types of solid waste materials
– Materials amalgamated into salable products
– Three different grades of product possible
– Fixed treatment cost covered by grants
– Objective: maximize the net weekly profit
• Determine amount of each product grade
• Determine mix of materials to be used for each
grade
© 2015 McGraw-Hill Education. All rights reserved. 26
Example 2: Reclaiming Solid Wastes
© 2015 McGraw-Hill Education. All rights reserved. 27
Example 2: Reclaiming Solid Wastes
© 2015 McGraw-Hill Education. All rights reserved. 28
Example 2: Reclaiming Solid Wastes
• Decision variables
(for i = A, B, C; j = 1,2,3,4)
number of pounds of material j allocated to
product grade i per week
• See Pages 56-57 in the text for solution
© 2015 McGraw-Hill Education. All rights reserved. 29
3.5 Formulating and Solving Linear
Programming Models on a Spreadsheet
• Excel and its Solver add-in
– Popular tools for solving small linear
programming problems
© 2015 McGraw-Hill Education. All rights reserved. 30
Formulating and Solving Linear
Programming Models on a Spreadsheet
• The Wyndor example
– Data entered into a spreadsheet
© 2015 McGraw-Hill Education. All rights reserved. 31
Formulating and Solving Linear
Programming Models on a Spreadsheet
• Changing cells
– Cells containing the decisions to be made
– C12 and D12 in the Wyndor example below
© 2015 McGraw-Hill Education. All rights reserved. 32
Formulating and Solving Linear
Programming Models on a Spreadsheet
© 2015 McGraw-Hill Education. All rights reserved. 33
Formulating and Solving Linear
Programming Models on a Spreadsheet
© 2015 McGraw-Hill Education. All rights reserved. 34
3.6 Formulating Very Large Linear
Programming Models
• Actual linear programming models
– Can have hundreds or thousands of functional
constraints
– Number of decision variables may also be
very large
• Modeling language
– Used to formulate very large models in
practice
– Expedites model management tasks
© 2015 McGraw-Hill Education. All rights reserved. 35
Formulating Very Large Linear
Programming Models
• Modeling language examples
– AMPL, MPL, OPL, GAMS, and LINGO
• Example problem with a huge model
– See Pages 73-78 in the text
© 2015 McGraw-Hill Education. All rights reserved. 36
3.7 Conclusions
• Linear programming technique
applications
– Resource-allocation problems
– Cost-benefit tradeoffs
• Not all problems can be formulated to fit a
linear programming model
– Alternatives: integer programming or
nonlinear programming models
© 2015 McGraw-Hill Education. All rights reserved. 37
