Weber probléma

A Weber probléma az egyik leghíresebb gyártási hely probléma . Nevét Alfred Weber német közgazdászról kapta . A feladat egy olyan pont megtalálása a síkon, amely minimalizálja a szállítási árak összegét innen n fogyasztási pontig, ahol a különböző fogyasztási pontokhoz saját szállítási árat rendelnek egységnyi távolságra.

A Weber-probléma általánosítja a geometriai medián keresését , amelyre a szállítási árakat minden fogyasztási pontra egyenlőnek feltételezzük, valamint a Fermat-pont , a három pont geometriai mediánjának megtalálásának problémáját. Emiatt a problémát néha Fermat–Weber-problémának is nevezik, bár ugyanezt a nevet használják a súlyozatlan geometriai medián megtalálására is. A Weber-problémát pedig a vonzás-taszítás problémára általánosítják, ami negatív árakat tesz lehetővé, így bizonyos pontoknál a nagyobb távolság előnyösebb.

A Fermat, Weber és a vonzás-taszítás problémák meghatározása és története

Farm feladat Weber probléma A vonzás feladata
- taszítás
Megfogalmazva Farm (1640 előtt) Simpson (1750) Tellier (1985)

A háromszög feladat geometriai megoldása		 Torricelli (1645) Simpson (1750) Tellier (2013)

A háromszög feladat közvetlen numerikus megoldása		 Tellier (1972) Tellier (1972) Tellier (1985)
A feladat iteratív numerikus
megoldása 		Kuhn és Kuen (1962) Kuhn és Kuen (1962) Chen, Hansen, Jomar és Tui (1992)

Háromszög esetén Fermat problémája az, hogy három A, B és C ponthoz képest találjon egy D pontot úgy, hogy a D-től a három pontig tartó távolságok összege minimális legyen. A problémát a híres francia matematikus, Pierre de Fermat fogalmazta meg 1640 előtt. A probléma a termelési hely probléma igazi kezdetének tekinthető. Torricelli 1645 körül talált geometriai megoldást a problémára, de több mint 325 évig nem volt közvetlen numerikus megoldás. Kuhn és Kuen [1] 1962-ben iteratív megoldást talált Fermat általános problémájára, 1972 -ben pedig Luc-Normand Tellier [2] közvetlen numerikus (trigonometrikus) megoldást talált Fermat háromszögproblémájára. Kuhn és Kuen megoldása háromnál több oldalú sokszögekre érvényes, ami Tellier megoldására az alábbiakban kifejtett okok miatt nem igaz.

Háromszög esetén Weber feladata olyan D pontot találni az A, B és C három ponthoz képest, hogy a D pontból a másik három pontba való szállítás költségének összege minimális legyen. A Weber-probléma a Fermat-probléma általánosítása, mivel egyenlő és egyenlőtlen vonzóerőket használ (lásd alább), míg a Fermat-probléma esetében az erők azonosak. A problémát először Thomas Simpson fogalmazta meg és oldotta meg egy háromszög esetére 1750-ben [3] [4] . Kuhn és Kuen 1962-ben talált egy iteratív megoldást, Tellier 1972-ben talált megoldása pedig Weber és Fermat problémáira egyaránt vonatkozik. Kuhn és Kuen megoldása egy háromnál több oldalú sokszög esetére érvényes.

A legegyszerűbb esetben a vonzás-taszítás problémája az, hogy a három A 1 , A 2 és R ponthoz képest olyan D pontot találjunk, amelyre az A 1 és A 2 pontok vonzási ereje és a taszító erő hat. az R pontból kompenzálják egymást [5] . A probléma általánosítja a Fermat-problémát és a Weber-problémát is. A problémát Luc-Normand Tellier [6] fogalmazta meg és oldotta meg egy háromszögre 1985 -ben . 1992-ben Chen, Hansen, Jomar és Tui megoldást találtak a Tellier-problémára a háromnál több oldalú sokszögekre.

Fermat-probléma Torricelli geometriai megoldása háromszögre

Evangelista Torricelli Fermat-háromszög-probléma geometriai megoldása két megfigyelésen alapul:

1. A D pont akkor van optimális helyzetben, ha ebből a pontból bármilyen eltolás az A, B és C pontok teljes távolságának növekedéséhez vezet, ami azt jelenti, hogy az optimális pont csak az a pont, ahol végtelenül kicsi az eltolódás a három közül. pont egyenlő a másik két pont változásainak összegével. Más szavakkal, a D pontot egyformán vonzzák az A, B és C pontok.

2. Egy körbe írt konvex négyszögben a szemközti szögek összeadódnak 180°-kal. Ezt a következőképpen fogalmazhatjuk meg: ha az AB húrral vágjuk a kört, akkor megkapjuk a kör íveit mondjuk AiB és AjB. Az AiB ív alapján tetszőleges ∠AiB szög azonos bármely i pontban, és az AjB íven alapuló ∠AjB szög minden j pontban azonos. Ezenkívül az ∠AiB és ∠AjB szögek összeadva 180°-ot tesznek ki.

