پارادوکس Braess

پارادوکس Braess این نظر را دارد که اضافه کردن یک یا چند جاده به یک شبکه جاده ای می تواند جریان کلی ترافیک را از طریق آن کند کند. پارادوکس در سال 1968 توسط ریاضیدان آلمانی، لازم دانسته شد دیتریش Braess ، که متوجه شدم که با اضافه کردن یک راه به یک خاص متراکم ترافیک شبکه جاده زمان کلی سفر را افزایش دهد.

پارادوكس ممكن است در شبكه هاي برق و سيستم هاي بيولوژيك شباهت داشته باشد. پیشنهاد شده است که در تئوری ، با از بین بردن قسمت های خاصی از آن ، بهبود یک شبکه ناقص عمل می کند. پارادوکس برای توضیح موارد بهبود گردش در هنگام بسته شدن جاده های اصلی اصلی استفاده شده است.

فهرست

کشف و تعریف [ ویرایش ]

دیتریش براس ، ریاضیدان دانشگاه روهر ، آلمان ، هنگام کار روی الگوی ترافیک ، متوجه اضافه شدن یک مسیر جدید در شبکه جاده ای شد . ایده او این بود که اگر هر راننده تصمیم بهینه خود را برای سرعت گرفتن سریع ترین مسیر اتخاذ کند ، میانبر اغلب می تواند برای رانندگان کمترین زمان سفر را انتخاب کند. به طور رسمی تر ، ایده ی کشف Braess این است که تعادل نش ممکن است با بهترین جریان کلی از طریق شبکه برابر نباشد. [1]

پارادوکس به شرح زیر است:

"برای هر نقطه از یک شبکه جاده ای ، اجازه دهید تعداد اتومبیل هایی که از آن شروع می شوند و مقصد خودروها باشد. در این شرایط فرد می خواهد توزیع جریان ترافیک را تخمین بزند. اینکه آیا یک خیابان نسبت به دیگری ارجح است بستگی ندارد. اگر فقط هر كدام از رانندگان مسیری را كه از نظر آنها مطلوب تر به نظر می رسد مسیریاب نكرد ، حداقل به كیفیت جاده برسد ، بلكه براساس چگالی جریان نیز می باشد . از شبکه راه ممکن است مجدداً توزیع ترافیک انجام شود که منجر به طولانی تر شدن زمان اجرای فرد می شود. "

افزودن ظرفیت اضافی به شبکه هنگامی که افراد در حال حرکت خودخواهانه مسیر خود را انتخاب کنند ، در برخی موارد می تواند عملکرد کلی را کاهش دهد. دلیلش این است که تعادل نش در چنین سیستم لزوماً بهینه نیست. تغییر شبکه ساختار جدیدی را ایجاد می کند که منجر به معضل زندانی (چند نفره) می شود . در تعادل نش ، رانندگان انگیزه ای برای تغییر مسیرهای خود ندارند. در حالی که سیستم در تعادل نش قرار ندارد ، رانندگان انفرادی می توانند با تغییر مسیری که طی می کنند ، زمان سفر خود را بهبود بخشند. در مورد پارادوکس Braess ، رانندگان با وجود کاهش در عملکرد کلی ، تعادل خود را تا رسیدن به تعادل نش ادامه خواهند داد.

اگر عملکردهای تأخیر خطی باشند ، اضافه کردن یک لبه هیچگاه نمی تواند کل عدد سفر را در حالت تعادل با عاملی بیش از 4/3 بدتر کند. [2]

موارد احتمالی پارادوکس در عمل [ ویرایش ]

شیوع [ ویرایش ]

در سال 1983 ، استینبرگ و زنگویل تحت فرضیات معقول ، شرایط لازم و کافی را فراهم کردند که پارادوکس Braess در یک شبکه حمل و نقل عمومی هنگام اضافه شدن یک مسیر جدید رخ دهد. (توجه داشته باشید که نتیجه آنها فقط در مورد اضافه کردن هر مسیر جدید ، نه فقط در مورد اضافه کردن یک لینک واحد اعمال می شود.) به عنوان نتیجه گیری ، آنها دریافتند که پارادوکس Braess تقریباً اتفاق می افتد که اتفاق نمی افتد. نتیجه آنها درمورد شبکه ها و برنامه های افزودنی تصادفی اعمال می شود. [3]

