Module 02. pptsimulation anh optimization

l

1. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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

2. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
Lecture 2
Formulating linear programs

3. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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.

4. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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.

5. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 - Introduction
•Linear program problem:
1.Decision variables: (x
1,x
2,…,x
n)
2.Objective function: z = c
1
x
1
+c
2
x
2
+…+c
n
x
n
3.Constraints: a
11
x
1
+a
13
x
3
≤ b
1
4.Goal: Choose values of the decision variables
that maximize the objective function
subject to the constraints.

6. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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

7. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 – Example 1- Product mix
Decision variables:
x
i
= the number of chairs of type i produced each x
i
is non-negative
Objective function:
maximize profit z = 12x
1 + 20x
2 + 18x
3 +40x
4
Constraints:
at most 4,400 lbs of steel available: x
1 + x
2 +3x
3 +9x
4  4, 400
at most 6, 000 lbs of wood available: 4x
1 + 9x
2 + 7x
3 + 2x
4  6, 000
Resulting program:
Max 12x
1 + 20x
2 + 18x
3 + 40x
4 = z [Profit]
s.t. x
1 + x
2 + 3x
3 + 9x
4  4, 400 [Steel]
4x
1 + 9x
2 + 7x
3 + 2x
4  6, 000 [Wood]
x
1, x
2, x
3, x
4  0

8. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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

9. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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

10. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Formulating linear program: row
(material balance) approach

11. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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

12. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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

13. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 – Example 1- Product mix
Step 1: Define the Activity Set
Making 1 unit
of Chair 1
(Level: x
1)
1 lb of steel
4 lbs of wood
$12 of profit
(inputs) (activity) (outputs)
Making 1 unit
of Chair 2
(Level: x
2)
1 lb of steel
9 lbs of wood
$20 of profit

14. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 – Example 1- Product mix
Step 1: Define the Activity Set
Making 1 unit
of Chair 3
(Level: x
3)
3 lbs of steel
7 lbs of wood
$18 of profit
(inputs) (activity) (outputs)
Making 1 unit
of Chair 4
(Level: x
4)
9 lbs of steel
2 lbs of wood
$40 of profit

15. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 x
1, we
consume 1x
1 lbs of Steel, 4x
1 lbs of Wood, and produce
12x
1
dollars of Profit.
Consider activity Chair 2 . ..Chair 4: similar manner

16. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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] 12x
1
+ 20x
2
+ 18x
3
+ 40x
4
= z
•[Steel] x
1 + x
2 + 3x
3 + 9x
4 ≤ 4,400
•[Wood] 4x
1
+ 9x
2
+ 7x
3
+ 2x
4
≤ 6,000
•x
1, x
2, x
3, x
4  0

17. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 – Example 1- Product mix
Resulting program:
Max 12x
1
+ 20x
2
+ 18x
3
+ 40x
4
= z [Profit]
Subject to:
x
1
+ x
2
+ 3x
3
+ 9x
4
 4, 400 [Steel]
4x
1
+ 9x
2
+ 7x
3
+ 2x
4
 6, 000 [Wood]
x
1
, x
2
, x
3
, x
4
 0

18. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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.

19. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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
(hrs)
Desk 2
(hrs)
Desk 3
(hrs)
Desk 4
(hrs)
Total
available
(hrs)
Carpentry
Shop
4 9 7 10 6,000
Finishing
Shop
1 1 3 40 4,000
Profit $12 $20 $18 $40 maximize

20. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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

21. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 – Example 2- Product mix
Step 1: Define the Activity Set
Making 1 unit
of Desk 1
(Level: x
1)
4 hrs of CS
1 hr of FS
$12 of profit
(inputs) (activity) (outputs)
Making 1 unit
of Desk 2
(Level: x
2)
9 hrs of CS
1 hr of FS
$20 of profit

22. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 – Example 2- Product mix
Step 1: Define the Activity Set
Making 1 unit
of Desk 3
(Level: x
3)
7 hrs of CS
3 hrs of FS
$18 of profit
(inputs) (activity) (outputs)
Making 1 unit
of Desk 4
(Level: x
4)
10 hrs of CS
40 hrs of FS
$40 of profit

23. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 x
1, we consume 4x
1
hrs of CS, 1x
1 hrs of FS, and produce 12x
1 dollars of Profit.
Consider activity Desk 2 . ..Desk 4: similar manner

24. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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] 12x
1
+20x
2
+18x
3
+40x
4
= z
•[CS] 4x
1 + 9x
2 + 7x
3 + 10x
4 ≤ 6,000
•[FS] 1x
1
+ 1x
2
+ 3x
3
+ 40x
4
≤ 4,000
•x
1, x
2, x
3, x
4  0

25. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 – Example 2- Product mix
Resulting program:
Max 12x
1 + 20x
2 + 18x
3 + 40x
4 = z [Profit]
Subject to:
4x
1 + 9x
2 + 7x
3 + 10x
4 ≤ 6,000 [CS]
1x
1 + 1x
2 + 3x
3 + 40x
4  4, 000 [FS]
x
1, x
2, x
3, x
4  0
Or
Min -12x
1
- 20x
2
- 18x
3
- 40x
4
= -z [Cost]
s.t. 4x
1 + 9x
2 + 7x
3 + 10x
4 ≤ 6,000 [CS]
1x
1 + 1x
2 + 3x
3 + 40x
4  4, 000 [FS]
x
1, x
2, x
3, x
4  0

26. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 x
1, x
2, x
3.
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.

27. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 x
j. 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.

28. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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
(hrs)
Desk 2
(hrs)
Desk 3
(hrs)
Desk 4
(hrs)
Total
available
(hrs)
Carpentry
Shop
4 9 7 10 6,000
Finishing
Shop
1 1 3 40 4,000
Profit $12 $20 $18 $40 maximize

29. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 x
j = 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).

30. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 3- Product mix (row app.)
Step 3: Set Up Constraints and the Objective Function
•The cost item leads to the objective function to be minimized:
-z = 12x
−
1 20x
−
2 18x
−
3 40x
−
4
•Material balance inequality for the carpentry item:
4x
1 + 9x
2 + 7x
3 + 10x
4 ≤ 6000
•Material balance inequality for the finishing shop:
1x
1
+ 1x
2
+ 3x
3
+ 40x
4
≤ 4000
Thus, the linear programming problem is to determine the numbers:
x
1 ≥ 0, x
2 ≥ 0, x
3 ≥ 0, x
4 ≥ 0,
and minimum z satisfying
−12x
1 20x
−
2 18x
−
3 40x
−
4 = z
4x
1
+ 9x
2
+ 7x
3
+ 10x
4
≤ 6000
x
1 + x
2 + 3x
3 + 40x
4 ≤ 4000

31. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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
P Q R
A - 20 50
B 20 30 -
C 30 20 40
Resource requirements/unit
Raw materials
Products
Maximum raw material availability: P - 80 units; Q - 100
units; R - 150 units.

32. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 4
Activity Set
Making 1 unit
of A
(Level: x
1)
0 unit P
20 units Q $5 of profit
(inputs) (activity) (outputs)
Making 1 unit
of B
(Level: x
2)
20 units P
30 units Q $3 of profit
Making 1 unit
of C
(Level: x
3
)
30 units P
20 units Q
$4 of profit
50 units R
0 units R
40 units R

33. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 x
1
, we
consume 0x
1
units of P, 20x
1
units of Q, 50 units of R, and produce 5x
1

dollars of Profit. Similar for B, and C activities.
[P] 0x
1
+ 20x
2
+ 30x
3
[Q] 20x
1
+ 30x
2
+ 30x
3
[R] 50x
1
+ 0x
2
+ 40x
3
[Profit]5x
1
+ 3x
2
+ 4x
3

34. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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] 0x
1
+ 20x
2
+ 30x
3
≤ 80
[Q] 20x
1
+ 30x
2
+ 30x
3
≤ 100
[R] 50x
1
+ 0x
2
+ 40x
3
≤ 150
[Profit]5x
1
+ 3x
2
+ 4x
3
= z

35. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 4
Resulting program:
maximize z = 5x
1 + 3x
2 + 4x
3 [Profit]
Subject to:
[P] 0x
1
+ 20x
2
+ 30x
3
≤ 80
[Q] 20x
1
+ 30x
2
+ 30x
3
≤ 100
[R] 50x
1 + 0x
2 + 40x
3 ≤ 150

36. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 5: Diet Problem-1
A 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?

37. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 5: Diet Problem-1
Let x = # 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

38. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 MilkCheesePotatoFishYogurt
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., g 15.0 11.7 0.4 22.6 0.0 17.0
Cal. 90 120 106 97 130 180

39. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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.

40. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 6: Diet Problem-2
Diet 1 unit of
bread
(Level: x
1)
4 unit protein
1 unit fat
$2 of cost
15 unit carb.
90 unit cal.
Diet 1 unit of
milk
(Level: x
2)
8 unit protein
5 unit fat
$3.5 of cost
11.7 unit carb.
120 unit cal.
Diet 1 unit of
cheese
(Level: x
3
)
7 unit protein
9 unit fat
$8 of cost
0.4 unit carb.
105 unit cal.
…

41. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 6: Diet Problem-2
…
[Protein]4x
1
+ 8x
2
+ 7x
3
+ 1.3x
4
+ 8x
5
+ 9.2x
6
≤ 10
[Fat] 1x
1 + 5x
2 + 9x
3 + 0.1x
4 + 7x
5 + 1x
6  8
[Carb] 15x
1
+ 11.7x
2
+ 0.4x
3
+ 22.6x
4
+ 0x
5
+ 17x
6
 10
[Cal] 90x
1
+ 120x
2
+ 106x
3
+ 97x
4
+ 130x
5
+ 180x
6
 300
[Cost] Min z = 2x
1 + 3.5x
2 + 8x
3 + 1.5x
4 + 11x
5 + 1x
6
x
1  0, 0 ≤ x
2 ≤ 1, x
3  0, x
4  0, x
5  0.5, x
6  0

42. Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 6: Diet Problem-2
…
Resulting linear program:
(Objective function):
[Cost] Min z = 2x
1
+ 3.5x
2
+ 8x
3
+ 1.5x
4
+ 11x
5
+ 1x
6

Subject to (constraints):
[Protein]4x
1
+ 8x
2
+ 7x
3
+ 1.3x
4
+ 8x
5
+ 9.2x
6
≤ 10
[Fat] 1x
1
+ 5x
2
+ 9x
3
+ 0.1x
4
+ 7x
5
+ 1x
6
 8
[Carb] 15x
1 + 11.7x
2 + 0.4x
3 + 22.6x
4 + 0x
5 + 17x
6  10
[Cal] 90x
1 + 120x
2 + 106x
3 + 97x
4 + 130x
5 + 180x
6  300
x
1
 0, 0 ≤ x
2
≤ 1, x
3
 0, x
4
 0, x
5
 0.5, x
6
 0