Chapter 2

Basic Properties of Linear Programs

2.1 Introduction

A linear program (LP) is an optimization problem in which the objective function

is linear in the unknowns and the constraints consist of linear equalities and linear
inequalities. The exact form of these constraints may differ from one problem to an-
other, but as shown below, any linear program can be transformed into the following
standard form:

minimize c1 x1 + c2 x2 + . . . + cn xn
subject to a11 x1 + a12 x2 + . . . + a1n xn = b1
a21 x1 + a22 x2 + . . . + a2n xn = b2
.. .. (2.1)
. .
am1 x1 + am2 x2 + · · · + amn xn = bm
and x1  0, x2  0, . . . , xn  0,

where the bi ’s, ci ’s and ai j ’s are fixed real constants, and the xi ’s are real numbers to
be determined. We always assume that each equation has been multiplied by minus
unity, if necessary, so that each bi  0.
In more compact vector notation,1 this standard problem becomes

minimize cT x
subject to Ax = b and x  0. (2.2)

Here x is an n-dimensional column vector, cT is an n-dimensional row vector, A is

an m × n matrix, and b is an m-dimensional column vector. The vector inequality
x  0 means that each component of x is nonnegative.

1
See Appendix A for a description of the vector notation used throughout this book.

© Springer International Publishing Switzerland 2016 11

D.G. Luenberger, Y. Ye, Linear and Nonlinear Programming, International
Series in Operations Research & Management Science 228,
DOI 10.1007/978-3-319-18842-3 2
12 2 Basic Properties of Linear Programs

Before giving some examples of areas in which linear programming problems

arise naturally, we indicate how various other forms of linear programs can be con-
verted to the standard form.
Example 1 (Slack Variables). Consider the problem

minimize c1 x1 + c2 x2 + · · · + cn xn
subject to a11 x1 + a12 x2 + · · · + a1n xn  b1
a21 x1 + a22 x2 + · · · + a2n xn  b2
.. ..
. .
am1 x1 + am2 x2 + · · · + amn xn  bm
and x1  0, x2  0, . . . , xn  0,

In this case the constraint set is determined entirely by linear inequalities.

The problem may be alternatively expressed as

minimize c1 x1 + c2 x2 + · · · + cn xn
subject to a11 x1 + a12 x2 + · · · + a1n xn + y1 = b1
a21 x1 + a22 x2 + · · · + a2n xn + y2 = b2
.. ..
. .
am1 x1 + am2 x2 + · · · + amn xn + ym = b m
and x1  0, x2  0, . . . , xn  0,
and y1  0, y2  0, . . . , ym  0.

The new positive variables yi introduced to convert the inequalities to equalities

are called slack variables (or more loosely, slacks). By considering the problem
as one having n + m unknowns x1 , x2 , . . . , xn , y1 , y2 , . . . , ym , the problem takes
the standard form. The m × (n + m) matrix that now describes the linear equality
constraints is of the special form [A, I] (that is, its columns can be partitioned into
two sets; the first n columns make up the original A matrix and the last m columns
make up an m × m identity matrix).
Example 2 (Surplus Variables). If the linear inequalities of Example 1 are reversed
so that a typical inequality is

ai1 x1 + ai2 x2 + · · · + ain xn  bi ,

it is clear that this is equivalent to

ai1 x1 + ai2 x2 + · · · + ain xn − yi = bi

with yi  0. Variables, such as yi , adjoined in this fashion to convert a “greater than

or equal to” inequality to equality are called surplus variables.
It should be clear that by suitably multiplying by minus unity, and adjoining slack
and surplus variables, any set of linear inequalities can be converted to standard form
if the unknown variables are restricted to be nonnegative.
2.1 Introduction 13

Example 3 (Free Variables—First Method). If a linear program is given in standard

