Deck 10: Distribution and Network Problems

Question 1

Which of the following is not true regarding the linear programming formulation of a transportation problem?

A)Costs appear only in the objective function.
B)The number of variables is (number of origins)x (number of destinations).
C)The number of constraints is (number of origins)x (number of destinations).
D)The constraints' left-hand side coefficients are either 0 or 1.

Answer 1

C

Question 2

The difference between the transportation and assignment problems is that

A)total supply must equal total demand in the transportation problem
B)the number of origins must equal the number of destinations in the transportation problem
C)each supply and demand value is 1 in the assignment problem
D)there are many differences between the transportation and assignment problems

Answer 2

C

Question 3

Converting a transportation problem LP from cost minimization to profit maximization requires only changing the objective function;the conversion does not affect the constraints.

Answer 3

True

Question 4

Consider a maximal flow problem in which vehicle traffic entering a city is routed among several routes before eventually leaving the city.When represented with a network,

A)the nodes represent stoplights.
B)the arcs represent one way streets.
C)the nodes represent locations where speed limits change.
D)None of the alternatives is correct.

Question 5

Whenever total supply is less than total demand in a transportation problem,the LP model does not determine how the unsatisfied demand is handled.

Question 6

The objective of the transportation problem is to

A)identify one origin that can satisfy total demand at the destinations and at the same time minimize total shipping cost.
B)minimize the number of origins used to satisfy total demand at the destinations.
C)minimize the number of shipments necessary to satisfy total demand at the destinations.
D)minimize the cost of shipping products from several origins to several destinations.

Question 7

The problem which deals with the distribution of goods from several sources to several destinations is the

A)maximal flow problem
B)transportation problem
C)assignment problem
D)shortest-route problem

Question 8

In the general linear programming model of the assignment problem,

A)one agent can do parts of several tasks.
B)one task can be done by several agents.
C)each agent is assigned to its own best task.
D)one agent is assigned to one and only one task.

Question 9

The number of units shipped from origin i to destination j is represented by

A)x_ij.
B)x_ji.
C)c_ij.
D)c_ji.

Question 10

Arcs in a transshipment problem

A)must connect every node to a transshipment node.
B)represent the cost of shipments.
C)indicate the direction of the flow.
D)All of the alternatives are correct.

Question 11

The assignment problem constraint x₃₁ + x₃₂ + x₃₃ + x₃₄ < 2 means

A)agent 3 can be assigned to 2 tasks.
B)agent 2 can be assigned to 3 tasks.
C)a mixture of agents 1,2,3,and 4 will be assigned to tasks.
D)there is no feasible solution.

Question 12

Constraints in a transshipment problem

A)correspond to arcs.
B)include a variable for every arc.
C)require the sum of the shipments out of an origin node to equal supply.
D)All of the alternatives are correct.

Question 13

If a transportation problem has four origins and five destinations,the LP formulation of the problem will have

A)5 constraints
B)9 constraints
C)18 constraints
D)20 constraints

Question 14

The assignment problem is a special case of the

A)transportation problem.
B)transshipment problem.
C)maximal flow problem.
D)shortest-route problem.

Question 15

Which of the following is not true regarding an LP model of the assignment problem?

A)Costs appear in the objective function only.
B)All constraints are of the > form.
C)All constraint left-hand side coefficient values are 1.
D)All decision variable values are either 0 or 1.

Question 16

In a transshipment problem,shipments

A)cannot occur between two origin nodes.
B)cannot occur between an origin node and a destination node.
C)cannot occur between a transshipment node and a destination node.
D)can occur between any two nodes.

Question 17

We assume in the maximal flow problem that

A)the flow out of a node is equal to the flow into the node.
B)the source and sink nodes are at opposite ends of the network.
C)the number of arcs entering a node is equal to the number of arcs exiting the node.
D)None of the alternatives is correct.

Question 18

The shortest-route problem finds the shortest-route

A)from the source to the sink.
B)from the source to any other node.
C)from any node to any other node.
D)from any node to the sink.

Question 19

Consider a shortest route problem in which a bank courier must travel between branches and the main operations center.When represented with a network,

A)the branches are the arcs and the operations center is the node.
B)the branches are the nodes and the operations center is the source.
C)the branches and the operations center are all nodes and the streets are the arcs.
D)the branches are the network and the operations center is the node.

