課程名稱︰作業研究
課程性質︰資管系選修
課程教師︰孔令傑
開課學院：管理學院
開課系所︰資管系
考試日期（年月日）︰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