CHE2034IU:

Simulation and Optimization

Spring Sem-II (2022-2023)

Lecturer: Khanh B. Vu
Department of Chemical Engineering
School of Chemical and Environmental
Engineering
International University-HCMC, VNU
Copyright (c) 2003 Brooks/Cole, a division of Thomson
 Lecture 2
Formulating linear
programs

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 - Introduction

• The process of building a mathematical model

is often considered to be as important as
solving.
• Models of the real world are not always easy
to formulate because of the richness, variety,
and ambiguity that exists in the real world or
because of our ambiguous understanding of it.
• Nevertheless, it is possible to state certain
principles that distinguish the separate steps
in the model-building process when the
system can be modeled as a linear program.

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 - Introduction

• The linear programming problem is to

determine the values of the variables of the
system that

(a) are nonnegative or satisfy certain bounds,

(b) satisfy a system of linear constraints, and
(c) minimize or maximize a linear form in the
variables called an objective.

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 - Introduction

• Linear program problem:

1. Decision variables: (x1,x2,…,xn)
2. Objective function: z = c1x1+c2x2+…+cnxn
3. Constraints: a11x1+a13x3 ≤ b1
4. Goal: Choose values of the decision variables
that maximize the objective function
subject to the constraints.

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix
Furniture company manufactures four models of chairs. Each
chair requires certain amount of raw materials (wood/steel)
to make. The company wants to decide on a production that
maximizes profit (assuming all produced chair are sold). The
required and available amounts of materials are as follows.

Chair 1 Chair 2 Chair 3 Chair 4 Total

available
Steel 1 1 3 9 4,400
(lbs)
Wood 4 9 7 2 6,000
(lbs)
Profit $12 $20 $18 $40 maximize

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix
Decision variables:
xi = the number of chairs of type i produced each x i is non-
negative
Objective function:
maximize profit z = 12x1 + 20x2 + 18x3 +40x4
Constraints:
at most 4,400 lbs of steel available: x 1 + x2 +3x3 +9x4  4, 400
at most 6, 000 lbs of wood available: 4x 1 + 9x2 + 7x3 + 2x4  6,
000
Resulting program:
Max 12x1 + 20x2 + 18x3 + 40x4 = z [Profit]
s.t. x1 + x2 + 3x3 + 9x4  4, 400 [Steel]
4x1 + 9x2 + 7x3 + 2x4  6, 000 [Wood]
x1 , x 2 , x 3 , x 4  0
Copyright (c) 2003 Brooks/Cole, a division of Thomson
 2.2 – Formulating linear program:
activity-based approach
Step 1: Define the Activity Set
Decompose the entire system under study into the activities
or processes. An activity has inputs, outputs, and activity
level
•inputs: materials consumed per unit of activity
•outputs: products produced per unit of activity
•activity level: a level at which we operate the activity

Step 2: Define the Item Set

Materials/labor/profit consumed or produced by an activity

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Formulating linear program:
activity-based approach
Step 3 Define the Input-Output Coefficients
The effect of an activity on items (i.e. the amounts of items
that are consumed/produced by an activity)

Step 4: Specify the Exogenous (External) Flows

The total amount of items available/supplied/required

Step 5: Set Up the Material Balance Equations

Express the flow of items in/out of activities and with respect
to
the external flow

Copyright (c) 2003 Brooks/Cole, a division of Thomson

2.2 – Formulating linear program:
row (material balance) approach

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix
Furniture company manufactures four models of chairs. Each
chair requires certain amount of raw materials (wood/steel)
to make. The company wants to decide on a production that
maximizes profit (assuming all produced chair are sold). The
required and available amounts of materials are as follows.

Chair 1 Chair 2 Chair 3 Chair 4 Total

available
Steel 1 1 3 9 4,400
(lbs)
Wood 4 9 7 2 6,000
(lbs)
Profit $12 $20 $18 $40 maximize

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix
Step 1: Define the Activity Set

The four manufacturing activities, each of which are

measured in desks produced:

1. Manufacturing Chair 1.
2. Manufacturing Chair 2.
3. Manufacturing Chair 3.
4. Manufacturing Chair 4

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix
Step 1: Define the Activity Set

1 lb of steel Making 1 unit

of Chair 1 $12 of profit
4 lbs of wood (Level: x1)
(inputs) (activity) (outputs)

1 lb of steel Making 1 unit

of Chair 2 $20 of profit
9 lbs of wood (Level: x2)

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix
Step 1: Define the Activity Set

