Mock LOA
docx
keyboard_arrow_up
School
HEC Montréal *
*We aren’t endorsed by this school
Course
20604A
Subject
Industrial Engineering
Date
Jan 9, 2024
Type
docx
Pages
9
Uploaded by mmirieu2020
PROBLEM 1
: 10604 INTRA H2020
Genius produces its SHT computer models from batches of recycled material coming from
reclaimers of old computers that are no longer in use (SHT comes from the abbreviation Super
High Tech). Genius obtains its batches of material from
4 different suppliers. Each batch is divided into a maximum of 5 components that we will name
C1, C2, ..., C5. The distribution of the number of components of each type per batch is given in
the following table. The last line of this table shows the acquisition cost (in $) of a batch:
The components obtained allow for the production of SHTs in 2 models. Genius would like to
produce 125 units of model M1 and 175 units of model M2.
The following table shows the
number of components needed to produce one unit of each of these models. If there are any
surplus components, they can be resold at the price indicated in the last column of the table.
125*60+175*75 = 20,625
Genius seeks to determine the number of lots that will need to be purchased to have enough of
each type of component to produce all the units of SHT while maximizing its profit for all of
these operations.
In the answer key, we have suggested the following model:
Variables
:
X
j
= number of batches purchased from supplier
j
,
j=1
, 2, 3 or 4.
In total, Genius will need 1,025 C1, 1,075 C2, 725 C3, 1,250 C4 and 1,125 C5. The surplus will
be resold... We can calculate the number of surplus components, but it is easier to assign a
variable to them:
Q
i
= number of components of type
i
in surplus,
i=1
, 2, ..., 5.
The objective function
to be maximized:
The profits associated with all these operations will be:
SHT's model revenues =
(60*125 + 75*175) = 20 625$;
Plus surplus income =
(
Q
1
+2
Q
2
+ 2Q
3
+
Q
4
+ 3Q
5
);
Minus the acquisition costs of the lots = 20
X
1
+ 15
X
2
+ 25
X
3
+ 20
X
4
.
MAX 20 625 + (
Q
1
+2
Q
2
+ 2Q
3
+
Q
4
+ 3Q
5
) - (20
X
1
+ 15X
2
+ 25X
3
+ 20X
4
);
Constraints
:
2
X
1
+
1
X
2
+
3
X
3
+
2
X
4
−
Q
1
=
1025
3
X
1
+
1
X
2
+
2
X
3
+
2
X
4
−
Q
2
=
1075
1
X
1
+
1
X
2
+
2
X
3
+
1
X
4
−
Q
3
=
725
4
X
1
+
0
X
2
+
1
X
3
+
3
X
4
−
Q
4
=
1250
0
X
1
+
2
X
2
+
1
X
3
+
1
X
4
−
Q
5
=
1125
Moreover, the variables are all non-negative and integer.
Question 1: (5 points)
A 5
th
supplier has just entered the market. It could sell lots with the following data: its lots are $12
each and contain 1 unit of each of components C1, C2 and C3 and 2 units of components C4 and
C5 but there is also a fixed cost of $50 if this new supplier is used. How should the model be
modified to account for this new player?
Answer 1:
We will have to add a variable
X
5
to the model that corresponds to the number of lots purchased
from this supplier. We will have to subtract 12*X
5
from our objective function. We will add this
variable to the 5 constraints with the appropriate coefficients.
To account for fixed costs, we will need to add a binary variable
Y
that will take the value 1 if
X
5
is greater than 0 and 0 otherwise. Asked that
X
5
≤
M Y
, and subtract 50Y from the objective
function. For the value of M, we need 1025 components 1, 1075 components 2, 725 components
3, 1250 components 4 and 1125 components 5, so there is no need to order more than 1075. We
can set
M=1075
.
The model thus becomes:
Max 20 625+(
Q
1
+2
Q
2
+ 2Q
3
+
Q
4
+ 3Q
5
) - (20
X
1
+ 15X
2
+ 25X
3
+ 20X
4
+ 12 X
5
) - 50
Y
;
Constraints
:
2
X
1
+
1
X
2
+
3
X
3
+
2
X
4
+
1
X
5
−
Q
1
=
1025
3
X
1
+
1
X
2
+
2
X
3
+
2
X
4
+
1
X
5
−
Q
2
=
1075
1
X
1
+
1
X
2
+
2
X
3
+
1
X
4
+
1
X
5
−
Q
3
=
725
4
X
1
+
0
X
2
+
1
X
3
+
3
X
4
+
2
X
5
−
Q
4
=
1250
0
X
1
+
2
X
2
+
1
X
3
+
1
X
4
+
2
X
5
−
Q
5
=
1125
X
5
≤
1075
Y
Moreover, the variables are all non-negative and integer,
Y
is binary.
Question 2: (5 points)
A 6
th
supplier has just entered the market. It could sell lots with the following data: its lots contain
2 units of each of components C1 and C5, 1 unit of components C2 and C4, and 3 units of
components C3. The cost of the lots is $20 for the first 100 lots and $15 for the rest of the lots.
How should the model in the previous question be modified to account for this new player?
Answer 2:
Two variables
X
6
and
X
7
should be added to the model, corresponding to the number of lots
purchased from this supplier at $20 and the number of lots at $15. In the objective function,
subtract (20 X6 + 15 X7). In addition, we will have to prohibit X7 from being greater than 0 as
long as X6 is less than 100. We will therefore add a binary variable Y2 that will indicate if
X6=100. The model becomes:
20 625 + Max (
Q
1
+2
Q
2
+ 2Q
3
+
Q
4
+ 3Q
5
) - (20
X
1
+ 15X
2
+ 25X
3
+ 20X
4
+ 12
X
5
+ 20
X
6
+ 15
X
7
) - 50
Y
;
Constraints
:
2
X
1
+
1
X
2
+
3
X
3
+
2
X
4
+
1
X
5
+
2
X
6
+
2
X
7
−
Q
1
=
1025
3
X
1
+
1
X
2
+
2
X
3
+
2
X
4
+
1
X
5
+
1
X
6
+
1
X
7
−
Q
2
=
1075
1
X
1
+
1
X
2
+
2
X
3
+
1
X
4
+
1
X
5
+
3
X
6
+
3
X
7
−
Q
3
=
725
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
4
X
1
+
0
X
2
+
1
X
3
+
3
X
4
+
2
X
5
+
1
X
6
+
1
X
7
−
Q
4
=
1250
0
X
1
+
2
X
2
+
1
X
3
+
1
X
4
+
2
X
5
+
2
X
6
+
2
X
7
−
Q
5
=
1125
X
5
≤
1075
Y
100
Y
2
≤ X
6
≤
100
0
≤ X
7
≤
1150
Y
2
Moreover, the variables are all non-negative and integer,
Y
and
Y
2
are binary.
Question 3: (5 points)
Genius would like to have no more than 2 suppliers from the 6 already mentioned. How should
the model be modified to ensure that no more than 2 vendors are selected?
Answer 3:
We just need to add 6 constraints saying that
X
j
≤0 for j=1,2,... 6, and allow at most 2 of these
constraints to be violated. To achieve this we will use 6 binary variables:
Z
j
={
1
if X
j
>
0
and
0
otherwise
We will use these variables as follows:
X
j
≤
0
+
1250
Z
j
for
j=1
to 5 and
X
6
+
X
7
≤
0
+
1250
Z
6
for the 6
th
supplier.
And we add a constraint to limit the number of binary variables that will take the value 1:
Z
1
+
Z
2
+
Z
3
+
Z
4
+
Z
5
+
Z
6
≤
2.
PROBLEM 2:
Consider the following enumeration tree obtained during the solution of a minimization
problem of an integer linear programming model. For each node, numbered from N0 to
N8, we have the lower bound (BI) associated to this node and its upper bound (BS) :
Question 1:
After solving these 9 linear relaxations, what is the best lower bound and what is the best upper
bound for the optimal value of the initial integer problem?
Question 2:
Which nodes should be researched further and which nodes should be terminated? Why should
the search be stopped?
Answer 1:
For the lower bound, the smallest upper bound is obtained at node N5: 112. This is the upper
bound for the value of
Z*
.
For the lower bound, there is still hope on the side of node N8 to find a better solution than 112.
We have a lower bound of 110.4.
The value of the objective function for the optimal solution is therefore in the interval [110.4;
112].
Answer 2:
For nodes N4 and N7, the lower bound is greater than the best-known solution at node N5. The
search is complete for these nodes.
For node N3, the set of admissible solutions is empty. So, we stop the search on this side.
For node N5, we have an integer solution whose value is 112, it is useless to try to find a better
solution on this side.
For node N8, there is hope of finding a better solution. So, we will have to plug in here, unless a
solution that is within
112
−
110,4
112
=
1,4%
from the optimal solution is sufficient.
PROBLEM 3:
Consider the following particular assignment problem. We have a set of
m
customers to be served
from a service point. There are
n
service points, but only
k
can be used. The idea is to assign
customers to one and only one service point in order to maximize profits. When a customer
i
is
assigned to service point
j
, there is a profit
p
ij
> 0. For this problem we have the following model:
Variables:
x
ij
={
1
if client iis assigned
¿
point j ,
∧
0
otherwise
y
j
={
1
if point j isselected ,
∧
0
otherwise
The objective function:
Max
∑
i
=
1
m
∑
j
=
1
n
p
ij
x
ij
Constraints:
Each customer is served one and only one time. We have constraints:
∑
j
=
1
n
x
ij
=
1,
i
=
1,2
,
⋯
,m
Customers can be served from point
j
only if it is open. We have n constraints:
∑
i
=
1
m
x
ij
≤n∙ y
j
, j
=
1,2,
⋯
,n
We can only use
k
points. We will then have the following constraint:
∑
j
=
1
m
y
j
≤k
Question 1:
Propose a greedy heuristic for this problem.
Question 2:
Apply your heuristic for the problem with 7 customers when we will have to choose at most 3
service points out of a possibility of 5 and the
p's
ij
are given by :
Answer 1:
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
We will start by using the service point that maximizes profits. Let
a
be
1
the number of this
service point. Let
S=
{a
1
} and
T= S\{a
1
}.
S
corresponds to the set of used service points and
T
to
those not used. For each customer we will keep in a vector
P
the profit associated to this vector:
P
i
=
max
j
∈
S
{
p
ij
}
Let Counter=1, which is a counter of iterations.
As long as
Counter < k perform the following calculations:
For each customer
i
, for each service point
j
in
T
calculate
r
ij
=
Max
{
p
ij
, P
i
}
For each deposit in
T
, calculate the sum
Total
j
=
∑
i
=
1
m
r
ij
Let
j*
be the duty point of
T
that has the largest value for
Total
j
.
Let S = S U {j*}, T = T \ {j*}. Counter = Counter +1.
End of
As long as.
Answer 2:
In the first iteration, we will choose point #5 which has a total profit of 65. In iteration 2, we will
open service point #3. The profits will then rise to 77. Finally, adding #2 as the third
e
service point
will bring the total profit to 80.
PROBLEM 4
: (10604 Aut 2019)
X, a machine tool manufacturing company, has just received approval from its banker to launch a
new line of three types of industrial drills. The following table shows, for the next month, the
number of hours of machining required to manufacture one unit of each type of drill, the number
of tons of steel required to manufacture one unit of each type of drill, and the profit in thousands
of dollars associated with the sale of one unit of each type.
Unit contributions
Type 1
Type 2
Type 3
Tons of steel required
8
6
9
Machining hours
40
30
20
Associated profit ($000)
25
18
14
X has 160 tonnes of steel available for this month. Any tonnes of steel not used during the month
would have to be stored at a cost of $100 per tonne for the month. X could purchase additional
tonnes of steel throughout the month from a competitor at a price of $600 per tonne.
X currently has 400 hours of machining labour per month.
X will try not to put any workers out
of work, motivated by the fact that its reputation as a good employer would suffer greatly. She
estimates that she will lose $20 in productivity for each available hour that is not used. However,
X knows that it could access additional labour hours by using temporary workers to whom it
would have to pay $40 per hour.
X's agreement with his banker, who was reluctant to launch this new line of drills, stipulates that
sales of the drills must ensure a total profit of at least $300,000 for the month. If the monthly
profit was lower, X would have to compensate by selling to the banker for every thousand dollars
short of this profit target, one share of X Company stock whose stock market price is around
$1,200.
X considers these three wishes as objectives.
In a first modelling effort, we will use the variables
x
1
,
x
2
and
x
3
, where
x
i
represents the number
of drills of type
i
that will be produced per month (for
i=1
, 2, 3).
Question 1:
Specify, in three short sentences, the three objectives that X will address if he decides to look at
the situation using
Goal programming
.
Question 2:
Using deviation variables, give a version of each of these three objectives.
Question 3:
Give an objective function with appropriate weights.
Answer 1
:
Goal #1
: Use exactly 160 tons of steel (Using less will cost $100 per ton for storage and more
will cost $600 per ton)
Goal #2
: Use 400 hours of labor (Using less results in a $20 loss in productivity, and using more
costs $40 per additional hour)
Goal #3: To
have a profit of at least $300,000. (Every thousand dollars less results in a loss of
$1200)
Answer 2:
Let's ask:
+
¿
−
¿
;d
i
¿
d
i
¿
the deviation variables associated with the objective #
i
(
i=1
, 2, 3)
+
¿
=
160
−
¿
−
d
1
¿
8
x
1
+
6
x
2
+
9
x
3
+
d
1
¿
+
¿
=
400
−
¿
−
d
2
¿
40
x
1
+
30
x
2
+
20
x
3
+
d
2
¿
+
¿
=
300
−
¿
−
d
3
¿
25
x
1
+
18
x
2
+
14
x
3
+
d
3
¿
Answer 3:
−
¿
+
¿
+
1200
d
3
¿
−
¿
+
40
d
2
¿
+
¿
+
20
d
2
¿
−
¿
+
600
d
1
¿
Min
100
d
1
¿
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help