COMP4121 Lecture Notes
Linear Programming
LiC: Aleks Ignjatovic
[email protected]
THE UNIVERSITY OF
NEW SOUTH WALES
School of Computer Science and Engineering
The University of New South Wales
Sydney 2052, Australia
We now move to one of the most important cases of convex programming,
called Linear Programming, (LP), in which the objective is a linear function
and the convex domain over which the extremum is sought is defined by con-
straints which are also linear functions. We follow closely our old COMP3121
textbook by Cormen, Leiserson, Rivest and Stein, introduction to Algorithms.
We start by defining a common representations of Linear Programming opti-
mization problems.
In the standard form the objective to be maximized is given by
f(x) =
n∑
j=1
cj xj ,
and the constraints are of the form
n∑
j=1
aijxj ≤ bi, 1 ≤ i ≤ m; (1)
xj ≥ 0, 1 ≤ j ≤ n, (2)
Note that x represents a vector, x> = 〈x1, . . . , xn〉; we assume that vectors are
columns; thus, to write them as rows we have to transpose them. The numbers
aij are assumed to be real.
Clearly, a minimization problem of the form:
minimize f(x) =
n∑
j=1
cj xj ,
subject to the constraints of the form
n∑
j=1
aijxj ≥ bi, 1 ≤ i ≤ m; (3)
xj ≥ 0, 1 ≤ j ≤ n, (4)
can easily be reduced to a corresponding maximization problem in the standard
form
maximize f (x) =
n∑
j=1
c j xj ,
with constraints of the form
n∑
j=1
a ijxj ≤ b i , 1 ≤ i ≤ m;
xj ≥ 0, 1 ≤ j ≤ n,
by taking c = c, a ij = aij and b = b.
1
Example: Humans require 13 vitamins V1, . . . , V13 in total; the daily re-
quired amounts d1, . . . , d13 for each of them are known. Your local grocery store
caries 130 types of food staples, and for each food staple Sk and each of the 13
vitamins Vi the content of Vi per gram of
Sk is also a known value, denoted by
C(k, i). For each food staple Sk you are also given its price per gram, denoted
by Pk. Your goal is to determine the quantities xk of each food staple Sk which
you should buy, such that your daily requirements of all vitamins are met, but
the total price you pay for your daily food provision is as small as possible.
Solution: You have to:
minimize the objective
130∑
k=1
Pk xk
subject to 13 constraints
130∑
k=1
C(k, i)xk > di, 1 ≤ i ≤ 13,
x1 ≥ 0, . . . , x130 ≥ 0.
Somewhat messy formulation of an LP program we have given can be refor-
mulated in a much more compact matrix form. To get a very compact represen-
tation of linear programs, let us introduce a partial ordering on vectors x ∈ Rn
by x ≤ y if and only if such inequalities hold coordinate-wise, i.e., if and only if
xj ≤ yj for all 1 ≤ i ≤ n. Since vectors are written as a single column matrices,
letting c> = 〈c1, . . . , cn〉 ∈ Rn and b> = 〈b1, . . . bm〉 ∈ Rm, and letting A be
the matrix A = (aij)i,j of size m × n, we get that the above problem can be
formulated simply as:
maximize c>x
subject to the following two (matrix-vector) constraints:1 Ax ≤ b and x ≥ 0.
Thus, to specify a Linear Programming optimisation problem we just have
to provide a triplet (A,b, c), and the information that the triplet represents an
LP problem in the standard form.
While in general the “natural formulation” of a problem into a Linear Pro-
gram does not necessarily produce the non-negativity constrains (4) for all of
the variables, in the standard form such constraints are indeed required for all
of the variables. However, this poses no problem, because each occurrence of
an unconstrained variable xj can be replaced by the expression x
′
j x j where
x′j , x