دانلود فایل مسائل برنامه ريزي خطي، تحقيق در عمليات

توضیحات تکمیلی

دانلود فایل مسائل برنامه ريزي خطي، تحقيق در عملياتاین فایل در قالب فرمت word قابل ویرایش ، آماده پرینت و استفاده میباشدبه نام خداوند متعالتحقيق در عمليات ۱مقدمهبرنامه‌ريزي خطي با بهينه‌سازي (ماكزيمم يا مينيمم) يك تابع خطي كه از محدوديت‌هاي مساوي يا نامساوي يا ضمني تشكيل شده است، سروكار دارد. مساله برنامه‌ريزي خطي را ابتدا جرج.بي.دانتزيك در سال ۱۹۴۷ ابداع كرد. اگرچه ال.دي.كانترويچ مساله‌اي از اين نوع كه با سازمان‌دهي و برنامه‌ريزي ارتباط پيدا مي‌كرد را در سال ۱۹۳۹ فرمول‌بندي كرده بود، ولي كار او تا سال ۱۹۵۹ ناشناخته باقي ماند. بنابراين مبتكر اصلي برنامه‌ريزي خطي به طور كلي جرج دانتزيك معرفي شد.در سال ۱۹۴۹ جرج.بي.دانتزيك «روش سيمپلكس» را براي حل برنامه‌ريزي خطي به چاپ رساند. از آن زمان به بعد افراد زيادي به روش‌هاي بسيار متعددي از جمله بسط و توسعه نظري، ديدگاه محاسباتي و بكارگيري كاربردهاي جديد آن، در اين حوزه وارد شدند. روش سيمپلكس به دلايل:۱٫ توانايي مدل‌بندي مسائل مهم و پيچيده مديريتي؛۲٫ توانمندي حل مسائل در مدت زمان معقول در برنامه‌ريزي خطي كاربردهاي وسيعي دارد.مدل‌بندي و مثال‌هاي برنامه‌ريزي خطيبه طول كلي مراحل مهمي كه يك تيم تحقيق در عمليات بايستي طي نمايد، عبارتند از:۱٫ تعريف مساله۲٫ ساختن مدل۳٫ حل مدل۴٫ معتبر بودن مدل۵٫ اجراي نتيجه‌ نهايي «اتخاذ تصميم»مهمترين نوع از انواع مدل‌هاي تحقيق در عمليات، مدل رياضي مي‌باشد. در نوشتن اين نوع مدل‌ها، فرض بر اين است كه متغيرها كميت‌پذيرند. بنابراين علائم رياضي را جهت نمايش متغيرها بكار مي‌رود كه بوسيله توابع رياضي به هم مربوط مي‌شود و مدل به وسيله الگوريتم مناسبي حل مي‌شود.ساختار مدل رياضي ۱٫ متغيرهاي تصميم۲٫ محدوديت‌ها «قيدها»۳٫ تابع هدفانواع مدل‌هاي رياضي كه در «R» (تحقيق در عمليات) استفاده مي‌شود:۱٫ مدل برنامه‌ريزي خطي۲٫ مدل برنامه‌ريزي پويا۳٫ مدل صف۴٫ مدل كنترل موجودي‌ها۵٫ مدل شبيه‌سازيبرنامه‌ريزي خطي يك مدل رياضي براي تحقيق در عمليات است.مساله۱٫ يك كارخانه مي‌خواهد برنامه‌اي براي توليد وسايل آشپزخانه داشته باشد. براي ساختن اين وسايل كارخانه به داده خام و نيروي انساني نيازمند است و مي‌خواهد سه نوع كالا از نوع A, B و C توليد كند. اطلاعات داده شده در جدول زير در اختيار كارخانه مي‌باشد. حداكثر در روز مي‌توان ۲۰۰ كيلوگرم ماده خام تهيه نموده و حداكثر نيروي انساني موجود ۱۵۰ نفر ساعت در روز مي‌باشد. مديريت كارخانه مي‌خواهد طوري تصميم بگيرد كه بيشترين سود را داشته باشد. مساله را به صورت برنامه‌ريزي خطي فرموله كنيد.C B A 6 3 7 كارگر «نفر ساعت»۵ ۴ ۴ ماده خام «كيلوگرم»۳ ۲ ۴ سود حاصل از فروش «دلار»تعداد واحدهاي كالاي نوع A xC:متغيرهاي تصميمتعداد واحدهاي كالاي نوع B xB تعداد واحدهاي كالاي نوع C xAمحدوديت مربوطبه نيروي انساني ۷xA+3xB+6xC≤۱۵۰:محدوديت‌هامحدوديت مربوط به ماده خام ۴xA+4xB+5xC≤۲۰۰ محدوديت xA+xB+xC≥۰Max Z=4xA+2xB+3xC: تابع هدف «ماكزيمم سود»مرتب كردن: اول تابع هدف و بعد قيدها۷xA+3xB+6xC≤۰S.T. 4xA+4xB+5xC≤۰xA, xB, xC≥۰۲٫ يك كارخانه كاغذسازي سه سفارش براي تهيه توپ‌هاي كاغذي «مشابه توپ پارچه» كه طول و عرض آنها در جدول زير داده شده است، دريافت مي‌كند. در اين كارخانه توپ‌هاي كاغذي در دو عرض استاندارد ۱۰ دسي‌متر و ۲۰ دسي‌متر توليد مي‌شود كه بايد به اندازه‌هايي كه در سفارش‌ها مشخص شده، بريده شوند. براي طول توپ‌هاي استاندارد محدوديتي نيست، زيرا از لحاظ علمي، توپ‌هاي با طول محدود مي‌توانند به هم وصل شوند و توپ‌هاي موردنظر را بوجود آورند. به فرم برنامه‌ريزي خطي فرموله كنيد.طول (دسي‌متر) عرض (دسي‌متر) شماره سفارش۱۰۰۰۰ ۵ ۱۳۰۰۰۰ ۷ ۲۲۰۰۰۰ ۹ ۳حل: هدف عبارت است از تعيين آن طرح برش كه ضمن كمينه ساختن ضايعات برش تقاضاي موردنظر را برآورده سازد.۲۰dm 10dm x26 x25 x24 x23 x22 x21 x13 x12 x11 عرض سفارش۰ ۰ ۱ ۲ ۲ ۴ ۰ ۰ ۲ ۵۰ ۱ ۲ ۰ ۱ ۰ ۰ ۱ ۰ ۷۲ ۱ ۰ ۱ ۰ ۰ ۱ ۰ ۰ ۹۲ ۴ ۱ ۱ ۳ ۰ ۱ ۳ ۰ عرض ضايعاتx12: كاغذ اول برش ۲x21: كاغذ دوم برش ۱متغيرهاي تصميم xij≥۰J=1,2,3,…,۶ i=1,2xij: طول كاغذ iام با استفاده از برش jام؛S1: كاغذي كه عرض آن ۵dm و مازاد بر نياز؛S2: كاغذي كه عرض آن ۷dm و مازاد بر نياز؛S3: كاغذي كه عرض آن ۹dm و مازاد بر نياز؛فرموله كردن مساله:۲xu+4×21+2×22+2×23+2×24-S1=10000x12+x22+x24+x25-S2=30000x13+x23+x25+x26-S3=20000تابع هدف «مينيمم ضايعات»Min Z: 3×12+ x13+ 3×22+ x23+ x24+ 4×25+ 2×26+5S1+7S2+9S3مرتب كردن:Min Z: 3×12+ x13+ 3×22+ x23+ x24+ 4×25+ 2×26+5S1+7S2+9S32×11+ 4×21+ 2×22+ 2×23+ x24-S1=10000S.T. x12+ x22+ x24+ x25-S2=30000x13+ x23+ x25+ x26-S3=20000xij≥۰, i=1.2, j=1, 2, …, ۶۳٫ كشاورزان يك منطقه زراعي تصميم دارند كه عمليات كاشت، داشت و برداشت را به شكل تعاوني انجام دهند تا از قابليت‌هاي ديگر و امكانات دولتي استفاده كنند و توليد جمعي را افزايش دهند. اين منطقه از سه مزرعه تشكيل شده است. دو عامل زمين و آب امكانات كاشت اين مزارع را محدود مي‌كند كه اطلاعات مربوط به آب و زمين قابل كشت در جدول زير آمده است:آب موجود (هزار مترمكعب) زمين قابل كشت (هكتار) مزرعه۶۰۰ ۴۰۰ ۱۸۰۰ ۶۰۰ ۲۳۷۵ ۳۰۰ ۳محصولات مناسب كشت در اين منطقه زراعي عبارت است از:چغندرقند، پنبه و ذرت. ميزان عملكرد در هكتار و آب مورد نياز اين سه محصول با يكديگر متفاوتند. به علاوه براي رسيدن به تركيب مناسب از سه محصول كاشت هم محصول نمي‌توانند از يك مقدار مشخص بيشتر باشد. اين اطلاعات در جدول زير آمده است:سود حاصل از فروش (هكتاري) مصرف آب در هكتار (هزارمترمربع) حداكثر كشت (هكتار) محصول۴۰۰ ۳ ۶۰۰ چغندرقند۳ ۲ ۵۰۰ پنبه۱۰۰ ۱ ۳۲۵ ذرتكشاورزان توافق كردند كه نسبت زمين كاشته شده به زمين موجود براي هر سه مزرعه مساوي باشد، اما محدوديتي در مورد تركيب كشت محصولات در هر يك از سه مزرعه وجود ندارد. اكنون مي‌خواهيم با توجه به محدوديت‌هاي فوق، ميزان سود جمعي را ماكزيمم كنيم. مساله را به فرم برنامه‌ريزي خطي فرموله كنيد.حل:xij: زمين كاشته شده از محصول iام در مزرعه jام.ذرت پنبه چغندرقند زمينx13 x12 x11 1x23 x22 x21 2x33 x32 x31 3تابع هدف:Max Z: 400(x11+ x12+x13) + 300 (x21+ x22+ x23) + 100 (x31+ x32+ x33)قيد مربوط به زمين قابل كشت:x11+ x12+ x13≤۴۰۰x21+ x22+ x23≤۶۰۰x31+ x32+ x33≤۳۰۰قيد مربوط به آب موجود۳×۱۱+ ۲×۱۲+x13≤۶۰۰۳×۲۱+ ۲×۲۲+ x23≤۸۰۰۳×۳۱+ ۲×۳۲+ x33≤۳۷۵قيد مربوط به حداكثر كشتx11+ x21+ x31≤۶۰۰x12+ x22+ x32≤۵۰۰x13+ x23+ x33≤۳۲۵قيد مربوط به توافق تساوي(x11+ x12+x13)/400=(x11+ x21+ x31)/600(x11+ x12+x13)/400=(x31+ x32+ x33)/300(x21+ x22+ x23)/600=(x31+ x32+ x33)/300xij ≥ ۰۴٫ يك كارخانه توليدي ۵ ماشين رنگ‌كاري و يك ماشين پرس دارد كه اين ماشين‌ها براي ساختن دو نوع محصول A و B بكار برده مي‌شوند.با تركيب يك واحد از A و يك واحد از B يك محصول جديد بدست مي‌آيد كه محصول نهايي C نام دارد. بهره‌دهي «راندمان» هر كدام از ماشين‌ها براي محصول A و B در جدول زير داده شده است:رنگ كاري (دقيقه) پرس (دقيقه) محصول۲۰ ۳ A15 5 Bصاحب كارخانه مي‌خواهد توازني روي بار ماشين‌ها داشته باشد. به اين صورت كه هيچ كدام از ماشين‌ها، «رنگ‌كاري و پرس» در روز نيم ساعت بيش از ديگر ماشين‌ها كار نكرده باشد. فرض بر اين است كه كار انجام شده در ماشين پرس به طور يكنواخت به ماشين‌هاي ديگر براي رنگ‌كاري داده مي‌شود. هدف مدير كارخانه در مدت ۸ ساعت كار روزانه، ماكزيمم كردن محصولات C مي‌باشد. مساله را به صورت برنامه‌ريزي خطي فرموله كنيد.حل:متغيرهاي تصميم:xA≥۰ A تعداد محصول نوعxB≥۰ B تعداد محصول نوعxC≥۰ C تعداد محصول نوعمحدوديت مربوط به پرس: ۳xA+5xB ≤ ۸/۶۰=۴۸۰محدوديت مربوط به رنگ‌كاري: (۲۰xA+15xB)/5 ≤ ۴۸۰  ۴xA+3xB ≤ ۴۸۰محدوديت مربوط به كار نكردن بيش از نيم ساعت:|(۳xA+5xB)-(4xA+3xB)| ≤ ۳۰  |-xA+2xB|≤۳۰ -xA+2xB≤۳۰-xA+2xB≥-۳۰ *(-) xA-2xB≤۳۰xA و xB وابسته به xC = min{xA,xB}  xC≤xA  xC-xA≤۰xC≤xB  xC-xB ≤۰مرتب كردن:تابع هدف : Max Z = xCS.T:3xA+5xB ≤ ۴۸۰۴xA+3xB ≤ ۴۸۰-xA+2xB ≤ ۳۰xA-2xB ≤ ۳۰xC-5xA ≤ ۰xC-xA ≤ ۰xA,xB,xC ≥ ۰۵٫ يك شركت توليد كننده تلويزيون تصميم دارد تلويزيون سياه و سفيد و رنگي توليد كند. ارزيابي بازار نشان مي‌دهد كه حداكثر مي‌توان ۱۰۰۰ تلويزيون رنگي و ۴۰۰۰ تلويزيون سياه و سفيد در ماه فروش داشت. ماكزيمم تعداد نفر ـ ساعت موجود در هر ماه ۵۰۰۰۰ است. يك تلويزيون رنگي ۲۰ نفر ـ ساعت و يك تلويزيون سياه و سفيد ۱۵ نفر ـ‌ ساعت وقت مي‌گيرد. سود حاصل از تلويزيون رنگي و سياه سفيد به ترتيب ۶۰ و ۳۰ دلار است. مي‌خواهيم تعداد تلويزيون‌هايي را پيدا كنيم كه شركت بايد از هر نوع توليد كند تا سود آن ماكزيمم شود. مساله را فرمول‌بندي كنيد.حل: xi: تعداد تلويزيون‌هاي نوع iام كه بايد توليد شوند. x1: تعداد تلويزيون‌هاي رنگي x2: تعداد تلويزيون‌هاي سياه و سفيدمرتب كردن مسالهMax Z: 60×1 + 30×220×1+15×2≤۵۰۰۰۰x1 ≤ ۱۰۰۰x2 ≤ ۴۰۰۰x1, x¬۲ ≥ ۰۶٫ يك مدير توليد زمان‌بندي سه محصول روي چهار ماشين را برنامه‌ريزي مي‌كند. هر محصول مي‌تواند با هر ماشين توليد شود. هزينه توليد هر واحد (بر حسب دلار) چنين است:۴ ۳ ۲ ۱ ماشينمحصول۷ ۵ ۴ ۴ ۱۶ ۵ ۷ ۶ ۲۱۱ ۸ ۱۰ ۱۲ ۳زمان لازم (بر حسب ساعت) براي توليد هر واحد محصول در هر ماشين در جدول زير آمده است.۴ ۳ ۲ ۱ ماشينمحصول۲/۰ ۲/۰ ۲۵/۰ ۳/۰ ۱ ۲۵/۰ ۲/۰ ۳/۰ ۲/۰ ۲۵/۰ ۶/۰ ۶/۰ ۸/۰ ۳فرض كنيد كه ۴۰۰۰، ۵۰۰۰ و ۳۰۰۰ واحد از محصولات مورد نياز است و نيز ماشين ـ ساعت موجود به ترتيب ۱۵۰۰، ۱۲۰۰، ۱۵۰۰ و ۲۰۰۰ باشد. مساله را به صورت يك برنامه خطي فرمول‌بندي كنيد.حل: xij: تعداد محصول iام كه توسط ماشين jام بايد توليد گردد.Min Z: 4×11+ 4×12+ 5×13 +7×14+ 5×23+ 6×24 +12×31+ 10×32+ 8×33+ 11×34محدوديت زماني هر ماشين:۰٫۳×۱۱+ ۰٫۲×۲۱+ ۰٫۸×۳۱≤۱۵۰۰۰٫۲۵×۱۲+ ۰٫۳×۲۲ +۰٫۶×۳۲≤۱۲۰۰۰٫۲×۱۳+ ۰٫۲×۲۳+ ۰٫۶×۳۳≤۱۵۰۰۰٫۲×۱۴+ ۰٫۲۵×۲۴+ ۰٫۵×۳۴≤۲۰۰۰محدوديت توليد هر محصولx11+ x12+x13+x14=4000x21+ x22 +x23 +x24=5000x31 +x32 +x33 +x34=3000xij≥۰i=1, 2, 3, j=1, 2, 3, 41-3 حل هندسي مساله‌هامثال: مساله برنامه‌ريزي خطي زير را به روش هندسي «ترسيمي» حل كنيد.Max Z: 3×1+5×21) x1≤۴۲) ۲×۲≤۱۲S.T: 3) 3×1+2×2≤۱۸۴) x¬۱≥۰۵) x2≥۰Z=3i+5j (/۲) ۳/۲i+5/2j نقطه A از برخورد ۲ و ۳:x2=63×1+2×2=18, → x1=2 A=|2, 6 ZA=36نقطه B از برخورد ۱ و ۳:x1=43×1+2×2=18, → x2=3 B=|4, 3 ZB=27نقطه C از برخورد ۲ و ۴:x2=6x1=0 C=|0, 6 ZC=30نقطه A جواب است.مثال: مساله برنامه‌ريزي خطي زير را به روش هندسي حل كنيد.Max Z: 2×1+3×21) x1+x2≤۲S.T 2) 4×1+6×2≤۹۳) x1, 4) x2≥۰نقطه A از برخورد ۲ و ۳:۴×۱+۶×۲=۹ x1=0 → x2=3/2 A|0, 3/2 ZA=9/2نقطه B از برخورد ۱ و ۲x1+x2=2 → x1=3/2 4×1+6×2=9 → x2=1/2 B|3/2, 1/2 ZB=9/2نقاط A و B هر دو جواب هستند.۲-۱ فضاي اقليدسيتركيبات خطيبرداي را تركيب خطي از بردارهاي a1, a2, …, ak گوييم هرگاهبه علاوه اين تركيب را به تركيب آنين گويند. اگر علاوه بر موارد بالا داشته باشيم:زيرفضاي خطيمجموعه را يك زيرفضاي خطي En گويند اگر:و همينطور را يك فضاي آنين En گويند اگر:استقلال خطي بردارهابردارهاي را مستقل خطي گوييم اگر:به علاوه بردارها وابسته خطي هستند اگر مستقل نباشند. يعني:مجموعه موادمجموعه كه يك مجموعه مواد براي En را بتوان تركيب خطي از اعضاي مجموعه مولد نوشت. مثال:وابسته خطي‌اند:پايه براي En:يك پايه براي En مجموعه‌اي از بردارهاي مي‌باشد، به طوري كه:۱٫ اين مجموعه يك مجموعه مولد باشد.۲٫ اين مجموعه مستقل خطي باشد.n = بعد فضاي En  {تعداد اعضاي پايه}= بعد يك فضا۲-۲ ماتريس‌هاماتريس An*n را يك ماتريس بالا مثلثي گوييم اگر درايه‌هاي پايين قطر اصلي صفر باشد. همين‌طور پايين مثلثي گوييم اگر درايه‌هاي بالامثلثي قطر اصلي صفر باشد.بالا مثلثي پايين مثلثي ماتريس‌هاي اندازه شده بلوكيعمليات سطري مقدماتي پله‌كاني:۱٫ سطح iام را با سطر jام تعويض مي‌كنيم.۲٫ سطر iام را در اسكالر λ ضرب مي‌كنيم.۳٫ سطح iام را با سطح iام به علاوه λ سطح jام تعويض مي‌كنيم.مثال:دستگاه زير را حل كنيد.ماتريس معكوسزماني ماتريس معكوس دارد كه:مثالمعكوس ماتريس زير را بدست آوريد.تعريف: ماتريس Am*n مفروض است:الف) رتبه سطري ماتريس A، تعداد سطرهاي مستقل خطي A مي‌باشد.ب) رتبه ستوني ماتريس A، تعداد ستون‌هاي مستقل خطي A مي‌باشد.ج) رتبه ستوني ماتريس A = رتبه سطري ماتريس A = رتبه ماتريس ARank A ≤ min{m,n}ماتريس Am*n را رتبه كامل گويند اگر:Rank A = min{m,n}تذك‍ر: دستگاه Am*n=b مفروض است:الف) اگر rank(A) ب) اگر rank(A) = rank (A|b)=n آنگاه دستگاه داراي جواب منحصر به فرد است.ج) اگر rank(A) = rank (A/b)۲-۳ مجموعه محدبمجموعه X در En را يك مجموعه محدب گويند اگر به ازاي هر دو نقطه x2, x1 در X به آنگاه به ازاي داشته باشيم:كه در آن تركيب را يك تركيب محدب گوييم و آن را محدب اكيد مي‌ناميم اگر: .از نظر مهندسي هر نقطه به صورت يك نقطه از پاره خطي است كه x1 را به x2 در En وصل مي‌كند.مثال:نشان دهيد مجموعه‌هاي زير محدب هستند.پس S محدب است.تعريف نطقه راسي يا گوشه‌اي: يك نقطه x در مجموعه محدب X نقطه راسي گفته مي‌شود. اگر x را نتوان به صورت محدب درآورد، دو نقطه متمايز در X بنويسيم.X نقطه راسي است اگر:۳-۲ جواب‌هاي شدني پايهسيستم مفروض است كه در آن Rank(A)=rank(A|b)=m. بعد از تغيير ترتيب ستون‌هاي ماتريس A در صورت لزوم فرض كنيد Am*n[B,N] كه در آن Bm*n يك ماتريس معكوس‌پذير باشد. در اين صورت يك جواب دستگاه AX=b است، زيرا:كه‌ آن را يك جواب پايه‌اي براي دستگاه گوييم. Bm*m را ماتريس پايه و Nm*(n-m) را ماتريس غيرپايه دستگاه گوييم. اگر XB=B-1b≥۰ باشد. جواب فوق را يك جواب پايه‌اي شدني گوييم.حال اگر يكي از مولفه‌هاي XB=B-1b دقيقاً صفر باشد، آن را يك جواب پايه‌اي شدني —– گوييم.مثال:مجموعه محدب زير مفروض است. جواب‌هاي (نقاط) پايه‌اي شدني آن را بدست آوريد.(ماتريس ۴×۲ است. بايد دنبال ماتريس ۲×۲ معكوس‌پذير بگرديم. چون دو تا سطر داريم و دنبال ۲ تا ستون مي‌گرديم).مساله مفروض است، به طوري كه:rank(A)=rank(A|b)=m.جواب شدني:نقطه X را يك جواب شدني براي Lp گوييم اگر در محدوديت‌هاي مساله صدق كند. يعني:مجموعه نقاط شدني مساله Lp را با S نمايش داده و اگر باشد، آنگاه مساله را شدني گوييم.جواب بهينه:جواب شدني X* را يك جواب بهينه براي Lp گوييم اگر:تعريف:مساله Lp نامتناهي است، اگر:تعريف:مساله Lp را ناشدني گوييم اگر ناحيه جواب آن تهي باشد.مساله Lp داراي جواب بهينه دگرين است اگر حداقل داراي ۲ جواب بهينه باشد.قضيهدر مساله Lp، اگر جواب شدني وجود داشته باشد، در اين صورت حتماً يك جواب پايه‌اي شدني وجود دارد.قضيه:مجموعه نقاط راسي با مجموعه نقاط پايه‌اي شدني متناظر است. اگر مساله Lp شدني باشد، آنگاه مجموعه نقاط راسي (مجموعه نقاط پايه‌اي شدني) ناتهي است.قضيه:به ازاي هر نقطه راسي يك جواب پايه‌اي شدني وجود دارد، ولي نه لزوماً منحصر به فرد.حل مساله Lp:يعني سطرهاي مستقل خطي باشند.CBT: ضريب متغيرهاي مربوط به XBCNT: ضريب متغيرهاي مربوط به XN(انديس متغيرهاي غيرپايه‌اي)سود متغير غيرپايه‌ايتذكر: ۱٫ در مساله‌ي Lp فوق با جواب پايه‌اي شدني كه R مجموعه انديس‌هاي ستون‌هاي غيرپايه‌اي باشد، براي بهتر نمودن مقدار تابع هدف كافي است انديسي از R را پيدا كنيم به طوري كه:در اين صورت با افزايش متغير xk «متغير غيرپايه‌اي نظير» از روند زير به تكرار بعدي مي‌رويم:بديهي است اگر انديس k با Zk-Ck>0 مولفه‌هاي بردار yk≤۰ باشد.۲٫ براي مساله Lp با جواب پايه‌اي شدني فرض كنيد تكرار فعلي، بهينه باشد. يعني:اما اگر انديسي مثل يافت شود يا موجود باشد، به طوري كه Zk-Ck=0 در اين صورت —- يعني:به جواب بهينه دگرين رسيده‌ايم.نكته:ماتريس پايه جديد در يك ستون با ماتريس قبلي اختلاف دارند.شرط اينكه ماتريس يك ماتريس پايه جديد باشد اين است كه .۳-۳ الگوريتم روش سيمپلكسگام اول: پايه شدني B داده شده است.گام دوم: قرار مي‌دهيم: يك جواب پايه‌اي شدني.گام سوم: قرار مي‌دهيم: گام چهارم: اگر آنگاه جواب پايه‌اي شدني فعلي بهينه است و توقف كن. در غيراينصورت قرار مي‌دهيم:گام پنجم: قرار مي‌دهيم اگر اين مقدار پيدا نشده، يعني (yik≤۰) مساله Lp نامتناهي است و توقف كن.تذكر: براي مساله Lp استاندارد با تابع هدف max كافيست گام چهارم را تغيير دهيم.گام ششم: ماتريس پايه جديد را در B قرار بده و به گام اول ببر.روش سيمپلكس در جدول.Z XB XN RHS1 -CBT -CNT 00 B N bZ xB1… xBr … xBm xj …………xk RHS1 0 0 0 Zj-Cj Zk-Ck CBTB-1b0 1 0 0۰ ۱ ۰۰ ۰ ۱ y1j y1kyrj yrkymj ymk b1brbmپاشنه حتماً بايد يك باشد و بالا و پايين آن حتماً صفر باشد.مثال:مساله Lp زير را به روش سيمپلكس حل كنيد.فرم استانداردRHs x1 x2 s1 s2 Z0 0 0 3 1 16۱ ۲ ۳ ۱ ۰-۱ ۱ ۰ ۱ ۰-۳ ۴ ۰ ۰ -۳ ۱۳۱ ۵ ۰ ۱ -۳-۱ ۱ ۰ ۱ ۰-۲۷/۵ ۰ -۴ -۴/۵ -۳/۵ ۱۳/۵۸/۵ ۱ ۰ ۱/۵ -۳/۵۰ ۱ ۱/۵ ۲/۵ ۰چون متغيرهاي سود همه صفر و يا منفي شدند، تكرار بهينه است.CBT: ضرايب متغيرهاي پايه در تابع هدفCi: ضريب xiها در Z.x1 مقدار x2 مقدار s1 مقدار s2 مقدارفرم استانداردRHs x1 x2 x3 s1 s2 s3 Z0 -1 -1 4 0 0 0 1924 1 1 2 1 0 01 1 -1 0 1 0-1 1 1 0 0 1 0-16 3 -5 0 0 0 -4 1164 3 -1 0 1 0 -20 2 0 0 1 0-۱ ۱ ۱ ۰ ۰ ۱ ۰-۱۷ ۰ -۴ ۰ -۱ ۰ -۲ ۱۱/۳۶۱۳/۳ ۱ -۱/۳ ۰ ۱/۳ ۰ -۲/۳۰ ۲ ۰ ۰ ۱ ۰۰ ۲/۳ ۱ ۱/۳ ۰ ۱/۳ ۱Z مقدار x1 مقدار x2 مقدار x3 مقدارفرم استانداردRHs x1 x2 s1 s2 s3 Z0 -5 -4 0 0 0 16415 1 2 1 0 0-2 1 0 1 05 3 0 0 1 015 0 -1 0 0 1 13103 0 7/5 1 0 -1/50 11/5 0 1 2/51 3/5 0 0 1/5 012/7 0 0 5/7 0 6/7 115/7۳۷/۷۱۲/۷ ۰ ۱ ۵/۷ ۰ -۱/۷۰ ۰ -۱۱/۷ ۱ ۵/۷۱ ۰ -۳/۷ ۰ ۲/۷ ۰Z مقدار x1 مقدار x2 مقدارفرم استانداردRHs x1 x2 x3 s1 s2 s3 Z0 -1 2 -1 0 0 0 11269 1 2 1 1 0 02 1 -1 0 1 0-1 3 0 0 0 1 03 0 5/2 -3/2 0 1/2 0 19312 0 3/2 3/2 1 -1/2 01 1/2 -1/2 0 1/2 00 7/2 -1/2 0 1/2 1 012 0 4 0 1 0 0 16615 0 1 1 2/3 -1/3 01 1 0 1/3 1/3 00 4 0 1/3 1/3 1 0Z مقدار x1 مقدار x2 مقدار x3 مقدار تذكر: براي حل مساله Lp با تابع هدف max، روش سيمپلكس دقيقاً مشابه مساله min است، با اين تفاوت كه معيار متغير ورودي به صورت زير تغيير مي‌كند:۴-۱ روش دو فازيفاز I:فاز II:هدف ما در اين است كه يك جواب پايه‌اي شدني براي مساله اصلي پيدا كنيم و متغيرهاي مصنوعي را حذف نماييم.تحليل روش دو فازيالف) اگر در پايان فاز I متغيرهاي مصنوعي با مقدار صفر باشند، در اين صورت دو حالت زير را داريم:۱٫ متغيرهاي مصنوعي در پايان فاز I خارج پايه هستند. «غيرپايه‌اي» در اين صورت بدون هيچ مشكل وارد فاز II مي‌شويم.۲٫ متغيرهاي مصنوعي در پايان فاز I پايه‌اي هستند با مقدار صفر (جواب تباهيده داريم). در اين صورت قبل از اينكه وارد فاز II بشويم، بايد متغيرهاي مصنوعي با مقدار صفر را از پايه توسط متغيرهاي غيرپايه‌اي غيرمصنوعي خارج كنيم. اگر توانستيم اين كار را انجام دهيم (تمام —– صفر باشند)، قيد را بايد حذف كنيم.ب) اگر در پايان فاز I متغيرهاي مصنوعي با مقدار غير صفر در پايه بهينه باشد، در اين صورت مساله اصلي ناشدني است. زيرا:برهان خلف: فرض كنيم مساله اصلي شدني باشد، يعني:مثال:مساله Lp زير را به روش فازي حل كنيد.فرم استانداردفاز I:RHs x1 x2 s1 s2 s3 R1 R2 Z3 1 2 -1 -1 0 0 0 1213 1 1 -1 0 0 1 0-1 1 0 -1 0 0 10 1 0 0 1 0 0 0۱ ۲ ۰ -۱ ۱ ۰ ۰ -۲ ۱۱۱۲ ۲ ۰ -۱ ۱ ۰ ۱ -۱-۱ ۱ ۰ -۱ ۰ ۰ ۱۱ ۰ ۰ ۱ ۱ ۰ -۱ ۰۰ ۰ ۰ ۰ ۰ ۰ -۱ -۱ ۱۱/۲۳/۲۳/۲ ۱ ۰ -۱/۲ ۱/۲ ۰ ۱/۲ -۱/۲۰ ۱ -۱/۲ -۱/۲ ۰ ۱/۲ ۱/۲۰ ۰ ۱/۲ ۱/۲ ۱ -۱/۲ -۱/۲ ۰فاز دوم:RHs x1 x2 s1 s2 s3 R1 R2 Z-5/2 0 0 1/2 3/2 0 11/23/23/2 1 0 -1/2 1/2 0 1/2 -1/20 1 -1/2 -1/2 0 1/2 1/20 0 1/2 1/2 1 -1/2 -1/2 0-4 -3 0 2 0 0 1121 2 0 -1 1 0 1 -11 1 -1 0 0 1 0-۱ ۰ ۱ ۰ ۱ -۱ ۰ ۰-۶ -۱ ۰ ۰ ۰ -۲ ۱۲۳۱ ۱ ۰ ۰ ۱ ۱ ۰ -۱۰ ۱ ۰ ۰ ۱ ۰ ۰-۱ ۰ ۱ ۰ ۱ -۱ ۰ ۰