OMIS 2010: Transportation and Trans-Shipment Models (Week 5)

What is the transport problem?

distribution type

What is the transportation problem goal?

decide how to transfer good from origin to destination @ minimum cost / maximum profit

What is an origin?

send location

What is a destination?

receive location

What are the transportation problem model characteristics?

• transfer item from origin to destination @ minimum cost

• origin supplies fixed units

• destination demands fixed units

What are the transportation problem model methods?

• step stone

• modify distribution

<

• Excel solver

What is the transportation & transshipment difference?

transportation: direct transfer

v.s.

transshipment: intermediate transfer

What is a network model?

transportation network drawing by node / arc & function

What are the network model elements?

• node

• arc

What is a node?

entity

What are some node examples?

• city

• people

• factory

• warehouse

What is an arc?

2 node relation

What are some arc examples?

• city road

• person knows other

• company ships to other

• warehouse receives good

What are the node types?

1. origin

2. destination

3. transshipment

What is the X_AB decision variable?

node flow / shipment amount

What are the node classes?

1. supply

2. demand

What does the transportation problem seek to minimize?

total shipping cost

What is the M decision variable?

origin number

What is the S_i decision variable?

supply

What is the N decision variable?

destination number

What is the D_j decision variable?

demand

What is the i decision variable?

origin

What is the j decision variable?

destination

What is the C_ij decision variable?

origin to destination unit shipping cost

What does the transportation problem tabular representation show?

row: s i

column: d j

cell: x_ij

→ send amount to i less than / equal to j send amount

→ receive amount from j less than / equal to i receive amount

What is the Excel setup process?

1. cost table

• row: i

• column: j

• inside cell: C_ij

2. shipping amount table

• row: i & total column [=SUM(s_i)] & s

• column: j & total row [=SUM(d_j)] & d

• inside cell: 0

3. total cost cell

• [=SUMPRODUCT(cost table’s cells, shipping amount table’s cells)]

4. Data → Solver

• Set Objective: total cost cell

• To: CHOOSE Min

• By Changing Variable Cells: (shipping amount’s cells)

5. constraint

meet d & NOT exceed s

• Subject to the Constraints:

  • Add → Cell Reference: total column → CHOOSE = sign → Constraint: s column

  • Add → Cell Reference: total row → CHOOSE = sign → Constraint: d row → OK

6. solve

• CHECK Make Unconstrained Variables Non-Negative

• Select a Solving Method: Simplex LP

7. interpret

• CHOOSE Keep Solver Solution

• Reports: Answer

What does the answer report show?

• when / how solve

• total cost

• shipping amounts

• requirements

What are the special cases?

• total supply does not equal total demand

• route maximum / route minimum

• unacceptable route

What if s exceeds d?

unused excess s

What is the Excel setup process if s exceeds d?

1. cost table

• row: i

• column: j

• inside cell: C_ij

2. shipping amount table

• row: i & total column [=SUM(s_i)] & s

• column: j & total row [=SUM(d_j)] & d

• inside cell: 0

3. total cost cell

• [=SUMPRODUCT(cost table’s cells, shipping amount table’s cells)]

4. Data → Solver

• Set Objective: total cost cell

• To: CHOOSE Min

• By Changing Variable Cells: (shipping amount’s cells)

5. constraint

meet d & NOT exceed s

• Subject to the Constraints:

  • Add → Cell Reference: total column → CHOOSE ≤ sign → Constraint: s column

  • Add → Cell Reference: total row → CHOOSE = sign → Constraint: d row → OK

6. solve

• CHECK Make Unconstrained Variables Non-Negative

• Select a Solving Method: Simplex LP

7. interpret

• CHOOSE Keep Solver Solution

• Reports: Answer

What if d exceeds s?

not feasible solution

→ add dummy origin with s equal to difference

• 0 cost

What is a route maximum?

x_ij ≤ L_ij

What is the L decision variable?

limit

What is the route minimum?

x_ij ≥ L_ij

What happens if there is an unacceptable route?

0 route capacity

What are some intermediate node examples?

• warehouse

• street

What is the transportation problem an example of?

network flow programming

What are some network flow programming problem examples?

• assignment problem

• equipment replacement

• financial plan

• short route

What explains why one models a problem as a network?

• make optimization models easy to explain

• available efficient algorithm

What does NFP stand for?

|:| network flow programming

What is NFP a case of?

linear programming

What does LP stand for?

|:| linear programming

What are some LP problem examples?

• product mix

• make v.s. buy

• capital budget

• production plan

• schedule / staff

What is the Excel setup process if d exceeds s?

1. cost table

• row: i & dummy → 0

• column: j

• inside cell: C_ij

2. shipping amount table

• row: i & total column [=SUM(s_i)] & s & dummy → d - s difference

• column: j & total row [=SUM(d_j)] & d

• inside cell: 0

3. total cost cell

• [=SUMPRODUCT(cost table’s cells, shipping amount table’s cells)]

4. Data → Solver

• Set Objective: total cost cell

• To: CHOOSE Min

• By Changing Variable Cells: (shipping amount’s cells)

5. constraint

meet d & NOT exceed s

• Subject to the Constraints:

  • Add → Cell Reference: total column → CHOOSE ≤ sign → Constraint: s column

  • Add → Cell Reference: total row → CHOOSE = sign → Constraint: d row → OK

6. solve

• CHECK Make Unconstrained Variables Non-Negative

• Select a Solving Method: Simplex LP

7. interpret

• CHOOSE Keep Solver Solution

• Reports: Answer

What is the transshipment Excel setup process?

1. origin to transshipment cost table

• row: origin

• column: transshipment

2. transshipment to destination cost table

• row: transshipment

• column: destination

3. origin to transshipment shipping amount table

• row: origin & total [=SUM]

• column: transshipment & total [=SUM] & s

4. transshipment to destination shipping amount table

• row: transshipment & total [=SUM] & d

• column: destination & total [=SUM]

5. transshipment flow table

• row: transshipment

• 2nd column: [0]

6. total cost cell

• [=SUMPRODUCT + SUMPRODUCT]

7. Data → Solver

• Set Objective: total cost cell

• To: CHOOSE Min

• By Changing Variable Cells: 3. cells, 4. cells

• Subject to the Constraints:

  • total column <= s column

  • transhipment column = 0

  • total row = d row

• CHECK Make Unconstrained Variables Non-Negative

• Select a Solving Method: CHOOSE Simplex LP

What are the transshipment variations?

• transshipment & destination

• flow goes between locations

What if d locations can be passed to further destinations along the way?

2nd column: d

What if the flow can go between locations?

create both variables

What explains how to prevent an unacceptable route?

assign high cost