پس از انقلاب صنعتی، بسیاری از قدرت‌های بزرگ سرنوشتی ایجابی از دو جنس بهره‌برداری بهینه از منابع مشترک و بلافاصله به حداکثر رسانیدن سود اقتصادی را برای خود رقم زدند. این صور از ایده‌آل گرایی محض اهداف متضادی را نیز در برداشت: جنگ و رفاه. تاریخچه‌ی رسمی تحقیق در عملیات و اولین جرقه‌های بهره‌برداری از […]
محمد نمک شناس/ دانشجوی دکتری مهندسی صنایع
اختصاصی اخبار مهندسی صنایع ایران
پس از انقلاب صنعتی، بسیاری از قدرت‌های بزرگ سرنوشتی ایجابی از دو جنس بهره‌برداری بهینه از منابع مشترک و بلافاصله به حداکثر رسانیدن سود اقتصادی را برای خود رقم زدند. این صور از ایده‌آل گرایی محض اهداف متضادی را نیز در برداشت: جنگ و رفاه. تاریخچه‌ی رسمی تحقیق در عملیات و اولین جرقه‌های بهره‌برداری از این علم، به اواخر سالهای ۱۹۳۰ الی ۱۹۴۰ برمی‌گردد؛ دقیقا زمانی که امپراتوری بریتانیا برای جنگ جهانی دوم آماده می‌شد. از طرفی طراحی و توسعه‌ی فناوری‌های نظامی (مانند رادارها) منجر به پیدایش انواع متعددی از مسایل سازمانی و مدیریتی در این برهه از زمان شد [۱]. در بهبوهه‌ی این نبرد تاریخ‌ساز بود که اولین نظریات بنیادی تحقیق در عملیات شکل گرفتند. پاتریک مینارد، فیزیکدان نظری امپراتوری بریتانیا، جزو اولین محققانی بود که علم تحقیق در عملیات را معرفی و به عنوان طراح استراتژی‌های نظامی از این علم بهره جست. ریاضیدان پرآوازه روس‌تبار، لئونید کانتروویچ، در سال ۱۹۳۹ برنامه‌ریزی خطی را جهت سازماندهی عملیات نظامی، کاهش هزینه‌های حاصل از جنگ و افزایش تلفات دشمن مطرح کرد. نکته‌ی قابل تامل در این است که برنامه‌ریزی خطی به بهانه‌ی حفظ اسرار جنگی تا سال ۱۹۴۷ از محافل علمی پنهان نگاه داشته شد و اغلب مورد استعمال سیاست‌های ضدبشری قرار می‌گرفت.
دانشمندان و محققان آن دوران بر این واقف بودند که توان تصمیم‌گیری برای عملیاتی با ابعاد بالا و امکانات متعدد بر مبنای یک مدل برنامه‌ریزی خطی را نخواهند داشت، چرا که آزمایش تمامی حالت‌های ممکن برای حل یک مدل خطی به زمان غیر قابل تصوری نیاز داشت. دقیقا در سال ۱۹۴۷ بود که جرج دانتزیگ، ریاضیدان مشهور آمریکایی و مسئول عملیات محاسباتی در نیروی هوایی ایالات متحده، الگوریتم سیمپلکس را جهت سرعت بخشی به حل مدل‌های خطی ارائه داد. به ذغم بسیاری از محققین تحقیق در عملیات، توسعه‌ی روش سیمپلکس مهم‌ترین دستاورد این علم تاکنون بوده است [۲]. تنها مزیت نسبی روش سیمپلکس، بررسی بخشی از حالات ممکن (نقاط گوشه‌ای) تا حد ممکن بود. از طرفی، درون‌مایه‌ی بنیادی‌ترین نظریات رایانشی و الگوریتم (همراه همیشگی علم تحقیق در عملیات) توسط آلن تورینگ و ریچارد نیومن، ریاضی‌دانان برجسته‌ی امپراطوری بریتانیا، در همان سالهای قوت‌گیری جنگ جهانی دوم در حال شکل‌گیری بود.
پس از فروکش کردن جنگ، علم تحقیق در عملیات در امپراطوری بریتانیا از حوزه‌ی نظامی به بخش‌های صنعتی گزار نرمی صورت داد. در آن دوران، این علم اغلب در صنایع ملی و بخصوص صنایع سنگین مانند صنعت فولاد بخدمت گرفته شد. این روند نیز با مشکل عمده‌ای روبرو بود که با افزایش سطح رفاه، مکانیزاسیون بخش‌های صنعتی، افزایش سطح فناوری و یکپارچه سازی عملیات، الگوریتم‌های سنتی ارائه شده در شرایط جنگی قادر به حل مدل‌های ریاضی توسعه‌یافته در قالب برنامه‌ریزی خطی نبودند. روشهای توسعه‌یافته مبتنی بر الگوریتم سیمپلکس، ارتباط تنگاتنگی با محاسبه‌ی معکوس ماتریس ضرایب فنی حاصل از یک مدل برنامه‌ریزی خطی داشتند؛ لذا پردازنده‌های دوران پس از جنگ توان پردازش این دسته از مسایل را نداشتند. اثبات شده است که روش سیمپلکس در برخی شرایط، از زمان حل با درجه‌ی نمایی تبعیت می کند [۳]. از طرفی کاربرد مدل‌های خطی در مواجهه با مسایل دارای فضای گسسته و بهینه‌سازی ترکیباتی به تدریج از رونق افتاد. در سالهای ۱۹۵۹ و ۱۹۶۰، هاروی واگنر و آلن منن اولین مدل‌های برنامه‌ریزی عدد صحیح را جهت زمان‌بندی مسایل تک ماشینه و تولید کارگاهی طی یک مقاله‌ی علمی ارائه دادند [۴]. اولین ظهور متغیرهای صفرویک و مسایل بهینه‌سازی ترکیباتی نیز در راستای همین مطالعات بوقوع پیوست. سلسله‌ی این رقابت‌‌ها جهت ارائه‌ی روشی موثر برای حل مدل‌های خطی، منجر به توسعه‌ی چند الگوریتم تاثیرگذار شد. الگوریتم نقطه‌ی داخلی، یکی از این راهکارها بود که ایده‌ی اولیه‌ی آن توسط جان نیومن ارائه شد و در سال ۱۹۸۴ توسط نراندرا کارمارکار توسعه داده شد. این روش به الگوریتم کارمارکار مشهور بوده و در مواجهه با مسایل با ابعاد بالا کارایی بسیار خوبی از خود به نمایش می‌گذارد.
اهم راهکارهای ارائه شده جهت واکاوی مسایل بهینه‌سازی ترکیباتی، در اصل یک الگوریتم بودند؛ لیکن دانشمندان علم تحقیق در عملیات در همان سالهای پس از جنگ درک درستی از عملکرد واقعی این الگوریتم‌ها نداشتند. در اوایل سالهای ۱۹۶۰ الی ۱۹۷۰، ایده‌ی ارزیابی زمان و فضای مورد استفاده‌ی یک الگوریتم از طرف ژوریس هارتمنیس و ریچارد استرنز مطرح گشت. فرجام این ایده زمینه‌ساز ظهور نظریه‌ی پیچیدگی محاسباتی شد که متعاقبا در سال ۱۹۷۱، استفان کوک و ریچارد کارپ با ارائه نظریه‌ای انقلابی نشان دادند که بسیاری از مسایل بهینه‌سازی ترکیباتی به لحاظ زمان حل در دسته‌ی چندجمله‌ای غیرقطعی جای می‌گیرند [۵]. در سال ۱۹۷۹، مایکل گری و دیود جانسون با انتشار کتابچه‌ای دسته‌بندی جامعی از این دسته مسایل را مطرح کردند که واقعیتی تلخ ولو تامل‌برانگیز در پی داشت: تقریبا تمامی مسایل بهینه‌سازی ترکیباتی در گستره‌ی زمان حل چندجمله‌ای غیرقطعی کامل، سکنی گزیده‌اند [۶]. به عبارتی برای بسیاری از این مسایل الگوریتم‌های کارا با زمان و سرعت حل معقول (چندجمله‌ای قطعی) در دسترس نیست. بدین‌سان اولین درک منطقی از دسته مسایل بهینه‌سازی ترکیباتی شکل گرفت. دانشمندان علوم کامپیوتر با کسب معرفت از این واقعیت، درصدد طراحی و توسعه‌ی الگوریتم‌هایی با شالوده‌ی تصادفی و شبه تصادفی برآمدند. در سالهای ۱۹۶۳ و ۱۹۶۵، لئونارد راستریجین و ج. ماتیاس مفاهیم جستجوی تصادفی و بهینه‌سازی تصادفی را طی انتشار مقالاتی مطرح کردند [۷] [۸]. یک الگوریتم تصادفی کارا قابلیت حل مساله‌ای با پیچیدگی چندجمله‌ای غیرقطعی را به «احتمال» زیاد در درجه‌ی چندجمله‌ای قطعی (با تعداد گام‌های قطعی) داراست. اولین الگوریتم‌های موثر با اقتباس از مفاهیم علوم زیستی چون نظریه‌ی تکامل توسعه داده شدند. برای اولین بار در سال ۱۹۶۶، اینگو رچنبرگ و لارنس فوگل الگوریتم‌های تکاملی چون الگوریتم ژنتیک را طراحی و توسعه دادند [۹]. از طرفی ورود علم تحقیق در عملیات به سیستم‌های زنجیره‌های تامین، موجودی، حمل و نقل و غیره را در سالهای ۱۹۶۰ الی ۱۹۷۵ دانسته‌اند. امروزه در دانشگاه‌ها و محافل علمی داخلی و خارجی، علم تحقیق در عملیات به اشکال مختلفی چون برنامه‌سازی عدد صحیح، محاسبات نرم، نظریه‌ی بازی‌ها و … در دپارتمان‌های مختلف مهندسی و علوم پایه مرتبط ارائه می‌شوند.
در یک کلام علوم کامپیوتر تاکنون نقش بارزی در شکل‌گیری مرزها و حتی درون‌مایه‌ی مباحث علم تحقیق در عملیات ایفا کرده است. از طرفی علم تحقیق در عملیات پس از طرح چندی از رویکردهای انقلابی (که در بخش‌های قبل اشاره شد) در دهه‌های اخیر دوران نسبتا یکنواختی را سپری می‌کند. بدون تحولات عظیم علم محاسبات کامپیوتری در امر بهینه‌سازی در دو دهه‌ی اخیر، تجسم بقای بسیاری از روشهای اساسی علم تحقیق در عملیات امکان‌پذیر نبود. نمونه‌ی آن را می‌توان در توسعه‌ی الگوریتم سیمپلکس توسط شرکت Ilog و یا احیای دوباره‌ی روش برش‌های گوموری در بسته‌های مختلف نرم‌افزاری ملاحظه نمود. (اشاره به طرح تجاری‌سازی روش سیمپلکس توسط متخصصین علوم کامپیوتر و ارائه آن در بسته‌ی نرم‌افزاری Ilog CPLEX در سال ۱۹۹۴ دارد.) [۱۰].
بسیاری از دانشمندان و متخصصین علوم کامپیوتر بر این باورند که ظرفیت محاسباتی کامپیوترهای سیلیکونی در آینده‌ای نه چندان دور به اشباع رسیده و لاجرم دستیابی به نتایج محاسباتی کارا به لحاظ سرعت و زمان حتی با بهره‌گیری از اهرم فشار تصادفی‌سازی امکان‌پذیر نخواهد بود. بدین سان متخصصین علوم کامپیوتر در سالهای اخیر جهت رهایی از این رکود، نظریاتی از افق‌های متفاوت در راستای توانمندی‌های سخت‌افزاری و نرم‌افزاری مطرح کرده‌اند. به عنوان مثال طراحی و توسعه‌ی سیستم‌های فراپردازشی چون شبکه‌های ابری و محاسبات کوانتمی به نوبه‌ی خود، متخصصین سایر علوم مهندسی را جهت توسعه‌ی الگوریتم‌هایی برای مسایل چالشی در حوزه‌ی خود ترغیب خواهد کرد. متخصصین این حوزه بر این باورند که پیاده‌سازی رایانه‌ها بر مبنای منطق کوانتمی چون کوبیت (واحد پردازش کوانتمی)، پردازش الگوریتم‌ها را هزاران برابر سریع‌تر از کامپیوترهای رایج امکان‌پذیر خواهد نمود [۱۱]. از مطالب موخر، سه چشم‌انداز متفاوت برای تعامل شالوده‌های علوم کامپیوتر و علم تحقیق در عملیات قابل ترسیم است:
۱- بازگشت محققین علوم تحقیق در عملیات به حوزه‌های علوم مدیریتی و مدل‌سازی صرف نظر از ابعاد محاسباتی و واگذاری این امور به متخصصان علوم کامپیوتر.
۲- ورود متخصصان علم تحقیق در عملیات به فرایند طراحی و توسعه‌ی الگوریتم‌های نوپا بر مبنای مفاهیم پردازشی.
۳- ادامه‌ی مسیر کنونی و دگردیسی حوزه تحقیق در عملیات به سایر علوم نوظهور. (جان هوکر اذعان دارد که دپارتمان‌های مرتبط با علم تحقیق در عملیات در حال ناپدید شدن هستند. [۱۲])
مراجع
|
Rosenhead, J. , Thunhurst, C., "A Materialist Analysis of Operational Research," Journal of the Operational Research Society, Vol. 33, No. 2, pp. 111-122, 1982. |
[۱] |
|
Who Was George B. Dantzig? [Online]. https://www.informs.org/Recognize-Excellence/INFORMS-Prizes-Awards/George-B.-Dantzig-Dissertation-Award/Who-Was-George-B.-Dantzig |
[۲] |
|
Cherniak, C., "Computational complexity and the universal acceptance of logic," Journal of Philosophy, Vol. 81, No. 12, pp. 739-758, 1984. |
[۳] |
|
Wagner, M.H., "An integer programming model for machine scheduling," Naval Research Logistics Quarterly, Vol. 6, No. 1, pp. 131-140, 1959. |
[۴] |
|
Cook, S., "The complexity of theorem-proving procedures," in STOC '71 Proceedings of the third annual ACM symposium on Theory of computing, New York, 1971. |
[۵] |
|
Garey, M.R. , Johnson, D.S.; Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: Bell Telephone Laboratories, Inc., 1979. |
[۶] |
|
Rastrigin, L.A., "The convergence of the random search method in the extremal control of a many parameter system," Automation and Remote Control, Vol. 24, No. 10, pp. 1337–1342, 1963. |
[۷] |
|
Matyas, J., "Random optimization," Automation and Remote Control, Vol. 26, No. 2, pp. 246-253, 1965. |
[۸] |
|
Fogel, L., Owens, A.J. , and Walsh, M.J.; Artificial Intelligence through Simulated Evolution, Michigan: John Wiley & Sons, 1966. |
[۹] |
|
Cornuéjols, G., "Revival of the Gomory cuts in the 1990’s," Annals of Operations Research, Vol. 149, No. 1, pp. 63-66, 2007. |
[۱۰] |
|
Aaronson, S.; "The limits of quantum computers," Scientific American, March, 2008. |
[۱۱] |
|
Hooker, J.N., "Good and Bad Futures for Constraint Programming (and Operations Research)," Constraint Programming Letters, Vol. 1, pp. 21-32, 2007. |
[۱۲] |
