課程名稱︰作業研究 課程性質︰資管系 大二必修 課程教師︰孔令傑 開課學院：管理學院 開課系所︰資管系 考試日期（年月日）︰2018/05/24 考試時限（分鐘）：180 mins 試題 : 1. (10 points; 2 points each) For the following statements, answer "T" if one is true or "F" if it is false. DO NOT provide any explanation. (a) If a solution for a standard form LP is an optimal solution, then it must be a basic feasible solution for this LP. (b) If a linear program has two distinct optimal solutions, then it has infintely many optimal solutions. (c) If a primal linear program is unbounded, its dual program can only be infeasible. (d) For a given linear integer program with a minimization objective function, the branch-and-bound algorithm always finds a global minimum (if the computer is good enough). However, it may take a very long time. (e) For a given Nonlinear program with a minimization objective function, the gradient descent method always finds a global minimum (if the computer is good enough). However, it may take a very long time. 2. (10 points) Consider the following LP max x_1 - 2 * x_2 s.t. x_1 - 2 * x_3 ≦ 6 x_1 - 3 * x_2 + x_3 ≦ 12 3 * x_2 - 2 * x_3 ≦ 8 x_i ≧ 0 ∀ i = 1, ..., 3. Use the simplex method to solve the linear program. Whenever there are multiple choices of the entering or leaving variables, use the smallest index rule: Choose the variable with the smallest index. If the LP is infeasible or unbounded, clearly indicate why. If it has a unique solution, write it down. If it has multiple optimal solutions, write down only one of them. Hint. You should reach an optimal tableau in two iterations. 3. (10 points) Use the simplex method with the smallest index rule and the two -phase implementation to solve min x_1 + x_2 s.t. x_1 + x_2 + 2 * x_3 - x_4 ＝ 12 2 * x_1 + x_2 + x_3 ≦ 8 x_i ≧ 0 ∀ i = 1, ..., 4. Write down all the iterations to get full credits. 4. (15 points; 5 points each) Consider the following primal linear program z* = max 3 * x_1 + 2 * x_2 + x_3 s.t. x_1 + x_2 + 2 * x_3 ≧ 6 2 * x_1 + 2 * x_2 + x_3 ≦ 9 x_i ≧ 0 ∀ i = 1, ..., 3. You are given an optimal solution to the primal program x* = (x_1*, x_2*, x_3*) = (4, 0, 1). The corresponding objective value z* = 13. (a) Write down the dual linear program. Graphically find a dual optimal solution. (b) DO NOT solve your dual LP graphically or using the simplex method. Instead, according to your primal optimal solution x*, find a set of dual constaints that must be binding at any dual optimal solution. Then find a dual optimal solution by solving the resulting linear system. You may want to use your dual optimal solution to verify your solution in Part (a). (c) Find the shadow prices for the two primal constraints. 5. (15 points) Use the branch-and-bound algorithm to solve min x_1 + 2 * x_2 + x_3 + 3 * x_4 s.t. 4 * x_1 + x_2 + 2 * x_3 + 2 * x_4 ≧ 7 x_i ∈ {0, 1} ∀ i = 1, ..., 4. You need to draw the complete branch-and-bound tree. However, you do not need to write down how you solve each node. 6. (15 points) You are selling a product to a region with ten countries, each contains five cities. For each country i (i = 1,2,...,10), the construcion cost of building a distributing center (DC) is H_i and the DC can serve at most K_i consumers. For each city j (j = 1,2,...,5) in country i, the number of consumers is D_ij (i.e., you may serve at most D_ij consumers in this city), the cost of serving one consumer is C_ij, the revenue of serving one consumer is R_ij, and the construction cost of a retail store is F_ij. You may build at most one DC in each country, build at most one store in each city, and serve a consumer in a city only if you build a store in that city and a DC in the associated country. Note that you are NOT required to serve all consumers in a city when you build a store there. (a) (10 points) Formulate an integer program that can maximize the total profit . (b) (2 points) Write additional constraints (and define new variables if you need) so that if you build a DC in country 6, you must also build a DC in country 8. (c) (3 points) Write additional constraints (and define new variables if you need) so that in no more than seven countries you duild no greater than two stores. 7. (10 points) Consider a linear program max x_1 + x_2 s.t. x_1 + 2 * x_2 ≦ 6 2 * x_1 + x_2 ≦ 6. solve this program by applying the KKT condition. DO NOT solve this program with the graphical approach or simplex method. 8. (15 points; 5 points each) A firm is trying to design and sell an app. The quality level and price of the app are denoted as q and p, respectively. To reach the quality level, an R&D fee cq^2 is paid to required. The firm chooses q ≧ 0 and p ≧ 0 to maximize its expected profit. After some derivations (the process is omitted), the firm's profit maximization problem is formulated as max p * ( 1 - p/q ) - 2 * q^2. q≧0,p≧0 Please note that the only cost of the firm is the R&D cost; reproducing the app does not incur any cost. (a) Find the gradient and Hessian for the nonlinear program. (b) Find a condition under which the nonlinear program is concave (or show that it is concave everywhere). (c) Let c = 2, starting from (p, q) = (1/2, 1/2) to run one iteration of gradient descent to get to the next solution. Set the step size (the notation "a" used in the lecture) to 1; DO NOT try to find an optimal step size. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.99 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1528535818.A.461.html