Quantitative Analysis week 3 Discussion

QAch.6.pptx

Home >Business & Finance homework help >Management homework help >Quantitative Analysis week 3 Discussion

An Introduction to Management Science, 15e Quantitative Approaches to Decision Making

Anderson Sweeney Williams Camm Cochran Fry Ohlmann

© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, 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 or school-approved learning management system for classroom use.

Chapter 6: Distribution and Network Models

6.1 – Supply Chain Models

6.2 – Assignment Problem

6.3 – Shortest-Route Problem

6.4 – Maximal Flow Problem

6.5 – A Production and Inventory Application

‹#›

Transportation, Transshipment, and Assignment Problems

The models discussed in this chapter belong to a special class of linear programming problems called network flow problems.

Examples: Supply chains, transportation and transshipment problems, assignment problems, shortest-route problems, and maximal flow problems.

In each case, we present a graphical representation of the problem in the form of a network. We then show how the problem can be formulated and solved as a linear program.

‹#›

Supply Chain Models

A supply chain describes the set of all interconnected resources involved in producing and distributing a product.

In general, supply chains are designed to satisfy customer demand for a product at minimum cost.

Those that control the supply chain must make decisions such as where to produce a product, how much should be produced, and where it should be sent.

‹#›

Transportation Problem (1 of 12)

The transportation problem arises frequently in planning for the distribution of goods and services from several supply locations to several demand locations.

Typically, the quantity of goods available at each supply location (origin) is limited, and the quantity of goods needed at each of several demand locations (destinations) is known.

The usual objective in a transportation problem is to minimize the cost of shipping goods from the origins to the destinations.

‹#›

Transportation Problem (2 of 12)

Let us consider a transportation problem faced by Foster Generators. This problem involves the transportation of a product from three plants to four distribution centers. Foster Generators operates plants in Cleveland, Ohio; Bedford, Indiana; and York, Pennsylvania.

Production capacities over the next three-month planning period for one particular type of generator are as follows:

Origin	Plant	Three-Month Production Capacity (units)
1	Cleveland	5,000
2	Bedford	6,000
3	York	2,500
		Total 13,500

‹#›

Transportation Problem (3 of 12)

The firm distributes its generators through four regional distribution centers located in Boston, Chicago, St. Louis, and Lexington; the three-month forecast of demand for the distribution centers is as follows:

Origin	Plant	Three-Month Production Capacity (units)
1	Boston	6,000
2	Chicago	4,000
3	St. Louis	2,000
4	Lexington	1,500
		Total 13,500

Management would like to determine how much of its production should be shipped from each plant to each distribution center.

‹#›

Transportation Problem (4 of 12)

Here is a graph showing the 12 distribution routes Foster can use.

Such a graph is called a network.

The circles are referred to as nodes and the lines connecting the nodes as arcs.

Note that the direction of flow (from origin to destination) is indicated by the arrows.

‹#›

Transportation Problem (5 of 12)

Each origin and destination is represented by a node, and each possible shipping route is represented by an arc.

The amount of the supply is written next to each origin node, and the amount of the demand is written next to each destination node.

The goods shipped from the origins to the destinations represent the flow in the network.

‹#›

Transportation Problem (6 of 12)

The objective is to determine the routes to be used and the quantity to be shipped via each route that will provide the minimum total transportation cost.

The cost for each unit shipped on each route is shown on each arc.

‹#›

Transportation Problem (7 of 12)

A linear programming model can be used to solve this transportation problem. We use double-subscripted decision variables, with

x11 = the number of units shipped from origin 1 (Cleveland) to destination 1 (Boston)

x12 = the number of units shipped from origin 1 (Cleveland) to destination 2 (Chicago), and so on.

In general, the decision variables for a transportation problem having m origins and n destinations are written as follows:

‹#›

Transportation Problem (8 of 12)

Because the objective of the transportation problem is to minimize the total transportation cost, we develop the following cost expressions:

Transportation costs for units shipped from Cleveland

Transportation costs for units shipped from Bedford

Transportation costs for units shipped from York

The sum of these expressions provides the objective function showing the total transportation cost for Foster Generators.

‹#›

Transportation Problem (9 of 12)

Transportation problems need constraints because each origin has a limited supply and each destination has a demand.

The constraints for the total number of units shipped are:

With the four distribution centers as the destinations, four demand constraints are needed:

‹#›

Transportation Problem (10 of 12)

Here is the optimal solution for the Foster Generators Transportation Problem:

Optimal Objective Value = 39500.00000

Variable	Value	Reduced Cost
X11	3500.00000	0.00000
X12	1500.00000	0.00000
X13	0.00000	8.00000
X14	0.00000	6.00000
X21	0.00000	1.00000
X22	2500.00000	0.00000
X23	2000.00000	0.00000
X24	1500.00000	0.00000
X31	2500.00000	0.00000
X32	0.00000	4.00000
X33	0.00000	6.00000
X34	0.00000	6.00000

‹#›

