Module 2: Linear Programming: Formulation and Graphic

Solution
2.1 - A Simple Maximization Problem
2.2 - Graphical Solution Procedure
2.3 - Extreme Points and the Optimal Solution
2.4 - Computer Solution of the Par, Inc., Problem
2.5 - A Simple Minimization Problem
2.6 - Special Cases
2.7 - General Linear Programming Notation

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
1
 Linear Programming (2 of 2)

• The maximization or minimization of some quantity

is the objective in all linear programming problems.
• All LP problems have constraints that limit the
degree to which the objective can be pursued.
• 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.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
2
 Guidelines for Model Formulation

Problem formulation or modeling is the process of

translating a verbal statement of a problem into a
mathematical statement.

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

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
3
 Standard Form

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
4
 A Typical LPP

Maximize Z = 50x1 + 75x2 + 60x3

Subject to
5x1 + 8x2 + 7x3 ≤ 480
4x1 + 2x2 + 3x3 ≤ 240
x1 – 2x2 + x3 ≥ 20
x1 , x2 , x3 ≥ 0

Constraints

Objective
Non-negativity condition Function

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
5
 Graphic Solution: Max Problem

Maximise Z = 40x1 + 35x2

Subject to 2x1 + 3x2 ≤ 60
4x1 + 3x2 ≤ 96
x1, x2 ≥ 0
Point x1 x2 Z
O 0 0 0
A 0 20 700
B 18 8 1000
C 24 0 960

Optimal
Solution
(unique)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Graphic Solution: Min Problem

Minimize Z = 40x1 + 24x2

Subject to 20x1 + 50x2 ≥ 4800
80x1 + 50x2 ≥ 7200
Point x1 x2 Z
and x1 x2 ≥ 0
P 0 144 3456
Q 40 20 3520
R 240 8 9600

Optimal
Solution
(unique)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Formulating a LP Model

 A product mix problem

• Decide how much to make of two or more products
• Objective is to maximize profit
• Limited resources
 Flair Furniture
• Best combination of tables and chairs
 Decision Variables
Two variables in the Flair problem
• Number of tables (T, Tables or X1)
• Number of chairs (C, Chairs or X2)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Objective Function

 For Flair Furniture

Profit = ($7 profit per table)

x (number of tables produced)
+ ($5 profit per chairs)
x (numbers of chairs produced)
 Using decision variables T and C
Maximize $7T + $5C

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Constraints

 Flair has four constraints

• Carpentry time
• Painting time
• Number of chairs to make
• Number of tables to make
 For carpentry time :
(3 hours per table) x (number of tables produced)
+ (4 hours per chair) x (number of chairs produced)
There are 2,400 hours of time available
3T + 4C ≤ 2,400

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Constraints

 All four constraints

Carpentry time 3T + 4C ≤ 2,400
Painting time 2T + 1C ≤ 1,000
Chairs sold C ≤ 450
Tables sold T ≥ 100
 Decision variables must be ≥ 0, so T ≥ 0, and C ≥ 0
 Decision variables may have to be integers

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Graphical Solution

 Complete model

Maximize profit = $7T + $5C

Subject to

3T + 4C ≤ 2,400 (carpentry time)

2T + 1C ≤ 1,000 (painting time)
C ≤ 450 (maximum chairs allowed)
T ≥ 100 (maximum tables allowed)
T, C ≥ 0 (nonnegativity)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Graphical Representation

Painting Constraint
1,000 –
Number of Chairs (C)

–
800 – Maximum Tables Required Constraint
–
600 – Maximum Chairs Allowed Constraint
–
400 –
– Carpentry Constraint
200 –
Feasible
–
Region
0– | | | | | | | | | | | |
0 200 400 600 800 1,000

Number of Tables(T)
© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Calculating a Solution

 Optimal point 4 is the intersection of two constraints,

carpentry and painting
 Solving simultaneously

6T + 8C = 4,800
– (6T + 3C = 3,000)
5C = 1,800
implies C = 360
and T = 320

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Using All Corner Points

Point 1 (T = 100, C = 0)
Profit = $7 x 100 + $5 x 0 = $700
Point 2 (T = 100, C = 450)
Profit = $7 x 100 + $5 x 450 = $2,950
Point 3 (T = 200, C = 450)
Profit = $7 x 200 + $5 x 450 = $3,650
Point 4 (T = 320, C = 360)
Profit = $7 x 320 + $5 x 360 = $4,040
Point 5 (T = 500, C = 0)
Profit = $7 x 500 + $5 x 0 = $3,500

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 A Simple Maximization Problem (1 of 4)

Par, Inc., is a small manufacturer of golf equipment and