Question 20

The parts of a network that represent the origins are

A)the capacities
B)the flows
C)the nodes
D)the arcs

Question 21

The maximal flow problem can be formulated as a capacitated transshipment problem.

Question 22

A transshipment problem is a generalization of the transportation problem in which certain nodes are neither supply nodes nor destination nodes.

Question 23

The shortest-route problem is a special case of the transshipment problem.

Question 24

Transshipment problem allows shipments both in and out of some nodes while transportation problems do not.

Question 25

If a transportation problem has four origins and five destinations,the LP formulation of the problem will have nine constraints.

Question 26

When a route in a transportation problem is unacceptable,the corresponding variable can be removed from the LP formulation.

Question 27

A dummy origin in a transportation problem is used when supply exceeds demand.

Question 28

A transportation problem with 3 sources and 4 destinations will have 7 decision variables.

Question 29

In the general assignment problem,one agent can be assigned to several tasks.

Question 30

The assignment problem is a special case of the transportation problem in which all supply and demand values equal one.

Question 31

A transshipment constraint must contain a variable for every arc entering or leaving the node.

Question 32

Write the LP formulation for this transportation problem.

Question 33

In a transportation problem with total supply equal to total demand,if there are four origins and seven destinations,and there is a unique optimal solution,the optimal solution will utilize 11 shipping routes.

Question 34

Draw the network for this transportation problem.
Min 2X_AX + 3X_AY + 5X_AZ+ 9X_BX + 12X_BY + 10X_BZ
s.t.X_AX + X_AY + X_AZ < 500
X_BX + X_BY + X_BZ < 400
X_AX + X_BX = 300
X_AY + X_BY = 300
X_AZ + X_BZ = 300
X_ij > 0

Question 35

When the number of agents exceeds the number of tasks in an assignment problem,one or more dummy tasks must be introduced in the LP formulation or else the LP will not have a feasible solution.

Question 36

In the LP formulation of a maximal flow problem,a conservation-of-flow constraint ensures that an arc's flow capacity is not exceeded.

Question 37

A transportation problem with 3 sources and 4 destinations will have 7 variables in the objective function.

Question 38

The capacitated transportation problem includes constraints which reflect limited capacity on a route.

Question 39

The direction of flow in the shortest-route problem is always out of the origin node and into the destination node.

Question 40

Flow in a transportation network is limited to one direction.

Question 41

Consider the network below.Formulate the LP for finding the shortest-route path from node 1 to node 7.

Question 42

Show both the network and the linear programming formulation for this assignment problem.

Question 43

RVW (Restored Volkswagens)buys 15 used VW's at each of two car auctions each week held at different locations.It then transports the cars to repair shops it contracts with.When they are restored to RVW's specifications,RVW sells 10 each to three different used car lots.There are various costs associated with the average purchase and transportation prices from each auction to each repair shop.Also there are transportation costs from the repair shops to the used car lots.RVW is concerned with minimizing its total cost given the costs in the table below.
a.Given the costs below,draw a network representation for this problem.

b.Formulate this problem as a transshipment linear programming model.

Question 44

Canning Transport is to move goods from three factories to three distribution centers.Information about the move is given below.Give the network model and the linear programming model for this problem.
Shipping costs are:

Question 45

The following table shows the unit shipping cost between cities,the supply at each source city,and the demand at each destination city.The Management Scientist solution is shown.Report the optimal solution.
TRANSPORTATION PROBLEM
*****************************
OBJECTIVE: MINIMIZATION
SUMMARY OF ORIGIN SUPPLIES
********************************
ORIGIN SUPPLY
---------- -----------
1 100
2 100
3 100
SUMMARY OF DESTINATION DEMANDS
***************************************
DESTINATION DEMAND
------------------- -------------
1 150
2 60
3 45
4 45
SUMMARY OF UNIT COST OR REVENUE DATA
*********************************************
FROM TO DESTINATION
ORIGIN 1 2 3 4
---------- ----- ----- ----- -----
1 8 6 12 9
2 5 5 10 8
3 3 2 9 10
OPTIMAL TRANSPORTATION SCHEDULE
****************************************
SHIP
FROM TO DESTINATION
ORIGIN 1 2 3 4
---------- ----- ----- ----- -----
1 0 10 45 45
2 100 0 0 0
3 50 50 0 0
TOTAL TRANSPORTATION COST OR REVENUE IS 1755

