ⓘ برنامه‌ریزی هندسی در سال ۱۹۶۷ توسط دافین، پترسون و زنر معرفی گردید. برنامه‌ریزی هندسی روشی کارآمد برای برخی از مسائل برنامه‌ریزی غیرخطی بوده و زیر مجموعه‌ای از ..

                                     

ⓘ برنامه‌ریزی هندسی

برنامه‌ریزی هندسی در سال ۱۹۶۷ توسط دافین، پترسون و زنر معرفی گردید. برنامه‌ریزی هندسی روشی کارآمد برای برخی از مسائل برنامه‌ریزی غیرخطی بوده و زیر مجموعه‌ای از مسائل سیگنومیال است. به کمک برنامه‌ریزی هندسی می‌توان مسائل کاربردی و در مقیاس بزرگ را به مدل بهینه‌سازی ریاضی تبدیل کرده و حل نمود. از کاربردهای GP می‌توان به طراحی مدارهای الکتریکی، مسائل مالی و آماری اشاره نمود.

                                     

1. نحوهٔ فرمول‌بندی

فرم استاندار

مسائل برنامه‌ریزی هندسی متشکل از تابع هدف پوزینومیال، قیود نامساوی پوزینومیال و قیود تساوی مونومیال هستند.

مونومیال به شکل زیر تعریف می‌شود:

پوزینومیال مجموع K جملهٔ مونومیال است:

شکل استاندارد یک مسأله‌ی برنامه‌ریزی هندسی به صورت زیر است:

x i {\displaystyle x_{i}} پارامتر بهینه‌سازی است. در بسیاری از موارد، برنامه‌ریزی هندسی می‌بایست به فرم استاندارد تبدیل شود. در صورتی که مسأله یک مسأله‌ی بیشینه‌سازی باشد می‌توان با معکوس کردن آن، مسأله را به یک مسأله‌ی کمینه‌سازی تبدیل نمود.

                                     

2.1. راهکارهای حل شدنی بودن

برای حل یک مسأله‌ی برنامه‌ریزی هندسی، مسأله می‌بایست شدنی باشد. در صورتی که مسأله شدنی نباشد، برای آن پاسخ بهینه وجود ندارد. در این موارد می‌توان حداقل یکی از قیود را ریلکس نمود. به منظور ریلکس سازی می‌توان یک متغیر اسکالر جدید s به منظور یافتن یک مقدار x ^ {\displaystyle {\hat {x}}} که نزدیک به شدنی است، اضافه نمود. برنامه‌ریزی هندسی به صورت زیر خواهد بود:

با حل مسأله‌ی بالا مقادیر بهینهٔ x ¯ {\displaystyle {\bar {x}}} و s ¯ {\displaystyle {\bar {s}}} بدست می‌آید. s ¯ {\displaystyle {\bar {s}}} بیانگر این است که مسأله‌ی اصلی برنامه‌ریزی هندسی چگونه شدنی است. به طور مثال در صورتی که s ¯ = 1 {\displaystyle {\bar {s}}=1} باشد، x ¯ {\displaystyle {\bar {x}}} برای مسأله اصلی برنامه‌ریزی هندسی شدنی است. در صورتی که s > 1 {\displaystyle s> 1} باشد، x ¯ = x ^ {\displaystyle {\bar {x}}={\hat {x}}} قرار داده می‌شود. روشی دیگر برای بررسی مسائل برنامه‌ریزی هندسی می‌توان با تغییر قیود، تأثیر آن‌ها را بر روی پاسخ بهینه بررسی نمود. این روش به شکل زیر مدل سازی می‌شود:

در مدل بالا به جای قیود نامساوی و مساوی با یک، پارامترهای u {\displaystyle u} و v {\displaystyle v} قرار داده شده است. در صورتی که u بزرگ‌تر از یک باشد، قید نامساوی آزادتر، و در صورتی که کوچکتر از یک باشد، قید نامساوی محکم تر است. با قرار دادن مقادیر مختلف u و v می‌توان تأثیر این مقادیر را بر پاسخ بهینه بررسی کرد.

                                     

2.2. راهکارهای حل شکل محدب

