Consider the following linear programming problem, which is denoted by (S):The various vectors and matrices have the following dimensions:a = an m-vectorAj = (j = 1 … n), an m by njmatrix,bj = (j = 1 … n), an mj-vector,Bj = (j = 1 … n), an mj by nj matrix,Cj = (j = 1 … n), an nj-vector, andxj = (j = 1 … n), a variable nj-vector.
Problems with this decomposable structure have been extensively studied in economics and management science literature, because they arise in several economic contexts and situations. Therefore, (S) lends itself to more than one economic interpretation, but the following one is hereby adopted for the purposes of this paper: (S) models a two-level manufacturing organization, consisting of headquarters and n producing divisions. Let this organization be called simply “the company”. The company can produce and sell a number of different products, thereby obtaining fixed unit contributions. These contributions are given by the vectors c1, c2, … cn. The products are produced by the different divisions. The variable vector xj (j = 1 … n) gives the production program for the jth division.