Introduction
Within this research, the objective of defining each of the network models was raised, starting from the most basic concepts such as the definition of what a node would be, which are the vertices used within a network model, an arc that could be the arrow or the connector of each node within the network, also the considerations to take to understand the structure of a network, such could be as the directions that the arcs take, they can be direct or indirect.
Once we have understood the terminologies of the parts that make up the networks, we continue with what each of the models would be, the first could be a node-arc incidence matrix that would be a table that represents a model in the network, the tree technique of minimum expansion, the steps that must be followed to carry it out, the maximum flow technique, the technical steps, the shortest route technique and other network models that would be, transportation problems, shortest path problems, critical path in network project planning, least-cost flow problem, sensitivity analysis for network models, vendor travel problem, also using some examples so that the issues can be clearer.
All of these topics are explained in more detail and with better understanding within the document.
Network Models
A network model is a transshipment model with capacities, which can take various forms, such as the shortest route model and the maximum and minimum flow model, the minimum reach tree problem, critical path method, among other applications of financial and production planning.
The main characteristic of a transshipment model with capacities is that it is a network where the offers are in the specific points of origin, the demands in the specific points of destination and the shipping alternatives are offered through intermediate nodes, so that follow routes with defined capabilities from origins to destinations.
Network terminology
A network is made up of a set of nodes joined by arcs (or branches). The notation to describe a network is (N, A), where N is the set of nodes, and A is the set of arcs.
N = {1, 2, 3, 4, 5}
A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5) }
Below is a diagram of the network and its main components.
Technological network models
What is a Node?
It is usually called a vertex, or point. It is usually represented by a circle. In transportation networks, these should be towns or cities on a map.
What is an Arch?
It is usually called a border or arrow. This could be direct or indirect. The head is the destination, and the tail the origin. The head and tail are nodes that can be both at the origin and at the end. In transportation networks, the arcs could be roads, navigation channels in a river, or the flight patterns of an airplane. The arcs provide the connectivity between the nodes. A one-way street could be represented by an arc, while a two-way street could be represented by a directionless arc or by two arcs pointing in opposite directions. A network with n nodes could have as many arcs as n! / = n (n-1) / 2. If targeted, this number could double.This enormous number of possible arcs is one of the reasons why there are special algorithm solutions for particular network problems.
In the network node you will commonly find a number with a positive or negative sign, which denotes the supply (+) and the demand or requirements (-) of the node.
A path is a set of arcs that join two different nodes, and that pass through other nodes in the network. For example, in Figure 1, arcs (1,2), (2,3), (3,4), and (4,5) form a path between nodes 1 and 5. A path forms a loop or a loop if you connect a node back to itself through other nodes. In figure 6.1, arcs (2,3), (3,4), and (4,2) form a cycle.
Important considerations:
- One-way arrows / lines are direct arcs. Lines with flow for both directions are indirect arcs. A network that has only direct arcs is a direct network. A network that has arcs in both directions is an indirect network. A direct path from node i to j is a sequence of connected arcs, so a flow that passes through that path is feasible An indirect path from node i to j is a sequence of connected arcs, whose direction is i and vice versa A path that begins and ends at the same node is a loop. If the network contains at least one direct path between 2 nodes, they are said to be connected. To determine which of the network routes will be chosen, we must consider the costs and capacities along the route of the routes.
Network Models Version 1
Node - arc incidence matrix
It is a table to represent the data of the constraints in a network model. Each arc of the network corresponds to a column of the table. Each node in the network corresponds to a row in the table. The columns only have two nonzero entries: +1 and -1.
Technological network models
Once we have raised the linear programming model, we must find the solution that linear programming, we must find the solution that optimizes the objective function.
- We can use some linear programming software like SOLVER or LINDO to find the optimal solution.
Closing
- The terminology and procedure for drawing a network will help you apply the optimization models, since when looking at Illustration 3 it is much easier to identify the shortest or longest path, etc.
Network model version 2
Minimum spanning tree technique
This tree links the nodes of a network using the minimum total length of the connecting branches. A common application is presented in the paving of roads that connect towns, or directly, or that pass through other towns. The least spanning tree solution provides the design of the road system.
Steps Minimum Spanning Tree Technique
- Select any node on the network. Connect this node to the closest node that minimizes the total distance. Considering all nodes that are now connected, find and connect the closest node that is not connected. If there is a tie for the closest node, select one arbitrarily. A tie suggests that there may be more than one optimal solution. Repeat the third step until all nodes are connected.
Example
Roxie LaMothe who owns a large horse breeding farm near Orlando plans to install a water system that connects all the stables and barns. The location of the facilities and the distances between them are shown in the following figure. Roxie must determine the cheapest way to supply water to each facility.
Technological network models
The Peak Flow Technique
- The peak flow technique determines the most that can flow through a network.
4 steps of the peak flow technique
- Pick any path from start (original) to end (destination) with some flow. If there is no flow path, then the optimal solution has been reached. Locate the arc of the path with the smallest available flow capacity. Call this capacity C. This represents the maximum additional capacity that can be allocated to this path. For each node on this path, decrease the flow capacity in the direction of flow by the amount C. For each node on this path, increase the capacity flow in the reverse direction by quantity C.
Repeat these steps until it is no longer possible to increase the flow.
Example
PetroChem, an oil refinery located on the Mississippi River south of Baton Rouge, Louisiana is designing a new plant to produce diesel fuel. Figure 5 shows the network of the main processing centers together with the existing flow rate. Management would like to determine the maximum amount of fuel that can flow through the plant, from node 1 to node 7.
Technological network models
Shortest path technique
This problem determines the shortest route between a source and a destination in a transportation network.
Steps of the shortest path technique
- Find the node closest to the origin. Put the distance in a box next to the node Find the next closest node to the origin (plant) and put the distance in a box next to the node. In some cases, multiple paths will have to be reviewed to find the closest node - repeat the process until you have traversed the entire network. The last distance at the end node will be the distance of the shortest path. Note that the distance placed in the box next to each node is the shortest path to this node. These distances are used as intermediate results to find the next closest node.
Example:
RentCar is developing a replacement policy for its fleet of cars on a 4-year planning horizon. At the beginning of each year, a car is replaced or kept in operation for one more year. A car should be in service for 1 to 3 years. The following table provides replacement cost as a function of the year a car is purchased and the years in operation.
Technological network models
The problem can be formulated as a network in which nodes 1 to 5 represent the beginning of years 1 to 5. The arcs from node 1 (year 1) can reach nodes 2, 3 and 4 because a car can be in operation for 1 to 3 years. The arcs from the other nodes can be interpreted in the same way. The length of each arch equals the replacement cost. Solving the problem is equivalent to determining the shortest path between nodes 1 and 5.
Illustration 6 shows the resulting network. Using TORA, 2 the shortest path is 1 S3 S5.
The solution indicates that a car purchased at the beginning of year 1 (node 1) must be replaced after 2 years at the beginning of year 3 (node 3). The replacement car will then remain in service until the end of year 4. The total cost of this replacement policy is $ 12,500.
(= $ 5400 + $ 7100).
Technological network models
Networking model version 3
Network Model Types
The network family of optimization problems includes the following model prototypes: Assignment problems, critical path, maximum flow, shortest path, transport and minimum cost of flows. Problems are easily established through the use of network arcs and nodes.
Transportation problems
Transportation models play an important role in logistics management and in the supply chain to reduce costs and improve services. Therefore, the goal is to find the most cost-effective way to transport goods. A distributor that has “m” warehouses with a supply of products to iith in them, must send said products to geographically dispersed retail centers, each one with a given customer demand eg, which must be covered. The objective is to determine the lowest possible transport cost given the costs per unit of transporting between the ith warehouse and the j Th retail center, which is Cij.
Shortest Path Problems
The problem is determining the best way to cross a network to find the cheapest way possible from one origin to a given destination. Suppose that in a given network there are m nodes and n arcs (edges) and a cost Cij associated with each arc (iaj) in the network. Formally, the shortest path (CC) problem is to find the shortest path (least cost) from starting node 1 to ending node m. The cost of the road is the sum of the costs of each arc traveled. Define the binary variables Xij, where Xij = 1 if the arc (iaj) is on the CC and Xij = 0 otherwise. There are two special nodes called source and destination. The goal is to find the shortest path between origin and destination.
Critical Path in Network Project Planning
Successful management of an ambitious project, be it construction, transportation, or finance, relies on careful coordination and planning of various tasks. The Critical Path (or Path) Method (CCM) attempts to analyze project planning. This enables better control and evaluation of the project. For example, we want to know how long will the project last? When will a particular task be ready to start? If the task is not completed on time, Will the rest of the project be delayed?
What tasks must be accelerated (effective) in order to finish the project earlier?
Minimum Cost Flow Problem
All of the above network problems are special cases of the minimal cost flow problem. Like the peak flow problem, it considers flows in networks with capabilities. Like the shortest path problem, this one considers a cost per flow to an arc. Like the transportation problem, it allows for multiple origins and destinations. Therefore, all these problems can be seen as special cases of the minimum cost flow problem. The problem is to minimize the total cost subject to the availability and demand of some nodes, and of the upper connection of flow through each arc.
Sensitivity Analysis for Network Models
The family of a classic network optimization problem includes the following model prototypes: allocation, critical path, maximum flow, shortest path, and transport. Although it is well known that these types of problems can be modeled as linear programming, they are usually never done. Due to the inefficiency and relative complexity of the simplex method (primal, dual, and other variations) for network models, this problem is handled by one of more than 400 special algorithms. This leads to many difficulties. The solutions of the algorithms are not unified and each algorithm uses a different strategy to explore the special structure of a specific problem. Additionally, small variations in the problem such as the addition of a separate constraint, or multiple indices,destroys the special structure and forces the algorithm to restart. Furthermore, these algorithms obtain efficient solutions at the cost of managerial cunning, as the final solution of these algorithms that do not have enough information to perform a sensitivity analysis.
The Seller's Travel Problem
A vendor must visit cities 1, 2,.. N, and his journey begins and ends in Hometown. Let Cij be the cost of traveling city and city j, which is given. The problem is to determine an optimal order to travel the cities in such a way that the cost is minimal. The maximization of flows is a typical problem in Operations Research, which has many applications, for example the road flow in a city, a sewage network, a computer network, etc.
conclusion
To conclude we can say that the arcs are the connectors of nodes within each network, these models can have a direct or indirect address, that within each network there may be multiple connectors that serve to unite several nodes and thus create routes, within each network there are cycles that join nodes outside the original path.
The models can be represented by network programs, those of the second version such as the minimum spanning tree technique is used for cases that are short distances or small routes, the maximum flow technique determines how much is the most that can flow Within a network, the shortest path technique helps us determine the shortest path from our node of origin and our transport path.
Network models have a common use in certain work aspects and that thanks to them we can solve problems, and they can be developed in different areas, facilitating the routes that best suit them.
Hopefully this article is very useful and that the concepts contained are clearly explained.
References
- Hillier, F., Lieberman, G. (2006). Introduction to operations research. (8th Ed.) Mexico. McGraw Hill. ISBN 970-10-5621-3Oc, F, (2010), Models of networks-Investigation of Operations, recovered from http://www.slideshare.net/FreddOc/modelos-de-redes-investigacin-de-operacionesTaha, HA (2012), Investigation of Operations, (9th Ed.), Mexico, Pearson Education. ISBN: 978-607-32-0796-6 Raffo, E. (1990), Investigation of Operations, Lima, Raffo Lecca Editores, Library Code: 658.4034 / T16
