# Operationalizing Linear Models Excel Task

Problem #1 Embassy Motorcycles (EM) manufacturers two lightweight motorcycles designed for easy handling and safety. The K250 model has a new engine and a low profile that make it easy to balance. The QX-500 model is slightly larger, uses a more traditional engine, and is specifically designed to appeal to women riders. Embassy produces the engines for both models at its Jeddah plant. Each K250 engine requires 6 hours of manufacturing time and each QX-500 engine requires 3 hours of manufacturing time. The Jeddah plant has 2100 hours of engine manufacturing time available for the next production period. Embassy’s motorcycle frame supplier can supply as many K250 frames as needed. However, the QX-500 frame is more complex and the supplier can only provide up to 280 QX-500 frames for the next production period. Final assembly and testing requires 2 hours for each K250 model and 2.5 hours for each QX-500 model. A maximum of 1000 hours of assembly and testing time are available for the next production period. The company’s accounting department projects a profit contribution of $2400 for each K250 produced and $1800 for each QX-500 produced. Formulate a linear programming model that can be used to determine the number of units of each model that should be produced in order to maximize the total contribution to profit.

In-class Practice Exercises: Formulating a Linear Programming Model

Problem #1

Embassy Motorcycles (EM) manufacturers two lightweight motorcycles designed for easy handling and

safety. The K250 model has a new engine and a low profile that make it easy to balance. The QX-500

model is slightly larger, uses a more traditional engine, and is specifically designed to appeal to women

riders. Embassy produces the engines for both models at its Jeddah plant. Each K250 engine requires 6

hours of manufacturing time and each QX-500 engine requires 3 hours of manufacturing time. The

Jeddah plant has 2100 hours of engine manufacturing time available for the next production period.

Embassy’s motorcycle frame supplier can supply as many K250 frames as needed. However, the QX-500

frame is more complex and the supplier can only provide up to 280 QX-500 frames for the next

production period. Final assembly and testing requires 2 hours for each K250 model and 2.5 hours for

each QX-500 model. A maximum of 1000 hours of assembly and testing time are available for the next

production period. The company’s accounting department projects a profit contribution of $2400 for

each K250 produced and $1800 for each QX-500 produced.

Formulate a linear programming model that can be used to determine the number of units of each

model that should be produced in order to maximize the total contribution to profit.

Problem #2

Mohammed recently inherited a large sum of money; he wants to use a portion of this money to set up

a trust fund for his two children. The trust fund has two investment options: (1) a bond fund and (2) a

stock fund. The projected returns over the life of the investments are 6% for the bond fund and 10% for

the stock fund. Whatever portion of the inheritance Mohammed finally decides to commit to the trust

fund, he wants to invest at least 30% of that amount in the bond fund. In addition, he wants to select a

mix that will enable him to obtain a total return of at least 7.5%.

Formulate a linear programming model that can be used to determine the percentage that should be

allocated to each of the possible investment alternatives.

Problem #3

Blue Ocean Restaurant would like to determine the best way to allocate a monthly advertising budget of

SAR 4,000 between poster advertising and online advertising. Management decided that at least 25% of

the budget must be spent on each type of media, and that the amount of money spent on local poster

advertising must be at least twice the amount spent on online advertising. A marketing consultant

developed an index that measures audience exposure per dollar of advertising on a scale from 0 to 100,

with higher values implying greater audience exposure. If the value of the index for local poster

advertising is 50 and the value of the index for online advertising is 80, how should the restaurant

allocate its advertising budget in order to maximize the value of total audience exposure?

Formulate a linear programming model that can be used to determine how the restaurant should

allocate its advertising budget in order to maximize the value of total audience exposure.

Linear Programming

DR JOEL M. EVANS

Housekeeping

• Midterm #1

• Remaining Deliverables

2

Review: Tools of Analysis

Analysis

Purpose

Descriptive statistics

•

What do the data look like?

•

What is the central tendency of the data?

•

How spread out are the data?

•

What is the relationship between two

variables?

•

What value of an input do we need to

achieve a specified value of an output?

•

E.g., break-even point; profit goal

1-way data table

•

How does the value of an outcome change

in response to a range of different values of

an input?

2-way data table

•

How does the value of an outcome change

in response to a range of respective values

for two separate inputs?

Goal seek

3

Review: Tools of Analysis

Analysis

Purpose

Moving averages &

exponential smoothing

•

How might we predict the value of a

variable based on its past values?

Multiple regression

•

How might we predict the value of a

variable based on a set of other variables?

•

Which input variables are significant

predictors of an outcome variable?

•

How does the predictive ability of an input

variable change once we control for other

input variables?

•

What is the equation for modeling these

predictive relationships?

•

Value optimization: What combination of

input values do we need to maximize or

minimize a certain output value, accounting

for certain constraints?

Linear Programming

4

The Textbook

.

.

.

.

.

.

.

.

.

.

.

.

SLIDES BY

John Loucks

St. Edward’s Univ.

Chapter 7

5

Ch 7: Introduction to Linear Programming

•

•

•

•

•

•

•

•

Linear Programming Problem

Problem Formulation

A Simple Maximization Problem

Graphical Solution Procedure

Extreme Points and the Optimal Solution

Computer Solutions

A Simple Minimization Problem

Special Cases

6

Linear Programming

• Linear programming has nothing to do with

computer programming.

• The use of the word “programming” here means

“choosing a course of action.”

7

Mathematical Programming

• Mathematical programming is the development of

modeling and solution procedures which employ

mathematical techniques to optimize the goals and

objectives of the decision-maker.

• Programming problems determine the optimal