Question 46

Consider the following shortest-route problem involving six cities with the distances given.Draw the network for this problem and formulate the LP for finding the shortest distance from City 1 to City 6.
Path Distance
1 to 2 3
1 to 3 2
2 to 4 4
2 to 5 5
3 to 4 3
3 to 5 7
4 to 6 6
5 to 6 2

Question 47

A beer distributor needs to plan how to make deliveries from its warehouse (Node 1)to a supermarket (Node 7),as shown in the network below.Develop the LP formulation for finding the shortest route from the warehouse to the supermarket.

Question 48

Peaches are to be transported from three orchard regions to two canneries.Intermediate stops at a consolidation station are possible.
Shipment costs are shown in the table below.Where no cost is given,shipments are not possible.Where costs are shown,shipments are possible in either direction.Draw the network model for this problem.

Question 49

The network below shows the flows possible between pairs of six locations.Formulate an LP to find the maximal flow possible from Node 1 to Node 6.

Question 50

Write the linear program for this transshipment problem.

Question 51

A professor has been contacted by four not-for-profit agencies that are willing to work with student consulting teams.The agencies need help with such things as budgeting,information systems,coordinating volunteers,and forecasting.Although each of the four student teams could work with any of the agencies,the professor feels that there is a difference in the amount of time it would take each group to solve each problem.The professor's estimate of the time,in days,is given in the table below.Use the computer solution to see which team works with which project.
ASSIGNMENT PROBLEM
************************
OBJECTIVE: MINIMIZATION
SUMMARY OF UNIT COST OR REVENUE DATA
*********************************************
TASK
AGENT 1 2 3 4
---------- ----- ----- ----- -----
1 32 35 15 27
2 38 40 18 35
3 41 42 25 38
4 45 45 30 42
OPTIMAL ASSIGNMENTS COST/REVENUE
************************ ***************
ASSIGN AGENT 3 TO TASK 1 41
ASSIGN AGENT 4 TO TASK 2 45
ASSIGN AGENT 2 TO TASK 3 18
ASSIGN AGENT 1 TO TASK 4 27
------------------------------------------- -----
TOTAL COST/REVENUE 131

Question 52

A network of railway lines connects the main lines entering and leaving a city.Speed limits,track reconstruction,and train length restrictions lead to the flow diagram below,where the numbers represent how many cars can pass per hour.Formulate an LP to find the maximal flow in cars per hour from Node 1 to Node F.

Question 53

Consider the following shortest-route problem involving seven cities.The distances between the cities are given below.Draw the network model for this problem and formulate the LP for finding the shortest route from City 1 to City 7.
Path Distance
1 to 2 6
1 to 3 10
1 to 4 7
2 to 3 4
2 to 5 5
3 to 4 5
3 to 5 2
3 to 6 4
4 to 6 8
5 to 7 7
6 to 7 5

Question 54

A foreman is trying to assign crews to produce the maximum number of parts per hour of a certain product.He has three crews and four possible work centers.The estimated number of parts per hour for each crew at each work center is summarized below.Solve for the optimal assignment of crews to work centers.

Question 55

Fodak must schedule its production of camera film for the first four months of the year.Film demand (in 1,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.
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 shelflife).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.
a.Modeling this problem as a transshipment problem,draw the network representation.
b.Formulate and solve this problem as a linear program.

Question 56

Find the maximal flow from node 1 to node 7 in the following network.

Question 57

Draw the network for this assignment problem.
Min 10x_1A + 12x_1B + 15x_1C + 25x_1D + 11x_2A + 14x_2B + 19x_2C + 32x_2D
+ 18x_3A + 21x_3B + 23x_3C + 29x_3D + 15x_4A + 20x_4B + 26x_4C + 28x_4D
s.t.x_1A + x_1B + x_1C + x_1D = 1
x_2A + x_2B + x_2C + x_2D = 1
x_3A + x_3B + x_3C + x_3D = 1
x_4A + x_4B + x_4C + x_4D = 1
x_1A + x_2A + x_3A + x_4A = 1
x_1B + x _2B + x_3B + x_4B = 1
x_1C + x_2C + x_3C + x_4C = 1
x_1D + x_2D + x_3D + x_4D = 1