Weber problem

Weber-problemet er et af de mest berømte produktionsplaceringsproblemer . Opkaldt efter den tyske økonom Alfred Weber . Opgaven er at finde et punkt på flyet, der minimerer summen af ​​transportpriser fra dette punkt til n forbrugspunkter, hvor forskellige forbrugspunkter får tildelt deres egen transportpris pr. afstandsenhed.

Webers problem generaliserer søgningen efter den geometriske median , for hvilken transportpriser antages at være ens for alle forbrugspunkter, og problemet med at finde Fermat-punktet , den geometriske median af tre punkter. Af denne grund kaldes problemet nogle gange for Fermat-Weber-problemet, selvom det samme navn også bruges til at finde den uvægtede geometriske median. Webers problem er til gengæld generaliseret til tiltrækning-frastødning-problemet, som tillader negative priser, så for nogle punkter er en større afstand at foretrække.

Definition og historie af Fermat-, Weber- og tiltræknings-afstødningsproblemerne

Farm opgave Weber problem Opgaven med tiltrækning
- frastødning
Formuleret Gård (før 1640) Simpson (1750) Tellier (1985)
Geometrisk løsning
af trekantsproblemet 		Torricelli (1645) Simpson (1750) Tellier (2013)
Direkte numerisk løsning
af trekantsproblemet 		Tellier (1972) Tellier (1972) Tellier (1985)
Iterativ numerisk
løsning af problemet 		Kuhn og Kuen (1962) Kuhn og Kuen (1962) Chen, Hansen, Jomar og Tui (1992)

I tilfælde af en trekant er Fermats problem at finde et punkt D i forhold til tre punkter A, B og C, således at summen af ​​afstandene fra D til hvert af disse tre punkter er minimal. Problemet blev formuleret af den berømte franske matematiker Pierre de Fermat før 1640. Problemet kan betragtes som den sande begyndelse på produktionsstedsproblemet. Torricelli fandt en geometrisk løsning på problemet omkring 1645, men der var ingen direkte numerisk løsning i mere end 325 år. Kuhn og Kuen [1] fandt en iterativ løsning på Fermats generelle problem i 1962, og i 1972 fandt Luc-Normand Tellier [2] en direkte numerisk (trigonometrisk) løsning på Fermats trekantede problem. Kuhn og Kuens løsning er gyldig for polygoner med mere end tre sider, hvilket ikke er tilfældet for Telliers løsning af årsager forklaret nedenfor.

I tilfælde af en trekant er Webers opgave at finde et sådant punkt D i forhold til de tre punkter A, B og C, at summen af ​​transportomkostningerne fra punkt D til de tre andre punkter var minimal. Weber-problemet er en generalisering af Fermat-problemet, fordi det bruger lige store og ulige tiltrækningskræfter (se nedenfor), mens kræfterne i Fermat-problemet er de samme. Problemet blev først formuleret og løst for tilfældet med en trekant af Thomas Simpson i 1750 [3] [4] . Kuhn og Kuen fandt en iterativ løsning i 1962, og Telliers løsning, der blev fundet i 1972, gælder både Webers og Fermats problemer. Kuhn og Kuens løsning gælder for tilfældet med en polygon med mere end tre sider.

I det enkleste tilfælde er problemet med tiltrækningsrepulsion at finde et sådant punkt D i forhold til de tre punkter A 1 , A 2 og R, at de påførte tiltrækningskræfter af punkt A 1 og A 2 påførte og frastødningskraften af punktet R kompenserer hinanden [5] . Problemet generaliserer både Fermat-problemet og Weber-problemet. Problemet blev formuleret og løst for en trekant i 1985 af Luc-Normand Tellier [6] . I 1992 fandt Chen, Hansen, Jomar og Tui en løsning på Tellier-problemet for polygoner med mere end tre sider.

Torricellis geometriske løsning af Fermats problem for en trekant

Evangelista Torricellis geometriske løsning af Fermats trekantproblem bygger på to observationer:

1. Punkt D har en optimal position, hvis en forskydning fra dette punkt fører til en stigning i den samlede afstand til punkterne A, B og C, hvilket betyder, at det optimale punkt kun er det punkt, hvor en uendelig forskydning mod en af ​​de tre point er lig med summen af ​​ændringerne til de to andre punkter. Med andre ord, punkt D er lige så tiltrukket af punkterne A, B og C.

