課程名稱︰作業研究
課程性質︰資管系選修
課程教師︰孔令傑
開課學院：管理學院
開課系所︰資管系
考試日期（年月日）︰109/06/04
考試時限（分鐘）：180
試題 :
1. (5 points) Write down the following statement on your answer sheet: "I certify that I have care-
fully read the exam rules listed on Page 1. If I violate any of the rules, I agree to be penalized
accordingly."
2. (10 points) Prove or disprove the following statements: "When using the simplex method with the
smallest index rule to solve a maximization linear program, it is guaranteed to have a positive in-
crement in the objective value in each iteration."
Hint. To prove this statement, clearly demonstrate why the guaranteed thing must happen given the
specified condtion; to disprove it, provide one concrete exam and show step-by-step when the guara-
nteed thing does not happen.
3. (15 points) Please solve the following problems regarding the dual simplex method.
(a) (5 points) Use your own words to explain how the branch-and-bound algorithm for solbing a gene-
ral integer program may be accelerated by the dual simplex method.
(b) (10 points) Does the dual simplex method work when two new constraints are simultaneously added
into a linear program? If yes, explain the detailed process of checking feasibility and fixing inf-
easibility. If no, explain why.
4. (15 points) Please solve the following problems regarding nonlinear programming.
(a) (5 points) Consider the following nonlinear porgram
max f + n - β(x-a1)^2 - w(x-a0)^2
s.t. x <= 1
x >= -1.
where f, n, β, w, a0, and a1 are parameters and x is the only decision variable. It is known that
n > 4β, β> 0, w > 0, -1<a0<1, -1<a1<1, and f is unrestricted in sign. Let the optimal solution of
this nonlinear program be x*. Prove that x* = (wa0+βa1)/(w+β).
(b) (10 points) Continue from the previous part and consider the following nonlinear program
max (p-c)(m-(a1-x*)^2-p) - f
s.t. f + n - β(x*-a1)^2 - w(x*-a0)^2 >= 0
p >= 0.
where c, m, n, β, w, a1, and a0 are parameters and p and f are the only decision variables. It is
known that c >= 0, m > 4, and the parameter values of n, β, w, a1, and a0 are identical to those
in Part (a). Let the optimal solution of this nonlinear program be (p*, f*), analytically solve th-
is program by finding analytical expressions for p* and f*. You will not get full points if you do
not write down your derivations, have your answer containing the symbol x*, or fail to show that
your proposed answers are indeed optimal.
5. (25 points) A company is seliing a product to a group of n_B buyers in the next m periods. Buyer
i requests d_{ik} units in period k, k=1,...,m, and is willing to pay p_i dollars for each unit pu-
rchased. If the company wants to serve buyer i, it must satisfy all the demands requested by buyer
i. In short, partial fulfillment is not allowed. The company wants to choose some buyers to fulfill
their demands to maximize its total revenue. All sales quantities are allowed to be fractional.
(a) (5 points) Suppose that in period k the company has h_k units available. Formulate a (mixed)
integer linear program that maximize the total revenue.
(b) (10 points) Ignore Part (a). Suppose that the company does not have its own supply. Instead,
the company is a platform allowing n_s sellers to provide their supplies. Seller j may offer s_{jk}
units in period k and is willing to sell the product if and only if the per-unit price is no less
than q_j. Single sourcing is required, i.e., a buyer's demands must be completely satisfied by the
supplies provided by a single seller. A seller, however, may serve multiple buyers as long as it
has enough supplies. Formulate a (mixed) integer linear program that maximize the total revenue.
(c) (10 points) Continue from Part (b). Now, multiple sourcing is allowed, i.e., a buyer's demands
may be satisfied by the supplies collected from multiple sellers. Formulate a (mixed) integer prog-
ram that maximize the totla revenue.
Hint. The total revenue, as always, has nothing to do with any cost. Therefore, in your answer for
Parts (b) and (c), q_j should not appear in the objective function.
Example. To help you understand this problem, here is a numerical example. Let n_B = 3, m = 4, p =
(7,10,5), and
┌3 6 0 0┐
d = │7 7 9 9│
└0 6 8 0┘
In Part (a), let h = (8,15,16,9). The optimal solution is to serve buyer 2 and earn $320. Note that
once you serve buyer 2, you do not have enough supply to serve more buyers. In Part (b) annd (c),
let n_S = 2, q = (3,6), and
s = ┌8 8 8 0┐
└0 7 8 9┘
When multiple sourcing is allowed, the optimal solution is still to serve only buyer 2 and earn $32
0. All feasible ways to combine the supplies from the two sellers are equally good (as p2 > p1, p2
> p1, and q_j is not a part of revenue). When single sourcing is required, however, serving buyer 2
is no longer possible (because d_{23} > s_{13} and d_{23} > s_{23}). The optimal solution is to se-
rve buyer 3 by seller 1 and earn $70. Once seller 1 serves buyer 3, it does not have enough suppli-
es to serve buyer 1. Seller 2 also cannot serve buyer 1. Please note that, even though assigning
nuyer 1 to seller 1 and buyer 3 to seller 2 seems to be feasible (and earning more revenue) from
the perspective of capacity, this is infeasible because p_3 < q_2, i.e., buyer 3 will not accept
the price asked by seller 2.
6. (15 points) A manager hires a worker and specifies the working hours of the worker. The more the
working hours, the higher the probability that a project will be successful. More precisely, let a
>= 0 bte the number of working hours and q in {0,1} be the outcome of the project, where q = 1 mea-
ns success and q = 0 means failure, we have
Pr(q=1|a) = p(a) = 1 - Pr(q=0|a).
The manager will pay the worker w0 if the project fails or w1 if it is successful. The worker's ut-
ility is u(w) - a, where u(.) is strictly increasing and strictly concave. The offer must make the
worker's expected utility nonnegative so that the worker will accept the offer. Therefore, the man-
ager solves
max_{w0, w1, a} p(a)(1-w1) + (1-p(a))(-w0)
s.t. p(a)u(w1) + (1-p(a))u(w0) - a >= 0.
(a) (5 points) Determine whether the nonlinear program is a convex program.
(b) (10 points) Prove or disprove that w0 = w1 in an optimal solution.
7. (15 points) There is a core component in a system (e.g., the door ofan elevator, the engine of a
car, etc.) that should work for the following T days. The system may break down if the component's
damage value is too high, and a pre-breakdown replacement may decrease the probability of breakdown
. At the beginning of day t, t = T,T-1,...,2,1, you do a maintenance check and observe the current
damage value x_t. You may then determine whether to replace the component by paying or not, during
a day its damage value will increase by a random value Y, where p_y = Pr(Y=y) is the probability
for Y to be y. It is know that y in {0,1,...,N}. If by the end of the day the damage value reaches
(or exceeds) L, the system breaks down, and you must immediately pay R dollars to replace it. It is
natural that R > r, so whether to replace the component before the system breaks down is a reasona-
ble problem. You may assume that N < L and the damage value at the beginning of the day after a po-
st-breakdown replacement must be 0. The system will be disposed at the beginning of day 0 at no co-
st regardless of x0, its damage value. Let V_t(x) be the total expected cost from day t to day 0
when the damage value at the beginning of day t is x. Formulate a dynamic program that may optimize
the pre-breakdown decisions to minimize V_T(x).
Example. To help you understand this problem, here is a numerical example. Suppose that L=3, N=2,
p=(0.6,0.3,0.1), r=1, and R=5. If you observe that xt = 2, and you choose to replace the componet
by paying r=1 dollar, you know for sure that the system will not break down today. x_{t-1}, the da-
mage value at the beginning to tomorrow, will be 0, 1, and 2 with probability 60%, 30%, and 10%. If
you do not od the pre-breakdown replacement, the probability for the system to break down is 30% +
10% = 40%, so the expected post-breakdown cost is 5*0.4 = 2. If today is the last day (i.e., T = 1)
, you should replace the component at the beginning of today to minimize the total expected cost.
However, as the damage value at the beginning of tomorrow must be 0, the problem becomes more comp-
licated if today is not the last day (i.e., T > 1).