Reference no: EM132729396

Question 1. Write an optimization problem to find the best location (px, py) to place a tv station broadcast antenna so that the average A1-distance to all the houses in the area is minimized. The location of the N houses are given by (h1,x, h1,y), (h2,x, h2,y), (h3,x, h3,y), . . . (hN,x, hN,y). Note however, that due to zoning restrictions, the antenna must be located within an industrial area of radius 5 miles, centered at (cx, cy).

(a) Write the optimization program. Clearly define all cost and constraint equations, deci- sion variables, etc.

(b) Implement and solve in CPLEX; explain necessary changes to the formulation required for implementation.
Use (cx, cy) = (-4, 5) and the locations, hi,x, hi,y, for three houses are given by
{(10, 10), (-4, -10), (0, -5)}. Where should the antenna be located?

(c) Instead of using the average A1-distance in the cost equation, minimize the average of the squared euclidean distance (e.g. 1/N · ΣN dist(antenna, home)2). Implement in CPLEX as a quadratic program. Where should the antenna be located?

(d) Discuss why there are differences in the solutions between the different cost functions. For example, discuss which cost function penalizes large distances more.

(e) [Extra Credit] Instead of using the average l1-distance in the cost equation, minimize the maximum l1-distance between the antenna and the houses

Question 2. Consider the following optimization problem

min   3x² - 5x
x

subject to x ≤ 13
               x ≥ -5
               x ∈ R
(a) Formulate and solve in CPLEX as a quadratic program.
(b) Find the linear approximation of the cost function about the points x˜ ∈ {0, 1, 2}. Using the linear approximation, rewrite the optimization problem in matrix form:

min  c^Tz
z

subject to Az ≤ b
                z ∈ R?

State c^T , A, and b. Also, clearly define the decision variable z. Make sure to include ALL constraints from the original problem.

(c) Implement the linearized optimization problem from part (b) in CPLEX as a linear program. Compare the solution with your response from part (a). Using a graph as evidence, explain why the answers are different or the same.

(d) Find the linear approximation of the cost function about the points x˜ ∈ {-5, -2, 0, 1, 2, 5, 10}. Using the linear approximation, implement the linearized optimization problem in CPLEX as a linear program. Compare the solution with your responses from parts (a) and (c). Explain why the answers are different or the same.

(e) Find the linear approximation of the cost function about the points x˜ ∈ {.8, .9}. Using the linear approximation, implement the linearized optimization problem in CPLEX as a linear program. Compare the solution with your responses from parts (a), (c), and (d). Provide some insights regarding the number of tangents lines and their location with the accuracy of the linear approximation.

(f) [Extra Credit] Using knowledge derived from (a)-(e) propose an algorithm to solve sim- ilar convex optimization problems by sequentially solving linear approximations of the original problem.

Question 3. Here we will consider the problem of the hotdog / newspaper stand discussed in lecture. Let's suppose the owner of the hotdog stand purchases hotdogs at a bulk price of $.50 per hotdog, and sells them at $1.50. Assuming the demand for hotdogs follows a probability distribution given by pi, where i ∈ {1, 2, ...N} is the number of customers (see excel file). Program a stochastic optimization program in CPLEX Optimization Studio to determine the number of hotdogs the owner should buy in bulk each day to maximize their expected profit. (Per the original discussion in lecture, assume any remaining hotdogs must be thrown out at the end of each day. Also, N is the maximum possible customer demand)
Download the excel file with the probability distribution of the customer demand.
• Load data directly from excel - do not hardcode in values. Note, in the excel file the "array" of probabilities are labeled 'p'. Also, the maximum number of customers N is labeled 'N' in the excel file.
• For this problem you are not required to submit a write up or explanation, only submit your CPLEX files.
• Submit your '.mod' file with the name 'p3.mod'. It is okay if webcourses automatically adds a ‘suffix' to the file name.
• Submit your '.dat' file with the name 'p3.dat'. It is okay if webcourses automatically adds a ‘suffix' to the file name.

Attachment:- p3 data.rar