An Infinite Linear Program with a Duality Gap

The first part of this paper is concerned with the semi-infinite linear programs studied by Charnes, Cooper and Kortanek. A form of the Farkas lemma stated by Haar appears to apply to such programs and leads to a duality theorem. In this paper an example of a semi-infinite program is given which is consistent and which has a finite minimum. However the dual program is found to be inconsistent. With a variation of the example a situation is exhibited in which both the program and its dual are consistent and have finite extrema. In this case, however, the minimum of the former is not equal to the maximum of the latter. The existence of such a “duality gap” indicates that Haar's statement needs qualification. In the second part of the paper a correct form of Haar's theorem is stated and proved. The proof invokes the infinite programming theory of Duffin and Kretschmer. The last part of the paper develops a new duality theory for infinite programs which, as a special case, insures a weak form of duality for programs typified by the examples. This new duality theory is somewhat simpler than previous theories of infinite programming.

• 저널Management Science · 12(1) · 122–134
• 토픽Logic, Reasoning, and Knowledge · Artificial Intelligence
• DOI10.1287/mnsc.12.1.122
• 저자R. J. Duffin, L. A. Karlovitz