3 lbs of steel Making 1 unit

of Chair 3 $18 of profit
7 lbs of wood (Level: x3)
(inputs) (activity) (outputs)

9 lbs of steel Making 1 unit

of Chair 4 $40 of profit
2 lbs of wood (Level: x4)

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix
Step 2: Define the Item Set
•Steel
•Wood
•Profit

Step 3 Define the Input-Output Coefficients

Consider activity Chair 1: consumes 1 lb of Steel, 4 lbs
of Wood, and produces $12 of Profit. Thus at level x1,
we consume 1x1 lbs of Steel, 4x1 lbs of Wood, and
produce 12x1 dollars of Profit.

Consider activity Chair 2 . ..Chair 4: similar manner

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix
Step 4: Specify the Exogenous (External) Flows
•Steel: 4,400 lbs of available (flowing in)
•Wood: 6,000 lbs of available (flowing in)
•Profit: maximize (flowing out)

Step 5: Material Balance Equations

•[Profit] 12x1 + 20x2 + 18x3 + 40x4 = z

•[Steel] x1 + x2 + 3x3 + 9x4 ≤ 4,400

•[Wood] 4x1 + 9x2 + 7x3 + 2x4 ≤ 6,000
•x1, x2, x3, x4  0

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 1- Product mix

Resulting program:

Max 12x1 + 20x2 + 18x3 + 40x4 = z [Profit]

Subject to:
x1 + x2 + 3x3 + 9x4  4, 400 [Steel]
4x1 + 9x2 + 7x3 + 2x4  6, 000 [Wood]
x1, x2, x3, x4  0

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 2- Product mix
A furniture company manufactures four models of desks.
Each desk is first constructed in the carpentry shop and is
next sent to the finishing shop, where it is varnished, waxed,
and polished. The number of man hours of labor required in
each shop is as shown in the display below (next slide).

Because of limitations in capacity of the plant, no more than

6,000 man hours can be expected in the carpentry shop and
4,000 in the finishing shop in the next six
months.

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 2- Product mix
Assuming that raw materials and supplies are available in
adequate supply and all desks produced can be sold, the
desk company wants to determine the optimal product mix,
that is, the quantities to make of each type product which
will maximize profit
Desk 1 Desk 2 Desk 3 Desk 4 Total
(hrs) (hrs) (hrs) (hrs) available
(hrs)
Carpentry 4 9 7 10 6,000
Shop
Finishing 1 1 3 40 4,000
Shop
Profit $12 $20 $18 $40 maximize

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 2- Product mix
Step 1: Define the Activity Set

The four manufacturing activities, each of which are

measured in desks produced:

1. Manufacturing Desk 1.
2. Manufacturing Desk 2.
3. Manufacturing Desk 3.
4. Manufacturing Desk 4

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 2- Product mix
Step 1: Define the Activity Set

4 hrs of CS Making 1 unit

of Desk 1 $12 of profit
1 hr of FS (Level: x1)
(inputs) (activity) (outputs)

9 hrs of CS Making 1 unit

of Desk 2 $20 of profit
1 hr of FS (Level: x2)

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 2- Product mix
Step 1: Define the Activity Set

7 hrs of CS Making 1 unit

of Desk 3 $18 of profit
3 hrs of FS (Level: x3)
(inputs) (activity) (outputs)

10 hrs of CS Making 1 unit

of Desk 4 $40 of profit
40 hrs of FS (Level: x4)

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 2- Product mix
Step 2: Define the Item Set
•Carpentry Shop
•Finishing Shop
•Profit

Step 3 Define the Input-Output Coefficients

Consider activity Desk 1: consumes 4 hrs of CS, 1 hr
of FS, and produces $12 of Profit. Thus at level x1, we
consume 4x1 hrs of CS, 1x1 hrs of FS, and produce
12x1 dollars of Profit.

Consider activity Desk 2 . ..Desk 4: similar manner

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 2- Product mix
Step 4: Specify the Exogenous (External) Flows
•Carpentry Shop: 6,000 hrs of available (flowing in)
•Finishing Shop: 4,000 hrs of available (flowing in)
•Profit: maximize (flowing out)

Step 5: Material Balance Equations

•[Profit] 12x1 +20x2 +18x3 +40x4 = z

•[CS] 4x1 + 9x2 + 7x3 + 10x4 ≤ 6,000

