University of Southern California



University of Southern California

Daniel J. Epstein Department of Industrial and Systems Engineering

ISE 330: Introduction to Operations Research

Final Review

Instructor: Elaine Chew

Minimum Spanning Tree Problem

Minimum Spanning Tree Problem and Shortest Path Problem

■ start with an undirected, connected network, with positive cost for each link

■ choose a subset of links that gives shortest total length

Requirement:

■ MST: chosen links must provide a path between each pair of nodes

■ SP: chosen links must provide a path between origin and destination

Definition: A spanning tree is a connected network of the n nodes that contains no undirected cycles.

Property: A network with n nodes requires only ( n – 1 ) links to provide a path between each pair of nodes.

A greedy algorithm for the MST problem

1. Select any node arbitrarily, then connect it to the nearest distinct node.

2. Identify unconnected node closest to a connected node, add arc to network.

3. Ties are broken arbitrarily. Ties may indicate multiple optimal solutions.

Maximum Flow Problem

The Maximum Flow Problem:

■ All flow through the directed, connected network originates from one node, (source); and, terminates at one other node ( sink). All remaining nodes are called transshipment nodes.

■ Directed arcs indicate flow direction, maximum flow is given by arc capacity. At source, all arcs point away; at sink, all arcs point into node.

■ Objective: maximize total flow from source to sink. Amount leaving source is equal to amount entering sink.

In some applications, flow originates at more than one node and terminate at more than one node. Add dummy source/sink in such cases.

Solution Methods:

■ Formulate as an LP and use the Simplex Method.

■ Augmented Path Algorithm

Definition 1: After some flows have been assigned to the arcs, the residual network shows the remaining arc capacities (called residual capacities) for assigning additional flows.

Definition 2: An augmented path is a directed path from the source to the sink in the residual network such that ievery arc on this parth has strictly positive residual capacity. The minimum of these residual capacities is called the residual capacity of the augmenting path.

The Augmented Path Algorithm for the Maximum Flow Problem:

1. Identify an augmenting path by finding some directed path from source to sink in the residual network s.t. every arc on this path has residual capacity>0.

2. Identify the residual capacity c* of this augmenting path by finding the minimum of the residual capacities of the arcs on this path. Increase flow in this path by c*.

3. Decrease by c* the residual capacity of each arc on this augmenting path. Increase by c* the residual capacity of each arc in the opposite direction on this augmenting path. Return to step 1.

Finding an augmenting path: Breadth-first search ( fanning-out procedure ).

How to know when we’re done? -- no more augmenting path exist.

Max-flow min-cut theorem: For any network with a single source and sink, the maximum feasible flow from the source to the sink equals the minimum cut value for all cuts of the network.

Minimum Cost Flow Problem

The Minimum Cost Flow Problem:

1. Considers a directed and connected network.

2. Nodes: At least one node is a supply node. At least one other node is a demand node. Remaining nodes are transshipment nodes.

3. Arcs are directed with capacities. Cost of flow through each arc is proportional to the amount of flow, cost per unit known.

4. A feasible solution exists: the network has sufficient capacity to enable all the flow generated at the supply nodes to reach all the demand nodes.

5. Objective: minimize total cost of sending available supply through network to satisfy demand.

Linear Programming Formulation:

xij = flow through arc (i,j)

cij = cost per unit flow through arc (i,j)

uij = arc capacity for arc (i,j)

bi = net flow generated at node i

Feasible Solutions Property: A necessary condition for a minimum cost flow problem to have any feasible solutions is that the total flow being generated at the supply nodes equals the total flow being absorbed at the demand nodes.

Integer Solutions Property: For minimum cost flow problems where every bi and uij have integer values, all the basic variables in every basic feasible solution (including the optimal one) also have integer values.

The Network Simplex Method

We use the upper bound technique to deal efficiently with upper bound constraints, xij ≤ uij. Whenever a nonbasic variable is at its upper bound, xij = uij, the slack variable yij = uij – xij = 0 becomes the nonbasic variable. Reverse flow of arc, and negate the cost.

