Description
Principles of Engineering Management
Question 1. Assume there are 5 clients that need to be supplied from a
warehouse. The following table lists the location of each of these clients in
terms of respective x and y coordinate values.
Client number Location in x coordinates Location in y coordinates
1 12 11
2 20 15
3 32 24
4 46 42
5 88 65
The distance is defined in terms of the sum of rectilinear movements, in
horizontal and vertical directions. (For instance, if warehouse is located at
the point (x, y), then its distance from the first client is |12 − x| +|11 − y| .)
(a) You are expected to come up with a linear programming model to choose
the coordinates of the location of the warehouse such that the sum of
the distances to all clients is as small as possible.
(b) How you modify your model in part (a) if your objective is to minimize
the largest of the five distance values?
1
Question 2. Consider the following linear programming model (LP):
min c1x − c2y
s.t. x − 2y ≤ 4
−x + y ≤ 3
x ≥ 0
y ≥ 0
Find positive coefficients c1 and c2 such that LP will have a unique optimal
solution.
Question 3. Consider the following tableau that corresponds to a maximizing LP in standard form. For each of the following parts, you need to change
the value of a single cell so that the stated condition is satisfied. Please carry
out a pivot operation after your change to see that, indeed, your answer takes
you to the desired state. Typically, more than one answer is acceptable. For
any positive number, write +1, and for any negative number, write -1 to
make grading easier.
(a) The bfs is optimal and there exists an alternate optimal bfs.
(b) The bfs is optimal and there exists alternate optimal solutions but only
one bfs which is optimal.
(c) The bfs is not optimal and x5 will become nonbasic after the next pivot.
(d) The bfs is not optimal and x3 will become basic after the next pivot.
2
(e) The bfs is degenerate.
Question 4. Turkish Airlines wants to plan seat arrangements for its upcoming flights that use 8 planes. The company currently has 20 planes to
choose from. There are two flight classes, namely economy, and business.
The plane room capacity is defined based on economy seats. Each plane can
seat up to 200 economy-class passengers. A business seat uses more room
and thus takes 1.5 times more seat room than an economy seat. The price of
a business ticket is two times that of an economy ticket. According to recent
regulations, if the total economy class seats over all 8 planes is less than a
certain threshold T (a given parameter), the company pays a penalty of $S
(another given parameter). Assume the ticket price for an economy seat is
$p (another given parameter).
(a) Formulate an integer programming model that will help Turkish Airlines
maximize its profit (total sales revenue-penalty cost (if any)) while obeying the capacity and operational limitations. Your model should be in
linear form.
(b) Now assume Turkish Airlines set a goal of G dollars for its upcoming
year’s total sales revenue (ignoring the penalty cost, if any). Formulate
this variant under the requirement that the maximum number of business
seats in each plane is minimum. You may define additional variables if
you like.
(c) Write the following additional restrictions due to some operational limitations in linear form to be appended to the model in part (a).
i. If both 1 and 5 are selected, then plane 6 or 8 or both should also
be selected.
ii. If neither plane 9 nor plane 10 is selected, then plane 4 should be
selected.
iii. Either at most two planes from the set {6,9,10} or at least four
planes from the set {1,4,5,13,15} should be selected.
iv. If at least one of planes 14, 17, and 19 is selected, then exactly one
of planes 15 or 20 should be selected.
3
