Analyzing the solution of a linear program: the effect of normal distributions in costs and constraints

Suppose the optimization of distribution network can be modeled as a Linear Program. This work considers multivariate normally distributed cost and constraint vectors. A method is developed to compare alternative basic solutions on optimality, feasibility and outliers. The basic solution is used instead of the full problem because of the corresponding invertible data matrix. This work contributes in four ways. First, an overview is provided of methods that optimize Linear Programs under uncertainty or analyze its solution. As no current method has the desired properties, requirements for such a method are stated. Second, expressions are derived for normal distributions in the cost and constraint vectors. These provide probabilities for optimality, feasibility and outliers for a solution of a Linear Program. In that way, the robustness of a solution can be determined. Third, a method is developed to systematically evaluate solutions of a Linear Program for varying costs and constraint values. This method provides a comprehensive approach to compare alternative solutions on optimality, feasibility and outliers. Finally, the method is applied to a small test case and a real world fuel distribution test case. The results show that the obtained basic solution is robust and outperforms the alternative basic solutions under changes in the demand for fuel.