allocation of scarce resources to meet certain

objectives.

8

Components of an LP Formation

1)

Decision Variables

–

2)

The things we can control

Objective Function

–

3)

The goal

Constraints

–

4)

Limitations that we cannot control

Non-negativity Conditions

–

Often a natural constraint that is mathematically necessary

9

Decision Variables

• Decision variables represent unknown quantities.

The solution for these terms are what we would

like to optimize.

10

Objective Function

• The objective function states the goal of the decisionmaker. There are two types of objectives:

– Maximization, or

– Minimization

11

Constraints

• Constraints put limitations on the possible solutions of the

problem. The availability of scarce resources may be

expressed as equations or inequalities which rule out

certain combinations of variable values as feasible

solutions.

12

Non-negativity Conditions

• Non-negativity constraints are special constraints which

require all variables to be either zero or positive.

13

Linear Programming (LP) Problem

• A feasible solution satisfies all the problem’s constraints.

• An optimal solution is a feasible solution that results in the

largest possible objective function value when maximizing

(or smallest when minimizing).

• A graphical solution method can be used to solve a linear

program with two variables.

14

Linear Programming (LP) Problem

• If both the objective function and the constraints are linear,

the problem is referred to as a linear programming

problem.

• Linear functions are functions in which each variable

appears in a separate term raised to the first power and is

multiplied by a constant (which could be 0).

• Linear constraints are linear functions that are restricted to

be “less than or equal to”, “equal to”, or “greater than or

equal to” a constant.

15

Problem Formulation

• Problem formulation or modeling is the process of

translating a verbal statement of a problem into a

mathematical statement.

• Formulating models is an art that can only be mastered

with practice and experience.

• Every LP problems has some unique features, but most

problems also have common features.

• General guidelines for LP model formulation are illustrated

on the slides that follow.

16

Guidelines for Model Formulation

•

•

•

•

•

•

Understand the problem thoroughly.

Describe the objective.

Describe each constraint.

Define the decision variables.

Write the objective in terms of the decision variables.

Write the constraints in terms of the decision variables.

17

Redwood Furniture Company

Resource

Wood

Labor

Unit Profit

Unit Requirements

Table

Chair

30

5

6

20

10

8

Amount

Available

300

110

18

Redwood Problem Formulation

Let:

XT = number of tables produced

XC = number of chairs produced

Z = profit

MAX Z = 6 XT + 8 XC

s.t.

(subject to)

where:

30 XT + 20 XC < 300
5 XT + 10 XC < 110
XT, XC > 0

19

Cabinets Problem Formulation

• You need to buy some filing cabinets. You know that:

• -Cabinet X costs $10 per unit, requires six square feet

of floor space, and holds eight cubic feet of files.

• -Cabinet Y costs $20 per unit, requires eight square feet

of floor space, and holds twelve cubic feet of files.

• You have been given $140 for this purchase, though

you don’t have to spend that much. The office has room

for no more than 72 square feet of cabinets. How many

of which model should you buy, in order to maximize

storage volume?

20

Cabinets Problem Formulation

• Maximise z = 8x + 12y

• s.t.

10x + 20y < 140
6x + 8y < 72
(cost)
(space)
• Non-negativity
x>0

y>0

21

Practice Exercises

1)

2)

3)

Go to the Content tab in Blackboard, and navigate to the

Practice Exercises folder.

Find the file called, “Practice exercises: Formulating

linear models”

Work through the problems as a group, and be prepared

to present your problem formulation.

22

Graphical LP Solution Procedure

1)

2)

3)

4)

5)

6)

7)

8)

Formulate the LP problem

Plot the constraints on a graph

Identify the feasible solution region

Plot two objective function lines

Determine the direction of improvement

Find the most attractive corner

Determine the coordinates of the corner

Find the value of the objective function

23

Example 1: A Simple Maximization Problem

• LP Formulation

Max

s.t.

5×1 + 7×2

x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1 > 0 and x2 > 0

Objective

Function

“Regular”

Constraints

Non-negativity

Constraints

24

Example 1: Graphical Solution

• First Constraint Graphed

x2

8

x1 = 6

7

6

5

4

3

Shaded region

contains all

feasible points

for this constraint

2

(6, 0)

1

1

2

3

4

5

6

7

8

9

10

x1

25

Example 1: Graphical Solution

• Second Constraint Graphed

x2

8

(0, 6.33)

7

6

2×1 + 3×2 = 19

5

4

3

2

1

Shaded

region contains

all feasible points

for this constraint

1

2

3

4

5

6

(9.5, 0)

7

8

9

10

x1

26

Example 1: Graphical Solution

• Third Constraint Graphed

x2

(0, 8)

8

7

x1 + x2 = 8

6

5

4

3

2

1

Shaded

region contains

all feasible points

for this constraint

1

2

3

4

5

(8, 0)

6

7

8

9

10

x1

27

Example 1: Graphical Solution

• Combined-Constraint Graph Showing Feasible Region

x2

x1 + x2 = 8

8

7

x1 = 6

6

5

4

3

2×1 + 3×2 = 19

Feasible

Region

2

1

1

2

3

4

5

6

7

8

9

10

x1

28

Example 1: Graphical Solution

• Objective Function Line

x2

8

7

(0, 5)

6

Objective Function

5×1 + 7×2 = 35

5

4

3

2

(7, 0)

1

1

2

3

4

5

6

7

8

9

10

x1

29

Example 1: Graphical Solution

Selected Objective Function Lines

x2

8

7

5×1 + 7×2 = 35

6

5×1 + 7×2 = 39

5

4

5×1 + 7×2 = 42

3

2

