Weberin ongelma

Weber - ongelma on yksi tunnetuimmista tuotannon sijaintiongelmista . Nimetty saksalaisen taloustieteilijän Alfred Weberin mukaan . Tehtävänä on löytää koneesta piste, joka minimoi kuljetushintojen summan tästä pisteestä n kulutuspisteeseen, joissa eri kulutuspisteille määrätään oma kuljetushinta yksikköetäisyyttä kohden.

Weberin ongelma yleistää geometrisen mediaanin etsimisen , jonka kuljetushintojen oletetaan olevan yhtä suuri kaikissa kulutuspisteissä, ja ongelman löytää Fermat-piste , kolmen pisteen geometrinen mediaani. Tästä syystä ongelmaa kutsutaan joskus Fermat–Weber-ongelmaksi, vaikka samaa nimeä käytetään myös painottamattoman geometrisen mediaanin löytämiseen. Weberin ongelma puolestaan ​​yleistetään vetovoima-hylkimisongelmaksi, joka sallii negatiiviset hinnat, joten joissakin kohdissa suurempi etäisyys on parempi.

Fermatin, Weberin ja vetovoima-hylkimisongelmien määritelmä ja historia

Maatilan tehtävä Weberin ongelma Tehtävä vetovoima
- hylkiminen
Muotoiltu Maatila (ennen vuotta 1640) Simpson (1750) Tellier (1985)

Kolmiotehtävän geometrinen ratkaisu		 Torricelli (1645) Simpson (1750) Tellier (2013)
Kolmiotehtävän suora numeerinen
ratkaisu 		Tellier (1972) Tellier (1972) Tellier (1985)
Tehtävän iteratiivinen numeerinen
ratkaisu 		Kuhn ja Kuen (1962) Kuhn ja Kuen (1962) Chen, Hansen, Jomar ja Tui (1992)

Kolmion tapauksessa Fermatin tehtävänä on löytää piste D suhteessa kolmeen pisteeseen A, B ja C siten, että D:stä kuhunkin näistä kolmesta pisteestä olevien etäisyyksien summa on minimaalinen. Ongelman muotoili kuuluisa ranskalainen matemaatikko Pierre de Fermat ennen vuotta 1640. Ongelmaa voidaan pitää tuotantopaikan ongelman todellisena alkuna. Torricelli löysi geometrisen ratkaisun ongelmaan noin vuonna 1645, mutta suoraa numeerista ratkaisua ei ollut yli 325 vuoteen. Kuhn ja Kuen [1] löysivät iteratiivisen ratkaisun Fermatin yleiseen ongelmaan vuonna 1962, ja vuonna 1972 Luc-Normand Tellier [2] löysi suoran numeerisen (trigonometrisen) ratkaisun Fermatin kolmioongelmaan. Kuhnin ja Kuenin ratkaisu pätee monikulmioihin, joissa on enemmän kuin kolme sivua, mikä ei päde Tellierin ratkaisulle alla selitetyistä syistä.

Kolmion tapauksessa Weberin tehtävänä on löytää kolmen pisteen A, B ja C suhteen sellainen piste D, että kuljetuskustannusten summa pisteestä D kolmeen muuhun pisteeseen on minimaalinen. Weber-ongelma on yleistys Fermat-ongelmasta, koska se käyttää yhtä suuria ja eriarvoisia vetovoimia (katso alla), kun taas Fermat-ongelmassa voimat ovat samat. Thomas Simpson muotoili ja ratkaisi ongelman ensimmäisen kerran kolmion tapaukselle vuonna 1750 [3] [4] . Kuhn ja Kuen löysivät iteratiivisen ratkaisun vuonna 1962, ja Tellierin vuonna 1972 löydetty ratkaisu pätee sekä Weberin että Fermatin ongelmiin. Kuhnin ja Kuenin ratkaisu pätee monikulmion tapaukseen, jossa on enemmän kuin kolme sivua.

