OnR.W. Llewellyn's rules to identify redundant constraints: A detailed critique and some generalizations

Abstract

In his book “Linear Programming” [1964]Llewellyn devoted a chapter to simplifications and reductions of a linear programming problem by means of algebraic rules. These rules are claimed to be rather general. Here we give some counterexamples, where the rules ofLlewellyn do not hold. Furthermore we give some general rules to identify redundant constraints in the caseLlewellyn considers and show that the original rules ofLlewellyn together with an extra condition are a variant of these general rules. Finally we consider the question whether or not the rules ofLlewellyn should be used to identify redundant constraints.

Zusammenfassung

Bereits 1964 hat sichLlewellyn in seinem Buch „Linear Programming“ mit der Vereinfachung von linearen Programmen durch Ermittlung redundanter Nebenbedingungen beschäftigt. Der von ihm für seine Regeln erhobene Anspruch der Allgemeingültigkeit wird in diesem Beitrag durch Gegenbeispiele widerlegt. Ferner werden allgemeine Regeln zur Identifikation redundanter Nebenbedingungen hergeleitet und gezeigt, daß diese die Regeln vonLlewellyn, sofern man sie um eine zusätzliche Bedingung erweitert, umfassen.