'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
$ 1/22
Megb´ızhato´ optimaliz´al´as matematikai feladatok megold´as´aban
Csendes Tibor
&
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
Pakol´asi feladatok koz´ ¨ epkori jap´an fat´abl´an
$ 2/22
Egy jap´an sangaku az Edo korszakbol ´ (1603–1867) korpakol´ ¨ asi feladatokkal. Ilyen sangakukat tal´alhatunk buddhista templomokban e´ s sintoista ´
&
szent´elyekben, valosz´ ´ ınuleg ˝ medit´acios ´ c´elra valok. ´
%
'
2007. junius ´ 8.
&
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
Sangaku egy jap´an szikl´an
$ 3/22
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
Bolyai Farkas javaslatai optim´alis fatelep´ıt´esre.
&
$ 4/22
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
$ 5/22
A korpakol´ ¨ asi feladat k´et ekvivalens megfogalmaz´asa Helyezzunk ¨ el adott n darab egybev´ago´ kort ¨ a´ tlapol´as n´elkul, ¨ maxim´alis sug´arral az egys´egn´egyzetben. Helyezzunk ¨ el adott n sz´amu´ pontot az egys´egn´egyzetben ugy, ´ hogy a kozt ¨ uk ¨ l´ev˝o minim´alis t´avols´ag maxim´alis legyen. max
min
1≤i6=j≤n
q (xi − xj )2 + (yi − yj )2 ,
ahol 0 ≤ xi , yi ≤ 1, &
i = 1, 2, . . . , n. %
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
$ 6/22
Naiv intervallum aritmetika
[a, b] + [c, d] = [a + c, b + d] [a, b] − [c, d] = [a − d, b − c] [a, b] · [c, d] = [min(ac, ad, bc, bd), max(ac, ad, bc, bd)] [a, b]/[c, d] = [a, b] · [1/d, 1/c] ha 0 ∈ / [c, d] P´elda: az f (x) = x2 − x fuggv´ ¨ eny befoglalo´ fuggv´ ¨ enye a [0, 1] intervallumon az [−1, 1] intervallumot adja, m´ıg az e´ rt´ekk´eszlet itt [−0.25, 0.0]. &
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
$ 7/22
Korpakol´ ¨ asi feladatok megold´asa 28-30 kor ¨ eset´en
n = 28
n = 29
n = 30
A sat´ırozott kor ¨ ok ¨ kis m´ert´ekben mozgathatok ´ az optimalit´as megtart´asa mellett (a glob´alis minimumpontok halmaza pozit´ıv m´ert´eku). ˝ K´et kor ¨ e´ rintkez´es´et az osszek ¨ ot˝ ¨ o vonalak jelzik.
&
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
Korpakol´ ¨ asi feladatok megold´asa r´eszletei
$ 8/22
Hardver: PC, Pentium IV 1800 MHz, 1 GB RAM. Szoftver: Linux, GNU C/C++, C–XSC Toolbox, PROFIL/BIAS. A sug´ar e´ rt´ek´ere kapott korl´atok: ∗ F28 = [0.2305354936426673, 0.2305354936426743], w ≈ 7 · 10−15 , ∗ F29 = [0.2268829007442089, 0.2268829007442240], w ≈ 2 · 10−14 , ∗ F30 = [0.2245029645310881, 0.2245029645310903], w ≈ 2 · 10−15 .
A teljes fut´asi id˝ok: ≈ 53, 50, illetve 21 ora. ´ A feladatok megold´as´ahoz kb. egy millio´ r´eszintervallum kellett. A verifik´alt elj´ar´as az optim´alis pakol´as hely´eben valo´ bizonytalans´agot tobb ¨ mint 711, 764, illetve 872 nagys´agrenddel csokkentette. ¨ &
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
Egy vegyipari h´alozattervez´ ´ esi feladat A A
F1
$ 9/22
P1
S1
x1
S3 x3 P2
x4 S2 F2
x2
S4
C C
P3
A feladat a fenti szepar´ator-h´alozatra ´ annak eldont´ ¨ ese, hogy az xi ∈ [0.0, 1.0], (i = 1, 2, 3, 4) megosztok ´ minim´alis kolts´ ¨ eget ado´ e´ rt´eke mellett van-e anyag´aram ciklus.
&
%
'
2007. junius ´ 8.
$
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
10/22
A vegyipari h´alozattervez´ ´ esi feladat eredm´enyei A valos ´ fuggv´ ¨ eny-ki´ert´ekel´esre t´amaszkodo´ sztochasztikus, klaszterez˝o algoritmus a´ ltal adott eredm´eny: f (x∗ )
x∗ 2
x∗ 3
x∗ 4
NFE
CPU
62.550111 0.00296602 0.99875609 0.75149047 1.0000000 56 067
8.73
62.791640 0.01029729 0.99757082 0.84846761 1.0000000 27 232
4.45
62.851381 0.02461725 0.99482994 0.64821641 1.0000000 61 190
9.45
62.855458 0.00166749 0.99553307 0.86046189 1.0000000 51 263
8.13
62.836668 0.05248426 0.99983809 0.81663978 1.0000000 38 757
6.10
a´ tlag
&
x∗ 1
47 486.3 7.470
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
$ 11/22
A vegyipari h´alozattervez´ ´ esi feladat eredm´enyei 2. Az intervallumos optimaliz´al´asi elj´ar´as 35 683 fuggv´ ¨ enyh´ıv´as e´ s 3 perc sz´am´ıtog´ ´ epid˝o a´ r´an tal´alt megold´ast 10 000 memoriaegys´ ´ egre (egy ilyen egys´eg egy r´eszintervallumot t´arolt) t´amaszkodva: F (X ∗ ) = [62.49, 62.69],
X∗
=
[0.00000000000, 0.00097656250], [0.99804687500, 0.99902343750], [0.71875000000, 0.72070312500], [0.99804687500, 1.00000000000]
&
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
A kellemetlen gy´ar telep´ıt´esi feladat eredm´enye
&
$ 12/22
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
K´aosz ellenorz´ ˝ es
$ 13/22
H´enon differencia-egyenlet rendszerekben Tekintsuk ¨ a H(x, y) = (1 + y − ax2 , bx) H´enon transzform´aciot ´ az a = 1.4 e´ s b = 0.3 e´ rt´ekekkel. A feladat olyan jellegu˝ rel´aciok ´ ellen˝orz´ese a teljes Q0 ∪ Q1 kiindul´asi halmazra, mint: H7 (Q0 ∪ Q1 ) ⊂ R2 \ E, H7 (a ∪ d) ⊂ O2 , H7 (b ∪ c) ⊂ O1 , ahol E, O1 e´ s O2 adott halmazok, e´ s a, b, c, d a Q0 e´ s Q1 paralelogramm´ak megfelel˝o oldalai. &
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
A kezdo˝ intervallum e´ s a 3 felt´etel ellenorz´ ˝ ese
a
&
Q0
$ 14/22
Q1 b c d
%
'
2007. junius ´ 8.
$
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
15/22
Az H´enon lek´epez´es 7. iter´altja kaotikuss´aga
O1
H7 (b) E2
y 0.1
E1 H7 (c) 1.0
H7 (d) H7 (a)
&
x
O2
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
$ 16/22
A f´ekezett, k´enyszereros ˝ inga is kaotikus
x
mg sin x
m mg
&
%
'
2007. junius ´ 8.
$
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
17/22
Az igazolt a´ thalad´as x′ P (Q0 ) 1 x Q−1
&
Q0
2π Q1
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
E.M. Wright 50 e´ ves sejt´ese
$ 18/22
egy k´esleltetett differenci´alegyenletrol ˝
z ′ (t) = −αz(t − 1) (1 + z(t)) , megold´asa α ∈ [1.5, π/2] eset´en is null´ahoz tart.
&
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
A megold´as befoglal´asa a y – y ′ s´ıkon.
$ 19/22
y′
y
&
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
M M ≥ log
1.8
m α
$ 20/22
+1
1.6
M ≤ −α (e−m − 1)
1.4 1.2
Computer Aided part
1 0.8 0.6 0.4 0.2 0
0
Theoretical part
(upper)
4
6
8
10
m
(upper)
y(inc,1)
y(dec,n)
(lower)
y(inc,1)
(upper)
y(dec,1) (lower)
&
y(dec,1)
(lower)
y(inc,n)
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
Kapcsolod ´ o´ kozlem´ ¨ enyek
$ 21/22
T. Csendes: Optimization methods for process network synthesis – a case study, In: Christer Carlsson and Inger Eriksson (eds.): Global & multiple criteria optimization and information systems quality. Abo Academy, Turku, 1998, 113-132 M.C. Markot ´ and T. Csendes: A new verified optimization technique for the ”packing circles in a unit square” problems. SIAM J. on Optimization 16(2005) 193-219 M.Cs. Markot ´ and T. Csendes: A reliable area reduction technique for solving circle packing problems. Computing 77 (2006) 147-162 T. Csendes, B.M. Garay, and B. B´anhelyi: A verified optimization technique to locate chaotic regions of H´enon systems. J. of Global Optimization 35(2006) 145-160 B. B´anhelyi, T. Csendes, and B.M. Garay: Optimization and the Miranda approach in detecting horseshoe-type chaos by computer. Int. J. Bifurcation and Chaos 17(2007) 735-748 T. Csendes, B. B´anhelyi, and L. Hatvani: Towards a computer-assisted proof for chaos in a forced damped pendulum equation. J. Computational and Applied Mathematics 199(2007) 378-383 P.G. Szabo, ´ M.Cs. Markot, ´ T. Csendes, E. Specht, L.G. Casado, and I. Garc´ıa: New Approaches to Circle Packing in a Square – With Program Codes. Springer, Berlin, 2007
&
%
'
2007. junius ´ 8.
XXVII. Magyar Oper´aciokutat´ ´ asi Konferencia, Balaton˝oszod ¨
$ 22/22
T´arsszerzok ˝ B´anhelyi Bal´azs, Csallner Andr´as Erik, Garay Barna, Hatvani L´aszlo, ´ Krisztin Tibor, Markot ´ Mih´aly Csaba, Arnold Neumaier Rost ¨ Gergely e´ s Szabo´ P´eter G´abor &
%