ترافیک [ ویرایش ]

همچنین مشاهده کنید: تقاضای القایی

پارادوكس Braess در صورت كاهش شبكه جاده (با كاهش زمان رفت و آمد فردي) ، يك همتاي دارد. [4]

در سئول ، کره جنوبی ، یک بالا بردن سرعت ترافیک در اطراف شهرستان دیده می شد هنگامی که یک بزرگراه به عنوان بخشی از برداشته شد Cheonggyecheon پروژه بازسازی. [5] در اشتوتگارت ، آلمان ، پس از سرمایه گذاری در شبکه راه در سال 1969 ، وضعیت ترافیک بهبود نیافت تا اینکه قسمتی از جاده تازه ساخته شده برای ترافیک دوباره بسته شد. [6] در سال 1990 بسته شدن موقتی خیابان 42 در نیویورک برای روز زمین ، میزان ازدحام در منطقه را کاهش داد. [7]در سال 2008 یون ، گاستنر و جئونگ مسیرهای مشخصی را در بوستون ، نیویورک سیتی و لندن به نمایش گذاشتند که در آن ممکن است واقع شود و به جاده هایی اشاره کرد که می توانند بسته شوند تا زمان سفر پیش بینی شده را کاهش دهند. [8] در سال 2009 ، نیویورک آزمایش بستن برادوی در میدان تایمز و میدان هرالد را تجربه کرد ، که منجر به بهبود جریان ترافیک و پلاک های دائمی پیاده رو شد. [9]

در سال 2012 ، پل لكروت ، از مؤسسه برنامه ریزی و توسعه Île-de-France ، نوشت: "علیرغم ترس های اولیه ، حذف جاده های اصلی باعث بدتر شدن شرایط ترافیك فراتر از تنظیم های شروع انتقال ترافیك محدود نمی شود. و زیر انتظارات " [4] وی همچنین خاطرنشان می کند که برخی سفرهای موتوری به وسایل نقلیه عمومی منتقل نمی شوند و به سادگی از بین می روند ("تبخیر"). [4]

همین پدیده همچنین مشاهده شد که بسته شدن جاده بخشی از یک پروژه شهری نبود بلکه پیامد یک تصادف بود. در سال 2012 در روون ، یک پل بر اثر تصادف سوزانده شد. در طی دو سال بعد ، از پلهای دیگر بیشتر استفاده شد ، اما از تعداد کل اتومبیل های عبور از پل ها کاسته شد. [4] به همین ترتیب ، در سال 2015 در ورشو ، یک پل بسته شد. مقامات شاهد افزایش استفاده از سایر جاده ها و وسایل نقلیه عمومی بودند ، اما نیمی از وسایل نقلیه معمولاً از روی پل عبور می کنند "ناپدید شدند" (52،000 از 105،000 روزانه). [4]

برق [ ویرایش ]

در سال 2012 ، دانشمندان موسسه پویا و خود سازمان ماکس پلانک از طریق مدل سازی محاسباتی ، پتانسیل بروز این پدیده را در شبکه های انتقال نیرو که تولید برق در آن غیرمتمرکز است ، نشان دادند. [10]

در سال 2012 ، یک تیم بین المللی از محققان موسسه نئل (CNRS ، فرانسه) ، INP (فرانسه) ، IEMN (CNRS ، فرانسه) و UCL (بلژیک) در Physical Review Letters [11] مقاله ای را منتشر کردند که نشان می دهد ممکن است پارادوکس Braess در مزوسکوپی سیستم های الکترونی. به طور خاص ، آنها نشان دادند كه اضافه كردن مسیری برای الکترونها در یك شبكه نانوسكوپی به طور غیرمترقبه باعث كاهش هدایت آن می شود. این هر دو توسط شبیه سازی و همچنین آزمایش در دمای پایین با استفاده از میکروسکوپ گیت روبشی نشان داده شده است .

زیست شناسی [ ویرایش ]

Adilson E. Motter و همکارانش نشان دادند كه نتایج پارادوكس برایس ممكن است اغلب در سیستمهای زیست شناختی و زیست محیطی رخ دهد. [12] Motter نشان می دهد که حذف بخشی از شبکه آشفته می تواند آن را نجات دهد. برای مدیریت منابع از شبکه های غذایی گونه های در معرض خطر ، که در آن انقراض بسیاری از گونه ها ممکن است به صورت متوالی دنبال شود ، حذف انتخابی یک گونه محکوم از شبکه می تواند در اصل نتیجه مثبتی از جلوگیری از یک سری از انقراض های بیشتر به همراه آورد. [13]

