Weber problém

Problém Weber je jedním z nejznámějších problémů s umístěním výroby . Pojmenována po německém ekonomovi Alfredu Weberovi . Úkolem je najít na rovině bod, který minimalizuje součet cen přepravy z tohoto bodu na n odběrných míst, kde je různým odběrným místům přiřazena vlastní cena dopravy za jednotku vzdálenosti.

Weberův problém zobecňuje hledání geometrického mediánu , u kterého se předpokládá, že ceny dopravy jsou stejné pro všechna místa spotřeby, a problém hledání Fermatova bodu , geometrického mediánu tří bodů. Z tohoto důvodu se problém někdy nazývá Fermat-Weberův problém, i když stejný název se používá také pro nalezení neváženého geometrického mediánu. Weberův problém je zase zobecněn na problém přitažlivosti-odpuzování, který umožňuje záporné ceny, takže pro některé body je výhodnější větší vzdálenost.

Definice a historie problémů Fermata, Webera a přitažlivosti-odpuzování

Farmářský úkol Weber problém Úkol přitažlivosti
- odpuzování
Formulováno Farma (před rokem 1640) Simpson (1750) Tellier (1985)
Geometrické řešení
úlohy trojúhelníku 		Torricelli (1645) Simpson (1750) Tellier (2013)
Přímé numerické řešení
úlohy trojúhelníku 		Tellier (1972) Tellier (1972) Tellier (1985)
Iterativní numerické
řešení úlohy 		Kuhn a Kuen (1962) Kuhn a Kuen (1962) Chen, Hansen, Jomar a Tui (1992)

V případě trojúhelníku je Fermatovým problémem najít bod D vzhledem ke třem bodům A, B a C tak, aby součet vzdáleností od D ke každému z těchto tří bodů byl minimální. Problém formuloval slavný francouzský matematik Pierre de Fermat před rokem 1640. Problém lze považovat za skutečný začátek problému umístění výroby. Torricelli našel geometrické řešení problému kolem roku 1645, ale více než 325 let neexistovalo žádné přímé numerické řešení. Kuhn a Kuen [1] našli iterativní řešení Fermatova obecného problému v roce 1962 a v roce 1972 Luc-Normand Tellier [2] našel přímé numerické (trigonometrické) řešení Fermatova trojúhelníkového problému. Kuhnovo a Kuenovo řešení je platné pro mnohoúhelníky s více než třemi stranami, což neplatí pro Tellierovo řešení z důvodů vysvětlených níže.

V případě trojúhelníku je úkolem Webera najít takový bod D vzhledem ke třem bodům A, B a C, aby součet nákladů na dopravu z bodu D do dalších tří bodů byl minimální. Weberův problém je zobecněním Fermatova problému, protože používá stejné a nestejné přitažlivé síly (viz níže), zatímco ve Fermatově problému jsou síly stejné. Úlohu poprvé zformuloval a vyřešil pro případ trojúhelníku Thomas Simpson v roce 1750 [3] [4] . Kuhn a Kuen našli iterativní řešení v roce 1962 a Tellierovo řešení, nalezené v roce 1972, platí pro Weberův i Fermatův problém. Řešení Kuhna a Kuena platí pro případ mnohoúhelníku s více než třemi stranami.

V nejjednodušším případě je problémem přitažlivosti-odpudivosti najít takový bod D vzhledem ke třem bodům A 1 , A 2 a R, aby působily aplikované přitažlivé síly bodů A 1 a A 2 a síla odpuzování. bodu R se vzájemně kompenzují [5] . Problém zobecňuje jak Fermatův problém, tak Weberův problém. Problém formuloval a vyřešil pro trojúhelník v roce 1985 Luc-Normand Tellier [6] . V roce 1992 našli Chen, Hansen, Jomar a Tui řešení Tellierova problému pro mnohoúhelníky s více než třemi stranami.

Torricelliho geometrické řešení Fermatovy úlohy pro trojúhelník

Geometrické řešení Fermatova trojúhelníkového problému Evangelisty Torricelliho se opírá o dvě pozorování:

