محمد نمک شناس/ دانشجوي دکتري مهندسي صنايع اختصاصي اخبار مهندسي صنايع ايران پس از انقلاب صنعتي، بسياري از قدرت‌هاي بزرگ سرنوشتي ايجابي از دو جنس بهره‌برداري بهينه از منابع مشترک و بلافاصله به حداکثر رسانيدن سود اقتصادي را براي خود رقم زدند. اين صور از ايده‌آل گرايي محض اهداف متضادي را نيز در برداشت: جنگ و رفاه. تاريخچه‌ي رسمي تحقيق در عمليات و اولين جرقه‌هاي بهره‌برداري از اين علم، به اواخر سالهاي 1930 الي 1940 برمي‌گردد؛ دقيقا زماني که امپراتوري بريتانيا براي جنگ جهاني دوم آماده مي‌شد. از طرفي طراحي و توسعه‌ي فناوري‌هاي نظامي (مانند رادارها) منجر به پيدايش انواع متعددي از مسايل سازماني و مديريتي در اين برهه از زمان شد [1]. در بهبوهه‌ي اين نبرد تاريخ‌ساز بود که اولين نظريات بنيادي تحقيق در عمليات شکل گرفتند. پاتريک مينارد، فيزيکدان نظري امپراتوري بريتانيا، جزو اولين محققاني بود که علم تحقيق در عمليات را معرفي و به عنوان طراح استراتژي‌هاي نظامي از اين علم بهره جست. رياضيدان پرآوازه روس‌تبار، لئونيد کانتروويچ، در سال 1939 برنامه‌ريزي خطي را جهت سازماندهي عمليات نظامي، کاهش هزينه‌هاي حاصل از جنگ و افزايش تلفات دشمن مطرح کرد. نکته‌ي قابل تامل در اين است که برنامه‌ريزي خطي به بهانه‌ي حفظ اسرار جنگي تا سال 1947 از محافل علمي پنهان نگاه داشته شد و اغلب مورد استعمال سياست‌هاي ضدبشري قرار مي‌گرفت. دانشمندان و محققان آن دوران بر اين واقف بودند که توان تصميم‌گيري براي عملياتي با ابعاد بالا و امکانات متعدد بر مبناي يک مدل برنامه‌ريزي خطي را نخواهند داشت، چرا که آزمايش تمامي حالت‌هاي ممکن براي حل يک مدل خطي به زمان غير قابل تصوري نياز داشت. دقيقا در سال 1947 بود که جرج دانتزيگ، رياضيدان مشهور آمريکايي و مسئول عمليات محاسباتي در نيروي هوايي ايالات متحده، الگوريتم سيمپلکس را جهت سرعت بخشي به حل مدل‌هاي خطي ارائه داد. به ذغم بسياري از محققين تحقيق در عمليات، توسعه‌ي روش سيمپلکس مهم‌ترين دستاورد اين علم تاکنون بوده است [2]. تنها مزيت نسبي روش سيمپلکس، بررسي بخشي از حالات ممکن (نقاط گوشه‌اي) تا حد ممکن بود. از طرفي، درون‌مايه‌ي بنيادي‌ترين نظريات رايانشي و الگوريتم (همراه هميشگي علم تحقيق در عمليات) توسط آلن تورينگ و ريچارد نيومن، رياضي‌دانان برجسته‌ي امپراطوري بريتانيا، در همان سالهاي قوت‌گيري جنگ جهاني دوم در حال شکل‌گيري بود. پس از فروکش کردن جنگ، علم تحقيق در عمليات در امپراطوري بريتانيا از حوزه‌ي نظامي به بخش‌هاي صنعتي گزار نرمي صورت داد. در آن دوران، اين علم اغلب در صنايع ملي و بخصوص صنايع سنگين مانند صنعت فولاد بخدمت گرفته شد. اين روند نيز با مشکل عمده‌اي روبرو بود که با افزايش سطح رفاه، مکانيزاسيون بخش‌هاي صنعتي، افزايش سطح فناوري و يکپارچه سازي عمليات، الگوريتم‌هاي سنتي ارائه شده در شرايط جنگي قادر به حل مدل‌هاي رياضي توسعه‌يافته در قالب برنامه‌ريزي خطي نبودند. روشهاي توسعه‌يافته مبتني بر الگوريتم سيمپلکس، ارتباط تنگاتنگي با محاسبه‌ي معکوس ماتريس ضرايب فني حاصل از يک مدل برنامه‌ريزي خطي داشتند؛ لذا پردازنده‌هاي دوران پس از جنگ توان پردازش اين دسته از مسايل را نداشتند. اثبات شده است که روش سيمپلکس در برخي شرايط، از زمان حل با درجه‌ي نمايي تبعيت مي کند [3]. از طرفي کاربرد مدل‌هاي خطي در مواجهه با مسايل داراي فضاي گسسته و بهينه‌سازي ترکيباتي به تدريج از رونق افتاد. در سالهاي 1959 و 1960، هاروي واگنر و آلن منن اولين مدل‌هاي برنامه‌ريزي عدد صحيح را جهت زمان‌بندي مسايل تک ماشينه و توليد کارگاهي طي يک مقاله‌ي علمي ارائه دادند [4]. اولين ظهور متغيرهاي صفرويک و مسايل بهينه‌سازي ترکيباتي نيز در راستاي همين مطالعات بوقوع پيوست. سلسله‌ي اين رقابت‌‌ها جهت ارائه‌ي روشي موثر براي حل مدل‌هاي خطي، منجر به توسعه‌ي چند الگوريتم تاثيرگذار شد. الگوريتم نقطه‌ي داخلي، يکي از اين راهکارها بود که ايده‌ي اوليه‌ي آن توسط جان نيومن ارائه شد و در سال 1984 توسط نراندرا کارمارکار توسعه داده شد. اين روش به الگوريتم کارمارکار مشهور بوده و در مواجهه با مسايل با ابعاد بالا کارايي بسيار خوبي از خود به نمايش مي‌گذارد. اهم راهکارهاي ارائه شده جهت واکاوي مسايل بهينه‌سازي ترکيباتي، در اصل يک الگوريتم بودند؛ ليکن دانشمندان علم تحقيق در عمليات در همان سالهاي پس از جنگ درک درستي از عملکرد واقعي اين الگوريتم‌ها نداشتند. در اوايل سالهاي 1960 الي 1970، ايده‌ي ارزيابي زمان و فضاي مورد استفاده‌ي يک الگوريتم از طرف ژوريس هارتمنيس و ريچارد استرنز مطرح گشت. فرجام اين ايده زمينه‌ساز ظهور نظريه‌ي پيچيدگي محاسباتي شد که متعاقبا در سال 1971، استفان کوک و ريچارد کارپ با ارائه نظريه‌اي انقلابي نشان دادند که بسياري از مسايل بهينه‌سازي ترکيباتي به لحاظ زمان حل در دسته‌ي چندجمله‌اي غيرقطعي جاي مي‌گيرند [5]. در سال 1979، مايکل گري و ديود جانسون با انتشار کتابچه‌اي دسته‌بندي جامعي از اين دسته مسايل را مطرح کردند که واقعيتي تلخ ولو تامل‌برانگيز در پي داشت: تقريبا تمامي مسايل بهينه‌سازي ترکيباتي در گستره‌ي زمان حل چندجمله‌اي غيرقطعي کامل، سکني گزيده‌اند [6]. به عبارتي براي بسياري از اين مسايل الگوريتم‌هاي کارا با زمان و سرعت حل معقول (چندجمله‌اي قطعي) در دسترس نيست. بدين‌سان اولين درک منطقي از دسته مسايل بهينه‌سازي ترکيباتي شکل گرفت. دانشمندان علوم کامپيوتر با کسب معرفت از اين واقعيت، درصدد طراحي و توسعه‌ي الگوريتم‌هايي با شالوده‌ي تصادفي و شبه تصادفي برآمدند. در سالهاي 1963 و 1965، لئونارد راستريجين و ج. ماتياس مفاهيم جستجوي تصادفي و بهينه‌سازي تصادفي را طي انتشار مقالاتي مطرح کردند [7] [8]. يک الگوريتم تصادفي کارا قابليت حل مساله‌اي با پيچيدگي چندجمله‌اي غيرقطعي را به «احتمال» زياد در درجه‌ي چندجمله‌اي قطعي (با تعداد گام‌هاي قطعي) داراست. اولين الگوريتم‌هاي موثر با اقتباس از مفاهيم علوم زيستي چون نظريه‌ي تکامل توسعه داده شدند. براي اولين بار در سال 1966، اينگو رچنبرگ و لارنس فوگل الگوريتم‌هاي تکاملي چون الگوريتم ژنتيک را طراحي و توسعه دادند [9]. از طرفي ورود علم تحقيق در عمليات به سيستم‌هاي زنجيره‌هاي تامين، موجودي، حمل و نقل و غيره را در سالهاي 1960 الي 1975 دانسته‌اند. امروزه در دانشگاه‌ها و محافل علمي داخلي و خارجي، علم تحقيق در عمليات به اشکال مختلفي چون برنامه‌سازي عدد صحيح، محاسبات نرم، نظريه‌ي بازي‌ها و … در دپارتمان‌هاي مختلف مهندسي و علوم پايه مرتبط ارائه مي‌شوند. در يک کلام علوم کامپيوتر تاکنون نقش بارزي در شکل‌گيري مرزها و حتي درون‌مايه‌ي مباحث علم تحقيق در عمليات ايفا کرده است. از طرفي علم تحقيق در عمليات پس از طرح چندي از رويکردهاي انقلابي (که در بخش‌هاي قبل اشاره شد) در دهه‌هاي اخير دوران نسبتا يکنواختي را سپري مي‌کند. بدون تحولات عظيم علم محاسبات کامپيوتري در امر بهينه‌سازي در دو دهه‌ي اخير، تجسم بقاي بسياري از روشهاي اساسي علم تحقيق در عمليات امکان‌پذير نبود. نمونه‌ي آن را مي‌توان در توسعه‌ي الگوريتم سيمپلکس توسط شرکت Ilog و يا احياي دوباره‌ي روش برش‌هاي گوموري در بسته‌هاي مختلف نرم‌افزاري ملاحظه نمود. (اشاره به طرح تجاري‌سازي روش سيمپلکس توسط متخصصين علوم کامپيوتر و ارائه آن در بسته‌ي نرم‌افزاري Ilog CPLEX در سال 1994 دارد.) [10]. بسياري از دانشمندان و متخصصين علوم کامپيوتر بر اين باورند که ظرفيت محاسباتي کامپيوترهاي سيليکوني در آينده‌اي نه چندان دور به اشباع رسيده و لاجرم دستيابي به نتايج محاسباتي کارا به لحاظ سرعت و زمان حتي با بهره‌گيري از اهرم فشار تصادفي‌سازي امکان‌پذير نخواهد بود. بدين سان متخصصين علوم کامپيوتر در سالهاي اخير جهت رهايي از اين رکود، نظرياتي از افق‌هاي متفاوت در راستاي توانمندي‌هاي سخت‌افزاري و نرم‌افزاري مطرح کرده‌اند. به عنوان مثال طراحي و توسعه‌ي سيستم‌هاي فراپردازشي چون شبکه‌هاي ابري و محاسبات کوانتمي به نوبه‌ي خود، متخصصين ساير علوم مهندسي را جهت توسعه‌ي الگوريتم‌هايي براي مسايل چالشي در حوزه‌ي خود ترغيب خواهد کرد. متخصصين اين حوزه بر اين باورند که پياده‌سازي رايانه‌ها بر مبناي منطق کوانتمي چون کوبيت (واحد پردازش کوانتمي)، پردازش الگوريتم‌ها را هزاران برابر سريع‌تر از کامپيوترهاي رايج امکان‌پذير خواهد نمود [11]. از مطالب موخر، سه چشم‌انداز متفاوت براي تعامل شالوده‌هاي علوم کامپيوتر و علم تحقيق در عمليات قابل ترسيم است: 1- بازگشت محققين علوم تحقيق در عمليات به حوزه‌هاي علوم مديريتي و مدل‌سازي صرف نظر از ابعاد محاسباتي و واگذاري اين امور به متخصصان علوم کامپيوتر. 2- ورود متخصصان علم تحقيق در عمليات به فرايند طراحي و توسعه‌ي الگوريتم‌هاي نوپا بر مبناي مفاهيم پردازشي. 3- ادامه‌ي مسير کنوني و دگرديسي حوزه تحقيق در عمليات به ساير علوم نوظهور. (جان هوکر اذعان دارد که دپارتمان‌هاي مرتبط با علم تحقيق در عمليات در حال ناپديد شدن هستند. [12]) مراجع Rosenhead, J. , Thunhurst, C., "A Materialist Analysis of Operational Research," Journal of the Operational Research Society, Vol. 33, No. 2, pp. 111-122, 1982. | [1] | 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 | [2] | Cherniak, C., "Computational complexity and the universal acceptance of logic," Journal of Philosophy, Vol. 81, No. 12, pp. 739-758, 1984. | [3] | Wagner, M.H., "An integer programming model for machine scheduling," Naval Research Logistics Quarterly, Vol. 6, No. 1, pp. 131-140, 1959. | [4] | 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. | [5] | Garey, M.R. , Johnson, D.S.; Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: Bell Telephone Laboratories, Inc., 1979. | [6] | 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. | [7] | Matyas, J., "Random optimization," Automation and Remote Control, Vol. 26, No. 2, pp. 246-253, 1965. | [8] | Fogel, L., Owens, A.J. , and Walsh, M.J.; Artificial Intelligence through Simulated Evolution, Michigan: John Wiley & Sons, 1966. | [9] | Cornuéjols, G., "Revival of the Gomory cuts in the 1990’s," Annals of Operations Research, Vol. 149, No. 1, pp. 63-66, 2007. | [10] | Aaronson, S.; "The limits of quantum computers," Scientific American, March, 2008. | [11] | Hooker, J.N., "Good and Bad Futures for Constraint Programming (and Operations Research)," Constraint Programming Letters, Vol. 1, pp. 21-32, 2007. |
|