استراتژی ورزشی تیم [ ویرایش ]

پیشنهاد شده است که در بسکتبال ، تیمی می تواند به عنوان شبکه ای از فرصت های مسیری برای به ثمر رساندن یک سبد ، با بازده متفاوت برای هر مسیر ، دیده شود و یک بازیکن ستاره می تواند بازده کلی تیم را ، مشابه آن با ، کاهش دهد. میانبر است که مورد استفاده بیش از حد افزایش بار کلی برای سفر از طریق شبکه جاده است. یک راه حل پیشنهادی برای حداکثر کارایی در گلزنی این است که یک بازیکن ستاره می تواند با همان تعداد شوت به عنوان هم تیمی شلیک کند. با این حال ، این روش با شواهد آماری سخت پشتیبانی نمی شود ، همانطور که در مقاله اصلی ذکر شد. [14]

در فوتبال هلنیو هررا به نقل قول معروفش معروف است "با 10 [بازیکن] تیم ما بهتر از 11 بازی می کند".

رویکرد ریاضی [ ویرایش ]

مثال [ ویرایش ]

یک شبکه جاده ای را همانطور که در نمودار مجاور نشان داده شده است ، در نظر بگیرید که 4000 راننده مایل به مسافرت از نقطه شروع تا انتهای آن هستند. مدت زمان مسافرت در دقایقی در جاده Start-A تعداد مسافرانی است که تقسیم بر 100 و در Start-B 45 دقیقه ثابت (به طور مشابه با جاده های اطراف آنها) است. اگر جاده خراب وجود نداشته باشد (بنابراین شبکه ترافیک در کل 4 جاده دارد) ، زمان لازم برای رانندگی مسیر Start-A-End با $آ$ رانندگان خواهند بود $\ displaystyle {\ tfrac {a} 100}} + 45$ . زمان لازم برای رانندگی مسیر Start-B-End با $\ displaystyle \ tfrac {b} {100} + 45$ . همانطور که 4000 راننده وجود دارد ، واقعیت این است $\ displaystyle a + b = 4000$ می تواند مورد استفاده قرار گیرد برای استنباط این واقعیت است $\ displaystyle a = b = 2000$ وقتی سیستم در تعادل است. بنابراین ، هر مسیر طول می کشد ${\ tfrac {2000} 100}} + 45 = 65$ دقایق. اگر هر مسیری زمان کمتری ببرد ، تعادل نش نخواهد بود: یک راننده منطقی از مسیر طولانی تر به مسیر کوتاه تر سوئیچ می کند.

