3.3 Standard Form of a Linear Programming Problem 123whereX=
x 1
x 2
..
.
xn
, b=
b 1
b 2
..
.
bm
, c=
c 1
c 2
..
.
cn
,
a=
a 11 a 12 · · · a 1 n
a 21 a 22 · · · a 2 n
..
.
am 1 am 2 · · ·amn
The characteristics of a linear programming problem, stated in standard form, are
1.The objective function is of the minimization type.
2.All the constraints are of the equality type.
3.All the decision variables are nonnegative.It is now shown that any linear programming problem can be expressed in standard
form by using the following transformations.
1.The maximization of a functionf (x 1 , x 2 ,... , xn) s equivalent to the minimiza-i
tion of the negative of the same function. For example, the objective functionminimizef=c 1 x 1 +c 2 x 2 + · · · +cnxn
is equivalent to
maximizef′= − f=−c 1 x 1 −c 2 x 2 − · · · −cnxnConsequently, the objective function can be stated in the minimization form in
any linear programming problem.
2.In most engineering optimization problems, the decision variables represent
some physical dimensions, and hence the variablesxj will be nonnegative.
However, a variable may be unrestricted in sign in some problems. In such
cases, an unrestricted variable (which can take a positive, negative, or zero
value) can be written as the difference of two nonnegative variables. Thus ifxj
is unrestricted in sign, it can be written asxj=xj′−xj′′, wherex′j≥ 0 and x′′j≥ 0
It can be seen thatxjwill be negative, zero, or positive, depending on whether
x′′jis greater than, equal to, or less thanxj′.
3 .If a constraint appears in the form of a “less than or equal to” type of
inequality as
ak 1 x 1 +ak 2 x 2 + · · · +aknxn≤bkit can be converted into the equality form by adding a nonnegative slack variable
xn+ 1 as follows:
ak 1 x 1 +ak 2 x 2 + · · · +aknxn+xn+ 1 =bk