Numerical Methods and Optimization

Introduction to Linear Programming 221

Including the nonnegativity constraints, we obtain the following formulation:

maximize c

1

x

1

+ ... + c

n

x

n

subject to a

11

x

1

+ ... + a

1n

x

n

≤ b

1

.

.

.

.

.

.

.

.

.

.

.

.

a

m1

x

1

+ ... + a

mn

x

n

≤ b

m

x

1

,...,x

n

≥ 0,

or, equivalently,

maximize

n



j=1

c

j

x

j

subject to

n



j=1

a

ij

x

j

≤ b

i

,i=1, 2,...,m

x

j

≥ 0,j=1, 2,...,n.

Denoting by

A =

⎡

⎢

⎣

a

11

··· a

1n

.

.

.

.

.

.

.

.

.

a

m1

··· a

mn

⎤

⎥

⎦

,b=

⎡

⎢

⎣

b

1

.

.

.

b

n

⎤

⎥

⎦

,c=

⎡

⎢

⎣

c

1

.

.

.

c

n

⎤

⎥

⎦

,

we represent the LP in a matrix form:

maximize c

T

x

subject to Ax ≤ b

x ≥ 0.

10.3 Practical Implications of Using LP Models

Just like any other methodology used to solve practical problems, linear

programming has its strengths and limitations. Its main advantages ...