1. Bod D má optimální polohu, pokud jakýkoli posun od tohoto bodu vede ke zvětšení celkové vzdálenosti k bodům A, B a C, což znamená, že optimálním bodem je pouze bod, ve kterém dojde k nekonečně malému posunu směrem k jednomu ze tří bodů. bodů se rovná součtu změn ostatních dvou bodů. Jinými slovy, bod D je stejně přitahován body A, B a C.

2. V konvexním čtyřúhelníku vepsaném do kruhu tvoří protilehlé úhly součet 180°. Můžeme to formulovat následovně: rozřízneme-li kružnici tětivou AB, dostaneme oblouky kružnice, řekněme AiB a AjB. Jakýkoli úhel ∠AiB založený na oblouku AiB je stejný pro jakýkoli bod i a úhel ∠AjB založený na oblouku AjB je stejný pro jakýkoli bod j. Navíc úhly ∠AiB a ∠AjB tvoří dohromady 180°.

Lze dokázat, že z prvního pozorování vyplývá, že v bodě optima musí být úhly ve vrcholech trojúhelníků založených na úsecích AD, BD a CD rovné 360° / 3 = 120°. Z toho Torricelli usoudil, že:

1. Jestliže trojúhelník ABD, jehož úhel ∠ADB je roven 120°, tvoří konvexní čtyřúhelník ABDE vepsaný do kruhu, musí být úhel ∠AEB trojúhelníku ABE roven (180° − 120°)= 60°;

2. Jedním ze způsobů, jak získat bod D, pro který je úhel ∠ADB 120°, je sestrojit rovnostranný trojúhelník ABE (protože všechny úhly rovnostranného trojúhelníku jsou 60°), kde bod E je vně trojúhelníku ABC, a nakreslit kružnici kolem tohoto trojúhelníku. Potom pro všechny body D' kružnice opsané trojúhelníku ležícího uvnitř trojúhelníku je úhel ∠AD'B roven 120°;

3. Totéž lze provést pro trojúhelníky ACD a BCD;

4. To vede ke konstrukci rovnostranných trojúhelníků ACF a BCG, kde F a G leží mimo trojúhelník ABC, a také ke konstrukci dvou dalších kružnic kolem těchto rovnostranných trojúhelníků. Všechny tři kružnice se protínají v jednom bodě D a úhly založené na úsecích AD, BD a CD budou rovné 120°, což dokazuje optimální polohu bodu.

Simpsonovo geometrické řešení úlohy Weberova trojúhelníku

Simpsonovo geometrické řešení takzvaného „Weberova trojúhelníkového problému“ (který zformuloval Thomas Simpson v roce 1750) přímo navazuje na Torricelliho řešení. Simpson a Weber zdůrazňují skutečnost, že v problému minimalizace dopravy závisí výhoda přiblížení se k místům spotřeby A, B nebo C na tom, co se přepravuje a za jakou cenu. Proto se výhoda přiblížení na určitou vzdálenost změní a úhly ∠ADB, ∠ADC a ∠BDC by již neměly být 120°.

Simpson ukázal, že trojúhelníky ABE, ACF a BCG, konstruované podobně jako Torricelliho řešení, kde E, F a G jsou mimo trojúhelník ABC, musí být úměrné přitažlivým silám. V případě Fermatova problému byly trojúhelníky rovnostranné, protože přitažlivé síly jsou stejné

Řešením je:

1. V trojúhelníku ABE ve výstavbě je strana AB úměrná přitažlivé síle C w vůči C, strana AE ​​je úměrná přitažlivé síle B w vůči B a strana BE je úměrná přitažlivé síle A w směrem k A.

2. Ve výstavbě trojúhelníku BCG je strana BC úměrná přitažlivé síle A w směrem k A, strana BG je úměrná síle přitažlivosti B w vůči B a strana CG je úměrná síle přitažlivosti C w směrem k C;

3. Optimální bod D se nachází v průsečíku dvou kružnic kolem sestrojených trojúhelníků ABE a BCG.

Třetí trojúhelník ACF, kde F je vnější trojúhelník ABC, může být postaven na straně AC a třetí kruh může být postaven kolem tohoto trojúhelníku. Tato třetí kružnice protíná další dvě kružnice ve stejném bodě D.

Tellierovo geometrické řešení problému přitažlivosti a odpuzování