supplies whose management has decided to move into the
market for medium- and high-priced golf bags. Par, Inc.’s
distributor has agreed to buy all the golf bags Par, Inc.,
produces over the next three months.
Each golf bag produced will require the following operations:
1. Cutting and dyeing the material
2. Sewing
3. Finishing (inserting umbrella holder, club separators,
etc.)
4. Inspection and packaging

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
16
 A Simple Maximization Problem (2 of 4)

This production information is summarized in this table:

Production Time (hours)

Department Standard Bag Deluxe Bag
Cutting and Dyeing 7/10 1
Sewing 1/2 5/6
Finishing 1 2/3
Inspection and Packaging 1/10 1/4

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
17
 A Simple Maximization Problem (3 of 4)

• Par, Inc.’s production is constrained by a limited number

of hours available in each department. The director of
manufacturing estimates that 630 hours for cutting and
dyeing, 600 hours for sewing, 708 hours for finishing, and
135 hours for inspection and packaging will be available
for the production of golf bags during the next three
months.
• The accounting department analyzed the production data
and arrived at prices for both bags that will result in a
profit contribution of $10 for every standard bag and $9 for
every deluxe bag produced.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
18
 A Simple Maximization Problem (4 of 4)

The complete model for the Par, Inc., problem is as follows:

Production Time (hours)
Department Standard Bag Deluxe Bag
Cutting and Dyeing 7/10 1
Sewing 1/2 5/6
Finishing 1 2/3
Inspection and Packaging 1/10 1/4

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
19
 Graphical Solution Procedure (1 of 5)

Earlier, we saw that the inequality representing the cutting

and dyeing constraint is:

7
S + 1D  630
10

To show all solution

points that satisfy this
relationship, we start by
graphing the solution
points satisfying the
constraint as an equality.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
20
 Graphical Solution Procedure (2 of 5)

We continue by identifying the solution points satisfying

each of the other three constraints.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
21
 Graphical Solution Procedure (3 of 5)

The graph shown identifies the feasible region:

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
22
 Graphical Solution Procedure (4 of 5)

The optimal solution point is at the intersection of the

cutting and dyeing and the finishing constraint lines.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
23
 Graphical Solution Procedure (5 of 5)

The optimal values of the decision variables S and D must

satisfy dyeing and the finishing constraints simultaneously.
7
S + 1D = 630 Dyeing Constraint
10
2
1S + D = 708 Finishing Constraint
3
This system of equations can be solved using substitution.
The exact location of the optimal solution point is S = 540
and D = 252. The optimal production quantities for Par, Inc.,
are 540 standard bags and 252 deluxe bags, with a resulting
profit contribution of 10(540) + 9(252) = $7,668.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
24
 A Simple Minimization Problem (1 of 6)

M&D Chemicals produces two products that are sold as raw

materials to companies manufacturing bath soaps and laundry
detergents.
• M&D’s management specified that the combined production
for products A and B must total at least 350 gallons.
• A customer ordered 125 gallons of product A.
• Product A requires 2 hours of processing time per gallon.
• Product B requires 1 hour of processing time per gallon.
• 600 hours of processing time are available.
• M&D’s objective is to satisfy these requirements at a
minimum total production cost.
• Production costs are $2 per gallon for product A and $3 per
gallon for product B.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
25
 A Simple Minimization Problem (2 of 6)

After adding the nonnegativity constraints (A, B ≥ 0), we arrive

at the following linear program for the M&D Chemicals
problem:

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
26
 A Simple Minimization Problem (3 of 6)

Here is the feasible region for the M&D Chemicals problem:

Note that the objective

function 2A + 3B = 800
intersects the feasible
region at the extreme
point A = 250, B = 100.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
27
 Slack and Surplus Variables (1 of 2)

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

negative and all the constraints are 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.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
28
 Graphical Solution

 Complete model

Maximize profit = $7T + $5C

Subject to

3T + 4C ≤ 2,400 (carpentry time)

2T + 1C ≤ 1,000 (painting time)
C ≤ 450 (maximum chairs allowed)
T ≥ 100 (minimum tables allowed)
T, C ≥ 0 (nonnegativity)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Slack Variables

 Complete model

Maximize profit = $7T + $5C

Subject to

3T + 4C + 𝑆1 = 2,400 (carpentry time)

2T + 1C + 𝑆2 = 1,000 (painting time)
C + 𝑆3 = 450 (maximum chairs allowed)
T ≥ 100 (maximum tables allowed)
T, C ≥ 0 (nonnegativity)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Surplus Variables

 Complete model

Maximize profit = $7T + $5C

Subject to

3T + 4C + 𝑆1 = 2,400 (carpentry time)

2T + 1C + 𝑆2 = 1,000 (painting time)
C + 𝑆3 = 450 (maximum chairs allowed)
T - 𝑆4 = 100 (maximum tables allowed)
T, C ≥ 0 (nonnegativity)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Surplus & Slack Variables

 Complete model

