New version page

TTU ISQS 5343 - Network programming

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

Network ModelsContextObjectivesPowerPoint Presentation6.1 Introduction6.1 Introduction, Cont’dNetwork TerminologySlide 8Network models vs. Linear programming models6.2 The Transportation ProblemSlide 11CARLTON PHARMACEUTICALSSlide 13Slide 14The Linear Programming ModelSlide 16The complete mathematical modelSlide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28MONTPELIER SKI COMPANY Using a Transportation model for production schedulingSlide 30Slide 31Slide 32Slide 33Slide 34Slide 35Problem 4-25Slide 37Slide 38Slide 39Slide 406.3 The Assignment ProblemBALLSTON ELECTRONICSSlide 43NETWORK REPRESENTATIONSlide 45Slide 466.5 The Shortest Path ProblemSlide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 546.6 The Minimal Spanning TreeSlide 56Slide 57Slide 58Slide 59Slide 606.7 The Maximal Flow ProblemSlide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 716.4 The Traveling Salesman ProblemSlide 73THE FEDERAL EMERGENCY MANAGEMENT AGENCYSlide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 831NetworkNetworkModelsModelsContext•Mathematical programming–Linear programming – Supp to Chap 14–Integer programming–Network programming – Suppl to Chap 11–Nonlinear programming–Geometric programming–Dynamic programming23 Objectives•Network concepts and definitions.•Importance of network models.•Linear programming models, network representations, and computer solutions for–Transportation models. (Production scheduling)–Capacitated transshipment models.–Assignment models.–Shortest path models.–Minimal spanning tree models.–Maximum flow models.–Travelling salesman models.--CONTROVERSIAL4A network problem is one that can be represented by...NodesArcs89101076Function on Arcs56.1 Introduction–Many business problems lend themselves to a network formulation. –Optimal solutions of network problems are guaranteed integer solutions, because of their special mathematical structures. No special restrictions are needed to ensure integrality –Network problems can be efficiently solved fast by compact algorithms due to their special mathematical structure, even for large scale models. • The importance of network models66.1 Introduction, Cont’d–WINQSB provides the specialized algorithms necessary to get fast solutions–These models can be solved as LP models within SOLVER say but solutions could take some time for large models7• Network Terminology–Flow : the amount sent from node i to node j, over an arc that connects them. The following notation is used:Xij = amount of flowUij = upper bound of the flowLij = lower bound of the flow–Directed/undirected arcs : when flow is allowed in one direction the arc is directed (marked by an arrow). When flow is allowed in two directions, the arc is undirected (no arrows).–Adjacent nodes : a node (j) is adjacent to another node (i) if an arc joins node i to node j.8•Path / Connected nodes–Path :a collection of arcs formed by a series of adjacent nodes. –The nodes are said to be connected if there is a path between them.•Cycles / Trees / Spanning Trees –Cycle : a path starting at a certain node and returning to the same node without using any arc twice.–Tree : a series of nodes that contain no cycles.–Spanning tree : a tree that connects all the nodes in a network ( it consists of n -1 arcs).9Network models vs. Linear programming models•Every network model has an underlying linear programming model•For every node there is exactly one constraint•For every arc there is one decision variable Xij, where i is the starting node and j is the ending node106.2 The Transportation Problem Transportation problems arise when a cost-effective pattern is needed to ship items from origins that have limited supply to destinations that have demand for the goods.11• Problem definition – There are m sources. Source i has a supply capacity of Si. – There are n destinations. The demand at destination j is D j. – Objective: Minimize the total shipping cost of supplying the destinations with the required demand from the available supplies at the sources.12CARLTON PHARMACEUTICALS•Carlton Pharmaceuticals supplies drugs and other medical supplies.•It has three plants in: Cleveland, Detroit, Greensboro.•It has four distribution centers in: Boston, Richmond, Atlanta, St. Louis.•Management at Carlton would like to ship cases of a certain vaccine as economically as possible.13•Data–Unit shipping cost, supply, and demand•Assumptions–Unit shipping cost is constant.–All the shipping occurs simultaneously.–The only transportation considered is between sources and destinations.–Total supply equals total demand.To From Boston Richmond Atlanta St. Louis Supply Cleveland $35 30 40 32 1200 Detroit 37 40 42 25 1000 Greensboro 40 15 20 28 800 Demand 1100 400 750 750To From Boston Richmond Atlanta St. Louis Supply Cleveland $35 30 40 32 1200 Detroit 37 40 42 25 1000 Greensboro 40 15 20 28 800 Demand 1100 400 750 75014NETWORK REPRESENTATION BostonRichmondAtlantaSt.LouisDestinationsSourcesClevelandDetroitGreensboroS1=1200S2=1000S3= 800D1=1100D2=400D3=750D4=75037404232354030253515202815• The Linear Programming Model –The structure of the model is:Minimize <Total Shipping Cost>ST[Amount shipped from a source] = [Supply at that source][Amount received at a destination] = [Demand at that destination]–Decision variablesXij = amount shipped from source i to destination j.where: i=1 (Cleveland), 2 (Detroit), 3 (Greensboro) j=1 (Boston), 2 (Richmond), 3 (Atlanta), 4(St.Louis)16 BostonRichmondAtlantaSt.LouisD1=1100D2=400D3=750D4=750The supply constraintsCleveland S1=1200X11X12X13X14Supply from Cleveland X11+X12+X13+X14 = 1200DetroitS2=1000X21X22X23X24Supply from Detroit X21+X22+X23+X24 = 1000GreensboroS3= 800X31X32X33X34Supply from Greensboro X31+X32+X33+X34 = 80017• The complete mathematical modelMinimize 35X11+30X12+40X13+ 32X14 +37X21+40X22+42X23+25X24+ 40X31+15X32+20X33+38X34STSupply constrraints:X11+ X12+ X13+ X14 1200 X21+ X22+ X23+ X24 1000X31+ X32+ X33+ X34 800Demand constraints: X11+ X21+ X31 1000X12+ X22+ X32 400X13+ X23+ X33 750 X14+ X24+ X34 750All Xij are nonnegative=======18Excel Optimal SolutionCARLTON PHARMACEUTICALS UNIT COSTSBOSTON RICHMOND ATLANTA ST.LOUIS SUPPLIESCLEVELAND 35.00$ 30.00$

View Full Document
Download Network programming
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...

Join to view Network programming and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Network programming 2 2 and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?