Intro to Management science

Slides by

John

Loucks

St. Edward’s

University

‹#›

‹#›

Chapter 6, Part B: Distribution and Network Models

Shortest-Route Problem

Maximal Flow Problem

A Production and Inventory Application

‹#›

‹#›

Shortest-Route Problem

The shortest-route problem is concerned with finding the shortest path in a network from one node (or set of nodes) to another node (or set of nodes).

If all arcs in the network have nonnegative values then a labeling algorithm can be used to find the shortest paths from a particular node to all other nodes in the network.

The criterion to be minimized in the shortest-route problem is not limited to distance even though the term "shortest" is used in describing the procedure. Other criteria include time and cost. (Neither time nor cost are necessarily linearly related to distance.)

‹#›

‹#›

Linear Programming Formulation

Using the notation:

xij = 1 if the arc from node i to node j

is on the shortest route

0 otherwise

cij = distance, time, or cost associated

with the arc from node i to node j

continued

Shortest-Route Problem

‹#›

‹#›

xij > 0 for all i and j

continued

Origin nodes i

Transshipment nodes

Destination nodes j

s.t.

Linear Programming Formulation (continued)

Shortest-Route Problem

‹#›

Susan Winslow has an important business meeting

in Paducah this evening. She has a number of alternate routes by which she can travel from the company headquarters in Lewisburg to Paducah. The network of alternate routes and their respective travel time, ticket cost, and transport mode appear on the next two slides.

If Susan earns a wage of $15 per hour, what route

should she take to minimize the total travel cost?

Example: Shortest-Route

‹#›

‹#›

6

A

B

C

D

E

F

G

H

I

J

K

L

M

Paducah

Lewisburg

1

2

5

3

4

Network Representation

Example: Shortest-Route

‹#›

‹#›

Transport Time Ticket

Route Mode (hours) Cost

A Train 4 $ 20

B Plane 1 $115

C Bus 2 $ 10

D Taxi 6 $ 90

E Train 3 1/3 $ 30

F Bus 3 $ 15

G Bus 4 2/3 $ 20

H Taxi 1 $ 15

I Train 2 1/3 $ 15

J Bus 6 1/3 $ 25

K Taxi 3 1/3 $ 50

L Train 1 1/3 $ 10

M Bus 4 2/3 $ 20

Example: Shortest-Route

‹#›

‹#›

Transport Time Time Ticket Total

Route Mode (hours) Cost Cost Cost

A Train 4 $60 $ 20 $ 80

B Plane 1 $15 $115 $130

C Bus 2 $30 $ 10 $ 40

D Taxi 6 $90 $ 90 $180

E Train 3 1/3 $50 $ 30 $ 80

F Bus 3 $45 $ 15 $ 60

G Bus 4 2/3 $70 $ 20 $ 90

H Taxi 1 $15 $ 15 $ 30

I Train 2 1/3 $35 $ 15 $ 50

J Bus 6 1/3 $95 $ 25 $120

K Taxi 3 1/3 $50 $ 50 $100

L Train 1 1/3 $20 $ 10 $ 30

M Bus 4 2/3 $70 $ 20 $ 90

Example: Shortest-Route

‹#›

‹#›

Example: Shortest-Route

LP Formulation

Objective Function

Min 80x12 + 40x13 + 80x14 + 130x15 + 180x16 + 60x25

+ 100x26 + 30x34 + 90x35 + 120x36 + 30x43 + 50x45

+ 90x46 + 60x52 + 90x53 + 50x54 + 30x56

Node Flow-Conservation Constraints

x12 + x13 + x14 + x15 + x16 = 1 (origin)

– x12 + x25 + x26 – x52 = 0 (node 2)

– x13 + x34 + x35 + x36 – x43 – x53 = 0 (node 3)

– x14 – x34 + x43 + x45 + x46 – x54 = 0 (node 4)

– x15 – x25 – x35 – x45 + x52 + x53 + x54 + x56 = 0 (node 5)

x16 + x26 + x36 + x46 + x56 = 1 (destination)

‹#›

‹#›

Example: Shortest-Route

Solution Summary

Minimum total cost = $150

x12 = 0 x25 = 0 x34 = 1 x43 = 0 x52 = 0

x13 = 1 x26 = 0 x35 = 0 x45 = 1 x53 = 0

x14 = 0 x36 = 0 x46 = 0 x54 = 0

x15 = 0 x56 = 1

x16 = 0

‹#›

‹#›

Maximal Flow Problem

The maximal flow problem is concerned with determining the maximal volume of flow from one node (called the source) to another node (called the sink).

In the maximal flow problem, each arc has a maximum arc flow capacity which limits the flow through the arc.

‹#›

‹#›

Maximal Flow Problem

A capacitated transshipment model can be developed for the maximal flow problem.

We will add an arc from the sink node back to the source node to represent the total flow through the network.

There is no capacity on the newly added sink-to-source arc.

We want to maximize the flow over the sink-to-source arc.

‹#›

‹#›

Maximal Flow Problem

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-to-source arc); arc capacity cannot be exceeded.

The objective is to maximize the flow over the added, sink-to-source arc.

‹#›

‹#›

Maximal Flow Problem

LP Formulation

(as Capacitated Transshipment Problem)

Max xk1 (k is sink node, 1 is source node)

s.t. xij - xji = 0 (conservation of flow) i j

xij < cij (cij is capacity of ij arc)

xij > 0, for all i and j (non-negativity)

(xij represents the flow from node i to node j)

‹#›

‹#›

Example: Maximal Flow

