Optimization problems under two-sided (max; min)–linear Inequalities constraints

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