•[FS] 1x1 + 1x2 + 3x3 + 40x4 ≤ 4,000
•x1, x2, x3, x4  0

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.1 – Example 2- Product mix
Resulting program:
Max 12x1 + 20x2 + 18x3 + 40x4 = z [Profit]
Subject to:
4x1 + 9x2 + 7x3 + 10x4 ≤ 6,000 [CS]
1x1 + 1x2 + 3x3 + 40x4  4, 000 [FS]
x1, x2, x3, x4  0
Or
Min -12x1 - 20x2 - 18x3 - 40x4 = -z [Cost]
s.t. 4x1 + 9x2 + 7x3 + 10x4 ≤ 6,000 [CS]
1x1 + 1x2 + 3x3 + 40x4  4, 000 [FS]
x1, x2, x3, x4  0

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Formulating linear program:
row (material balance) approach
For many modelers the natural way to set up a linear
programming model is to state directly the material balance
relations in terms of the decision variables.
Step 1: Define the Decision Variables
•Variables that represent the quantity to produce, buy, etc.

•Decision variables are usually denoted by x1, x2, x3.

Step 2: Define the Item Set

•Materials/labor/profit consumed or produced by an activity.
•Are considered to be potential bottlenecks and choose a
unit for measuring each type of item.

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Formulating linear program:
row (material balance) approach
Step 3: Set Up Constraints and the Objective Function
•For each item, write down the constraints associated with
the bottleneck by noting how much of each item is used or
produced by a unit of each decision variable xj. This results
in a system of material balance inequalities (or material
balance equations).
•Write down the objective function which is formed by
multiplying each decision variable by its unit cost (or
negative unit profit) and summing.

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 3- Product mix (row
app.)
Assuming that raw materials and supplies are available in
adequate supply and all desks produced can be sold, the
desk company wants to determine the optimal product mix,
that is, the quantities to make of each type product which
will maximize profit
Desk 1 Desk 2 Desk 3 Desk 4 Total
(hrs) (hrs) (hrs) (hrs) available
(hrs)
Carpentry 4 9 7 10 6,000
Shop
Finishing 1 1 3 40 4,000
Shop
Profit $12 $20 $18 $40 maximize

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 3- Product mix (row
app.)
Step 1: Define the Decision Variables
•Decision variables are how many desks to manufacture of
each type. Let xj = the number of desks j to manufacture per
month, for j = 1, 2, 3, 4.
Step 2: Define the Item Set
•Capacity in Carpentry Shop (measured in man hours).
•Capacity in Finishing Shop (measured in man hours).
•Costs (measured in dollars).

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 3- Product mix (row
Step 3: app.)
Set Up Constraints and the Objective Function
•The cost item leads to the objective function to be minimized:
-z = −12x1 − 20x2 − 18x3 − 40x4
•Material balance inequality for the carpentry item:
4x1 + 9x2 + 7x3 + 10x4 ≤ 6000
•Material balance inequality for the finishing shop:
1x1 + 1x2 + 3x3 + 40x4 ≤ 4000
Thus, the linear programming problem is to determine the
numbers: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,
and minimum z satisfying
−12x1 − 20x2 − 18x3 − 40x4 = z
4x1 + 9x2 + 7x3 + 10x4 ≤ 6000
x1 + x2 + 3x3 + 40x4 ≤ 4000

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 4
A company produces three products A, B, C. For
manufacturing three raw materials P, Q and R are
used. Profit per unit A - $5, B - $3, C - $4
Resource requirements/unit
Raw materials P Q R
Products
A - 20 50
B 20 30 -
C 30 20 40

Maximum raw material availability: P - 80 units; Q -

100 units; R - 150 units.

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 4
Activity Set

0 unit P Making 1 unit

20 units Q of A $5 of profit
50 units R (Level: x1)
(inputs) (activity) (outputs)

20 units P Making 1 unit

30 units Q of B $3 of profit
0 units R (Level: x2)

30 units P Making 1 unit

20 units Q of C $4 of profit
40 units R (Level: x3)

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 4
Item set
•Material P
•Material Q
•Material R
•Profit

Input-Output Coefficients
Consider activity making 1 unit of A : consumes 0 unit of P, 20
units of Q, 50 units R, and produces $5 of Profit. Thus at level
x1, we consume 0x1 units of P, 20x1 units of Q, 50 units of R,
and produce 5x1 dollars of Profit. Similar for B, and C
activities.
[P] 0x1 + 20x2 + 30x3
[Q] 20x1 + 30x2 + 30x3
[R] 50x1 + 0x2 + 40x3
[Profit] 5x1 + 3x2 + 4x3
Copyright (c) 2003 Brooks/Cole, a division of Thomson
 2.2 – Example 4