National Express operates a fleet of cargo planes and

is in the package delivery business. NatEx is interested

in knowing what is the maximum it could transport in

one day indirectly from San Diego to Tampa (via Denver, St. Louis, Dallas, Houston and/or Atlanta) if its direct flight was out of service.

NatEx's indirect routes from San Diego to Tampa, along with their respective estimated excess shipping capacities (measured in hundreds of cubic feet per day), are shown on the next slide.

Is there sufficient excess capacity to indirectly ship 5000 cubic feet of packages in one day?

‹#›

‹#›

Network Representation

2

5

1

4

7

3

4

4

3

3

2

3

4

2

3

3

3

1

5

5

1

6

3

Denver

San

Diego

St. Louis

Houston

Tampa

Atlanta

Dallas

6

Example: Maximal Flow

‹#›

‹#›

Modified Network Representation

4

4

3

3

2

3

4

2

3

3

3

1

5

5

1

6

3

Sink

Source

Added

arc

2

5

1

4

7

3

6

Example: Maximal Flow

‹#›

‹#›

Example: Maximal Flow

LP Formulation

18 variables (for 17 original arcs and 1 added arc)

24 constraints

7 node flow-conservation constraints

17 arc capacity constraints (for original arcs)

‹#›

‹#›

Example: Maximal Flow

LP Formulation

Objective Function

Max x71

Node Flow-Conservation Constraints

x12 + x13 + x14 – x71 = 0 (node 1)

– x12 + x24 + x25 – x42 – x52 = 0 (node 2)

– x13 + x34 + x36 – x43 = 0 (and so on)

– x14 – x24 – x34 + x42 + x43 + x45 + x46 + x47 – x54 – x64 = 0

– x25 – x45 + x52 + x54 + x57 = 0

– x36 – x46 + x64 + x67 = 0

– x47 – x57 – x67 + x71 = 0

‹#›

‹#›

Example: Maximal Flow

LP Formulation (continued)

Arc Capacity Constraints

x12 < 4 x13 < 3 x14 < 4

x24 < 2 x25 < 3

x34 < 3 x36 < 6

x42 < 3 x43 < 5 x45 < 3 x46 < 1 x47 < 3

x52 < 3 x54 < 4 x57 < 2

x64 < 1 x67 < 5

‹#›

‹#›

Alternative Optimal Solution #1

Objective Function Value = 10.000

Variable Value

x12 3.000

x13 3.000

x14 4.000

x24 1.000

x25 2.000

x34 0.000

x36 5.000

x42 0.000

x43 2.000

Variable Value

x45 0.000

x46 0.000

x47 3.000

x52 0.000

x54 0.000

x57 2.000

x64 0.000

x67 5.000

x71 10.000

Example: Maximal Flow

‹#›

‹#›

Alternative Optimal Solution #1

3

4

3

2

1

2

3

2

5

5

Sink

Source

10

2

5

1

4

7

3

6

Example: Maximal Flow

‹#›

‹#›

Alternative Optimal Solution #2

Objective Function Value = 0.000

Variable Value

x12 3.000

x13 3.000

x14 4.000

x24 1.000

x25 2.000

x34 0.000

x36 4.000

x42 0.000

x43 1.000

Variable Value

x45 0.000

x46 1.000

x47 3.000

x52 0.000

x54 0.000

x57 2.000

x64 0.000

x67 5.000

x71 10.000

Example: Maximal Flow

‹#›

‹#›

Example: Maximal Flow

Alternative Optimal Solution #2

3

4

3

2

1

2

3

1

1

5

4

Sink

Source

10

2

5

1

4

7

3

6

‹#›

‹#›

A Production & Inventory Application

Transportation and transshipment models can be developed for applications that have nothing to do with the physical movement of goods from origins to destinations.

For example, a transshipment model can be used to solve a production and inventory problem.

‹#›

Example: Production & Inventory Application

Fodak must schedule its production of camera film for the first four months of the year. Film demand (in 000s of rolls) in January, February, March and April is expected to be 300, 500, 650 and 400, respectively. Fodak's production capacity is 500 thousand rolls of film per month.

The film business is highly competitive, so Fodak cannot afford to lose sales or keep its customers waiting. Meeting month i's demand with month i+1's production is unacceptable.

‹#›

Example: Production & Inventory Application

Film produced in month i can be used to meet demand in month i or can be held in inventory to meet demand in month i+1 or month i+2 (but not later due to the film's limited shelf life). There is no film in inventory at the start of January.

The film's production and delivery cost per thousand rolls will be $500 in January and February. This cost will increase to $600 in March and April due to a new labor contract. Any film put in inventory requires additional transport costing $100 per thousand rolls. It costs $50 per thousand rolls to hold film in inventory from one month to the next.

‹#›

© 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted

in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

‹#›

© 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted

in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

‹#›

© 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted

in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

‹#›

© 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted

in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

‹#›

© 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted

in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

‹#›

© 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted

in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

‹#›

© 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted

in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

‹#›

© 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted

in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

‹#›

2

3

4

7

6

5

11

10

9

8

1

FEBRUARY

PRODUCTION

JANUARY

PRODUCTION

MARCH

PRODUCTION

JANUARY

DEMAND

FEBRUARY

DEMAND

MARCH

DEMAND

APRIL

DEMAND

APRIL

PRODUCTION

MONTH 1

ENDING INVENTORY

MONTH 2

ENDING INVENTORY

MONTH 3

ENDING INVENTORY

500

500

500

500

300

500

650

400

500

600

500

600

700

600

50

100

50

100

50

600