Problema Weber

Problema Weber este una dintre cele mai cunoscute probleme legate de locația producției . Numit după economistul german Alfred Weber . Sarcina este de a găsi un punct în plan care minimizează suma prețurilor de transport din acest punct la n puncte de consum, unde diferitelor puncte de consum li se atribuie propriul preț de transport pe unitate de distanță.

Problema lui Weber generalizează căutarea medianei geometrice , pentru care se presupune că prețurile de transport sunt egale pentru toate punctele de consum, și problema găsirii punctului Fermat , mediana geometrică a trei puncte. Din acest motiv, problema se numește uneori problema Fermat-Weber, deși același nume este folosit și pentru găsirea medianei geometrice neponderate. Problema lui Weber, la rândul ei, este generalizată la problema atracție-repulsie, care permite prețuri negative, astfel încât pentru unele puncte este de preferat o distanță mai mare.

Definiția și istoria problemelor Fermat, Weber și atracție-repulsie

Sarcina fermei Problema Weber Sarcina atracției
- repulsie
Formulat Fermă (înainte de 1640) Simpson (1750) Tellier (1985)
Rezolvarea geometrică
a problemei triunghiului 		Torricelli (1645) Simpson (1750) Tellier (2013)
Rezolvarea numerică directă
a problemei triunghiului 		Tellier (1972) Tellier (1972) Tellier (1985)
Rezolvarea numerică iterativă
a problemei 		Kuhn și Kuen (1962) Kuhn și Kuen (1962) Chen, Hansen, Jomar și Tui (1992)

În cazul unui triunghi, problema lui Fermat este de a găsi un punct D față de trei puncte A, B și C astfel încât suma distanțelor de la D la fiecare dintre aceste trei puncte să fie minimă. Problema a fost formulată de celebrul matematician francez Pierre de Fermat înainte de 1640. Problema poate fi considerată drept adevăratul început al problemei locației producției. Torricelli a găsit o soluție geometrică a problemei în jurul anului 1645, dar nu a existat o soluție numerică directă pentru mai mult de 325 de ani. Kuhn și Kuen [1] au găsit o soluție iterativă la problema generală a lui Fermat în 1962, iar în 1972 Luc-Normand Tellier [2] a găsit o soluție numerică (trigonometrică) directă a problemei triunghiulare a lui Fermat. Soluția lui Kuhn și Kuen este valabilă pentru poligoane cu mai mult de trei laturi, ceea ce nu este cazul soluției lui Tellier din motivele explicate mai jos.

În cazul unui triunghi, sarcina lui Weber este să găsească un astfel de punct D în raport cu cele trei puncte A, B și C încât suma costurilor de transport de la punctul D la celelalte trei puncte să fie minimă. Problema Weber este o generalizare a problemei Fermat deoarece folosește forțe atractive egale și inegale (vezi mai jos), în timp ce în problema Fermat forțele sunt aceleași. Problema a fost formulată și rezolvată pentru cazul unui triunghi de Thomas Simpson în 1750 [3] [4] . Kuhn și Kuen au găsit o soluție iterativă în 1962, iar soluția lui Tellier, găsită în 1972, se aplică atât problemelor lui Weber, cât și problemelor lui Fermat. Soluția lui Kuhn și Kuen se aplică în cazul unui poligon cu mai mult de trei laturi.

În cel mai simplu caz, problema atracției-repulsiunii este de a găsi un astfel de punct D față de cele trei puncte A 1 , A 2 și R pe care să se aplice forțele de atracție aplicate ale punctelor A 1 și A 2 și forța de repulsie. a punctului R se compensează reciproc [5] . Problema generalizează atât problema Fermat, cât și problema Weber. Problema a fost formulată și rezolvată pentru un triunghi în 1985 de Luc-Normand Tellier [6] . În 1992, Chen, Hansen, Jomar și Tui au găsit o soluție la problema Tellier pentru poligoane cu mai mult de trei laturi.

Soluția geometrică a lui Torricelli a problemei lui Fermat pentru un triunghi

Soluția geometrică a lui Evangelista Torricelli a problemei triunghiului lui Fermat se bazează pe două observații:

