→ yrclamb:我打字是有這麼快嗎.. = = 01/18 22:06
課程名稱︰作業研究一
課程性質︰工管系科管組大二必修
課程教師︰蔣明晃老師
開課學院：管理學院
開課系所︰工管系
考試日期（年月日）︰2008/01/14
考試時限（分鐘）：220 分鐘
是否需發放獎勵金：是的 感謝～
（如未明確表示，則不予發放）
試題 :
I. Multiple choice questions: (30 points)
1. If the feasible region gets larger due to a change in one of the
constraints, the optimal value of the objective function
a. Must increase or remain the same for a maximization problem.
b. Must decrease or remain the same for a maximization problem.
c. Must increase or remain the same for a minimization problem.
d. Cannot change
2. A transshipment problem has 2 sources, 3 transshipment points, and 5 final
destinations. How many constraints would this linear program have?
a. 7
b. 10
c. 21
d. 30
3. The shadow price for a constraint
a. Is the value of an additional unit of that resource.
b. Is not equal to zero if there is no slack for that constraint.
c. Is found from the value in the excess (surplus) variable column
corresponding to that constraint at row 0.
d. All of the above are correct
4. A change in the objective function coefficient for a basic variable within
the allowable increase or decrease range will affect
a. The value of row 0 of all the nonbasic variables.
b. The value of row 0 of all the basic variables.
c. Only the value of row 0 of that variable.
d. The values of objective function coefficient of other basic variables.
5. If the total demand is greater than the total capacity in a transportation
problem, then
a. The optimal solution will be degenerate.
b. A dummy source must be added.
c. A dummy destination must be added.
d. Both a dummy source and a dummy destination must be added.
6. In solving a facility location problem in which there are two possible
locations being considered, the transportation method may be used. In doing
this,
a. Two rows (sources) would be added to the existing rows and the enlarged
problem would be solved.
b. Two separate transportation problems would be solved.
c. Costs of zero would be used for each of the new facilities.
d. The transportation simplex method must be used to evaluate the empty
cells.
7. The critical path is the
a. Shortest path in a network
b. Longest path in a network
c. Path with the largest variance
d. None of the above.
8. If a project is to be crashed at the minimum possible additional cost, then
the first activity to be crashed must be
a. The one with the lowest cost
b. The one with the longest activity time
c. The one with the shortest activity time.
d. The one on the critical path.
9. For a nondegenerate optimal solution to a Max model, if the ovjective
function coefficient c1 increases be (exactly) the allowable increase
a. The objective function value may change
b. The previous optimal solution remains optimal.
c. There will be a new optimal solution with a larger optimal value of x1
d. All of the above
10.Consider any primal problem (P) and its dual (D)
a. The objective function values in (P) and (D) will be the same.
b. (P) will have an optimal solution if and only if (D) does also.
c. Both (P) and (D) cannot be infeasible
d. All of the above
11.If xk and xm are 0-1 variables (the value 1 meaning select) for project k
and m, respectively, the constraint xk + xm ≦ 0 implies that
a. k cannot be selected unless m is selected.
b. m cannot be selected unless k is selected.
c. k must be selected if m is selected.
d. None of the above.
12.In solving a Max Integer LP a lower bound for the objective function value
of the original problem can always be found by
a. Solving the LP relaxation of the Integer LP and using the objective
function value of the LP.
b. Finding a feasible solution to the Integer LP by any available means and
evaluating the objective function value
c. Solving the LP relaxation and then rounding fractions < 0.5 down, those
≧ 0.5 up, and evaluating the objective function value at this point.
d. None of the above.
13.Which of the following is a condition that assures that there is an optimal
integer solution t a capacitated transshipment problem?
a. The right-hand side of all flow equation be integer.
b. The arc capacities be integer
c. Either a or b
d. Both a and b
14.The latest finish time for an activity entering node H
a. Equals the max of the latest start times for all activities leaving node
H.
b. Depends on the latest finish time for the project.
c. Equals the latest start time minus the activity time for the same
activity.
d. None of the above.
15.Fundamental ideas in the LP network crashing models are
a. Activity time equals normal time + crash time
b. Earliest start time for an activity leaving a node equals the Max of the
earliest finish times for activities leaving that node.
c. Earliest finish time equals latest finish time minus activity time
d. None of the above
II. Formulations and Calculations: (70 points)
1. A firm produces self-assembly bookshelf kits in two models A and B.
production of kits is limited by the availability of raw materials (high
quality board) and machine processing time. Each unit of A requires 3 m^2
of board and each unit of B requires 4 m^2 of board. The firm can obtain up
to 1700 m^2 of board each week from its suppliers. Each unit of A needs 12
minutes of machine time and each unit of B needs 30 minutes of machine time.
Each week a total of 160 machine hours is available. If the profit on each
A unit is $2 and on each B unit is $4. Suppose we know that model A and B
are produced certain positive amount at the optimal solution. Answer the
following questions independently.
a. Suppose we can buy extra board from a second timber merchant, how much
per square meter are we prepared to pay for it? (7 points)
b. Suppose that we can obtain extra machine time by working overtime. If
this costs $7 per hour extra is it worth it? (3 points)
c. Suppose that the profit on each A unit is $P1 and on each B unit is $P2.
For what possible values of $P1 and $P2 is the solution we have obtained
optimal? (4 points)
d. Suppose a third type of kit (C), can be made. Suppose it uses 4 m^2 of
board and needs 20 minutes of machine time. If the profit on each unit
if $P, when should we make it? (4 points)
e. Suppose that during a period of economic recession the sales team report
that the market will not stand more than 450 sales of kits each week.
How does this affect the production schedule? (6 points)
!
2. Find the optimal solution to the MCNFP in Figure 1 using the bfs in Figure 2
as a starting basis. (10 points)
(5) (0, 6)
╭─╮ $1 ╭─╮(0)
│１├──→│２│
╰┬╯(1, 8)╰┬╯ (Lij, Uij)
(0, 3) $4│ $1 ↗ │(0, 4) $2
↓ ╱ ↓
╭─╮╱ ╭─╮
│３├──→│４│
(3)╰─╯(1, 5)╰─╯(-8)
$6
Figure 1
!
╭─╮ 2 ╭─╮
│ ├──→│ │
╰┬╯ ╰┬╯
3 虛 2 ↗ 虛 4
↓ ╱ ↓
╭─╮╱ ╭─╮
│ ├──→│ │
╰─╯ 4 ╰─╯
Figure 2 ╰w╯
3. PROTRAC Co. is deciding which of four salespeople to assign to each of four
midwestern sales districts. Each salesperson is apt to achieve a different
sales volume in each district. The estimates are shown in following table.
PROTRAC would like to maximize total sales volume. However, it is impossible
to assign B to district 1 or salesperson A to district 2 sice these
assignments would violate personnel rotation policies. PROTRAC would like to
maximize total sales volume of 4 districts. Formulate the problem and solve
it. (12 points)
┌───┬───────────────────┐
│ │ District │
│Sales-├────┬────┬────┬────┤
│person│ 1 │ 2 │ 3 │ 4 │
├───┼────┼────┼────┼────┤
│ A │ 65 │ 73 │ 55 │ 58 │
├───┼────┼────┼────┼────┤
│ B │ 90 │ 67 │ 87 │ 75 │
├───┼────┼────┼────┼────┤
│ C │ 106 │ 86 │ 96 │ 89 │
├───┼────┼────┼────┼────┤
│ D │ 84 │ 69 │ 79 │ 77 │
└───┴────┴────┴────┴────┘
4. Alpha Airline wishes to schedule no more than one flight out of Chicago to
each of the following cities: Columbus, Denver, Los Angles, and New York.
The available departure slots are 8 a.m., 10 a.m., and 12 noon. Alpha leases
the airplanes at the cost of $5,000 before and including 10 a.m. and $3,000
afoter 10 a.m. and is able to lease at most two per departure slot. Also, if
a flight leaves for New York in a time slot, there must be a flight leaving
for Los Angles in the same time slot. The expected profit contribution
before rental costs per flight is shown in the following table. Formulate a
model for a profit-maximizing schedule. Define your decision variables
carefully. (12 points)
┌───────┬──────────────┐
│ │ Time Slot │
│ ├────┬────┬────┤
│ │ 8 │ 10 │ 12 │
├───────┼────┼────┼────┤
│Columbus │ 10 │ 6 │ 6 │
├───────┼────┼────┼────┤
│Denver │ 9 │ 10 │ 9 │
├───────┼────┼────┼────┤
│Los Angeles │ 14 │ 11 │ 10 │
├───────┼────┼────┼────┤
│New York │ 18 │ 15 │ 10 │
└───────┴────┴────┴────┘
5. A type of machine always is needed for an auto repair shop during the next
N years. A new machine costs p. The costs of operating for one year a
machine which is of age i at the start of the year is c(i). A machine can
be trade-in for a new one. The trade-in value received is t(i) when a
machine if of age i at the start of a year and traded for a new machine at
the start of the year. At the end of year N, we received a salvage value
s(i) for a machine that has just turned age i. (12 points)
a. Formulate the appropriate dynamic programming recursion that will
minimize the total cost for the next N years. Write down the recurrence
relation and boundary condition.
b. Suppose any machine reaching age M (M is given) must be replaced and,
further more, that one can trade-in a used machine on a machine of any
age between 0 (new) and M-1. The cost of replacing an i-year-old machine
by one of age j is u(i, j), where u(i, j) = p - t(i) and u(i, i) = 0.
Reformulate the appropriate dynamic programming recursion that will
minimize the total cost for the next N years. Write down the recurrence
relation and boundary condition.
c. Based on b, but all of the data are year-dependent; i.e., that costs in
year k different from those in year j for j ≠ k. Let uk(i, j) is the
cost of trading a i-year-old machine by one of age j at the start of
year k. Reformulate the appropriate dynamic programming recursion that
will minimize the total cost for the next N years. Write down the
recurrence relation and boundary condition.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.31.168