On the set of all optimal solutions in network programming

It is shown that set of optimal solutions (primal and dual) in network programming is in 1-1 correspondence with the set of feasible solutions of a new graph with adjusted parameters. The new graph is obtained from the original one by certain matroid operations: deletion, contraction and reversing the direction of edges. Optimization of a linear objective function over the set of optimal solutions turns out to be another network programming problem. The maximum value of the reduced cost of an edge over the set of all dual optimal solutions is equal to increase in the objective function value when the same edge is forced to have a positive flow. Moreover the above value can be calculated by solving a shortest path problem over the new graph.