Network representation of BFS: Every BFS has (n – 1) basic variables, where each basic variable xij represents the flow through arc i ( j. The (n – 1) arcs are referred to as basic arcs. The arcs corresponding to the nonbasic variables xij = 0 or yij = 0 are called nonbasic arcs.

Note: Any complete set of (n – 1) basic arcs forms a spanning tree.

To obtain as spanning tree solution:

1. For arcs not in the spanning tree, set xij = 0 or yij = 0.

2. For arcs in the spanning tree, solve for xij or yij in the system of linear equations derived from the node constraints.

A feasible spanning tree is a spanning tree whose solution from the node constraints also satisfies all the other constraints ( 0 ( xij ( uij or 0 ( yij ( uij).

Fundamental Theorem for the network simplex method: Basic solutions are spanning tree solutions and that BFS are solutions for feasible spanning trees. The converse is also true.

Goal: To select the incoming variable that improves Z at the fastest rate…

Nonbasic Arc Cycle Created (Z when ( = 1

To select the leaving basic variable, find the variable that first reaches its lower or upper bound as ( increases.

A Transportation Problem

Requirements Assumption: Each source has a fixed supply of units, si, where the entire supply must be distributed to he destinations. Each destination has a fixed demand for units, dj, and the entire demand must be received from the sources.

Feasible Solutions Property: A transportation problem will have feasible solutions if and only if sum of supplies equals sum of demands.

Cost Assumption: The cost of distributing units from any particular source to any particular destination, cij, is directly proportional to the number of units distributed, xij.

The model: Any transportation model can be described completely by a parameter table…

| |Cost per Unit Distributed |Supply |

| |Destination | |

| |1 |2 |… |n | |

| |1 |c11 |c12 |… |c1n |s1 |

|Source |2 |c21 |c22 |… |c2n |s2 |

| | |: |: | |: |: |

| |3 |cm1 |cm2 |… |cmn |sm |

|Demand |d1 |d2 |… |dn | |

The LP Formulation of the Problem…

Integer Solutions Property: For transportation problems where every si and dj have integer values, all the basic variables in every BFS also have integer values.

The Transportation Simplex Method

Format of a transportation simplex tableau:

If x i j is basic… If x i j is nonbasic…

Constructing an Initial BFS:

[1] From rows and columns still under consideration, select the next basic variable (allocation) according to some criterion*.

[2] Make allocation large enough to use up remaining supply in row or remaining demand in column (whichever is smaller).

[3] Eliminate that row or column from further consideration. (Break ties arbitrarily.)

[4] If only one row or only one column remains under consideration, then complete procedure by selecting every remaining variable associated with that row or column to be basic with the only feasible allocation. Otherwise, return to [1].

*For step [1]: the methods are…

Northwest corner rule: Begin by selected x11. Thereafter, if xij was the last basic variable selected, then next select xi,j+1 (one column to the right) if source i has any supply remaining. Otherwise, next select xi+1, j (one row down).

Vogel’s approximation method: For each row and column remaining under consideration, calculate its difference, the arithmetic difference between the smallest and next-to-the-smallest unit cost cij still reamining in that row or column. In that row or column having the largest difference, select the variable having the smallest remaining unit cost.

Russel’s approximation method: For each source row i remaining under consideration, determine its ui, the largest unit cost cij still remaining in that row. For each destination column j remaining under consideration, determine its vj, which is the largest unit cost cij still remaining in that column. For each variable xij not previously selected in these rows and columns, calculate (ij = cij – ui – vj. Select the variable having the largest (in absolute terms) negative value of (ij.

The Transportation Simplex Method

Initialization: Construct an initial BFS by the procedure outlined above.

Optimality Test: Derive ui and vj by selecting the row having the largest number of allocations, setting its ui = 0, then solving the set of equations cij = ui + vj for each (i,j) such that xij is basic. If cij – ui – vj ( 0 for every (i,j) such that xij is nonbasic, then the current solution is optimal.

Iteration:

1. Determine the entering basic variable: Select the nonbasic variable xij having the largest (in absolute terms) negative value of cij – ui – vj.

2. Determine the leaving basic variable: Identify the chain reaction required to retain feasibility when the entering basic variable is increased. From the donor cells, select the basic variable having the smallest value.

3. Determine the new BFS: Add the value of the leaving basic variable to the allocation for each recipient cell. Subtract this value from the allocation for each donor cell.

The Assignment Problem Definition

1. The number of assignees and the number of tasks are the same, n.

2. Each assignee is to be assigned to exactly one task.

3. Each task is to be performed by exactly one assignee.

4. There is a cost cij associated with assignee i (i = 1,2,…,n) performing task j (j = 1,2,…,n).

5. The objective is to determine how all n assignments should be made to minimize the total cost.

Solution Procedure 1: Simplex Method – dummy not necessary

Solution Procedure 2: Transportation Simplex Method

Drawbacks of using the transportation simplex method:

[1] Number of degenerate basic variables and wasted iterations.

[2] Does not exploit the additional structure of the assignment problem.

-----------------------

cij

cij – ui – vj

xij

cij

5

B

O

2

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download