Pro problém přitažlivosti – odpuzování v případě trojúhelníku existuje geometrické řešení. Byl objeven relativně nedávno [7] . Toto geometrické řešení se liší od dvou předchozích, protože v tomto případě jsou trojúhelníky budovaných sil superponovány na trojúhelník umístění bodů A 1 A 2 R (zde A 1 a A 2 jsou přitahovací body a R je bod odpuzování).

Řešením je:

1. V rozestavěném trojúhelníku RA 2 H, který je částečně navrstven na trojúhelník umístění bodů A 1 A 2 R, je strana RA 2 úměrná přitažlivé síle A1 w vůči A 1 , strana RH je úměrná. k přitažlivé síle A2w směrem k A2 a strana A2H je úměrná odpudivé síle Rw ve směru od R.

2. V rozestavěném trojúhelníku RA 1 I, který je částečně navrstven na trojúhelník umístění bodů A 1 A 2 R, je strana RA 1 úměrná přitažlivé síle A2 w ve směru A 2 , strana RI je úměrná přitažlivé síle A1w ve směru k A1 a strana A1I je úměrná odpudivé síle Rw ve směru od R ;

3. Optimální bod D se nachází v průsečíku dvou kružnic opsaných kolem sestrojených trojúhelníků RA 2 H a RA 1 I. Řešení se nezíská, pokud je jedna ze sil větší než součet ostatních dvou nebo pokud úhly nejsou srovnatelné. V některých případech nedochází k žádným výše uvedeným porušením (žádná síla není větší než součet ostatních dvou a úhly jsou srovnatelné), ale optimální řešení je nalezeno v bodě s větší přitažlivou silou.

Tellierovo trigonometrické řešení Fermatových a Weberových úloh

Více než 332 let dělí formulaci Fermatovy úlohy pro trojúhelník a objev neiterativního numerického řešení, ačkoli geometrické řešení existovalo téměř po celou dobu. To je vysvětleno skutečností, že počátky tří vektorů směřujících ke třem přitažlivým bodům se nemusí shodovat. Pokud se shodují a leží v optimálním bodě P, vektory směrem k A, B a C a strany trojúhelníku přitažlivých bodů ABC svírají šest úhlů ∠1, ∠2, ∠3, ∠4, ∠5 a ∠6 a tři vektory svírají úhly ∠α A , ∠α B a ∠α C . Je snadné napsat následujících šest rovností týkajících se šesti neznámých (úhly ∠1, ∠2, ∠3, ∠4, ∠5 a ∠6) se šesti známými hodnotami (úhly ∠A, ∠B a ∠C jsou uvedeny a hodnoty úhlů ∠α A , ∠α B a ∠α C závisí pouze na relativních hodnotách tří přitažlivých sil k bodům A, B a C):

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

Bohužel tento systém šesti rovnic je neurčitý a možnost tří vektorů začínajících ve směru přitahovacích bodů vysvětluje proč. V případě neshody je snadné vidět, že rovnice zůstávají pravdivé. Optimální poloha bodu P však mizí díky trojúhelníkové „díře“ uvnitř trojúhelníku. Ve skutečnosti, jak ukázal Tellier (1972) [2] , tato trojúhelníková „díra“ má přesně stejné proporce jako „silové trojúhelníky“, které jsme postavili v Simpsonově geometrickém řešení.

Abychom problém vyřešili, musíme k těmto šesti rovnicím přidat sedmou rovnici, která by měla zabránit vzniku trojúhelníkové „díry“ ve středu trojúhelníku přitažlivých bodů. Jinými slovy, začátky vektorů se musí shodovat.

Řešení Tellierových problémů Fermata a Webera pro trojúhelník se provádí ve třech krocích:

1. Určete úhly ∠α A , ∠α B a ∠α C , při kterých se tři přitažlivé síly A w, B w a C w vzájemně vyrovnávají a zajišťují rovnováhu. K tomu používáme následující rovnosti:

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. Určete hodnotu úhlu ∠3 (tato rovnost zajišťuje shodu bodů D a E):

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

kde k = (CB/CA) (sin ∠α B / sin ∠α A ) a k' = (∠A + ∠B + ∠α C ) − 180°;

3. Řešíme soustavu rovnic, ve které je již známo ∠3:

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

Tellierovo trigonometrické řešení problému přitažlivosti-odpuzování