1. Punctul D are o poziție optimă dacă orice deplasare din acest punct duce la o creștere a distanței totale până la punctele A, B și C, ceea ce înseamnă că punctul optim este doar punctul în care o deplasare infinitezimală către unul dintre cele trei puncte este egală cu suma modificărilor celorlalte două puncte. Cu alte cuvinte, punctul D este atras în mod egal de punctele A, B și C.

2. Într-un patrulater convex înscris într-un cerc, unghiurile opuse însumează 180°. Putem formula acest lucru după cum urmează: dacă tăiem cercul cu coarda AB, obținem arcele cercului, să zicem, AiB și AjB. Orice unghi ∠AiB bazat pe arcul AiB este același pentru orice punct i, iar unghiul ∠AjB bazat pe arcul AjB este același pentru orice punct j. În plus, unghiurile ∠AiB și ∠AjB se adună până la 180°.

Se poate demonstra că din prima observație rezultă că în punctul optim unghiurile de la vârfurile triunghiurilor bazate pe segmentele AD, BD și CD trebuie să fie egale cu 360° / 3 = 120°. Din aceasta, Torricelli a concluzionat că:

1. Dacă triunghiul ABD, al cărui unghi ∠ADB este egal cu 120°, formează un patrulater convex ABDE înscris într-un cerc, unghiul ∠AEB al triunghiului ABE trebuie să fie egal cu (180° − 120°)= 60°;

2. O modalitate de a obține un punct D pentru care unghiul ∠ADB este de 120° este de a construi un triunghi echilateral ABE (deoarece toate unghiurile unui triunghi echilateral sunt de 60°), unde punctul E este în afara triunghiului ABC și desenați un cerc în jurul acestui triunghi. Atunci pentru toate punctele D' ale cercului circumferitor al triunghiului aflate în interiorul triunghiului, unghiul ∠AD'B este egal cu 120°;

3. Același lucru se poate face și pentru triunghiurile ACD și BCD;

4. Aceasta duce la construirea triunghiurilor echilaterale ACF și BCG, unde F și G se află în afara triunghiului ABC și, de asemenea, la construirea altor două cercuri în jurul acestor triunghiuri echilaterale. Toate cele trei cercuri se intersectează într-un punct D iar unghiurile bazate pe segmentele AD, BD și CD vor fi egale cu 120°, ceea ce demonstrează poziția optimă a punctului.

Soluția geometrică a lui Simpson a problemei triunghiului Weber

Soluția geometrică a lui Simpson la așa-numita „problema triunghiului Weber” (care a fost formulată de Thomas Simpson în 1750) decurge direct din soluția lui Torricelli. Simpson și Weber subliniază faptul că, în problema minimizării transportului, beneficiul abordării punctelor de consum A, B sau C depinde de ceea ce este transportat și de ce costuri. Prin urmare, beneficiul abordării unor distanțe se modifică și unghiurile ∠ADB, ∠ADC și ∠BDC nu ar trebui să mai fie de 120°.

Simpson a arătat că triunghiurile ABE, ACF și BCG, construite în mod similar cu soluția lui Torricelli, unde E, F și G sunt în afara triunghiului ABC, trebuie să fie proporționale cu forțele de atracție. În cazul problemei lui Fermat, triunghiurile erau echilaterale deoarece forțele de atracție sunt aceleași

Solutia este:

1. În triunghiul ABE în construcție, latura AB este proporțională cu forța de atracție Cw spre C , latura AE este proporțională cu forța de atracție Bw spre B , iar latura BE este proporțională cu forța de atracție A w spre A.

2. În triunghiul BCG în construcție, latura BC este proporțională cu forța de atracție A w către A, latura BG este proporțională cu forța de atracție B w către B, iar latura CG este proporțională cu forța de atracție C w către C;

3. Punctul optim D este situat la intersecția a două cercuri în jurul triunghiurilor construite ABE și BCG.

Un al treilea triunghi ACF, unde F este în afara triunghiului ABC, poate fi construit pe latura AC și un al treilea cerc poate fi construit în jurul acestui triunghi. Acest al treilea cerc intersectează celelalte două cercuri în același punct D.

Soluția geometrică a lui Tellier a problemei atracție-repulsie

Pentru problema atracției - repulsie în cazul unui triunghi, există o soluție geometrică. A fost descoperit relativ recent [7] . Această soluție geometrică diferă de cele două anterioare, deoarece în acest caz triunghiurile de forțe care se construiesc sunt suprapuse triunghiului de plasare a punctelor A 1 A 2 R (aici A 1 și A 2 sunt punctele de atracție, iar R este punctul de respingere).