2. I en konveks firkant indskrevet i en cirkel summer modsatte vinkler op til 180°. Vi kan formulere dette som følger: Hvis vi skærer cirklen med akkorden AB, får vi cirklens buer, f.eks. AiB og AjB. Enhver vinkel ∠AiB baseret på buen AiB er den samme for ethvert punkt i, og vinklen ∠AjB baseret på buen AjB er den samme for ethvert punkt j. Desuden summer vinklerne ∠AiB og ∠AjB op til 180°.

Det kan bevises, at det af den første observation følger, at ved det optimale punkt skal vinklerne ved trianglernes toppunkter baseret på segmenterne AD, BD og CD være lig med 360° / 3 = 120°. Ud fra dette konkluderede Torricelli, at:

1. Hvis trekant ABD, hvis vinkel ∠ADB er lig med 120°, danner en konveks firkant ABDE indskrevet i en cirkel, skal vinklen ∠AEB på trekanten ABE være lig med (180° − 120°)= 60°;

2. En måde at få et punkt D for, hvor vinklen ∠ADB er 120°, er at konstruere en ligesidet trekant ABE (da alle vinkler i en ligesidet trekant er 60°), hvor punktet E er uden for trekant ABC, og tegne en cirkel omkring denne trekant. Så er vinklen ∠AD'B for alle punkter D' i trekantens omskrevne cirkel, der ligger inde i trekanten, lig med 120°;

3. Det samme kan gøres for trekanter ACD og BCD;

4. Dette fører til konstruktionen af ​​ligesidede trekanter ACF og BCG, hvor F og G ligger uden for trekanten ABC, og også til konstruktionen af ​​to andre cirkler omkring disse ligesidede trekanter. Alle tre cirkler skærer hinanden i et punkt D og vinklerne baseret på segmenterne AD, BD og CD vil være lig med 120°, hvilket beviser punktets optimale position.

Simpsons geometriske løsning af Weber-trekantproblemet

Simpsons geometriske løsning på det såkaldte "Weber-trekantproblem" (som blev formuleret af Thomas Simpson i 1750) følger direkte af Torricellis løsning. Simpson og Weber understreger det faktum, at i transportminimeringsproblemet afhænger fordelen ved at nærme sig forbrugspunkter A, B eller C af, hvad der transporteres og til hvilken pris. Derfor bør fordelen ved at nærme sig nogle afstandsændringer og vinklerne ∠ADB, ∠ADC og ∠BDC ikke længere være 120°.

Simpson viste, at trekanter ABE, ACF og BCG, konstrueret på samme måde som Torricellis løsning, hvor E, F og G er uden for trekant ABC, skal være proportionale med tiltrækningskræfterne. I tilfælde af Fermats problem var trekanterne ligesidede, fordi tiltrækningskræfterne er de samme

Løsningen er:

1. I trekanten ABE under konstruktion er side AB proportional med tiltrækningskraften Cw mod C , side AE ​​er proportional med tiltrækningskraften Bw mod B , og side BE er proportional med tiltrækningskraften A w mod A.

2. I trekanten BCG under konstruktion er side BC proportional med tiltrækningskraften A w mod A, side BG er proportional med tiltrækningskraften B w mod B, og side CG er proportional med tiltrækningskraften C w mod C;

3. Det optimale punkt D er placeret i skæringspunktet mellem to cirkler omkring de konstruerede trekanter ABE og BCG.

En tredje trekant ACF, hvor F er uden for trekant ABC, kan bygges på siden AC og en tredje cirkel kan bygges omkring denne trekant. Denne tredje cirkel skærer de to andre cirkler i samme punkt D.

Telliers geometriske løsning af tiltrækning-frastødning-problemet

For problemet med tiltrækning - frastødning i tilfælde af en trekant, er der en geometrisk løsning. Det blev opdaget relativt nylig [7] . Denne geometriske løsning adskiller sig fra de to foregående, da trekanterne af kræfter, der bygges, i dette tilfælde er overlejret på placeringstrekanten for punkterne A 1 A 2 R (her er A 1 og A 2 tiltrækningspunkterne, og R er punktet af afvisning).