1

1

2

3

4

5

6

7

8

9

10

x1

30

Example 1: Graphical Solution

Optimal Solution

x2

Maximum

Objective Function Line

5×1 + 7×2 = 46

8

7

Optimal Solution

(x1 = 5, x2 = 3)

6

5

4

3

2

1

1

2

3

4

5

6

7

8

9

10

x1

31

Summary: Graphical Solution for Maximization

• Prepare a graph of the feasible solutions for each of the

constraints.

• Determine the feasible region that satisfies all the

constraints simultaneously.

• Draw an objective function line.

• Move parallel objective function lines toward larger

objective function values without entirely leaving the

feasible region.

• Any feasible solution on the objective function line with the

largest value is an optimal solution.

32

Slack and Surplus Variables

• A linear program in which all variables are non-negative

and all constraints are expressed as equalities is said to

be in standard form.

• Standard form is attained by adding slack variables to

“less than or equal to” constraints (and by subtracting

surplus variables from “greater than or equal to”

constraints).

• Slack (and surplus) variables represent the difference

between the left and right sides of the constraints.

• Slack (and surplus) variables have objective function

coefficients equal to 0.

33

Example 1: A Simple Maximization Problem

• LP Formulation

Max

s.t.

5×1 + 7×2

x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1 > 0 and x2 > 0

Objective

Function

“Regular”

Constraints

Non-negativity

Constraints

34

Slack Variables (for < constraints)
Example 1 in Standard Form
Max
s.t.
5x1 + 7x2 + 0s1 + 0s2 + 0s3
x1 + s1 = 6
2x1 + 3x2 + s2 = 19
x1 + x2 + s3 = 8
x1, x2 , s1 , s2 , s3 > 0

s1 , s2 , and s3

are slack variables

35

Slack Variables

Optimal Solution

x2

Third

Constraint:

x1 + x2 = 8

8

7

First

Constraint:

x1 = 6

s3 = 0

s1 = 1

6

5

Second

Constraint:

2×1 + 3×2 = 19

4

3

2

1

Optimal

Solution

(x1 = 5, x2 = 3)

1

2

3

4

5

s2 = 0

6

7

8

9

10

x1

36

Extreme Points and the Optimal Solution

• The corners or vertices of the feasible region are referred

to as the extreme points.

• An optimal solution to an LP problem can be found at an

extreme point of the feasible region.

• When looking for the optimal solution, you do not have to

evaluate all feasible solution points.

• You have to consider only the extreme points of the

feasible region.

37

Example 1: Extreme Points

x2

8

7

5 (0, 6.33)

6

5

4

4 (5, 3)

3

Feasible

Region

2

1

3 (6, 2)

2 (6, 0)

1 (0, 0)

1

2

3

4

5

6

7

8

9

10

x1

38

Computer Solutions

• LP problems involving 1000s of variables and 1000s of

constraints are now routinely solved with computer

packages.

• Linear programming solvers are now part of many

spreadsheet packages, such as Microsoft Excel.

• Leading commercial packages include CPLEX, LINGO,

MOSEK, Xpress-MP, and Premium Solver for Excel.

39

Interpretation of Computer Output

• We will discuss the following output:

– Objective function value

– Values of the decision variables

– Reduced costs

– Slack and surplus

• An optimal solution is affected by a change in:

– A coefficient of the objective function

– The right-hand side value of a constraint

40

Example 1: Spreadsheet Solution

Partial Spreadsheet Showing Solution

A

8

9

10

11

12

13

14

15

16

17

B

C

Optimal Decision Variable Values

X1

X2

5.0

3.0

Maximized Objective Function

Constraints

#1

#2

#3

Amount Used

5

19

8

D

46.0

4

x1, x2 > 0

44

Example 2: Graphical Solution

• Graph the Constraints:

– Constraint 1

• When x1 = 0, then x2 = 2; when x2 = 0, then x1 = 5.

Connect (5,0) and (0,2). The “>” side is above this line.

– Constraint 2

• When x2 = 0, then x1 = 3. But setting x1 to 0 will yield x2

= -12, which is not on the graph. Thus, to get a second point

on this line, set x1 to any number larger than 3 and solve for

x2: when x1 = 5, then x2 = 8. Connect (3,0) and (5,8). The

“>“ side is to the right.

45

Example 2: Graphical Solution

• Graph the Constraints (continued)

– Constraint 3

• When x1 = 0, then x2 = 4

• When x2 = 0, then x1 = 4.

• Connect (4,0) and (0,4). The “>” side is above this line.

46

Example 2: Graphical Solution

Constraints Graphed

x2

6

Feasible Region

5

4×1 – x2 > 12

4

x1 + x2 > 4

3

2×1 + 5×2 > 10

2

1

x1

1

2

3

4

5

6

47

Example 2: Graphical Solution

• Graph the Objective Function

– Set the objective function equal to an arbitrary constant

(say 20) and graph it. For 5×1 + 2×2 = 20, when x1 = 0,

then x2 = 10; when x2= 0, then x1 = 4. Connect (4,0)

and (0,10).

• Move the Objective Function Line Toward

Optimality

–

Move it in the direction which lowers its value (down),

since we are minimizing, until it touches the last point of

the feasible region, determined by the last two

constraints.

48

Example 2: Graphical Solution

Objective Function Graphed

x2

Min 5×1 + 2×2

6

5

4×1 – x2 > 12

4

x1 + x2 > 4

3

2×1 + 5×2 > 10

2

1

1

2

3

4

5

6

x1

49

Example 2: Graphical Solution

Solve for the Extreme Point at the Intersection of the

Two Binding Constraints

