p.295

Optimal Solution of a Dynamic Leontief Model with Substitution

George B. Dantzig

Abstract

A fairly general dynamic Leontief System with discrete time periods is considered in which (a) alternative substitute type activities are allowed, (b) a bill of goods is given over time, and (c) the unknown quantities of activities satisfying the system are to be determined so as to minimize a specified linear objective function. The model has two features (a) the "general Leontief aspect" which assumes that there is one and only one output for each activity, and (b) a "dynamic (or one-way flow) aspect" which assumes that no inputs for an activity occur later in time than the time of its output. In the optimal solution certain activities appear in positive amounts and others in zero quantities. Once they are known, the quantitative solution is obtained readily by direct solution of the equations. Hence, the basic problem is to select the activities which appear in positive quantity in the optimal solution. The main results are (a) the "Samuelson Property" due to the Leontief aspect; i.e., the selection of these activities can be made independent of the bill of goods; (b) the local optimization property due to the inclusion also of the dynamic aspect; i.e., when the activities are ordered over time according to the time of production of their principal item, the selection of activities for the first k time periods, k = 1, 2, ... can be made without consideration of the nature of activities producing in time periods later than k, moreover, if the coefficients in the linear objective function are interpreted as "costs" to perform a unit quantity of an activity, then the optimum selection for successive time periods can be obtained inductively as a sequence of local optimizations using an implicit cost for each time period by subtracting from original costs those implicit costs associated with earlier time periods. The two properties, together, lead to a special computational procedure which is more efficient than the ordinary procedure of the generalized simplex method and which, of course, is not applicable to a general linear programming problem. Numerically, the number of multiplications, required for the optimal solution by the conventional simplex method, is reduced by a factor p where p is the number of discrete time periods considered.