Løsningen er:

1. I trekanten RA 2 H under konstruktion, som er delvist overlejret på placeringstrekanten af ​​punkterne A 1 A 2 R, er siden RA 2 proportional med tiltrækningskraften A1 w mod A 1 , siden RH er proportional. til tiltrækningskraften A2 w mod A 2 , og side A 2 H er proportional med frastødningskraften Rw i retningen væk fra R.

2. I trekanten RA 1 I under opbygning, som er delvist overlejret på placeringstrekanten af ​​punkterne A 1 A 2 R, er siden RA 1 proportional med tiltrækningskraften A2 w i retning af A 2 , siden RI er proportional med tiltrækningskraften A1 w i retningen til A 1 , og side A 1 I er proportional med frastødningskraften R w i retningen væk fra R;

3. Det optimale punkt D er placeret i skæringspunktet mellem to cirkler, der er afgrænset omkring de konstruerede trekanter RA 2 H og RA 1 I. Løsningen opnås ikke, hvis en af ​​kræfterne er større end summen af ​​de to andre, eller hvis vinklerne ikke er sammenlignelige. I nogle tilfælde er der ingen overtrædelser ovenfor (ingen kraft er større end summen af ​​de to andre, og vinklerne er sammenlignelige), men den optimale løsning findes på punktet med den større tiltrækningskraft.

Den Tellier-trigonometriske løsning af Fermat- og Weber-problemerne

Mere end 332 år adskiller formuleringen af ​​Fermat-problemet for en trekant og opdagelsen af ​​en ikke-iterativ numerisk løsning, selvom en geometrisk løsning eksisterede i næsten hele tidsperioden. Dette forklares ved, at begyndelsen af ​​de tre vektorer rettet mod de tre tiltrækningspunkter måske ikke er sammenfaldende. Hvis de falder sammen og ligger i det optimale punkt P, danner vektorerne mod A, B og C og siderne af trekanten af ​​tiltrækningspunkter ABC de seks vinkler ∠1, ∠2, ∠3, ∠4, ∠5, og ∠6, og de tre vektorer danner vinklerne ∠α A , ∠α B og ∠α C . Det er nemt at skrive følgende seks ligheder, der relaterer seks ukendte (vinklerne ∠1, ∠2, ∠3, ∠4, ∠5 og ∠6) med seks kendte værdier (vinklerne ∠A, ∠B og ∠C er givet, og værdierne af vinklerne ∠α A , ∠α B og ∠α C afhænger kun af de relative værdier af de tre tiltrækningskræfter til punkterne A, B og C):

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

Desværre er dette system med seks ligninger ubestemt, og muligheden for, at tre vektorer begynder i retning af tiltrækningspunkterne, forklarer hvorfor. I tilfælde af mismatch er det let at se, at ligningerne forbliver sande. Den optimale position af punktet P forsvinder dog på grund af det trekantede "hul" inde i trekanten. Faktisk, som Tellier (1972) [2] har vist , har dette trekantede "hul" nøjagtig de samme proportioner som de "krafttrekanter", vi byggede i Simpsons geometriske løsning.

For at løse problemet skal vi tilføje en syvende ligning til disse seks ligninger, som skulle forhindre fremkomsten af ​​et trekantet "hul" i midten af ​​trekanten af ​​tiltrækningspunkter. Med andre ord skal begyndelsen af ​​vektorerne matche.

Løsningen af ​​Fermats og Webers Tellier-problemer for en trekant udføres i tre trin:

1. Bestem vinklerne ∠α A , ∠α B og ∠α C , ved hvilke de tre tiltrækningskræfter A w, B w og C w balancerer hinanden og giver balance. For at gøre dette bruger vi følgende ligheder:

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. Bestem værdien af ​​vinklen ∠3 (denne lighed sikrer sammenfaldet af punkterne D og E):

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

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

3. Vi løser et ligningssystem, hvor ∠3 allerede er kendt:

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

Telliers trigonometriske løsning af tiltrækning-frastødning-problemet

Tellier (1985) [6] udvidede Fermat-Weber-problemet til at omfatte frastødende kræfter. Overvej sagen for en trekant, hvor to tiltrækningskræfter A1 w og A2 w og en frastødende kraft R w virker. Her, som i det foregående tilfælde, er tilfældet med mismatch af begyndelsen af ​​tre vektorer muligt. Løsningen skal således kræve deres matchning. Telliers trigonometriske løsning på dette problem er som følger:

1. Bestem vinklen ∠e:

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

2. Bestem vinklen ∠p:

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

3. Bestem vinklen ∠c:

∠c = 180° − ∠p ;

4. Bestem vinklen ∠d:

∠d = ∠e − ∠c;

5. Bestem værdien af ​​vinklen ∠3 (denne ligning kræver sammenfald af punkterne D og E):

tan ∠3 = x/y;

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

6. Bestem vinklen ∠1:

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

7. Bestem vinklen ∠5:

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

8. Bestem vinklen ∠2:

∠2 = ∠a − ∠5.

Iterativ løsning af Fermat-, Weber- og tiltræknings-afstødningsproblemerne

Hvis antallet af kræfter er større end tre, bliver det umuligt at bestemme vinklerne uden at overveje geometrien af ​​tiltrækningspunktets polygon. Geometriske og trigonometriske metoder er magtesløse. I disse tilfælde anvendes iterative optimeringsmetoder. Kuhn og Kuen (1962) [1] foreslog en algoritme baseret på iterativ vægtede mindste kvadrater der generaliserer Weissfeld-algoritmen for det uvægtede problem . Deres metode virker for Fermat- og Weber-problemerne, som har mange kræfter, men ikke for tiltrækning-frastødning-problemet. I denne metode, for at finde en tilnærmelse til et punkt y , der minimerer den vægtede sum af afstande

en indledende løsning y 0 tages, og ved hvert trin nærmer algoritmen sig den optimale løsning ved at vælge y j  + 1 , hvilket minimerer den vægtede sum af afstande

,

hvor startvægtene w i er divideret med afstanden fra punktet til tilnærmelsen af ​​det foregående trin. Hver successiv tilnærmelse kan opnås som et vægtet gennemsnit af den eneste optimale vægtede mindste kvadraters løsning:

For tiltrækning-frastødning-problemet kan man henvise til algoritmen foreslået af Chen, Hansen, Jomar og Tui (1992) [8] .

Fortolkning af jordværditeorien i lyset af tiltrækning-frastødning-problemet

I rumøkonomiens verden er frastødende kræfter allestedsnærværende. Værdien af ​​jord er deres vigtigste illustration. Faktisk kan en væsentlig del af teorien om jordværdi , både på landet og i byerne, opsummeres som følger.

I det tilfælde, hvor alle er tiltrukket af et enkelt attraktionspunkt (landmarkedet eller det centrale forretningskvarter i en by), danner konkurrencen fra forskellige tilbudsgivere, der ønsker at være placeret i centrum, prisen på jord, hvilket transformerer tiltrækningspunktet. af systemet til et frastødningspunkt, bestemt af de høje omkostninger ved jord, og hver beboer og forretningsaktivitet er placeret på det punkt, hvor tiltræknings- og frastødningskræfterne ophæver.

Problemet med tiltrækning-frastødning og den nye økonomiske geografi

Ottavino og Thiess (2005) [9] betragter Tellier-problemet som en optakt til den "nye økonomiske geografi" (NEG) udviklet i 1990'erne, som Paul Krugman modtog Nobelprisen i økonomi for i 2008. Begrebet attraktive kræfter er relateret til begrebet agglomeration eller centripetale kræfter af NEG, og begrebet frastødende kræfter er relateret til begrebet spredning eller centrifugalkræfter.

Noter

  1. ↑ 1 2 Kuhn og Kuenne, 1962 , s. 21-34.
  2. ↑ 1 2 Tellier, 1972 , s. 215-233.
  3. ↑ Simpson, 1750 .
  4. ↑ Weber, 1922 .
  5. ↑ Kræfter, der ligner gravitations- eller elektriske kræfter, menes ikke her, da disse kræfter ikke afhænger af afstanden.
  6. ↑ 12 Tellier , 1985 .
  7. ↑ Tellier, 2013 .
  8. ↑ Chen, Hansen, Jaumard, Tuy, 1992 , s. 467-486.
  9. ↑ Ottaviano, Thisse, 2005 , s. 1707–1725

Litteratur

Links