1
GRADUAL NUMBERS AND FUZZY OPTIMIZATION
by
Elizabeth Anne Stock
M. S., University of Colorado Denver, 2006
A thesis submitted to the
University of Colorado Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
2010
This thesis for the Doctor of Philosophy
degree by
Elizabeth Anne Stock
has been approved
by
Weldon Lodwick
2.*i Mnvi to\o
Date
Burt Simon
Stock, Elizabeth Anne (Ph.D., Applied Mathematics)
Gradual Numbers and Fuzzy Optimization
Thesis directed by Professor Weldon Lodwick
ABSTRACT
Gradual numbers are a new element of fuzzy set theory and have not yet been
fully characterized or welldefined mathematically. Further, the literature only
captures application of gradual numbers to combinatorial fuzzy optimization
problems, and not to other fuzzy optimization problems. This dissertation offers
a rigorous definition of a gradual number and further characterizes the set of
gradual numbers by relating them to the gradual cardinalities of finite fuzzy
sets and by showing that a gradual number is the difference in the size of two
fuzzy sets. Gradual numbers are used to develop a gradual simplex method, a
new solution method for linear programs with fuzzy feasible regions. Gradual
numbers are also used to optimize nonlinear functions over fuzzy regions, with
specific application to the fuzzy extension of realvalued functions.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
Weldon Lodwick
DEDICATION
This dissertation is dedicated to Victor,
who has been waiting to call me Dr. Mom.
ACKNOWLEDGMENT
This thesis would not have been possible without the guidance, encourage
ment, and freedom granted me by Weldon. The support of the remainder of
the committee was also invaluable. I owe a debt of gratitude to George for his
careful eye, to Burt for his help with the convergence theorem, to Alex for his
eleventhhour miracleworking, and the Steve for keeping me on my toes.
I was supported practically, emotionally, and spiritually by the family and
friends who surround me. Special thanks to Carrie for the writing retreat, and to
CJ and Victor for patience during what surely seemed an interminable process.
This thesis was supported in part by NSF #07424 UCD GK12 Transforming
Experiences Project.
CONTENTS
Figures ................................................................ ix
Tables................................................................ xiii
Chapter
1. Introduction to Gradual Numbers and Fuzzy Optimization.......... 1
1.1 Assumptions, Definitions, and Notation.............................. 1
1.1.1 Fuzzy Sets and Fuzzy Intervals.................................... 1
1.1.2 Gradual Numbers................................................... 6
1.2 Motivation for Current Research .................................. 10
2. Characterization of Gradual Numbers................................ 14
2.1 Fuzzy Natural Numbers.............................................. 15
2.2 Fuzzy Integers..................................................... 26
2.3 Fuzzy Rational Numbers............................................. 32
2.4 Gradual Numbers.................................................... 37
2.5 Discussion of the Nature of Gradual Numbers..................... 41
2.6 Chapter Summary ................................................... 42
3. Gradual Numbers in Linear Optimization: A Gradual Simplex Method 44
3.1 Background of Fuzzy Optimization................................... 46
3.1.1 A Gradual Optimum................................................ 55
3.2 Main Results: A Gradual Simplex Method.............................. 58
3.2.1 Formulating the Problem ......................................... 61
vi
3.2.2 Pivoting......................................................... 71
3.2.3 Special Considerations in the Gradual Simplex Method............. 76
3.2.3.1 Degeneracy..................................................... 76
3.2.3.2 Convergence ................................................... 77
3.3 Discussion........................................................ 80
3.4 Extensions........................................................ 81
3.4.1 Problems over Necessarily Feasible Regions ....................... 84
3.5 Chapter Summary................................................... 89
4. Gradual Numbers in NonLinear Optimization: Evaluating Functions
on Fuzzy Intervals................................................... 90
4.1 Introduction...................................................... 90
4.2 Background........................................................ 91
4.2.1 Extension Principles.............................................. 91
4.2.2 Interval Analysis................................................. 92
4.2.3 Optimization in Interval Analysis................................. 96
4.3 Extending Functions to Fuzzy Intervals........................... 100
4.3.1 Previous Work.................................................... 100
4.3.2 Main Results: Fuzzy Extension of Differentiable Functions .... 106
4.4 Chapter Summary ................................................. 115
5. Conclusion......................................................... 116
Appendix
A. Notation........................................................... 119
B. Glossary........................................................... 121
C. Some Gradual Number Theoretic Results................... 125
vii
C.l Divisibility and Fuzzy Primes.......................................... 125
C.2 Equivalence Classes.................................................... 128
References................................................................. 132
viii
FIGURES
Figure
1.1 An illustration of a LR fuzzy interval with core [w,uj+], support
[w~aw, w++f3w\, and reference functions L = 1 x4, and R = 1 2.x. 5
1.2 A trapezoidal fuzzy interval with core (a, b) and support (c, d). ... 6
1.3 An illustration of three gradual numbers, f, s, and t. To see partial
ordering, observe that r > t, and s > t, but there is no order relation
between r and s.................................................. 7
1.4 The inverses of the left and right profiles of the membership function,
(yu^,)1(c*) and a) are special cases of gradual numbers. . 11
2.1 The fuzzy natural number representing the cardinality of the fuzzy
set V = {0.2/F, 0.5/D, 0.5/C, 0.6/B, 1/Aj............................ 18
2.2 I: The fuzzy natural number f (bold). II: The fuzzy natural number
s (dashed). Ill and IV: Their difference, the fuzzy integer t = r s
(light)......................................................... 28
2.3 I: The fuzzy natural number f (bold). II: f (bold) and s (dashed).
f
III and IV: Their quotient, the fuzzy integer t = (light).......... 35
s
2.4 Given the fuzzy interval W, the width of each acut of W can be
represented by the nonnegative nonincreasing gradual number \W\. 42
2.5 I. The gradual number f is the difference of the nonnegative, non
increasing gradual numbers \W\ and V. In turn, IV and V mea
sure the width of fuzzy intervals W and V....................... 43
IX
3.1 I: Feasible region. The shaded area satisfies 0 < x\ < 6, 6x2 X\ <
30, X2 > 0. II: Fuzzified feasible region. Darker shading represents
the most satisfactory decisions, which are a safe distance from the
edge, and lighter shading represent partially satisfactory decisions,
which exceed the edges by a small amount............................. 45
3.2 I: A threedimensional view of a set of fuzzy constraints. II: An
example of a fuzzy goal for a maximization problem. III. The in
tersection of the fuzzy constraints (characterized by Hq(x)) and the
fuzzy goal (characterized by Hq{x)). IV. The fuzzy decision (char
acterized by /j.q{x)) and the optimal decision, x*, which maximizes
AiÂ£>(x).............................................................. 48
3.3 I: A threedimensional view of the the fuzzy feasible regions from
Figure 3.1. The feasible region still has two dimensions, with the
ccdimension added to show the membership function. II: A gradual
number on the edge of the feasible region. III. A gradual number
in the interior of the feasible region. IV. A gradual number at an
extreme point of the feasible region................................. 56
3.4 A hypothetical result for a radiation therapy planning problem, z
represents the total level of radiation delivered to the tumor, and
a indicates the degree to which the safety requirements are met.
Given this graph, the oncologist might choose a riskaverse strategy
for Patient 1, for whom alternative treatments are available, and an
aggressive strategy for Patient 2, for whom radiation is the only option. 58
x
3.5 The farmers profit level in dollars on the yaxis compared to the
level of satisfaction she has with the feasibility of the corresponding
solution............................................................... 75
3.6 Higher acuts of a possibility distribution correspond to narrower
intervals.............................................................. 84
3.7 For each acut of the possibility distribution, the decision maker
indicates how satisfied he will be if the solution is feasible for every
possible outcome in the interval. For instance, a solution that is
feasible so long as the uncertain variable takes on a value less than a
is satisfactory to degree 0.2, whereas a solution that is feasible so long
as the uncertain variable takes on a value less than e is satisfactory
to degree 0.9..................................................... 86
4.1 A twodimensional fuzzy interval is shown in (I), with examples of
configurations in (II)(IV). The configuration in (IV) is an example
of an extreme configuration since it lies on the upper endpoint of
the the siaxis fuzzy interval and on the lower endpoint of the the
X2axis.......................................................... 101
4.2 The fuzzy interval x is defined by its gradual endpoints, [x_,x+] =
[a,la]......................................................... 102
4.3 Vertex method example: The extension of x2 to the fuzzy interval in
Figure 4.2 yields the fuzzy interval x2, which is defined by its gradual
endpoints, [z~, z+] [ct2,1 cn + a2].................. 103
4.4 Vertex method underestimation: The extension of x(l x) to the
fuzzy interval in Figure 4.2 yields the single gradual number a \{ce)2.104
xi
4.5 The fuzzy interval x is defined by its gradual endpoints, [x ,5+] =
[a,lÂ§a]............................................................ 112
4.6 Optimization example: the extension of x(l x) to the fuzzy interval
in Figure 4.2 yields [z~,z+] [a \a2, ], Va (0,1]............ 114
C.l I: The fuzzy natural number f (bold). II: f (bold) and its fuzzy
divisor, s (dashed). Ill and IV: Their quotient, the fuzzy relative
integer t (light).................................................... 126
C.2 I: Fuzzy natural numbers f and s are Jequivalent. II: Gradual
numbers t and u are Jequivalent.................................... 129
C.3 I: Fuzzy natural numbers r and s are iJequivalent. II: Gradual
numbers t and u are //equivalent.................................... 129
C.4 Fuzzy natural numbers f and s are /equivalent. II: Gradual numbers
t and u are /equivalent............................................. 130
xii
TABLES
Table
2.1 The membership function, Hy{x), describing the degree to which the
elements x G X are members of V.................................... 17
2.2 El, the cardinality of the fuzzy set V, is defined by its membership
function A^j. The value of AP(a) is the number of elements in the
strong acut of V............................................. 17
3.1 Relevant characteristics of the three crops under consideration for
spring planting.................................................... 59
3.2 The farmers optimal solution for a selection of alevels.......... 76
xiii
1. Introduction to Gradual Numbers and Fuzzy Optimization
Fortin, Fargier, and Dubois [27] introduced gradual numbers as elements of
fuzzy intervals in 2006. Until this time, there was no general concept of what
an element of a fuzzy interval might be, an absence which may have impaired
the use of fuzzy intervals as computational tools. In the brief time since their
introduction, gradual numbers have been employed as tools for computations on
fuzzy sets, with applications to combinatorial optimization [28, 40] and mono
tonic function evaluation [26, 27]. The goal of this dissertation is to further
the mathematical understanding of gradual numbers and to explore the use of
gradual numbers in optimization of both linear and nonlinear functions over
fuzzy sets.
1.1 Assumptions, Definitions, and Notation
It is assumed that the reader is familiar with linear and nonlinear optimiza
tion and with basic mathematical analysis. The notation used in this disserta
tion is the result of a recent attempt to standardize interval notation [43] and is
summarized in Appendix A. An overview of fuzzy and gradual concepts follows.
1.1.1 Fuzzy Sets and Fuzzy Intervals
Fuzzy sets are sets without sharp boundaries, in which there is a grad
ual transition between elements that are members and elements that are non
members. The notion of a fuzzy set is useful to mathematical modeling because
real world sets are not always crisply defined. Sometimes a gradual transition
1
from nonmembership to membership is required. When the set in question is a
set of possible events, this corresponds to a need to move gradually from impos
sible to possible, with values on the outskirts of the set being somewhat possible.
Fuzzy set theory accomplishes this by softening the boundaries of a set. Grades
of membership in the softened set are defined by a membership function.
Definition 1.1 (fuzzy set) Let X denote a set. Then a fuzzy set A on X is
a set of ordered pairs
A = {{x,pA(x)) :xeX},
where the membership function pL^ : X [0,1] is a map from set X into the
set of possible degrees of memberships, [0,1], with p^{x) = 1 indicating full
membership, p^{x) = 0 indicating nonmembership, and values between 0 and 1
indicating partial membership. When there is no potential for confusion, A(x)
may be used in place of p^{x).
The following concepts regarding fuzzy sets will be useful in later chapters of
the dissertation. For easy reference, these definitions are repeated in Appendix
B.
normalized. A normalized fuzzy set achieves a maximal membership func
tion value of 1.
acut. The acut of a fuzzy set is the set {x\p^{x) > a}1 and is denoted
Aa.
Support. The support of a fuzzy interval A is the set {x\p^(x) > 0.}
1This is elsewhere referred to as the strong acut, with acut defined using strict equality.
[46]
2
Core. The core of a fuzzy interval A is the set {x\ji^{x) = 1}.
Equality. Two fuzzy sets, A and B are said to be equal if and only if
(J
Disjoint. Two fuzzy sets, A and B are said to be disjoint if and only if
Ha{x) = 0 whenever x) > 0 for all x X.
Containment. A fuzzy set A is said to be a subset of fuzzy set B if and
only if fi^(x) < faÂ§(x) for all x G X.
Extension Principle. The extension principle is used to extend usual func
tions to fuzzy setvalued arguments [93]. Let / : U > V, and let X
(defined by its membership function pxiv)) be a fuzzy set in U. The ex
tension of / is denoted F. To obtain the fuzzy set Y = F(X) on V, apply
the extension principle, which creates the following:
Vf(X)(v) '= sup{//*() : v = /()} x
= 0 if {v = f(u)} 0.
Crisp. A crisp entity is nonfuzzy. This term is used to describe sets and
intervals in ambiguous contexts.
A normalized fuzzy set achieves a maximal membership function value of
1. A fuzzy interval is a normalized fuzzy set on the real number line whose
membership function is upper semicontinuous 2 and whose alevels are convex.
A fuzzy interval is a generalization of an interval, in which the boundaries of the
2 A realvalued function / is upper semicontinuous at a point x0, if the right and lefthand
limits of / exist at Xq and are less than or equal to xq.
3
intervals are softened. A fuzzy interval W is defined by its membership function,
Hw : R i> [0,1], where Pw(x) indicates to what extent x is a member of W.
When X is a fuzzy interval, this extension principle (1.1) is consistent, at
each a, with evaluating the function over the acut. Thus, the following holds
[68]:
f(K) = \HA)\*.
Fuzzy interval extensions and standard interval extensions are discussed in more
depth in Chapter 4.
Fuzzy intervals need not have a closed form representation, in general. For
practical purposes, however, fuzzy intervals with simple representations are eas
ier to work with. One standard fuzzy interval is the L R fuzzy interval [20],
which is defined by a membership function /%, a core [iu,u;+], a support
[w~ aw,w+ + flw\, and reference functions L and R. L : R > [0,1] and
R : R [0,1] are upper semicontinuous and decreasing in the range (0,1]. /i^
is defined as follows:
Rw(x)
1 for x G [rc
L ( W X  for x < w~,
^ Off /
R\ (xw+ \ l ftw ) for x > w+.
An L R fuzzy interval is illustrated in Figure 1.1. A fuzzy interval with an
even simpler form occurs when L and R are linear functions. This special form
is called a trapezoidal fuzzy interval, which is defined by a membership function
4
Figure 1.1: An illustration of a LR fuzzy interval with core [w iy+], support
[w~ aw, w+ + Pw], and reference functions L = 1 x4, and R 1 2x.
HVy, a core (a, b), and a support (c, d), with c < a < b < d. Then
Hw(x) = <
0
^ ax
ac
i xb
1 db
for x G [a, b],
for x (c, d),
for x (c, a),
for x (b, d).
A trapezoidal fuzzy interval is illustrated in Figure 1.2.
A fuzzy set is a softened set, and a fuzzy interval can be seen as a soft
ened interval. Sets are composed of elements, and in particular, real intervals
are composed of real numbers. From any interval, an element, which is a real
number, can be selected. A new idea, some concept of a fuzzy element, will be
needed to complete the analogy between real intervals and fuzzy intervals. The
next section describes how gradual numbers and gradual elements fulfill that
5
Figure 1.2: A trapezoidal fuzzy interval with core (a, b) and support (c,d).
role.
1.1.2 Gradual Numbers
Fortin, Dubois, and Fargier [27] introduced gradual numbers to be the sin
gletons of fuzzy intervals, and Dubois and Prade [22] generalized the concept
to gradual elements as singletons of fuzzy sets. In addition to the analogy
real number : interval :: gradual number : fuzzy interval,
it is instructive to consider the analogy
real number : gradual number :: interval : fuzzy interval.
That is, a gradual number is a softened real number in the same way that a
fuzzy interval is a softened interval. The definition of gradual numbers reflects
this softening, or parameterization, of the real numbers.
6
!
Figure 1.3: An illustration of three gradual numbers, f, s, and t. To see partial
ordering, observe that f > t, and s > t, but there is no order relation between
f and s .
Definition 1.2 (gradual number) [26] A gradual number, f, is defined by a
function, called the assignment function, Af : (0,1] i* R. It can be understood
as a real value parametrized by a G (0,1], Then for each a, a real value ra is
given by Af(a). When there is no potential for confusion, f{a) may be substituted
for Af(a).
Figure 1.3 shows the assignment functions for three gradual numbers. The
set of gradual numbers has been only loosely defined in the literature [26]. If
every function from (0,1] to R is permitted to be an assignment function, the
set of gradual numbers contains elements with assignment functions which are
unbounded, or highly discontinuous, such as the Dirchlet function [76]. For the
applications of gradual numbers considered in this dissertation, it is desirable
to restrict the set of gradual numbers to those with assignment functions which
meet the following requirements:
7
1. Af{a) is leftcontinuous with a finite number of jumpdiscontinuities. That
is, for every a, A?(a) is continuous on the interval (a e, a] for some e > 0.
2. Af(a) is bounded. That is, there exists M G R such that A?(a) < M for
all a.
For the remainder of this dissertation, the symbol Q will represent this restricted
set of gradual numbers.
Definition 1.3 (order relations for Q) The following relations can be de
fined on the set of gradual numbers.
Equivalence relation:
r = s if A?(a) = As(a) for all a G (0,1].
Strict partial orders:
r > s if Af (a) > ^(a) for all a G (0,1].
r < s if Af{a) < As{ol) for all a G (0,1].
f ^ s if Af(a) > As(a:) for all a G (0,1] and r A Â§
r s if A?(a) < A$(a) for all a G (0,1] and f ^ s.
Partial orders:
f > s if Af(ot) > 4s(a:) for all a G (0,1].
f < s if Af{ot) < A.s(q;) for all a G (0,1].
For the remainder of this dissert ation, it is assumed that these order relations
are imposed, and Q will be considered as the corresponding partially ordered set.
Given two elements of Q, it is not required that any of the seven order relations
hold. Figure 1.3 shows two gradual numbers for which no order relation holds.
This partial ordering becomes relevant when later chapters of this dissertation
8
consider optimality, because identifying an optimal element depends entirely on
the ability to order elements of a set. Since gradual numbers and fuzzy intervals
are only partially ordered, some alternative to full ordering must be used to
determine optimum.
Basic arithmetic operations are defined on the set Q of gradual numbers as
follows [27]:
1. Addition. Given two gradual numbers f and s G Q, define their sum r + s
by its assignment function, ^+5(0) = Ar(a) + v4s(a), Vq (0,1].
2. Subtraction. Given two gradual numbers f and s G Q, define their differ
ence r s by its assignment function, A?g(a) = Af(a) ^4j(a), Va G (0,1].
3. Multiplication. Given two gradual numbers r and s G G, define their
product rs by its assignment function, = Af{a)As{a)ya G (0,1].
4. Division. Given two gradual numbers r and s G G, such that ^4s(o:) 7^ 0
for any a G (0,1], define their quotient 4 by its assignment function,
= (Ml
In addition, real valued functions are extended to gradual numbers by the grad
ual number extension principle. Let / : R R, and let x (defined by its
assignment function A^a)) be a gradual number in Q. The gradual extension
of / is denoted /. To obtain the gradual number y = f(x), apply the gradual
extension principle:
Ay{ot) = f(A$(a)), (1.2)
which is welldefined.
9
Fortin, Dubois, and Fargier showed that a fuzzy interval can be represented
as a set of gradual numbers that lie between two gradual number endpoints in
the same way that a real interval can be represented as a set of real numbers
that lie between two real endpoints [27]. That is, a fuzzy interval, W, might
be represented as the interval between two gradual numbers, [u'_,F,+]. Since a
fuzzy interval is a fuzzy set with an uppersemicontinuous membership function,
A$ must be nondecreasing, and Ayj+ must be nonincreasing. Also, to form
an interval, A,j(1) must be less than Ay,+ (1). Then the interval of gradual
numbers, corresponds to the fuzzy interval W, where is defined as
follows:
fi(x)
sup{AA^(A) < a;} if x e A* ((0,1])
1 if 4n(l)
sup{AArn+ (A) > a;} if x G A^+ ((0,1])
0 otherwise.
(1.3)
Then, in a certain sense, w~ is the inverse of the left profile of the membership
function, /r^(a), and w+ is the inverse of the right profile of the membership
function, ^u^(a) For an example of two gradual numbers and the corresponding
fuzzy interval, see Figure 1.4.
1.2 Motivation for Current Research
Gradual numbers, introduced as elements of a fuzzy set, have proven to be
useful tools in the fuzzy set community despite their limited theoretical expo
sition. For example, they have been applied to evaluation of fuzzy weighted
averages [27], and to combinatorial optimization problems [40, 28]. Enhancing
10
Figure 1.4: The inverses of the left and right profiles of the membership
function, (/j^)_1(a) and (//jt^)_1(a) are special cases of gradual numbers.
the understanding of gradual numbers may expand the breadth and depth of
their application. Chapter 2 provides an alternative approach to gradual num
bers, by mathematical characterization of Q and some of its subsets.
Consider the analogy of real numbers to understand two possible views of
gradual numbers. Given any real interval, (2,10) for instance, every element in
the interval is a real number, so we can think of a real number as an element of
a real interval. Alternatively, the set of real numbers can be derived analytically
by beginning with the natural numbers, introducing subtraction and division
to get the integers and rationals, respectively, and finally by adding the limits
of bounded sequences of rationals to obtain the set of real numbers. Fortin,
Fargier, and Dubois introduced gradual numbers the first way, as elements of a
fuzzy interval. This view, however, is deficient. For example, e G [2,10] does
not make sense if there is no concept of what a real number is. The purpose
of Chapter 2 is to look at the set of gradual numbers the second way, from the
point of view of arithmetic operations, important subsets, and construction.
11
The set of fuzzy natural numbers, which represents the cardinality of a fuzzy
set, is manipulated arithmetically to produce the fuzzy integers and the fuzzy ra
tional numbers [74, 75]. To the authors knowledge, these sets are characterized
algebraically for the first time in Chapter 2. One contribution of this dissertation
is showing that every element of Q is the limit of a sequence of fuzzy rationals.
The mathematical characterization of gradual numbers shows that they form a
partially ordered commutative ring. In addition, to the authors knowledge, it is
here observed for the first time that the width of a fuzzy interval is naturally
a nonnegative, nonincreasing gradual number.
Chapters 3 and 4 will draw on some of these gradual number properties
for use in optimization over fuzzy sets. Not all of the properties developed in
Chapter 2 are needed in the optimization applications of the later chapters of
this thesis, but it is hoped that future applications might be enhanced by this
characterization of Q.
Chapter 3 introduces a gradual simplex method for linear programming
problems with fuzzy feasible regions. The optimal element will be a singleton
of the fuzzy feasible region, or equivalently, a gradual number. The gradual
simplex method searches the parameterized vertices of the fuzzy feasible region
to find the gradual optimal element. The resulting optimum is parameterized,
producing a curve which allows the decision maker to evaluate the tradeoff
between the degree of feasibility and the optimality of the objective function.
Each feasibility level corresponds to a nonfuzzy solution.
Chapter 4 shows that gradual numbers have a role in the nonlinear optimiza
tion of a differentiable function over a fuzzy feasible region. One application of
12
this nonlinear fuzzy optimization is the extension of realvalued functions to
fuzzy intervals. While the gradual number techniques in the current literature
are able to extend only monotonic functions of fuzzy intervals [27], this chapter
employs optimization of gradual numbers to evaluate any differentiable function
of fuzzy intervals, in theory. Chapter 4 begins with the role of optimization in
extending realvalued functions to crisp intervals. The analogous extension to
fuzzy intervals follows, capitalizing on the perspective of fuzzy intervals as crisp
intervals of gradual numbers. Gradual KarushKuhnTucker conditions leading
to a novel function evaluation method.
13
2. Characterization of Gradual Numbers
This chapter provides a mathematical characterization of gradual
numbers. The set of fuzzy natural numbers, which represent the
gradual cardinalities of finite fuzzy sets, are used as a basis to de
rive the fuzzy integers, followed by the fuzzy rational numbers and
finally, the gradual numbers. Both the fuzzy rationals and the grad
ual numbers are shown to form partially ordered commutative rings.
In addition, it is suggested that the width of a fuzzy interval with a
compact support can be represented by a gradual number.
Fortin, Fargier, and Dubois [27] have given the intuitive description of a
gradual number as an element of a fuzzy interval. This concept suggests that
gradual numbers can be used to apply interval techniques to problems involving
fuzzy intervals. Indeed, both Chapters 3 and 4 of this dissertation use the
idea of a gradual number as an element of a fuzzy interval to develop fuzzy
optimization techniques, exploring their potential use in finding optima over
fuzzy feasible regions, for linear functions in Chapter 3 and nonlinear functions
in Chapter 4.
Typically, the better a tool is understood, the more it is used, and it is hoped
that gradual numbers will be no exception. Expanding the understanding of
gradual numbers beyond the representation of elements of a fuzzy interval may
expand the breadth and depth of their application. The purpose of this chapter
is to provide an alternative, mathematically sound understanding of gradual
14
numbers. The result is a mathematical characterization of the set Q and some
of its subsets, along with the observation that gradual numbers can be used to
measure the width of fuzzy intervals.
Section 2.1 introduces the set of fuzzy natural numbers, Nf, as the cardinal
ities of fuzzy sets. Defining addition and additive inverses on Nf leads to the set
of fuzzy integers, Zf, in Section 2.3. Adding multiplication and multiplicative
inverses to Zf results in the set of fuzzy rationals, Qf, which is shown to be a
partially ordered distributive ring, in Section 2.3. Section 2.4 addresses Q, the
set of gradual numbers defined in Chapter 1, and shows every element of Q to
be a limit of a sequence of fuzzy rationals. These gradual numbers are charac
terized, and Section 2.5 shows that some gradual numbers describe the size of
fuzzy intervals.
2.1 Fuzzy Natural Numbers
Rocacher and Bose [74, 75] first constructed the sets of fuzzy natural num
bers, fuzzy integers, and fuzzy rationals. Their construction is followed here,
with changes in notation. The arithmetic and algebraic properties are original
to this chapter.
Begin by observing that one purpose of the set of natural numbers, N, is
counting. A child learns the natural numbers by enumerating discrete items
in a finite set, such as toes on his feet. The originator of set theory, Georg
Cantor, is responsible for the monumental mathematical result that establishes
this intuitive connection between counting and size: every natural number is
the cardinality of some finite set [44], Analogously, some notion of the size of
a fuzzy set defined on a finite universe, that is, a finite fuzzy set, should be a
15
fuzzy natural number.
A fuzzy cardinality of a finite fuzzy set was first described by Zadeh [94], with
extensions following from Dubois and Prade [19], among others. Definitions,
interpretations and applications of fuzzy cardinality have varied widely over the
years, for examples, see [10], [46], and [72], Though opinions vary, it is generally
agreed in the literature that the fuzzy cardinality of a fuzzy set should be a
fuzzy set defined on N [78]. Rocacher and Bose [75] solidified the idea of a fuzzy
natural number as a fuzzy subset of N to describe the cardinality of a finite
fuzzy set.
Definition 2.1 (gradual cardinality) Given a fuzzy subset F of some finite
set S, the gradual cardinality of F is characterized by an assignment function
: (0,1] i> R defined by A^(a) = \Fa\.
Definition 2.2 (fuzzy natural numbers) The set of fuzzy natural numbers,
denoted Nf, is the set of gradual cardinalities of all finite fuzzy sets. That is,
for every finite fuzzy set F, Nf.
An example will aid in the understanding of a fuzzy natural number as a
cardinality of a fuzzy set. Let X be the set of letters in the English alphabet and
define the elements of the fuzzy set V G X by the membership function, /J,y(x),
listed in Table 2.1. Recall that the strong acut of a fuzzy set is defined to be the
subset of elements whose membership levels are at least a. Then the cardinality
of an acut is the number of members of the fuzzy that have a membership level
of a or higher. For example, the 0.5 cut of V, or V0.5, is {D, C, B, A}. Then the
cardinality of V0.5, denoted ] V0.51, is 4.
16
X HV{X)
A 1
B 0.6
C 0.5
D 0.5
E 0.2
Table 2.1: The membership function, fiy(x), describing the degree to which
the elements x X are members of V.
a A\y\{&) va
a e (0,0.2] 5 {F, D, C, B, A}
a e (0.2,0.5] 4 {D, C, B, 71}
a (0.5,0.6] 2 {B, A)
a (0.6,1] 1 {A}
Table 2.2: V, the cardinality of the fuzzy set V, is defined by its membership
function A^yy The value of A^y^a) is the number of elements in the strong
ctcut of V.
17
5
4
3
2
1
0 
o a i
Figure 2.1: The fuzzy natural number representing the cardinality of the fuzzy
set V = {0.2/F,0.5/D,0.5/C,0.6/B,l/A}.
Also observe that the acuts of V completely determine the fuzzy natu
ral number \V\. Table 2.2 shows how the assignment function A^y^{a) follows
from the cardinality of the acut. The fuzzy natural number \V\ also can be
represented by the distinctive stairstep graph in Figure 2.1.
Aside on notation: This concept of fuzzy cardinality was pro
posed by Rocacher [74], who used the opposite mapping, assign
ing a membership value between 0 and 1 to every natural num
ber. Rocacher observed that fuzzy natural numbers can be rep
resented entirely by their characteristic points, or the points of
jump discontinuities in the assignment functions. This means that
IF in the previous example can be represented by the set of or
dered pairs {(0.2,5), (0.5,4), (0.6, 2), (1,1)}, which is a convenient
notion. An equal influence on the notation used in this chapter is
the work of Dubois and Prade [22], which represents the inverse of
the membership function of a fuzzy set as an assignment function
18
Ap : (0,1] R. This dissertation combines the notation from the
literature to represent Rocachers fuzzy natural numbers with the
inverse mapping of Dubois and Prades assignment function. The
assignment function notation is chosen to be consistent with the
gradual numbers in later sections.
Several observations can be made about Nf, the set of fuzzy natural num
bers.
General Properties of Nf
Property 1 The assignment function of a fuzzy natural number takes on non
negative integer values everywhere on its domain (0,1]. That is, for every
n Â£ Nf, An(a) e N0, Va, where N0 := N U {0}.
Property 2 Every fuzzy natural number is nonincreasing on its domain (0,1]
because for a > /?, there cannot be more elements with membership of at
least (3 than there are elements with membership of at least a.
Property 3 The assignment function of a fuzzy natural number has a finite
number of discontinuities. This follows directly from the finiteness of the
fuzzy set for which the fuzzy natural number is the cardinality, and from
the fact that the range of the assignment function is nonincreasing and
can only take on nonnegative integer values.
Property 4 Every fuzzy natural number is an element of Q, that is, a function
from R to (0,1] that is bounded and leftcontinuous with a finite number
of jump discontinuities. This results from the finiteness of the underlying
19
fuzzy set and the definition of gradual cardinality as the cardinality of the
strong acut.
Proposition 2.3 The first two characteristics distinguish elements of the set
Nf from other gradual numbers. That is, any element of Q with Properties 1
and 2 is an element of Nf.
Proof: This can be seen by beginning with an arbitrary gradual number g
which satisfies Properties 1 and 2, and constructing a finite fuzzy set, IF, whose
gradual cardinality is g. If Ag(a) = 0,Va, let W = 0. Then the gradual
cardinality of IF is g since, for any a, the empty set contains zero elements.
Otherwise, Ag{a) > 0 for some a. Ag(a) is bounded above since g E Q, is
bounded below by 0, and is a nonnegative integer for every a E (0,1] according
to Property 1. It follows that a finite number of nonnegative integers comprises
the range of Ag(a). Since the case Ag(a) = 0,Va has already been handled,
no := minQ{74p(a) > 0} is guaranteed to exist and to be a positive integer. From
an infinitely countable ordered set X, select no different elements, xi,...,xno,
and set argmax{a : Ag(a) = n0} for i = l,...,n0 If Ag(a) =
no, Vo (0,1], then W is a finite fuzzy set whose cardinality is g. Otherwise,
let n\ mina{^lg(Q;) > n0} (such an element is sure to exist and be a natural
number by the same argument as before). Then select n\ no elements from X,
xno+\, ..,xni, and set g^{xi) argmax{a : Ag(a) = ni} for i = n0 + l,...,ni.
Continue adding elements to IV in this fashion, increasing the index of n, at
each step, until W contains p elements, where p = maxaAg(a). Then IF is a
finite fuzzy set whose cardinality is g.
20
A numerical example is offered to illustrate the construction process. Let
Ag(a)
5 for a G (0,0.25],
<4 for a G (0.25,0.6],
2 for a G (0.6,1],
Then a fuzzy set W with gradual cardinality g can be defined on the set X =
{100,200,300,...} as follows.
1. minQ{Ag(a)} = 2, so select two elements from A, 100 and 200, and assign
them membership values //^(100) = ^(200) = argmax{ct : Ag(a) =
2} = 1
2. minQ{Ag(ct) > 2} = 4, so select the next 42=2 elements from X, 300
and 400, and assign them the membership value /i^(300) = ^(400) =
argmax{a : Ag(a) = 4} = 0.6.
3. minQ{Ag(a) > 4} = 5, so select the next 54=1 element from X, 500, and
assign it a membership value //j^(500) = argmaxjo: : Ag(a) 5} = 0.25.
Then the set W with membership function
1 for x G {100,200},
0.6 for x G {300,400},
0.25 for x = 500,
0 otherwise.
has gradual cardinality equal to g.
21
Nf is a subset of Q, and can be equipped with the same order relations
defined on Q in (1.3). Hence, for the remainder of this dissertation, Nf will be
considered a partially ordered set. Next, addition and multiplication are defined
for Nf, with the result that Nf is a commutative monoid1 under addition and
under multiplication.
Definition 2.4 (addition on Nf) Given two fuzzy natural numbers r and s Â£
Nf, their sum r+s is defined pointwise as the sum of their assignment functions,
Af+S(a) = Af(a) + Ag(a;), V G (0,1]. (When there is no potential for confusion,
Af(a) may be written r(a), so Af+s(a) = r(a) + s(a).J
The following properties of addition hold.
Additive Properties of Nf
Property 1 Nf is closed under addition.
Proof: Given two fuzzy natural numbers f and s Â£ Nf, the assign
ment function of their sum is Af+s(a:) = f + s Â£ Nf if and only if it
is a gradual number satisfying Properties 1 and 2. Af+j(a) is defined
everywhere on (0,1] as a real number. Furthermore, since Afia) and
Ag(a) are bounded and leftcontinuous at every a Â£ (0,1], Ar+s(a) =
Af{a) + Ag(a) is bounded and leftcontinuous at every a G (0,1]. Thus
Af+s{a) Â£ Q. Further, for all a Â£ (0,1], Af+s(a) is a natural number
since r(a), s(a) G N0, and the nonnegative integers are closed under addi
tion. To see that Af+s(a) must be nonincreasing, select (3 and 7 so that
0 < 0 < 7 < 1. Then A?((3) > A?(7) and Afifi) > Ag(7) since r,sÂ£ Nf,
1A set and an operation form a monoid if closure, associativity, and identity hold.
22
so Af+s(/3) = Af(P) + As(f3) > Af{7) + As(7) = ^+5(7) and Ar+g(a) is
nonincreasing. Thus r + s G Nf.
Property 2 Addition is commutative.
Proof: Af+(a) = r(a) + s(a),Va G (0,1]. Since f(a) and s(a) G N0,
and addition of nonnegative integers commutes, f(a) + s(a) = s(a)+f(a).
As+f(a) = s(a) + r(a), so Af+S(a) = As+f(a). m
Property 3 Addition is associative. The proof is analogous to the proof for
commutativity.
Property 4 There is a unique additive identity on Nf, 0, defined by its assign
ment function Aq(q:) = 0, Vo G (0,1].
Proof: To see that 0 is an additive identity, consider any f G Nf with
assignment function A?(a). Let f + 0 be defined pointwise by its assign
ment function A+g(a) = Af(a) + Ag(a) = Af(a) + 0 = Af(a), Vo G (0,1].
Since Af+5 = A?, r + 0 = f for any f G Nf, so 0 is an additive iden
tity on Nf. To see uniqueness, fix f G Nf and let f + t = f. Then
Af{ct) + Aj(a) = Af(a), Va G (0,1]. Thus At(a) = 0, Va G (0,1] and
t = 0.
These properties suffice to show that Nf forms a commutative monoid under
addition. This definition of addition relates to the cardinality of finite fuzzy
sets as follows. Let a and b be fuzzy natural numbers which correspond to the
gradual cardinalities of disjoint finite fuzzy sets A and B. Then a + b = Cj,
where C = A U B.
23
Next, multiplication is defined on fuzzy natural numbers, and it is shown
that Nf forms a monoid under multiplication.
Definition 2.5 (multiplication on Nf.) Given two fuzzy natural numbers, r
and s G Nf, their product r x s is defined pointwise by its assignment function,
Afxs(a) = Af(a) x As(a), Va G (0,1].
The following properties hold:
Multiplicative Properties of Nf
Property 1 Nf is closed under multiplication. The proof is analogous to the
proof that Nf is closed under addition.
Property 2 Multiplication is commutative on Nf. The proof is analogous to
the proof that addition is commutative on Nf.
Property 3 Multiplication is associative on Nf. The proof is analogous to the
proof that addition is associative on Nf.
Property 4 There is a unique multiplicative identity on Nf, which is 1, defined
by its assignment function ylj(a) = 1, Va G (0,1].
Proof: To see that 1 is a multiplicative identity, consider any r G Nf
with assignment function Af(a). r x 1 is defined by its assignment function
Afxi(a) Af(a) x Ai(a) = A?(a) x 1 = Af{a), Va G (0,1]. Since Afxi =
A?, f x 1 = r for any f G Nf, so 1 is an additive identity on Nf. To
see uniqueness, fix f G Nf and let f x t = r. Then Afia) x Afia) =
Af(a), Va G (0,1]. Thus Afia) = 1, Va G (0,1] and t 1.
24
These properties suffice to show that Nf forms a commutative monoid under
multiplication. It remains to show that the distributive property holds.
Distributive Property of Nf
Multiplication is distributive over addition. That is, given r,s,t G Nf, r(s +
t) = rs+ft. The proof is similar to the proof for commutativity of addition,
and is based on the distributive property of multiplication over addition
in the real numbers.
The author observes that multiplication of fuzzy natural numbers relates to
the gradual cardinalities of finite fuzzy sets as follows. Let a and b be fuzzy
natural numbers which correspond to the gradual cardinalities of finite fuzzy
sets A and B. Then a x b C, where C is set of ordered pairs {(a,6)a G
A and b E B} with jjL^{a,b) := min(/z^(a),Hg(b)). The min operator is the
typical standard join operator in fuzzy set theory [46]. For example, let A and
B be defined on the alphabet by the membership functions
and
HA(x)
Hb(x)
1 for x G {B, C}
0.5 for x A,
0 otherwise,
1 for x E,
< 0.25 for x = D,
0 < otherwise.
25
Then C is the set of ordered pairs {(a,b)\a G A and b G B} is defined by
Hcia>b)
min (nA{a),Hg{b))
1, for (a, b) G {{B, E), (C, E)},
0.5, for (a, b) = (A, E),
0.25, for (a, b) G {(A Â£), (B, Â£>), (C, Â£>)},
0 otherwise.
Then the gradual cardinality of C,
A\c\(a)
6, for a e (0,0.25],
< 3, for a (0.25,0.5],
2, for a G (0.5,1],
is exactly the product of the gradual cardinalities of A and B, since
and
A\A\(a)
A\B\{a)
3, for a G (0,0.5],
2, for a G (0.5,1].
2, for a G (0,0.25],
1, for a G (0.25,1].
2.2 Fuzzy Integers
Rocacher and Bose [75] introduce Zf, the set of fuzzy integers2, by defining
subtraction on the set of fuzzy natural numbers, Nf [75].
2Rocacher and Bose refer to fuzzy relative integers because they are defined in the context
of differences between fuzzy bags. Relative is not used in this dissertation because it is not
essential to the present context.
26
Definition 2.6 (subtraction on Nf) [75] Given two fuzzy natural numbers f
and s, let their difference, t = r s, be defined pointwise by its assignment
function, Ai(a) Af(a) t4j(o),Vq G (0,1]. The set of fuzzy integers, Zf, is
defined as {f sr, s G Nf}.
For example, define f by
Af(a)
and define s by
Af{a)
Then r s is defined by
5, for a G (0,0.2],
4, for a G (0.2,0.5],
<
3, for a G (0.5,0.6],
1, for a G (0.6,1]
f
4, for a G (0,0.3],
<3, for a G (0.3,0.8],
2, for a G (0.8,1],
Afs(,(A)
1, for a G (0,0.2],
0, for a G (0.2,0.3],
1, for a G (0.3,0.5],
<
0, for a G (0.5,0.6]
2, for a G (0.6,0.8],
1, for a G (0.8,1],
as illustrated in Figure 2.2. Notice that f G Nf is integervalued, but it is not
necessarily nonnegative or nonincreasing on (0,1].
27
4
3
r
I
o 
1
2
a
i
i
o
1
2
t
a
/V
**
t =rs 
a . 1
hi
rs
a
i
ii
i
IV
Figure 2.2: I: The fuzzy natural number f (bold). II: The fuzzy natural
number s (dashed). Ill and IV: Their difference, the fuzzy integer t f s
(light).
28
The following observations can be made about the set of fuzzy integers, Zf.
General Properties of Zf
Property 1 The value of the assignment function of a fuzzy integer anywhere
on its domain (0,1] is a real integer.
Property 2 The assignment function of a fuzzy integer has a finite number of
jumps.
Proof: Since any fuzzy integer t can be represented as the difference of
two fuzzy natural numbers, say f and s, the set of jumpdiscontinuities of
Ai is at most the union of the set of discontinuities of Af and the set of
discontinuities of ^4$. The result follows from the fact that a finite union
of finite sets is finite.
Property 3 Every fuzzy integer is a gradual number. Since a fuzzy integer is
the difference of two fuzzy natural numbers, which are bounded and left
continuous, it is also bounded and leftcontinuous. By Property 2, it has
a finite number of jumps.
Zf is a subset of Q, so the order relations defined on Q in (1.3) can be defined
on Z. For the remainder of this dissertation, Zf will be considered to be a
partially ordered set. It can be shown that Zf forms an abelian group under
addition. Recall that a set and an operator form a group if closure, identity,
associativity, and invertibility hold. When commutativity holds, the group is
said to be abelian.
29
Addition is defined on Zf as it was on Nf. That is, given two fuzzy integers
f and s G Zf. their sum f + s is defined by its assignment function, Af+S(a)
Af(ft) + Aj(a), Vci G (0,1].
Additive Properties of Zf
Property 1 Addition is commutative on Zf. The proof is analogous to the
proof that addition is commutative on Nf.
Property 2 Addition is associative on Zf. The proof is analogous to the proof
that addition is associative on Nf.
Property 3 0 is the unique additive identity on Zf. The proof is analogous to
the proof that 0 is the unique additive identity on Nf.
Property 4 Every fuzzy integer r has a unique additive inverse r, defined
by its assignment function A_^(a) = (f(a)),Vo; G (0,1], Furthermore,
subtraction is equivalent to addition of the additive inverse. That is, rs =
f + (5).
Proof: f + (f) = A?(a) + A?(a) = Af(a) + (Af(a)) Ag(a:), Vo G
(0,1], so f + (f) = 0. Uniqueness follow's from the uniqueness of the
additive inverse on Z.
Property 5 The set of fuzzy integers is closed under addition.
Proof: Let t and u G Zf be given. Then there exist f, s, v, w G Nf such
that t rs and u = vw. Then t+u fs+(vw) (r+v) (s+w) by
associativity of addition on Nf and Zf. Since Nf is closed under addition,
f + v G Nf, and s + w G Nf. Thus, t + ft is expressed as the difference of
two fuzzy natural numbers, so t + u G Zf.
30
Property 6 The set of fuzzy integers is closed under subtraction.
Proof: Let t and u Zf be given. Then there exist r, s, v, w G Nf such
that t f s and u = v w. Then t u = f s {v w) = (f+w) {s+v).
Since Nf is closed under addition, r + w G Nf, and s + v G Nf. We have
thus expressed t u as the difference of two fuzzy natural numbers, so
t T u G Zf.
These properties suffice to show that Zf forms an abelian group under ad
dition. Next, it is shown that Zf forms a monoid under multiplication. Mul
tiplication is defined on Zf as it was on Nf. That is, given two fuzzy integers
f G Zf and s G Zf, their product f x s is defined by its assignment function,
Afxs(a) r(a) x s(cn),Va G (0,1].
Multiplicative Properties of Zf
Property 1 Multiplication is commutative on Zf. The proof is analogous to
the proof that addition is commutative on Nf.
Property 2 Multiplication is associative on Zf. The proof is analogous to the
proof that addition is associative on Nf.
Property 3 1 is the unique multiplicative identity on Zf. The proof is analo
gous to the proof that 1 is the unique multiplicative identity on Nf.
Property 4 The set of fuzzy relative integers is closed under multiplication.
Proof: Let t and u G Zf be given. Then there exist r, s, v, w G Nf such
that t f s and u = v w. Then txu = r sx (v w) = ((f x v) (r x
w)) ((Â§ x v) + (s x w)) = ((r x v) (f x w)) + ((s x w) (s x v)). Since
31
Nf is closed under multiplication, ((r x v) E Nf, (r x w) E Nf, (s x v) E
Nf, (sxw)g Nf, so ((r xv) (rx w)) E Zf and ((s xw) (s x 7)) E Zf.
Since Zf is closed under addition, t x u G Zf.
Property 5 There is a unique multiplicative identity on Zf, which is 1, defined
by its assignment function zlj(a) = 1, Va E (0,1]. The proof is omitted.
The discussion above shows that Zf forms an abelian group under addition,
and a monoid under multiplication. It remains to show that the distributive
property holds.
Distributive Property of Zf
Multiplication is distributive over addition. That is, given f,s,t G Zf, r(s+t) =
rs + ft. The proof is similar to proof for the commutativity of addition
on Nf, and is based on the distributive property of multiplication over
addition in the integers.
The distributive property, taken together with the additive and multiplicative
properties, make the set of fuzzy integers a commutative ring under multiplica
tion and addition. The next section defines division on the set of fuzzy integers,
which creates the set of fuzzy rational numbers.
2.3 Fuzzy Rational Numbers
Rocacher and Bose [75] construct the set of fuzzy rational numbers, Qf,
from fuzzy integers by introducing division and mimicking the construction of
the rational numbers from the integers.
32
Definition 2.7 (fuzzy rational numbers) Given two fuzzy natural numbers
f and s, such that s(a) > e, for some e > 0, for all a G (0,1], their quotient
f
t is a fuzzy rational number, which is defined by its assignment function,
s
Me) = rM, Va e (0,1],
s[a)
For illustration, define f by
and define s by
2, for a e (0,0.2],
1, for a G (0.2,0.3],
2, for a G (0.5,0.6],
1, for a G (0.6,0.8],
1, K. for a G (0.8,1],
4, for a G (0,0.4],
< 2, for a G (0.3,0.8],
1, for a G (0.8,1].
33
Then is defined by
0.5, for a G (0,0.2],
0.25, for a G (0.2,0.3]
0.5, for a G (0.3,0.4]
1, for a G (0.4,0.5]
0.5, for a G (0.5,0.6]
0.5, for a G (0.6,0.8]
0 for a G (0.8,1],
as illustrated in Figure 2.3. Note that t is not nonnegative, integervalued, or
nonincreasing on (0,1], in general.
We can make the following observations about the set of fuzzy rational
numbers, Qf.
General Properties of Qf
Property 1 The assignment function of a fuzzy rational number has a rational
value everywhere on its domain (0,1].
Property 2 The assignment function of a fuzzy rational number has a finite
number of jumps.
Proof: Since the fuzzy rational number t can be represented as the ratio
of two relative fuzzy integers, say f and s, the set of jumpdiscontinuities
of Ai is at most the union of the set of discontinuities of Af and the set of
discontinuities of A$. The result follows from the fact that a finite union
of finite sets is finite.
34
5
4
3
2
1
/v
s
5 \
4 i
3 !
2 '
1
0
1
2
a
i
0 "
1
2
I
a
i
ii
5
1
2
a
i
in
a
i
IV
Figure 2.3: I: The fuzzy natural number f (bold). II: f (bold) and s (dashed).
f
III and IV: Their quotient, the fuzzy integer t = (light).
Property 3 Every fuzzy rational number is a gradual number. It is bounded
because the numerator is bounded away from infinity (or negative infinity)
and the denominator is bounded away from zero. It is leftcontinuous
because both numerator and denominator are leftcontinuous, and the
number of discontinuities is finite, by Property 1.
Next, it is shown that Qf forms a partially ordered commutative ring, with
addition, multiplication, and order relations on Qf defined as they are for Nf.
Additive and Multiplicative Properties of Qf
Property 1 Addition is commutative and associative on Qf. The proof is
analogous to the proof that addition is commutative on Nf.
Property 2 Multiplication is commutative and associative on Qf. The proof
35
is analogous to the proof that addition is commutative on Nf.
Property 3 Multiplication is distributive over addition on Qf. The proof is
analogous to the proof that addition is commutative on Nf, and is based
on the distributive property of multiplication over addition on Q.
Property 4 The set of fuzzy rational numbers is closed under addition.
Proof: Given two fuzzy rational numbers, t and u, At(a) is a rational
number for every a G (0,1], and A^ia) is a rational number for every a G
(0,1]. Since the set of rational numbers is closed under addition, =
Ai{a) + Au(a) is a rational number for every a (0,1]. Specifically,
Af+il(a) has an integer numerator and an integer denominator for every
a G (0,1]. Then let a be the fuzzy integer whose assignment function
Aa(a) is defined to be equal to the numerator of A^+il(a) and let b be the
fuzzy integer whose assignment function A^(a) is defined to be equal to
the denominator of Ai+i(a) for all a G (0,1]. Thus t + u is represented as
the ratio of two fuzzy integers, a and b, so t + u G Qf.
Property 5 The set of fuzzy rational numbers is closed under subtraction. The
proof is analogous to the proof of Property 4.
Property 6 The set of fuzzy rational numbers is closed under multiplication.
The proof is analogous to the proof of Property 4.
Property 7 6 is the unique additive identity on Qf. The proof is analogous to
the proof that 6 is the unique additive identity on Nf
36
Property 8 1 is the unique multiplicative identity on Qf. The proof is analo
gous to the proof that 1 is the unique multiplicative identity on Nf
Property 9 Every fuzzy rational number f has a unique additive inverse f.
Property 10 Every fuzzy rational number f which is nowhere zero (i.e. r(a) ^
Nf, Zf, and Qf form commutative rings. The next section will show that Q
is also a commutative ring.
2.4 Gradual Numbers
The fuzzy rationals relate to the set Q as described in the following theorem.
Theorem 2.8 Ifx G Q, then there exists a sequence qj of fuzzy rational numbers
which converges in the L\ norm to x. That is, given e > 0, there exists N such
that n > N implies that \ qnda Ai(a)da\ < e. Then Q is a proper subset
of the completion of Qf
Proof: A partition P of (0,1] is a finite set of points 0 < p\ < P2 < < pn = E
and Api := p\ and Ap^ Pi p,i for i > 1. Now every x G Q is bounded and
has a countable number of simple discontinuities, so AÂ£(a) is Riemann integrable
on (0,1]. Then given ej > 0, there exists a partition Pj such that
Observe that the leftcontinuous step function rj : (0,1] * R defined as
0, Vn G (0,1]) has a multiplicative inverse
^ is defined by its assignment function .
(2.1)
rj(a) = AÂ£(pi) for a G (.r4,Pii]
37
has the property that
[ rJ(a)da = ^ ApfAstpf)
Jo i=i
Then (2.1) can be rewritten as
'l pi
rj(a)da / Ag(a)da
(2.2)
/ o Jo
Because the rationals are dense in the reals, rational numbers pf can be selected
in each interval [Ax(p{), Ai{pi)+^\ Then another leftcontinuous step function
qJ : (0,1] > R can be defined as
q3(a) =
rj(a) if rj(a) G Q
Then
p*(a) if rJ(a) ^ Q.
J qi(a)da J q^da < ^.
By the triangle inequality,
/ qj(a)da / Ax(a)da
Jo Jo
< Cj
In other words, {qj} converges to x in the L\ norm. Since every qJ (a) is a fuzzy
rational, we have our result.
It can be shown that Q forms a partially ordered commutative ring, with
addition, multiplication, and a partial order on Q defined as they were for Nf.
The proofs that are similar to Section 2.1 are omitted.
38
Additive and Multiplicative Properties of Q
Property 1 Addition is commutative and associative on Q.
Proof: Given r,s G Q, Ar+5(a) = r(a) + s(a),Va G (0,1]. Since f(a)
and s(a) G R, and addition commutes on the real numbers, f (a) + s(a) =
s(a) + r(a). As+f(a) = s(a) + r(a), so Af+s(a:) = A5+r(a) and addition is
commutative on Q. The proof of associativity is analogous, and depends
on the associativity of addition on R.
Property 2 Multiplication is commutative and associative on Q. The proof is
analogous to the proof of Property 1 and relies on the commutativity and
associativity of multiplication on R.
Property 3 Multiplication is distributive over addition on Q. The proof is
analogous to the proof of Property 1 and relies on the distributive property
of multiplication over addition in R.
Property 4 The set Q is closed under addition.
Proof: Two gradual numbers, t and u, have bounded assignment func
tions Af(a) and A(a) that are leftcontinuous with a finite number of
simple discontinuities. Then A^+jl(a) = At(a) + As(a) is bounded and
leftcontinuous, and the set of discontinuities of A^+ii(a) is at most the
sum of the discontinuities of At(a) and the discontinuities of A(a), so is
finite.
Property 5 G is closed under subtraction. The proof is analogous to the proof
of Property 4.
39
Property 6 Q is closed under multiplication. The proof is analogous to the
proof of Property 4.
Property 7 0 is the unique additive identity on Q.
assignment function A?(a). Then r+0 is defined by its assignment function
A?+d{a) = Af(ot) + ^(a) = A?(a) + 0 = Af(a),Vo G (0,1]. Since Tf+o =
Af, f + 0 = f for any f G Q, so 0 is an additive identity on Q. To see
uniqueness, fix f G Q and let f+t = f. Then Af(a) + A^(a) ylf(a), Va G
Property S 1 is the unique multiplicative identity on Q.
Proof: To see that 1 is a multiplicative identity, consider any f G Q
with assignment function Af(a). Then f x 1 is defined by its assignment
function j4?xi(a) = A?(a) x ^4j;(a) = Af{a.) x 1 = A?(a),Vcr G (0,1]. Since
Afxi = Af, r x 1 = f for any r G Q, so 1 is an additive identity on Nf.
To see uniqueness, fix r G Q and let f x t = f. Then Af(a) x Ai(a) =
Property 9 Every gradual number f has a unique additive inverse f.
Property 10 Every gradual number f which is bounded away from zero (i.e.
there exists e > 0 such that \f(a)\ > e Va G (0,1]) has a multiplicative
Proof: To see that 0 is an additive identity, consider any f G Q with
(0,1]. Thus Ai{a) = 0, Va G (0,1] and t = 0.
Af(a), Va G (0,1], Thus ^4t(a) = 1, Va G (0,1] and t 1.
inverse
such that r x
= 1.
is defined by its assignment
40
Then Q is a commutative ring. This dissertations preliminary characteriza
tion of Q is concluded, and further characterization is left to future work. The
next section consists of observations made in the course of this characterization
of g.
2.5 Discussion of the Nature of Gradual Numbers
Nf, Zf, and Qf have been described as subsets of Q. A stated purpose of this
chapter was to use the characteristics of these subsets and of their construction
to gain insight into the nature of gradual numbers. One defining characteristic
of the set of natural fuzzy numbers is the nonincreasing membership function,
and there may be a connection between fuzzy naturals and gradual numbers
with nonnegative nonincreasing membership functions. In particular, a fuzzy
natural number can indicate the size (in the form of gradual cardinality) of a
finite fuzzy set, and a nonnegative nonincreasing gradual number can be used
to indicate the size (in the form of gradual width) of a fuzzy interval. Given
a fuzzy interval 5 with gradual endpoints [z~,z+], the gradual width of the
fuzzy interval, as a function of a, is the nonnegative, nonincreasing gradual
number f defined by Af(a) = z+(a) z~(a). Figure 2.4 shows an example of a
nonnegative nonincreasing gradual number and one fuzzy interval for which it
represents the width.
The relationship between fuzzy natural numbers and their associated finite
fuzzy sets suggests this relationship between nonnegative nonincreasing grad
ual numbers and some associated fuzzy sets. Recall that the difference between
two fuzzy natural numbers is not nonnegative or nonincreasing, in general. As
a result, a gradual number with an integervalued assignment function (in other
41
Figure 2.4: Given the fuzzy interval W, the width of each acut of W can be
represented by the nonnegative nonincreasing gradual number \W\.
words, any fuzzy integer) might represent the difference of two fuzzy natural
numbers, or the difference between the gradual cardinalities of two finite fuzzy
sets. This suggests, by analogy, that a general element of Q might be represented
as a difference of two nonnegative, nonincreasing gradual numbers, or as the
difference between the sizes of two fuzzy intervals.
Figure 2.5 illustrates how a gradual number can be equivalent to the differ
ence of two nonincreasing gradual numbers, which in turn measure the width
of two fuzzy intervals.
2.6 Chapter Summary
This chapter has examined gradual numbers in a slightly different context
than in their original role as elements of fuzzy intervals. Indeed, they can be
associated to the gradual cardinalities of finite fuzzy sets in the same way that
the set of real numbers is related to the set of natural numbers. Furthermore,
it has been shown that Q can be equipped with addition, multiplication, and
several order relations to form a partially ordered commutative ring. Future
42
Figure 2.5: I. The gradual number f is the difference of the nonnegative,
nonincreasing gradual numbers \W\ and \ V\. In turn, \W\ and C measure the
width of fuzzy intervals W and V.
work might investigate whether a denumerable subset of Qf is dense in Q. which
will then give an alternative theoretical foundation for computer approximations
of the elements of Q.
The definition and characterization of Q may also form a foundation for
the use of gradual numbers in mathematical models based on fuzzy intervals.
Chapters 3 and 4 address potential roles for gradual numbers in fuzzy optimiza
tion. Chapter 3 uses gradual numbers to find optima of linear programming
problems with fuzzy feasible regions. In Chapter 3, the partial order established
on Q is of particular concern. Chapter 4 uses gradual numbers in fuzzy non
linear programming problems, with emphasis on the application of extending
differentiable realvalued functions to fuzzy intervals.
43
3. Gradual Numbers in Linear Optimization: A Gradual Simplex
Method
The goal of a linear programming problem with fuzzy constraints is
to optimize a linear objective function over a fuzzy feasible region.
The optimal element will be a singleton of the fuzzy feasible set, or
a gradual number. This chapter explores the potential of a gradual
simplex method, which pivots through the vertices of the fuzzy feasible
region, (these vertices are elements ofQ), to find the gradual optimal
element. The resulting optimum is parameterized, producing a curve
that reflects the tradeoff between the degree of feasibility and the
objective function value. Since each feasibility level corresponds to
a crisp solution, the gradual simplex method provides the decision
maker with flexibility and a clear way to defuzzify the solution.
The decision sciences combine information about system requirements and
preferences to identify a course of action with a desirable outcome. In the
course of modeling, fuzzy constraints naturally arise from preferences, which
often reflect a gradual transition from a preferred state of affairs to a non
preferred state. Fuzzy constraints can also arise from vague information about
requirements. As a result, it is often appropriate and desirable to assign a
degree of satisfaction to each acceptable decision, that is, to each element of the
feasible region. The result is a fuzzy feasible region. Figure 3.1 shows a polytope
representing the set of feasible solutions for a linear program, with shading to
44
01 234567891 01 23456789 a
Figure 3.1: I: Feasible region. The shaded area satisfies 0 < x\ < 6, 6x2X\ <
30, x2 > 0. II: Fuzzified feasible region. Darker shading represents the most
satisfactory decisions, which are a safe distance from the edge, and lighter
shading represent partially satisfactory decisions, which exceed the edges by a
small amount.
indicate a fuzzified feasible region in which solutions that violate the constraints
by a small amount are somewhat satisfactory, and solutions that do not come
close to violating the constraints are most satisfactory.
A fuzzy feasible region is appropriate whenever a decision maker might be
willing to relax requirements in to achieve a more desirable outcome. A mo
tivating example is the radiation therapy planning (RTP) problem. Patients
undergoing radiation treatment for cancerous tumors receive radiation from sev
eral angles. The RTP optimization problem looks for durations and angles of
radiation which will deliver a lethal dose of radiation to the tumor, while keep
ing radiation to the rest of the patient s body at safe levels, taking particular
precautions for critical organs. There are many different mathematical formu
lations for the RTP problem (see [35] for a survey), but for this example, let
the feasible region represent the set of treatment plans that are acceptably safe,
and let the objective be to maximize the amount of radiation delivered to the
tumor.
45
The feasible region has intrinsically flexible, or fuzzy, boundaries if the ra
diation oncologist is willing to exceed the recommended total body radiation by
a small amount to reach a level of radiation which will surely kill the tumor.
On the other hand, the radiation oncologist might want to deliver a slightly
lower dose to the tumor to protect a particularly vulnerable critical organ, espe
cially if the patient is also undergoing chemotherapy or surgery. In other words,
the feasible region is not necessarily fixed, but is gradual, subject to adjust
ment when the tradeoff is desirable. Fuzzy optimization methods, along with
nonfuzzy multiobjective optimization methods, aim to solve this problem and
others with similarly fuzzy requirements. The goal of this chapter is to explore
a potential role for gradual numbers in optimization by looking at the problem
through a fuzzy paradigm from problem formulation to solution. This repre
sents a departure from nonfuzzy multiobjective optimization techniques, and
also from most fuzzy optimization techniques, which use nonfuzzy intermediate
calculations [25].
3.1 Background of Fuzzy Optimization
Bellman and Zadeh first propose a mathematical programming problem with
fuzziness [5]. They observe that a conventional mathematical program has three
principal components: A set of alternatives, X, a set of constraints, C, which
restricts the choice of alternatives, and an objective function, z, which measures
the desirability of the outcome of each alternative. Bellman and Zadeh pro
pose that, in a fuzzy environment, a more natural framework is one in which
a goal (or goals) replaces the objective function, with such goals consequently
treated as constraints. Each fuzzy goal, Gi, or fuzzy constraint, Cj, is defined
46
as a fuzzy set on the universe of solution alternatives, X, via a membership
function (Aq.(x) or fj,g.{x). In the typical formulation of Bellman and Zadehs
fuzzy decision making, these fuzzy goals and fuzzy constraints are represented
by fuzzy intervals. For the RTP problem, the set of fuzzy constraints would be
the set of radiation dosages thought to be safe, and the fuzzy goal would be the
set of radiation dosages thought to be potent enough to kill the tumor. Then
the fuzzy decision, D, is the fuzzy set resulting from the intersection of C and D
and is characterized by membership function Hf}{x)) = minfi^, (x)).
The optimal decision is chosen to maximize (/i^x)). Tanaka, Okuda, and Asai
proposed an acutbased algorithm to identify this optimal decision [82], and
Zimmermann formulated it as a linear program [95]. Figure 3.2 shows a fuzzy
decision as a fuzzy goal intersecting a fuzzy feasible region. The solution re
sulting from Bellman and Zadehs model is the maximizer of this fuzzy decision
region. Observe that the solution is a single, crisp solution, associated with a
single a level (the highest a in the fuzzy set D), and that the solution is highly
dependent on the arbitrary process by which the objective function is translated
into a goal.
Many fuzzy optimization approaches were proposed in the wake of Bellman
and Zadehs introduction of fuzzy decision making, with a large subset of these
approaches focused on fuzzy linear programming. The authors survey of fuzzy
linear programming methods is found in [85] and will not be repeated in full
detail here. The plethora of fuzzy linear programming approaches reflects the
fact that there are a variety of interpretations for the underlying fuzzy linear
47
a
T7
2.
0 1 2 3456789!
a
i
2,
1
01
0 1
Mb(x)
________
3456789 1!
Me(x)
a
0 1 2 345 6789 HI
Mg(x) ..
TU. X*\
6 x'* H>(x)
L.x.........;&~x
v / /
. /.
3 4 5 6 7 8 9 1''
Figure 3.2: I: A threedimensional view of a set of fuzzy constraints. II: An
example of a fuzzy goal for a maximization problem. III. The intersection of
the fuzzy constraints (characterized by i^q(x)) and the fuzzy goal (characterized
by Hq(x)). IV. The fuzzy decision (characterized by /j,f}(x)) and the optimal
decision, x*, which maximizes Hq(x).
48
program
maximize cTx
(3.1)
subject to Ax
where c and b are vectors of fuzzy intervals, .4 is a matrix of fuzzy intervals,
and < is a fuzzy relation. Indeed, even the fuzziness of each individual com
ponent, c, <, A, and b, is subject to various interpretations. This chapter is
primarily concerned with the linear program with fuzzy constraints, which shall
be represented here as 1
maximize cTx
(3.2)
subject to Ax < b.
The inequality Ax < b compares a realvalued vector, Ax to a fuzzy interval
valued vector, b, so is ambiguous. Dubois and Prade introduced four possible in
terpretations of inequality constraints in fuzzy optimization[16], and most fuzzy
linear programming methods abide (either explicitly or by implication) by one
of the following:
i. Ax < b~(a),\/a,
ii. Ax < 6+(a),Va,
iii. Ax < b~(a), for some a,
iv. Ax < b+(a), for some a,
1 Fuzzy constraints represented with B and fuzzy constraints represented with < both
appear in the literature, with overlapping interpretations, and subtle distinctions that are
outside the scope of this work [85]. For our purposes, all fuzzy constraints will be represented
with B.
49
where the fuzzy interval B is a fuzzy interval with gradual endpoints
Which of these interpretations of Ax < B is used varies by algorithm and
application.
Ralescu [71] first suggested that the solution to a fuzzy optimization problem
should be fuzzy, rather than crisp, and Verdegay [89] proposed a method for
finding such a fuzzy solution. Given a crisp linear objective function, cTx, to
be maximized over the fuzzy feasible region Ax < b, where b is a fuzzy interval,
Verdegay defines, for each alevel, the mathematical program
maximize cTx
(3.3)
subject to Ax < b(a).
Verdegay defines this b(a) in a way that is equivalent to the gradual number
endpoint of fuzzy interval b. Now b(a) is a real number, so (3.3) is a welldefined
linear program at each alevel, and an optimal solution x*(a) can be found for
as many a (0,1] as the user wishes to compute. There is a tradeoff between
computational efficiency (obtained by evaluating few alevels) and solution ac
curacy (obtained by evaluating many alevels). This tradeoff is circumvented
in the special case where the membership functions for the components of B
are linear (i.e. the B{ are triangular or trapezoidal fuzzy intervals). Then the
problem takes on the form
maximize cTx
subject to Ax < b + aAb,
(3.4)
where 6j is the minimum value in the core of 6; and A6, is the slope of the mem
bership function of 6*. Problem (3.4) can be solved with the w'ellestablished
techniques of parametric linear programming [63]. Observe that the fuzzy
50
optima, cTx*(a), of both (3.3) and (3.4) are real numbers parameterized by
a (0,1], which means these fuzzy optima are gradual numbers. The gradual
simplex method proposed here is related to Verdegays work in that it solves
a parameterized optimization problem and produces solutions cTx*(a) that are
gradual numbers. Section 3.1.1 will discuss the implications of gradual solutions
further. The gradual simplex method differs from Verdegays method by solving
problems with more general fuzzy endpoints and by offering interpretable partial
solutions at every stage of the algorithm.
A gradual simplex method can be seen as a parameterization of a linear
program, so a brief review of basic of parametric programming is appropriate.
There are two traditional applications of parametric programming. Given a
mathematical program, parametric programming can be used either to search
for an optimum of the problem or to study the stability (or reliability) of a model
[96]. Although the method in this chapter can be viewed as a type of parametric
programming, it is motivated from a different perspective. The goal of the
current work is to explore the use of gradual numbers as a vehicle for propagating
fuzziness, from the formulation of the fuzzy optimization problem through every
step of the optimization procedure all the way to the implementation of the
solution, which is gradual. Section 3.1.1 examines the parameterized solution
provided by the gradual simplex method more closely.
The literature records a variety of combinations of parametric programming
and fuzzy sets, many of which, however, are not directly related to the current
research. For instance, parametric programming has been used to assess the
stability of nonlinear multiobjective programs with fuzziness in the parameters
51
[41]. There also have been applications to queuing theory, in which queues with
fuzzy rates and policies are represented by parameterized, or gradual, numbers.
Then the functions that describe queuing system characteristics (like expected
waiting time and expected queue length) are extended to accept these fuzzy
inputs. The function extension is accomplished through parametric nonlinear
programming because it seeks the minimax of all component membership func
tions. For an introduction to this body of research, see [13] or [42],
Carlsson and Korhonen [9] introduced fuzzy parametric programming in
1986. Like the gradual simplex method developed in the next section, fuzzy
parametric programming produces a gradual optimum, where the precision of
the gradual optimum is defined by the intersection of membership functions
which belong to imprecise parameters denoted by the minimum of the mem
bership functions. Carlsson and Korhonen observe that the inherited precision
in the optimal solution equals the precision of the most risky of the parame
ters and point out that it is important for a solution to be both optimal and
implementable at the same time. Arikan and Gungor extend fuzzy parametric
programming to problems with multiple objective functions [3]. Their devel
opment of fuzzy parametric programming is limited to programs whose fuzzy
membership functions all have the same shape, for instance, all triangular, or
all trapezoidal, or all convex continuous. An example in Section 3.2 will demon
strate that this is not always a meaningful way to model reality, and the grad
ual simplex method will address fuzzy linear programs with a variety of fuzzy
interval shapes. Fuzzy parametric programming takes the important step of
extending Verdegays work to produce a fuzzy solution (which is actually a
52
parameterized or gradual solution) to a fuzzy problem. The gradual simplex
method produces fuzzy intermediate solutions as well as a fuzzy final solution.
Other researchers have recognized the value of a fuzzy solution to a fuzzy
programming problem. For instance, Wang and Liao [90] propose a heuristic
algorithm to analyze a differentiable nonlinear integer program with fuzzy in
equality constraints. They parameterize the fuzzy inequality and use a hybrid
solution procedure incorporating a genetic algorithm. Gani [29] notes that any
crisp result represents a loss of information and that only a fuzzy solution can
conserve the fuzziness of the problem. While these observations have philosoph
ical value, it must be pointed out that only crisp solutions are implementable. A
fuzzy solution without a key to defuzzification cannot be implemented, which
is why the gradual simplex method developed here has a defuzzification process.
Lai and Hwang [50] introduce a unique and interactive fuzzy linear program
intended to improve flexibility and robustness. They develop a metaprogram
which trades off among solutions of four different programming techniques. The
interactive concept provides a learning process about the system, whereby the
decision maker is expected to learn to recognize good solutions and relative
importance of factors in the system and then design a highproductivity system.
This is similar to the gradual simplex method in the sense that it gives a high
degree of transparent control to the decision maker. Lai and Hwangs method
allows interaction in the early stages of the algorithm, whereas the gradual
simplex method allows for interactivity in the defuzzification of the final output.
The gradual simplex method in this chapter is a parameterization of the
simplex method, but it is not the only fuzzification of the simplex method in
53
the literature. A body of research by Mahdavi [57] and Nasseri [64] introduces
a fuzzification of the simplex method. They seek a fuzzy vector x (made of
triangular fuzzy intervals) which maximizes a fuzzy objective z = cTx, subject
to fuzzy constraints Ax < b (where b is comprised of triangular fuzzy intervals).
Mahdavi and Nasseri introduce many concepts which are useful to the current
work, including feasibility, degeneracy, and fuzzy basic solutions. In addition,
the entire theory is rooted in a strong duality theory [58, 59]. Though the set
up of the problem is similar to the gradual simplex method introduced in this
chapter, the maximum is determined by a ranking function, which induces a
complete order on the set of triangular fuzzy intervals. The result is a sim
plification which eliminates some of the information in the fuzzy interval. In
contrast, the gradual simplex method is designed to work with the partial order
of gradual numbers so that none of the fuzzy information is lost during the op
timization. Although the gradual simplex method and Mahdavi and Nesseris
methods both produce fuzzy solutions, Mahdavi and Nasseris result is actually
a fuzzy interval. Any defuzzification process and semantic interpretation is left
to the user. In contrast, the gradual simplex method introduced here produces a
parameterized, or gradual, solution, from which a crisp solution can be selected
to be put into production.
Another fuzzy simplex method is proposed by Gao [30], who considers prob
lems with parameters that are trapezoidal fuzzy intervals. In this situation, the
best case simplex is solved, with a membership level of 0, the worst case scenario
is solved with a membership of 1, and solutions with intermediate functions are
produced by linear extrapolation. This reduces to the method proposed by
54
Verdegay, and while implementable and semantically viable, it is limited to
problems with triangular and trapezoidal fuzzy intervals.
Although this chapter only considers linear programs with fuzziness in the
constraint coefficients and righthand sides, much work has been done to solve
the fully fuzzy LP (3.1), with fuzzy objective functions. The attempts to date
have been limited in their success (see [62] as an example), or in the class of fuzzy
membership functions they consider (for example, [8].) A future extension of
the current work may be a gradual simplex method for the fully fuzzy problem.
3.1.1 A Gradual Optimum
The goal of any linear programming problem is to identify an optimal ele
ment from its feasible region. When the linear programming problem contains
fuzzy inequalities, the cvsets of this feasible region are polytopes, so the fuzzy
feasible region is a connected fuzzy subset of Rn. In other words, it is an n
dimensional fuzzy interval (fuzzy intervals defined in each of n dimensions),
which means that the elements of the feasible region are gradual ntuples, el
ements of Qn. This is exactly the kind of optimum Verdegay finds with (3.3)
for triangular or trapezoidal fuzzy intervals. This chapter is concerned with a
broader class of L R fuzzy intervals. For visualization of a gradual element of a
fuzzy feasible region, see Figure 3.3. An optimal element from the fuzzy feasible
region, which is a gradual ntuple, x*(a), will produce a gradual optimum, z(a),
also parameterized by a. The graph of z(a) represents the relationship between
optimality (on the zaxis) and feasibility (on the aaxis), leaving the feasibility
optimality tradeoff decision in the hands of the decision makers rather than
the modeler. For an example, see Figure 3.4. This gives control to the decision
55
Ol 2 345 6789] 01 2 345 6789 H
a
I
1
6.. "?'
1 1 \ ,x
0
0 1 2 3 4 5 6 7
Figure 3.3: I: A threedimensional view of the the fuzzy feasible'regions from
Figure 3.1. The feasible region still has two dimensions, with the adimension
added to show the membership function. II: A gradual number on the edge of
the feasible region. III. A gradual number in the interior of the feasible region.
IV. A gradual number at an extreme point of the feasible region.
56
maker, who may have unarticulated situational knowledge of which the modeler
is unaware. Once the decision maker has selected a*, the most satisfactory a
level for the situation, the associated crisp optimal solution x* is obtained easily
by evaluating x*(a*). The selection of a* may be suggested by the model, but
will be interactive with the decision maker.
For example, in the radiation therapy planning problem, one possible result
of optimization over the fuzzy feasible region is shown in Figure 3.4. A gradual
solution of this form gives the decision maker both the information and the
flexibility to choose a treatment plan appropriate to a particular patient. For a
hypothetical juvenile patient with a slowgrowing tumor that is easily accessible
surgically, the radiation oncologist might pick an optimal solution with a very
high degree of safety, represented by an alevel near one. Given the same gradual
optimum for an adult patient with a fastgrowing brain tumor inaccessible by
surgery, the radiation oncologist might prefer a less safe solution with a higher
likelihood of delivering a tumorcidal dose of radiation.
The objective of this chapter is to find an optimal gradual element of a
fuzzy feasible region. When the gradual endpoints of the constraints are lin
ear functions, parametric linear programming, as indicated by Verdegay [89],
is an efficient and established method of finding the gradual solution. It will
be demonstrated that linear fuzzy intervals are not always the best choice for
modeling the constraints of the problem, and a general method for finding a
gradual optimum is desired.
57
Figure 3.4: A hypothetical result for a radiation therapy planning problem.
z represents the total level of radiation delivered to the tumor, and a indicates
the degree to which the safety requirements are met. Given this graph, the
oncologist might choose a riskaverse strategy for Patient 1, for whom alternative
treatments are available, and an aggressive strategy for Patient 2, for whom
radiation is the only option.
3.2 Main Results: A Gradual Simplex Method
A gradual simplex method is introduced to address the general class of linear
programming problems with fuzzy feasible regions. This section describes the
gradual simplex method for a linear programming problem with fuzzy right hand
sides.
In this chapter, the fuzzy righthand sides are restricted to be interval end
points which are elements of Q. That is, they are nonincreasing (because they
are endpoints of fuzzy intervals) and are bounded and leftcontinuous with a
finite number of jump discontinuities. Previous related work has been restricted
to linear righthand sides.
A motivating example will demonstrate the need to model fuzzy constraints
with nonlinear fuzzy righthand sides. A small family farm has 40 acres, 4 of
58
which are currently used for a farmhouse, barn, front and back yard for children
and pets, leaving 36 acres for planting. The farmer works an office job because
farming on a small scale is not sufficiently profitable to support her family.
She restricts herself to working her land on Saturdays year round, and takes
a week of vacation from her office job during harvest time. Together with the
occasional holiday, she has 60 days per year for farming. She has the ability to
work Sundays on occasion, but this causes significant heartache to her church
going family. She currently has $1500 in a bank account to finance her farming
operation. She would like to limit her seed expenditures to $1000 so that she
has money in her account to cover emergency expenses. For spring planting, she
is deciding among crops A, B, and C, with characteristics described in Table
3.1, and wants to know aq, how many acres to plant of crop A, :r2, how many
acres to plant of crop B, and Â£3, how many acres to plant of crop C.
Crop A Crop B Crop C
$ per acre for seed 40 20 30
labor per acre (in days) 1 2 1
$profft per acre 100 300 200
Table 3.1: Relevant characteristics of the three crops under consideration for
spring planting.
The constraints in this case are preferences rather than requirements. The
farmer can choose to work up to ten Sundays, for a total of up to 70 days of labor,
which is less satisfactory than working no Sundays because it compromises her
faith. She can also chose to plant up to three of the acres currently set apart
59
for the use of her family and animals, for a total of up to 39 acres, which is less
satisfactory because it compromises her childrens and animals quality of life.
Finally, she can choose to spend up to an additional $500 over her seed budget
of $1000, (which is less satisfactory because it creates financial stress). In fact,
for each of these three constraints, the farmer can specify a level of satisfaction,
a, creating a fuzzy feasible region for the problem.
The reduced quality of life for her children and animals is assumed to be
directly proportional to the reduction of their playspace, so the fuzzy region
of the farmers satisfaction with her land usage has a linear gradual number
for an endpoint with full satisfaction (a = 1) at 36 acres or less, and minimal
satisfaction (a 0) at 39 acres. This results in the acreage constraint
5i + X2 + X3 < 39 3a (acreage constraint). (3.5)
Note that the decision variables are elements of this new fuzzy feasible region,
so are gradual numbers, denoted with a tilde. Missing even a single church
service to work her land is undesirable, but once shes missed a few Sundays, the
heartache associated with missing additional Sundays decreases, so the farmers
satisfaction with her number of labor days has a concave gradual number for
an endpoint with full satisfaction (a = 1) at 60 days or less, and minimal
satisfaction (a = 0) at 70 days. This can be modeled by the labor constraint
x\ + 2x2 + Â£3 < 70 10\/a (labor constraint). (3.6)
The farmer is not opposed to exceeding her spending goal of $1000 by a little bit,
but the closer her savings account balance is to zero, the more anxiety she feels,
so her satisfaction with her spending on seeds has a convex gradual endpoint,
60
with full satisfaction (a = 1) at $1000 or less, and minimal satisfaction (a = 0)
at $1500, as modeled by
405i + 20^2 + 30^3 < 1500 500a2 (seed money constraint). (3.7)
The fuzzy feasible region described by constraints (3.5)(3.7) is paired with a
profit maximizing objective function to create the fuzzy linear programming
problem
maximize 100xi +300x2 +200x3 (profit objective)
subject to 40xi +20x2 +30xs < 1500 500a2 (seed money constraint)
Xi + 2X2 ++? < % o 1 o r (labor constraint)
Xl +X2 +^3 5: 39 3a (acreage constraint)
Xi > 0, Vi.
This fuzzy linear programming problem is parameterized by a, but a solution
cannot be found with parametric linear programming methods because the ele
ments of b, the gradual righthand side, are nonlinear. This class of problems
motivates the development of a gradual simplex method.
3.2.1 Formulating the Problem
A gradual simplex method is applied to fuzzy linear optimization problems
in the form
maximize cTx
subject to Ax < b (3.8)
x > 0,
where A is a rankm m x n matrix of real numbers, c is an nvector of real
numbers, b is an mvector of gradual numbers, and < is the partial order defined
61
on gradual numbers. The fuzzy feasible region of (3.8) has the form
Ax < b
x > 0,
which corresponds to
Ax + Is b
(3.9)
x, s > 0,
where I is the m x m identity matrix, and Â§ is the mvector of gradual slack
variables. For notational simplicity, we redefine
c X
c  0 , x = s
and A = [A I],
Then (3.8) becomes
maximize crx
subject to Ax = b (3.10)
x > 0.
Together with the requirement that 6 Qm, (3.18) will be considered the stan
dard form2 for the development of this gradual simplex algorithm. The require
ment that all b 6 Q means the assignment functions are leftcontinuous on (0,1].
Then the following argument holds is for every alevel of the parameterized
LP. For every binding constraint in the original problem (3.8), the corresponding
slack variable of (3.9) must be zero. Since an extreme point of the feasible region
in nspace corresponds to n binding constraints, n of the n + m variables must
be zero at an extreme point. Furthermore, it is assumed that A has full row
2There are a variety of standard forms in the literature. For the sake of clarity and
convenience, a fuzzified version of Vanderbeis convention [88] is followed here.
62
rank, which means that the system of equations defined by the m constraints
and the m nonzero variables must have a unique solution. In other words, the
columns of A associated with nonzero variables are linearly independent and
form a basis for the vector space corresponding to matrix A. Such a solution is
called a basic solution in linear programming. Analogously, any gradual number
which is a basic solution at every cclevel might be called a gradual basic solution.
If, in addition to satisfying the m technical constraints at every a level, the x,
are all also nonnegative, they might be said to form a gradual basic feasible
solution. Because the set of gradual numbers, Q, is not fully ordered, the same
constraints might not be binding at all a levels. That is, given a gradual basic
feasible solution x, the set of m binding constraints for a 0 may differ from
the set of m binding constraints for a = 1. As a result, at different alevels,
different subsets of the m + n variables of (3.9) might be zerovalued. However,
for every a, there will be a system of m constraints and m nonzero variables
with a unique solution, and for every a, at least n of the Xi(a) will be zero.
Definition 3.1 (Basic Feasible Gradual Solution) A gradual basic feasible
solution, x, is an n + mtuple of gradual numbers (iq, ...xn, sq, which meets
the following conditions at each alevel:
i. (x(a)) solves Ax = b.
ii. n or more entries in x(a) are zero.
in. x(a) > 0.
iv. The columns of A associated with nonzero entries of x are linearly inde
63
pendent.
When more than n of the Xj(a) are zero at some a, the gradual basic solution
is called degenerate for that a. Degeneracy will be further addressed in Section
3.2.3. If there are no basic feasible solutions, the fuzzy LP is said to be infeasible.
for every feasible y. A feasible fuzzy LP with no optimal solution would be said
to be unbounded. When the fuzzy feasible region is restricted to be a subset of
Q, the feasible region is bounded, so the unbounded case is not a concern in this
dissertation.
Proposition 3.2 If a fuzzy LP has at least two different gradual basic solutions,
it has an infinite number of gradual basic solutions to the fuzzy LP.
Proof: Let f and s be gradual basic solutions such that f s. Because the LP
is in standard form, r,s G Q, which means that Af and As are leftcontinuous
and do not have any isolated points, so there is an interval [a, a+] such that
Af(a) 7^ As(a), Va G [a a+].
Define a family of new basic solutions t parameterized by (3 G [a, a+] such that
Each solution in the family is basic because at every alevel it is equal to either
Basic solutions are critical to the theory of linear programming because of
the following result:
A feasible solution x is said to be an optimal solution if and only if cTy < cTx
r(a) or s(a), which are basic.
64
Theorem 3.3 (Fundamental theorem of linear programming.) Given an LP in
standard form,
i. if there is a feasible solution, there is a basic feasible solution, and
ii. if there is an optimal solution, there is a basic optimal solution.
For the proof, the reader is referred to [88]. This theorem holds for every alevel
of the fuzzy LP (3.8), and an analogous result can be stated for the fuzzy LP.
Theorem 3.4 Given a fuzzy LP in the form of (3.18),
i. if there is a feasible gradual solution, there is a gradual basic feasible solu
tion (e.g. a feasible solution in Q), and
ii. if there is an optimal gradual solution, there is a gradual basic optimal
solution (e.g. an optimal solution in Q).
Proof:
Restrict the fuzzy LP to an arbitrary alevel. The fundamental theorem
of linear programming clearly holds for this restriction, so
i. if there is a feasible solution, there is a basic feasible solution, and
ii. if there is an optimal solution, there is a basic optimal solution.
If there is a feasible solution at every alevel, it must be shown that there
is a gradual vector of feasible solutions. Specifically, there must be a vector
of gradual basic solutions which is bounded and leftcontinuous.
65
i. Every gradual feasible solution must be bounded. Suppose x is a
gradual vector of feasible solutions to (3.9) Then any x solving Ax_1f>
is bounded because A is constant and because every entry of b is an
element of Q and therefore bounded.
ii. It is next shown that x can be constructed that is leftcontinuous,
basic, and feasible for every alevel. Fix a G (0,1]. Then from step 1
there is a basic feasible x*(a) for which x*(a) = B~lb{a), where B is
composed of the columns of A corresponding to the basic variables in
x*(a). Because b G Q is leftcontinuous at a and B~x is constant, the
basic gradual solution defined on some semiclosed interval (a e, a]
as x* := B~lb is continuous on that interval. Since x*(a) is feasible,
each entry is either zero or strictly greater than zero. If x*(a) > 0 for
all i, there is a semiclosed interval (a to, a\ C (a e, a] for which
x* > 0 by the leftcontinuity of x* := B~lb. Then x* is continuous,
basic, and feasible on (a eo,a]. If x*(a) = 0 for some i, and there
exists an interval (a o,a] C (a e, a] for which x*(a) > 0, then
x* > 0 because x* := B~lb is continuous. Then x* is continuous,
basic, and feasible on (a eo,a]. If no such interval exists, then x*
can leave the basis at a and be replaced by some nonbasic variable
Xj, which will be zero, so will not affect the feasibility of the basic
solution. We call the new basis x* and the associated columns of A
we call 5. If there exists an interval (a eo, a] C (a e, a] for which
x*j{oi) > 0, then x* > 0 by the continuity of x* Such an Xj is
sure to exist because if there is no nonbasic Xj greater than or equal
66
to 0. on some interval, (a eo,a], then there is no gradual feasible
solution, which violates the hypothesis of the theorem.
It must be shown that there is a vector of optimal solutions that is an
element of Qn. Specifically, there must be a vector of gradual basic optimal
solutions which is bounded and leftcontinuous.
i. Since every gradual feasible solution is bounded, every gradual opti
mal solution is bounded.
ii. It is next shown that at every a, there is some gradual basic solution
x* which is leftcontinuous, basic, and optimal. Fix a (0,1]. Then
by the fundamental theorem of linear programming, there is a basic
optimal solution x*(a) for which for which x*(a) = B~1b(a), where B
is composed of the columns of A corresponding to the basic variables
in x*(a). Because b G Q is leftcontinuous at a, the basic gradual
solution defined on some semiclosed interval (a e, a] as x* B~lb
is continuous on that interval.
Now if x is optimal on some interval (a e0,a] C (a e,a], the
proof is complete. Otherwise, cTx*(a) < cTy(a) for an optimal y,
which can be assumed, without loss of generality to be in Q because
the conditions of the corollary require that stipulate the existence of
a gradual optimal solution. Since y G Q, it is continuous on some
interval (a eyi a]. Then, because x*(a) is leftcontinuous, and is not
optimal on any (a eo,a] C (a e^a], cTx*(a) < cTy(a) on some
(a e,a) C (a ty,a].
67
Now choose a new interval, (i ei,ai] C (a e0, a) Then the
continuous basis x* is not optimal anywhere on the interval. But
by the fundamental theorem of linear programming, there is a basic
optimal solution at on, call it x\. Because b G Q is leftcontinuous at
a, the basic gradual solution defined by x\ := B~lb is continuous on
(ai ei,ai]. Now if x\ is optimal on some interval (au ei,ai] C
((*1 c, cvi ], the proof is complete. Otherwise, because .x*(o) is left
continuous, and is not optimal on any (cq e^cci] C (au Â£i,ai],
cTx*l{a) < cTy(a) on some (ai ei, Qi) C (cti ei, ai].
The proof continues in this manner, with a sequence of nested semi
closed intervals, until a basic solution is found which is leftcontinuous
and optimal on a semiclosed interval. At a fixed a*, there are only
(m + n)! , . . . , , .
; basic solutions, suppose this process does not find a basic
n\
(jyi ( fi\\
optimal solution that is leftcontinuous in ;iterations. Then
n!
there must be a point, o;*, which is in PI(Q:* ei,ai] fr which every
basic solution has been shown to be suboptimal. This contradicts
the fundamental theorem of linear programming.
The implication of the fundamental theorem of linear programming and The
orem 3.4 is that to find an optimum solution for a fuzzy LP, it is sufficient to
search the gradual basic feasible solutions.
68
Recall the fuzzy linear program in standard form with slack variables:
max cTx
subject to Ax = b (3.11)
x > 0.
Now any m gradual basic variables create the mvector Xb, which corresponds, at
each alevel, to m linearly independent columns of A. Because the gradual basic
solution is leftcontinuous, the m parameterized columns of A which correspond
to gradual basic variable are also leftcontinuous. The matrix A is fixed, but the
columns which correspond to gradual basic variables will vary by alevel. Call
these columns of gradual numbers B. Now Bit = b. Since 5t,b e Q, they are
leftcontinuous. If B were not leftcontinuous, this could lead to a contradiction,
so the elements are B are assumed to be leftcontinuous. Additionally, the m
components of the objective function vector c which correspond to the basic
variables are also leftcontinuous, and form the mvector of gradual numbers c^.
Then there are n nonbasic variables which are zero. These nonbasic variables
form the gradual nvector x^(a). which corresponds to gradual matrix N and
gradual vector cjj(a). Because Ar consists of the columns of A which are not in
B, and B is leftcontinuous, N is necessarily leftcontinuous. Now, introducing
z to represent the value of the fuzzy objective function, 3.11 is equivalent to
max 5 = &qXb+ cJjXn
subject to Bxb+ Nxn = b (312)
x >0.
At every alevel, B is invertible, so let B~l be defined by the assignment
function 51(a) = (5(a))1. Rearranging the constraint equation from 3.12
69
yields the identity
xb = B J(6 Nxh). (3.13)
Note that xB,b,N,x^ E Q and thus leftcontinuous. A contradiction might
arise if is not leftcontinuous, so R_1 is assumed to be leftcontinuous.
Substituting (3.13) into the objective function from (3.12) yields
z = Nxn) + cJjXN (314)
and rearranging,
5 = cTBB~lb + xn(ctn B~lN). (3.15)
Recall that the nonbasic variables are set equal to zero, so the current value of
the objective function is
5 = cTBB~lb. (3.16)
The second term from (3.15), Xn{cn B~lN), shows the potential contribution
of the nonbasic variable x^ to the objective function. Note that the reduced
costs are in Q since R1,1V, and c^i are elements of Q and Q is closed under
multiplication and subtraction. For each unit increase in the level of nonbasic
variable 5j, the corresponding gradual reduced cost, (q [R_1lV]j) will be added
to the objective function. It follows that if any of the gradual reduced costs,
denoted f for brevity, are positive anywhere on (0,1], the objective can be im
proved by a change of basis, and the solution is nonoptimal. Likewise, if all
gradual reduced costs are < 0, there is no basis which will improve the objective
function. This observation is formalized below:
Proposition 3.5 A basic gradual feasible solution is optimal if and only if all
the gradual reduced costs are nonpositive.
70
3.2.2 Pivoting
Recall the farmers fuzzy linear programming problem
max 100xi +300x2 +200x3 (profit objective)
subject to 40x! +20x2 +30x3 < 1500 500a2 (seed money constraint)
Xi +2x2 +^3 ^ L> o 1l 1 o p (labor constraint)
Xi +x2 +^3 ^ 39 3a (acreage constraint)
Xi > 0 Vi.
Adding slack variables (which will also be gradual numbers) gives an equivalent
fuzzy linear program
max lOOxi +300^2 +200x3
subject to 40xi +20x2 +30x3 +S"i = 1500 500a2
Xi +2x2 +x3 +S2 = 70 10 y/a
Xi +x2 +x3 +s3 = 39 3a
Xi > 0 Vi
Si > 0 Vi,
which can be represented by a tableau of coefficients:
Xi x2 x3 Si Â§2 s3
40 20 30 1 0 0
1 2 10 10
1 1 10 0 1
100 300 200 0 0 0
b(a) (profit objective)
1500 500a2 (seed money constraint)
70 10y/a (labor constraint)
39 3a (acreage constraint)
0 (profit objective).
(3.17)
71
The initial basis consists of si, s2, and s:i. Setting = x2 = x> 0 and solving
for si,s2, and s3 yields the basic feasible solution X\ = 52 = x3 0,si =
1500 500a2, Â§2 = 70 10y/a, and s3 = 39 3a. In the lower righthand corner,
the profit from the current basis is seen to be $0. Increasing the objective
function requires a change of basis, or a pivot.
The bottom row of Tableau (3.17) gives the reduced costs of the current non
basic variables, which indicates that bringing x2 into the basis would increase the
objective function at a rate of 300 per unit. Similarly, bringing x\ into the basis
would increase the objective function at a rate of 100 per unit, and bringing x2 in
would increase the objective function at a rate of 200 per unit. For more detail
on reduced costs and tableaux, see [63]. Since x2 increases profit the most for
every acre planted, it makes sense to increase the level of x2 as much as possible
without making the solution infeasible (this makes use of the largestcoefficient
rule, which is but one pivoting option in the simplex method.) The number of
units of x2 which will violate a constraint is given by the current constraint level
(in the 6(a) column of the tableau) divided by the corresponding x2 coefficient
, . , . * . 1500 500a2 _ o
(in the x2 column), ihis ratio is  
20
= 75 25a2 for the first row,
= 35 5y/a for the second row, and ^ = 39 3a for the
third row. Since the second row has the smallest ratio for all levels of a, the
corresponding basic variable s2 will leave the basis.
The following formulation of the gradual simplex method uses the largest
cell pivoting rule with the smaller index as a tiebreaker. Adjusting the rules in
the event of cycling is discussed in Section 3.2.3.1.
72
Definition 3.6 (Gradual Simplex Method) Given a fuzzy linear program
in the form
maximize cTx
subject to Ax = b (3.18)
x > 0,
and the corresponding tableau
A b(a)
r z(a)
the gradual simplex method proceeds according to the following rules:
i. The entering variable is the one with the largest positive reduced cost.
(a) If two are equal, chose the variable with the lowest index.
(b) If all reduced costs are nonpositive, the solution is optimal.
(c) If there is no largest cost for all a G (0,1], the tableau branches into
an appropriate number of parallel cases, each operating on a well
ordered interval.
ii. The leaving variable is the gradual basic variable greater than or equal to
0 associated with the constraint having the smallest ratio of current level
to entering variable coefficient.
(a) If there is no ratio that is smallest for all a G (0,1], the tableau
branches into an appropriate number of parallel cases, each operating
on a wellordered interval.
After the pivot, that is, the set of row operations by which si is set to zero
and the value of x2 is increased as much as possible, the farmers tableau looks
73
like this:
Xi Â£2 Â£3 h Â§2 Â§3 z{a)
30 0 20 1 10 0 800 500a2 +100Va
0.5 10.5 0 0.5 0 35 5 y/a
0.5 0 0.5 0 0.5 1 43a +5 y/a
50 0 50 0150 0 10,500 +l,500Va.
(3.19)
This tableau corresponds to an Â£2 level of 35 5y/a, while x\ and Â£3 are still
zero, and the resulting gradual objective value is $10,500 $1500\/a.
The positive reduced cost associated with Â£3 in Tableau (3.19) indicates
that the objective function can be increased further by bringing Â£3 into the
basis. To determine the leaving variable, consider the number of units of Â£3
which will violate a constraint, given by the current constraint level divided by
, ^ ^ . . 800 500a2 + 100v/5
the corresponding X3 coefficient, this ratio is  = 40
35 5 y/a
20
25a2 + 5y/a for the first row,
4 3a + 5 y/a
0.5
= 70 lOv^ for the second row, and
0.5
= 8 6a + 10 y/a for the last row. The last row has the smallest
ratio for all levels of a, so the corresponding basic variable S3 will leave the
basis. After the pivot, the tableau looks like this:
Â£1 x2 Â£3 Si Â§2 S3 z(a)
10 0 0 1 10 40 640 +120a 500a2 300i/a
0 1 0 0 1 1 31 +3a 10y/a
1 0 1 0 1 2 8 6a 10 y/a
100 0 0 0 100 100 10,900 300a 1,000^/a.
(3.20)
The bottom row is all nonpositive, which indicates that no variable which can
be brought into the basis will increase the profit, so Tableau (3.20) represents a
74
Figure 3.5: The farmers profit level in dollars on the yaxis compared to the
level of satisfaction she has with the feasibility of the corresponding solution.
basic optimal solution. Then the optimal profit is $10,900 $300a $l,000\/cq
as shown in Figure 3.5. Profit is a function of a, the farmers satisfaction with
her solution. The number of acres she should plant of crops A, B, and C, to
achieve that profit are 0, 31 + 3a 10^/a, and 8 6a + 10\/a, respectively.
It is also noted that the second and third constraints, the acreage and labor
constraints, are binding as evidenced by the fact that the corresponding slack
variables, s2 and S3, are nonbasic. Furthermore, these constraints are binding
at all alevels since no splits were encountered.
The gradual optimal solution allows the farmer to understand easily the po
tential profit increase associated with compromising her planting requirements,
and to make an informed decision. Once she has selected a*, the degree of feasi
bility she is most comfortable with, she knows which crops to plant by evaluating
75
a* = 1 a* = .75 a* = .5 a* = .25 a* = 0
Crop B (acres) 24 24.59 25.43 26.75 31
Crop C (acres) 12 12.16 12.07 11.5 8
Profit ($) $9,600 $9,808.97 $10,042.89 $10,325 $10,900
Seed ($) $840 $856.60 $870.71 $880 $860
Labor (days) 60 61.34 62.92 65 70
Land (acres) 36 36.75 37.5 38.25 39
Table 3.2: The farmers optimal solution for a selection of alevels.
the optimal solution at a*. Table 3.2 gives the planting plans and their impacts
on profit, seed money, days of labor, and acres used, for several choices of a*.
This toy example shows how easily a gradual simplex method can be imple
mented for a problem with an optimal solution that does not require branching,
and for which there is no degeneracy. Many, many problems are not this simple.
Dealing with a small number of branches is troublesome but straightforward,
as outlined in the pivoting rules. As the number of branches grow, the method
rapidly becomes intractable. Degeneracy is considered, along with other special
considerations, in the next section.
3.2.3 Special Considerations in the Gradual Simplex Method
3.2.3.1 Degeneracy
A gradual basic solution consisting of one or more basic variable which are
zero for some a is said to be degenerate for that a. Degeneracy itself is not
necessarily a problem, but difficulties arise when a pivot is degenerate. When
76
one zerovalued basic variable leaves, and the entering variable is also zero
valued, the objective function does not improve, and the pivot is degenerate. If
a series of degenerate pivots occur, with the objective function value remaining
the same after each pivot, there is the potential to return to exactly the same
tableau and enter an infinite cycle. Fortunately, Bland's rule for pivoting will
prevent cycling in the gradual simplex method. Under Blands rule, the gradual
simplex method proceeds as usual except that both the entering and leaving
variables will be selected from their respective sets of choices by choosing the
variable with the smallest index. These rules should replace the typical GSM
pivoting rules if cycling occurs under the typical rules. For more details on
Blands rule, see [7].
Theorem 3.7 Using Blands rule, the gradual simplex method does not cycle.
Proof: For every value of a, the gradual tableau reduces to a crisp linear
programming tableau. It has been shown that Blands rule prevents cycling on
such tableaux [7, 88].
3.2.3.2 Convergence
The usual simplex method, with anticycling rules, is known either to find
an optimal solution or determine a problem to to be infeasible in a finite number
of iterations.
Theorem 3.8 (Convergence Theorem For Linear Programming) [63]
If an LP in standard form has an optimal solution, the simplex algorithm
will find one in a finite number of iterations.
77
The proof follows from the facts that the simplex method systematically pivots
through basic feasible solutions and that there are a finite number of basic
feasible solutions. Because a fuzzy linear program has an infinite number of
gradual feasible solutions, an analogous convergence result will not easily be
proved. Even when the gradual endpoints of the fuzzy constraints are restricted
to continuous functions, there might be an infinite number of splits. For example
consider the fuzzy linear program
max x\
subject to afi + i = a (3.21)
Xi + Si a + a cos(a) cos (^) .
The level of X\ is determined by which of the two constraints, x\ + Si = a or
X\ + Â§i = a + acos(a) cos (^), is smaller. But the order of these two functions
switches infinitely many times on the interval (0,1], so implementation of the
gradual simplex method requires an infinite number of tableau splits.
Finite convergence can be shown for some restricted classes of functions.
Theorem 3.9 If a fuzzy LP in standard form has an optimal solution, and the
membership functions of the fuzzy constraints are linear, the gradual simplex
method will find an optimal solution in n' 5 or fewer iterations.
Proof: By Corollary 3.4 and Proposition 3.5, the gradual simplex method
will find an optimal gradual solution if it exists. By Theorem 3.7, cycling is
avoidable. It remains to show that the gradual simplex method will visit only
a finite subset of the infinite number of gradual basic solutions before arriving
at optimality conditions. A basic solution has n of its m + n variables set to
78
(l7l H Ti)!
zero, so there are basic solutions. When the gradual simplex method
n!
(jfl { 77,)!
terminates without splitting, it visits a maximum of :1 solutions, and
n\
so terminates finitely. Recall that splits occur during the comparison of ratios
k
. If relevant ratios are not wellordered, the simplex splits into wellordered
ay
intervals. At each iteration, there are n or fewer ratios to consider because
there are n constraints. Fortin et al. [27] show that the minimum of n linear
functions is piecewise linear with a maximum of n pieces. Hence there are a
maximum of n simplexes after the first iteration, each of which must search over
(m + n 1)! .
 solutions. Each of these simplexes is now subject to n splits. The
n\
overall complexity of this procedure is
t v* + \inax iterations (m+,n)!
(max splits per iteration) = n "! ,
and the gradual simplex method will terminate finitely.
Theorem 3.10 If a fuzzy LP in standard form has an optimal solution, and
the membership functions of the fuzzy constraints are polynomials of degree p or
less, the gradual simplex method, using Blands rule when necessary, will find
an optimal solution in (np+ 1)( ^ 5 or fewer iterations.
Proof: This proof is identical to the proof of Theorem 3.9 except for the
analysis of the number of splits. In the comparison of any two polynomials,
P(a) and Q(a), of degree p, the change of order will occur at the zeros of the
difference, P(a) Q(a) = 0. Since the polynomial P(ot) Q(a) has at most
p zeros, there are at most p + 1 separate tableaux generated. When a third
polynomial R(a) is compared, it will cross P at most p times, and will cross Q
79
at most p times, creating a maximum of 2p + 1 splits. Since a maximum of n
ratios are compared, there is a maximum of np + 1 splits in each iteration. The
overall complexity of this procedure is
t r, nmax iterations , . .izn+zill
(max splits per iteration) = (np +1) n! ,
and the gradual simplex method will terminate finitely.
It is anticipated that the gradual simplex method can be shown to terminate
finitely for many other classes of functions. This task is left for further work.
3.3 Discussion
The complexity of the algorithm is daunting, as is the fact that there are
fuzzy intervals for which the gradual simplex method is known not to terminate,
(3.21) for example. In practice, the complexity might be reduced by revised
pivoting rules which avoid branching whenever possible. This is left for further
research. Regardless, the method makes an important semantical contribution
to the fuzzy community by bridging the perceived gap between fuzzy modeling,
optimization, and decisionmaking without the need to fall back on crisp num
bers. From a computational perspective, future research may show that there
are more powerful approaches (perhaps a gradual interior point method) whose
complexity will be acceptable.
The gradual simplex method is an approach to solving an LP with a fuzzy
feasible region described by constraints with fuzzy right hand sides. In contrast
to parametric programming, and in a departure from many fuzzy optimization
approaches, this gradual simplex method looks at each step of the optimization
problem from a fuzzy perspective. The idea of a gradual number as an element
80
of a fuzzy interval is maintained from problem formulation to solution, with
intermediate components of the gradual simplex algorithm such as reduced costs
and basic feasible solutions expressed as gradual numbers. All computations
are performed on gradual numbers, which prevents the loss of information that
results when fuzzy quantities are defuzzified early in the process (as in [5, 54, 65]
and [66], among others.)
A gradual solution gives a decision maker a continuum of solutions which
are each optimal in their own right. This allows the decision maker to use
his situational knowledge to select from among a set of optimal solutions, the
solution which will give him a sense of control and satisfaction while guaranteeing
an optimal solution. It is hoped that the idea of a gradual optimum will be
compelling and will find its way into other fuzzy optimization techniques.
3.4 Extensions
The gradual simplex method may be modified for other variations of the
fuzzy linear programming problem. Fuzziness and/or fuzzy uncertainty, which
is often called possibility [46], can occur in the cost vector and in the constraint
coefficient matrix in addition to the righthand sides. For a survey of the many
shades of fuzzy optimization and the respective solution approaches, see [85].
One class of problems that might be addressed by the gradual simplex
method is that of linear programs with fuzzy constraint coefficients. The fuzzy
feasible regions in Section 3.2 are generated by constraints of the form Ax < b.
Fuzziness in the righthand side generally corresponds to the decision makers
degree of satisfaction with the strictness of the constraints [55], and the typical
interpretation of the fuzzy feasible region is as a fuzzy set whose membership
81
function indicates the degree to which a solution satisfies the requirements of
the problem. The interpretation is less obvious when the fuzzy feasible region
is generated by constraints of the form Ax < b, where A is a matrix of gradual
numbers and b is a vector of fuzzy intervals.
Consider what it means for an entry of A to be a fuzzy interval. A fuzzy
aij indicates that the problem variable Xj contributes to constraint i to differing
degrees. The literature largely interprets this varying degree of contribution as
a result of uncertainty. (For a detailed discussion of interpretations of fuzzy
constraint coefficients, see [36], [55], [73], or [85].) In other words, the extent
to which variable Xj contributes to constraint i is unknown. In practice, un
certainty is modeled in a variety of ways, including probability distributions,
possibility distributions, intervals, random sets, and others [83], but if is
presented as a fuzzy interval, then the uncertainty has been modeled as a possi
bility distribution. Possibility distributions are uncertainty distributions which
take the shape of fuzzy sets. The reader is referred to [46] for details on the
connection between fuzzy sets and possibility distributions. For the purpose of
adapting the gradual simplex method to problems with constraints of the form
Ax < b, it is sufficient to know that fuzziness in A represents uncertainty about
the values of constraint coefficients.
The set of solutions which satisfies the uncertain linear relation Ax < b is
open to a variety of interpretations, but in all cases, the solution sets will be
polytopes, connected fuzzy sets on Rn, and as such, their elements will be n
tuples of gradual numbers. Four generally accepted solution sets for the relation
Ax < b, described by [25], [53], and others, are:
82
i. Necessary solution set: {x : Ax = b}. This is the set of all x that will
make the membership function of the fuzzy set Ax exactly identical to
the membership function of the fuzzy set b. In practice, this set is nearly
always empty.
ii. Strongly necessary solution set {x : Ax C &}. This is the set of all x for
which the membership function of the fuzzy set Ax is always less than the
membership function of the fuzzy set b, which follows from the definition
of set containment for fuzzy sets. This is the solution set of interest in this
section.
iii. Strongly possible solution set: {x : Ax D b}. This is the set of all x that
will make the membership function of the fuzzy set Ax always greater
than the membership function of the fuzzy set b, again, following from the
definition of set containment for fuzzy sets, but in reverse.
iv. Possible solution set: {x : Ax fl b ^ 0} This is the set of all x that
guarantee that there is some real number x for which both pteix) > 0
and Pi{x) > 0.
An interpretation of Ax < b will only be of interest here if it corresponds to
feasible regions that actually arise in the course of mathematical modeling. The
strongly necessary solution set ii is compelling to the author, for reasons that will
be made clear in Section 3.4.1, where the gradual simplex method is evaluated for
solving optimization problems with this interpretation of the Ax < b constraint.
Future research is intended that will show that the gradual simplex method can
also find solutions to linear programs with feasible regions consisting of possible
83
1J
y
4
i
b
0
f
i
Figure 3.6: Higher Qcuts of a possibility distribution correspond to narrower
intervals.
solution set iv. The possible solution set i is almost always empty, so does not
make sense as a feasible region, and there is no clear interpretation for possible
solution set iii.
3.4.1 Problems over Necessarily Feasible Regions
Consider a fuzzy optimization problem with the feasible region described by
Ax < b, where b denotes the decision makers satisfaction with the strictness of
the constraints, and A represents uncertainty about the values of the constraint
coefficients. Then higher alevels of b correspond with higher satisfaction. Mean
while, higher acuts of A correspond to narrower intervals containing only the
most likely values of A (a result of the fact that acuts of fuzzy intervals are
nested [46]). Figure 3.6 demonstrates that high avalues correspond to narrow
intervals in an uncertainty distribution. The alevel of A, then, does not cor
respond to satisfaction as the alevel of b does. In fact, quite the opposite is
true: a solution that is only feasible for a narrow interval of possible constraint
coefficient values is less satisfactory than a more robust solution that would be
84
feasible for a wider interval of possible constraint values. Creating a fuzzy fea
sible region that reflects the degree of the decision makers satisfaction with the
solution will require a mapping from the possibility levels of A to the decision
makers satisfaction with solutions at those possibility levels. A modelrobust
solution will hedge against uncertainty by being feasible for a wide variety of
possible constraint coefficient values [14, 86]. The more uncertainty a solution
hedges against, the more satisfied the decision maker will be. These mappings
are proposed in [23], and an example of an inverse linear mapping is found in
[86]. Precise methods for constructing appropriate mappings, largely related to
human betting behavior, are beyond the scope of this dissertation and can be
found in [23]. Figure 3.7 shows how the acuts of the fuzzy interval representing
the uncertainty distribution from Figure 3.6 might correspond to the decision
makers satisfaction with the amount of uncertainty taken into account. Note
that the alevel now corresponds to the robustness of the solution rather than
the feasibility. The final gradual solution to this problem will allow for a trade
off between a high objective function value and a high a. This mapping takes
the form of a gradual number, which is a function of a corresponding to satis
faction. Once the possibilistic A has been mapped to satisfaction, a meaningful
fuzzy feasible region results from Ax < b, and the gradual simplex method may
be applied.
Remark 3.11 It should be noted that a fuzzy satisfaction mapping can be cre
ated from other representations of uncertainty, including probability distribu
tions, intervals, clouds [67], and random sets [21]. As a result, the extension
of the gradual simplex method developed in this section can be applied to a wide
85
f..4
\
a bed e
a b cd e
Figure 3.7: For each acut of the possibility distribution, the decision maker
indicates how satisfied he will be if the solution is feasible for every possible
outcome in the interval. For instance, a solution that is feasible so long as the
uncertain variable takes on a value less than a is satisfactory to degree 0.2,
whereas a solution that is feasible so long as the uncertain variable takes on a
value less than e is satisfactory to degree 0.9.
class of problems with uncertain constraint coefficients and flexible constraints.
An example of a feasible region given by Ax < b is instructional. Consider
a traveler stranded on an island with nothing but a large supply of avocados,
potatoes, and eggplants. He wants to eat the minimum number of vegetables
that will meet his daily nutrition requirements. He needs a minimum of 1500
calories, but prefers to exceed 1600, with a degree of satisfaction proportional
to how close he is to 1600 or more, so his fuzzy caloric requirement is
total calories > 1500 + 100a.
Likewise, he needs a minimum of 45 grams of fat but prefers to exceed 50, with
a degree of satisfaction proportional to how close he is to 50 or more, so his
fuzzy fat requirement is
total fat > 45 + 5a.
Finally, he needs a minimum of 30 grams of fiber, but prefers to exceed 60, again
with a linear satisfaction, so his fuzzy fiber requirement is
total fiber > 30 + 30a.
The traveler recalls nutritional data for average avocados, potatoes, and egg
plants, and combines them with his fuzzy requirements to arrive at the following
fuzzy formulation:
min i\+ X2+ Â£3 (min # of vegetables)
s.t. 3205:1 + 115.5x2 + 360x3 > 1500 1lOOa (calorie constraint)
29.35:1 + 0.1x2 + 2.8x3 >45 +5a (fat constraint)
13.4xi + 3.3x2 + 51x3 > 30 +30a (fiber constraint)
Xi > 0 Vi.
Because these vegetables vary widely in size, the traveler wants a solution that
will ensure that he meets his dietary requirements even if he ends up eating
smallerthanaverage vegetables. For example, he knows that an average 200g
avocado has 320 calories, that caloric content is proportional to weight, and that
that avocados range in weight between 150g and 250g. He will be fully satisfied if
his solution will meet his nutritional requirements even if he ends up consuming
a 150 g avocado with only 240 calories, and he will be minimally satisfied if his
solution only meets his nutritional requirements when the avocados he eats have
at least the average 320 calories. For ease of modeling, assume this satisfaction
varies linearly. Then the avocado parameter in the calorie constraint, fin, is set
to 320 80a to reflect his satisfaction with the amount of uncertainty it hedges
87