Maximize profit = $7T + $5C

Subject to

3T + 4C + 𝑆1 = 2,400 (carpentry time)

2T + 1C + 𝑆2 = 1,000 (painting time)
C + 𝑆3 = 450 (maximum chairs allowed)
T - 𝑆4 = 100 (maximum tables allowed)
T, C, 𝑆1 , 𝑆2 , 𝑆3 , 𝑆4 ≥0 (nonnegativity)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Surplus & Slack Variables: Objective Function

 Complete model

Maximize profit = $7T + $5C + 0. 𝑆1 + 0. 𝑆2 + 0. 𝑆3 +0. 𝑆4

Subject to

3T + 4C + 𝑆1 = 2,400 (carpentry time)

2T + 1C + 𝑆2 = 1,000 (painting time)
C + 𝑆3 = 450 (maximum chairs allowed)
T - 𝑆4 = 100 (maximum tables allowed)
T, C, 𝑆1 , 𝑆2 , 𝑆3 , 𝑆4 ≥0 (nonnegativity)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
 Practice Question

RMC, Inc., is a small firm that produces a variety of chemical products. In a particular production process,
three raw materials are blended (mixed together) to produce two products: a fuel additive and a solvent base.
Each ton of fuel additive is a mixture of 2/5 ton of material 1 and 3/5 of material 3. A ton of solvent base is a
mixture of 1/2 ton of material 1, 1/5 ton of material 2, and 3/10 ton of material 3. After deducting relevant costs,
the profit contribution is $40 for every ton of fuel additive produced and $30 for every ton of solvent base
produced. RMC’s production is constrained by a limited availability of the three raw materials. For the current
production period, RMC has available the following quantities of each raw material:
Raw Material Amount Available for Production
Material 1 20 tons
Material 2 5 tons
Material 3 21 tons
Assuming that RMC is interested in maximizing the total profit contribution, answer the following.
a. What is the linear programming model for this problem?
b. Find the optimal solution using the graphical solution procedure. How many tons of each product
should be produced, and what is the projected total profit contribution?
c. Is there any unused material? If so, how much?
d. Are any of the constraints redundant? If so, which ones?

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
34
 Solution

a. Let F = number of tons of fuel additive

S = number of tons of solvent base
Max 40F + 30S
s.t.
2/5F + 1/2 S ≤ 200 Material 1
1/5 S ≤ 5 Material 2
3/5 F + 3/10 S ≤ 21 Material 3
F, S ≥ 0

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
35
 Solution

b.
c. Material 2: 4 tons are used, 1 ton is
unused.
d. No redundant constraints.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
36
 Practice Question

The complete model for the Par, Inc., problem is as follows:

Production Time (hours)
Department Standard Bag Deluxe Bag
Cutting and Dyeing 7/10 1
Sewing 1/2 5/6
Finishing 1 2/3
Inspection and Packaging 1/10 1/4

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
37
 Solution

Assuming that Par, Inc., encounters each of these situations

separately, what is the optimal solution and the total profit
contribution for each situation described?

a. The accounting department revises its estimate of the profit

contribution for the deluxe bag to $18 per bag.

Optimal Solution
(300,420)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
38
 Solution

Assuming that Par, Inc., encounters each of these situations

separately, what is the optimal solution and the total profit
contribution for each situation described?

a. The accounting department revises its estimate of the profit

contribution for the deluxe bag to $18 per bag.

Optimal Solution
(300,420)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
39
 Solution

Assuming that Par, Inc., encounters each of these situations

separately, what is the optimal solution and the total profit
contribution for each situation described?

b. New sewing equipment is available that would increase the

sewing operation capacity to 750 hours. (Assume that 10A + 9B is
the appropriate objective function.)
The sewing constraint is redundant. Such a change would not
change the optimal solution to the original problem.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
40
 Slack and Surplus Variables (2 of 2)

The complete solution tells management that the production of

540 standard bags and 252 deluxe bags will require all
available cutting and dyeing time (630 hours) and all available
finishing time (708 hours), while 600 - 480 = 120 hours of
sewing time and 135 - 117 = 18 hours of inspection and
packaging time will remain unused. The 120 hours of unused
sewing time and 18 hours of unused inspection and packaging
time are referred to as slack for the two departments.
Hours Required forS = 540 and
Constraint D = 252 Hours Available Unused Hours
Cutting and Dyeing 7/10(540) + 1(252) = 630 630 0
Sewing 1/2(540) + 5/6(252) = 480 600 120
Finishing 1(540) + 2/3(252) = 708 708 0
Inspection and Packaging 1/10(540) + 1/4(252) = 117 135 18

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
41
 Slack Variables (1 of 2)

Often slack variables, are added to the formulation of a linear

