物流建模与仿真04
10/12/2011
Instructor: Jia Yongji s uc o : J o gj Office: 721, Xuri Building Phone: 62378372 Email: [email protected]
A. B. C. D. E. F.
Linear Programming Applications Transportation Problems Transshipment Problems Assignment Problems Shortest Route Maximal Flow
Steps in LP application:
1. Identify problem as solvable by linear programming. ◦ If the problem is about optimization (max, or min)? ◦ If all the inputs and their relationships with objective can be quantified as a linear model? 2. Formulate an LP model of the unstructured problem. 3. Solve the model
3
1
10/12/2011
Formulating linear programming models involves the following 6 steps:
1. 2. 3. 4. Define the decision variables. Determine the objective function. Identify the constraints. Determine appropriate values for parameters and determine whether an upper limit, lower limit, or equality is called for. 5. Use this information to build a model. 6. Validate the model.
4
Distribution System Design (0-1 variables with fixed charge)
The Martin-Beck Company operates a plant in St Louis with an annual capacity of 30,000 units. Product is shipped to regional distribution centers located in Boston, Atlanta, and Houston. Because of an anticipated increase in demand, Martin-Beck plans to increase capacity by constructing a new plant in one or g , , , y more of the following cities: Detroit, Toledo, Denver, and Kansas City. The estimated annual fixed cost and annual capacity for the four proposed plants are shown below:
Proposed Plant (i) Detroit Toledo Denver Kansa City Annual Fixed Cost $175,000 $300,000 $375,000 $500,000 Annual Capacity 10,000 20,000 30,000 40,000 Distribution Centers (j) Boston Atlanta Houston Annual Demand 30,000 20,000 20,000
5
The shipping cost per unit from each plant to each distribution centers shown below: Distribution Centers j Plant Site Detroit D i Toledo Plant i Denver Kansas City St. Louis Boston $5 $4 $9 $10 $8 Atlanta $2 $3 $7 $4 $4 Houston $3 $4 $5 $2 $3
6
2
10/12/2011
Plants ( i )
10
1 Detroit
5 2
Distribution Centers ( j )
1 Boston 3
20
2 Toledo
3 4
30
4
30
3 Denver D
9 7 5 10 4 2 8 4 3 3 Houston 2 Atlanta
20
40
4 Kansas City 5 St Louis
20
30
Demand in thousands
Distribution Routes Capacity in thousands Total Supplies (e.g., 130) > Total Demands (e.g., 70)
7
The complete model for Martin-Beck distribution system design problem is as follows: Min 5X11 +2 X12 +3 X13+ 4X21+3 X22+4X23+9 X31+7 X32+5 X33+10 X41+4 X42+2 X43+8 X51+4 X52+3 X53+175Y1 +300Y2 +375Y3+500Y4 s.t st X11+ X12 + X13 0, for all i and j; Y1 ,Y2, Y3, Y4= 0,1
Total Supplies (e.g., 130) > Total Demands (e.g., 70)
8
Round Tree Manor is a hotel that provides two types of rooms with three rental classes: Super Saver, Deluxe, and Business. The profit per night for each type of room and rental class is as follows:
Rental Class Super Saver Room Type I Room Type II $30 $20 Deluxe $35 $30 Business -$40
Type I rooms do not have Internet access and are not available for the Business rental class. Round Tree’s management makes a forecast of the demand by rental class for each night in the future. A linear programming model developed to maximize profit is used to determine how many reservations to accept for each rental class. The demand forecast for a particular night is 130 rentals in the Super Saver class, 60 rentals in the Deluxe class, and 50 rentals in the Business class. Round Tree has 100 Type I rooms and 120 Type II rooms.
9
3
10/12/2011
Hotel Room (i) 100
Type I
$30 $35 $20
Rental Class ( j )
Super Saver
130
120
Type II
$30 $40
Deluxe
60
Supply Capacities (220)
Business
50
Distribution Routes Rental Demand (240)
Total Supplies (e.g., 220)
10
Model Formulation:
Let S1= SuperSaver Rentals allocated to room type I S2= SuperSaver Rentals allocated to room type II D1= Deluxe rentals allocated to room type I D2= Deluxe rentals allocated to room type II B2= Business rentals allocated to room type II Max 30S1 + 20S2 + 35D1 + 30D2 + 40B2 Subject to: 1S1 + 1S2 ≤ 130 (estimated demand for rentals in Super Saver class) 1D1 + 1D2 ≤ 60 (estimated demand for rentals in Deluxe class) 1B2 ≤ 50 (estimated demand for rentals in Business class) 1S1 + 1D1 = 100 (availability of Type I room) 1S2 + 1D2 + 1B2 = 120 (availability of Type II room) S1, S2, D1, D2 and B2 ≥ 0 and integers.
11
The manager of Harley’s Sand and Gravel Pit has decided to utilize two intermediate nodes as transshipment points for temporary storage of topsoil.
Cost of Shipping One Unit from the Farms to Warehouses
Cost of Shipping One Unit from the Warehouses to Projects
12
4
10/12/2011
13
xij = quantity of topsoil shipped from source i to destination j.
M in im ize to tal c o st = c1 4 x1 4 + c 2 4 x 2 4 + c 3 4 x 3 4 + c1 5 x1 5 + c 2 5 x 2 5 + c 3 5 x 3 5 + c 46 x 46 + c 47 x 47 + c 48 x 48 + c56 x56 + c57 x57 + c58 x58 su b ject to : N ode 1: N ode 2: N ode 3: N ode 4: N ode 5: N ode 6: N ode 7: N ode 8: x 1 4 + x1 5 x24 + x25 x34 + x35 = S1 = S2 = S3
Transshipment constraints
x1 4 + x 2 4 + x 3 4 − x 4 6 − x 4 7 − x 4 8 = 0 x1 5 + x 2 5 + x 3 5 − x 5 6 − x 5 7 − x 5 8 = 0 x 46 + x56 x47 + x57 x 48 + x58 A ll va riab les ≥ 0 = D6 = D7 = D8
14
15
5
10/12/2011
A manager has prepared a table that shows the cost of performing each of five jobs by each of five employees (see Table 5-7). According to this table, job I will cost $15 if done by Al. $20 if it is done by Bill, and so on. The manager has stated that his goal is to develop a set of job assignments that will minimize the total cost of getting all four jobs done. It is further required that the jobs be performed simultaneously, thus requiring one job being assigned to each employee.
16
17
xij = quantity shipped from source i to destination j.
18
6
10/12/2011
19
Find the shortest Route from node 1 to node 7.
20
A transshipment model can be developed for the shortest route problem. We will define all nodes as a transshipment nodes, except a supply of 1 at the origin node, and a demand p pp y g , of 1 at the destination node. We will define all remaining nodes as transshipment nodes. We want to minimize the total cost of shipping one unit from the source node to the destination node.
21
7
10/12/2011
xij= flow from node i to node j
22
23
Consider the following network model. Formulate this problem as a linear programming.
3 2 3 Input 4 3 Source 4 1 3 3 3 5 6 1 6 4 1 5 2 3 4 3 7 Sink 2 Output 5
24
8
10/12/2011
A capacitated transshipment model can be developed for the maximal flow problem. We need to modify the network by adding a fictitious dummy branch between node 7 (sink) and node 1(source). There is no capacity on the newly added 7-1 arc 7 1 arc. We want to maximize the flow over the 7-1 arc. Thus, the objective function is to maximize the flow of the dummy branch. This can be obtained as: maximize x71
25
x12 4 Source 1 3 x13
3 x25 5 x52 3 x45 x42 2 3 4 3 x24 x54 4 x14 3 4 x34 x64 1 3 x46 1 5 x43 3 x36 6 6 2
2 x57 x47 7 x67 5 Sink
x71 We add a fictitious dummy arc from node 7 back to node 1 to represent the total flow through the network.
26
LP Formulation (as Capacitated Transshipment Problem)
◦ There is a variable for every arc. ◦ There is a constraint for every node; the flow out must equal the flow in. ◦ There is a constraint for every arc (except the added sink-tosource arc); arc capacity cannot be exceeded. ◦ The objective is to maximize the flow over the added, sinkto-source arc.
Let xij = the flow on the arc from node i to node j . Max xk1 (where k is sink node, 1 is source node) s.t. Σxij - Σxji = 0 xij
27
xij > 0, for all i and j (non-negativity)
9
10/12/2011
Conservation Constraints for Each Node
x12 4 Sour ce
1 3 x13
x25 3 5 x52 3 x45 x42 2 3 4 3 x24 x54 4 x14 3 4 x34 x64 1 3 x46 1 5 x43 3 6 x36 6 2 x71
2 x57 x47 7 Sink
x67 5
28
Objective Function Max x71 Conservation Constraint for Each Node: x71 - x12 - x13 - x14 = 0 (flow in & out of node 1) x12 + x42 + x52 – x24 - x25 = 0 ( ode ) (node 2) x13 + x43 – x34 – x36 = 0 (node 3) x14 + x24 +x34+x54 +x64 –x42 -x43 -x45 - x46 -x47= 0 (node4) x25 + x45 – x52 – x54 - x57 = 0 (node 5) x36 + x46 - x64 - x67 = 0 (node 6) x47 + x57 + x67 - x71 = 0 (node 7)
29
Conservation Constraints for Each Node
x12
x13
x14
x12 4 x25 3 5 x52 3 x45 x42 2 3 4 3 x24 x54 4 x14 3 4 x34 x64 1 3 x46 1 5 x43 3 6 x36 6 2 x71
30
2 x57 x47 7 Sink
Source
1 3 x13
x67 5
10
10/12/2011
Capacity constraint for each arc: x12 x25 x43 x52 x67
Nonnegative constraint: xij≥ 0
31
2 3 Source 4 1 3 3 1
2
5 2 3 1 5 7 Sink
4 1 4 10
6
32
See the handouts for all the examples of the application problems that we are not discussed in the class.
11
10/12/2011
A. Integer Programming B. Excel for IP problem
12