Date of Award

3-2002

Document Type

Thesis

Degree Name

Master of Science

Department

Department of Aeronautics and Astronautics

First Advisor

Curtis H. Spenny, PhD

Abstract

In this work goal programming is used to solve a minimum cost multicommodity network flow problem with multiple goals. A single telecommunication network with multiple commodities (e.g., voice, video, data, etc.) flowing over it is analyzed. This network consists of: linear objective function, linear cost arcs, fixed capacities, specific origin-destination pairs for each commodity. A multicommodity network flow problem with goals can be successfully modeled using linear goal programming techniques. When properly modeled, network flow techniques may be employed to exploit the pure network structure of a multicommodity network flow problem with goals. Lagrangian relaxation captures the essence of the pure network flow problem as a master problem and sub-problems (McGinnis and Rao, 1977). A subgradient algorithm may optimize the Lagrangian function, or the Lagrangian relaxation could be decomposed into subproblems per commodity; each subproblem being a single commodity network flow problem. Parallel to the decomposition of the Lagrangian relaxation, Dantzig-Wolfe decomposition may be implemented to the linear program. Post-optimality analyses provide a variety of options to analyze the robustness of the optimal solution. The options of post-optimality analysis consist of sensitivity analysis and parametric analysis. This mix of modeling options and analyses provide a powerful method to produce insight into the modeling of a multicommodity network flow problem with multiple objectives.

AFIT Designator

AFIT-GSE-ENY-02-1

DTIC Accession Number

ADA401509

Comments

Co-authored thesis.

Download

Share

COinS