OPTIMIZATION PROBLEMS UNDER TWO-SIDED (max,min)−LINEAR
INEQUALITIES CONSTRAINTS
Mahmoud Gad
Cha les Uni e si y in P ague
Facul y o Ma hema ics and Physics
Sokolo sk´
a 83, P aha 8, 186 75, Czech Republic
*Sohag Uni e si y
Facul y o Science
Sohag, Egyp
Mahmoud A ya [email p o ec ed]
Abs ac
Sys ems o so called wo-sided (max,min)−linea inequali ies wi h a iables on bo h sides will
be s udied. Op imiza ion p oblems, he objec i e unc ion o which is equal o he maximum
o a ini e numbe o con inuous unc ions o one a iable a e conside ed. The se o easible
solu ions in desc ibed by a sys em o wo-sided (max,min)−linea inequali ies wi h a iables
on bo h sides. A ini e algo i hm o inding he op imal solu ion o he p oblem is p oposed.
Keywo ds: Two-sided (max,min)−linea inequali ies sys em; lowe and uppe bounds; max-
min op imiza ion p oblems.
In oduc ion
The algeb aic s uc u es in which (max,+) o (max,min) eplace addi ion and mul iplica ion
o he classical linea algeb a ha e been appea ed in he li e a u e app oxima ely since he six-
ies o he las cen u y (see e.g. [1], [3], and [8]). In ecen ly published book [2] eade s can
ind he la es esul s conce ning heo y and algo i hms o (max,+)−linea sys ems o equa-
ions. A polynomial me hod o inding he maximum solu ion o he (max,min)-linea sys em
has been p oposed in [5]. A ini e algo i hm o inding he op imal solu ion o he op imiza-
ion p oblems unde (max,+)−linea cons ain s has been in oduced in [10]. A su ey o
some o he ecen esul s conce ning he (max,min)-linea sys ems o equa ions and inequali-
ies and op imiza ion p oblems unde he cons ain s desc ibed by such sys ems o equa ions
and inequali ies is p esen ed in [6]. Algo i hm o op imiza ion p oblems unde one-sided
(max,min)−linea equali y cons ain s is in oduced in [4]. Maximal solu ions o wo-sided
linea sys ems in max-min algeb a ha e been gi en in [7]. A no e on applica ion o wo-sided
sys ems o (max,min)−linea equa ions and inequali ies o some uzzy se p oblems has been
gi en in [9].
In his con ibu ion, we will s udy sys ems o so called (max,min)−linea (o using an
al e na i e no a ion (max,∧)−linea ) inequali ies wi h a iables on bo h sides. We conside
op imiza ion p oblems, he objec i e unc ion o which is equal o he maximum o a ini e
numbe o con inuous and unimodal unc ions o one a iable. The se o easible solu ions is
desc ibed by a sys em o (max,∧)−linea inequali ies wi h a iables on bo h sides. Le us no e
ha i we ha e a iables xon he le hand sides and di e en a iables yon he igh hand sides,
he sys em can be p ocessed like he one-sided sys em conside ed e.g. in [6]. Including lowe
and uppe bounds on x,yis only a echnical p oblem.
We can conside he p ac ical p oblem, in which anspo a ion means o di e en size a e
85
anspo ing goods om places i∈I o one e minal T. The goods a e unloaded in Tand he
anspo a ion means (possibly wi h o he goods a e uploaded in T) ha e o e u n o i. We
assume ha he connec ion be ween iand Tis only possible ia one o he places (e.g. ci ies)
j∈J he oads be ween iand ja e one-way oads, and he capaci y o he oad be ween i∈I
and j∈Jis equal o aij. We ha e o join places jwi h Tby a wo-way oad wi h a capaci y
xjin bo h di ec ions. The o al capaci y o he connec ion be ween iand Tis he e o e equal
o maxj∈J(aij ∧xj). The anspo om T o iis ca ied ou ia o he one-way oads be ween
places j∈Jand i∈Iwi h (in gene al, di e en ) capaci ies be ween jand ia e equal o bij.
Since he oads be ween Tand ja e wo-way oads, he o al capaci y o he connec ion be ween
Tand iis equal o maxj∈J(bij ∧xj), o all i∈I. We assume ha he anspo a ion means can
only pass h ough some oads wi h he capaci y which is no smalle han he capaci y o he
anspo a ion mean and ou ask is o choose app op ia e capaci ies xj,j∈J. In o de ha each
o he anspo a ion means may e u n o i, we may e.g. equi e o each i ha he maximal
a ainable capaci y o connec ions be ween iand T ia jis g ea e han o equal o maximal
a ainable capaci y o connec ions be ween Tand ion he way back. In o he wo ds, we ha e
o choose xj,j∈J, which sa is y ela ion (1) below. In wha ollows, assume ha we ha e he
same a iables on he le hand sides and igh hand sides o he inequali y sys em.
1 Sys ems o (max,min)−Linea Inequali ies
Le us conside he ollowing sys em o inequali ies:
ai(x)≥bi(x),i∈I,(1)
whe e ai(x) = maxj∈J(aij ∧xj),bi(x) = maxj∈J(bij ∧xj),and aij,bij ∈R,i∈I,j∈Jbe
gi en numbe s. Le M≥deno e he se o all solu ions o sys em (1). We will se o any
x,y∈Rn:x≤y⇔xj≤yj∀j∈J. Le us se M≥(x,x) = {x;x∈M≥&x≤x≤x} o any
ini e x≤xand le xmax deno e he maximum elemen o M≥(x,x). So ha M≥(x,x)⊂M≥,and
M≥(x,xmax)⊂M≥,also i is clea M≥(x,xmax)⊆M≥(x,x). To p o e M≥(x,x)⊆M≥(x,xmax)
he e a e wo cases: he i s one, i x/∈M≥, hen xmax <x.The e o e ∀x∈M≥(x,x), he
inequali y x≤xmax e i ied, i.e. xj≤xmax
j∀j∈Jand i x∗∈(xmax,x], (i.e. xmax <x∗≤x,
i.e. xmax
j0<x∗
j0≤xj0 o a leas one j0∈Jand xmax
j≤x∗
j≤xj o j∈J&j6=j0)
hen x∗/∈M≥, o he wise x∗is he maximum elemen o M≥(x,x), bu his con adic s he
hypo hesis xmax is he maximum elemen o M≥(x,x).So ha o any x∈M≥(x,x),we ha e
x≤xmax , and x∈M≥(x,xmax), hen M≥(x,x)⊆M≥(x,xmax).The second case, i x∈M≥,
hen xmax =x.Then we ha e M≥(x,xmax) = M≥(x,x)⊂M≥.In his sec ion we will p opose an
algo i hm, which ind he maximum elemen o he se M≥(x,x), and calcula es he maximum
solu ion o sys em (1), ake in accoun x≤x≤x. No e ha , since any equa ion can be eplaced
by wo inequali ies, he e o we can use he nex algo i hm o ind he maximum elemen o he
se M=(x,x), which is he se o all solu ions o a sys em o equa ions, (ai(x) = bi(x),i∈I).
Algo i hm 1
0 Inpu I,J,x,aij and bij o all i∈Iand j∈J.
1 Find I<(x)≡{i∈I;ai(x)<bi(x)}.
2 I I<(x) = /0, hen xmax :=x, STOP.
3 Find
α
(x)≡mini∈I<(x)ai(x).
86
4 Find I<(
α
(x)) ≡{i∈I<(x);ai(x) =
α
(x)}.
5 Find H<
i(x)≡j∈J;bij ∧xj>
α
(x),∀i∈I<(
α
(x)).
6 Se H<(x):=Si∈I<(
α
(x)) H<
i(x).
7 Se xj:=
α
(x) o all j∈H<(x)go o 1 .
We will illus a e he pe o mance o his algo i hm by he ollowing small nume ical example.
Example 1. :Le J ={1,2,3,4}, I ={1,2,3}, x = (10,10,10,10), and conside sys em (1) o
inequali ies whe e aij &bij ∀i∈I and j ∈J a e gi en by he ma ices A and B as ollows:
A=
7 5 3 0
4 3 1 2
10 20 10 −1
,B=
6 13 10 −1
8 0 3 1
1 1 1 −8

