課程名稱︰管理科學模式
課程性質︰工管系企管組必修
課程教師︰黃崇興
開課系所︰工管系
考試時間︰95/04/25
試題 :
§ IP in our exam problems means integer programming as our textbook.
§ LP means linear programming.
§ All marks or symbols aapeared on the network graphs are the same as our
textbook.
1. Please specify at least two reasons or occasions for which we need to
include integer variables in LP formulation for managerial problems.
2. Solve the following IP problem graphically.
a.
MAX z = 5 x1 + x2
s.t -x1 + 2 x2 ≦ 4
x1 - x2 ≦ 1
4 x1 + x2 ≦ 12
x1 , x2 ≧ 0 ,and integer
draw the feasible region and find the optimal solution.
b.
MAX z = 5 x1 + x2
s.t -x1 + 2 x2 ≦ 4
x1 - x2 ≦ 1
4 x1 + x2 ≦ 12
x1 , x2 ≧ 0
draw the feasible region and solve for the optimal solution of this LP.
Then only try to round the LP optimal solution to its nearest integer
solutions. Can you get feasible solution,or even the same integer solution
as in part (a) ?
3. There are six cities (city 1~6) in Taotuan Country. The country must
determine where to build fire stations. The country wants to build the
minimum number of the stations needed,but to sure that at least one fire
station is "wihtin 15 minutes"(driving time)for each city. The time (in
minutes)required to drive between the cities in Taoyuan Country are shown
in Table-1. Formulate an IP model that can determine Taoyuan how many fire
stations should be build and where they should be located.(only
formulation,no solution is needed)
Table-1 drivung time between cities
From\to City1 City2 City3 City4 City5 City6
City1 0 10 20 30 30 20
City2 10 0 25 35 20 10
City3 20 25 0 15 30 20
City4 30 35 15 0 15 25
City5 30 20 30 15 0 14
City6 20 10 20 25 14 0
4. Yu-Long auto is considering manufacturing three types of autos:compact,
midsize and large. The resource required for,and the profits yielded by,
each type of car are shown in Table-2. Country,6000 tons of steel and
60000 hours of labor are available. For production of a type of car to be
economically feasible,if they decide to produce,at least 1000 cars of each
type must be produced. Formulate an IP to maximize the profit.
Table-2 Yu-Long Production Data
Compact Midsize Large
Steel required 1.5 tons 3 tons 5 tons
Labor required 30 hrs 25 hrs 40 hrs
Profit $2000 $3000 $4000
5. Clock Accounting Office has three auditors. Each can work as many as 160
hours during the next month,during which time three must be completed.
Project1 will take 130 hours;project2,140 hours;project3,160 hours. The
amount per hour that can be billed for assigning each auditor to each
project is given in Table-3
a.
Formulate this problem as a transportation problem to maximize total
billings the next month using either regular LP way or graphic way.
b.
Can this be defined as an assignment problem ? If yes,do;If no,why not ?
Table-3 Auditors' contribution to each individual project
Project1 Project2 Project3
Auditor1 $120 $150 $190
Auditor2 $140 $130 $120
Auditor3 $160 $140 $150
6. Please use the network below to construct the shortest paths from node1
to all other node
120 160
2 ───────5 ─────── 7
│ ∣ / ∣
∣ ∣ / ∣
80∣ 50∣ / ∣
∣ ∣ / ∣
∣ 140 ∣ / ∣
1 ────── 4 210 / ∣
∣ ∣ / ∣190
∣ ∣ / ∣
∣ ∣ / ∣
∣ 40∣ / ∣
∣ ∣ / ∣
∣ ∣ / ∣
∣ ∣ / ∣
130└────── 3 / │
│ │
└──────── 6
50
7. Find the minimum spanning tree from the network shown below.
260 140
┌── 2 ──── 6 ───┐210
│ \ / │ │
│ 110 \ 170/ │130 7
│ \ / │ ∕│
│ 3 ── 5──/ │
1 │ 90 \ │
│ 70│ 120 \ │160
│ │ \ │
190└───── 4──── 8─┘
230
8. Find the maximum capacity the traffic which may flow through the network
from node1 and exit from node8
6 0
2 ────— 5
0 ╱ │3 ╱ ╲8
╱ │ ╱2 ╲
╱ │ ╱ ╲
10 ╱ 5│ 6╱ ╲0
╱7 1 │╱ 0 4 0╲
1───── 3 ────— 6 ──── 8
╲ 5 ╱∣2 0╱
8 ╲ ╱2 ∣갠 ╱
╲ ╱ ∣ ╱
╲0 4╱ 6∣ﴠ╱
╲ ╱ 0 ∣╱9
4 ───── 7
5
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.245.204
※ 編輯: ilovecloud 來自: 140.112.245.204 (05/02 20:39)
※ 編輯: ilovecloud 來自: 140.112.245.204 (05/02 20:39)