Yksinkertaisimmassa tapauksessa veto-hylkimisen ongelmana on löytää kolmen pisteen A 1 , A 2 ja R suhteen sellainen piste D, johon kohdistuvat pisteiden A 1 ja A 2 vetovoimat ja hylkimisvoima. pisteen R kompensoivat toisiaan [5] . Ongelma yleistää sekä Fermatin että Weberin ongelman. Luc-Normand Tellier [6] muotoili ja ratkaisi ongelman kolmiolle vuonna 1985 . Vuonna 1992 Chen, Hansen, Jomar ja Tui löysivät ratkaisun Tellier-ongelmaan polygoneille, joissa on enemmän kuin kolme sivua.

Torricellin geometrinen ratkaisu Fermatin ongelmaan kolmiolle

Evangelista Torricellin geometrinen ratkaisu Fermatin kolmioongelmaan perustuu kahteen havaintoon:

1. Pisteellä D on optimaalinen sijainti, jos mikä tahansa siirtymä tästä pisteestä johtaa kokonaisetäisyyden kasvuun pisteisiin A, B ja C, mikä tarkoittaa, että optimaalinen piste on vain piste, jossa äärettömän pieni siirtymä kohti yhtä kolmesta pisteet on yhtä suuri kuin kahden muun pisteen muutosten summa. Toisin sanoen pisteet A, B ja C houkuttelevat yhtä paljon pistettä D.

2. Ympyrään piirretyssä kuperassa nelikulmiossa vastakkaisten kulmien summa on 180°. Voimme muotoilla tämän seuraavasti: jos leikkaamme ympyrän jänteellä AB, saamme ympyrän kaaret, esimerkiksi AiB ja AjB. Mikä tahansa kaareen AiB perustuva kulma ∠AiB on sama missä tahansa pisteessä i, ja kaareen AjB perustuva kulma ∠AjB on sama missä tahansa pisteessä j. Lisäksi kulmien ∠AiB ja ∠AjB summa on 180°.

Voidaan todistaa, että ensimmäisestä havainnosta seuraa, että optimipisteessä janoihin AD, BD ja CD perustuvien kolmioiden kärkien kulmien tulee olla 360° / 3 = 120°. Tästä Torricelli päätteli seuraavaa:

1. Jos kolmio ABD, jonka kulma ∠ADB on 120°, muodostaa kuperan nelikulmion ABDE, joka on piirretty ympyrään, tulee kolmion ABE kulman ∠AEB olla (180° − 120°)= 60°;

2. Yksi tapa saada piste D, jonka kulma ∠ADB on 120°, on rakentaa tasasivuinen kolmio ABE (koska tasasivuisen kolmion kaikki kulmat ovat 60°), jossa piste E on kolmion ABC ulkopuolella, ja piirtää ympyrä tämän kolmion ympärillä. Tällöin kaikissa kolmion sisällä olevan kolmion ympyrän pisteissä D' kulma ∠AD'B on 120°;

3. Sama voidaan tehdä kolmiolle ACD ja BCD;

4. Tämä johtaa tasasivuisten kolmioiden ACF ja BCG rakentamiseen, joissa F ja G ovat kolmion ABC ulkopuolella, ja myös kahden muun ympyrän rakentamiseen näiden tasasivuisten kolmioiden ympärille. Kaikki kolme ympyrää leikkaavat yhdessä pisteessä D ja janoihin AD, BD ja CD perustuvat kulmat ovat 120°, mikä osoittaa pisteen optimaalisen sijainnin.

Simpsonin geometrinen ratkaisu Weberin kolmiotehtävään

Simpsonin geometrinen ratkaisu niin sanottuun "Weber-kolmioongelmaan" (jonka Thomas Simpson muotoili vuonna 1750) seuraa suoraan Torricellin ratkaisusta. Simpson ja Weber korostavat sitä tosiasiaa, että kuljetuksen minimointiongelmassa kulutuspisteiden A, B tai C lähestymisen hyöty riippuu siitä, mitä kuljetetaan ja millä hinnalla. Siksi etäisyyden muutoksen lähestymisen edut ja kulmien ∠ADB, ∠ADC ja ∠BDC ei pitäisi enää olla 120°.