4×1 – x2 = 12

x1+ x2 = 4

Adding these two equations gives:

5×1 = 16 or

x1 = 3.2

Substituting this into x1 + x2 = 4 gives: x2 = 0.8

Solve for the Optimal Value of the Objective

Function

5×1 + 2×2 = 5(3.2) + 2(0.8) = 17.6

50

Example 2: Graphical Solution

Optimal Solution

x2

6

4×1 – x2 > 12

5

x1 + x2 > 4

4

Optimal Solution:

x1 = 3.2, x2 = 0.8,

3

5×1 + 2×2 = 17.6

2

2×1 + 5×2 > 10

1

1

2

3

4

5

6

x1

51

Summary: Graphical Solution for Minimization

• Prepare a graph of the feasible solutions for each of the

constraints.

• Determine the feasible region that satisfies all the

constraints simultaneously.

• Draw an objective function line.

• Move parallel objective function lines toward smaller

objective function values without entirely leaving the

feasible region.

• Any feasible solution on the objective function line with the

smallest value is an optimal solution.

52

Surplus Variables

Example 2 in Standard Form

Min

5×1 + 2×2 + 0s1 + 0s2 + 0s3

s.t.

2×1 + 5×2 – s1 = 10

4×1 – x2 – s2 = 12

x1 + x2 – s3 = 4

s1 , s2 , and s3

> 0

are surplus

variables

x1, x2, s1, s2, s3

53

Example 2: Spreadsheet Solution

Partial Spreadsheet Showing Solution

A

B

C

Decision Variables

X1

X2

3.20

0.800

9

10

11 Dec.Var.Values

12

13

Minimized Objective Function

14

15

Constraints

Amount Used

16

#1

10.4

17

#2

12

18

#3

4

D

17.600

>=

>=

>=

Amount Avail.

10

12

4

54

Example 2: Spreadsheet Solution

Interpretation of Computer Output

We see from the previous slide that:

Objective Function Value = 17.6

Decision Variable #1 (x1) = 3.2

Decision Variable #2 (x2) = 0.8

Surplus in Constraint #1 = 10.4 – 10 = 0.4

Surplus in Constraint #2 = 12.0 – 12 = 0.0

Surplus in Constraint #3 = 4.0 – 4 = 0.0

55

Feasible Region

• The feasible region for a two-variable LP problem can be

nonexistent, a single point, a line, a polygon, or an

unbounded area.

• Any linear program falls into one of four categories:

– Is infeasible

– Has a unique optimal solution

– Has alternative optimal solutions

– Has an objective function that can be increased without bound

• A feasible region may be unbounded and yet there may be

optimal solutions. This is common in minimization

problems and is possible in maximization problems.

56

Special Cases

Alternative Optimal Solutions

In the graphical method, if the objective function line is

parallel to a boundary constraint in the direction of

optimization, there are alternate optimal solutions, with all

points on this line segment being optimal.

57

Example: Alternative Optimal Solutions

Consider the following LP problem.

Max 4×1 + 6×2

s.t.

x1 < 6
2x1 + 3x2 < 18
x1 + x2 < 7
x1 > 0 and x2 > 0

58

Example: Alternative Optimal Solutions

Boundary constraint 2×1 + 3×2 < 18 and objective
function Max 4x1 + 6x2 are parallel. All points on the
line segment A – B are optimal solutions.
7
6
5
x2
x1 + x2 < 7
A
B
4
x1 < 6
2x1 + 3x2 < 18
3
2
1
1
2
3
4
5
6
7
x1
8
9
10
59
Special Cases
• Infeasibility
– No solution to the LP problem satisfies all the
constraints, including the non-negativity conditions.
– Graphically, this means a feasible region does not exist.
– Causes include:
• A formulation error has been made.
• Management’s expectations are too high.
• Too many restrictions have been placed on the problem (i.e.,
the problem is over-constrained).
60
Example: Infeasible Problem
Consider the following LP problem:
Max
2x1 + 6x2
s.t.
4x1 + 3x2 < 12
2x1 + x2 > 8

x1, x2 >

0

61

Example: Infeasible Problem

There are no points that satisfy both constraints, so there

is no feasible region (and no feasible solution).

x2

10

2×1 + x2 > 8

8

6

4×1 + 3×2 < 12
4
2
2
4
6
8
10
x1
62
Special Cases
• Unbounded
– The solution to a maximization LP problem is unbounded if the
value of the solution may be made indefinitely large without
violating any of the constraints.
– For real problems, this is the result of improper formulation. (Quite
likely, a constraint has been inadvertently omitted.)
63
Example: Unbounded Solution
Consider the following LP problem.
Max
4x1 + 5x2
s.t.
x1 +
3x1 +
x2 > 5

x2 > 8

x1, x2 > 0

64

Example: Unbounded Solution

The feasible region is unbounded and the objective

function line can be moved outward from the origin

without bound, infinitely increasing the objective function.

x2

10

3×1 + x2 > 8

8

6

4

x1 + x2 > 5

2

2

4

6

8

10

x1

65

Practice Exercises: Operationalizing the LP

1)

2)

3)

4)

First, an instructor demo of Excel Solver

Second, download the Excel file entitled, “Practice

exercises: Operationalizing linear models”.

Revisit your answers to our earlier exercises (“Practice

exercises: Formulating linear models”) and

operationalize these models in Excel.

Work through the problems as a group and be prepared

to present your problem operationalization.

66

End of Chapter 7

67

Linear Programming

DR JOEL M. EVANS

Housekeeping

• Midterm #1

• Remaining Deliverables

2

Review: Tools of Analysis

