辅导Object-oriented、Java程序讲解、辅导Java语言、讲解data file

2019.01.25 - 首页 >> Java编程

Objective: Object-oriented solution (Java)

Create the classes needed to solve this problem. Your program must be an application called

findOptimalTransport that takes the input data file as an argument.

You can’t use static methods (except main). Your program must be a Java application that takes as a

command line argument the name of the data file.

Problem Description

In this assignment, we study the classic problem of transporting goods to places where they are in

demand. Suppose we have a number of factories, located in different locations and each having a certain

production capacity. The goods produced must be sent to warehouses that are also located around the

world and that, depending on demand, require a certain amount of goods. This problem is usually

represented by a table.

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 ($6) ($8) ($10) 30

Factory 2 ($7) ($11) ($11) 40

Factory 3 ($4) ($5) ($12) 50

The above table contains the number of units produced by each factory and requested by each

warehouse. The numbers in parentheses indicate the cost of transporting a unit from a factory to a

warehouse. The problem is to find out how many goods are to be sent to each warehouse from each

factory in order to minimize transportation costs. Note that we consider here the case where supply and

demand are balanced.

This problem can be solved in different ways. In this assignment, you must use the solution described

here, which proceeds in two steps: i) the first step is to find an initial solution then ii) in the second step,

the optimal solution is found by iteratively improving the current solution until an optimal solution is

reached.

Step 1: Minimum Cell Cost Method

The principle is simple, goods are first allocated through the least expensive route. In the example

above, this is the route from Factory 3 to Warehouse A.

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 (6) (8) (10) 30

Factory 2 (7) (11) (11) 40

Factory 3 40 (4) (5) (12) 50

The next allocation is made using the least expensive remaining route, knowing that Factory 3 has only

10 units left.

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 (6) (8) (10) 30

Factory 2 (7) (11) (11) 40

Factory 3 40 (4) 10 (5) (12) 50

The process continues by identifying the next lower cost route by noting that Warehouse A has received

all the goods requested (so the cells in the first column can no longer be used) and that Factory 3 has

already committed all its goods (so cells in the last row can no longer be used). The next assignment is

therefore:

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 (6) 10 (8) (10) 30

Factory 2 (7) (11) (11) 40

Factory 3 40 (4) 10 (5) (12) 50

Which only leaves the demand at warehouse C:

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 (6) 10 (8) 20 (10) 30

Factory 2 (7) (11) 40 (11) 40

Factory 3 40 (4) 10 (5) (12) 50

When all the goods of the factories have been assigned to warehouses, an initial solution is found.

However, this solution is not optimal. Some roads are not used. The second step is therefore to

determine whether the use of these unused roads would reduce the total cost of transportation.

Step 2: Stepping-stone Method

To determine if an unused route would be more beneficial, one needs to calculate its cost of use.

Let us first consider the route from Factory 1 to Warehouse A (1-A) of the previous solution and

calculate what it would cost to transport a unit by this route.

If a unit was to be transported by this route from Factory 1 to Warehouse A, then a unit from

Plant 1 to another warehouse (either B or C) would have to be removed, since Factory 1 produces only

30 units. So let's remove a unit from Route 1-B. This means that warehouse B loses a unit that will

have to be moved by another road, say 3-B.

In order to respect the production constraints of Factory 3, one unit must be removed from road

3-A. And since we have added a unit to warehouse A, we are in balance again. The re-routing of a unit

as described is thus represented on our board:

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 +1 (6) -1 10 (8) 20 (10) 30

Factory 2 (7) (11) 40 (11) 40

Factory 3 -1 40 (4) +1 10 (5) (12) 50

This makes it possible to calculate the cost of this re-routing of one unit: +6-8+5-4 = -1. That

means we save $ 1 for each unit redirected by that route. The 'marginal cost' of the 1-A route is therefore

-1 considering the current solution.

Formally, the marginal cost of an unused road is calculated as follows: Starting from an

empty cell, you have to jump to a non-empty cell on the same row. From this cell, we then move to a

non-empty cell of the same column, then to a non-empty cell of the same row and so on until we fall

back on the empty cell of departure and this without ever landing two times on the same cell. The cost is

then calculated by alternating subtractions and additions along the route.

Next we calculate the marginal cost of cell 2-A, i.e., the cost of transporting one unit via this

route. The sequence is a little more complex this time: 2-A, 2-C, 1-C, 1-B, 3-B, 3-A, 2-A.

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 (6) -1 10 (8) +1 20 (10) 30

Factory 2 +1 (7) (11) -1 40 (11) 40

Factory 3 -1 40 (4) +1 10 (5) (12) 50

This gives the following marginal cost: +7-11+10-8+5-4 = -1, i.e., the same cost as before, so this route

is also advantageous.

Now let's explore Route 2-B:

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 (6) -1 10 (8) +1 20 (10) 30

Factory 2 (7) +1 (11) -1 40 (11) 40

Factory 3 40 (4) 10 (5) (12) 50

The marginal cost of Route 2-B is +11-11+10-8 = +2. This route is more expensive, so it will not be

considered.

The last unused route is Route 3-C.

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 (6) +1 10 (8) -1 20 (10) 30

Factory 2 (7) (11) 40 (11) 40

Factory 3 40 (4) -1 10 (5) +1 (12) 50

The marginal cost of 3-C is +12-10+8-5 = 5. Only the first two roads are advantageous.

We take one of them, for example 1-A (If these negative cost routes would not be equal, we would of

course the route with the largest reduction in cost – the most negative value).

One then assigns the maximum transport of units by this selected route:

Demand ?

Warehouse A

Warehouse B

Warehouse C

Production

▼

Factory 1 10 (6) (8) 20 (10) 30

Factory 2 (7) (11) 40 (11) 40

Factory 3 30 (4) 20 (5) (12) 50

This is a cheaper solution than the one initially found. We start again with the same procedure

considering all empty cells and calculate the marginal cost. This continues until no new route can be

found that result in a saving of transport costs.

** this algorithm needs to be reworked ...

do :

best-marginal-cost=0

for all empty cell :

marginal-cost= cell-cost

do:

move to a non-empty cell on same row: marginal-cost-= cell-cost

move to a non-empty cell on same column: marginal-cost+= cellcost

while back to current empty cell

if marginal-cost<best-marginal-cost

best-marginal-cost= marginal-cost

if best-marginal-cost<0

re-allocate units to best route

while (best-marginal-cost < 0)