课程名称︰作业研究
课程性质︰资管系选修
课程教师︰孔令杰
开课学院：管理学院
开课系所︰资管系
考试日期（年月日）︰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