2002-05-15

Linear programming with
interval coefficients
Journal of the Operational Research Society (2000) 51. 209-220
JW Chinneck and K Ramadan
91/5/15

An example of the standard form of A linear programming
problem.
0 ,
60 2
40
2
2 1
2 1
2 1
2 1
>
> +
> +
+
x x
x x
x x to subject
x x Minimize

Algorithm 1 Solving the type I LPIC with inequalities
Given :
| |
=
=
n
j
j j j
x c c Z
1
, min
| | | | m i b b x a a
i i
n
j ij ij
,...., 1 for , , , subject to
1 j
= >
=
1. Find the best optimum by solving this LP:
s
>
=
e =
=
0 :
0 :
'
, for where , ' min
1
j j
j j
j
si
j
n
j
j j
x if c
x if c
c
x x x c z
subject to
s
>
=
e >
=
0 :
0 :
'
for where , '
1
j ij
j ij
ij
si
j i j
n
j
ij
x if a
x if a
a
x x i b x a
2. Find the worst optimum by solving this LP:
s
>
=
e =
=
0 :
0 :
' '
, for where , ' ' min
1
j j
j j
j
si
j
n
j
j j
x if c
x if c
c
x x x c z
subject to
s
>
=
e >
=
0 :
0 :
' '
for where , ' '
1
j ij
j ij
ij
si
j i
n
j
j ij
x if a
x if a
a
x x i b x a
Theorem 1 Suppose we have the interval inequality
where Then
and are maximum value
range and minimum value range inequalities.
| | | |
=
>
n
j
j j j
b b x a a
1
, ,
( ) .
0
j x x x
si
j
e
=
>
n
j
j j
b x a
1

=
>
n
j
j j
b x a
1
Proof

b b x a x a
x x x
n
j
j j
n
j
j j
si
j j
> > >
e >

= = 1 1
see we , for 0 If
Theorem 2 Let be an objective func-
Tion where
For any given solution x.
| |
=
=
n
j
j j j
x c c Z
1
,

= =
> e >
n
j
j j
n
j
j j
si
j j
x c x c Then x x for x
1 1
. 0
Proof Since proof is trivial.

, for 0
si
j j
x x x e >
Theorem 3 For an interval equality constraint:
| | | |, , ,
1
=
=
n
j
j j j
b b x a a
A pair of inequality constraints:
s
>
=
e >
=
0 :
0 :
'
for where , '
1
j j
j j
j
si
j j
n
j
j
x if a
x if a
a
x x i b x a
s
>
=
e s
=
0 :
0 :
' '
for where , ' '
1
j j
j j
j
si
j
n
j
j j
x if a
x if a
a
x x i b x a
defines a convex region of possibility in which every
point could satisfy some legal version of the original
interval equality constraint.
Proof

( )

= =
= = =
> >
> > > = > >
n
j
j j
n
j
j j
n
j
j j
n
j
j j
n
j
j j j
x a b b x a x
b b b x a b x a x a x
1 1
1 1 1
and both satisfies Therefore
and , 0 for
Theorem 4 When an interval equality constraint is included
in the model, then the worst optimum solution will occur at
either:
s
>
= =
=
0 :
0 :
' where , '
1
j ij
j ij
ij i j
n
j
ij
x if a
x if a
a b x a
s
>
= =
=
0 :
0 :
' ' where , ' '
1
j ij
j ij
ij i
n
j
j ij
x if a
x if a
a b x a
Proof
Because of the convexity of the region of possibility defined
by above constraints, . | | ' ' , ' max z z z s
Type II LPIC: at least one variable belongs to
ui
x
Theorem 5 Let M denote the model-orthant and T denote the
terminal-orthant for some model solution, where .
Then is no worse than .

M T =
( ) | | u b T x Z , ,
*
( ) | | u b M x Z , ,
*
Proof
Observe the Algorithm 1.
1. We set and are .
In order to make the z maximal,
we set .
1
x
2
x
0 >
i i ij ij j j
b b a a c c = = = , ,
2. But and are actually,
the before setting will make the
z minimal.
1
x
2
x
0 s
| | | |
2 1
1 , 1 1 , 1 min x x Z + =
| |
| | 1 5 . 0 , 1 :
3 2 , 2 :
2 1 2
2 1 1
> +
>
x x c
x x c
If we want to find the worst optimum by enumeration
method, there are three possibilities for each orthant:
1. The terminal point for the model setup (M,w,u) is also
in orthant M, that is, .
2. The terminal point for the model setup (M,w,u) is in a
different orthant T. that is, where
T M.
3. There is a balance relationship. For two orthants A and
B, this means that if then .
Balancing relationships among more than two orthants
are also possible.
( ) M u w M x e , ,
*
( ) T u w M x e , ,
*
=
( ) B u w A x e , ,
*
( ) A u w B x e , ,
*
u)] w, Z[x(T, to drcease u)] w, Z[x(M,
and
u)] w, Z[x(M, to drcease u)] w, Z[x(T,
7, Theorem the to According
T
S
M
S
) Z(S
I
I
S
Case 3: Balance relationship
0. I set we so constrint, and function object in
I from on construbti the discard want to we
above, given reason By the
). Z(S ) Z(S ) Z(S ) then Z(S
problem. LP the influence not do S and S If
then ,
I S , S
S S S
S S S
set
). Z(S and ) Z(S ) Z(S and
, S called setting middle a is there If
' ' '
T M I I
b c
b c
I c M
I b T
M T I
I
=
= = =
e
=
= +
<
Z
) Z(S
M
) Z(S
T
References
1. Wendell RE (1982) A preview of a toLeraNce apprOach to sensitivity analysis in linear
programming Disc Math 38: 121-124
2. Bradley SP, Hax AC and Magnanti TL (1977) Applied Mathematical Programming Addison-
Wesley: Reading, Massachusetts.
3. Alefeld G and Herzberger J (1983) Introduction to Interval Computations. Academic Press: New
York.
4. Ramadan K (1997) Linear Programming with Interval Coefficients. M.Sc. Thesis, Department of
Systems and Computer Engineering, Carleton University, Ottawa, Canada.
5. Ben-Israel A and Robers PD (1977) A decomposition method for interval linear programming.
Mgmt Sci 15: 374-384.
6. Levin VI (1994) Boolean linear programming with interval coefficients. Autom and Remote
Control 55: 1019-1028.
7. Inuiguchi M and Sakawa M (1995) Minimax regret solution to linear programming problems
with an interval objective function. Eur J Opl Res 86: 526-536.
8. Shaocheng T (1994) Interval number and fuzzy number linear programming. Fuzzy Sets and
Systems 66: 301-306.
9. Gass SI (1985) On the solutio of liear programming problems with free (unrestricted variables.
Comp and Opns Res 12: 265-271.
10. Winston WL (1995) Introduction to Mathematical Programming: Applications and Algoithm.
Duxbury Press Belmont, California.

2002-05-15

Uploaded by

Copyright:

Available Formats

2002-05-15

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

2002-05-15

Uploaded by

Copyright:

Available Formats

Linear programming with

You might also like