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

صفحه 1:
برش گومری (برش کسری ) روش دیگری برای حل مدلهای برنامه ریزی عدد صحیح است. زمانی می توان از این روش استفاده کرد که مقادير سمت ‎(bi) Curly‏ و ضرایب فنی(ه) همگی صحیحح باشند . در اين روش به منظور حل مدل ‎ee eat‏ شود . ما استفاه از اين صفحات ناحيه موجه به كونه اى برش داده مى شود كه ‎Vol‏ قطه شایی مورد نظر تبديل به عدد صحیح گردد و ثانیاهیچ چواب عدد صحیحی هم در اثر برش از ناحیه موجه حذف نشود 

صفحه 2:
5و وه + و7 

صفحه 3:
فرایند حل مساله به روش گومری )مساله را صرفنظر از فرض صحيح بودن با استفاه از روش ۲)در صورتیکه مدل دارای جواب بهینه عدد صحیع باشد مساله به جواب بهینه عدد صحیح رسیده است در غیر این صورت محدود یت جدیدی که موجب عدد صحیح شدن جواب بهینه شود به مدل ‎Sots Sati ١‏ عالت ال دستورالعمل اضافه كردن محدوديت جديد ۲-۱)معادله معرف متفیر اسا ور ى أست ‎ye‏ .)3 سورنسته بیش | ما ‎hp‏ ‎feos‏ 1 ‎Pa aise‏ تس وی ‎Ss (ama‏ ‎(onde‏ ا دراک ی ‎ll cy ln ۴‏ شدهررا به يشل و گسري ‎SES‏ ‏کنید. برای این منظور تابلو سیمپلکس زیر را در ‎ee‏ 

صفحه 4:
د اه ‎mS‏ Bu Vy Gn Gan رلز .۰ ۳ رو ۰ ينه ل a yy ‎oO].‏ سر ‎ ‎o -|N ‎ ‎ ‎ ‎ ‎ 

صفحه 5:
به عنوان مثال در معادله فوق معادله ا ام معرف ‎xt‏ ‏غير صحيح است. بنابراین این معادله انتخاب و سورك ور السرم بوه 77 - 2 ay; ja ay Jon ‏مه و8‎ ها کسری هستند می توان آنها را بصورت زیر تفکیک کرد ‎ee‏ 

صفحه 6:
به عبارت ديكر > و 1> ررك 0 در تفكيك مقاديري سمت راست و ضرايب متغيرهاى غير اساسى به دو قسمت صحيح و كسرى از قاعده زیر استفاده نمائید 

صفحه 7:
| جع ببس مارم 2 - )29( -2 on 9 110] ۵ب و مربت دم f=a-[a] [a] 

صفحه 8:
بنابراين می توان معادله مر بوط به محدودیت را که بصورت رازه زر -ر< ود ‎ja‏ است به شکل زیر در می آید درگ - مدا - رو جار0اع بر => X- elt Sila ‏درگ - رح رل‎ 

صفحه 9:
جه به صحيح ۳ معادله سمت بو ت حب ۱ اح 1 باشد واز طرفي راست n n- Sy 1 ‏11ب‎ >> 1 ‏داريم.‎ 171 ١ ‏ل‎ ‎= 22 ‏بودن‎ ‏لذا شرط لازم برای صحیح ب‎ nD ne Sy 2,035 <=0 stand 

صفحه 10:
این محدودیتی است که پس از استاندارد سازی می :بایست به مدل افزوده شود. لذا خواهیم داشت 12 11 > 1; =0 jal 

صفحه 11:
ه م زا ‎Moo‏ Qo ‏رر©‎ Bm ‎Sm" mn‏ مه ‎~My Ma‏ وت ‎ ‎ ‎ ‎ ‎° ‏ه ‎ ‎ 

