Information Technology Reference
In-Depth Information
Let
y
ij
be the quantity of product shipped from factory
i
to customer
j
. The total
transportation cost is
m
n
y
ij
c
ij
.
(2.3)
i
=
1
j
=
1
The amount sent from factory
i
is
j
=
1
y
ij
and since the amount available at factory
i
is
s
i
, we must have
n
y
ij
≤
s
i
for
i
=
1,
...
,
m.
(2.4)
j
=
1
The amount sent to customer
j
is
i
=
1
y
ij
and since the amount required there is
r
j
,
we must have
m
y
ij
≥
=
r
j
for
j
1,
...
,
n.
(2.5)
i
=
1
It is assumed that we cannot send a negative amount from factory
i
to customer
j
,
so we have also
y
ij
≥
0
for
i
=
1,
...
,
m
and
j
=
1,
...
,
n.
(2.6)
Our problem is to minimise (
2.3
) subject to (
2.4
), (
2.5
) and (
2.6
).
Two classes of problems, the
standard maximum problem
and the
standard mini-
mum problem
, play a special role in linear programming. We are given an
m
-vector,
b
=
(
b
1
,
...
,
b
m
)
T
, and an
n
-vector,
c
=
(
c
1
,
...
,
c
n
)
T
and an
m
×
n
matrix,
⊛
⊞
a
11
a
12
···
a
1
n
⊝
⊠
a
21
a
22
···
a
2
n
A
=
.
.
.
.
.
.
a
m
1
a
m
2
···
a
mn
of real numbers.
(
x
1
,
...
,
x
n
)
T
The Standard Maximum Problem
Find an
n
-vector,
x
=
that
maximises
c
T
x
=
c
1
x
1
+···+
c
n
x
n
≤
subject to the constraints
Ax
b
, i.e.
a
11
x
1
+
a
12
x
2
+···+
a
1
n
x
n
≤
b
1
a
21
x
1
+
a
22
x
2
+···+
a
2
n
x
n
≤
b
2
.
a
m
1
x
1
+
a
m
2
x
2
+···+
a
mn
x
n
≤
b
m
Search WWH ::
Custom Search