Simpson osoitti, että kolmioiden ABE, ACF ja BCG, jotka on rakennettu samalla tavalla kuin Torricellin ratkaisu, jossa E, F ja G ovat kolmion ABC ulkopuolella, täytyy olla verrannollisia vetovoimiin. Fermatin ongelman tapauksessa kolmiot olivat tasasivuisia, koska vetovoimat ovat samat

Ratkaisu on:

1. Rakennettavan kolmion ABE sivu AB on verrannollinen vetovoimaan C w kohti C, sivu AE on verrannollinen vetovoimaan B w kohti B ja sivu BE on verrannollinen vetovoimaan A w kohti A.

2. Rakennettavan kolmion BCG sivu BC on verrannollinen vetovoimaan A w kohti A, sivu BG on verrannollinen vetovoimaan B w kohti B ja sivu CG on verrannollinen vetovoimaan C w kohti A:ta. C;

3. Optimaalinen piste D sijaitsee kahden ympyrän leikkauskohdassa muodostettujen kolmioiden ABE ja BCG ympärillä.

Kolmas kolmio ACF, jossa F on kolmion ABC ulkopuolella, voidaan rakentaa sivulle AC ja kolmas ympyrä voidaan rakentaa tämän kolmion ympärille. Tämä kolmas ympyrä leikkaa kaksi muuta ympyrää samassa pisteessä D.

Tellierin geometrinen ratkaisu vetovoima-hylkimisongelmaan

Kolmion tapauksessa vetovoiman - hylkimisen ongelmalle on olemassa geometrinen ratkaisu. Se löydettiin suhteellisen hiljattain [7] . Tämä geometrinen ratkaisu eroaa kahdesta edellisestä, koska tässä tapauksessa rakennettavat voimien kolmiot asettuvat pisteiden A 1 A 2 R sijoituskolmion päälle (tässä A 1 ja A 2 ovat vetopisteitä ja R on vastenmielisyys).

Ratkaisu on:

1. Rakenteilla olevassa kolmiossa RA 2 H, joka on osittain päällekkäin pisteiden A 1 A 2 R kolmion päälle, sivu RA 2 on verrannollinen vetovoimaan A1 w kohti A 1 , sivu RH on verrannollinen vetovoimaan A2 w kohti A 2 , ja sivu A 2 H on verrannollinen hylkäysvoimaan R w poispäin R:stä.

2. Rakenteilla olevassa kolmiossa RA 1 I, joka on osittain päällekkäin pisteiden A 1 A 2 R sijoituskolmion päällä, sivu RA 1 on verrannollinen vetovoimaan A2 w A 2 :n suunnassa , sivu RI on verrannollinen vetovoimaan A1 w suunnassa A1:een ja sivu A 1 I on verrannollinen hylkäysvoimaan R w poispäin R:stä;

3. Optimaalinen piste D sijaitsee muodostettujen kolmioiden RA 2 H ja RA 1 I ympärille piirretyn kahden ympyrän leikkauskohdassa. Ratkaisua ei saada, jos toinen voimista on suurempi kuin kahden muun summa tai jos kulmat eivät ole vertailukelpoisia. Joissakin tapauksissa yllä olevia poikkeamia ei ole (mikään voima ei ole suurempi kuin kahden muun summa ja kulmat ovat vertailukelpoisia), mutta optimaalinen ratkaisu löytyy kohdasta, jossa vetovoima on suurempi.

Tellier-trigonometrinen ratkaisu Fermatin ja Weberin tehtäviin