Transportation Problem (11 of 12)

The minimal cost transportation schedule is:

Route (From)	Route (To)	Units Shipped	Cost per Unit	Total Cost
Cleveland	Boston	3500	$3	$10,500
Cleveland	Chicago	1500	$2	$ 3,000
Bedford	Chicago	2500	$5	$12,500
Bedford	St. Louis	2000	$2	$ 4,000
Bedford	Lexington	1500	$3	$ 4,500
York	Boston	2500	$2	$ 5,000
				$39,500

‹#›

Transportation Problem (12 of 12)

And the network diagram for the optimal solution is:

For example, 3500 units should be shipped from Cleveland to Boston, and 1500 units should be shipped from Cleveland to Chicago.

‹#›

Transshipment Problem (1 of 13)

The transshipment problem is an extension of the transportation problem in which intermediate nodes, referred to as transshipment nodes, are added to account for locations such as warehouses.

In this general type of distribution problem, shipments may be made between any pair of the three general types of nodes: origin nodes, transshipment nodes, and destination nodes.

As was true for the transportation problem, the supply available at each origin is limited, and the demand at each destination is specified.

The objective in the transshipment problem is to determine how many units should be shipped over each arc in the network so that all destination demands are satisfied with the minimum possible transportation cost.

‹#›

Transshipment Problem (2 of 13)

Consider the transshipment problem faced by Ryan Electronics. Ryan is an electronics company with production facilities in Denver and Atlanta. Components produced at either facility may be shipped to either of the firm’s regional warehouses, which are located in Kansas City and Louisville. From the regional warehouses, the firm supplies retail outlets in Detroit, Miami, Dallas, and New Orleans.

‹#›

Transshipment Problem (3 of 13)

We need a constraint for each node and a variable for each arc. Let xij denote the number of units shipped from node i to node j.

For example, x13 denotes the number of units shipped from the Denver plant to the Kansas City warehouse, x14 denotes the number of units shipped from the Denver plant to the Louisville warehouse, and so on.

‹#›

Transshipment Problem (4 of 13)

Because the supply at the Denver plant is 600 units, the amount shipped from the Denver plant must be less than or equal to 600. Mathematically, we write this supply constraint as

Similarly, for the Atlanta plant we have

‹#›

Transshipment Problem (5 of 13)

We now consider how to write the constraints corresponding to the two transshipment nodes.

For node 3 (the Kansas City warehouse), we must guarantee that the number of units shipped out must equal the number of units shipped into the warehouse. If the number of units shipped out of node 3 equals

And the number of units shipped into node 3 equals

we obtain

Placing all the variables on the left-hand side provides the constraint corresponding to node 3 as

Similarly, the constraint corresponding to node 4 is

‹#›

Transshipment Problem (6 of 13)

To develop the constraints associated with the destination nodes, we recognize that for each node the amount shipped to the destination must equal the demand.

For example, to satisfy the demand for 200 units at node 5 (the Detroit retail outlet), we write

Similarly, for nodes 6, 7, and 8, we have

As usual, the objective function reflects the total shipping cost over the 12 shipping routes.

‹#›

Transshipment Problem (7 of 13)

Combining the objective function and constraints leads to a 12-variable, 8-constraint linear programming model of the Ryan Electronics transshipment problem.

‹#›

Transportation Problem (8 of 13)

The optimal solution for the Ryan Electronics Transshipment problem is shown here.

Optimal Objective Value = 5200.00000

Variable	Value	Reduced Cost
X13	550.00000	0.00000
X14	50.00000	0.00000
X23	0.00000	3.00000
X24	400.00000	0.00000
X35	200.00000	0.00000
X36	0.00000	1.00000
X37	350.00000	0.00000
X38	0.00000	0.00000
X45	0.00000	3.00000
X46	150.00000	0.00000
X47	0.00000	4.00000
X48	300.00000	0.00000

‹#›

Transshipment Problem (9 of 13)

The optimal solution for the Ryan Electronics Transshipment problem is shown here.

Route (From)	Route (To)	Units Shipped	Cost per Unit	Total Cost
Denver	Kansas City	550	$2	$1100
Denver	Louisville	50	$3	$ 150
Atlanta	Louisville	400	$1	$ 400
Kansas City	Detroit	200	$2	$ 400
Kansas City	Dallas	350	$3	$ 1050
Louisville	Miami	150	$4	$ 600
Louisville	New Orleans	300	$5	$1500
				$5200

‹#›

Transshipment Problem (10 of 13)

For an illustration of a more general type of transshipment problem, let us modify the Ryan Electronics problem.

Suppose that it is possible to ship directly from Atlanta to New Orleans at $4 per unit and from Dallas to New Orleans at $1 per unit.

‹#›

Transshipment Problem (11 of 13)

The new variables x28 and x78 appear in the objective function and in the constraints corresponding to the nodes to which the new arcs are connected.

‹#›

Transshipment Problem (12 of 13)

