Information Technology Reference
In-Depth Information
and
x
≥
0
, i.e.
0
.
The Standard Minimum Problem
Find an
m
-vector,
y
x
1
≥
0,
x
2
≥
0,
...
,
x
n
≥
(
y
1
,
...
,
y
m
)
T
=
that
minimises
b
T
y
=
b
1
y
1
+···+
b
m
y
m
subject to the constraints
A
T
y
≥
c
, i.e.
a
11
y
1
+
a
21
y
2
+···+
≥
a
m
1
y
m
c
1
a
12
y
1
+
a
22
y
2
+···+
a
m
2
y
m
≥
c
2
.
a
1
n
y
1
+
a
2
n
y
2
+···+
a
mn
y
m
≥
c
n
and
y
≥
0
, i.e.
y
1
≥
0,
y
2
≥
0,
...
,
y
m
≥
0
.
In a linear programming problem, the function to be maximised or minimised is
called the
objective function
. A vector, e.g.
x
for the standard maximum problem
or
y
for the standard minimum problem, is said to be
feasible
if it satisfies the
corresponding constraints. The set of feasible vectors is called the
constraint set
.A
linear programming problem is said to be
feasible
if the constraint set is not empty;
otherwise, it is said to be
infeasible
. A feasible maximum (resp. minimum) problem
is said to be
unbounded
if the objective function can assume arbitrarily large positive
(resp. negative) values at feasible vectors; otherwise, it is said to be
bounded
. The
value
of a bounded feasible maximum (resp, minimum) problem is the maximum
(resp. minimum) value of the objective function as the variables range over the
constraint set. A feasible vector at which the objective function achieves the value is
called
optimal
.
Proposition 2.4
All linear programming problems can be converted to a standard
form.
Definition 2.21
The dual of the standard maximum problem
maximise
c
T
x
subject to the constraints
Ax
≤
b
and
x
≥
0
is defined to be the standard minimum problem
minimise
b
T
y
subject to the constraints
A
T
y
≥
c
and
y
≥
0
and vice versa.
Theorem 2.10 (The Duality Theorem)
If a standard linear programming problem
is bounded feasible, then so is its dual, their values are equal, and there exist optimal
vectors for both problems.
Search WWH ::
Custom Search