Analysis

Purpose

Descriptive statistics

•

What do the data look like?

•

What is the central tendency of the data?

•

How spread out are the data?

•

What is the relationship between two

variables?

•

What value of an input do we need to

achieve a specified value of an output?

•

E.g., break-even point; profit goal

1-way data table

•

How does the value of an outcome change

in response to a range of different values of

an input?

2-way data table

•

How does the value of an outcome change

in response to a range of respective values

for two separate inputs?

Goal seek

3

Review: Tools of Analysis

Analysis

Purpose

Moving averages &

exponential smoothing

•

How might we predict the value of a

variable based on its past values?

Multiple regression

•

How might we predict the value of a

variable based on a set of other variables?

•

Which input variables are significant

predictors of an outcome variable?

•

How does the predictive ability of an input

variable change once we control for other

input variables?

•

What is the equation for modeling these

predictive relationships?

•

Value optimization: What combination of

input values do we need to maximize or

minimize a certain output value, accounting

for certain constraints?

Linear Programming

4

The Textbook

.

.

.

.

.

.

.

.

.

.

.

.

SLIDES BY

John Loucks

St. Edward’s Univ.

Chapter 7

5

Ch 7: Introduction to Linear Programming

•

•

•

•

•

•

•

•

Linear Programming Problem

Problem Formulation

A Simple Maximization Problem

Graphical Solution Procedure

Extreme Points and the Optimal Solution

Computer Solutions

A Simple Minimization Problem

Special Cases

6

Linear Programming

• Linear programming has nothing to do with

computer programming.

• The use of the word “programming” here means

“choosing a course of action.”

7

Mathematical Programming

• Mathematical programming is the development of

modeling and solution procedures which employ

mathematical techniques to optimize the goals and

objectives of the decision-maker.

• Programming problems determine the optimal

allocation of scarce resources to meet certain

objectives.

8

Components of an LP Formation

1)

Decision Variables

–

2)

The things we can control

Objective Function

–

3)

The goal

Constraints

–

4)

Limitations that we cannot control

Non-negativity Conditions

–

Often a natural constraint that is mathematically necessary

9

Decision Variables

• Decision variables represent unknown quantities.

The solution for these terms are what we would

like to optimize.

10

Objective Function

• The objective function states the goal of the decisionmaker. There are two types of objectives:

– Maximization, or

– Minimization

11

Constraints

• Constraints put limitations on the possible solutions of the

problem. The availability of scarce resources may be

expressed as equations or inequalities which rule out

certain combinations of variable values as feasible

solutions.

12

Non-negativity Conditions

• Non-negativity constraints are special constraints which

require all variables to be either zero or positive.

13

Linear Programming (LP) Problem

• A feasible solution satisfies all the problem’s constraints.

• An optimal solution is a feasible solution that results in the

largest possible objective function value when maximizing

(or smallest when minimizing).

• A graphical solution method can be used to solve a linear

program with two variables.

14

Linear Programming (LP) Problem

• If both the objective function and the constraints are linear,

the problem is referred to as a linear programming

problem.

• Linear functions are functions in which each variable

appears in a separate term raised to the first power and is

multiplied by a constant (which could be 0).

• Linear constraints are linear functions that are restricted to

be “less than or equal to”, “equal to”, or “greater than or

equal to” a constant.

15

Problem Formulation

• Problem formulation or modeling is the process of

translating a verbal statement of a problem into a

mathematical statement.

• Formulating models is an art that can only be mastered

with practice and experience.

• Every LP problems has some unique features, but most

problems also have common features.

• General guidelines for LP model formulation are illustrated

on the slides that follow.

16

Guidelines for Model Formulation

•

•

•

•

•

•

Understand the problem thoroughly.

Describe the objective.

Describe each constraint.

Define the decision variables.

Write the objective in terms of the decision variables.

Write the constraints in terms of the decision variables.

17

Redwood Furniture Company

Resource

Wood

Labor

Unit Profit

Unit Requirements

Table

Chair

30

5

6

20

10

8

Amount

Available

300

110

18

Redwood Problem Formulation

Let:

XT = number of tables produced

XC = number of chairs produced

Z = profit

MAX Z = 6 XT + 8 XC

s.t.

(subject to)

where:

30 XT + 20 XC < 300
5 XT + 10 XC < 110
XT, XC > 0

19

Cabinets Problem Formulation

• You need to buy some filing cabinets. You know that:

• -Cabinet X costs $10 per unit, requires six square feet

of floor space, and holds eight cubic feet of files.

• -Cabinet Y costs $20 per unit, requires eight square feet

of floor space, and holds twelve cubic feet of files.

• You have been given $140 for this purchase, though

you don’t have to spend that much. The office has room

for no more than 72 square feet of cabinets. How many

of which model should you buy, in order to maximize

storage volume?

20

Cabinets Problem Formulation

• Maximise z = 8x + 12y

• s.t.

10x + 20y < 140
6x + 8y < 72
(cost)
(space)
• Non-negativity
x>0

y>0

21

Practice Exercises

1)

2)

3)

Go to the Content tab in Blackboard, and navigate to the

Practice Exercises folder.

Find the file called, “Practice exercises: Formulating

linear models”

Work through the problems as a group, and be prepared

to present your problem formulation.

22

Graphical LP Solution Procedure

1)

2)

3)

4)

5)

6)

7)

8)

Formulate the LP problem

Plot the constraints on a graph

Identify the feasible solution region

Plot two objective function lines

Determine the direction of improvement

Find the most attractive corner

Determine the coordinates of the corner

Find the value of the objective function

23

Example 1: A Simple Maximization Problem

