China
Africa
Explore chapters and articles related to this topic
Network Models and the Network Simplex Algorithm
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
Given an initial basic feasible solution, the only piece missing from our specialized simplex algorithm for networks is the minimum ratio test that determines the leaving variable. The cycle completion method for computing reduced costs shows how to identify the leaving basic variable. When we change the value of the nonbasic variable xij by θ, we also must change the flow on every arc on the path P from i to j by ±θ. As |θ| increases, the flows on the arcs in P and the flow on the arc (i,j) move towards either their upper or lower bounds. The first arc whose flow hits its upper or lower bound leaves the basis. As in the bounded simplex method, the entering arc could be the leaving arc. The minimum ratio test has this particularly simple meaning because the denominator of each ratio is ±1. We can now describe a single iteration of the network simplex algorithm.
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
In some special cases, the problems may become easy. For example, Yan and Tu [27] proposed a pure network flow model for crew pairing in Taiwan’s China Airlines where much fewer constraints are needed. They used the network simplex algorithm to solve the problem. There are also some other approaches that do not belong to conventional mathematical programming techniques, such as the simulated annealing algorithm proposed by Emden-Weinert and Proksch [28] and the genetic algorithms proposed by Levine [29] and Ozdemir and Mohan [30].
Introduction
Published in Hassan Rashidi, Edward P. K. Tsang, Port Automation and Vehicle Scheduling, 2023
Hassan Rashidi, Edward P. K. Tsang
The Network Simplex Algorithm (NSA) is the fastest solution for the MCF model. We apply it to the scheduling problem of AGVs in the port. We then extend the NSA in both static and dynamic aspects. These extensions are the Network Simplex plus Algorithm (NSA+), the Dynamic Network Simplex Algorithm (DNSA), and the Dynamic Network Simplex plus Algorithm (DNSA+). To solve the problems, NSA and NSA+ start from scratch, whereas DNSA and DNSA+ repair solutions when the changes occur.
A synthetic water distribution network model for urban resilience
Published in Sustainable and Resilient Infrastructure, 2022
Nasir Ahmad, Mikhail Chester, Emily Bondank, Mazdak Arabi, Nathan Johnson, Benjamin L. Ruddell
where t is the length of period for which peak demand is required (days). From Equation 1 the hourly peak demand was 247% of average daily demand, thus, multiply the average daily demand by 2.47 to obtain the hourly peak demand. As synthesizing storage tanks or storage requirements for fire flow is not a scope of SyNF; thus, we do not explicitly consider fire flow demand for this model. However, the general peak demand factor of 2.47 is well above the factor (i.e., 1.70) recommended by the city of Phoenix (City of Phoenix, 2020b). Finally, the network simplex algorithm (Király & Kovács, 2012; Orlin, 1997) is applied to calculate the flow through pipes that satisfy the requirement at each node. The network simplex algorithm is the graph-theoretic version of the simplex linear optimization algorithm. In many WDN studies, flow in pipes is calculated by modeling a network in EPANET (US EPA, 2014) the state-of-the-art software model developed by the United States environmental protection agency. EPANET requires water pipe diameter as a fundamental input into the model, which can be obtained from the SyNF.
Military Human Resource Planning through Flow Network Modeling
Published in Engineering Management Journal, 2022
Oussama Mazari Abdessameud, Filip Van Utterbeeck, Marie-Anne Guerry
The network simplex–algorithm is a general algorithm to solve network problems using linear programming. Bazaraa et al. (2009) illustrate how to use it for minimum cost network flows. Despite the fact that this algorithm can solve such problems, it should be adapted to generate an adequate solution for our model. The network simplex–algorithm handles balanced flow network problems, which is not always the case for the HR situation. Therefore, we employ goal programming that can handle the discrepancies between the demand and the available flow. Moreover, a common technique in HR planning is the use of goal programming to reach the multiple goals and objectives targeted by the organization.