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 Learning, Inc.
Lecture 2
Formulating linear programs
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.
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.
Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 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
Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.1 – Example 1- Product mix
Decision variables:
xi = the number of chairs of type i produced each xi is non-
negative
Objective function:
maximize profit z = 12x1 + 20x2 + 18x3 +40x4
Constraints:
at most 4,400 lbs of steel available: x1 + x2 +3x3 +9x4 £ 4, 400
at most 6, 000 lbs of wood available: 4x1 + 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, x2, x3, x4 ³ 0
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
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
Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Formulating linear program: row
(material balance) approach
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
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
Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 Learning, Inc.
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 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 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 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] 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 Learning, Inc.
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 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.
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 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 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
Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
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 Learning, Inc.
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 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 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 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] 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 Learning, Inc.
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 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 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 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 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 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 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 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 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 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 = −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 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
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 Learning, Inc.
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 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 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 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] 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 Learning, Inc.
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 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?
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
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 Milk Cheese Potato Fish Yogurt
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
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.
Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 6: Diet Problem-2
4 unit protein
1 unit fat Diet 1 unit of
15 unit carb. bread $2 of cost
90 unit cal. (Level: x1)
8 unit protein
5 unit fat Diet 1 unit of
11.7 unit carb. milk $3.5 of cost
120 unit cal. (Level: x2)
7 unit protein
9 unit fat Diet 1 unit of
0.4 unit carb. cheese $8 of cost
105 unit cal. (Level: x3)
…
Copyright (c) 2003 Brooks/Cole, a division of Thomson Learning, Inc.
2.2 – Example 6: Diet Problem-2
[Protein] 4x1+ 8x2 + 7x3 + 1.3x4 + 8x5 + 9.2x6 ≤ 10
[Fat] 1x1 + 5x2 + 9x3 + 0.1x4 + 7x5 + 1x6 ³ 8
[Carb] 15x1 + 11.7x2 + 0.4x3 + 22.6x4 + 0x5 + 17x6 ³ 10
[Cal] 90x1 + 120x2 + 106x3 + 97x4 + 130x5 + 180x6 ³ 300
[Cost] 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 Learning, Inc.
2.2 – Example 6: Diet Problem-2
Resulting linear program:
(Objective function):
[Cost] Min z = 2x1 + 3.5x2 + 8x3 + 1.5x4 + 11x5 + 1x6
Subject to (constraints):
[Protein] 4x1+ 8x2 + 7x3 + 1.3x4 + 8x5 + 9.2x6 ≤ 10
[Fat] 1x1 + 5x2 + 9x3 + 0.1x4 + 7x5 + 1x6 ³ 8
[Carb] 15x1 + 11.7x2 + 0.4x3 + 22.6x4 + 0x5 + 17x6 ³ 1
[Cal] 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 Learning, Inc.