Solutia este:

1. În triunghiul RA 2 H în construcție, care se suprapune parțial triunghiului de plasare a punctelor A 1 A 2 R, latura RA 2 este proporțională cu forța de atracție A1 w spre A 1 , latura RH este proporțională cu forța de atracție A2 w spre A 2 , iar latura A 2 H este proporțională cu forța de respingere R w în direcția îndepărtată de R.

2. În triunghiul RA 1 I în construcție, care se suprapune parțial triunghiului de plasare a punctelor A 1 A 2 R, latura RA 1 este proporțională cu forța de atracție A2 w în direcția lui A 2 , latura RI este proporțională cu forța de atracție A1 w în direcția către A 1 , iar latura A 1 I este proporțională cu forța de respingere R w în direcția îndepărtată de R;

3. Punctul optim D este situat la intersecția a două cercuri circumscrise în jurul triunghiurilor construite RA 2 H și RA 1 I. Soluția nu se obține dacă una dintre forțe este mai mare decât suma celorlalte două sau dacă unghiurile nu sunt comparabile. În unele cazuri, nu există încălcări de mai sus (nicio forță nu este mai mare decât suma celorlalte două și unghiurile sunt comparabile), dar soluția optimă se găsește în punctul cu forța de atracție mai mare.

Soluția trigonometrică Tellier a problemelor Fermat și Weber

Mai mult de 332 de ani separă formularea problemei Fermat pentru un triunghi și descoperirea unei soluții numerice neiterative, deși o soluție geometrică a existat aproape toată perioada de timp. Acest lucru se explică prin faptul că începuturile celor trei vectori direcționați către cele trei puncte de atracție pot să nu coincidă. Dacă coincid și se află în punctul optim P, vectorii către A, B și C și laturile triunghiului punctelor de atracție ABC formează cele șase unghiuri ∠1, ∠2, ∠3, ∠4, ∠5 și ∠6, iar cei trei vectori formează unghiuri ∠α A , ∠α B și ∠α C . Este ușor să scrieți următoarele șase egalități care raportează șase necunoscute (unghiurile ∠1, ∠2, ∠3, ∠4, ∠5 și ∠6) cu șase valori cunoscute (unghiurile ∠A, ∠B și ∠C sunt date, iar valorile unghiurilor ∠α A , ∠α B și ∠α C depind doar de valorile relative ale celor trei forțe de atracție către punctele A, B și C):

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

Din păcate, acest sistem de șase ecuații este nedeterminat, iar posibilitatea ca trei vectori să înceapă în direcția punctelor de atracție explică de ce. În cazul unei nepotriviri, este ușor de observat că ecuațiile rămân adevărate. Totuși, poziția optimă a punctului P dispare din cauza „găurii” triunghiulare din interiorul triunghiului. De fapt, după cum a arătat Tellier (1972) [2] , această „găură” triunghiulară are exact aceleași proporții ca „triunghiurile de forță” pe care le-am construit în soluția geometrică a lui Simpson.

Pentru a rezolva problema, trebuie să adăugăm o a șaptea ecuație la aceste șase ecuații, care ar trebui să împiedice apariția unei „găuri” triunghiulare în centrul triunghiului punctelor de atracție. Cu alte cuvinte, începuturile vectorilor trebuie să se potrivească.

Rezolvarea problemelor Tellier ale lui Fermat și Weber pentru un triunghi se realizează în trei pași:

1. Să se determine unghiurile ∠α A , ∠α B și ∠α C , la care cele trei forțe de atracție A w, B w și C w se echilibrează reciproc, oferind echilibru. Pentru a face acest lucru, folosim următoarele egalități:

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. Determinați valoarea unghiului ∠3 (această egalitate asigură coincidența punctelor D și E):

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

unde k = (CB/CA) (sin ∠α B / sin ∠α A ) și k' = (∠A + ∠B + ∠α C ) − 180° ;

3. Rezolvăm un sistem de ecuații în care ∠3 este deja cunoscut:

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

Soluția trigonometrică a lui Tellier a problemei atracție-repulsie

