課程名稱︰作業研究 課程性質︰資管系選修 課程教師︰孔令傑 開課學院：管理學院 開課系所︰資管系 考試日期（年月日）︰110.05.25 考試時限（分鐘）：180 試題 : 註：以下部分數學符號與式子以LaTeX語法表示。 1. (5 points) Write down the following statement on your answer sheet: "I cert- ify that I have carefully read the exam rules listed on Page 1. If I violate a- ny of the rules, I agree to be penalized accordingly." 2. (30 points; 10 points each) Answer three in the following four subproblems. You may choose any three subproblem by yourselves, but you need to indicate the subproblem numbers (a, b, c, or d) clearly. If you answer all subproblems, only the first three will be graded. (a) Use your own words to explain the concept of optimality gap. Suppose that we are solving an IP. To define an optimality gap, when should we use the objective value of an optimal solution as a benchmark, and when should we use that of the linear relaxation? Limit your answer to be no more than 200 words. (b) Use your own words to give one example for linear programming duality to be useful. Your example may be for problem solving in practice, algorithm dev- elopment, of theoretical analysis. You should clearly describe the issue, what is difficulty without duality, and how duality helps. Limit your answ- er to be no more than 200 words. (c) Use your own words to give one numerical example showing that the choice of step sizes is critical for the performance of gradient descent. Do not use examples that already appeared in this course. You should specify a functi- on, an initial solution, and two ways of determing the step sizes. You sho- uld then show that gradient descent performs badly with the first step of step sizes but well with the second. Limit your answer to be no more than 200 words. (d) Use your own words to give one example for network flow models to be useful . Your example may be for problem solving in practice, algorithm developme- nt, or theoretical analysis. Limit your answer to be no more than 200 words. . 3. (15 points; 5 points each) Consider the following nonlinear function f(q,c) = p(q-q^2_ - cq - kc^2. (a) Find the gradient and Hessian for f(q,c). (b) Find a condition so that f(q,c) is concave if and only if the condition ho- lds. (c) Find (q^*, c^*) such that f(q^*,c^*) \geq f(q,c) for all (q,c) \in R^2 by assuming that the condition you find in Part (b) holds. 4. (20 points; 5 points each) When using the simplex method to solve a minimiz- ation LP, you get a tableau c -2 0 0 0 | 10 ------------------+---- -1 a^1 1 0 0 | 4 a^2 -1 0 1 0 | 1 a^3 1 0 0 1 | b at the end of an iteration. Give conditions on the unknowns c, b, a^1, a^2, and a^3 to make the following statements true. Provide brief explanations for your answer for each subproblem. Limit your explanation to be no more than fifty wo- rds. For each subproblem, you may get full points only if answer is correct and complete (i.e., covers all cases for the statement to be true). (a) The current basis is optimal. (B) The KP is unbounded. (c) The current basis is suboptimal, in one iteration we cannot conclude that the LP is unbounded, and we will improve the solution by doing the next si- mplex iteration. (d) The matrix A^{-1}_BA_N is totally unimodular, where B and N are the set of basic and nonbasic variables and A is the coefficient matrix of the origin- al LP. 5. (20 points; 5 points each) An electricity company is responsible for provid- ing electricity to consumers in areas 1 and 2. For area i \in {1,2}, the daily electricity demand D_i is random. According to past experience, et S be the set of all possible values of d, the company believes that p_{id} = Pr(D_i = d) is the probability for the daily demand to be d, i \in {1,2}, d \in S. The company wants to determine the capacity of electricity generation K_i in area i. In ei- ther area, if in a day the demand is larger than the capacity, it is said that shortage occurs. In area i, the cost of maintaining capacity at the level of K_i is estimated to be c_iK_i^2, where c_i is a given constant. In each area, the probability of shortage cannot be greater than \alpha. This is called the reliability requirement. (a) Suppose that the electricity generated in an area cannot be used in the ot- her area. Formulate a linear IP that minimizes the total cost to achieve a- ll requirements. (b) Relax the integer constraints, if any, in the program you formulate in Part (a). In other words, let all integer variables be fractional. Is the resul- ting program a convex program? Briefly explain why. (c) Suppose that the electricity generated in area i can be "shipped" to area j to be used there. Each unit of shipping from area i to area j requires t_{ij} as the shipping cost. However, for every unit shipped from area i, area j only receive \beta_{ij} unit, where \beta_{ij} \in [0,1), due to so- me natural loss during the shipping process. Note that t_{ij} and t_{ji} m- ay be different, and \beta_{ij} and \beta_{ji} may be different. Formulate a linear IP that minimizes the total cost to achieve the reliability requi- rement. (d) Generaluize your formulation in Part (c) to n areas for n > 2. 6. (20 points; 5 points each) An elevator company in a city is responsible for providing regular maintenance to its customers by sending engineers from its f- acility. Let I be the set of customers. A contract has been signed with custom- er i for the company to provide h_I times of maintenance in a year, where h_i \in {2,3,4}/ A year is divided into twelve months, and the multiple times of m- aintenance must be allocated to the twelve months somewhat uniformly. More pre- cisely: - If h_i = 2, there must be exactly one maintenance in months 1 to 6 and anoth- er one in months 7 to 12. - If h_i = 3, there myst be exactly one maintenance in months 1 to 4, one in m- onths 5 to 8, and the last one in months 9 to 12. - If h_i = 4, there must be exactly one maintenance in months 1 to 3, one in m- onths 4 to 6, one in months 7 to 9, and the last one in months 10 to 12. The company's current capacity is limited and may provide maintenance services to at most K companies in a month. Let I_j be the set of customers whose h_i = j, j \in {2,3,4}. The company now wants to make a schedule for its annual main- tenance for all customers. (a) Formulate a set of constraints to ensure that the schedule satisfies the c- ontract requirement described above. Note. For the following subproblems, you do not need to replicate the cons- traints you formulate in Part (a) again. (b) If in a month the company's current capacity is lower than the number of s- cheduled maintenance services, we say the month is of insufficient capacity . Formulate a libear IP to minimize the number of months with insufficient capacity. (c) Suppose that the company may expand its capacity by 1 (i.e., making K beco- me K+1) by spending B dollars. That additional unit of capacity can be used in all months (just like the original units of capacity). THe company may add as many units as it wants as long as it pays. Formulate a linear IP to minimize the amount of spending to make the (expanded) capacity enough for all months. (d) Suppose that the contracts become stricter so that two maintenance services for a customer must be separated by at least two months. For examples, hav- ing services in months 1 and 4 is allowed, but having services in months 2 and 4 is not allowed. Formulate a set of constraints to make the schedule satisfy the new requirement. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.115.36 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1624600981.A.4FE.html ※ 編輯: unmolk (114.24.173.199 臺灣), 06/27/2021 07:40:19