برنامه ریزی اعداد صحیح

برنامه ریزی اعداد صحیح

اسلاید 1:

اسلاید 2: برنامه ريزي عدد صحيحInteger Programming اانوع برنامه ريزي عدد صحيحالف)برنامه ريزي عدد صحيح محضب)برنامه ريزي عدد صحيح مختلط mathematical Definition:

اسلاید 3: روشهاي حل مدلهاي برنامه ريزي عدد صحيح محضروش گرد کردن روش مجموعه ترازروش شاخه و کرانروش برش گومري ( Gomery)

اسلاید 4: 1) روش گرد کردن در اين روش از قاعده گرد کردن اعداد براي دست يابي به جواب بهينه عدد صحيح استفاده مي شود ليکن استفاده از اين زمانيکه مقادير متغيرهاي تصميم بسيار بزرگ باشد استفاه از اين روش ارزش کاربرد دارد ليکن هرگاه مقادير متغيرهاي تصميم نسبتا کوچک باشد استفاده از اين روش از کارائي لازم برخوردار نخواهد بود.

اسلاید 5: مثال هايي از برنامه ريزي عدد صحيح با جوابهاي بهينه ماخوذ از روش گرد کردن و عدد صحيح

اسلاید 6: Second Example:

اسلاید 7: Third Example:

اسلاید 8: 2) روش مجموعه ترازدراين روش بدون توجه به فرض عدد صحيح مدل LP ، ناحيه موجه موجه مدل تعين مي شود و سپس کليه جوابهاي عدد صحيح و موجه مدل شناسايي مي گردد و پس از آن مجموعه تراز رسم و جهت حرکت آن تعيين مي شود . سپس مجموعه تراز تا حد امکان به سمت بهبود حرکت مي دهيم آخرين جواب عدد صحيح و موجهي که در مسير بهبود قرار دارد جواب بهينه مدل خواهد بود.

اسلاید 9: Example:

اسلاید 10: Z=1800Z=800

اسلاید 11: کاربرد مجموعه تراز زماني مي توان از اين روش استفاه کرد که امکان حل مدل به روش ترسيمي وجود داشته باشد . به بيان ديگر هرگاه تعداد متغيرهاي تصميم به سه متغير افزايش يابد حل مدل به روش ترسيمي دشوار و در صورت افزايش تعداد به بيش از سه متغير حل مدل به روش ترسيمي غيرممکن خواهد شد.

اسلاید 12: 3)روش شاخه و کران اساس اين روش به برش ناحيه اي موجهي که متغيرهاي تصميم در آن ناحيه غير صحيح هستند استوار است. اين برشها تا جايي ادامه مي يابد که به يک جواب بهينه عدد صحيح دست يابيم.

اسلاید 13: مدل LP زير را به همراه جواب بهينه آن در نظر بگيريد

اسلاید 14: در شکل ناحيه موجه و جواب بهينه مدل LP را نشان مي دهد.

اسلاید 15: با توجه به اينکه X1 عدد صحيح است در جواب بهينه الزاما مي بايست يکي از دو شرط زير برقرار باشد.

اسلاید 16: بنابراين از کل ناحيه موجه ناحيه اي که در آن X1 غير صحيح است را مي توان حذف کرد. به بيان ديگر ناحيه P را مي توان از ناحيه موجه برش داد.

اسلاید 17: لذا ناحيه موجه براي برنامه ريزي عدد صحيح بصورت زير در مي آيد Pهمانگونه که مشاهده مي شود ناحيه باز P حذف گرديده و ناحيه موجه به دوقسمت جدا از هم تبديل شده است. بديهي است جواب بهينه عدد صحيح در صورت وجود الزاماً يکي از آنها واقع خواهد شد.

اسلاید 18: لذا مي بايست مدل برنامه ريزي هر دو ناحيه موجه را مستقل از همديگر در نظر گرفته از هم ديگر و جواب بهينه هر کدام را بدست آورد. مدل برنامه ريزي خطي مر بوط به هر دو ناحيه موجه بصورت زير است.

اسلاید 19:

اسلاید 20: همانطوريکه مشاهده مي شود در هر دو مدل x1 بصورت عدد صحيح تبديل شده است و لي اين بار x2 غير صحيح است. اين بار بطور مشابه هر دو مدل به دو زير شاخه منشعب مي شود.

اسلاید 21: نيازي به انشعاب مدل (2-1) و(2-2) وجود نداردزيرا اولي داراي جواب بهينه عدد صحيح و ديگري فاقد جواب است. ولي دو مدل ديگر بطور مشابه هر کدام به دو شاخه منشعب مي شود

اسلاید 22:

اسلاید 23:

اسلاید 24: همانگونه که ملاحظه مي شود همه شاخه ها به انتها رسيده و امکان انشعاب وجود ندارد.لذا از بين مجموعه جوابهاي بهينه جوابي به عنوان جواب بهينه انتخاب خواهد شد که اولاً عدد صحيح باشد ثانيا از بين جوابهاي عدد صحيح موجود مطلوب ترين مقدار را براي تابع هدف داشته باشد. با توجه به اينکه در اينجه تابع هدف حداقل سازي مي باشد جواب بهينه بصورت زير خواهد بود.

اسلاید 25:

اسلاید 26: والسلام علیکم و رحمه ا... و برکاته