برش گومری (برش کسری)

برش گومری (برش کسری)

اسلاید 1: برش گومری (برش کسری ) روش دیگری برای حل مدلهای برنامه ریزی عدد صحیح است. زمانی می توان از این روش استفاده کرد که مقادیر سمت راست (bi ) و ضرایب فنی(aij) همگی صحیحح باشند . در این روش به منظور حل مدل صفحات برشی استفاه می شود . با استفاه از این صفحات ناحیه موجه به گونه ای برش داده می شود که اولاً نقطه غایی مورد نظر تبدیل به عدد صحیح گردد و ثانیاًهیچ جواب عدد صحیحی هم در اثر برش از ناحیه موجه حذف نشود

اسلاید 2:

اسلاید 3: فرایند حل مساله به روش گومری1)مساله را صرفنظر از فرض صحیح بودن با استفاه از روش سیمپلکس حل کنید2)در صورتیکه مدل دارای جواب بهینه عدد صحیح باشد مساله به جواب بهینه عدد صحیح رسیده است در غیر این صورت محدودیت جدیدی که موجب عدد صحیح شدن جواب بهینه می شود به مدل اضافه نمائید.دستورالعمل اضافه کردن محدودیت جدید2-1)معادله معرف متغیر اساسی را که دارای مقدار کسری است انتخاب نمائید.(در صورتیکه بیش از یک معادله معرف وجوداشته باشد بهتر است آنرا نتخاب نمائید که دارای مقدار کسری برزرگتری است و اگر چند معادله دارای مقدار کسری بزرگ یکسانی باشد یکی را به دلخواه انتخاب کنید) 2-2) معادله معرف انتخاب شده را به بخش صحیح و کسری تفکیک کنید. برای این منظور تابلو سیمپلکس زیر را در نظر بگیرید.

اسلاید 4:

اسلاید 5: به عنوان مثال در معادله فوق معادله i ام معرف xi غیر صحیح است. بنابراین این معادله انتخاب و بصورت زیر نوشته می شود. با توجه به اینکه و برخی از ها کسری هستند می توان آنها را بصورت زیر تفکیک کرد

اسلاید 6: به عبارت ديگر و در تفکیک مقادیر سمت راست و ضرایب متغیرهای غیر اساسی به دو قسمت صحیح و کسری از قاعده زیر استفاده نمائید

اسلاید 7: a[a]f=a-[a]22030-2-20-3-1

اسلاید 8: بنابراین می توان معادله مر بوط به محدودیت را که بصورت است به شکل زیر در می آید

اسلاید 9: با توجه به صحیح بودن سمت چپ معادله سمت راست معادله می بایست صحیح باشد و از طرفی داریم. لذا شرط لازم برای صحیح بودنآنست که :

اسلاید 10: این محدودیتی است که پس از استاندارد سازی می بایست به مدل افزوده شود. لذا خواهیم داشت:

اسلاید 11:

اسلاید 12: محدویت افزوده شده را اصطلاحاً برش کسری می نامند زیرا موجب برش بخشی از ناحیه موجه که فقط جوابهای کسری در آن قرار دارد می شود.3- همانگونه که ملاحظه می شود با اضافه شده این محدودیت شرط موجه بودن نقض می شود . بنابراین می بایست با استفاده از سیمپلکس ثانویه مدل حل شده و جواب موجه بهینه جدید بدست آید.

اسلاید 13: 4- در صورتیکه جواب بهینه جدید بدست آمده عدد صحیح باشد ، جواب بهینه حاصل شده است در غیر اینصورت به مرحله دوم بروید.

اسلاید 14: مثال (1)

اسلاید 15: با توجه به اینکه معادله معرف x2 بیشترین مقدار کسری را دارد به عنوان معادله معرف انتخاب و محدودیت زیر افزوده می شود.

اسلاید 16: لذا تابلو نهایی بصورت زیر در می آید.

اسلاید 17: پس از حل مدل با استفاده از سیمپلکس ثانویه تابلو زیر نشان دهنده جواب بهینه عدد صحیح است حاصل می شود.

اسلاید 18: مثال (2)

اسلاید 19: با توجه به اینکه هر دو مقدار کسری یکسانی دارند ، انتخاب هر دو معادله برای تعریف شرایط یکسانی برای انتخاب دارند، در هر صورت معادله اول برای تعریف محدویت برشی انتخاب می شود

اسلاید 20: لذا تابلو نهایی بصورت زیر در می آید.

اسلاید 21: با حل مدل به روش سیمپلکس ثانویه تابلو زیر حاصل خواهد شد.