Tellier (1985) [6] a extins problema Fermat-Weber la cazul forțelor de respingere. Luați în considerare cazul unui triunghi în care acționează două forțe de atracție A1 w și A2 w și o forță de respingere R w. Aici, ca și în cazul precedent, este posibil cazul nepotrivirii începuturilor a trei vectori. Astfel, soluția trebuie să necesite potrivirea lor. Soluția trigonometrică a acestei probleme a lui Tellier este următoarea:

1. Determinați unghiul ∠e:

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

2. Determinați unghiul ∠p:

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

3. Determinați unghiul ∠c:

∠c = 180° − ∠p ;

4. Determinați unghiul ∠d:

∠d = ∠e − ∠c ;

5. Determinați valoarea unghiului ∠3 (această ecuație necesită coincidența punctelor D și E):

tan ∠3 = x / y ;

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

6. Determinați unghiul ∠1:

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

7. Determinați unghiul ∠5:

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

8. Determinați unghiul ∠2:

∠2 = ∠a − ∠5 .

Rezolvarea iterativă a problemelor Fermat, Weber și atracție-repulsie

Dacă numărul de forțe este mai mare de trei, devine imposibil să se determine unghiurile fără a lua în considerare geometria poligonului punctului de atracție. Metodele geometrice și trigonometrice sunt neputincioase. În aceste cazuri, se folosesc metode de optimizare iterativă. Kuhn și Kuen (1962) [1] au propus un algoritm bazat pe cele mai mici pătrate ponderate iterative care generalizează algoritmul Weissfeld pentru problema neponderată . Metoda lor funcționează pentru problemele Fermat și Weber, care au multe forțe, dar nu și pentru problema atracție-repulsie. În această metodă, pentru a găsi o aproximare a unui punct y care minimizează suma ponderată a distanțelor

se ia o soluție inițială y 0 și la fiecare pas algoritmul se apropie de soluția optimă alegând y j  + 1 , minimizând suma ponderată a distanțelor

,

unde greutățile inițiale w i se împart la distanța de la punct până la aproximarea pasului precedent. Fiecare aproximare succesivă poate fi obținută ca medie ponderată a singurei soluții optime pentru cele mai mici pătrate ponderate:

Pentru problema atracție-repulsie, se poate face referire la algoritmul propus de Chen, Hansen, Jomar și Tui (1992) [8] .

Interpretarea teoriei valorii terenului în lumina problemei atracție-repulsie

În lumea economiei spațiale, forțele repulsive sunt omniprezente. Valoarea terenului este ilustrația lor principală. De fapt, o parte semnificativă a teoriei valorii terenului , atât rural cât și urban, poate fi rezumată după cum urmează.

În cazul în care toată lumea este atrasă de un singur punct de atracție (piața rurală sau cartierul central de afaceri al unui oraș), concurența diverșilor ofertanți care doresc să fie amplasați în centru formează prețul terenului, care transformă punctul de atracție. a sistemului într-un punct de respingere, determinat de costul ridicat al terenului, iar fiecare rezident și activitate de afaceri este situat în punctul în care forțele de atracție și repulsie se anulează.

Problema atracție-repulsie și noua geografie economică

Ottavino și Thiess (2005) [9] consideră problema Tellier ca un preludiu la „noua geografie economică” (NEG) dezvoltată în anii 1990, pentru care Paul Krugman a primit Premiul Nobel pentru Economie în 2008. Conceptul de forțe atractive este legat de conceptul de aglomerare sau forțe centripete ale NEG, iar conceptul de forțe de respingere este legat de conceptul de dispersie sau forțe centrifuge.

Note

  1. ↑ 1 2 Kuhn și Kuenne, 1962 , p. 21–34.
  2. ↑ 1 2 Tellier, 1972 , p. 215–233.
  3. ↑ Simpson, 1750 .
  4. ↑ Weber, 1922 .
  5. ↑ Forțele similare forțelor gravitaționale sau electrice nu sunt înțelese aici, deoarece aceste forțe nu depind de distanță.
  6. ↑ 12 Tellier , 1985 .
  7. ↑ Tellier, 2013 .
  8. ↑ Chen, Hansen, Jaumard, Tuy, 1992 , p. 467–486.
  9. ↑ Ottaviano, Thisse, 2005 , p. 1707–1725

Literatură

Link -uri