مسائل برنامه‌ریزی هندسی به طور کلی جزو مسائل بهینه‌سازی محدب نیستند، اما می‌توان این مسائل را با تغییر متغیر x i = l o g y i {\displaystyle x_{i}=logy_{i}} و b = l o g C {\displaystyle b=logC} به مسائل بهینه‌سازی محدب تبدیل نمود. در این صورت قیود مونومیال به شکل زیر خواهند بود:

به طور مشابه قیود پوزینومیال نیز به شکل زیر خواهند بود:

با جایگذاری عبارات بدست آمده در مسأله‌ی برنامه‌ریزی هندسی، شکل مسأله به صورت زیر خواهد شد:

با توجه به این که لگاریتم یک تابع صعودی است، لگاریتم گرفتن از توابع هدف و قیود سبب تغییر نقطه‌ی بهینه مسأله نخواهد نشد؛ بنابراین با لگاریتم گرفتن از توابع هدف و قیود مسأله‌ی معادل زیر بدست خواهد آمد:

مسأله‌ی بدست آمده یک مسأله‌ی محدب است.

                                     

3. کاربردها

  • مسائل موازنه‌ی شیمی
  • بیشینه‌سازی آنتروپی
  • طراحی فرایند جداسازی پوسته
  • مهندسی
  • بهینه‌سازی سیستم‌های اتمی
  • مدل فهرست اموال در علم مدیریت
  • بیشینه‌سازی قابلیت اطمینان
  • طراحی حمل و نقل
  • سایر حوزه‌ها
                                     
  • مدل سازی هندسی انگلیسی: Geometric modeling شاخه ای از ریاضیات کاربردی و هندسه محاسباتی است که روش ها و الگوریتم های لازم برای توصیف ریاضی اشکال مختلف
  • برنامه ریزی خطی یا همان بهینه سازی خطی روشی در ریاضیات است که به پیدا کردن مقدار کمینه یا بیشینه از یک تابع خطی روی یک چندضلعی محدب می پردازد. این چندضلعی
  • حسینعلی خان مهندس گوران یا حسینعلی خان هندسی گوران در کرمانشاه - مرداد در مهندس معمار دانش آموختۀ دارالفنون و بنیانگذار آموزش و پرورش
  • روباتیک برنامه ریزی حرکتی سیستم های اطلاعات جغرافیایی جستجو و مکان یابی هندسی نقشه کشی راه ها طراحی مدار مجتمع طراحی و بازبینی هندسی مدارهای مجتمع
  • برخورد موقعیت هندسی ربات با محیط را بررسی می کند. فضای هدف یک زیر فضا از فضای آزاد است که ما می خواهیم ربات به آن جا برود. در برنامه ریزی حرکت جهانی عمومی
  • داخل یک مخروط مرتبه دوم تعریف می شوند. این نوع برنامه ریزی در حل مسائل هندسی کاربرد دارد و همچنین در برنامه ریزیهای خطی که داده ها با خطا همراه هستند و به طور
  • می کند. یکی از مشخصه های فراقلم این است که شکل های حروف به وسیله معادله های هندسی تعریف می شوند. برخلاف طرح های رایج فرمت های قلم از قبیل ttf و نوع پست اسکریپت
  • این مدرسه در اواخر مهر سال خورشیدی میلادی توسط حسینعلی خان هندسی گوران تأسیس شد. همچنین تاریخ تأسیس این مدرسه قمری خورشیدی و
  • المان تا چهار بعد با خود دارد: سه بعد هندسی و یک بعد اطلاعات. اما در ادامه با استفاده از نرم افزارهای مناسب برنامه زمانبندی به این مدل لینک می شود به نحوی
  • تأکید بر وفاداری فیزیکی از مناطق مرتبط مدل سازی هندسی و گرافیک رایانه ای متمایز می شود. اصول مدل سازی هندسی و جامد پایه و اساس طراحی سه بعدی - رایانه ای
  • نظم هندسی که در فرم اجزای معماریو درون بناها و فضاهایشان جریان دارد جای خود را به نظمی فضایی در ابعاد مختلف می دهد.ممکن است این نظم از نظر هندسی نا منظم