One of the most important problems in the field of statistics is the linear regression problem. Roughly speaking, this problem involves fitting a straight line to statistical data represented by points—(x1, y1), (x2, y2), . . . , (xn, yn)—on a graph. If we denote the line by y  a  bx, the objective is to choose the constants a and b to provide the “best” fit according to some criterion. The criterion usually used is the method of least squares, but there are other interesting criteria where linear programming can be used to solve for the optimal values of a and b.

Formulate a linear programming model for this problem under the following criterion:

Minimize the sum of the absolute deviations of the data from the line; that is, Minimize n

i1

yi  (a  bxi).

(Hint: Note that this problem can be viewed as a nonpreemptive goal programming problem where each data point represents a

“goal” for the regression line.)