Yli 332 vuotta erottaa kolmion Fermat-ongelman muotoilun ja ei-iteratiivisen numeerisen ratkaisun löytämisen, vaikka geometrinen ratkaisu oli olemassa lähes koko ajan. Tämä selittyy sillä, että kolmeen vetopisteeseen suunnattujen kolmen vektorin alku ei välttämättä ole sama. Jos ne osuvat yhteen ja sijaitsevat optimaalisessa pisteessä P, vektorit kohti A, B ja C sekä vetopisteiden kolmion ABC sivut muodostavat kuusi kulmaa ∠1, ∠2, ∠3, ∠4, ∠5 ja ∠6, ja kolme vektoria muodostavat kulmat ∠α A , ∠α B ja ∠α C . On helppo kirjoittaa seuraavat kuusi yhtälöä, jotka liittyvät kuuteen tuntemattomaan (kulmat ∠1, ∠2, ∠3, ∠4, ∠5 ja ∠6) kuudella tunnetulla arvolla (kulmat ∠A, ∠B ja ∠C on annettu, ja kulmien ∠α A , ∠α B ja ∠α C arvot riippuvat vain pisteisiin A, B ja C kohdistuvien kolmen vetovoiman suhteellisista arvoista:

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

Valitettavasti tämä kuuden yhtälön järjestelmä on epämääräinen, ja kolmen vektorin mahdollisuus alkaa vetopisteiden suunnasta selittää miksi. Epävastaavuuden tapauksessa on helppo nähdä, että yhtälöt pysyvät totta. Pisteen P optimaalinen sijainti kuitenkin katoaa kolmion sisällä olevan kolmion "reiän" vuoksi. Itse asiassa, kuten Tellier (1972) [2] on osoittanut , tällä kolmiomaisella "reiällä" on täsmälleen samat mittasuhteet kuin "voimakolmioilla", jotka rakensimme Simpsonin geometrisessa ratkaisussa.

Ongelman ratkaisemiseksi meidän on lisättävä näihin kuuteen yhtälöön seitsemäs yhtälö, jonka pitäisi estää kolmiomaisen "reiän" ilmestyminen vetopisteiden kolmion keskelle. Toisin sanoen vektorien alkujen on vastattava toisiaan.

Fermatin ja Weberin Tellier-ongelmien ratkaisu kolmiolle suoritetaan kolmessa vaiheessa:

1. Määritä kulmat ∠α A , ∠α B ja ∠α C , joissa kolme vetovoimaa A w, B w ja C w tasapainottavat toisiaan ja muodostavat tasapainon. Tätä varten käytämme seuraavia yhtäläisyyksiä:

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. Määritä kulman ∠3 arvo (tämä yhtälö varmistaa pisteiden D ja E yhteensopivuuden):

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

missä k = (CB/CA) (sin ∠α B / sin ∠α A ) ja k' = (∠A + ∠B + ∠α C ) − 180° ;

3. Ratkaisemme yhtälöjärjestelmän, jossa ∠3 on jo tiedossa:

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

Tellierin trigonometrinen ratkaisu vetovoima-hylkimisongelmaan

Tellier (1985) [6] laajensi Fermat-Weberin ongelman koskemaan myös hylkiviä voimia. Tarkastellaan kolmion tapausta, jossa vaikuttavat kaksi vetovoimaa A1 w ja A2 w ja yksi hylkäysvoima R w. Tässä, kuten edellisessä tapauksessa, kolmen vektorin alkujen yhteensopimattomuus on mahdollinen. Siten ratkaisun on vaadittava niiden yhteensovittamista. Tellierin trigonometrinen ratkaisu tähän ongelmaan on seuraava:

1. Määritä kulma ∠e:

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

2. Määritä kulma ∠p:

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

3. Määritä kulma ∠c:

∠c = 180° − ∠p ;

4. Määritä kulma ∠d:

∠d = ∠e − ∠c ;

5. Määritä kulman ∠3 arvo (tämä yhtälö edellyttää pisteiden D ja E yhtäläisyyttä):

tan ∠3 = x/y;

missä x = sin ∠f - (RA 1 /RA 2 )(sin ∠d sin [∠e − ∠b] / sin ∠c) ; ja y = (RA 1 /RA 2 )(sin ∠d cos [∠e − ∠b] / sin ∠c) − cos ∠f ;

6. Määritä kulma ∠1:

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

7. Määritä kulma ∠5:

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

8. Määritä kulma ∠2:

∠2 = ∠a − ∠5 .

Iteratiivinen ratkaisu Fermat-, Weber- ja vetovoima-hylkimisongelmien ratkaisuun

Jos voimien lukumäärä on suurempi kuin kolme, on mahdotonta määrittää kulmia ottamatta huomioon vetopisteen monikulmion geometriaa. Geometriset ja trigonometriset menetelmät ovat voimattomia. Näissä tapauksissa käytetään iteratiivisia optimointimenetelmiä. Kuhn ja Kuen (1962) [1] ehdottivat iteratiivisiin painotettuihin pienimmän neliösumman algoritmia , joka yleistää Weissfeld-algoritmin painottamattomalle ongelmalle . Heidän menetelmänsä toimii Fermatin ja Weberin ongelmissa, joilla on monia voimia, mutta ei vetovoima-hylkimisongelmaan. Tässä menetelmässä pisteen y approksimaatio, joka minimoi etäisyyksien painotetun summan

otetaan alkuratkaisu y 0 ja jokaisessa vaiheessa algoritmi lähestyy optimaalista ratkaisua valitsemalla y j  + 1 , minimoimalla etäisyyksien painotetun summan

,

jossa alkupainot w i jaetaan etäisyydellä pisteestä edellisen askeleen approksimaatioon. Jokainen peräkkäinen approksimaatio voidaan saada ainoan optimaalisen painotetun pienimmän neliösumman ratkaisun painotettuna keskiarvona:

Vetovoima-hylkimisongelman osalta voidaan viitata Chenin, Hansenin, Jomarin ja Tuin (1992) [8] ehdottamaan algoritmiin .

Maan arvoteorian tulkinta vetovoima-hylkimisongelman valossa

Avaruustalouden maailmassa hylkivät voimat ovat kaikkialla läsnä. Maan arvo on heidän tärkein esimerkki. Itse asiassa merkittävä osa maan arvon teoriasta , sekä maaseudulla että kaupungissa, voidaan tiivistää seuraavasti.

Siinä tapauksessa, että jokainen vetää puoleensa yhteen vetopisteeseen (maaseututori tai kaupungin keskusyritysalue), eri tarjoajien välinen kilpailu, jotka haluavat sijaita keskustassa, muodostaa maan hinnan, mikä muuttaa vetovoiman. järjestelmän hylkimispisteeseen, jonka määrää maan korkeita kustannuksia, ja jokainen asukas ja yritystoiminta sijaitsee kohdassa, jossa veto- ja hylkimisvoimat kumoutuvat.

Vetovoima-hylkimisongelma ja uusi talousmaantiede

Ottavino ja Thiess (2005) [9] pitävät Tellier-ongelmaa alkusoittona 1990-luvulla kehitetylle "uudelle talousmaantieteelle" (NEG), josta Paul Krugman sai taloustieteen Nobelin vuonna 2008. Vetovoiman käsite on liittyy NEG:n agglomeraatio- tai keskipakovoimien käsitteeseen, ja hylkimisvoimien käsite liittyy hajautus- tai keskipakovoimien käsitteeseen.

Muistiinpanot

  1. ↑ 1 2 Kuhn ja Kuenne, 1962 , s. 21–34.
  2. ↑ 1 2 Tellier, 1972 , s. 215-233.
  3. ↑ Simpson, 1750 .
  4. ↑ Weber, 1922 .
  5. ↑ Gravitaatio- tai sähkövoimien kaltaisia ​​voimia ei tässä tarkoiteta, koska nämä voimat eivät riipu etäisyydestä.
  6. ↑ 12 Tellier , 1985 .
  7. ↑ Tellier, 2013 .
  8. ↑ Chen, Hansen, Jaumard, Tuy, 1992 , s. 467–486.
  9. ↑ Ottaviano, Thisse, 2005 , s. 1707-1725

Kirjallisuus

Linkit