form except that one or more of the unknown variables is not required to be non-
negative, the problem can be transformed to standard form by either of two simple
techniques.
To describe the first technique, suppose in (2.1), for example, that the restriction
x1  0 is not present and hence x1 is free to take on either positive or negative
values. We then write
x1 = u 1 − v1 , (2.3)
where we require u1  0 and v1  0. If we substitute u1 − v1 for x1 everywhere in
(2.1), the linearity of the constraints is preserved and all variables are now required
to be nonnegative. The problem is then expressed in terms of the n + 1 variables
u 1 , v1 , x2 , x3 , . . . , xn .

There is obviously a certain degree of redundancy introduced by this technique,

however, since a constant added to u1 and v1 does not change x1 (that is, the rep-
resentation of a given value x1 is not unique). Nevertheless, this does not hinder
the simplex method of solution.
Example 4 (Free Variables—Second Method). A second approach for converting to
standard form when x1 is unconstrained in sign is to eliminate x1 together with one
of the constraint equations. Take any one of the m equations in (2.1) which has a
nonzero coefficient for x1 . Say, for example,

ai1 x1 + ai2 x2 + · · · + ain xn = bi , (2.4)

where ai1  0. Then x1 can be expressed as a linear combination of the other vari-
ables plus a constant. If this expression is substituted for x1 everywhere in (2.1),
we are led to a new problem of exactly the same form but expressed in terms of
the variables x2 , x3 , . . . , xn only. Furthermore, the ith equation, used to determine
x1 , is now identically zero and it too can be eliminated. This substitution scheme
is valid since any combination of nonnegative variables x2 , x3 , . . . , xn leads to a
feasible x1 from (2.4), since the sign of x1 is unrestricted. As a result of this sim-
plification, we obtain a standard linear program having n − 1 variables and m − 1
constraint equations. The value of the variable x1 can be determined after solution
through (2.4).

Example 5 (Specific Case). As a specific instance of the above technique consider

the problem

minimize x1 + 3x2 + 4x3

subject to x1 + 2x2 + x3 = 5
2x1 + 3x2 + x3 = 6
x2  0, x3  0.

Since x1 is free, we solve for it from the first constraint, obtaining

14 2 Basic Properties of Linear Programs

x1 = 5 − 2x2 − x3 . (2.5)

Substituting this into the objective and the second constraint, we obtain the equiva-
lent problem (subtracting five from the objective)

minimize x2 + 3x3
subject to x2 + x3 = 4
x2  0, x3  0,

which is a problem in standard form. After the smaller problem is solved (the answer
is x2 = 4, x3 = 0) the value for x1 (x1 = −3) can be found from (2.5).

2.2 Examples of Linear Programming Problems

Linear programming has long proved its merit as a significant model of numerous
allocation problems and economic phenomena. The continuously expanding litera-
ture of applications repeatedly demonstrates the importance of linear programming
as a general framework for problem formulation. In this section we present some
classic examples of situations that have natural formulations.
Example 1 (The Diet Problem). How can we determine the most economical diet
that satisfies the basic minimum nutritional requirements for good health? Such a
problem might, for example, be faced by the dietitian of a large army. We assume
that there are available at the market n different foods and that the jth food sells at a
price c j per unit. In addition there are m basic nutritional ingredients and, to achieve
a balanced diet, each individual must receive at least bi units of the ith nutrient per
day. Finally, we assume that each unit of food j contains ai j units of the ith nutrient.
If we denote by x j the number of units of food j in the diet, the problem then is
to select the x j ’s to minimize the total cost
c1 x1 + c2 x2 + · · · + cn xn
subject to the nutritional constraints
ai1 x1 + ai2 x2 + · · · + ain xn  bi , i = 1, . . . , m,
and the nonnegativity constraints
x1  0, x2  0, . . . , xn  0
on the food quantities.
This problem can be converted to standard form by subtracting a nonnegative
surplus variable from the left side of each of the m linear inequalities. The diet
problem is discussed further in Chap. 4.
Example 2 (Manufacturing Problem). Suppose we own a facility that is capable of
manufacturing n different products, each of which may require various amounts