Tellier (1985) [6] rozšířil Fermat-Weberův problém na případ odpudivých sil. Uvažujme případ pro trojúhelník, ve kterém působí dvě přitažlivé síly A1 w a A2 w a jedna odpudivá síla R w. Zde, stejně jako v předchozím případě, je možný případ nesouladu začátků tří vektorů. Řešení tedy musí vyžadovat jejich spárování. Tellierovo trigonometrické řešení tohoto problému je následující:

1. Určete úhel ∠e:

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

2. Určete úhel ∠p:

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

3. Určete úhel ∠c:

∠c = 180° − ∠p ;

4. Určete úhel ∠d:

∠d = ∠e − ∠c ;

5. Určete hodnotu úhlu ∠3 (tato rovnice vyžaduje shodu bodů D a E):

tan ∠3 = x/y;

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

6. Určete úhel ∠1:

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

7. Určete úhel ∠5:

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

8. Určete úhel ∠2:

∠2 = ∠a − ∠5 .

Iterativní řešení Fermatova, Weberova a přitažlivě-odpudivého problému

Pokud je počet sil větší než tři, je nemožné určit úhly bez uvážení geometrie polygonu přitažlivého bodu. Geometrické a trigonometrické metody jsou bezmocné. V těchto případech se používají metody iterační optimalizace. Kuhn a Kuen (1962) [1] navrhli algoritmus založený na iterativních vážených nejmenších čtvercích zobecňující Weissfeldův algoritmus pro nevážený problém . Jejich metoda funguje pro problémy Fermat a Weber, které mají mnoho sil, ale ne pro problém přitažlivosti a odpuzování. V této metodě najít aproximaci k bodu y , která minimalizuje vážený součet vzdáleností

vezme se počáteční řešení y 0 a v každém kroku se algoritmus blíží k optimálnímu řešení volbou y j  + 1 , čímž se minimalizuje vážený součet vzdáleností

,

kde počáteční váhy w i jsou děleny vzdáleností od bodu k aproximaci předchozího kroku. Každou následnou aproximaci lze získat jako vážený průměr jediného optimálního váženého řešení nejmenších čtverců:

Pro problém přitažlivosti-odpuzování lze odkázat na algoritmus navržený Chenem, Hansenem, Jomarem a Tui (1992) [8] .

Interpretace teorie hodnoty půdy ve světle problému přitažlivosti-odpuzování

Ve světě vesmírné ekonomiky jsou odpudivé síly všudypřítomné. Jejich hlavním příkladem je hodnota půdy. Ve skutečnosti lze významnou část teorie hodnoty půdy , venkovské i městské, shrnout následovně.

V případě, že je každý přitahován jediným přitažlivým místem (venkovské tržiště nebo centrální obchodní čtvrť města), konkurence různých uchazečů, kteří chtějí být umístěni v centru, tvoří cenu pozemku, která mění bod přitažlivosti. systému do bodu odpuzování, určeného vysokou cenou půdy, a každý obyvatel a obchodní činnost se nachází v bodě, kde se síly přitažlivosti a odpuzování vyruší.

Problém přitažlivosti a odpuzování a nová ekonomická geografie

Ottavino a Thiess (2005) [9] považují Tellierův problém za předehru k „nové ekonomické geografii“ (NEG) vyvinuté v 90. letech, za kterou Paul Krugman obdržel v roce 2008 Nobelovu cenu za ekonomii . souvisí s konceptem aglomeračních nebo dostředivých sil NEG a koncept odpudivých sil souvisí s konceptem rozptylových nebo odstředivých sil.

Poznámky

  1. ↑ 1 2 Kuhn a Kuenne, 1962 , s. 21–34.
  2. ↑ 1 2 Tellier, 1972 , str. 215–233.
  3. ↑ Simpson, 1750 .
  4. ↑ Weber, 1922 .
  5. ↑ Síly podobné gravitačním nebo elektrickým silám zde nejsou myšleny, protože tyto síly nezávisí na vzdálenosti.
  6. ↑ 12 Tellier , 1985 .
  7. ↑ Tellier, 2013 .
  8. ↑ Chen, Hansen, Jaumard, Tuy, 1992 , str. 467–486.
  9. ↑ Ottaviano, Thisse, 2005 , str. 1707–1725

Literatura

Odkazy