Instructions
DNSC 6212: Optimization Methods and Applications Fall 2019 – Final Exam
1. The exam was made available at 8:00 am on Saturday 12/14, and is due by midnight on Monday 12/16.
2. Please work independently on the exam. NO COLLABORATION, WHATSOEVER, IS PERMITTED. Make sure to include and sign a statement attesting that the exam was completed by you alone, without seeking help from others, and in accordance with the Code of Academic Integrity. This is required for me to grade the exam.
3. I added a Discussion Forum in Blackboard for the exam. If you feel there is a typo or wording ambiguity, please post your question under the forum. If I decide that the question is of merit, I shall post a clarification for everyone’s benefit. All other questions discussing the exam may be tantamount to academic dishonesty. I suggest that you subscribe to the forum to stay aware of any questions and answers posted. I shall not be answering questions regarding the exam via e-mail.
4. Make sure to upload to Blackboard ONE zipped folder that contains your exam solution (pdf file, AMPL files, Excel, etc.). I’ll allow for two submission attempts just in case you need to re-submit; however, I shall be grading the last submission you make. Do NOT send me your exam solution via e-mail.
Question 1 (Network Models 1 – 22 points)
The supply chain for a company consists of two plants (P1 and P2), four central depots (D1 through D4), and six regional warehouses (W1 through W6). The distribution costs (in $ per ton) between the plants and the depots, and then the depots and the regional warehouses are shown in the first and second tables below.
In order to relieve the congestion that can happen at the depots, the company has recently allowed limited direct shipping from plant P1 to regional warehouses W1, W4 and W6, and from plant P2 to regional warehouse W1. The table below shows the corresponding distribution costs.
1
Certain regional warehouses have expressed preferences for being supplied from certain plants or depots. W1 has expressed preference for plant P1, W2 for depot D1, W5 for depot D2, and W6 for depots D3 or D4. The monthly capacity for plants P1 and P2 (in tons) are 300,000 and 400,000, respectively, and the maximum monthly throughput for depots D1, D2, D3, and D4 (also in tons) are 140,000, 100,000, 200,000, and 80,000, respectively. Finally, the monthly requirements for the regional warehouses W1, W2, W3, W4, W5, and W6 (in tons), are 100,000, 20,000, 80,000, 70,000, 120,000, and 40,000, respectively.
(a) Draw a network flow model for the problem that does not take the stated preferences into account. (6 points)
Make sure to include:
• All nodes with associated exogenous supply and demand.
• All arcs with associated costs and capacities.
(b) Implement the model in AMPL. Follow the “good practices” demonstrated in the various
examples we’ve done together. In particular, make sure that the model allows for changes in the data as well as the dimension (i.e., size) of the problem instance. Provide the .mod, .dat and .run files for the model. Make sure to use CPLEX’s netopt option. (9 points)
(c) Referring back to the solution you obtained in (b): (3 points)
• Describe the distribution plan that minimizes the overall cost.
• Which preferences could be met? Which were violated and by how much?
(d) Modify the network model to give the highest priority to meeting the stated preferences. (4 points)
• How exactly is the network model modified?
• Update your AMPL implementation and re-run the model. Provide separate updated
AMPL file(s) for the modified version.
• Which preferences can now be met? Which are still violated and by how much? At what
cost did this improvement in meeting the preferences come?
Question 2 (Integer Programming – Algebraic Formulation – 15 points)
A company supplies retailers with one of two products (P1 and P2). Due to historical reasons, the company is organized in two major divisions (D1 and D2) that operate autonomously to a large extent. At this point in time, senior management is interested in re-organizing the allocation of markets to each division with the goal of having D1 control about 40% of the market and D2 the remaining 60%. The table below shows for each market (M1-M23), the region (R1-R3) it is in, yearly demand for each of the two products, number of delivery points, and a growth potential indicator (A or B).
2
It is desired to enforce the 40-60 split between the two divisions for each of the following aspects:
1. P1 market in region R1,
2. P1 market in region R2,
3. P1 market in region R3,
4. Overall P2 market,
5. Overall number of delivery points,
6. Overall number of retailers in group A, and
7. Overall number of retailers in group B.
Provide a complete algebraic formulation for an optimization model that can help the company minimize the maximum percentage deviation from the desired 40-60 split for the seven stated aspects. Make sure to explain in detail the decision variables, objective, and constraints.
Question 3 (Integer Programming – AMPL Implementation – 25 points)
A utility company is committed to meeting demand for electricity, expressed in megawatts (MW) per hour, for each day as shown in the first table below. The utility company uses thermal generators: 12 of type 1, 10 of type 2, and 5 of type 3. As shown in the second table below, each thermal generator has to work between a maximum and a minimum output level expressed in MW/hour. There is an hourly cost for running a generator at its minimum level, and there is an
3
extra cost per MW-hour for going beyond the minimum level. Starting up a thermal generator also incurs a fixed cost as shown.
In addition to the thermal generators, the company has a reservoir that can operate one hydro- generator of type A and another of type B. When a hydro-generator operates, it generates a fixed output level (MW/hr), and the depth of the reservoir decreases at a fixed rate per hour. There is an associated fixed startup cost and a running cost per hour. The characteristics of the two hydro-generators are shown in the third table below.
For environmental reasons, the reservoir depth has to remain between 15 and 20 m. The thermal generators are used to pump water into the reservoir, and it requires 3,000 MW to increase the reservoir level by 1 m. For modeling purposes, we assume that rainfall does not affect the reservoir level.
Regulations require that the company should allocate enough generation “capacity” to meet up to 15% increase in demand for electricity, with the capacity, in this case, corresponding to that of both hydro-generators plus the maximum output levels of thermal generators that are planned to be started. Note that while thermal generators cannot be switched on instantaneously to meet increased demand, hydro-generators can be.
The company develops an optimization model to help answer the following two questions:
• Which generators should be working in which periods of the day?
• How should the reservoir be maintained to minimize the total cost? The following indices, sets, and parameters are first defined.
i = Index for generators
T = Set of thermal generators H = Set of hydro-generators
j = Index for demand periods (j = 1,…,5) 4
Ei = Cost at minimum level for operating thermal generator i ∈ T ($/hr)
Ci = Cost above minimum level for operating thermal generator i ∈ T ($/MW-hr) Fi = Start-up cost for thermal generator i ∈ T ($)
mi = Minimum output level for thermal generator i ∈ T (MW/hr)
Mi = Maximum output level for thermal generator i ∈ T (MW/hr)
Ni = Number of units available for thermal generator i ∈ T
Ki = Cost for operating hydro-generator i ∈ H ($/hr)
Gi = Start-up cost for hydro-generator i ∈ H ($)
Li = Output level for hydro-generator i ∈ H (MW/hr)
Ri = Reservoir level reduction when operating hydro-generator i ∈ H (m/hr)
Tj = Number of hours in period j (j = 1,…,5)
Dj = Demand for period j (j = 1,…,5) (MW/hr)
The model formulation is as follows. 55555
Fs + i ij
Minimize∑∑ETn +
∑∑ i∈T j=1
CT (x −mn )+ ijij iij
∑∑ i∈T j=1
∑∑ i H j 1∈
∑∑ i∈H j=1
Gt i ij
i∈T j=1
i j ij
i j ij
KTh +
Subject to:
∑xij +∑Lihij −pj ≥Dj,j=1,…,5
i∈T i∈H
xij ≥minij,∀i∈T,j=1,…,5
xij ≤Minij,∀i∈T,j=1,…,5 lj−lj−1−Tjpj +∑TjRihij=0,j=1,…,5
=
3, 000 i∈H
∑Minij ≥1.15Dj −∑Li,j=1,…,5
i∈T i∈H
xij ≥nij −nij−1,∀i∈T,j=1,…,5*
sij ≥hij −hij−1,∀i∈H,j=1,…,5* 0≤nij ≤Ni,∀i∈T,j=1,…,5
15≤lj ≤20,j=1,…,5
nij and sij are integer,∀i∈T, j =1,…,5 xij ≥0,∀i∈T,j=1,…,5
hij and tij are binary,∀i∈H, j =1,…,5
5
lj,pj ≥0,j=1,…,5
* When j = 1, period j−1 is taken as 5.
(a) Clearly justify the formulation. Explain the structure of the model and all its components (decision variables, objective function, and constraints). (8 points)
(b) Implement the model in AMPL. Follow the “good practices” demonstrated in the various examples covered in class. In particular, make sure that the model allows for changes in the data as well as the dimension (i.e., size) of the problem instance without changing the model formulation. Provide the .mod, .dat and .run files for the model. (13 points)
(c) Use your solution from (b) to comprehensively address the two questions the company would like answered. (4 points)
Question 4 (Branch and Bound – 15 points)
We’ve seen several examples of branch-and-bound involving binary variables. Branch-and- bound equally applies to general integer programs. The main difference is how the branching is done. Suppose that we select a variable xi = 3.25 for branching, then one branch will set xi ≤ 3.00 and the other branch xi ≥ 4.00. Otherwise, the algorithm proceeds in the same way as for binary variables. For problems where the objective function coefficients are all integer, the objective function value for any feasible integer solution has to also be integer, and this fact can be used to tighten the upper bounds at the B&B node. Accordingly, any bound obtained can be rounded down (for maximization problems) to the nearest integer. For example, if the objective function value for the LP relaxation at some node is v = 14.76, then based on the above
observation, the bound can be tightened to v = 14 .
Develop a complete branch-and-bound tree to solve the IP below. Use:
• Best-bound-first for node selection,
• Variable with fractional value closest to 0.5 for branching,
• Parent node bounding (whenever applicable) for fathoming, and
• Bound tightening as described above.
Make sure the numbering of nodes follows the order in which the candidate problems are solved, and that all bounds, solutions and fathoming decisions are clearly indicated for each node.
Maximize Subjectto:
3y1 +2y2 +y3 +2y4
y1 −y2 +2y3 +y4 ≤11 y2 + y3 + y4 ≤ 7
3y1 −y3 −3y4 ≤5
y1 , y2 , y3 , y4 ≥ 0 and integer
6
Question 5 (Nonlinear Programming Theory – 23 points)
A company sells two main products. The marketing department has estimated linear demand functions relating the price and monthly demand for the each of the two products. For Product 1, the demand function is x1 = 550 – 2.5p1, where p1 and x1 are the price and demand volume, respectively. The demand function for Product 2 is x2 = 900 – 5p2 , where p2 and x2 are the price and demand volume, respectively, for Product 2. The variable costs of production are $60 per unit for Product 1, and $45 per unit for Product 2. Each product is assembled and inspected on site. Product 1 requires 2 hours per unit for assembly, and 2 hours per unit for inspection, while Product 2 requires 3 hours per unit for assembly, and 1 hour per unit for inspection. A total of 800 assembly and 500 inspection hours are available. Assume that p1 ≥ 60 and p2 ≥ 45.
(a) Provide a mathematical program for the problem that maximizes the company’s profit. (3 points)
(b) Implement and solve the model in Excel; report and describe the solution. (7.5 points)
(c) Classify the model (e.g., convex, separable, quadratic, etc.). Can we claim that the solution is a global optimum? Why or why not? Hint: In the objective function, substitute for x1 and x2 their corresponding expressions in terms of p1 and p2. (4 points)
(d) Suppose that instead of the given demand functions, the company decides to use constant elasticity demand functions x1 = 8,762(p1)−1.27 and x2 = 2,329(p2)−2.94. These alternative demand functions are characterized as being of constant elasticity because for a 1% increase in price, the demand decreases by a fixed percentage, referred to as the constant of elasticity. (3.5 points)
• Determine the demand constants of elasticity for these two products.
• Provide an alternative formulation for the model to determine the optimal prices and
production amounts.
(e) Answer (b) and (c) for the new formulation. (5 points)
7
Reviews
There are no reviews yet.