The value of the optimal solution has been reduced $600 by allowing these additional shipping routes. The value of x28 = 300 indicates that 300 units are being shipped directly from Atlanta to New Orleans. The value of x78 = 0 indicates that no units are shipped from Dallas to New Orleans in this solution.

Optimal Objective Value = 4600.00000

Variable	Value	Reduced Cost
X13	550.000	0.00000
X14	50.000	0.00000
X23	0.000	3.00000
X24	100.000	0.00000
X35	200.000	0.00000
X36	0.000	1.00000
X37	350.000	0.00000
X38	0.000	2.00000
X45	0.000	3.00000
X46	150.000	0.00000
X47	0.000	4.00000
X48	0.000	2.00000
X28	300.000	0.00000
X78	0.000	0.00000

‹#›

Transshipment Problem (13 of 13)

As with transportation problems, transshipment problems may be formulated with several variations, including

1. Total supply not equal to total demand

2. Maximization objective function

3. Route capacities or route minimums

4. Unacceptable routes

The linear programming model modifications required to accommodate these variations are identical to the modifications required for the transportation problem. When we add one or more constraints of the form xij ≤ Lij to show that the route from node i to node j has capacity Lij, we refer to the transshipment problem as a capacitated transshipment problem.

‹#›

Assignment Problem (1 of 11)

The assignment problem arises in a variety of decision-making situations; typical assignment problems involve assigning jobs to machines, agents to tasks, sales personnel to sales territories, contracts to bidders, and so on.

A distinguishing feature of the assignment problem is that one agent is assigned to one and only one task.

Specifically, we look for the set of assignments that will optimize a stated objective, such as minimize cost, minimize time, or maximize profits.

‹#›

Assignment Problem (2 of 11)

Let’s consider the case of Fowle Marketing Research, which has received requests for market research studies from 3 new clients.

The company faces the task of assigning a project leader (agent) to each client (task).

Three individuals have no other commitments and are available for the project leader assignments.

The time required to complete each study will depend on the experience and ability of the project leader assigned.

The three projects have approximately the same priority, and management wants to assign project leaders to minimize the total number of days required to complete all three projects.

A project leader is to be assigned to one client only.

‹#›

Assignment Problem (3 of 11)

Fowle’s management must first consider all possible project leader–client assignments and then estimate the corresponding project completion times. With three project leaders and three clients, nine assignment alternatives are possible.

Here are the estimated project completion times (days) for each possible project leader–client assignment:

	Client
Project Leader	1	2	3
Terry	10	15	9
2. Carle	9	18	5
3. McClymonds	6	14	3

‹#›

Assignment Problem (4 of 11)

Note the similarity between the network models of the assignment problem and the transportation problem.

‹#›

Assignment Problem (5 of 11)

The assignment problem is a special case of the transportation problem in which all supply and demand values equal 1, and the amount shipped over each arc is either 0 or 1.

If x11 = 1, we interpret this as “project leader 1 (Terry) is assigned to client 1.”

If x11 = 0, we interpret this as “project leader 1 (Terry) is not assigned to client 1.”

Using this notation and the completion time data, we develop completion time expressions:

‹#›

Assignment Problem (6 of 11)

The sum of the completion times for the 3 project leaders provide the total days required to complete the three assignments. Thus, the objective function is

The constraints reflect the conditions that each project leader can be assigned to at most one client and each client must have one assigned project leader. These constraints are:

‹#›

Assignment Problem (7 of 11)

Combining the objective function and constraints into one model provides the following nine-variable, six-constraint linear programming model:

‹#›

Assignment Problem (8 of 11)

The optimal solution is:

Optimal Objective Value = 4600.00000

Variable	Value	Reduced Cost
X11	0.00000	0.00000
X12	1.00000	0.00000
X13	0.00000	2.00000
X21	0.00000	1.00000
X22	0.00000	5.00000
X23	1.00000	0.00000
X31	1.00000	0.00000
X32	0.00000	3.00000
X33	0.00000	0.00000

Project Leader	Assigned Client	Days
Terry	2	15
Carle	3	5
McClymonds	1	6

‹#›

Assignment Problem (9 of 11)

Because the assignment problem can be viewed as a special case of the transportation problem, the problem variations that may arise in an assignment problem parallel those for the transportation problem.

Specifically, we can handle

1. Total number of agents (supply) not equal to the total number of tasks (demand)

2. A maximization objective function

3. Unacceptable assignments

‹#›

Assignment Problem (10 of 11)

If the total number of agents (supply) are not equal to the total number of tasks (demand):

This is analogous to total supply not equaling total demand in a transportation problem.

The extra agents simply remain unassigned in the linear programming solution.

If the number of tasks exceeds the number of agents, the linear programming model will not have a feasible solution. By adding two dummy project leaders, we can create a new assignment problem with the number of project leaders equal to the number of clients. The objective function coefficients for the assignment of dummy project leaders would be zero so that the value of the optimal solution would represent the total number of days required by the assignments actually made.

‹#›