4 - Linear programming

Linear programming is a chapter of applied mathematics concerned with the maximization (or minimization) of a linear function, subject to linear constraints. A key role is designated to the Lagrange multipliers . In economics, these are the marginal productivities of the constraining entities. Our development of the theory of linear programming is made through an analysis of the Lagrange multipliers. The multipliers are constructed on the basis of inequality implications (sections 4.2 and 4.3) and yield an intuitive and simple derivation of the main results (sections 4.4 and 4.5). The remaining sections characterize the multipliers (section 4.6), identify the active variables (section 4.7), and provide an economic interpretation in terms of scarcity (section 4.8).

There is a close connection between linear programs and inequality implications. An inequality implication states that one set of inequalities implies another inequality. For example, the inequality pair x 1 ≥ 0 and x 2 ≥ 0 clearly implies the new inequality x 1 + x 2 ≥ 0. A linear program can be designed in this framework. If a point is feasible, meaning that it fulfills the inequalities of the constraints, it is implied that the value of the linear function is less than or equal to the optimal value. Lemma 4.1 will reveal the structure of inequality implications, contains the seed of the Lagrange multipliers, and enable us to quickly derive the main results of the theory of linear programming.