صفحه 12:
محدویت افزوده شده را اصطلاحا برش کسری ی نامند زرا موجب برش بخشی از ناحیه موجه که .فقط جوابهای کسری در آن قرار دارد می شود هطنگونه که ملاحظه می‌شود بالضافه شده لیرمحدودیت-9 ‎RUS ae ga‏ قغو یوش وة «ب- تایرلیرهی سكسا امكف از .سيميلكسثانويه مدلح[شده و جولبموجه بسهینه جدید بدسلید 

صفحه 13:
در صورتیکه جولدبسهینه ‎cl hee‏ دس 6۳ لمده علد صحيح باشد » جوليسهينه حاصل شده لستدر غیر لینصورنسه مرحله دوم نوف 

صفحه 14:
0 ب مزه ۱9 ۱ ۵ In P AR oP Malas In aw 3 © ه ب| ه 1 ae & N م ه هزه اير تت ه جم و | و ار ‎Nie |۱۵ © ©‏ 5 ف سم | ۱ ام 

صفحه 15:
با توجه به انکه معادله معرف 62 بیشترین مقدار ‎lydia‏ دارد به عنوان معادله معرف انتخاب و محدودیت زیر افزوده می شود. 2 پرگ ع1 و = 9% 9% ‎=-ix-2%+sq=-2‏ ‏3 و *9 

صفحه 16:
9 1 ۷ #۷ ما & هو ‎ooo‏ وگو و۱ ۳ ۱ اس اس ور سو راو 29 هم ه ه سب و ام ه سم ه ه ۵ اور ه ماه هر ‎N‏ ° ° S 0 le gb WW. بصورت زیر در مى ايد 

صفحه 17:
مه م ماه ‎MIN, BIN‏ 1 1 اماه ‎IN‏ ۵۱0| بس ۳۳ ه ه مب Ou ۵ 0 qd © © © 0 6۵ ۵ ۵ ee ey + ‏8ه‎ ‎3 ae 1 ‏م‎ ‎1 ob - : \yaHo 1 a ane 0 x Nea ۱ ye ۸ un از حل مدل با استفاده از ل ثانويه تابلو 

صفحه 18:


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

صفحه 20:
.لذا تابلو نهايى بصورت زير ‎S 5 SG b‏ و2 ۶6 9 15 28 و 11 11 گو 9 3 2 1 2 22 22 ‎o0-+ 3 o Jat‏ 2 22 22 1 1 0-2-1 2 9 :22 RIN © © 50 

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

صفحه 22:


برش گومری (برش کسری ) روش دیگری برای حل مدلهای برنامه ریزی عدد صحیح است. زمانی می توان از این روش استفاده کرد که مقادیر سمت راست ( ) biو ضرایب فنی( )aijهمگی صحیحح باشند .در این روش به منظور حل مدل صفحات برشی استفاه می شود .با استفاه از این صفحات ناحیه موجه به گونه ای برش داده می شود که او ً ال نقطه غایی مورد نظر تبدیل به عدد صحیح گردد و ثانیاًهیچ جواب عدد صحیحی هم در اثر برش از ناحیه موجه حذف نشود Max Z 14x1  18x2 s.t :  x1  3x2 6 7x1  x2 35 x1, x2 0,int; 9   x1   2   z 126  7  x2   2   x1 4    z 110 x  3  2  فرایند حل مساله به روش گومری )1مساله را صرفنظر از فرض صحیح بودن با استفاه از روش سیمپلکس حل کنید )2در صورتیکه مدل دارای جواب بهینه عدد صحیح باشد مساله به جواب بهینه عدد صحیح رسیده است در غیر این صورت محدودیت جدیدی که موجب عدد صحیح شدن جواب بهینه می شود به مدل اضافه نمائید. دستورالعمل اضافه کردن محدودیت جدید )2-1معادله معرف متغیر اساسی را که دارای مقدار کسری است انتخاب نمائید(.در صورتیکه بیش از یک معادله معرف وجوداشته باشد بهتر است آنرا نتخاب نمائید که دارای مقدار کسری برزرگتری است و اگر چند معادله دارای مقدار کسری بزرگ یکسانی باشد یکی را به دلخواه انتخاب کنید) )2-2معادله معرف انتخاب شده را به بخش صحیح و کسری تفکیک کنید .برای این منظور تابلو سیمپلکس زیر را در نظر بگیرید. به عنوان مثال در معادله فوق معادله iام معرف xi غیر صحیح است .بنابراین این معادله انتخاب و بصورت زیر نوشته می شود. ‏n ‏  ij yj ‏j 1 با توجه به اینکه ‏i و برخی از ‏xi  i  ‏ ij ها کسری هستند می توان آنها را بصورت زیر تفکیک کرد ‏ i  i   i ‏ ij   ij  ij ‏  به عبارت ديگر 0  i  1 و 0 ij  1 در تفکیک مقادیر; سمت راست و ضرایب متغیرهای غیر اساسی به دو قسمت صحیح و کسری از قاعده زیر; استفاده نمائید a 2 1 3 3 3 5 -2 2  (2 ) 5 1  4 [a] 2 3 f=a-[a] 0 0 3 5 -2 -3 0 -1 1 3 3 5 3 4 بنابراین می توان معادله مر بوط به محدودیت را که بصورت xi  i  n   ij yj j 1 است به شکل زیر در می آید xi [ i ]  i  n n j 1 j 1   ij  yj   ij yj n    xi  [ i ]    ij y j i  j 1 n  ij yj j 1 با توجه به صحیح بودن سمت چپ معادله سمت راست معادله می بایست صحیح باشد و از طرفی ‏n داریم. ‏ij yj  i  1 ‏j 1 ‏i  ‏n لذا شرط الزم برای صحیح بودن ‏ ij yj ‏j 1 ‏n آنست که : ‏ij yj 0 ‏j 1 ‏i  ‏i  این محدودیتی است که پس از استاندارد سازی می :بایست به مدل افزوده شود .لذا خواهیم داشت ‏n ‏ij yj 0 ‏j 1 ‏i  ‏n ‏  ij yj  i ‏j 1 ‏n ‏  ij yj  Sg   i ‏i ‏j 1 محدویت افزوده شده را اصطالح ًا برش کسری می نامند زیرا موجب برش بخشی از ناحیه موجه که .فقط جوابهای کسری در آن قرار دارد می شود همان;گون;ه ک;;ه م;الح;ظه م;یش;;ود ب;;ا ا;ضاف;ه ش;;ده; ا;ی;نم;حدود;ی;ت3- ش;;رط م;وج;ه ب;;ود;نن;;قضم;یش;;ود .ب;;;نابرا;ی;نم;یب;;ای;ستب;;ا ا;س;تفاد;ه; از ;ت;ید .س;;یمپلکسث;;انوی;ه م;دلح;لش;;ده; و ج;وا;بم;وج;ه ب;;;هینه ج;دید ب;;دس آ در ص;;ور;ت;یکه ج;وا;بب;;;هینه ج;دید ب;;دس;ت4- آ;مده; ع;دد ص;;حیح ب;;اشد ،ج;وا;بب;;;هینه ح;اص;ل ش;;ده; ا;س;تدر غ;یر ا;ی;نصور;تب;;;ه م;رح;له دو;م .ب;;رو;ید Max z 4x1  11x2 S.t : 2x1  x2 4 2x2  5x3 16 )1( مثال  x1  2x2 4 x j 0, Int Xb z x1 x2 s1 z 1 0 0 0 s1 0 0 0 1 x1 0 1 0 0 x2 0 0 1 0 s2 19 9 1  3 2 9 1 9 s3 2 9 4 3 5  9 2 9 b 104 3 4 1 1 3 2 2 3 با توجه به اینکه معادله معرف x2بیشترین مقدار کسری را دارد به عنوان معادله معرف انتخاب و محدودیت زیر افزوده می شود. 1 2 2 ‏ x1  ‏x2  9 9 3 1 2 2 ‏  x1  ‏x2  Sg1  9 9 3 .لذا تابلو نهایی بصورت زیر در می آید ‏b ‏Sgi 104 3 0 4 0 1 1 3 2 2 3 2 ‏ 3 0 0 1 ‏s3 2 9 4 3 5 ‏ 9 2 9 2 ‏ 9 ‏s2 19 9 1 ‏ 3 2 9 1 9 1 ‏ 9 ‏z ‏Xb ‏s1 ‏x2 ‏x1 ‏z 0 0 0 1 1 0 0 0 ‏s1 0 0 1 0 ‏x1 0 1 0 0 ‏x2 0 0 0 0 ‏Sgi پس از حل مدل با استفاده از سیمپلکس ثانویه تابلو زیر نشان دهنده جواب بهینه عدد صحیح است حاصل می شود. ‏b ‏Sgi ‏s3 ‏s2 ‏s1 ‏x2 ‏x1 ‏z 34 0 1 6 5 ‏ 2 1 9 ‏ 2 0 0 2 ‏ 1 1 2 0 1 2 0 1 0 0 0 0 1 0 ‏Xb ‏z ‏s1 0 0 1 0 ‏x1 0 1 0 0 ‏x2 0 0 0 0 ‏S3 3 2 3 0 0 1 Max z 14x1  18x2 S.t :  2x1  6 x2 12 )2( مثال 14x2  2x3 70 x j 0, Int; Xb z z x1 x2 1 0 0 x2 0 0 1 x1 0 1 0 s1 28 11 7 22 1  22 s2 15 11 1 22 3 22 b 126 1 3 2 1 4 2 با توجه به اینکه هر; دو مقدار کسری یکسانی دارند ،انتخاب هر دو معادله برای تعریف شرایط یکسانی برای انتخاب دارند ،در هر صورت معادله اول برای تعریف محدویت برشی انتخاب می شود 7 1 1 ‏x2  (0 )s1  (0 )s2 3 22 22 2 7 1 1 ‏  ‏S1  ‏S2  Sg1  22 22 2 .لذا تابلو نهایی بصورت زیر در می آید ‏b 126 1 3 2 1 4 2 1 ‏ 2 ‏s1 ‏s2 ‏sg1 28 15 0 11 11 7 1 0 22 22 1 3 ‏ 0 22 22 7 1 ‏ ‏ 1 22 22 ‏x2 ‏z x1 0 1 0 ‏Xb ‏z 1 0 0 ‏x2 0 1 0 ‏x1 0 0 ‏sg1 0 با حل مدل به روش سیمپلکس ثانویه تابلو زیر .حاصل خواهد شد