Line: 1 to 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

<-- Under Construction --> | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Line: 84 to 84 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

American Steel, an Ohio-based steel manufacturing company, produces steel at its two steel mills located at Youngstown and Pittsburgh. The company distributes finished steel to its retail customers through the distribution network of regional and field warehouses shown below:
The network represents shipment of finished steel from American Steel’s two steel mills located at Youngstown (node 1) and Pittsburgh (node 2) to their field warehouses at Albany, Houston, Tempe, and Gary (nodes 6, 7, 8 and 9) through three regional warehouses located at Cincinnati, Kansas City, and Chicago (nodes 3, 4 and 5). Also, some field warehouses can be directly supplied from the steel mills.
The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the
The current monthly demand at American Steel’s four field warehouses is as follows:
The Youngstown and Pittsburgh mills can produce up to 10,000 tons and 15,000 tons of steel per month, respectively. The management wants to know the least cost monthly shipment plan.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|*1. IDENTIFY THE DECISION VARIABLES*
The decision variables for this problem are the same as for the transportation problem, the # The set of all nodes in the network set NODES; # The set of arcs in the network set ARCS within NODES cross NODES;Now we define bounds on the flow (of our goods) along each arc: # The minimum and maximum flow allowed along the arcs param Min {ARCS} integer, default 0; param Max {(m, n) in ARCS} integer, >= Min[m, n], default Infinity;and finally declare our `Flow` variables:
# The flow of goods to be sent across an arc var Flow {(m, n) in ARCS} >= Min[m, n], <= Max[m, n], integer;
The objective of transshipment problems in general and The American Steel Problem in particular is to minimise the cost of shipping goods through the network: # The cost of shipping 1 unit of goods (per time unit) param Cost {ARCS}; # Minimise the total shipping cost minimize TotalCost: sum {(m, n) in ARCS} Cost[m, n] * Flow[m, n];
All the nodes have supply and demand, demand = 0 for supply nodes, supply = 0 for demand nodes and supply = demand = 0 for transshipment nodes. Also, the supply and demand amounts must be integer to ensure a naturally integer solution (i.e., linear programming will provide an integer optimal solution). # Each node has a (non-negative, integer) supply and a (non-negative, integer) demand # Note. supply nodes have demand = 0 and vice versa, # transshipment nodes have supply = demand = 0 param Supply {NODES} >= 0, integer, default 0; param Demand {NODES} >= 0, integer, default 0;
The only constraints in the transshipment problem are # Must conserve flow in the network (goods cannot disappear!) subject to ConserveFlow {n in NODES}: sum {m in NODES: (m, n) in ARCS} Flow[m, n] + Supply[n] => sum {p in NODES: (n, p) in ARCS} Flow[n, p] + Demand[n]; For example, if a node has a supply of 10 units and has 10 units flowing in, then it can have no more than 20 units flowing out:
Transshipment problems are often presented as a network formulation:
The nodes of The American Steel Problem can be easily ???LINK??? defined using a list : set NODES := Youngstown Pittsburgh Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary ;Note that `Kansas City` must be enclosed in `'` and `'` because of the whitespace in the name.
The arc set is 2-dimensional and can be ???LINK??? defined in a number of different ways : # List of arcs set ARCS := (Youngstown, Albany), (Youngstown, Cincinnati), ... , (Chicago, Gary) ; # Table of arcs set ARCS: Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary := Youngstown + + + + - - - Pittsburgh + + + - - - + Cincinnati - - - + + - - 'Kansas City' - - - - + + - Chicago - - - - - + + ; # Array of arcs set ARCS := (Youngstown, *) Cincinnati 'Kansas City' Chicago Albany (Pittsburgh, *) Cincinnati 'Kansas City' Chicago Gary . . . (Chicago, *) Tempe Gary ;
We can choose lists, tables or arrays to define the parameters for The American Steel Problem,
but in this case we will use a list and ???LINK??? define multiple parameters
at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of
param: Cost Min Max:= Youngstown Albany 500 . 1000 Youngstown Cincinnati 350 . 3000 Youngstown 'Kansas City' 450 1000 5000 Youngstown Chicago 375 . 5000 Pittsburgh Cincinnati 350 . 2000 Pittsburgh 'Kansas City' 450 2000 3000 Pittsburgh Chicago 400 . 4000 Pittsburgh Gary 450 . 2000 Cincinnati Albany 350 1000 5000 Cincinnati Houston 550 . 6000 'Kansas City' Houston 375 . 4000 'Kansas City' Tempe 650 . 4000 Chicago Tempe 600 . 2000 Chicago Gary 120 . 4000 ;Note that the cost is in $/1000 ton, so we must divide the cost by 1000 before solving: let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;| |

View topic | History: r24 < r23 < r22 < r21 | More topic actions...

Copyright © 2008-2023 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback