پديد آورنده :
صدري، پدرام
عنوان :
رويكردي جديد در حل مسائل برنامه ريزي عدد صحيح خطي خالص با ضرايب صحيح
مقطع تحصيلي :
كارشناسي ارشد
گرايش تحصيلي :
سيستم هاي اقتصادي و اجتماعي
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان، دانشكده صنايع و سيستم
صفحه شمار :
دوازده،[68]ص.: مصور،جدول،نمودار
يادداشت :
ص.ع.به فارسي و انگليسي
استاد راهنما :
محمد سعيد صباغ
توصيفگر ها :
برنامه ريزي عدد صحيح خالص , برش تابع هدف , برنامه ريزي عدد صحيح دودويي , شاخه زدن براساس جمع مقادير غير صحيح متغيرها
استاد داور :
ناصر ملاوردي، حميد مير محمدي
تاريخ ورود اطلاعات :
1395/08/04
دانشكده :
مهندسي صنايع و سيستم ها
چكيده فارسي :
چكيده در دنياي امروز بشر با مسائ ل گوناگون در زمينه هاي مختلف علمي كاربردي صنعتي توليدي و غيره روبرو است كه بايستي با مدل هاي خاص خود حل گردد يكي از اين مدل ها برنامه ريزي عدد صحيح است كه به دليل كاربرد فرواني كه در مسائ ل و پروژه هاي گوناگون دارد از اهميت ويژه اي برخوردار است لذا رسيدن به راه حلي جديد با مزيت هاي بيشتر براي حل مسئله برنامه ريزي عدد صحيح داراي اهميت فراواني است از سال 1591 فعالين تحقيق در عمليات در حال مدلسازي و حل مسائل برنامه ريزي عدد صحيح بوده اند همانگونهه كهه سهخت افهزار كامپيوتر پيشرفت كرده است محققان براي مدلسازي مسائل پيچيده و حل آنها آزادي عمل بيشتري يافته اند در اين مطالعه با ارائه رويكردهاي جديد براي حل مسائل برنامه ريزي عدد صحيح در برخي مسائل زمان حل و حجم عمليات كاهش يافته است در روش هاي ارائه شده فرض مي شود ضرايب صحيح هستند در واقع مسائل برنامه ريزي عدد صحيح خالص 1 با ضهرايب صحيح بررسي ميشوند همچنين رويكرد هايي براي حل مسائل برنامه ريزي عدد صحيح دودويي 2 نيز ارائه مهي شهود در ايهن تحقيهق الگوريتمي ارائه شده كه در آن ابتدا مسئله آزاد شده حل مي شود اگر جواب ها صحيح بودند كه مسئله حل است در غير اينصورت از برش تابع هدف استفاده مي شود از مزيت هاي برش تابع هدف اين است كه سمت چپ آن همواره ثابت است و فقط مقهدار سهمت راست آن تغيير مي كند لذا مانند ساير برش ها باعث بزرگتر شدن وپيچيده تر شدن مسئله نمي شود اگر در الگهوريتم ارائهه شهده بهه جواب بهينه چندگانه رسيديم بايستي بررسي كنيم در بين جواب ها جو اب مطلوب وجود دارد يا خير بررسي اين موضوع خود مسئله دشواري است در ادامه روش هايي ارائه شده كه در برخي مسائل مي توا ند در بين جواب ها جواب مطلوب را يافته و مسئله را حل كند يا نشان دهد كه جواب مطلوب وجود ندارد و مي توان الگوريتم را ادامه داد و برش هاي بعدي تابع هدف را اعمال كرد در روش هاي ارائه شده مي توان از شاخه زدن بر اساس جمع مقادير غيرصحيح متغيرها شاخه زدن بر اساس جمع متغيرهاي با هزينه تقليل يافته صفر و برش بر اساس جمع متغيرهاي كمبود نام برد در برخي مسائل در مقايسه با نرم افزارهاي CPLEX و WINQSB روش هاي ارائه شده مسائل را در مدت زمان كوتاه تر حل كرده اند همچنين مسائل خاص مانند تخصيص سه بعدي و دو مسئله متقارن با اين روش ها حل شده اند كه مسئله تخصيص سه بعدي در زمان كوتاه البته تقريبا برابر با زمان حل نرم افزارهاي ذكر شده حل شده است اما مسئله متقارني در مدت زمان كوتاه با روش ارائه شده حل شده است كه با استفاده از CPLEX جواب بهينه بدست نيامد و نرم افزار WINQSB پس از گذشت ساعت ها نتوانست آن را حل كند كلمات كليدي 1 برنامه ريزي عدد صحيح خالص 2 بهرش تهابع ههدف 3 برنامهه ريهزي عهدد صهحيح دودويهي 4 شاخه زدن براساس جمع مقادير غيرصحيح متغيرها 1 Pure integer programming 2 Binary integer programming
چكيده انگليسي :
A new approach for solving pure linear integer programming problems with integer coefficient pedram sadri p sadri@in iut ac ir Date of submission 2016 6 21 Department of Industrial Systems Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language PersianSupervisor Dr M S Sabbagh sabbagh@cc iut ac irAbstract Since 1950 activists in operations research are solving integer programmingproblems As computer hardware memory and speed has increased researchers have beenmodeling complex problems and solving them with more freedom In this study weprovide new approaches to solve integer programming problems which resulted inreducing solution times for some problems It is assumed that model has integercoefficients and constants and all variables are integers as well Also binary integerprogramming are studied In this research the algorithm first solves the relaxedproblem If the solution is integer we are done otherwise we use an objective function The advantage of using a cutting objective function is that the left side of the constraintdose not change and just its right hand side changes If the model has multiple optimalsolution we need to check whether an integer solution exists These methods find anoptimum integer solution among multiple solution or show that an integer solution doesnot exist The proposed methods are named branching based on total non integer valuesof variables branching based on the sum of zero reduce cost variables or based on sumof slack variables In some problems methods introduced have solved problems in ashorter time in comparison with the CPLEX and WINQSB softwares Also we havesolved specific problems such as the axial three dimensional and symmetric integerprogramming problems Keywords pure integer programming objective function cut binary integer programming branching based on total non integer values of variables
استاد راهنما :
محمد سعيد صباغ
استاد داور :
ناصر ملاوردي، حميد مير محمدي
