課程名稱︰作業研究一
課程性質︰工管系科管組大二必修
課程教師︰蔣明晃老師
開課學院：管理學院
開課系所︰工管系
考試日期（年月日）︰2007/11/05
考試時限（分鐘）：180 分鐘
是否需發放獎勵金：是的 感謝～
（如未明確表示，則不予發放）
試題 :
1. Consider the following problem:
Minimize z = 3x1 + 4x2
Subject to 6x1 + 1x2 ≧ 120
4x1 + 4x2 ≧ 320
3x1 + 5x2 ≧ 300
x1, x2 ≧ 0
Answer the following questions by using graphical method:
(1) Determine and graph the optimal z-value as a function of objective
function coefficient c1.
(Note: c1 is the objective function coefficeint of variable x1) (9pts)
(2) Determine and graph the optimal z-value as a function of b2.
(Note: b2 is the rhs of the 2nd constraint) (9pts)
(3) If the rhs of the 3rd constraint is increased by Δ (a small amount),
what is the impact on the optimal value of z? (4pts)
2. Each of the following tableaus represents the end of an iteration to a
maximization problem. Select one or more of the following conditions that
best describe the results indicated by each tableau, and then answer any
question in parentheses. (18pts) (Note: M is a large number, si is a slack
variable, ei is a excess variable, ai is a artificial variable)
(1) Improvement in the value of the objective function is still possible.
(Identify the variable should be brought into solution and the variable
should be removed. And determine the total improvement in the objective
function)
(2) The original problem in infeasible (Why?)
(3) The solution is degenerate. (Which variable causes degenerate?)
(4) The solution represented by the tableau is not a basic feasible
solution. (Why?)
(5) The unique solution is obtained. (Why?)
(6) One of the optimal solutions has been obtained, but an alternative
optimum exists. (Find the alternative solution)
(7) The optimal solution to the original problem is unbounded. (Why?)
Tableau 1
┌─┬──┬──┬──┬──┬──┐
│z │ x1 │ x2 │ s1 │ s2 │ rhs│
├─┼──┼──┼──┼──┼──┤
│1 │ 0 │ 0 │ 0 │ 3 │ 6 │
│0 │17/2│ 0 │ 1 │-7/2│ 28 │
│0 │-1/2│ 1 │ 0 │ 1/2│ 1 │
└─┴──┴──┴──┴──┴──┘
Tableau 2
┌─┬──┬───┬──┬──┬──┐
│z │ x1 │ x2 │ s1 │ s2 │ rhs│
├─┼──┼───┼──┼──┼──┤
│1 │ 0 │-1/12 │ 0 │ 1/3│ 0 │
│0 │ 0 │-1/12 │ 1 │ 1/3│ 0 │
│0 │ 1 │ -1/3 │ 0 │ 1/3│ 0 │
└─┴──┴───┴──┴──┴──┘
Tableau 3
┌─┬──┬──┬──┬──┬──┬──┐
│z │ x1 │ x2 │ s1 │ s2 │ s3 │ rhs│
├─┼──┼──┼──┼──┼──┼──┤
│1 │ 0 │ 0 │ 7/4│-1/2│ 0 │ 16 │
│0 │ 0 │ 1 │ 1 │ -1 │ 0 │ 2 │
│0 │ 1 │ 0 │-1/4│ 1/2│ 0 │ 2 │
│0 │ 0 │ 0 │-3/4│ 1/2│ 1 │ 0 │
└─┴──┴──┴──┴──┴──┴──┘
Tableau 4
┌─┬──┬──┬──┬──┬──┐
│z │ x1 │ x2 │ s1 │ a2 │ rhs│
├─┼──┼──┼──┼──┼──┤
│1 │ 0 │ 0 │ 2 │ M-1│ 5 │
│0 │ 1 │ 0 │ 1 │ -1 │ 1 │
│0 │ 0 │ 1 │ -1 │ 2 │ 2 │
└─┴──┴──┴──┴──┴──┘
Tableau 5
┌─┬──┬────┬──┬──┬────┬────┐
│z │ x1 │ x2 │ e1 │ a1 │ a2 │ rhs │
├─┼──┼────┼──┼──┼────┼────┤
│1 │ 0 │(M-6)/3 │ M │ 0 │(5M-3)/3│-4-10M/3│
│0 │ 0 │ -1/3 │ -1 │ 1 │ -2/3 │ 10/3 │
│0 │ 1 │ 2/3 │ 0 │ 0 │ 1/3 │ 4/3 │
└─┴──┴────┴──┴──┴────┴────┘
Tableau 6
┌─┬──┬──┬──┬──┬──┬──┬──┐
│z │ x1 │ x2 │ x3 │ s1 │ s2 │ s3 │ rhs│
├─┼──┼──┼──┼──┼──┼──┼──┤
│1 │ 0 │ 5 │ 0 │ 0 │ 10 │ 10 │ 380│
│0 │ 0 │ -2 │ 0 │ 1 │ 2 │ -8 │ 44│
│0 │ 0 │ -2 │ 1 │ 0 │ 2 │ -4 │ 28│
│0 │ 1 │1.25│ 0 │ 0 │-0.5│1.5 │ -3│
└─┴──┴──┴──┴──┴──┴──┴──┘
3. For the following LP, s1 and x2 are current basic variables of an iteration
to a maximization problem. Use this information to check whether the
current iteration is in the optimal stage. If not, use revised simplex to
determine the optimal basis and corresponding optimal solution. (16pts)
Maximize z = 2x1 + 4x2
Subject to
3x1 + 4x2 ≦ 1700
2x1 + 5x2 ≦ 1600
x1, x2 ≧ 0
4. A farmer owner in Des Moines, Iowa, is interested in determining how to
divide the farmland among 4 different types of crops. The farmer owns 2
farms in separate locations and has decided to plant the following 4 types
of crops in these farms: corn, wheat, bean, and cotton. The first farm
consists of 1,450 acres of land, while the second farm consists of 850
acres of land. Any of the four crops may be planted on either farm.
However, after survey of the land, based on the characteristics of the
farmlands. Table 1 shows the maximum acerage restrictions the farmer has
placed for each crop. The profit per acre for each crop is estimated as
follows: Corn, $500; Wheat, $400; Bean, $300; Cotton, $350.
In determining the optimal cultivation of land the farmer has to account
for the cost of fertilizer estimated for each acre of land. Due to
different terrain and soil, the two farms have different costs of
fertilizers per acre. The cost of fertilizer per acre at Farm 1 is $100,
and the cost of fertilizer per acre at Farm 2 is $70. Seasonal demand
(acres' worth) for the 4 crops are estimated at least 450 (Corn),
550 (Wheat), 400 (Bean), and 600 (Cotton), respectively. The farmer has a
storage facility that can store 100 acres' worth of the excess supply of
different types of crops. In addition, the farm owner wants to ensure that
total wheat and bean cultivation must be proportionally equal to the
maximum acerage restriction of both farms. The farmer's objective is to
determine how much of each crop to plant on each farm in order to maximize
profit and satisfy seasonal demand.
Formulate a linear programming model. (12pts)
Table 1
┌───┬───────────────────┐
│ │ Crop │
│ ├────┬────┬────┬────┤
│ Farm │ Corn │ Wheat │ Bean │ Cotton │
├───┼────┼────┼────┼────┤
│ 1 │ 550 │ 450 │ 350 │ 400 │
├───┼────┼────┼────┼────┤
│ 2 │ 250 │ 300 │ 200 │ 350 │
└───┴────┴────┴────┴────┘
5. The Growall Fertilizer Company produces 3 types of fertilizer -- Supergro,
Dynaplant, and Soilsaver. The company has the capacity to produce a
maximum of 2,000 tons of fertilizer in a week. It costs $800 to produce a
ton of Supergro, $1500 for Dynaplant, and $500 for Soilsaver. The
production process requires 10 hours of labor for a ton of Supergro, 12
hours of labor for a ton of Dynaplant, and 18 hours of labor for a ton of
Soilsaver. The company has 800 hours of normal production labor available
each week. Each week the company can expect a demand for 800 tons of
Supergro, 900 tons of Dynaplant and 1,100 tons of Soilsaver. The company
has established the following goals, in order of their priority:
(1) The company doesn't want to spend over $20,000 per week on production,
if possible.
(2) The company would like to limit overtime to 100 hours per week.
(3) The company wants to meet demand for all 3 fertilizers; however, it is
twice as important to meet the demand for Supergro as it is to meet
the demand for Dynaplant, and it is twice as important to meet the
demand for Dynaplant as it is to meet the demand for Soilsaver.
(4) It is desirable to avoid producing under capacity, if possible.
(5) Because of union agreements, the company wants to avoid
underutilization of labor.
Formulate a goal programming model to determine the number of tons of each
brand of fertilizer to produce to satisfy the goals. (14pts)
6. (18pts)
The King (TK) makes three lines of tires. Its four-ply biased tires
produces $7 in contribution per tire, its fiberglass belted line $4 a tire,
and its radials $8 a tire. Each type of tire passes through three
manufacturing processes. The three process centers have the following hours
of available production time per day:
┌─────┬───┐
│ Process │ Hours│
├─────┼───┤
│ Molding │ 15 │
│ Curing │ 9 │
│ Assembly │ 10 │
└─────┴───┘
The time required in each process to produce one hundred tires of each line
is
┌─────┬──────────────┐
│ │ Hours Per 100 Units │
├─────┼────┬────┬────┤
│ Tire │ Molding│ Curing │Assembly│
├─────┼────┼────┼────┤
│Four-ply │ 2 │ 3 │ 2 │
├─────┼────┼────┼────┤
│Fiberglass│ 2 │ 2 │ 1 │
├─────┼────┼────┼────┤
│Radial │ 2 │ 1 │ 3 │
└─────┴────┴────┴────┘
The marketing department believes that there is not enough demand to
justify production of more than 200 fiberglass belted tires per day.
Further, it recommends that at least 2 four-ply biased tires be produced
for each fiberglass belted tire made.
Model Formulation:
Decision Variables:
X1 = number of four-ply tires produced (in hundreds).
X2 = number of fiberglass tires produced (in hundreds).
X3 = number of radial tires produced (in hundreds).
Objective Function:
max 700 X1 + 400 X2 + 800 X3 (Maximize total profit)
Constraints:
2 X1 + 2 X2 + 2 X3 ≦ 15 (Molding process)
3 X1 + 2 X2 + X3 ≦ 9 (Curing process)
2 X1 + X2 + 3 X3 ≦ 10 (Assembly process)
X2 ≦ 2 (max fiberglass demand)
X1 - 2 X2 ≧ 0 (four-ply fiberglass ratio)
X1, X2, X3 ≧ 0 (Non-negativity)
The following Excel Solver output shows the model, the answer report, and
the sensitivity report for the problem of determining an optimal production
schedule. Use only these outputs to provide the best answers you can give
to the questions that follow.
Spreadsheet Solution:
A B C D E F G
1TireKing.xls Tire King Problem
2OPIM 621: Management Science
3Self Study #2
4 Four-ply Fiberglass Radial Max Total
5Unit contribution ($) 700 400 800 Contribution
6Production Quantity('00) 1.789474 0.8947368 1.842105 3,084
7
8 Hours used Hours avail
9Molding 2 2 2 9.1 <= 15
10Curing 3 2 1 9 <= 9
11Assembly 2 1 3 10 <= 10
12
13Fiberglass limit 1 0.9 <= 2
14Four-ply/fiber ratio 1 -2 0 >= 0
Decision Variables: X1, X2, X3 are in block B6:D6
Objective Function: Maximum total contribution in cell G6 is
= sumproduct(B6:D6, B5:D5)
Constraints: Left-hand-sides of available production time constraints are in
block E9:E11, e.g. cell E10 contains =sumproduct($B$6:$D$6, B10:D10).
Left-hand-sides of marketing constraints are in cells E13 and E14.
Sensitivity Report:
Changing Cells
#1 #2 #3
───────────────────────────────────────
Final Reduced Obj. Allow. Allow.
Cell Name Value Cost Coeff. Inc. Dec.
───────────────────────────────────────
$B$6 Production Quantity('00) Four-ply 1.78947 0 700 20 233.333
$C$6 Production Quantity('00) Fiberglass 0.89474 0 400 4600 14.286
$D$6 Production Quantity('00) Radial 1.84211 0 800 280 100
───────────────────────────────────────
#1 -- Objective Coefficient
#2 -- Allowable Increase
#3 -- Allowable Decrease
Constraints
───────────────────────────────────────
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H.Side Increase Decrease
───────────────────────────────────────
$E$9 Molding Hours used 9.1 0.0 15 1E+30 5.947
$E$10 Curing Hours used 9 73.68 9 7 5.667
$E$11 Assembly Hours used 10 242.11 10 11.3 4.375
$E$13 Fiber Production 0.9 0.0 2 1E+30 1.105
$E$14 Ratio LHS 0 -5.26 0 2.429 3
───────────────────────────────────────
Questions:
Answer each question independently of the others. You must justify your
answers with clear, cogent explanations. If you feel there is insufficient
information to answer a question, you must indicate why the question cannot be
answered.
a) Approximately, how many tires of each type should be produced each day?
How much contribution per day is made from this production strategy?
b) One of TK's junior accountants has just discovered that the contribution
per four-ply biased tire is really $5 rather than $7. What is your best
estimate of how daily contribution will change?
c) Rubber prices have dropped, and consequently there has been a 5% increase
in contribution for each class of tire. What is TK's optimal daily
production schedule now? How much profit is TK making per day?
d) Due to a non-recurring work slowdown, 3 hours of curing time have been
lost today. How will this affect TK's profits today, assuming TK has been
able to adjust its production to make the new optimal prodcut mix?
e) TK is considering the acquisition of 12 additional hours of assembly
production time (per day) at a cost of $3000 per day. This is an
all-or-nothing proposition. Should they do this? Why or why not?
f) Answer (e) if the cost of the additional 12 hours is $2,700 per day.
g) Suppose that it is required that TK make at least 100 Radial tires each
day. Will the optimal solution change? Why or why not?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.112.185