Abstract FR:

My thesis focusses on two applications of network flow problems. We emphasize on networks modelling energy or fluid distribution and telecommunication services. We study two differents aspects:The first aspect consists of the sensitivity analysis of flows in distribution networks. That is the analysis of the effects of one or more capacity variations on the all pairs maximum flow values. Moreover, we evaluate the importance of an edge in the network. Our contributions begin with a correction of the unique method in the literature that dealed with the case of a single capacity variation. We then propose simple and efficient algorithms to solve the same case, before proposing a generalization to the case of more than one capacity variation. Our algorithms and methods are based on Gomory-Hu cut trees. Given an undirected network in which capacities lambda_1, \lambda_2, \lambda_3, \ldots \lambda_k are varying. We show that ^k Gomory-Hu cut tree computations are sufficient in order to determine the all pairs maximum flow values. As far as link importance analysis is concerned, we show that two Gomory-Hu cut tree computations are sufficient to determine the set of all vertex pairs for which any maximum flow saturates the studied link. The second aspect concerns resource allocation in a telecommunicationnetwork with an objective of demands satisfaction. To do so, we study this problem using pricing in order to handle network congestion while taking into account users behaviour and the operator's profit maximization objective. We use a bi-level programming approach to solve the problem. With an Augmented Lagrangian method, we solve the resource allocation problem by associating the Lagrangian multipliers to the network link prices. We then use the Karush-Kuhn-Tucker optimality conditions to verify about the multipliers (prices) unicity. In case the multipliers are not unique, we show that a second optimization problem over the multipliers (prices) can be solved in order to improve the network revenu.