Network Simplex Metod网络单纯形法.pptVIP

Network Simplex Method Fatme Elmoukaddem Jignesh Patel Martin Porcelli Outline Definitions Economic Interpretation Algebraic Explanation Initialization Termination Transshipment Problem Find the cheapest way to ship prescribed amounts of a commodity from specified origins to specified destinations through a transportation network Network A network is a collection of nodes connected by arcs Each node has a demand for the commodity Nodes that are sources of the commodity have a negative demand The sum of all the demands is zero Each arc has a cost to ship a unit of commodity over it Example Schedule A schedule describes how much of the commodity is shipped over each arc Requirements The amount entering a node minus the amount leaving it is equal to its demand The amount shipped over any arc is nonnegative Example LP Formulation Let c be a row vector and x a column vector indexed by the set of arcs cij is the cost of shipping over ij xij is the amount to ship over ij Let b be a column vector indexed by the set of nodes bi is the demand at i Example LP Formulation LP Formulation (2) Let A be the matrix indexed by the set of nodes x the set of arcs Ai,jk is either -1 if i=j 1 if i=k 0 otherwise A is known as the incidence matrix of the network Example LP Formulation (2) Tree Solution A spanning tree of a network is a network containing every node and enough arcs such that the undirected graph it induces is a tree A feasible tree solution x associated with a spanning tree T is a feasible solution with xij = 0 if ij is not an arc of T Network Simplex Method Search through feasible tree solutions to find the optimal solution Has a nice economic interpretation Economic Interpretation Given a spanning tree T and an associated feasible tree solution x Imagine you are the only company that produces the commodity What price should you sell the commodity for at each node? Assume that you ship according to x Price Setting You want to set the price yi at node i For all ji in T, yi