Bizonyítható, hogy az első megfigyelésből az következik, hogy az optimum pontjában az AD, BD és CD szakaszok alapján a háromszögek csúcsaiban lévő szögeknek 360° / 3 = 120°-nak kell lenniük. Ebből Torricelli arra a következtetésre jutott:

1. Ha az ABD háromszög, amelynek ∠ADB szöge 120°, egy konvex ABDE négyszöget alkot egy körbe, akkor az ABE háromszög ∠AEB szögének egyenlőnek kell lennie (180° − 120°)= 60°;

2. Az egyik módja annak, hogy olyan D pontot kapjunk, amelynél az ∠ADB szög 120°, ha megszerkesztünk egy ABE egyenlő oldalú háromszöget (mivel egy egyenlő oldalú háromszög minden szöge 60°), ahol az E pont az ABC háromszögön kívül van, és kört rajzolunk. e háromszög körül. Ekkor a háromszögben elhelyezkedő háromszög körülírt körének minden D' pontja esetén az ∠AD'B szög egyenlő 120°-kal;

3. Ugyanezt megtehetjük az ACD és BCD háromszögeknél is;

4. Ez az ACF és BCG egyenlő oldalú háromszögek felépítéséhez vezet, ahol F és G az ABC háromszögön kívül található, valamint két másik kör megalkotásához ezen egyenlő oldalú háromszögek köré. Mindhárom kör egy D pontban metszi egymást, és az AD, BD és CD szakaszok szögei 120°-kal egyenlők, ami bizonyítja a pont optimális helyzetét.

A Weber-háromszög probléma Simpson-féle geometriai megoldása

Simpson geometriai megoldása az úgynevezett "Weber-háromszög problémára" (amelyet Thomas Simpson fogalmazott meg 1750-ben) közvetlenül Torricelli megoldásából következik. Simpson és Weber azt a tényt hangsúlyozzák, hogy a szállítási minimalizálás problémájában az A, B vagy C fogyasztási pontok megközelítésének haszna attól függ, hogy mit és milyen áron szállítanak. Emiatt a távolság bizonyos mértékig megváltozik, és az ∠ADB, ∠ADC és ∠BDC szögek már nem lehetnek 120°-ok.

Simpson megmutatta, hogy a Torricelli-féle megoldáshoz hasonlóan megszerkesztett ABE, ACF és BCG háromszögeknek, ahol E, F és G kívül esnek az ABC háromszögön, arányosnak kell lenniük a vonzási erőkkel. Fermat-probléma esetén a háromszögek egyenlő oldalúak voltak, mert a vonzási erők azonosak

A megoldás a következő:

1. Az épülő ABE háromszögben az AB oldal arányos a C irányú C w, az AE oldal a B w vonzáserővel arányos a B felé, a BE oldal pedig az A vonzáserővel . w A felé.

2. Az épülő BCG háromszögben a BC oldal arányos az A irányú A w, a BG oldal a B irányú B w vonzáserővel, a CG oldal pedig a C w vonzáserővel A felé . C;

3. Az optimális D pont az ABE és BCG háromszögek körüli két kör metszéspontjában található.

Egy harmadik ACF háromszög, ahol F az ABC háromszögön kívül van, építhető az AC oldalra, és egy harmadik kör építhető e háromszög köré. Ez a harmadik kör a másik két kört ugyanabban a D pontban metszi.

A vonzás-taszítás probléma Tellier-féle geometriai megoldása

A vonzás - taszítás problémájára háromszög esetén létezik egy geometriai megoldás. Viszonylag nemrég fedezték fel [7] . Ez a geometriai megoldás eltér az előző két megoldástól, mivel ebben az esetben a felépülő erőháromszögek az A 1 A 2 R pontok elhelyezési háromszögére helyezkednek (itt A 1 és A 2 a vonzási pontok, R pedig a taszítás pontja).

A megoldás a következő:

1. Az épülő RA 2 H háromszögben, amely részben az A 1 A 2 R pontok elhelyezési háromszögére van ráhelyezve , az RA 2 oldal arányos az A1 w vonzási erővel A 1 felé , az RH oldal arányos az A2 w vonzási erővel A 2 felé, az A 2 H oldal pedig arányos az R -től távolodó R w taszítóerővel .

2. Az A 1 A 2 R pontok elhelyezési háromszögére részben ráhelyezett RA 1 I épülő háromszögben az RA 1 oldal arányos az A 2 irányú A2 w vonzási erővel , az oldal RI arányos az A1 w vonzási erővel A 1 irányában, az A 1 I oldal pedig az R -től távolabbi R w taszítóerővel ;