programming problem to represent the slack, or idle capacity.
Unused capacity makes no contribution to profit; thus, slack
variables have coefficients of zero in the objective function. After
the addition of four slack variables, denoted as 𝑆1 , 𝑆2 , 𝑆3 , and 𝑆4 ,
the mathematical model of the Par, Inc., problem becomes
Max 10S + 9D + 0𝑆1 + 0𝑆2 + 0𝑆3 + 0𝑆4

s.t.
7Τ
10 S + 1D + 1𝑆1 + + + = 630
1Τ
2 S + 5Τ
6 D + + 1𝑆2 + + = 600
1S + 2Τ
3 D + + + 1𝑆3 + = 708
1Τ
10 S + 1Τ
4 D + + + + 1𝑆4 = 135
S, D, 𝑆1 , 𝑆2 , 𝑆3 , 𝑆4 ≥ 0

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
42
 Slack Variables (2 of 2)

Referring to the standard form of the Par, Inc., problem, we

see that at the optimal solution (S = 540 and D = 252), the
values for the slack variables are
Constraint Value of Slack Variable
Cutting and Dyeing 𝑆1 = 0
Sewing 𝑆2 = 120
Finishing 𝑆3 = 0
Inspection and Packaging 𝑆4 = 18

On the other hand, the sewing and the inspection and

packaging constraints are not binding the feasible region at
the optimal solution, which means we can expect some
unused time or slack for these two operations.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
43
 Extreme Points and the Optimal Solution (1 of 2)

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

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
44
 Extreme Points and the Optimal Solution (2 of 2)

Here are the 5 extreme points of the feasible region for

the Par, Inc., Problem:

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
45
 A Simple Minimization Problem (4 of 6)

The optimal solution to the M&D Chemicals problem shows

that the desired total production of A + B = 350 gallons is
achieved by using all processing time: 2A + 1B = 2(250) +
1(100) = 600 hours.
Note that the constraint requiring that product A demand be
met has been satisfied with A = 250 gallons. In fact, the
production of product A exceeds its minimum level by 250 –
125 = 125 gallons.
This excess production for product A is referred to as
surplus.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
46
 A Simple Minimization Problem (5 of 6)

Including two surplus variables, S1 and S2, for the ≥

constraints and one slack variable, S3, for the ≤
constraint, the linear programming model of the M&D
Chemicals problem becomes

All the constraints are now equalities.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
47
 A Simple Minimization Problem (6 of 6)

At the optimal solution of A = 250 and B = 100, the

values of the surplus and slack variables are as follows:

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
48
 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 in 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.
© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
49
 Special Cases (1 of 5)

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.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
50
 Special Cases (2 of 5)

Let’s return to the Par, Inc., problem. However, now assume

that the profit for the standard golf bag (S) has decreased to
$6.30. The revised objective function becomes 6.3S + 9D.

The objective function

values at these two
extreme points are
identical:
6.3S + 9D =
6.3(300)+9(420) = 5670
and
6.3S + 9D =
6.3(540)+9(252) = 5670

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
51
 Special Cases (3 of 5)

Furthermore, any point on the line connecting the two

optimal extreme points also provides an optimal solution.
For example, the solution point (S = 420, D = 336),
which is halfway between the two extreme points, also
provides the optimal objective function value of 6.3S +
9D = 6.3(420) + 9(336) = 5670.
A linear programming problem with alternative optimal
solutions is generally a good situation for the manager or
decision maker. It means that several combinations of
the decision variables are optimal and that the manager
can select the most desirable optimal solution.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
52
 Special Cases (4 of 5)

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).

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
53
 Special Cases (5 of 5)

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.)

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
54
 General Linear Programming Notation (1 of 3)

We selected decision-variable names of S and D in the

Par, Inc., problem and A and B in the M&D Chemicals
problem to make it easier to recall what these decision
variables represented in the problem.
Although this approach works well for linear programs
involving a small number of decision variables, it can
become difficult when dealing with problems involving a
large number of decision variables.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
55
 General Linear Programming Notation (2 of 3)

A more general notation that is often used for linear programs

uses the letter x with a subscript.
In the Par, Inc., problem, we could have defined the decision
variables:
x
1 = number of standard bags

x 2 = number of deluxe bags

In the M&D Chemicals problem, the same variable names

would be used, but their definitions would change:
x 1 = number of gallons of product A
x 2 = number of gallons of product B

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
56
 General Linear Programming Notation (3 of 3)

A disadvantage of using general notation for decision

variables is that we are no longer able to easily identify
what the decision variables actually represent in the
mathematical model.
The advantage of general notation is that formulating a
mathematical model for a problem that involves a large
number of decision variables is much easier.

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
57
 End of Module 2

Keep optimizing, keep practicing,

and don't forget to smile!
- Dr. Rashi R. Sharma

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
58