On the more-for-less paradoxical situations in linear programs: A parametric optimization approach

Abstract

A curious property called the more(same)-for-less (MFL) phenomenon is associated with some classical transportation problems (CTP) described as follows: Given an optimal solution, is it possible to find a lower (or equivalent) cost solution by shipping more total goods under the restriction that we ship at least the same amount from each origin and to each destination and all shipment costs are non-negative? Although MFL in CTP is not a rare event, it can also occur in TP with mixed constraints and in general LP. The existing literature has demonstrated the practicality and value of identifying cases where the paradoxical situation exists for these three problems. However, each problem is treated differently, after solving the nominal optimization problem, and finding the optimal amount of MFL is left to trial and error. This paper proposes a prior approach using a right-hand-side (RHS) parametric formulation of the nominal problem to identify and resolve the paradoxical situation in systematic and algorithmic treatments which are the same for all the three types problems. Using this unified approach one can first find the paradoxical solution (if it exists) and then be positioned to solve the nominal problem. Moreover, the proposed all-RHS parametric approach provides the necessary information to perform all types of sensitivity analysis. Under the proposed approach the elaborate theorems that support the existing posterior approaches fall out as a by-product. For comparison purposes, the methodology is discussed while applying it to some published problems solved by other methods.