Exogenous (External) Flows

•Materials P: 80 units of available (flowing in)
•Materials Q: 100 units of available (flowing in)
•Materials R: 150 units of available (flowing in)
•Profit maximize (flowing out)

Material Balance
[P] 0x1 + 20x2 + 30x3 ≤ 80
[Q] 20x1 + 30x2 + 30x3 ≤ 100
[R] 50x1 + 0x2 + 40x3 ≤ 150
[Profit] 5x1 + 3x2 + 4x3 = z

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 4

Resulting program:

maximize z = 5x1 + 3x2 + 4x3 [Profit]

Subject to:
[P] 0x1 + 20x2 + 30x3 ≤ 80
[Q] 20x1 + 30x2 + 30x3 ≤ 100
[R] 50x1 + 0x2 + 40x3 ≤ 150

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 5: Diet
A Problem-1
student is trying to decide on lowest cost diet that
provides sufficient amount of protein, with two choices:

– Steak: 2 units of protein/pound, $3/pound

– Peanut butter: 1 unit of protein/pound, $2/pound

In proper diet, need 4 units protein/day

Formulate a linear program for the diet problem?

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 5: Diet
Let x =Problem-1
# pounds peanut butter/day in the diet.
Let y = # pounds steak/day in the diet.

Goal: minimize 2x + 3y (total cost)

subject to constraints:
x + 2y ≥ 4
x ≥ 0, y ≥ 0

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 6: Diet
Problem-2
Consider the problem of diet optimization. There are six
different foods: bread, milk, cheese, potato, fish, and yogurt.
The cost and nutrition values per unit are displayed in Table

Bread Milk Chees Potat Fish Yogur

e o t
Cost 2.0 3.5 8.0 1.5 11.0 1.0
Prot., g 4.0 8.0 7.0 1.3 8.0 9.2
Fat, g 1.0 5.0 9.0 0.1 7.0 1.0
Carb., 15.0 11.7 0.4 22.6 0.0 17.0
g
Cal. 90 120 106 97 130 180

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 6: Diet
Problem-2
The objective is to find a minimum-cost diet that contains
at least 300 calories, not more than 10 grams of protein,
not less than 10 grams of carbohydrates, and not less
than 8 grams of fat. In addition, the diet should contain
at least 0.5 unit of fish and no more than 1 unit of milk.

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 6: Diet
Problem-2
4 unit protein
1 unit fat Diet 1 unit of
bread $2 of cost
15 unit carb.
(Level: x1)
90 unit cal.
8 unit protein
5 unit fat Diet 1 unit of
milk $3.5 of cost
11.7 unit carb.
(Level: x2)
120 unit cal.
7 unit protein
9 unit fat Diet 1 unit of
cheese $8 of cost
0.4 unit carb.
(Level: x3)
105 unit cal.
…

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 6: Diet
Problem-2
ein] 4x1+ 8x2 + 7x3 + 1.3x4 + 8x5 + 9.2x6 ≤ 10
1x1 + 5x2 + 9x3 + 0.1x4 + 7x5 + 1x6  8
] 15x1 + 11.7x2 + 0.4x3 + 22.6x4 + 0x5 + 17x6  1
90x1 + 120x2 + 106x3 + 97x4 + 130x5 + 180x6  300
] Min z = 2x1 + 3.5x2 + 8x3 + 1.5x4 + 11x5 + 1x6

x1  0, 0 ≤ x2 ≤ 1, x3  0, x4  0, x5  0.5, x6  0

Copyright (c) 2003 Brooks/Cole, a division of Thomson

 2.2 – Example 6: Diet
Problem-2
lting linear program:

ctive function):
] Min z = 2x1 + 3.5x2 + 8x3 + 1.5x4 + 11x5 + 1x6

ect to (constraints):

ein] 4x1+ 8x2 + 7x3 + 1.3x4 + 8x5 + 9.2x6 ≤ 10

1x1 + 5x2 + 9x3 + 0.1x4 + 7x5 + 1x6  8
b] 15x1 + 11.7x2 + 0.4x3 + 22.6x4 + 0x5 + 17x6 
90x1 + 120x2 + 106x3 + 97x4 + 130x5 + 180x6  300
x1  0, 0 ≤ x2 ≤ 1, x3  0, x4  0, x5  0.5, x6  0
…

Copyright (c) 2003 Brooks/Cole, a division of Thomson