تاریخچه GAMS

اصالت GAMS

تحقیق و توسعه اولیه GAMS توسط بانک بین المللی بازسازی و توسعه، که معمولاً به آن بانک جهانی می گویند، تأمین مالی شد. از سال ۱۹۸۷، تحقیقات و توسعه بیشتر توسط شرکت توسعه GAMS تامین مالی شده است. GAMS با همکاری نزدیک اقتصاددانان ریاضی که گروه مهمی از کاربران GAMS بودند و هنوز هم هستند، ایجاد شد. هم افزایی بین اقتصاد، علوم کامپیوتر و تحقیق در عملیات مهمترین عامل موفقیت در توسعه سیستم بود. برنامه نویسی ریاضی و نظریه اقتصاد از نزدیک در هم تنیده شده اند. جایزه نوبل اقتصاد که در سال ۱۹۷۵ به لئونید کانتوروویچ و تجلینگ کوپمنز برای “مشارکت آنها در تئوری تخصیص بهینه منابع” اعطا شد، واقعاً جایزه ای در برنامه ریزی ریاضی بود. دیگر برندگان جایزه نوبل مانند کنت ارو در سال ۱۹۷۲، واسیلی لئونتیف در سال ۱۹۷۳ و هری مارکوویتز در سال ۱۹۹۰ نام های شناخته شده ای در برنامه نویسی ریاضی هستند. یکی دیگر از نمونه های اولیه این هم افزایی، استفاده از LP در عملیات پالایش است که توسط آلن مان، اقتصاددان، با کتاب برنامه ریزی عملیات پالایشگاه نفت در سال ۱۹۵۶ آغاز شد.

منشا الگوریتم های برنامه ریزی خطی همگی به کارهای اولیه جورج دانتسیگ در دهه های ۱۹۴۰ و ۱۹۵۰ برمی گردد. فناوری محاسبات و نظریه الگوریتمی با سرعتی سریع توسعه یافته بود. سی سال بعد، می‌توانیم مسائلی با اندازه و پیچیدگی عملی را حل کنیم که به ما اجازه می‌دهد تئوری اقتصادی را روی مسائل زندگی واقعی آزمایش کنیم. دستور کار تحقیقاتی بانک جهانی در دهه‌های ۱۹۷۰ و ۱۹۸۰، محیط مناسبی را برای گرد هم آوردن رشته‌های مختلف برای بکارگیری برنامه‌ریزی ریاضی در تحقیقات و سؤالات عملیاتی در توسعه اقتصادی ایجاد کرد.

پیشینه و انگیزه

از همان ابتدا، نیروی محرکه توسعه سیستم مدل‌سازی جبری عمومی (GAMS) کاربران برنامه‌نویسی ریاضی بوده‌اند که به بهینه‌سازی به عنوان چارچوبی قدرتمند و ظریف برای حل مسائل زندگی واقعی در علوم و مهندسی اعتقاد داشتند. در عین حال، این کاربران از هزینه بالا، نیازهای مهارت و قابلیت اطمینان پایین استفاده از ابزارهای بهینه سازی ناامید بودند. بیشتر ابتکارات و حمایت های ما برای توسعه جدید از دنیای اقتصاد، مالی و مهندسی شیمی بود. این رشته ها دیدن و درک جهان و رفتار آن را به عنوان یک برنامه ریاضی طبیعی می دانند.

انگیزه GAMS برای توسعه ناشی از تجربیات ناامیدکننده یک گروه بزرگ مدلسازی اقتصادی در بانک جهانی است. در گذشته، می توان آن را یک حادثه تاریخی نامید که در دهه ۱۹۷۰، اقتصاددانان و آماردانان ریاضی برای رسیدگی به مشکلات توسعه گرد هم آمدند. آنها از بهترین تکنیک‌های موجود در آن زمان برای حل مدل‌های اقتصاد چندبخشی و مدل‌های شبیه‌سازی و بهینه‌سازی بزرگ در کشاورزی، فولاد، کود، نیرو، مصرف آب و سایر بخش‌ها استفاده کردند. اگرچه این گروه تحقیقات قابل توجهی انجام داد، اما بازتولید موفقیت های اولیه در خارج از محیط تحقیقاتی که به خوبی کار می کرد دشوار بود. تکنیک‌های موجود برای ساخت، دستکاری، و حل چنین مدل‌هایی نیازمند چندین ترجمه دستی، زمان‌بر و مستعد خطا به نمایش‌های مختلف و خاص مسئله مورد نیاز هر روش راه‌حل است. در طول ارائه سمینار، مدل‌سازان مجبور بودند از نسخه‌های موجود مدل‌های خود دفاع کنند، گاهی اوقات کاملاً غیرمنطقی، زیرا زمان و هزینه لازم برای ایجاد تغییرات پیشنهادی بسیار زیاد بود. مدل‌های آنها را نمی‌توان به محیط‌های دیگر منتقل کرد، زیرا دانش برنامه‌نویسی خاصی مورد نیاز بود و قالب‌های داده و روش‌های راه‌حل قابل حمل نبود.

