Linear Programming and Resource Allocation Modeling

12Duality Revisited

12.1 Introduction

The material presented in this chapter is largely theoretical in nature and may be considered to be a more “refined” approach to the study of linear programming and duality. That is to say, the mathematical techniques employed herein are quite general in nature in that they encompass a significant portion of the foundations of linear (as well as nonlinear) programming. In particular, an assortment of mathematical concepts often encountered in the calculus, along with the standard matrix operations which normally underlie the theoretical development of linear programming, are utilized to derive the Karush‐Kuhn‐Tucker necessary conditions for a constrained extremum and to demonstrate the formal equivalence between a solution to the primal maximum problem and the associated saddle‐point problem. Additionally, the duality and complementary slackness theorems of the preceding chapter are reexamined in the context of this “alternative” view of the primal and dual problems.

12.2 A Reformulation of the Primal and Dual Problems

Turning to the primal problem, let us maximize f(X) = C′X subject to AX ≤ b, X ≥ O, X ∈ Eⁿ, where A is of order (m × n) with rows a₁, …, a_m, and b is an (m × 1) vector with components b₁, …, b_m. Alternatively, if

are, respectively, of order (m + n × n) and (m + n × 1), then we may maximize f(X) = C′X subject to where ...