حال فرض کنید خط خراب AB جاده ای است که مدت زمان مسافرت بسیار کوتاه آن تقریباً 0 دقیقه است. فرض کنید که جاده باز شده است و یک راننده Start-AB-End را امتحان می کند. در کمال تعجب او متوجه می شود که زمان او فرا رسیده است $\ displaystyle {\ tfrac {2000} {100}} + {\ tfrac {2001} {100}} = 40.01$ دقیقه ، صرفه جویی تقریباً 25 دقیقه. به زودی تعداد بیشتری از 4000 راننده در این مسیر جدید تلاش می کنند. زمان لازم از 40.01 بالا می رود و صعود خود را ادامه می دهد. وقتی تعداد رانندگانی که مسیر جدید را امتحان می کنند به 2500 برسد ، با 1500 نفر همچنان در مسیر Start-B-End ، زمان آنها خواهد بود $\ displaystyle {\ tfrac {2500} 100}} + {\ tfrac {4000 {100}} = 65$ دقیقه ، که هیچ پیشرفتی در مسیر اصلی ندارد. در همین حال ، آن 1500 راننده کم شده اند $\ displaystyle 45 + {\ tfrac {4000 100} = 85$ دقیقه ، افزایش 20 دقیقه ای. آنها موظفند از طریق A نیز به مسیر جدید تغییر دهند ، بنابراین اکنون نیز طول می کشد ${\ tfrac {4000 100}} {+ {\ tfrac {4000 100}} = 80$ دقایق. هیچ کس مشکلی برای سفر A-End یا Start-B ندارد زیرا هر راننده ای که آنها را امتحان می کند 85 دقیقه طول می کشد. بنابراین ، باز شدن مسیر صلیب باعث تغییر غیرقابل برگشت برای آن توسط هر کس می شود و هزینه 80 دقیقه به جای 65 اصلی است. اگر هر راننده موافقت می کرد از مسیر AB استفاده نکند ، یا اگر این مسیر بسته بود ، هر راننده می شد. با کاهش 15 دقیقه‌ای در زمان سفر سود ببرید.

وجود تعادل [ ویرایش ]

اگر کسی زمان سفر را برای هر فردی که بر روی لبه رانندگی برابر است تصور کند ، یک تعادل همیشه وجود خواهد داشت.

اجازه دهید $L_ {e} (x)$ فرمول زمان سفر هرکس است که در امتداد لبه سفر می کند $ایکس$ مردم آن لبه را می گیرند فرض کنید نمودار ترافیکی وجود دارد $x_ {e$ رانندگی در امتداد لبه $ه$ . اجازه دهید انرژی $ه (ه)$ ، بودن

$\ sum _ {i = 1} ^ {x_ {e}} L_ {e} (i) = L_ {e} (1) + L_ {e} (2) + \ cdots + L_ {e} (x_ {e })$

(اگر $x_ {e} = 0$ اجازه دهید $E (e) = 0$ ) بگذارید کل انرژی نمودار ترافیک ، مجموع انرژی هر لبه در نمودار باشد.

مسیری را انتخاب کنید که انرژی کل را به حداقل برساند. چنین انتخابی باید وجود داشته باشد زیرا در نهایت بسیاری از مسیرها وجود دارد. این یک تعادل خواهد بود.

فرض کنید ، برای تضاد ، این مورد نیست. سپس حداقل یک راننده وجود دارد که می تواند مسیر را تغییر داده و زمان سفر را بهبود بخشد. فرض کنید مسیر اصلی است $e_ {0} ، e_ {1} ، \ ldots ، e_ {n$ در حالی که مسیر جدید است $e '_ {0}، e' _ {1}، \ ldots، e '_ {m}$ . اجازه دهید $ه$ انرژی کلی نمودار ترافیک را در نظر بگیرید و در نظر بگیرید که هنگام مسیر چه اتفاقی می افتد $e_ {0} ، e_ {1} ، ... e_ {n$ حذف شده است. انرژی هر لبه $e_ {i$ کاهش خواهد یافت $L_ {e_ {i}} (x_ {e_ {i}})$ و همینطور $ه$ کاهش خواهد یافت $\ sum _ {i = 0} ^ {n} L_ {e_ {i}} (x_ {e_ {i}})$ . این فقط کل زمان سفر مورد نیاز برای طی کردن مسیر اصلی است. اگر مسیر جدید اضافه شود ، $e '_ {0}، e' _ {1}، \ ldots، e '_ {m}$ ، کل انرژی $ه$ با کل زمان سفر مورد نیاز برای طی کردن مسیر جدید افزایش می یابد. از آنجا که مسیر جدید کوتاه تر از مسیر اصلی است ، $ه$ باید نسبت به پیکربندی اصلی کاهش یابد ، با این فرض که مجموعه اصلی مسیرها باعث کاهش کل انرژی می شوند.

بنابراین ، انتخاب مسیرهایی که انرژی کل را به حداقل می رسانند یک تعادل است.

یافتن تعادل [ ویرایش ]

اثبات فوق یک روال معروف به بهترین پویایی پاسخ را تشریح می کند ، که تعادل را برای نمودار ترافیک خطی پیدا می کند و در تعداد محدودی از مراحل خاتمه می یابد. این الگوریتم "بهترین پاسخ" نامیده می شود زیرا در هر مرحله از الگوریتم ، اگر نمودار در حالت تعادل قرار نگیرد ، برخی از درایورها بهترین راه حل را به استراتژی های سایر درایورهای دیگر نشان می دهند و به آن پاسخ سوئیچ می شوند.

Pseudocode برای بهترین پاسخ پویا:

بگذارید P الگوی ترافیکی باشد.
 در حالی که  P در تعادل نیست:
   محاسبه انرژی پتانسیل E از P 
   برای هر راننده د در P :
      برای هر مسیر جایگزین ص دسترس به د :
        محاسبه انرژی پتانسیل n از الگوی هنگامی که d مسیر p
         را می گیرد اگر  n < e :
          اصلاح P به طوری که د طول می کشد مسیر ص 
 ادامه بالاترین در حالی که

 Let P be some traffic pattern.
 while P is not at equilibrium:
   compute the potential energy e of P
   for each driver d in P:
     for each alternate path p available to d:
        compute the potential energy n of the pattern when d takes path p
        if n < e:
          modify P so that d takes path p
 continue the topmost while

در هر مرحله ، اگر برخی از رانندگان خاص می توانستند با طی کردن یک مسیر متناوب ("بهترین پاسخ") بهتر عمل کنند ، با انجام این کار به شدت انرژی نمودار کاهش می یابد. اگر هیچ راننده ای بهترین پاسخ را نداشته باشد ، نمودار در حال تعادل است. از آنجایی که انرژی هر نمودار با هر مرحله به شدت کاهش می یابد ، بهترین الگوریتم دینامیک پاسخ در نهایت باید متوقف شود.

ترافیک در تعادل چقدر از مطلوب فاصله دارد؟ [ ویرایش ]

اگر توابع زمان سفر خطی باشد ، یعنی $L_ {e} (x) = a_ {e} x + b_ {e$ برای برخی $a_ {e} ، b_ {e} \ geq 0$ پس از آن در بدترین حالت ، ترافیک در تعادل به حداقل رساندن انرژی دو برابر اقتصادی مطلوب است. [15]

اثبات: بگذارید Z پیکربندی شده ای با ترافیک باشد ، همراه با انرژی E ( Z ) و کل زمان سفر T ( Z ). برای هر لبه ، انرژی حاصل یک مقدار حسابی است و با استفاده از فرمول جمع حاصل از حسابی می توان نشان داد که E ( Z ) ≤ T ( Z ) E 2 E ( Z ) است. اگر $Z_ {o}$ جریان ترافیکی بهینه اجتماعی و $Z_ {e$ جریان ترافیک با کمترین انرژی است ، نابرابری حاکی از آن است $T (Z_ {e}) \ leq 2E (Z_ {e}) \ leq 2E (Z_ {o}) \ leq 2T (Z_ {o})$ .

بنابراین ، کل زمان سفر برای تعادل کمینه انرژی حداکثر دو برابر جریان بهینه است.

تجزیه و تحلیل دینامیکی پارادوکس Braess [ ویرایش ]

در سال 2013 ، دال فرونو و مرلون [16] پارادوكس براس را به عنوان یك مسئله انتخاب پویا انتخاب می كنند. تجزیه و تحلیل نشان می دهد که چگونه مسیر جدید مسئله را تغییر می دهد. قبل از دستیابی به مسیر جدید ، پویایی همانند گزینه های باینری با موارد بیرونی است ، اما مسیر جدید آن را به یک مسئله انتخاب سه گانه تبدیل می کند. افزودن یک منبع اضافی پیچیدگی دینامیک را غنی می کند. در حقیقت ، حتی می توانید همزیستی چرخه ها وجود داشته باشد و دلالت پارادوکس بر پویایی را هم از منظر هندسی و هم از دیدگاه تحلیلی می توان دید.

همچنین مشاهده کنید [ ویرایش ]

ناهنجاری بیلیدی است
انتخاب مسیر
پارادوکس داونز - تامسون
پارادوکس جونز
ثابت مارچتی
تقاضای القایی
موقعیت لوئیس - موگرج
قانون هوتلینگ
پارادوکس غنی سازی : افزایش مواد غذایی موجود در اکوسیستم ممکن است بی ثباتی پویا ایجاد کند و حتی منجر به انقراض شود.
موج ترافیک
پارادوکس تقسیم
جان گلن وردروپ
اثر هیدرا
موش دویدن
رژیم غذایی
بوفلوبات

منبع

https://en.wikipedia.org/wiki/Braess%27s_paradox

+ نوشته شده در شنبه بیست و سوم فروردین ۱۳۹۹ ساعت 12:1 توسط علی رضا نقش |

کامپیوتر و ریاضی با علی رضا نقش

آموزش