Inverse Problem For A Class Of Generalized Planning Problem

This article discusses the inverse generalized upper bounding problem and generalized maximum flow problems.In the first chapter, we study the inverse generalized upper bounding problem, based on the general inverse linear programming problem we consider the inverse generalized linear programming problem. We need to adjust the cost coefficients of a given generalized upper bounding problem as less as possible so that a known feasible solution becomes the optimal one. Taking advantage of the optimality conditions of linear problem, it is proposed the mathematical model of the generalized inverse (GUB) problems under l₁ norms and l_∞norms and a simple method to solve it. Under l₁ norms, we translate the inverse generalized upper bounding problem into its dual problem to solve it. Especially, we consider the case in which the given feasible solution are 0-1 vectors and one optimal solution of the (GUB) problem has all components between 0 and 1, then the inverse (GUB) problem can be solved very easily.In the second chapter, the generalized maximum flow problem is discussed. Firstly, we present the usual maximum flow problem model. Because in realistic life the network flow contains lower bound constrains, so we present the generalized maximum flow problem model. The modified algorithm of the generalized maximum flow problem is obtained, and a necessary and sufficient condition is given, and translating the inverse generalized maximum flow problem into the minimum cut of its dual problem to solve it.