• LP Formulation

Max

s.t.

5×1 + 7×2

x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1 > 0 and x2 > 0

Objective

Function

“Regular”

Constraints

Non-negativity

Constraints

24

Example 1: Graphical Solution

• First Constraint Graphed

x2

8

x1 = 6

7

6

5

4

3

Shaded region

contains all

feasible points

for this constraint

2

(6, 0)

1

1

2

3

4

5

6

7

8

9

10

x1

25

Example 1: Graphical Solution

• Second Constraint Graphed

x2

8

(0, 6.33)

7

6

2×1 + 3×2 = 19

5

4

3

2

1

Shaded

region contains

all feasible points

for this constraint

1

2

3

4

5

6

(9.5, 0)

7

8

9

10

x1

26

Example 1: Graphical Solution

• Third Constraint Graphed

x2

(0, 8)

8

7

x1 + x2 = 8

6

5

4

3

2

1

Shaded

region contains

all feasible points

for this constraint

1

2

3

4

5

(8, 0)

6

7

8

9

10

x1

27

Example 1: Graphical Solution

• Combined-Constraint Graph Showing Feasible Region

x2

x1 + x2 = 8

8

7

x1 = 6

6

5

4

3

2×1 + 3×2 = 19

Feasible

Region

2

1

1

2

3

4

5

6

7

8

9

10

x1

28

Example 1: Graphical Solution

• Objective Function Line

x2

8

7

(0, 5)

6

Objective Function

5×1 + 7×2 = 35

5

4

3

2

(7, 0)

1

1

2

3

4

5

6

7

8

9

10

x1

29

Example 1: Graphical Solution

Selected Objective Function Lines

x2

8

7

5×1 + 7×2 = 35

6

5×1 + 7×2 = 39

5

4

5×1 + 7×2 = 42

3

2

1

1

2

3

4

5

6

7

8

9

10

x1

30

Example 1: Graphical Solution

Optimal Solution

x2

Maximum

Objective Function Line

5×1 + 7×2 = 46

8

7

Optimal Solution

(x1 = 5, x2 = 3)

6

5

4

3

2

1

1

2

3

4

5

6

7

8

9

10

x1

31

Summary: Graphical Solution for Maximization

• Prepare a graph of the feasible solutions for each of the

constraints.

• Determine the feasible region that satisfies all the

constraints simultaneously.

• Draw an objective function line.

• Move parallel objective function lines toward larger

objective function values without entirely leaving the

feasible region.

• Any feasible solution on the objective function line with the

largest value is an optimal solution.

32

Slack and Surplus Variables

• A linear program in which all variables are non-negative

and all constraints are expressed as equalities is said to

be in standard form.

• Standard form is attained by adding slack variables to

“less than or equal to” constraints (and by subtracting

surplus variables from “greater than or equal to”

constraints).

• Slack (and surplus) variables represent the difference

between the left and right sides of the constraints.

• Slack (and surplus) variables have objective function

coefficients equal to 0.

33

Example 1: A Simple Maximization Problem

• LP Formulation

Max

s.t.

5×1 + 7×2

x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1 > 0 and x2 > 0

Objective

Function

“Regular”

Constraints

Non-negativity

Constraints

34

Slack Variables (for < constraints)
Example 1 in Standard Form
Max
s.t.
5x1 + 7x2 + 0s1 + 0s2 + 0s3
x1 + s1 = 6
2x1 + 3x2 + s2 = 19
x1 + x2 + s3 = 8
x1, x2 , s1 , s2 , s3 > 0

s1 , s2 , and s3

are slack variables

35

Slack Variables

Optimal Solution

x2

Third

Constraint:

x1 + x2 = 8

8

7

First

Constraint:

x1 = 6

s3 = 0

s1 = 1

6

5

Second

Constraint:

2×1 + 3×2 = 19

4

3

2

1

Optimal

Solution

(x1 = 5, x2 = 3)

1

2

3

4

5

s2 = 0

6

7

8

9

10

x1

36

Extreme Points and the Optimal Solution

• The corners or vertices of the feasible region are referred

to as the extreme points.

• An optimal solution to an LP problem can be found at an

extreme point of the feasible region.

• When looking for the optimal solution, you do not have to

evaluate all feasible solution points.

• You have to consider only the extreme points of the

feasible region.

37

Example 1: Extreme Points

x2

8

7

5 (0, 6.33)

6

5

4

4 (5, 3)

3

Feasible

Region

2

1

3 (6, 2)

2 (6, 0)

1 (0, 0)

1

2

3

4

5

6

7

8

9

10

x1

38

Computer Solutions

• LP problems involving 1000s of variables and 1000s of

constraints are now routinely solved with computer

packages.

• Linear programming solvers are now part of many

spreadsheet packages, such as Microsoft Excel.

• Leading commercial packages include CPLEX, LINGO,

MOSEK, Xpress-MP, and Premium Solver for Excel.

39

Interpretation of Computer Output

• We will discuss the following output:

– Objective function value

– Values of the decision variables

– Reduced costs

– Slack and surplus

• An optimal solution is affected by a change in:

– A coefficient of the objective function

– The right-hand side value of a constraint

40

Example 1: Spreadsheet Solution

Partial Spreadsheet Showing Solution

A

8

9

10

11

12

13

14

15

16

17

B

C

Optimal Decision Variable Values

X1

X2

5.0

3.0

Maximized Objective Function

Constraints

#1

#2

#3

Amount Used

5

19

8

D

46.0

4

x1, x2 > 0

44

Example 2: Graphical Solution

• Graph the Constraints:

– Constraint 1