By subs i u ion o hese alues in sys em (1) and using Algo i hm 1:
I e a ion 1:
1 I<(x) = {1,2}.
2 I<(x)6=/0.
3
α
(x) = min(7,4) = 4.
4 I<(
α
(x)) = {2}.
5 H<
2(x) = {1}.
6 H<(x) = {1}.
7 x1=4,x= (4,10,10,10)go o 1 .
I e a ion 2:
1 I<(x) = {1}.
2 I<(x)6=/0.
3
α
(x) = 5.
4 I<(
α
(x)) = {1}.
5 H<
i(x) = {2,3}.
6 H<(x) = {2,3}.
7 x2=5,x3=5,x= (4,5,5,10)go o 1 .
I e a ion 3:
1 I<(x) = /0, hen xmax = (4,5,5,10)STOP.
87
In he nex pa o his sec ion we will in oduce a me hod which inds he minimum uppe
bound ˜x o solu ion o sys em (1) such ha ˜x≥x. In o he wo ds ˜xhas he p ope ies ˜x∈
M≥(x,xmax)and i x≤˜x,x6=˜x, hen he e exis s x∗∈M≥(x,xmax)such ha x∗6≤ ˜x. I will
be clea ha ˜x∈M≥(x,xmax)and his elemen is sui able o ind he op imal solu ion o he
minimiza ion p oblem as we will see in he nex sec ion. In wha ollows o simpli y he no a ion
we se o any
α
,
β
∈R:
α
∨
β
=max(
α
,
β
). Le us se
Tij ={xj;xj≤xmax
j&aij ∧xj≥bi(x)∨xj},∀i∈I,j∈J.
No e ha i i1,i2a e wo di e en indices o I,j∈J, and bi2(x)∨xj≤bi1(x)∨xj, hen
e iden ly Ti1j⊆Ti2j. I ollows ha o any subse o indices o I, he e exis s such pe mu a ion
i1, ,..., i o hese indices ha he inclusions Ti1j⊆Ti2j⊆... ⊆Ti jhold so ha T
h=1Tihj=
Ti1j. Se s Tij ha e he ollowing p ope ies:
Tij 6=/0 ⇔aij ≥bi(x)∨xj,
Tij 6=/0 ⇒Tij = [bi(x)∨xj,xmax
j].
Since we assumed ha x≤xmax, se M≥(x,xmax)is nonemp y. Le us no e ha o any
x∈M≥(x,xmax)and any i∈I, he inequali ies bi(x)≥bi(x)&xj≥xj∀j∈Jhold and u he
he e exis s o each i∈Ian index j(i)∈Jsuch ha Tij(i)6=/0 (o he wise se M≥(x,xmax)
would be emp y, because we would ha e aij <bi(x)∨xj∀j∈Jand he e o e ai(x)<bi(x)
o any x∈Rnand we ha e x≤xmax so ha M≥(x,xmax)6=/0). Le us no e u he , ha i
aij ∧xj<bi(x)∨xj∀j∈J, hen we ha e ai(x)<bi(x)and hus x6∈M≥(x,xmax). I o some
ixed j∈J he inequali ies aij <bi(x)∨xjhold , hen aij ∧xj<bi(x)∨xj∀xj∈Rso ha Tij =/0
and xjwill ne e be ”ac i e” in ai(x)o bi(x)i x∈M≥(i.e. i will ne e de e mine he alues
o ai(x)o bi(x)). We will exclude such a iables om ou conside a ions and assume ha o
each j∈J he e exis s a leas one ” ow” index i∈Isuch ha aij ≥bi(x)∨xj. We de ine se s
Vj,j∈JVj={i∈I;aij ≥bi(x)∨xj},
and deno e maxk∈Vj(bk(x)) = bk(j)(x). A ec o ˜xwill be de ined as ollows:
˜xj=max
k∈Vj(bk(x))∨xj=bk(j)(x)∨xj∀j∈J.(2)
The elemen ˜xde ined by (2) has he ollowing p ope ies:
(1) M≥(x,˜x)6=/0,& ˜x∈M≥(x,˜x).
(2)
ξ
∈M≥(x,˜x)⇒x≤
ξ
≤˜x.
(3) The e may exis elemen s
η
∈M≥(x,˜x)such ha
η
6=˜x.
I ˜xis he minimum elemen o M≥(x,xmax), hen i would be ˜x∈M≥(x,xmax)and o any
x∈M≥(x,xmax)⇒x≥˜x. The e o e, because o he p ope y (3) ˜xis no he minimum elemen
o M≥(x,xmax), bu we can say ha ˜xis he minimum uppe bound o M≥(x,xmax)such ha
M≥(x,˜x)6=/0. Le us choose
τ
≤xmax,&
τ
6=xmax, and ˇx∈M≥(x,
τ
)⇒ˇx≤xmax and ai(ˇx)≥
bi(ˇx)∀i∈Iand x≤ˇx≤
τ
. Le H=xmax(
τ
)|xmax(
τ
)is he maximum elemen o M≥(x,
τ
),
hen ˜xis he minimum elemen o H.
Theo em 1. :Le ˜x be de ined as in (2). Then ˜x∈M≥(x,xmax).
88
P oo : Since e iden ly ˜x≥x, we ha e o p o e ha only ai(˜x)≥bi(˜x),∀i∈I. Le i∈Ibe
a bi a ily chosen. We ha e
bi(˜x) = max
j∈J(bij ∧˜xj) = max
j∈J(bij ∧(max
k∈Vj(bk(x)∨xj))) = max
j∈J(bij ∧(bk(j)(x)∨xj))
Le us assume ha bi(˜x) = max
j∈J(bij ∧˜xj) = bij(i)∧˜xj(i).
Since in his case i∈Vj(i), we ha e aij(i)≥˜xj(i)and we ob ain ai(˜x)≥aij(i)∧˜xj(i)=˜xj(i)≥
bij(i)∧˜xj(i)=bi(˜x).Since i∈Iwas a bi a ily chosen, he heo em is p o ed.
Elemen ˜xde ined by (2) shows ha he gi en lowe bound xmigh no be an elemen o
M≥(x,xmax). Mo eo e we ob ained an explici dependence o ˜xon he gi en lowe bound
x(compa e (2)), which can be used o sensi i i y analysis o he se M≥(x,x)o o a pos
op imal analysis o op imiza ion p oblems, he se o easible solu ions equal o M≥(x,xmax).
The p ope ies o ˜xenable us o sol e some o he op imiza ion p oblems men ioned abo e
explici ly.
2 Op imiza ion P oblems unde Two-Sided (max,min)−Linea Inequali ies Cons ain s
In his sec ion we conside an op imiza ion p oblem ha is a combina ion o he p oblems
sol ed in he abo e chap e s bu wi h a di e en easible se . In o he wo ds, le us conside o
ins ance he op imiza ion p oblem:
(x)≡max
j∈J j(xj)−→ min (3)
subjec o x∈M≥(x,xmax),whe e j,j∈Ja e inc easing unc ions. Le indices j(i)∈Jwill
be chosen o each i∈Isuch ha minj∈J j(x(i)
j) = j(i)(xj(i)),whe e j(x(i)
j) = minxj∈Tij j(xj).
Le ˜xbe de ined as in (2) and hen we ha e o p oceed as ollows:
˜
Tij =




