Random Linear Programs.
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Pagination or Media Count:
In this paper, we study the random generation of a linear program of the type P Max cx subject to Ax or b. We assume these random variables to be independent and symmetric around zero and to have continuous distribution functions, therefore, transforming the random generation problem into a distribution free combinatorial problem. Making use of the theory of d-Arrangements, we compute the probabilities of P being feasible and bounded, and we also calculate the expected number of faces, of all possible dimensions, of the polytope that is the feasibility set of P, given that P is feasible.
- Operations Research