• When x1 = 0, then x2 = 2; when x2 = 0, then x1 = 5.

Connect (5,0) and (0,2). The “>” side is above this line.

– Constraint 2

• When x2 = 0, then x1 = 3. But setting x1 to 0 will yield x2

= -12, which is not on the graph. Thus, to get a second point

on this line, set x1 to any number larger than 3 and solve for

x2: when x1 = 5, then x2 = 8. Connect (3,0) and (5,8). The

“>“ side is to the right.

45

Example 2: Graphical Solution

• Graph the Constraints (continued)

– Constraint 3

• When x1 = 0, then x2 = 4

• When x2 = 0, then x1 = 4.

• Connect (4,0) and (0,4). The “>” side is above this line.

46

Example 2: Graphical Solution

Constraints Graphed

x2

6

Feasible Region

5

4×1 – x2 > 12

4

x1 + x2 > 4

3

2×1 + 5×2 > 10

2

1

x1

1

2

3

4

5

6

47

Example 2: Graphical Solution

• Graph the Objective Function

– Set the objective function equal to an arbitrary constant

(say 20) and graph it. For 5×1 + 2×2 = 20, when x1 = 0,

then x2 = 10; when x2= 0, then x1 = 4. Connect (4,0)

and (0,10).

• Move the Objective Function Line Toward

Optimality

–

Move it in the direction which lowers its value (down),

since we are minimizing, until it touches the last point of

the feasible region, determined by the last two

constraints.

48

Example 2: Graphical Solution

Objective Function Graphed

x2

Min 5×1 + 2×2

6

5

4×1 – x2 > 12

4

x1 + x2 > 4

3

2×1 + 5×2 > 10

2

1

1

2

3

4

5

6

x1

49

Example 2: Graphical Solution

Solve for the Extreme Point at the Intersection of the

Two Binding Constraints

4×1 – x2 = 12

x1+ x2 = 4

Adding these two equations gives:

5×1 = 16 or

x1 = 3.2

Substituting this into x1 + x2 = 4 gives: x2 = 0.8

Solve for the Optimal Value of the Objective

Function

5×1 + 2×2 = 5(3.2) + 2(0.8) = 17.6

50

Example 2: Graphical Solution

Optimal Solution

x2

6

4×1 – x2 > 12

5

x1 + x2 > 4

4

Optimal Solution:

x1 = 3.2, x2 = 0.8,

3

5×1 + 2×2 = 17.6

2

2×1 + 5×2 > 10

1

1

2

3

4

5

6

x1

51

Summary: Graphical Solution for Minimization

• Prepare a graph of the feasible solutions for each of the

constraints.

• Determine the feasible region that satisfies all the

constraints simultaneously.

• Draw an objective function line.

• Move parallel objective function lines toward smaller

objective function values without entirely leaving the

feasible region.

• Any feasible solution on the objective function line with the

smallest value is an optimal solution.

52

Surplus Variables

Example 2 in Standard Form

Min

5×1 + 2×2 + 0s1 + 0s2 + 0s3

s.t.

2×1 + 5×2 – s1 = 10

4×1 – x2 – s2 = 12

x1 + x2 – s3 = 4

s1 , s2 , and s3

> 0

are surplus

variables

x1, x2, s1, s2, s3

53

Example 2: Spreadsheet Solution

Partial Spreadsheet Showing Solution

A

B

C

Decision Variables

X1

X2

3.20

0.800

9

10

11 Dec.Var.Values

12

13

Minimized Objective Function

14

15

Constraints

Amount Used

16

#1

10.4

17

#2

12

18

#3

4

D

17.600

>=

>=

>=

Amount Avail.

10

12

4

54

Example 2: Spreadsheet Solution

Interpretation of Computer Output

We see from the previous slide that:

Objective Function Value = 17.6

Decision Variable #1 (x1) = 3.2

Decision Variable #2 (x2) = 0.8

Surplus in Constraint #1 = 10.4 – 10 = 0.4

Surplus in Constraint #2 = 12.0 – 12 = 0.0

Surplus in Constraint #3 = 4.0 – 4 = 0.0

55

Feasible Region

• The feasible region for a two-variable LP problem can be

nonexistent, a single point, a line, a polygon, or an

unbounded area.

• Any linear program falls into one of four categories:

– Is infeasible

– Has a unique optimal solution

– Has alternative optimal solutions

– Has an objective function that can be increased without bound

• A feasible region may be unbounded and yet there may be

optimal solutions. This is common in minimization

problems and is possible in maximization problems.

56

Special Cases

Alternative Optimal Solutions

In the graphical method, if the objective function line is

parallel to a boundary constraint in the direction of

optimization, there are alternate optimal solutions, with all

points on this line segment being optimal.

57

Example: Alternative Optimal Solutions

Consider the following LP problem.

Max 4×1 + 6×2

s.t.

x1 < 6
2x1 + 3x2 < 18
x1 + x2 < 7
x1 > 0 and x2 > 0

58

Example: Alternative Optimal Solutions

Boundary constraint 2×1 + 3×2 < 18 and objective
function Max 4x1 + 6x2 are parallel. All points on the
line segment A – B are optimal solutions.
7
6
5
x2
x1 + x2 < 7
A
B
4
x1 < 6
2x1 + 3x2 < 18
3
2
1
1
2
3
4
5
6
7
x1
8
9
10
59
Special Cases
• Infeasibility
– No solution to the LP problem satisfies all the
constraints, including the non-negativity conditions.
– Graphically, this means a feasible region does not exist.
– Causes include:
• A formulation error has been made.
• Management’s expectations are too high.
• Too many restrictions have been placed on the problem (i.e.,
the problem is over-constrained).
60
Example: Infeasible Problem
Consider the following LP problem:
Max
2x1 + 6x2
s.t.
4x1 + 3x2 < 12
2x1 + x2 > 8