/0 i aij <bi(x),
bi(x)i aij >bi(x),
[xj,˜x]i aij =bij.
Se j(˜x(i)
j) = minxj∈˜
Tij j(xj), (i ˜
Tij =/0,we se minimum equal o +∞). Le us se
min
j∈J j(˜x(i)
j) = j(i)(˜x(i)
j(i)).
And ˜
Rj={i∈I|j(i) = j},∀j∈J, ( i may be ˜
Rj=/0 o some j). Then we ha e
k(xop
k) = max
i∈˜
Rk
k(˜x(i)
k),
i ˜
Rk6=/0,bu when ˜
Rk=/0, we se
k(xop
k) = k(xk).
The p oo can be ca ied ou in he same way as in he one sided case in [6]. We men ioned
abo e ha a sys em o inequali ies can be ans o med o a sys em o equa ions by making use
o slack a iables. Le us no e ha he o he way ound, sys ems o equa ions conside ed can
be sol ed al e na i ely by he me hods in his sec ion, i we eplace he equa ion sys em by he
sys em o inequali ies o he o m
89

ai(x)≥bi(x),i∈I
bi(x)≥ai(x),i∈I
xj≥xj,j∈J.
We will desc ibe now he co esponding algo i hm explici ly s ep by s ep.
Algo i hm 2
0 Inpu m,n,x,x,A,B, (x).
1 Find xmax ∈M≥(x,x).
2 I xxmax, hen M≥(x,x) = /0, STOP.
3Vj:={i∈I;aij >bi(x)∨xj} ∀j∈J.
4x(i)
j:= (bi(x)∨xj)∀i∈Vj o all j∈Jsuch ha Vj6=/0.
5 Se ˜xj:=maxi∈Vj(x(i)
j)i Vj6=/0, ˜xj:=xji Vj=/0.
6Q:={k∈J; (˜x) = k(˜xk)},P:={j∈J; ˜xj=xj}.
7 I Q∩P6=/0, hen se xop :=˜x, STOP.
8Pk:={i∈I; ˜xk=x(i)
k} ∀k∈Q.
9Vk:=Vk Pk∀k∈Q.
10 I Sj∈JVj=I, go o 4 .
11 Se xop :=˜x, STOP.
We will illus a e he pe o mance o his algo i hm by he ollowing nume ical examples.
Example 2. :Le J ={1,2,...,5}, I ={1,2,3}, x = (10,10,10,10,10), x = (0,3,0,0,1)and
conside sys em (1) o inequali ies whe e aij &bij ∀i∈I and j ∈J a e gi en by he ma ices
A and B as ollows:
A=
−10 10 15 −9−8
5−8 10 20 7
3 4 −18 19 11
,B=
7 2 −10 −20 6
8 9 −15 −25 5
13 −17 12 10 9

