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