ایده یک رویکرد جبری برای نمایش، دستکاری و حل مدل‌های ریاضی در مقیاس بزرگ، پارادایم‌های قدیمی و جدید را در یک سیستم ثابت و قابل محاسبه محاسباتی در هم آمیخت. استفاده از مولدهای ماتریس (به ضمیمه GAMS در مقابل مولدهای ماتریس فرترن مراجعه کنید) برای برنامه های خطی، اهمیت نامگذاری سطرها و ستون ها را به شیوه ای ثابت به ما آموخت. ارتباط با مدل داده های رابطه ای در حال ظهور آشکار شد. تجربه دردناک استفاده از زبان‌های برنامه‌نویسی سنتی برای مدیریت آن فضاهای نام طبیعتاً باعث می‌شود که فرد به مجموعه‌ها و تاپل‌ها فکر کند و این منجر به مدل داده‌های رابطه‌ای شد. ترکیب نماد جبری چند بعدی با مدل داده های رابطه ای پاسخ واضح بود. تکنیک های نوشتن کامپایلر در حال حاضر گسترده شده بود و زبان هایی مانند GAMS می توانستند نسبتاً سریع پیاده سازی شوند. با این حال، ترجمه این نمایش ریاضی دقیق به قالب خاص الگوریتم نیاز به محاسبه مشتقات جزئی در سیستم‌های بسیار بزرگ داشت. در دهه ۱۹۷۰، TRW سیستمی به نام PROSE توسعه داد که از ایده‌های مهندسان شیمی استفاده می‌کرد تا مشتقات نقطه‌ای را که مشتقات دقیقی در یک نقطه معین هستند محاسبه کند و آنها را در یک زبان مدل‌سازی حساب دیفرانسیل و انتگرال ثابت و به سبک فرترن جاسازی کند. سیستم به دست آمده به کاربر اجازه می داد تا از مشتقات دقیق مرتبه اول و دوم به طور خودکار تولید شده استفاده کند. این یک سیستم پیشگام و نمایش مهم یک مفهوم بود. با این حال، به نظر ما PROSE دارای کاستی هایی بود: نمی توانست سیستم های بزرگ را مدیریت کند، نمایش مشکل به یک ساختار داده از نوع آرایه گره خورده بود که به محاسبات آدرس نیاز داشت، و سیستم دسترسی به پیشرفته ترین ها را فراهم نمی کرد. روش های حل از برنامه نویسی خطی، متوجه شدیم که بهره برداری از پراکندگی کلید حل مشکلات بزرگ است. بنابراین، آخرین قطعه پازل استفاده از ساختارهای داده پراکنده بود.

با در نظر گرفتن همه قطعات، تنها کاری که باید انجام می‌دادیم این بود که تکنیک‌هایی را به کار می‌گرفتیم تا در یک چارچوب منسجم قرار بگیرند و برای مشکلات بزرگ کار کنند.

اهداف طراحی و تغییر تمرکز

هدف اصلی و همچنان معتبر بهبود بهره‌وری سازنده مدل، کاهش هزینه‌ها و بهبود قابلیت اطمینان و اعتبار کلی فرآیند مدل‌سازی است. برای دستیابی به این هدف، ما اصول کلیدی زیر را برای هدایت توسعه GAMS ایجاد کردیم:

• نمایش مسئله مستقل از روش حل است.
• نمایش داده ها از مدل داده های رابطه ای پیروی می کند.
• مشکل و نمایش داده ها مستقل از پلتفرم های محاسباتی هستند.
• مشکل و نمایش داده ها مستقل از رابط های کاربر هستند.

روش‌های بهینه‌سازی با شکست مواجه خواهند شد و سیستم‌ها باید به گونه‌ای طراحی شوند که ایمن باشند.

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

نمایش مدل در GAMS به شکلی است که توسط انسان و ماشین به راحتی قابل خواندن است. این به این معنی است که برنامه GAMS خود مستندات مدل است و توضیحات جداگانه مورد نیاز در گذشته (که برای نگهداری بار سنگینی بود و به ندرت به روز می شد) دیگر مورد نیاز نیست. علاوه بر این، طراحی GAMS دارای ویژگی های زیر است که به طور خاص نیازهای مستندسازی کاربر را برطرف می کند:

نمایش مدل GAMS مختصر است و از ظرافت نمایش ریاضی به طور کامل استفاده می کند.

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

متن توضیحی می تواند بخشی از تعریف همه نمادها باشد و هر زمان که مقادیر مرتبط نمایش داده شود، بازتولید می شود.

تمام اطلاعات مورد نیاز برای درک مدل در یک سند است.

البته برای استفاده کامل از این ویژگی‌های طراحی به نظم و انضباط نیاز است، اما هدف این است که مدل‌ها را در دسترس‌تر، قابل درک‌تر، تأییدپذیرتر و در نتیجه معتبرتر کنیم.

آموزنده است که توسعه سیستم های مدل سازی را در یک چشم انداز تاریخی قرار دهیم و ببینیم که چگونه تمرکز و محدودیت های فنی در ۳۰ سال گذشته تغییر کرده است. ما می توانیم سه مرحله اصلی را مشاهده کنیم که تأکید را از مسائل محاسباتی به مسائل مدل سازی و در نهایت کاربرد یا مشکلات واقعی تغییر می دهد. هر فاز یکی از لایه های اصلی سیستم را که در بالا مورد بحث قرار گرفت، تعریف کرد. محدودیت‌های غالب در فاز اول، محدودیت‌های محاسباتی الگوریتم‌های ما بود. نمایش مشکل باید از راحتی الگوریتمی پیروی می کرد، گروه های متخصص متمرکز پروژه های بزرگ، گران قیمت و طولانی مدت را مدیریت کردند و کاربران نهایی به طور موثر کنار گذاشته شدند. فاز دوم مدل را در کانون توجه قرار داده است. برنامه‌ها با مهارت مدل‌سازی محدود می‌شوند، گروه‌های پروژه بسیار کوچک‌تر و غیرمتمرکز هستند، هزینه‌های محاسباتی پایین هستند و کاربران در طراحی برنامه مشارکت دارند. برنامه ها به گونه ای طراحی شده اند که مستقل از پلتفرم های محاسباتی باشند و اغلب در یک محیط سرویس گیرنده-سرور کار کنند.

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