and conside he objec i e unc ion (x) = max(x1,x2−3,x3,x4,x5).By subs i u ion o hese
alues in sys em (1) and using Algo i hm 1 and Algo i hm 2:
1 xmax =x= (10,10,10,10,10).
2 x ≤xmax.
3 V1={2},V2={1,3},V3={1,2},V4={2,3},V5={2,3}.
90
4 x(1)
1=2,x(1)
2=3,x(1)
3=2,x(1)
4=2,x(1)
5=2,x(2)
1=3,x(2)
2=3,x(2)
3=3,
x(2)
4=3,x(2)
5=3,x(3)
1=1,x(3)
2=3,x(3)
3=1,x(3)
4=1,x(3)
5=1.
5˜x= (3,3,2,3,3).
6 Q ={1,4,5},, (˜x) = 3,P={2} hen Q∩P=/0.
8 P1={2},P2={1,2,3},P3={1},P4={2},P5={2}.
9 V1=/0,V2=/0,V3={2},V4={3},V5={3}.
10 Sj∈JVj={2,3}6=I.
11 xop =˜x, STOP.
Then xop = (3,3,2,3,3)is he op imal solu ion o he se M≥(x,x)and
(xop ) = max(3,0,2,3,3), hen he objec i e unc ion is equal o 3.
Example 3. :Le J ={1,2,...,5}, I ={1,2,...,6},x= (20,20,20,20,20), x = (0,3,0,0,0)
and conside sys em (1) o inequali ies whe e aij &bij ∀i∈I and j ∈J a e gi en by he
ma ices A and B as ollows:
A=








