DNSC 6212: Optimization Methods and Applications
Fall 2018 – Final Exam
Instructions
1. The exam was made available at 8:00 am on Friday 12/14, and is due by midnight on Monday 12/17.
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 you need further clarification for any item, 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. 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 – 12 points)
A company has two plants, A and B, and three demand regions X, Y and Z. Over periods 1, 2, and 3, plant A has available supplies of up to1As, 2As and3As, respectively, and plant B has available supplies of up to1Bs, 2Bs and3Bs, respectively. Similarly, over periods 1, 2, and 3, the required demands for the three regions are denoted by 1Xd, 2Xd and 3Xd for region X, 1Yd, 2Yd and 3Yd for region Y, and 1Zd, 2Zd and 3Zd for region Z. Let ijcdenote the cost of shipping a unit from plant i (i = A, B) to demand region j (j = X, Y, Z) in any period. Up to uA and uB units can be held in inventory at plants A and B, respectively. Let hA and hB denote the per unit holding cost at plants A and B, respectively.
(a) Assuming that feasible solutions exist for the model, draw a complete network flow model for the problem. Make sure to include all arcs, nodes, supply amounts and their types (≤, ≥, or =), demand amounts and their types (≤, ≥, or =), costs and bounds. (9 points)
(b) Suppose now that it is impossible to meet all of the stipulated demands. Modify the network model of Part (a) to allow for filling as much of the demand as possible while minimizing overall cost. (3 points)
Question 2 (Network Models 2 – 10 points)
Draw the network model corresponding to the following LP. Make sure to include all arcs, nodes, supplies, demands, costs and bounds.
2
12142324525354Minimize 352534xxxxxxx++++++
1214Subject to: 10xx−−=− 122324520xxxx−−+= 23536xx+= 1424547xxx++= 5253543xxx−−−=− 12142324525354,,,,,,0xxxxxxx≥ 12543,5xx≤≤
Question 3 (Integer Programming – Algebraic Formulation – 13 points)
A large drug company must determine how many sales representatives to assign to each of four sales districts. The cost of having R representatives in a district is ($88,000 + $80,000R) per year. If a “rep” is based in a given district, the average time (in hours) required to complete a call on a doctor in each of the four districts is given in the table below.
Each sales rep can work up to 160 hours per month, and the required numbers of monthly calls for each district are:
District
# of Calls
Provide a complete formulation for the problem. Make sure to clearly define the variables, objective, and all constraints. Constants used for fixed charge constraints, if any, should be set at their minimum “safe” values.
Question 4 (Integer Programming – AMPL Implementation – 25 points)
A “green” automobile manufacturing company is planning capacities and configurations of three plants to produce four electric vehicle models for the upcoming market cycle. The first table below shows the configuration options available at each plant, along with the implied capacities (in thousands of vehicles) and fixed changeover costs (in $ million). Option 1 for each plant is the current facility configuration with no changeover cost involved.
District of Call
District of Rep
Different configurations at the plants imply different mixes of models that can be manufactured there. The second table shows the production cost ($ thousand per vehicle) for the models that are eligible for manufacture at a specific plant given the chosen configuration.
Exactly one configuration must be chosen for each plant well in advance, but demands and market prices that will materialize for vehicles produced are uncertain until later. The next table shows four scenarios for demands and prices applicable for the entire market cycle. Estimated probabilities for the scenarios are p(s) = 0.15, 0.30, 0.35 and 0.20, respectively.
The model below was developed for the problem, while making use of the following additional notation.
C(j) = Set that contains all configurations that are allowable for plant j
PC(i) = Set that contains all plant/configuration pairs, (j, k), that can produce model i
()344()()1()11(.)()MaximizesssjkjkiijkijkjkCjsijkPCifyprcx=∈==∈−+−ΣΣΣΣΣ
Subject to: ()1,1,...,3jkkCjyj∈==Σ ()(,)(),1,...4,1,...,4ssijkijkPCixdis∈≤==Σ {}()1,...,4(,)(),1,...,3, and (),1,...,4sijkjkjkijkPCixuyjkCjs∈∈≤=∈=Σ
4
yjk binary, j = 1, …, 3 and all k ∈C(j) ()0,1,...,3 and all (,)()sijkxijkPCi≥=∈
(a) Clearly justify the formulation. Explain the structure of the model and all its components (decision variables, objective function constraints). (5 points)
(b) Will the solution always assume integral values for the()sijkx decision variables? Clearly justify your answer. (2 points)
(c) Implement the model in AMPL, and discuss the solution obtained. 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. (18 points)
Question 5 (Branch and Bound – 12 points)
Develop a complete branch-and-bound tree to minimize a mixed integer program with binary variables w1, w2 and w3, and continuous variable w4 ≥ 0. Use:
• Depth first for node selection, and in the case of a tie, the nearest child rule.
• Variable with value closest to an integer for branching.
• Parent node bounding (whenever applicable) for fathoming.
• The LP relaxation outcomes for all possible combinations of fixed and free (denoted by #) variables as shown below.
Make sure to clearly describe the logic followed in constructing the tree.
5
Question 6 (Nonlinear Programming Theory – 16 points)
Consider the following quadratic program (QP).
()()()22212323123maximize 821014820xxxxxxxx−−−++−+
subject to: 1344xx+= 2331xx−+=
(a) A general symmetric quadratic program can be stated as:
maxs.t.: TT+=cxxQxAxb
What are the values for Q, c, A and b for this QP? (4 points)
(b) Write the KKT conditions for the model. (6 points)
(c) Solve the system of equations from (b) to find the KKT point for the model. (2 points)
(d) Is the point you obtained in (c) a global optimum for the QP? Clearly justify your answer. (4 points)
Question 7 (Nonlinear Programming Modeling – 12 points)
Each day qi tons of freight arrive by sea in Japan bound for in-country regions i = 1,…, 50. These goods may arrive at any of the major ports j = 1,…, 17, but the internal transportation cost per ton cij varies by port and destination. The government plans a capital investment program in port facilities to secure a daily tonnage processing capacity at each port j that minimize the total transportation, maintenance and delay costs. Port j’s maintenance costs can be expressed as ()capacity of port jbjaj , where aj and bj are known constants. Delay cost at j can be estimated by ()(),capacity of port tons shipped through of port djj−where d is the delay cost per ton per day. Formulate an NLP model to optimize the ports using the decision variables (i = 1,…,50, j = 1,…,17):
tons shipped through port for region ijxji
tons shipped through port jxj
capacity of port jyj
(a) Provide a complete algebraic formulation for the problem. (9 points)
(b) Attempt to determine if your formulation corresponds to a convex program or not. (3 points)