Manufacturing processes
Lectures: Wednesday, 13:15 – 14:45, room 120/B3
Part 1
11.10 Decision making problems in manufacturing and
18.10 production - linear programming methods
25.10 (simplex, transportation algorithm)
Part 2
15.11 Classyfication of production and manufacturing
processes, basic manufacturing process:
casting, metal forming, cold and hot working
29.11 Plastic manufacturing/Injection molding
13.13 Powder metallurgy
10.01 Machinning processes
24.01 Exam
Auditorium classes:
Group 1: Wednesday, 13:15 – 14:45, room 120/B3 – 8.11, 22.11, 6.12, 20.12, 3.01, 17.01
Group 2: Monday, 15:00 – 16:30, room 11/B2 – starting from 16.10
Final grade: weighted average grade of auditorium (60%) and exam (40%)
Decision-making problems in manufacturing
There are variety of problems in manufacturing and production which involve to solve
the optimization problems:
The product-mix problem
A manufacturer has finite set of different resources such as raw material,
labor, and equipment which are combined to produce different products.
The quantity of each resource required to produce one unit of the product is
known. A profit contribution per unit is also known.
Find the product mix that maximizes profit in the presence of constrained
resources and product demand.
Diet problem
Selecting optimal blends of raw materials combination to minimize the
production costs.
Decision-making problem
The production scheduling problem (inventory problem)
A factory must produce a certain product over the n months, satisfying the
monthly demand for this product. There are different demands at each
month (lower or higher then production efficiency per month).
Thus, the product should be produced whether in regular time (lower
production cost) and stored in a magazine (higher storage cost), or in
overtime = higher production cost but lower storage cost.
The factory wants to minimize the total costs = production cost + storage
cost.
Transportation problem
There are m sources (e.g. factories) which supply the commodity to the n
destinations (e.g. warehouses). The unit transportation costs from each
origin to each destination is known. The objective is to find how much
should be shipped from each source to each destination so as to minimize
the total transportation cost and satisfy the demand at each destination.
Product-mix problem - Example
The two products P1 and P2 are manufactured from the two raw materials M1 and M2 which are
limited to 400 kg and 600 kg, respectively. The P1 requires 1 kg of M1 and 2 kg of M2 in
manufacturing process, while the profit per unit is 4 and 3 for P1 and P2, respectively.
How much of P1 and P2 should be manufactured to maximize the profit?
profit
M1 M2 decision variables:
per unit
x1 – the amount of P1,
P1 1 2 4 x2 – the amount of P2.
P2 1 1 3
Limit of
400 600
M1 and M2
max z 4 x1 3x2
s.t.
x1 x2 400
2 x1 x2 600
x1 , x2 0
Standard form of LPP
Mathematical model of LP maximization problem in the standard form:
max z c1 x1 c2 x2 cn xn - objective function
subject to
a11 x1 a12 x2 a1n xn b1
a 21 x1 a 22 x2 a 2 n xn b2
- constraints
a m1 x1 a m 2 x2 a mn xn bm
x j 0, j 1, 2, ...., n - sign restrictions (non-negativity requirements)
where:
xj (j = 1, 2, ..., n) - decision variables (e.g. amount of manufactured product j)
cj (j = 1, 2, ..., n) – e.g. profit per unit,
bi (i = 1, 2, …, m) – e.g. limitations of resources.
Standard form of LPP
Standard form of minimization problem:
min z c1 x1 c2 x2 cn xn - objective function
subject to
a11 x1 a12 x2 a1n xn b1
a 21 x1 a 22 x2 a 2 n xn b2
- constraints
a m1 x1 a m 2 x2 a mn xn bm
x j 0, j 1, 2, ...., n - sign restrictions (non-negativity requirements)
Standard form of LPP
Standard form of maximization Standard form of minimization
problem: problem:
c x
n
max z c x
j 1
j j
min z
j 1
j j
s.t. s.t.
n
a x
n
a x
j 1
ij j bi , i 1, 2, ..., m
j 1
ij j bi , i 1, 2, ..., m
x j 0, j 1, 2, ...., n x j 0, j 1, 2, ...., n
in the matrix form:
c T x max c T x min
Ax b Ax b
x0 x0
Cannonical form of LPP
A linear programming is an optimization technique by which the maximum or minimum value of
a function is determined under certain conditions and the technique requires only finite number of
steps, called algorithm.
standard form: canonical form:
n
c x c x
n
max z j j
max z j j
j 1 j 1
n
a x a x
n
ij j bi , i 1, 2, ..., m si ij j bi , i 1, 2, ..., m
j 1 j 1
x j 0, j 1, 2, ...., n i 1, 2, ..., m
si 0, x j 0 ,
j 1, 2, ...., n
Maximization LPP can be transformed from the standard form to the canonical form
through converting the inequality constraints (≤) into the equality constraints by adding
a slack variable si to the left-hand side of the constraint, and adding the sign restriction
si ≥ 0.
Cannonical form of LPP
max z c1 x1 c2 x2 cn xn
s1 a11 x1 a12 x2 a1n xn b1
s2 a 21 x1 a 22 x2 a 2 n xn b2
s m a m1 x1 a m 2 x2 a mn xn bm
s j , x j 0, i 1, 2, ...., m, j 1, 2, ...., n
for all non-negative variables: augmented matrix:
s1 a11 x1 a12 x2 a1n xn b1 1 0 0 a11 a1n b1
s2 a 21 x1 a 22 x 2 a 2 n xn b2 0 1 0 a a2 n b2
21
s m a m1 x1 a m 2 x2 a mn xn bm
0 0 0 1 am1 amn bm
z c1 x1 c 2 x2 cn x n b0 0 0 0 0 c1 cn b0
Cannonical form of LPP
augmented matrix:
1 0 0 a11 a1n b1
0 1 0 a a2 n b2
21
0 0 0 1 am1 amn bm
0 0 0 0 c1 cn b0
the initial simplex tableau expresses the initial feasible basic sollution (FBS):
x1 = x2 = … = xn = 0, z = b0 = 0.
BV s1 s2 … sm x1 … xn bi
s1 1 0 … 0 a11 … a1n b1
s2 0 1 … 0 a21 … a2n b2
… … … … … … … … …
sm 0 0 … 1 an1 … amn bm
z 0 0 … 0 - c1 … - cn b0
BV = {s1, s2, …, sm} are the basic variables
NBV = {x1, x2, …, xn} are the non-basic variables
Simplex method: Example 1
The two products P1 and P2 are manufactured from the two raw materials M1 and M2 which are
limited to 400 kg and 600 kg, respectively. The P1 requires 1 kg of M1 and 2 kg of M2 in
manufacturing process, while the profit per unit is 4 and 3 for P1 and P2, respectively.
How much of P1 and P2 should be manufactured to maximize the profit?
profit
M1 M2 decision variables:
per unit
x1 – the amount of P1,
P1 1 2 4 x2 – the amount of P2.
P2 1 1 3
Limit of
400 600
M1 and M2
standard LPP model: canonical form:
max z 4 x1 3x2 max z 4 x1 3x2
s.t.
x1 x2 400 s1 x1 x2 400
2 x1 x2 600 s2 2 x1 x2 600
x1 , x2 0 x1 , x2 , s1 , s2 0
Simplex method: Example 1
The first feasible basic sollution (FBS) is x1 = x2 = 0, s1 = 400, s2 = 600, z = 0
basic variables: BV = {s1, s2}
non-basic variables: NBV = {x1, x2}
Find the better FBS:
1. The greatest increase in objective function z can
s1 x1 x2 400 (1)
be obtained by increasing value of the x1 than x2.
s2 2 x1 x2 600 (2)
max z 4 x1 3x2
x1 , x2 , s1 , s2 0
2. How much we can increase x1?
z 4 x1 3x2 0 (3)
From Eq. (1) and (2), for x2 = 0 and non-negative
conditions we can determine the upper bound of x1 .
The starting simplex tableau
From Eq. (1):
cB BV s1 s2 x1 x2 bi s1 400 x1 ; s1 0 x1 400
0 s1 1 0 1 1 400 From Eq. (2):
0 s2 0 1 2 1 600 s2 600 2 x1 ; s 2 0 x1 300
z 0 0 -4 -3 0
The upper bound x1 ≤ 300 associates with (2).
Simplex method: Example 1
s1 x1 x2 400 (1)
s2 2 x1 x2 600 (2) x1 300
x1 , x2 , s1 , s2 0
z 4 x1 3x2 0 (3)
3. Determine x1 from Eq. (2): 4. Substitute x1 into Eqs. (1) and (3) by (2a):
1 1
1 1 s1 s 2 x2 100 (1a)
x1 s2 x2 300 (2a) 2 2
2 2
z 2s2 x2 1200 (3a)
The new FBS: s1 = 100, x1 = 300, s2 = x2 = 0, z = 1200
1 1 cBV BV s1 s2 x1 x2 bi
s1 s 2 x2 100 (1a)
2 2
0 s1 1 -1/2 0 1/2 100
1 1
s 2 x1 x2 300 (2a)
2 2 4 x1 0 1/2 1 1/2 300
x1 , x2 , s1 , s 2 0
z 0 2 0 -1 1200
z 2s2 x2 1200 (3a)
Simplex method: Example 1
Simplex tableau - procedure
cBV BV s1 s2 x1 x2 bi 1. Find the highest negative optimization
coefficient to dermine the column of the entering
0 s1 1 0 1 1 400 variable (pivot column - PC).
0 s2 0 1 2 1 600
x1 – variable entering the basis
z 0 0 -4 -3 0
PC [a1 p , a2 p , ..., amp , c p ]T
2. Select the row of the leaving variable from the basis (pivot row), by finding a minimum of
b
min i - ties can be broken arbitrarily
aip 0 a
ip
cBV BV s1 s2 x1 x2 bi
0 s1 1 0 1 1 400 x1 400 / 1 400
0 s2 0 1 2 1 600 x1 600 / 2 300 s2 – variable leaving the basis
z 0 0 -4 -3 0
x1 will be the new basic variable of the next FBS
s2 will be the non-basic variable of the next FBS
Simplex method: Example 1
3. Convert the pivot row (PR) by dividing this row by its pivot element
cBV BV s1 s2 x1 x2 bi cBV BV s1 s2 x1 x2 bi
0 s1 1 0 1 1 400 PR 0 s1 1 0 1 1 400
PR
2
0 s2 0 1 2 1 600 4 x1 0 1/2 1 1/2 300
z 0 0 -4 -3 0 z 0 0 -4 -3 0
Simplex method: Example 1
4. Apply the Gauss-Jordan method to reduce the simplex tableau
Row = Row – its pivot element * PR
cBV BV s1 s2 x1 x2 bi cBV BV s1 s2 x1 x2 bi
R1=R1–1*PR
0 s1 1 0 1 1 400 0 s1 1 -1/2 0 1/2 100
4 x1 0 1/2 1 1/2 300 4 x1 0 1/2 1 1/2 300
z 0 0 -4 -3 0 z 0 0 -4 -3 0
cBV BV s1 s2 x1 x2 bi cBV BV s1 s2 x1 x2 bi
0 s1 1 -1/2 0 1/2 100 0 s1 1 -1/2 0 1/2 100
4 x1 0 1/2 1 1/2 300 4 x1 0 1/2 1 1/2 300
R3 = R3 + 4*PR
z 0 0 -4 -3 0 z 0 2 0 -1 1200
Simplex method: Example 1
the current simplex tableau
cBV BV s1 s2 x1 x2 bi
BV = {s1 , x1}
NBV ={ s2, x2}
0 s1 1 -1/2 0 1/2 100
4 x1 0 1/2 1 1/2 300
z 0 2 0 -1 1200 z 1200 2s2 x2
There is still posiible to obtain the better solution through increassing x2.
Simplex method: Example 1
1. Find the entering variable
cBV BV s1 s2 x1 x2 bi
0 s1 1 -1/2 0 1/2 100
4 x1 0 1/2 1 1/2 300
z 0 2 0 -1 1200
x2 – the entering variable
2. Find the leaving variable
PC
cBV BV s1 s2 x1 x2 bi
100
PR 0 s1 1 -1/2 0 1/2 100 x2 200
0.5
300
4 x1 0 1/2 1 1/2 300 x2 600
0.5
z 0 2 0 -1 1200
s1 – the leaving variable
Apply the Gauss-Jordan method to reduce the simplex tableau
cBV BV s1 s2 x1 x2 bi cBV BV s1 s2 x1 x2 bi
PR
PR
0 s1 1 -1/2 0 1/2 100 0.5 3 x2 2 -1 0 1 200
4 x1 0 1/2 1 1/2 300 4 x1 0 1/2 1 1/2 300
z 0 2 0 -1 1200 z 0 2 0 -1 1200
cBV BV s1 s2 x1 x2 bi cBV BV s1 s2 x1 x2 bi
3 x2 2 -1 0 1 200 3 x2 2 -1 0 1 200
R2=R2–0.5*PR 4 x1 -1 1 1 0 200
4 x1 0 1/2 1 1/2 300
z 0 2 0 -1 1200 z 0 2 0 -1 1200
cBV BV s1 s2 x1 x2 bi cBV BV s1 s2 x1 x2 bi
3 x2 2 -1 0 1 200 3 x2 2 -1 0 1 200
4 x1 -1 1 1 0 200 4 x1 -1 1 1 0 200
R3=R3+1*PR
z 0 2 0 -1 1200 z 2 1 0 0 1400
Simplex method: Example 1
The new FBS: x1 = 200, x2 = 200, s1 = s2 = 0, z = 1400
cBV BV s1 s2 x1 x2 bi
BV = {x1 , x2}
NBV ={ s1, s2}
3 x2 2 -1 0 1 200
4 x1 -1 1 1 0 200
z 2 1 0 0 1400 z 1400 2s1 s2
Optimization condition:
if all the optimization coefficients are non-negative
then the current basic solution is an optimal.
Simplex method: Procedure
Step 1: Present the LPP in the canonical form and construct the initial
simplex tableau.
Step 2: If all the optimization coefficients are non-negative then STOP
- the current basic solution is an optimal. Otherwise go to Step 3.
Step 3: Find the entering variable associated with the highest negative
optimization coefficient.
Step 4: Select the leaving variable associated with the least upper bound
of the entering variable
bi
min
aip 0 a
ip
Step 5. Reduce the rows of the simplex tableau (augmented matrix) using
the Gauss Jordan method, and go to Step 2.
Example 2
max z 2 x1 2 x2
s.t.
2 x1 x 2 10
x1 x 2 8
x1 4
x1 , x 2 0
Example 2
max z 2 x1 2 x2
s.t.
2 x1 x 2 10
x1 x 2 8
x1 4
x1 , x 2 0
Example 2
max z 2 x1 2 x2
s1 2 x1 x2 10
s.t.
canonical form: s2 x1 x2 8
2 x1 x 2 10
s3 x1 4
x1 x 2 8
s1 , s 2 , s 2 , x1 , x2 0
x1 4
z 2 x1 2 x2 0
x1 , x 2 0
The first simplex tableau
cBV BV s1 s2 s3 x1 x2 bi
0 s1 1 0 0 2 1 10
0 s2 0 1 0 1 1 8
0 s3 0 0 1 1 0 4
z 0 0 0 -2 -2 0
BV ={ s1, s2, s3}
NBV = {x1 , x2}
Example 2
Iteration 1
cBV BV s1 s2 s3 x1 x2 bi
0 s1 1 0 0 2 1 10 x1 10 / 2 5
0 s2 0 1 0 1 1 8 x1 8 / 1 8
0 s3 0 0 1 1 0 4 x1 4 / 1 4
z 0 0 0 -2 -2 0
PivotRow = PivotRow/1
R1 = R1 – 2*PivotRow
R2 = R2 - 1*PivotRow
R4 = R4 + 2*PivotRow
cBV BV s1 s2 s3 x1 x2 bi cBV BV s1 s2 s3 x1 x2 bi
0 s1 1 0 0 2 1 10 0 s1 1 0 -2 0 1 2
0 s2 0 1 0 1 1 8 0 s2 0 1 -1 0 1 4
2 x1 0 0 1 1 0 4 2 x1 0 0 1 1 0 4
z 0 0 0 -2 -2 0 z 0 0 2 0 -2 8
Example 2
cBV BV s1 s2 s3 x1 x2 bi
0 s1 1 0 -2 0 1 2
0 s2 0 1 -1 0 1 4
2 x1 0 0 1 1 0 4
z 0 0 2 0 -2 8
BFS: x1 = 4, x2 = 0 B
Example 2
Iteration 2
cBV BV s1 s2 s3 x1 x2 bi
0 s1 1 0 -2 0 1 2 x2 2 / 1 2 bi
min
0 s2 0 1 -1 0 1 4 x2 4 / 1 4 aip 0 a
ip
2 x1 0 0 1 1 0 4
z 0 0 2 0 -2 8
PivotRow = PivotRow/1
R2 = R2 – 1*PivotRow
R3 = R3 - 0*PivotRow
R4 = R4 + 2*PivotRow
cBV BV s1 s2 s3 x1 x2 bi cBV BV s1 s2 s3 x1 x2 bi
2 x2 1 0 -2 0 1 2 2 x2 1 0 -2 0 1 2
0 s2 0 1 -1 0 1 4 0 s2 -1 1 1 0 0 2
2 x1 0 0 1 1 0 4 2 x1 0 0 1 1 0 4
z 0 0 2 0 -2 8 z 2 0 -2 0 0 12
Example 2
cBV BV s1 s2 s3 x1 x2 bi
2 x2 1 0 -2 0 1 2
0 s2 -1 1 1 0 0 2
2 x1 0 0 1 1 0 4
z 2 0 -2 0 0 12
BFS: x1 = 4, x2 = 2 C
Example 2
Iteration 3
cBV BV s1 s2 s3 x1 x2 bi
2 x2 1 0 -2 0 1 2
s3 2 / 1 2 bi
0 s2 -1 1 1 0 0 2 min
aip 0 a
2 x1 0 0 1 1 0 4 s3 4 / 1 4 ip
z 2 0 -2 0 0 12
PivotRow = PivotRow/1
R1 = R1 + 2*PivotRow
R3 = R3 - 1*PivotRow
R4 = R4 + 2*PivotRow
cBV BV s1 s2 s3 x1 x2 bi cBV BV s1 s2 s3 x1 x2 bi
2 x2 1 0 -2 0 1 2 2 x2 -1 2 0 0 1 6
0 s3 -1 1 1 0 0 2 0 s3 -1 1 1 0 0 2
2 x1 0 0 1 1 0 4 2 x1 1 -1 0 1 0 2
z 2 0 -2 0 0 12 z 0 2 0 0 0 16
Example 2
cBV BV s1 s2 s3 x1 x2 bi
2 x2 -1 2 0 0 1 6
0 s3 -1 1 1 0 0 2
BFS: x1 = 2, x2 = 6 D
2 x1 1 -1 0 1 0 2
z 0 2 0 0 0 16
The basic solution is an optimal - all the
optimization coefficients are non-negative.
If there is a nonbasic variable which has an
optimization coefficient equal to zero in
the optimal simplex tableau then multiple
optima exists.
BV ={x1 , x2 , s3}
NBV = {s1, s2}
Example 3: minimization problem
min z 2 x1 2 x2
s.t.
2 x1 x 2 10
x1 x 2 8
x1 4
x1 , x 2 0
The first constraint is not active.
Dual problem
The basic procedure used to solve minimization problem is to convert it to a maximization
problem.
Primal problem (minimization) Dual problem (maximization)
n m
a x
j 1
ij j bi , i 1, 2, ..., m a y
i 1
ij j ci , j 1, 2, ..., n
x j 0, j 1, 2, ...., n yi 0, i 1, 2, ...., m
m
b y
n
min z c x
j 1
j j
max w
i 1
i i
where:
yj (j = 1, 2, ..., m) – dual variables
The value of the dual variable yi (shadow price or dual price) is interpreted as the
amount of change in the objective function if the constraint is changed by one unit.
Each constraint has a shadow price per unit of this constraint.
bi 1yi bi yi yi
In a business application, a shadow price is the maximum price that management is
willing to pay for an extra unit of a given limited resource.
Example 3: dual problem
Primal problem (minimization) Dual problem (maximization)
2 x1 x2 10
2 y1 y 2 y3 2
x1 x 2 8
y1 y 2 2
x1 4
y1 , y 2 , y3 0
x1 , x2 0
max w 10 y1 8 y 2 4 y3
min z 2 x1 2 x 2
The dual model is given by the transposition of the augmented matrix of the primal model:
T
2 1 10 2 1 1 2
1 1 8 1 1 0 2
1 0 4 10 8 4 0
2 2 0
Example 3: duality
2 y1 y2 y3 2 s1 2 y1 y 2 y3 2
y1 y2 2 canonical form s 2 y1 y 2 2
y1 , y2 , y3 0 s1 , s 2 , y1 , y 2 , y3 0
max w 10 y1 8 y2 4 y3 w 10 y1 8 y 2 4 y3 0
The first simplex tableau
bBV BV s1 s2 y1 y2 y3 ci
0 s1 1 0 2 1 1 2
0 s2 0 1 1 1 0 2
w 0 0 -10 -8 -4 0
Example 3: duality
Primal problem (minimization) Dual problem (maximization)
2 x1 x2 10 2 y1 y 2 y3 2
x1 x 2 8 y1 y 2 2
x1 4 y1 , y 2 , y3 0
x1 , x2 0 max w 10 y1 8 y 2 4 y3
min z 2 x1 2 x 2
The last simplex tableau for the dual problem:
bBV BV s1 s2 y1 y2 y3 ci Solution of the dual problem is the solution of
the primal problem:
4 y3 1 -1 1 0 1 0
8 y2 0 1 1 1 0 2 w = z = 16
w 4 4 2 0 0 16
x1 = 4
x2 = 4
Properties of a simplex tableau
Primal problem (minimization) Dual problem (maximization)
n m
a x
j 1
ij j bi , i 1, 2, ..., m a y
i 1
ij j ci , j 1, 2, ..., n
x j 0, j 1, 2, ...., n yi 0, i 1, 2, ...., m
m
b y
n
min z c x
j 1
j j
max w
i 1
i i
zw
x B 1b * y B 1c *
y cTBV B 1 x bBV
T
B 1
y - dual variables,
b* - right-hand side constraints,
c* - objective function coefficients.
Example 3: Properties of a simplex tableau
The firs simplex tableau for the dual problem: The last simplex tableau for the dual problem:
bBV BV s1 s2 y1 y2 y3 ci bBV BV s1 s2 y1 y2 y3 ci
0 s1 1 0 2 1 1 2 4 y3 1 -1 1 0 1 0
0 s2 0 1 1 1 0 2 8 y2 0 1 1 1 0 2
w 0 0 -10 -8 -4 0 w 4 4 2 0 0 16
(2) (or take directly from
(1)
the last simplex table)
y3 y2
1 1 (3) 1 1
B B 1
0 1 0 1
1 1 2 0
1 *
yB c
0 1 2 2
1 1
x T
bBV B 1 4 8 4 4
0 1