2 2 6 0 13
8 11 10 7 7
4 3 0 13 8
14 3 3 13 2
1 3 13 4 2
12 15 7 3 14








,B=








0 10 9 −1 5
3−3 1 −6−7
4−8 2 −14 11
14 −7 7 −3 4
6−8 12 2 0
0−11 2 −3 5








and conside he objec i e unc ion (x) = maxj∈J( j(xj),whe e j(xj) = cjxj+dj,
c= (6,3,7,3,7)and d = (10,0,5,1,7). By subs i u ion o hese alues in sys em (1) and
using Algo i hm 1 and Algo i hm 2:
1 xmax =x= (20,20,20,20,20).
2 x ≤xmax.
3 V1={2,3,4,5,6},V2={2,6},V3={1,2,4,5,6},V4={2,3,4,5,6},V5={1,2,3,4,5,6}.
4 ind x(i)
j.
5˜x= (0,3,3,0,3).
6 Q ={5}, (˜x) = 28,P={1,2,4} hen Q∩P=/0.
10 Sj∈JVj={1,2,3,4,5,6}=I go o 4 .
4 ind x(i)
j.
5˜x= (0,3,3,0,0).
91
6 Q ={3}, (˜x) = 26,P={1,2,4,5} hen Q∩P=/0.
10 Sj∈JVj={1,2,4,5,6}6=I.
11 xop =˜x, STOP.
Then xop = (0,3,3,0,0)is he op imal solu ion o he se M≥(x,x)and
(xop ) = max(10,9,26,1,7), hen he objec i e unc ion is equal o 26.
Conclusion
We can summa ize he p ope ies o he sys ems o (max,min)-linea inequali ies s udied in his
pape as ollows:
(1) Any sys em o wo-sided (max,min)-linea inequali ies is sol able and has a unique maxi-
mum elemen xmax(A,B)depending on he ma ices A,Bwi h ini e elemen s aij,bij (no e ha
including in ini e elemen s can cause nonsol abili y o he sys em).
(2) I we include an addi ional equi emen x≤x, hen he sys em is also sol able and has he
maximum elemen xmax(A,B,x)≤xmax(A,B).
(3) The sys em wi h a ini e lowe bound on a iables (i.e. wi h an addi ional cons ain x≥x)
is sol able i and only i x≤xmax(A,B), o in case o he addi ional uppe bound xi and only
i x≤xmax(A,B,x).
Acknowledgmen s
This wo k was suppo ed by The Minis y o Highe Educa ion and Scien i ic Resea ch o he
A ab Republic o Egyp . The au ho also o e s since e hanks o P o . Ka el Zimme mann o
his con inuing suppo and e e nally g ea ad ice.
Li e a u e
[1] BUTKOVIˇ
C, P.; HEGED ¨
US, G.: An Elimina ion Me hod o Finding All Solu ions o
he Sys em o Linea Equa ions o e an Ex emal Algeb a, Ekonomicko–ma ema ick´
y ob-
zo 20, 1984, pp. 203-215.
[2] BUTKOVIˇ
C, P.: Max-linea Sys ems: Theo y and Algo i hms, Sp inge Monog aphs in
Ma hema ics, 267 p., Sp inge -Ve lag, London, 2010.
[3] CUNINGHAME-GREEN, R. A.: Minimax Algeb a. Lec u e No es in Economics and
Ma hema ical Sys ems 166, Sp inge -Ve lag, Be lin 1979.
[4] GAD, M.: Op imiza ion p oblems unde one-sided (max,min)−linea inequali ies con-
s ain s ( o appea ).
[5] GAVALEC, M.; ZIMMERMANN, K.: Sol ing Sys ems o Two-Sided (max,min)-Linea
Equa ions, Kybe ne ika 46, 2010, pp. 405-414.
[6] GAVALEC, M.; GAD, M.; ZIMMERMANN, K.: Op imiza ion p oblems unde
(max,min)−linea equa ion and/o inequali y cons ain s ( o appea ).
[7] KRB ´
ALEK, P.; POZD´
ILKOV ´
A, A.: Maximal solu ions o wo-sided linea sys ems in
max-min algeb a, Kybe ne ika 46, 2010, pp. 501-512.
92
[8] VOROBJOV, N. N.: Ex emal Algeb a o posi i e Ma ices, Da en e a bei ung und Ky-
be ne ik 3, 1967, pp. 39-71 (in Russian).
[9] ZIMMERMANN, K.: A No e on Applica ion o Two-sided Sys ems o
(max,min)−Linea Equa ions and Inequali ies o Some Fuzzy Se P oblems, Ac a
Uni . Palacki. Olomuc., Fac. e . na ., Ma hema ica 50, 2, 2011, pp. 129-135.
[10] ZIMMERMANN, K.; GAD, M.: Op imiza ion P oblems unde (max,+)−linea Con-
s ain s, In e na ional con e ence p esen a ion o ma hema ics ’11 (ICPM ’11), Libe ec,
11, pp. 159-165, 2011. ISBN 978-80-7372-773-4.
Mahmoud Gad, M.Sc.
93