Page 389 - A Course in Linear Algebra with Applications

10.1: Introduction to Linear Programming 373

maximize or minimize: z = C\Xx + 1- c nx n
{ a-nxi H V a inx n Xj > or 0. = or > bi,
<
=
i
1,2,... ,m,
certain
The understanding here is that a^-, &*, Cj are all known quan-
tities. The object is to find x\,..., x n which optimize the ob-
jective function z, while satisfying the constraints. Evidently
Examples 10.1.1 and 10.1.2 areproblems of this type.
Feasible and optimal solutions
x T
It will be convenient to think of X = (£i,a;2, • • • > n)
n
in the above problem as a point in Euclidean space R . If
X satisfies all the constraints (including the conditions Xj >
0), then it is called a feasible solution of the problem. A
feasible solution for which the objective function is maximum
or minimum is said to be an optimal solution.
For a general linear programming problem there are three
possible outcomes.

(i) There are no feasible solutions and thus the problem
has nooptimal solutions.

(ii) Feasible solutions exist, but the objective function has
arbitrarily large or small values at feasible solutions.
Again thereare no optimal solutions.
(iii) The objective function has finite maximum or
minimumvalues at feasible points. Then optimal
solutions exist.

In a linear programming problem the object is to find an
optimal solution or show that none exists.