x1, x2 >

0

61

Example: Infeasible Problem

There are no points that satisfy both constraints, so there

is no feasible region (and no feasible solution).

x2

10

2×1 + x2 > 8

8

6

4×1 + 3×2 < 12
4
2
2
4
6
8
10
x1
62
Special Cases
• Unbounded
– The solution to a maximization LP problem is unbounded if the
value of the solution may be made indefinitely large without
violating any of the constraints.
– For real problems, this is the result of improper formulation. (Quite
likely, a constraint has been inadvertently omitted.)
63
Example: Unbounded Solution
Consider the following LP problem.
Max
4x1 + 5x2
s.t.
x1 +
3x1 +
x2 > 5

x2 > 8

x1, x2 > 0

64

Example: Unbounded Solution

The feasible region is unbounded and the objective

function line can be moved outward from the origin

without bound, infinitely increasing the objective function.

x2

10

3×1 + x2 > 8

8

6

4

x1 + x2 > 5

2

2

4

6

8

10

x1

65

Practice Exercises: Operationalizing the LP

1)

2)

3)

4)

First, an instructor demo of Excel Solver

Second, download the Excel file entitled, “Practice

exercises: Operationalizing linear models”.

Revisit your answers to our earlier exercises (“Practice

exercises: Formulating linear models”) and

operationalize these models in Excel.

Work through the problems as a group and be prepared

to present your problem operationalization.

66

End of Chapter 7

67

In-class Practice Exercises: Formulating a Linear Programming Model

Problem #1

Embassy Motorcycles (EM) manufacturers two lightweight motorcycles designed for easy handling and safety. The K250 model

has a new engine and a low profile that make it easy to balance. The QX-500 model is slightly larger, uses a more traditional

engine, and is specifically designed to appeal to women riders. Embassy produces the engines for both models at its Jeddah

plant. Each K250 engine requires 6 hours of manufacturing time and each QX-500 engine requires 3 hours of manufacturing

time. The Jeddah plant has 2100 hours of engine manufacturing time available for the next production period. Embassy’s

motorcycle frame supplier can supply as many K250 frames as needed. However, the QX-500 frame is more complex and the

supplier can only provide up to 280 QX-500 frames for the next production period. Final assembly and testing requires 2 hours

for each K250 model and 2.5 hours for each QX-500 model. A maximum of 1000 hours of assembly and testing time are

available for the next production period. The company’s accounting department projects a profit contribution of $2400 for each

K250 produced and $1800 for each QX-500 produced.

Formulate a linear programming model that can be used to determine the number of units of each model that should be

produced in order to maximize the total contribution to profit.

Embassy Motorcycles (EM) Manufacturers Data:

Model

Manufacturing time

Production quantity

Assembly & testing time

Profit

Embassy Motorcycles

K250

QX-500

6 hours

3 hours

?

280

2 hours

2.5 hours

$2400

$1800

X = K250

Y = QX 500

How much to produce to Maximizing the profit

Max z = 2400 X + 1800 Y

Subjective too (constraints)

St = 6 X + 3 Y ≤ 2100 Manufactures

St = 2 X + 2.5 Y ≤ 1000 Testing

St = Y ≥ 280 Frames

Non negativity

X≥0

Y≥0

Amount

2100 hours

?

1000 hours

X&Y

Problem #2

Mohammed recently inherited a large sum of money; he wants to use a portion of this money to set up

a trust fund for his two children. The trust fund has two investment options: (1) a bond fund and (2) a

stock fund. The projected returns over the life of the investments are 6% for the bond fund and 10% for

the stock fund. Whatever portion of the inheritance Mohammed finally decides to commit to the trust

fund, he wants to invest at least 30% of that amount in the bond fund. In addition, he wants to select a

mix that will enable him to obtain a total return of at least 7.5%.

Formulate a linear programming model that can be used to determine the percentage that should be

allocated to each of the possible investment alternatives.

Problem #3

Blue Ocean Restaurant would like to determine the best way to allocate a monthly advertising budget of

SAR 4,000 between poster advertising and online advertising. Management decided that at least 25% of

the budget must be spent on each type of media, and that the amount of money spent on local poster

advertising must be at least twice the amount spent on online advertising. A marketing consultant

developed an index that measures audience exposure per dollar of advertising on a scale from 0 to 100,

with higher values implying greater audience exposure. If the value of the index for local poster

advertising is 50 and the value of the index for online advertising is 80, how should the restaurant

allocate its advertising budget in order to maximize the value of total audience exposure?

Formulate a linear programming model that can be used to determine how the restaurant should

allocate its advertising budget in order to maximize the value of total audience exposure.

## We've got everything to become your favourite writing service

### Money back guarantee

Your money is safe. Even if we fail to satisfy your expectations, you can always request a refund and get your money back.

### Confidentiality

We don’t share your private information with anyone. What happens on our website stays on our website.

### Our service is legit

We provide you with a sample paper on the topic you need, and this kind of academic assistance is perfectly legitimate.

### Get a plagiarism-free paper

We check every paper with our plagiarism-detection software, so you get a unique paper written for your particular purposes.

### We can help with urgent tasks

Need a paper tomorrow? We can write it even while you’re sleeping. Place an order now and get your paper in 8 hours.

### Pay a fair price

Our prices depend on urgency. If you want a cheap essay, place your order in advance. Our prices start from $11 per page.