3. Az optimális D pont az RA 2 H és RA 1 I megszerkesztett háromszögek körül körülírt két kör metszéspontjában található . A megoldást nem kapjuk meg, ha az egyik erő nagyobb, mint a másik kettő összege, vagy ha a szögek nem összehasonlíthatók. Egyes esetekben nincs fent említett szabálytalanság (egyetlen erő sem nagyobb, mint a másik kettő összege, és a szögek összehasonlíthatók), de az optimális megoldást a nagyobb vonzóerővel rendelkező pontban találjuk.

A Fermat- és Weber-probléma Tellier-trigonometrikus megoldása

Több mint 332 év választja el a Fermat-probléma háromszögre való megfogalmazását és a nem iteratív numerikus megoldás felfedezését, bár a geometriai megoldás szinte az egész idő alatt létezett. Ez azzal magyarázható, hogy a három vonzási pontra irányított három vektor kezdete nem feltétlenül esik egybe. Ha egybeesnek és az optimális P pontban fekszenek, akkor az A, B és C irányába eső vektorok, valamint az ABC vonzási pontok háromszögének oldalai alkotják a hat szöget ∠1, ∠2, ∠3, ∠4, ∠5 és ∠6, és a három vektor ∠α A , ∠α B és ∠α C szögeket alkot . Könnyű felírni a következő hat egyenlőséget hat ismeretlenre (a ∠1, ∠2, ∠3, ∠4, ∠5 és ∠6 szögekre) hat ismert értékkel (a ∠A, ∠B és ∠C szögek). adottak, és a ∠α A , ∠α B és ∠α C szögek értéke csak az A, B és C pontokhoz ható három vonzási erő relatív értékétől függ):

∠1 + ∠2 = ∠C ; ∠3 + ∠4 = ∠A ; ∠5 + ∠6 = ∠B ; ∠1 + ∠6 + ∠α A = 180° ; ∠2 + ∠3 + ∠α B = 180° ; ∠4 + ∠5 + ∠α C = 180°.

Sajnos ez a hat egyenletrendszer határozatlan, és a vonzási pontok irányában kezdődő három vektor lehetősége megmagyarázza miért. Eltérés esetén könnyen belátható, hogy az egyenletek igazak maradnak. A P pont optimális helyzete azonban eltűnik a háromszög belsejében lévő háromszög alakú "lyuk" miatt. Valójában, amint Tellier (1972) [2] kimutatta , ennek a háromszög alakú „lyuknak” pontosan ugyanolyan az aránya, mint a Simpson geometriai megoldásában felépített „erőháromszögeknek”.

A probléma megoldásához ehhez a hat egyenlethez hozzá kell adnunk egy hetedik egyenletet, amely megakadályozza egy háromszög alakú "lyuk" megjelenését a vonzási pontok háromszögének közepén. Más szóval, a vektorok kezdeteinek egyeznie kell.

Fermat és Weber Tellier-problémáinak háromszögre vonatkozó megoldása három lépésben történik:

1. Határozza meg azokat a ∠α A , ∠α B és ∠α C szögeket , amelyeknél a három vonzási erő A w, B w és C w kiegyensúlyozza egymást, egyensúlyt biztosítva. Ehhez a következő egyenlőségeket használjuk:

cos ∠α A = −( B w 2 + C w 2 − A w 2 ) / (2 B w C w) ; cos ∠α B = −( A w 2 + C w 2 − B w 2 ) / (2 A w C w) ; cos ∠α C = −( A w 2 + B w 2 − C w 2 ) / (2 A w B w) ;

2. Határozza meg a ∠3 szög értékét (ez az egyenlőség biztosítja a D és E pontok egybeesését):

tan ∠3 = (k sin k') / (1 + k cos k') ;

ahol k = (CB/CA) (sin ∠α B / sin ∠α A ) és k' = (∠A + ∠B + ∠α C ) − 180° ;

3. Megoldunk egy egyenletrendszert, amelyben ∠3 már ismert:

∠1 + ∠2 = ∠C ; ∠3 + ∠4 = ∠A ; ∠5 + ∠6 = ∠B ; ∠1 + ∠6 + ∠α A = 180° ; ∠2 + ∠3 + ∠α B = 180° ; ∠4 + ∠5 + ∠α C = 180°.

A vonzás-taszítás probléma Tellier-féle trigonometrikus megoldása

Tellier (1985) [6] kiterjesztette a Fermat-Weber problémát a taszító erők esetére. Tekintsük egy olyan háromszög esetét, amelyben két A1 w és A2 w vonzóerő és egy R w taszító erő hat. Itt, akárcsak az előző esetben, lehetséges három vektor kezdetének eltérése. Így a megoldásnak meg kell követelnie ezek párosítását. Tellier trigonometrikus megoldása erre a problémára a következő:

1. Határozza meg a ∠e szöget:

cos ∠e = -( A1 w 2 + A2 w 2 − R w 2 ) / (2 A1 w A2 w) ;

2. Határozza meg a ∠p szöget:

cos ∠p = -( A1 w 2 + R w 2 − A2 w 2 ) / (2 A1 w R w) ;

3. Határozza meg a ∠c szöget:

∠c = 180° − ∠p ;

4. Határozza meg a ∠d szöget:

∠d = ∠e − ∠c ;

5. Határozza meg a ∠3 szög értékét (ehhez az egyenlethez a D és E pontok egybeesése szükséges):

tan ∠3 = x / y ;

ahol x = sin ∠f - (RA 1 /RA 2 )(sin ∠d sin [∠e − ∠b] / sin ∠c) ; és y = (RA 1 /RA 2 )(sin ∠d cos [∠e − ∠b] / sin ∠c) − cos ∠f ;

6. Határozza meg a ∠1 szöget:

∠1 = 180° - ∠e - ∠3 ;

7. Határozza meg a szöget ∠5:

∠5 = 180° - ∠b - ∠c - ∠1 ;

8. Határozza meg a ∠2 szöget:

∠2 = ∠a − ∠5 .

A Fermat, Weber és a vonzás-taszítás problémák iteratív megoldása

Ha az erők száma háromnál nagyobb, lehetetlenné válik a szögek meghatározása anélkül, hogy figyelembe vennénk a vonzási pont sokszögének geometriáját. A geometriai és trigonometrikus módszerek tehetetlenek. Ezekben az esetekben iteratív optimalizálási módszereket alkalmaznak. Kuhn és Kuen (1962) [1] egy iteratív súlyozott legkisebb négyzeteken alapuló algoritmust javasoltak, általánosítva a Weissfeld-algoritmust a súlyozatlan problémára . Módszerük működik a Fermat- és Weber-problémákra, amelyeknek sok ereje van, de nem a vonzás-taszítás problémára. Ebben a módszerben egy olyan y pont közelítésének megtalálása, amely minimalizálja a távolságok súlyozott összegét

egy y 0 kezdeti megoldást veszünk, és az algoritmus minden lépésben megközelíti az optimális megoldást y j  + 1 választásával , minimalizálva a távolságok súlyozott összegét

,

ahol a w i kezdeti súlyokat elosztjuk a pont és az előző lépés közelítésének távolságával. Minden egymást követő közelítés megkapható az egyetlen optimális súlyozott legkisebb négyzetek megoldásának súlyozott átlagaként:

A vonzás-taszítás problémájához Chen, Hansen, Jomar és Tui (1992) által javasolt algoritmusra lehet hivatkozni [8] .

A földértékelmélet értelmezése a vonzás-taszítás probléma tükrében

Az űrgazdaságtan világában a taszító erők mindenütt jelen vannak. A föld értéke a fő szemléltetésük. Valójában a földérték elméletének jelentős része , mind a vidéki, mind a városi, a következőképpen foglalható össze.

Abban az esetben, ha mindenkit egyetlen vonzási pont vonz (vidéki piac vagy egy város központi üzleti negyede), a központban elhelyezkedni kívánó különböző pályázók versenye alakítja ki a telek árát, ami átalakítja a vonzáspontot. a rendszer egy taszító pontjává, amelyet a magas földköltség határoz meg, és minden lakó és üzleti tevékenység azon a ponton helyezkedik el, ahol a vonzás és a taszító erők megszűnnek.

A vonzás-taszítás probléma és az új gazdaságföldrajz

Ottavino és Thiess (2005) [9] a Tellier-problémát az 1990-es években kifejlesztett „új gazdaságföldrajz” (NEG) előjátékának tekinti , amelyért Paul Krugman 2008 -ban közgazdasági Nobel-díjat kapott . A vonzó erők fogalma a NEG agglomerációs vagy centripetális erőinek fogalmához, a taszító erők fogalma pedig a szétszóródó vagy centrifugális erők fogalmához kapcsolódik.

Jegyzetek

  1. ↑ 1 2 Kuhn és Kuenne, 1962 , p. 21–34.
  2. ↑ 1 2 Tellier, 1972 , p. 215–233.
  3. ↑ Simpson, 1750 .
  4. ↑ Weber, 1922 .
  5. ↑ A gravitációs vagy elektromos erőkhöz hasonló erőket itt nem értjük, mivel ezek az erők nem függenek a távolságtól.
  6. ↑ 12 Tellier , 1985 .
  7. ↑ Tellier, 2013 .
  8. ↑ Chen, Hansen, Jaumard, Tuy, 1992 , p. 467–486.
  9. ↑ Ottaviano, Thisse, 2005 , p. 1707–1725

Irodalom

Linkek