مدل حمل و نقل

صفحه 1:
۰ دانشگاه آزاد اسلامی واحد تهران جتوب 

صفحه 2:
1 ١ مدل ‎Siig cos‏ ™ مدل برنامه ریزی خطی حمل و نقل 2 یافتن یک جواب آغازین برای حل * مدل ويزه حمل و نقل مقايسه با روش سيميلكس * تباهيدكى در مدل حمل و نقل < مسأله تخصیص «واگذاری) 

صفحه 3:
روش حل مسائل حمل و نقل ل مسائل حمل و نقل. در ابتدا یک جواب اولیه برای مسئله بدست می آید و سپس این جواب اولیه را بهینه می کنیم ۱ ‏رمشيله سنك.1‎ (Dette th aie shy | رمشت ونیعت- عیلشده .2 

صفحه 4:
نکات اولیه أولين مرحله.در حل مسائل حمل:وائقل: آماذه سازى مسهلة كه شامل © نكتة اسث» ‎٠‏ مجموع تقاضاها و ظرفيت ها بايد برابر باشد اللف- اكر ظرفيتها بیشتر از تقاضاها بودنده باید یک ستون مجازی با هزینه های صفر تشکیل داد ظرفیت 3 2 1 15 12 24 400 500=400- 2 7 8 15 300 900 3 27 18 21 200 00 100 200 100 تقاضا 

صفحه 5:
نکات اولیه أولين مرحله.در حل مسائل حمل:وائقل: آماذه سازى مسهلة كه شامل © نكتة اسث» مجموع تقاضاها و ظرفيت ها بايد برابر باشد اللف- اكر ظرفيتها بیشتر از تقاضاها بودنده باید یک ستون مجازی با هزینه های صفر تشکیل داد ظرنیت ‏ 4 3 2 1 400 0 24 12 15 1 300 0 15 8 7 2 200 0 21 18 27 900 500 100 200 100 تقاضا 

صفحه 6:
نکات اولیه ب- اگر تقاضاها بیشتر از ظرفیتها بودند. باید یک سطر مجازی با هزینه های صفر | تشکیل داد 1 2 3 oe 1 15 12 24 100 400=250- 2 7 8 15 100 650 3 27 18 50 21 تقاضا 50 650 100 50 500 

صفحه 7:
نکات اولیه | تشکیل داد ظرفیت 3 100 24 100 15 50 21 0 00 100 650 650 12 18 50 15 27 500 ب- اگر تقاضاها بیشتر از ظرفیتها بودند. باید یک سطر مجازی با هزینه های صفر عر دم ب 75 

صفحه 8:
روش حل حمل و نقل برای مسائل از نوع کمینه (هزینه) است اگر اعداد داخل جدول برای مسائل از نوع بیشینه (سود) بود فقط کافی است اعداد داخل جدول را قبل از حل در یک منقی ضرب نمود 15 12 24 100 2 7 8 15 100 3 27 18 21 50 50 250 50 50 150 تقاضا 

صفحه 9:
روش حل حمل و نقل برای مسائل از نوع کمینه (هزینه) است اگر اعداد داخل جدول برای مسائل از نوع بیشینه (سود) بود فقط کافی است اعداد داخل جدول را قبل از حل در یک منقی ضرب نمود 

صفحه 10:
اگر در مسئله حمل و نقل نتوان میدای را به مقصدی تخصیص داد باید به جای هزینه آن . عدد ]1 را قرار داد. * در مثال زیر فرض کنید میدا ۳ را نتوان به مقصد ۲ تخصیص داد ظرفیت 3 2 1 1 15 12 24 100 7 8 15 100 3 27 18 21 50 50 250 50 50 150 تقاضا 

صفحه 11:
اگر در مسئله حمل و نقل نتوان میدای را به مقصدی تخصیص داد باید به جای هزینه آن . عدد ]1 را قرار داد. * در مثال زیر فرض کنید میدا ۳ را نتوان به مقصد ۲ تخصیص داد ظرفیت 3 2 1 1 15 12 24 100 7 8 15 100 3 27 M 21 50 50 250 50 50 150 تقاضا 

صفحه 12:
در تمامی روشهای محاسبه جواب اولیه. هرگاه یک سطر یا یک ستون باقی ماند. باید به تمامی خانه های آن سطر یا ستون .مربوطه مقدار تخصیص داد از اينروء برای شروع مقداردهی از خانه با کمترین هزینه شروع شود 

صفحه 13:
‎G‏ هزینه ارسال هر واحد ‎Hos IVS‏ به مفصد [ ‏میزان کالای ارسالی از مبدأ / به مقصد [ ‎CX)‏ 2 -مطنده ‏دز در ‏و رداک ود ‎st‏ ‏۱ ‏[قلر. .رات قر ) ,0 - 2% ‎ ‎i ‎9-0 ‏1 شرط توازن مسأله حمل ونقل متوازن يا متعادل 

صفحه 14:
minz=cX st AX=b و أو وسو كم تج ی 4] 3 ‏مر ...ی‎ Agr Amal ۲ 

صفحه 15:
x x, q مص Xx, x, 

صفحه 16:
گامهای روش گوشه شمال غربی ۲ تخصیص کمترین مقدار تقاضا و ظرفیت به آن خانه و کم کردن مقدار تخصیصی مربوطه از تقاضا و ظرا ۳ بعد از کم کردن مقدار تخصیصی اگر تقاضا صفر شده باشد باید خانه های خالی ستون مربوطه را حذف کرد. اگر ظرفیت صغر شده باشد باید خانه های خالی سطر مربوطه را حذف کرد. اگر تقاضا و ظرفیت همزمان صفر شدند یکی را به دلخواه انتخاب می کنیم. سپس به گام ۱ رفته و آنقدر الگوریتم را تکرار می کنیم تا تمامی ظرفیت و تقاضاها صفر شوند 

صفحه 17:
" " روش گوشه چپ بالا (گوشه شمال غربی) نب كام اول: از خلنه (سلول) كوشه جب بالا (رر3) شروع مى كنبم. حداكثر میزان عرضه با تقاشا راید آن باس كاد : للننا 29 لازا تفاكناازا در ان سطر يا ستو #صديل.مى كننم: ‎rege ple‏ میزان عرضه یا تقاضای حاصل از گام اول صفر خواهد شد لذا سطر یا ستون مربوط به آن را از انتخاب های بعدی مان حذف می کنیم. البته اگر هم سطر و هم ستون هر دو صفر شوند فقط يكى را بك ذا 1ك 21 ل نتة: كام سوم:جدول حاصل از حذف یک سطر یا ستون را در نظر گرفته دوباره عنصر كوشه چپ بالا را برای ن در نظر مى كيريم و به كام اول برميكرديم. لين روند را تا يايان جدول و پیدا کردن جواب ‎Bee al MD‏ فرض کنید در جریان یافتن جواب پایه آغازین مقادیر فعلی عرضه و تقاضا به صورت زیر نشان داده شود: 

صفحه 18:
يحاي بی شما عر ل كوشه جب (گوشه ( 4 ۳ م روش بالا ‎J‏ 

صفحه 19:
‎(a : ۰‏ گوشه شه 1 ارو شما ال ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 20:
< " روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 21:
بی) » شه ر + 3 رو 9 

صفحه 22:
روش گوشه چپ بالا (گوشه شمال غربی) سكج 

صفحه 23:
مثال روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 24:
روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 25:
روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 26:
روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 27:
روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 28:
روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 29:
غربی) شمال غرب گوشه چپ بالا (گو شه چپ ش كو روس مثال 

صفحه 30:
مثال روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 31:
ِ بی) گوشه شه شما ساپ روس مثال 

صفحه 32:
روش گوشه چپ بالا (گوشه شمال غربی) 

صفحه 33:
مثال غربی) شمال غرب گوشه چپ بالا (گو روس 

صفحه 34:
گام های روش حداقل هزبنه ۱ انتخاب خانه با کمترین هزینه (اگر حالت تساوی پیش آمده یکی به دلخواه انتخاب امس تیدا" س ۲ تخصیص کمترین مقدار تقاضا و ظرفیت به آن خانه و کم کردن مقدار تخصیصی مربوطه از تقاضا و ظرفیت آن ۳ بعد از کم کردن مقدار تخصیصیی اگر تقاضا صفر شده باشد باید خانه های خالی ستون مربوطه را حذف کرد. اگر ظرفیت صفر شده باشد بايد خانه های خالی سطر مربوطه را حذف کرد. اگر تقاضا و ظرفیت همزمان صفر شدند یکی را به دلخواه انتخاب می کنیم. سپس به گام ۱ رفته و آنقدر الگوریتم را تکرار می کنیم تا تمامی ظرفیت و تقاضاها صفر شوند 

صفحه 35:
روش کمترین چنانچه در روش كو نداشتند. پس درست است که رو هزینه های هر واحد در یافتن جواب آغازین هیچ نقشی قبل یک جواب پلیه به ما می دهد و لیکن لین جواب به هیچ وجه تضمین بهینه بودن یا نزدیک به بهینگی را ندارد. لذا چنانچه در حل خواهید دید این روش یافتن جواب باعث می شود تا با تکرار های بیشتری به جواب بهینه برسیم. روش هایی که ذکر خواهد شد اين مشكل را تا حدودی رفع می کنند. سح گام اول: خانه هایی را در جدول پیدا می کنیم که کمترین هزینه را دارد (در صورت منحصر به قرد نبودن یکی را انتخاب می کنیم) حداکثر مقدار ممکن را به آن خانه (سلول) تخصيص داده و عرضه و تقاضاى آن را تعديل مى كنيم. ست كام دوم: ميزان عرضه يا تقاضاى حاصل از كام اول صفر خواهد شد لذا سطر يا ستون مربوط به أن را از انتخاب هاى بعدى مان حذف مى كنيم. البته اكر هم سطر و هم ستون هر دو صفر شوند فقط يكى را به دلخواه حذف مى كنيم. است؛ كام سوم:جدول حاصل از حذف يك سطر يا ستون را در نظر كرفته دوباره به كام اول برميكرديم. اين روند را تا يايان جدول و بيدا كردن جواب پایه ادامه می دهیم. نكته: روش هاى كمترين سطر و حداقل ستون مشلبه حداقل هزينه است با لين تفاوت كه به جاى مقايسه ى هزينه ها در كل جدول هزينه ها را سطر به سطر و يا ستون به ستون ایسه می کنیم 

صفحه 36:
روش کمترین هزینه 

صفحه 37:
7 روش کمترین هزینه 

صفحه 38:
روش کمترین هزینه 

صفحه 39:
روش کمترین هز ینه 

صفحه 40:
روش کمترین هزینه 

صفحه 41:
"" روش کمترین هزینه 

صفحه 42:


صفحه 43:
مثال 

صفحه 44:
مثال 

صفحه 45:
مثال 

صفحه 46:
مثال روش کمترین هز إينه 

صفحه 47:
روش تقریب وگل ۱ لین روش اگر چه پیچیده تر از روش های قبلی است اما معمولا نسبت به روش های دیگر به وییه در مسائل بزرگ جواب پلیه آغازین بهتری را ارلئه می دهد. روش فوگل از اطلاعات مربوط به هزينه بابه كاركيرى مفهوم هزينه ى فرصت از دست رفته براى تعيين جواب شدنى أغازين استفاده مى كند. اين روش تفاوت بين دو مورد از كم هزينه ترين خانه ها را در هر ستون و هر سطر مورد بررسى قرار مى دهد و مى كوشد از تخصيص به خلنه هاى يرهزينه جلوكيرى كند لين تفاوت. حداقل هزینه فرصتی (که در اينجا با مفهوم جريمه بيان مى شود) ناشى از عدم تخصيص صحيح را بيان مى دارد. نت گام اول: برای هر سطر و ستون جریمه ی حاصل از تفاضل دو خانه اى كه كمترين هزينه را در آن سطر يا ستون دارد محاسبه می کنیم. تتاگام دوم: سطر یا ستونی که دارای بیشترین جریمه است را انتخاب می کنیم و کم هزینه رین خلنه از آن سطر یا ستون را انتخاب می کنیم و حداکثر میزان ممکن را برای آن خانه تخصيص مى دهيم. اگز در یک سطر يا ستون تنها يك خلنه باقى مانده باشد ما آن خلنه را به عنوان يك عنصر يايه در نظر مى كيريم و عرضه و تقاضا را تعديل مى كنيم" ‏ نت كام سوم: عرضه يا تقاضليى كه صفر مى شود سطر يا ستون مربوط به كن را حذف مى كنيم. جدول حاصل از حذف يك سطر يا ستون را در نظر كرفته دوباره به كام اول برميكرديم. ن روند را تا پایان جدول و پیدا کردن جواب پایه ادامه می دهیم. 

صفحه 48:
روش تقریب وگل 

صفحه 49:
روش تقریب وگل 

صفحه 50:


صفحه 51:
"روش تقریب وگل 

صفحه 52:
روش تقریب وگل 

صفحه 53:


صفحه 54:
روش تقریب وگل 

صفحه 55:
N ° ‏لين‎ ‎0 ‎2 ‎5 ‎ry روش تقریب وگ 

صفحه 56:
روش تقریب وگل 

صفحه 57:
5 5 حل مساله به روش سيميلكس 2 گام اول: پیدا کردن یک جواب پایه آغازین شدنی كام دوم: محاسبه ى © 207 برای متفیر های غیر پایه ای و بررسی بهینگی اگر تمام 6,۲ مثبت بودند جواب بهینه حاصل شده است و توقف می کنیم آگر همگی نامثبت نبودند در این صورت مثیت ترین ۰ ۰ ۷ ّانتخاب و متفیر غير پایه ای متناظر را به عنوان وارد شونده انتخاب می کنیم. كام سوم: متغیر خارج شونده را پیدا می کنیم ‎Ole =‏ پایه ای شدنی فعلی را حساب کرده و به گام دوم می رویم. ‏به این روش روش پله سنگی هم می گویند ‏در اسلاید های قبلی ما یک سری خصوصیات برای رل را بیان و اثات کردیم.پس در این صورت خواهیم داشت ‎k 5 ۳ ۱‏ © درة' توه - ر6 درة 2 6 "راو ‎ay‏ ‏ره -(6 +6 م6 ‎Gav‏ -رکا< ره - 2 |( ‎aK ay ‎ ‏بردار زا بوسیله یک دور منحصر به فرد از در آیه ی ‎2D‏ ‏برخی بردار های پایه مشخص می شود. به این روش روش دور با یر بسته گفته می شود. رتست | رل ۹9 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 58:
حل مسأله به روش سيميلكس برای تعیین متفیر خارج شونده طبق آنجه كه قبلاً در مورد روش سيميلكس ميدانيم. فرض كنيد متغير وارد شونده ى 6 مشخص شده است. اكر همانتد فصل سوم متغير غير يايه اى وارد شونده |7 1 بلا باشد در اين صورت مقدار متغير هاى بايه نيز افزايش مى يابد اما اكر درآيه 1 ببرلا+ باشد افزايش متغير غير بايه اى وارد شونده مقادير پایه را کاهش می دهدتا چایی که یک پایه به عنوان متفیر مسدود کننده صفر می شود. اگر مقدار افزایش متغیر غیر پیه ای وارد شونده ۵ اد و ."دار ...در تکرار علی سیمپلکس باشد.در این صورت با آزمون مینیسم نسبت خواهیم داشت: ‎A =min ,:basicell, A haa+1‏ ‎inrepreserttanof‏ thenonbasirelli, j)} حال در جدول جدید برای متغیر های پایه ای که در دور شرکت کرده بودند مقدار ۸۵ را از خانه های با ضریب ۱+ کم کرده و مقدار ۸۵ را به خانه های با ضریب ۱- اضافه کنید. جدول جدید را تشکیل دهید. پایه ها و مقادیر آنها را در آن مشخص کنید و دوباره به كام دوم برويد و تا رسیدن به بهینگی این عمل را تکرار 

صفحه 59:
مثال پایه ی شدنی به روش گوشه چپ الا بدست آمده است مقدار © 20 را برای خانه های غير بايه محاسبه مى كنيم SF wigs oly pice A=min{,,x,}=min{,"}=)- 62۴-۵۳۰۲ 2 ادع لعجو ردن دع ‎1١-١‏ د ل ‎١‏ د بد ‎FA ۵ +۱۰ 2۵ ‎ ‎x = x, X, =A (unchangpd ‎- ۸ <۲۰- ۰ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 60:
تباهیدگی در مسأله حمل و نقل همانطور که در روش سیمپلکس دیده شده در این جا هم حالت تباهیدگی وجود دارد. لته اين وضعیت مشکل چندانی در حالت عملی برای حل مسأله بوجود نمی آورد. نشانه حالت تباهید گی وجود مقدار صفر در یک متفیر پایه است. در دو حالت تباهیدگی در جدول حمل و نقل رخ مى دهد: 8 در مرحله پیدا کردن جواب پایه آغازین: همان طور که در روش های مذ کور برای چیدا کردن جواب پایه اولیه دیدیم برخخى أوقات در بيدا كردن يكك خانه بايه مقدار عرضه و تقاضا باهم صفر می شوند. یکی از این ها حذف و مقدار صفر دیگر به مرحله بعدی می رود. در مرحله پا مراحل بعدی حتماً یک مقدار صفر برای خانه ای که در سطر یا ستون صفر واقع شده تعلق خواهد گرفت. در مرحله بهبود جواب: هر گاه در زمان بدست آوردن متفیر خروجی با آزمون مبنیسم مقدار پرای خانه های با ضریب ۱+ دو خانه (پایه) برای انتخاب داشته لذا در گام بعدی که جدول به روز می شود یک مقدار صفر را برای یک خانه پایه خواهیم داشت. 

صفحه 61:
تباهیدگی در مسأله حمل و نقل #7 شرط لازم برای تباهید کی در مسأله حمل و نقل: فرض کنید در یک تکرار الگوریتم حمل و نقل مابا یک پایه شدنی تباهیده روبرو شویم (مانند آنچه در شکل می بینیم). با حذف خانه (سلول) تباهیده درخت مربوط به پایه به دو مزلفه جدا از هم (جنگل) تبدیل می شود. مجموع متفیرهای پایه ی موجود در مولفه ی رن) را با هم جمع می کنیم. در این صورت خواهیم داشت: همچنین برای همان مزلفه داریم: لذا داریم: چس یک شرط لازم برای تباهیدگی آن است که یک زیرمجموعه مناسب از سطر ها و ستون ها (عرضه ها و تقاضا ها) مجموع یکسانی داشته باشند. 0 

صفحه 62:
گامهای روش راسل ۱ محاسبه برای هر سطر: بزرگترین هزینه در سطر باقی مانده ۲. محاسبه_برای هر ستون: بزرگترین هزینه در ستون باقی مانده محاسيه رای هر خانه باق مانده ؟. تخصيص كمترين مقدار تقاضا و ظرفيت به خانه ى با منفى ترين و كم كردن مقدار ۱ تخصیصی مربوطه از تقاضا و ظرفیت آن ه. بعد از كم كردن مقدار تخصیصی, اگر تقاضا صفر شده باشد باید خانه های خالی ستون مربوطه را حذف کرد. اگر ظرفیت صفر شده باشد باید خانه های خالی سطر مربوطه را حذف کرد. اگر تقاضا و ظرفیت همزمان صفر شدند یکی را به دلخواه انتخاب می کنیم. سپس به گام ۱ رفته و آنقدر الگوریتم را تکرار می کنیم تا تمامی 3 و تقاضاها صف_ شوند 

صفحه 63:
مثالی از روش راسل A B 6 eb 1 15 12 24 400 2 7 8 15 300 3 27 18 100 21 تقاضا 3800 300140 360 

صفحه 64:
مثالی از روش راسل c 24 15 21 B 12 8 18 300 A 15 7 27 360 تقاضا 

صفحه 65:
مثالی از روش راسل Bone? Cc 24 15 21 140 B 12 8 18 300 A 15 7 27 360 تقاضا 

صفحه 66:
مثالی از روش راسل ظرفیت 400 300 100 Bone? Cc 24 15 21 140 B 12 8 18 300 A 15 7 27 360 تقاضا 

صفحه 67:
مثالی از روش راسل 12 18 300 15 27 360 

صفحه 68:
مثالی از روش راسل ظرفیت 400 300 100 Bone? Cc 24 15 21 140 B 12 8 18 300 1 8 15 27 360 

صفحه 69:
مثالی از روش راسل 12 18 300 15 27 360 

صفحه 70:
مثالی از روش راسل محاسبه نل ‎A B © sb x,‏ 400 24 12 - © 36 0 15 8 7 Nu 2 100 2 18 ,27 3 تقاضا 360 300 140 5800 2 4 3 © رت A, 4=15 -24-27=-36 

صفحه 71:
مثالی از روش راسل محاسبه نل ‎A B © sb x,‏ 400 24 = 45 * 8 30 36 300 15 8 7 Nu 27 18 100 21 7 360 300 140 ۳ 2 > @ 4 ۸-12 -24 -18- -0 

صفحه 72:
مثالی از روش راسل محاسبه نل رمه ظرفیت ‎A B C‏ 400 > يدق ع 15 > @ 6 24 30 36 0 15 8 7 2 100 1 18 27 2 7 360 300 140 ۳ 2 1 7 8 © ۸-24-24 -24--4 

صفحه 73:
مثالی از روش راسل محاسبه نل رمه ‎A B © tb‏ 2 400 24 - 12 - 15 - 3 36 300 15 8 ۱ 2 100 18 27 A, ,=7 -15 -27=-35 

صفحه 74:
مثالی از روش راسل Aye ‏محا‎ A B 6 ‏ظرفیت‎ zs, - 15 - 12 - 24 400 2 36 30 4 300 15 5 ا © 25 35 3 100 21 18 27 00 0“ 0 360 3 & @ 7 A, ,=8 -15 -18=—25 

صفحه 75:
مثالی از روش راسل محا ‎Aye‏ ‏رمت ‎A B © tb‏ - 15 - 12 - 24 400 2 30 4 27 18 21 100 3 360 300 140 00 7 8 © Ay =15 -15 -24=-24 ۳۹ 

صفحه 76:
مثالی از روش راسل © 8 4 A, ,=27 —27 -27=-27 ۳۹ 

صفحه 77:
مثالی از روش راسل Aye ‏محا‎ 7 @ 4 A,,=18 -27 -18=-27 

صفحه 78:
مثالی از روش راسل محاسبه نل رمت ‎A B © tb‏ 2 400 24 - 12 - 15 - 24 0 300 15 ,5 )8 = 7 = 5 24 25 35 @ 100 8 27 9 00 39,0 30 7 60“ : 1 oO” ۸-21 -27 -24--0 

صفحه 79:
مثالی از روش راسل محاسبه نل ‎A B 9 cob x,‏ 2 400 24 - 12 ۰ 15 1 ‎OQ 30 24 4‏ 300 15 "8 > 7 - 2 5 24 25 35 3 100 21 - 18 - 27 9 300809 ملد 3300 30 تقاضا 2 1 3 بت 7 5 8 4 

صفحه 80:
مثالی از روش راسل A B 9 cob x, 15 12 24 2 QS 400, 7 8 15 300 5 3 100 21 18 27 ۳ 140 300 0 مود 2 1 2 4 8 7 

صفحه 81:
mS ‏بسر ان در قل‎ 0 مثالى از روش راسل A B Cc ‏ظرفیت‎ ‎15 12 24 ‏ما‎ ‎8 15 300 18 21 100 ‏هو‎ 0 300 140 00000 2 1 2 7 8 4 

صفحه 82:
مثالی از روش راسل A B 6 ‏رمه ظرفيت‎ 15 12 - 24 40 2 12 © 24 1 aS 15 300 a 213 #۳3 8 2 21 100 0 * 500 mo 0 1 2 

صفحه 83:
مثالی از روش راسل A B 6 ‏ظرفيت‎ zz, 2/2 1 15 02 24 Moat 2 8 15 300 1/1 313 3 18 21 0 | 741 

صفحه 84:
مثالی از روش راسل رمه ظرفيت 6 ‎A B‏ 2 2 م 0 1 1 300 15 8 313 1 21 100 | 741 ۰0ج 140 موز 0 1 

صفحه 85:
15 300 مثالی از روش راسل 

صفحه 86:
mS ‏بسر ان در قل‎ 0 مثالى از روش راسل 8 © eb 15 2 ‏أ‎ [| 0 © 8 15 30 18 21 100 260, 140 «۰ 1 0 2 

صفحه 87:


صفحه 88:
mS ‏بسر ان در قل‎ 0 مثالى از روش راسل 8 © eb wo ۰ 8 (5 ‏ور‎ 21 100 

صفحه 89:


صفحه 90:
مثالی از روش راسل A B 6 Sab 1 ‏تا‎ G12 24 400 2 7 e& 8 4015 0 3 27 18 21 100 تقاضا ‎ope?‏ 140 300 360 هزینه کل 

صفحه 91:
= ۳ Siw ab ‏گامهای روش‎ ۱. انتخاب یک خانه خالی جدول (خانه ای که مقدار نگرفته است) ۲ رسم پله سنگ برای خانه خالی مربوطه ۲ برای رسم پله سنگ خانه خالی؛ از آنن خانه شروع به حرکت کرده و با حرکتهای افقی و عمودی از روی خانه های پر (متفیر اساسی) باید به آنن خانه ‎ede‏ .. در رسم بله ستكك؛ تفیبر جهت فقط روی خانه های پر صورت می گیرد. ۲ از خانه های خالی فقط عبور می توان کرد. ۲ از روی خانه های پر می توان عبور کرد با تغییر جهت داد. 

صفحه 92:
گامهای روش پله سنك ۳ علامت گذاری پله سنگ: خانه خالی مربوطه را علامت + و به بقیه خانه ها یکی در مان 9۳ می دهم ۴ محاسبه ارزش پله سنگ: جمع جبری هزینه تمامی گوشه ها با توجه به علامت. آنها ۵ انجام گامهای ۱ تا ۴ برای تمامی خانه های خالی جدول ۶ انتخاب بله سنكك با منفى ترين ارزش ۶ انتخاب متغیر ورودی: خانه خالی پله سنگ مربوطه ۶ اتتخاب متغير خروجى: كوجكترين بر خالى با علامت منفى 

صفحه 93:
گامهای روش پله سنگک غير خروجى به خانه های با علامت + اضافه و از خانه های با ۸ گامهای ۱ تا ۸ آنقدر تکرار می شوند تا هیچ پله سنگی با ارزش منفی وجود نداشته باشد 

صفحه 94:
100 200 300 400 100 500 100 200 100 100 200 600 300 Pw Ne a 

صفحه 95:
100 200 300 400 100 500 100 200 100 200 600 300 سرادم أب اص a 

صفحه 96:
100 200 300 400 100 500 100 200 100 100 200 600 300 دم ‎Wi‏ در a 

صفحه 97:
100 200 300 400 100 500 100 200 مثالی از مسیریابی 100 100 200 600 300 PW) nN) a 

صفحه 98:
100 200 300 400 100 500 100 200 100 100 200 600 300 Pw) nN) a 

صفحه 99:
مثالی از روش پله سنك فرض کنید جوابهای اولیه زیر از روش راسل بدست آمده اند و قرار است با روش يله سنگ بهیود پیدا کنند A B 6 sab 1 G15 CD12 © 24 400 2 0 © 8 )0(15 0 100 ی 18 © 27 © 3 تقاضا ووو 140 300 360 © خانه هاى خالى خانه هاى ير 

صفحه 100:


صفحه 101:
محاسبه ارزش پله سنگ 

صفحه 102:


صفحه 103:
مثالى از روش يله سنك طرفت 0 6 ‎B‏ ۸ محاسبه ارزش پله سنگ 

صفحه 104:
مثالی از روش پله سنك 

صفحه 105:
A B 6 sab 15_ 40 12 24 400 8 40 15 300 27 18 c 21 10 360 300 ‏مدا‎ 00 ۳۳ 

صفحه 106:
مثالی از روش پله سنك A B © | ‏ظرفيت‎ ‎i * 15 4 2 24 400 2 26 7 8 15 300 0 2 40 3 27 18 0 21 10 we 360 300 ‏میا‎ 00 

صفحه 107:


صفحه 108:
مثالی از روش پله سنك A B 6 sab 1 15 30 12 24 400 cp" 3 2 28 7 8 40 15 0 3 27 18 c 21 10 ‏میا 300 360 تقاضا‎ 00 

صفحه 109:
400 300 00 عفر فد مثالى از روش يله سنك ‎A B c‏ 10 15 30 12 24 0 0 6 7 8 ‏و4‎ 5 27 18 c 21 360 300 G40 

صفحه 110:


صفحه 111:


صفحه 112:
مثالی از روش پله سنك A B © tb 1 Gps Ge 24 400 2 co 7 8 GIS 300 3 27 18 Cet 100 Als ‏0و 140 300 360 اضا‎ هزینه کل 

صفحه 113:
مثالی از روش پله سنك جواب اولیه مسئله زیر را از روش گوشه شمالفربی بدست. آورده و با روش پله سنگ بهبود دهید؟ ظرفيت || © ‎A B‏ 00 15 12 9 1 200 8 11 7 2 0 17 18 10 3 240 200 260 تقاضا 

صفحه 114:
گامهای روش توزیع تعدیل رابطه ی برای تمامی خانه های پر و محاسبه ی تمامی ها و ها ۱ برای هر سطر ۰ برای هر ستون اوه برای تمامی خانه های خالی ۳ انتخاب منفی ترين ۳ رسم پله سنگگ برای خانه خالی آن ۳ انتخاب متفیر ورودی: خانه خالی پله سنگگ مریوطه ۳۳ اب متفیر خروجی: کوچکترین خانه پر با علامت منفی 

صفحه 115:
گامهای روش توزیع تعدیل شده ۴ بهبود پله مقدار متغیر خروجی به خانه های با علامت. + اضافه و از خانه های با علامت - كم مى شود ۵. گامهای ۱ تا ۵ آنقدر تکرار مى شوند تا باشد پله سنگی با ارزش منفی وجود نداشته 

صفحه 116:
مثالی از روش توزیع تعدیل شده ‎A B © ob‏ رم 400 24 وق ‎C15‏ 1 و 300 615 8 ‎Qa‏ 7 2 وم 100 1 18 27 3 تقاضا “قوم 140 30 360 ‎Up‏ ولا ولا 2و۷ +1 5 1+۷ ۷5 +رلا 8 عور۲ +1 1 م۷ +ولا 

صفحه 117:
مثالی از روش توزیع تعدیل شده ‎vy ,=15‏ — 215 ر0+۷ ب 15ح ربا جره ‎vz=12‏ — 12 حور 0+۷ مت ۷-12 +1 4-< لا ب 8< 12+ — ‎n+ Vz=8‏ ۷29 مب 15 م۷ +4- مب ۷15 +رلا ‎Ut Vo=21— u3+19=21 — 2 <2‏ ‎u,=0 

صفحه 118:
مثالی از روش توزیع تعدیل شده ظرفیت © ‎A B‏ مده 400 24 © وق ‎G15‏ 1 4-عیه 300 ‎@DIS‏ ۶ 6 7 © 2 2عیبه 100 روت 18 © 27 0 3 ?30080 0 ۰ 300 20360 تقاضا ۷,9 ۷12 15<ر۲ 24-0-1925 سای تا 3 8 4- -15-(4-|- 7ع رل - یلا - ماو ‎4=Cy4— Uy —V4=27 —2 -15=10‏ 3 2-24 2-1 19 خرن ولا - وروا حو و0 

صفحه 119:
مثالی از روش توزیع تعدیل شده A Bc. cas 1 15 G@I2 24 0 2 2 8 GIS 300 3 270 18 1 0 ‏تقاضا‎ ‎360 30 140 ‏تچ‎ ‎36 ۱ 0 er x 26— 0 

صفحه 120:
مثالی از روش توزیع تعدیل شده A B 6 Sab 1 * 15 40 12 24 400 2 26 7 8 15 300 4 2 40 3 27 18 10 21 100 0 ‏تقاضا‎ ‎360 300 140 gonee® GF 

صفحه 121:
مثالی از روش توزیع تعدیل شده ۳۹ B © sib 1 36 15 12 24 400 0 @® 2 36 7 8 40 15 300 3 27 18 c 21 100 ‏تقاضا‎ 0م 140 300 360 

صفحه 122:
مثالی از روش توزیع تعدیل شده A B 6 Sab 400 24 12 30 15 1 ا 2 26 7 8 40 15 300 3 27 18 10 21 100 0 ‏تقاضا‎ ‎360 300 140 gonee® GF 

صفحه 123:
مثالی از روش توزیع تعدیل شده A B 0 ‏ظرفیت‎ ‎1 10 15 30 12 24 400 9 0 2 3 7 8 40 15 300 3 27 18 10 21 0 0 ‏تقاضا‎ ‎360 300 140 gonee® GF 

صفحه 124:
مثالی از روش توزیع تعدیل شده ‎A B 6 sab‏ 7م 400 24 ری ترفن 1 2 Ce 7 8 40215 300 ‏و2‎ عل 100 21 18 27 3 تقاضا 0م 140 300 360 ‎Dp Dy Og‏ 2و۷ +1 5 1+۷ ‎Unt V4=7 Unt Vo=15‏ 1 م۷ +ولا 

صفحه 125:
مثالی از روش توزیع تعدیل شده ‎vy ,=15‏ — 215 ر0+۷ ب 15ح ربا جره ‎vz=12‏ — 12 حور 0+۷ مت ۷-12 +1 8- ديل مب 7< 15+ مب 7ع را +ولا ۷-23 مب 15<م8+۷- مت 15عم۷ +رلا 2- یره — ‎U3+23=21‏ ص21 عم +ولا ‎u,=0 

صفحه 126:
مثالی از روش توزیع تعدیل شده ظرفيت | 6 ‎A B‏ 1 eos G2 © 24 400 u4=0 2 Gp? © 8 4015 300 w,=-8 3 ‏و‎ 2 9 18 1 100 y,=-3 تقاضا «شوم 140 300 360 ۷3 12و۲۷ ۲215 0-23-1- 24حينا- لاح © ع0 

صفحه 127:
مثالی از روش توزیع تعدیل شده A B 6 | ‏ظرفيت‎ ‎1 ‏قد‎ Gr 24 400 2 cS 7 8 GOS 300 3 27 18 Cert 100 تقاض 0م 140 300 360 تقاض هزينه كل 

مدل حمل و نقل درس:مهندسی سیستم دانشجو :محمدرضا اسدزاده استاد :حمیدرضا ربیعی فر بهار 1400 دانشگاه آزاد اسالمی واحد تهران جنوب مدل حمل و نقل مدل برنامه ریزی خطی حمل و نقل یافتن یک جواب آغازین برای حل مدل ویژه حمل و نقل مقایسه با روش سیمپلکس تباهیدگی در مدل حمل و نقل مسأله تخصیص (واگذاری) روش حل مسائل حمل و نقل در روش حل مسائل حمل و نقل ،در ابتدا یک جواب اولیه برای مسئله بدست می آید و سپس این جواب اولیه را بهینه می کنیم جواب اولیه روش گوشه شمالغربی 1. جواب بهینه روش پله سنگ 1. روش حداقل هزینه 2. روش توزیع تعدیل شده 2. روش وگل 3. روش راسل 4. نکات اولیه اولین مرحلSه در حSل مسSائل حمSل و نقSل ،آمSاده سSازی مسSئله کSه شامل 4نکته است. نکتSSSSه :1 مجمSوع تقاضSاها و ظSرفیت هSا بایSد برابر باشد ال ف -اگSر ظرفیتهSا بیشSتر از تقاضSاها بودنSد ،بایSد یSک سSتون مجازی با هزینه های صفر تشکیل داد 500=400-900 ظرفیت 3 2 1 400 24 12 15 1 300 15 8 7 2 200 21 18 27 3 100 200 100 تقاضا 900 400 نکات اولیه اولین مرحلSه در حSل مسSائل حمSل و نقSل ،آمSاده سSازی مسSئله کSه شامل 4نکته است. نکتSSSSه :1 مجمSوع تقاضSاها و ظSرفیت هSا بایSد برابر باشد ال ف -اگSر ظرفیتهSا بیشSتر از تقاضSاها بودنSد ،بایSد یSک سSتون مجازی با هزینه های صفر تشکیل داد ظرفیت 4 3 2 1 400 0 24 12 15 1 300 0 15 8 7 2 200 0 21 18 27 3 500 100 200 100 تقاضا 900 900 نکتSSSSه :1 نکات اولیه ب -اگSر تقاضSاها بیشSتر از ظرفیتهSا بودنSد ،بایSد یSک سSطر مجSازی با هزینه های صفر تشکیل داد 400=250-650 ظرفیت 3 2 1 100 24 12 15 1 100 15 8 7 2 50 21 18 27 3 100 50 500 تقاضا 250 650 نکتSSSSه :1 نکات اولیه ب -اگSر تقاضSاها بیشSتر از ظرفیتهSا بودنSد ،بایSد یSک سSطر مجSازی با هزینه های صفر تشکیل داد ظرفیت 3 2 1 100 24 12 15 1 100 15 8 7 2 50 21 18 27 3 400 0 0 0 4 100 50 500 تقاضا 650 650 نکتSSSSه :2 نکات اولیه روش حل حمل و نقل برای مسائل از نوع کمینه (هزینه) است اگSر اعSداد داخSل جSدول بSرای مسSائل از نSوع بیشSینه (سSود) بSود ،فقSط کSافی اسSت اعSداد داخSل جSدول را قبSل از حSل در یک منفی ضرب نمود ظرفیت 3 2 1 100 24 12 15 1 100 15 8 7 2 50 21 18 27 3 50 50 150 تقاضا 250 250 نکتSSSSه :2 نکات اولیه روش حل حمل و نقل برای مسائل از نوع کمینه (هزینه) است اگSر اعSداد داخSل جSدول بSرای مسSائل از نSوع بیشSینه (سSود) بSود ،فقSط کSافی اسSت اعSداد داخSل جSدول را قبSل از حSل در یک منفی ضرب نمود ظرفیت 3 2 1 100 -24 -12 -15 1 100 -15 -8 -7 2 50 -21 -18 -27 3 50 50 150 تقاضا 250 250 نکتSSSSه :3 نکات اولیه اگSر در مسSئله حمSل و نقSل نتSوان مبSدای را بSه مقصSدی تخصSیص داد باید به جای هزینه آن عدد Mرا قرار داد. * در مثSال زیSر فSرض کنیSد مبSدا 3را نتSوان بSه مقصSد 2تخصSیص داد ظرفیت 3 2 1 100 24 12 15 1 100 15 8 7 2 50 21 18 27 3 50 50 150 تقاضا 250 250 نکتSSSSه :3 نکات اولیه اگSر در مسSئله حمSل و نقSل نتSوان مبSدای را بSه مقصSدی تخصSیص داد باید به جای هزینه آن عدد Mرا قرار داد. * در مثSال زیSر فSرض کنیSد مبSدا 3را نتSوان بSه مقصSد 2تخصSیص داد ظرفیت 3 2 1 100 24 12 15 1 100 15 8 7 2 50 21 ‏M 27 3 50 50 150 تقاضا 250 250 نکته بسیار مهم در تمامی روشهای محاسبه جواب اولیه ،هرگاه یک سطر یا یک ستون باقی ماند ،باید به تمامی خانه های آن سطر یا ستون مربوطه مقدار تخصیص .داد از اینرو ،برای شروع مقداردهی از خانه با کمترین هزینه شروع شود  Cijهزینه ارسال هر واحد کاال از مبدأ i مقصد j xijبه کاالی میزان ارسالی از مبدأ i به مقصد j ‏m ‏n ‏min z   Cij xij تقاضا عرضه ‏d1 ‏S1 ‏d2 ‏S2 ‏ ‏ ‏dn ‏Sm ‏i 1 j 1 ‏n ) x S (i 1,..., m ‏i ‏ij ‏j 1 ‏m ) x d ( j 1,..., n ‏j ‏ij ‏i 1 ‏xij 0 ‏s.t. ‏j ‏ S  d ‏i ‏j ‏i شرط توازن مسأله حمل ونقل متوازن یا متعادل min z cX s.t. AX b X 0 ˆ o 1  ˆ o 1 A    o o   I n I n o   o   ˆ o 1   I n  ( m n )( mn )   1[1,...,1] بارn  x11      x x  1n   x2n       xmn   S1      S b  m   d1       d n  c [c11,..., c1n ,..., cm1,..., cmn ] A [a11,..., a1n ,..., am1,..., amn ] مدل حمل و نقل مقصد c11 x11 c12 x12 c21 مبدأ x21 x22   cm1 cm 2 xm1 تقاضا c22 xm 2 d1 d2   c1n x1n S1 c2n S2 x2n     عرض ه  cmn Sm xmn dn  S  d i i j j گامهای روش گوشه شمال غربی .1انتخاب خانه شمال غربی جدول (سطر اول -ستون اول) .2تخصSیص کمSترین مقSدار تقاضSا و ظSرفیت بSه آن خانSه و کم کردن مقدار تخصیصی مربوطه از تقاضا و ظرفیت آن .3بعSد از کم کSردن مقSدار تخصیصSی ،اگSر تقاضSا صSفر شSده باشSد بایSد خانSه هSای خSالی سSتون مربوطSه را حSذف کSرد .اگSر ظSرفیت صSفر شSده باشSد بایSد خانSه هSای خSالی سSطر مربوطSه را حSذف کSرد .اگSر تقاضSا و ظSرفیت همزمSان صSفر شSدند یکی را بSه دلخSواه انتخSاب می کSنیم .سSپس بSه گSام 1رفتSه و آنقSدر الگSوریتم را تکرار می کنیم تا تمامی ظرفیت و تقاضاها صفر شوند روش گوشه چپ باال (گوشه شمال غربی)اول :از خانSه (سSلول) گوشSه چپ بSاال ( )x11شSروع می کنبم. گام حSداکثر مSیزان عرضSه یSا تقاضSا را بSه آن اختصSاص داده و مقSدار عرضSه و تقاضا را در آن سطر یا ستون تعدیل می کنیم. گام دوم :مSیزان عرضSه یSا تقاضSای حاصSل از گSام اول صSفر خواهSد شSد لSذا سSطر یSا سSتون مربSوط بSه آن را از انتخSاب هSای بعSدی مSان حSذف می کSنیم .البتSه اگSر هم سSطر و هم سSتون هSر دو صSفر شSوند فقط یکی را به دلخواه حذف می کنیم. گام سوم:جSدول حاصSل از حSذف یSک سSطر یSا سSتون را در نظSر ‏Sیریم وو بSه می گ مقادیرظSر آغازینآن در ن را بSرای یافتن چپ ب جریانگوشSه در عنصSر ‏Sاره ‏Sه دوب گرفت تقاضا عرضه فعلی جوابSاالپایه کنید فرض شود:را تSا پایSان جSدول و پیSدا کSردن جSواب پایSه دادهرونSد نشان این زیرگSردیم. صورتبرمی ‏Sام اول گبه ادامه می دهیم. مثا ل روش گوشه چپ باال (گوشه شمال غربی) تقاضا 100 230 50 120 30 170 140 100 60 عرضه مثا ل روش گوشه چپ باال (گوشه شمال غربی) تقاضا 100 60 230 50 120 30 170 140 100 60 عرضه روش گوشه چپ باال (گوشه شمال غربی) مثال تقاضا 40 100 60 230 50 120 30 170 140 100 60 0 عرضه روش گوشه چپ باال (گوشه شمال غربی) مثال تقاضا 0 40 100 40 60 230 50 120 30 170 140 100 60 60 0 عرضه روش گوشه چپ باال (گوشه شمال غربی) مثال تقاضا 0 40 100 230 170 40 60 50 120 30 170 140 100 60 0 60 0 عرضه مثا ل روش گوشه چپ باال (گوشه تقاضاشمال غربی) 0 40 100 230 170 40 60 60 50 120 30 170 140 100 60 0 60 0 عرضه روش گوشه چپ باال (گوشه شمال غربی) مثال تقاضا 0 40 100 230 170 40 60 60 50 120 30 170 140 100 60 0 60 0 عرضه روش گوشه چپ باال (گوشه شمال غربی) مثال تقاضا 0 230 40 170 40 100 30 140 60 60 50 120 30 170 140 0 100 60 0 60 0 عرضه روش گوشه چپ باال (گوشه شمال غربی) مثال تقاضا 0 230 40 170 40 100 30 140 60 60 50 120 30 170 140 0 100 60 0 60 0 عرضه روش گوشه چپ باال (گوشه شمال غربی) مثا ل تقاضا 0 230 40 170 40 100 30 30 140 60 60 50 120 30 170 140 140 0 100 60 0 60 0 عرضه مثا ل روش گوشه چپ باال (گوشه شمال غربی) تقاضا 0 170 40 40 100 0 30 230 30 140 60 60 50 120 30 170 140 140 0 100 60 0 60 0 عرضه روش گوشه چپ باال (گوشه شمال غربی) مثال تقاضا 0 170 40 40 100 0 30 230 50 30 0 140 60 60 50 120 30 170 140 90 140 0 100 60 0 60 0 عرضه مثا ل روش گوشه چپ باال (گوشه شمال غربی) تقاضا 0 170 40 40 100 0 30 230 50 30 0 140 60 60 50 120 30 170 140 90 140 0 100 60 0 60 0 عرضه مثا ل روش گوشه چپ باال (گوشه شمال غربی) تقاضا 40 0 170 40 100 0 30 230 50 120 30 0 140 60 60 50 30 90 30 170 140 90 0 140 0 100 60 0 60 0 عرضه مثا ل روش گوشه چپ باال (گوشه شمال غربی) تقاضا 40 0 170 40 100 0 30 230 50 120 30 0 30 140 60 60 50 30 90 30 170 140 90 0 140 0 100 60 0 60 0 عرضه مثا ل روش گوشه چپ باال (گوشه شمال غربی) تقاضا 0 170 120 40 40 100 0 30 230 50 0 30 0 30 140 60 60 50 30 90 30 0 170 140 90 0 140 0 100 60 0 60 0 عرضه گام های روش حداقل هزینه .1انتخاب خانه با کمترین هزینه (اگر حالت تساوی پیش آمد، یکی به دلخواه انتخاب می شود) .2تخصSیص کمSترین مقSدار تقاضSا و ظSرفیت بSه آن خانSه و کم کردن مقدار تخصیصی مربوطه از تقاضا و ظرفیت آن .3بعSد از کم کSردن مقSدار تخصیصSی ،اگSر تقاضSا صSفر شSده باشSد بایSد خانSه هSای خSالی سSتون مربوطSه را حSذف کSرد .اگSر ظSرفیت صSفر شSده باشSد بایSد خانSه هSای خSالی سSطر مربوطSه را حSذف کSرد .اگSر تقاضSا و ظSرفیت همزمSان صSفر شSدند یکی را بSه دلخSواه انتخSاب می کSنیم .سSپس بSه گSام 1رفتSه و آنقSدر الگSوریتم را تکرار می کنیم تا تمامی ظرفیت و تقاضاها صفر شوند روش کمترین هزینهروش گوشSه چپ دیSد هزینSه هSای هSر واحSد در یSافتن جSواب چنانچSه در آغSازین هیچ نقشSی نداشSتند .پس درسSت اسSت کSه روش قبSل یSک جSواب پایSه بSه مSا می دهSد و لیکن این جSواب بSه هیچ وجSه تضSمین بهینSه بSودن یSا نزدیSک بSه بهینگی را نSدارد .لSذا چنانچSه در حSل خواهیSد دیSد این روش یSافتن جSواب بSاعث می شSود تSا بSا تکSرار هSای بیشSتری بSه جSواب بهینSه برسSیم .روش هSایی کSه ذکSر خواهSد شSد این مشSکل را تSا حSدودی رفSع می کنند. گام اول :خانSه هSایی را در جSدول پیSدا می کSنیم کSه کمSترین هزینSه را دارد (در صSورت منحصSر بSه فSرد نبSودن یکی را انتخSاب می کSنیم) حSداکثر مقSدار ممکن را بSه آن خانSه (سSلول) تخصSیص داده و عرضSه و تقاضای آن را تعدیل می کنیم. گام دوم :مSیزان عرضSه یSا تقاضSای حاصSل از گSام اول صSفر خواهSد شSد لSذا سSطر یSا سSتون مربSوط بSه آن را از انتخSاب هSای بعSدی مSان ‏Sوند ‏Sفر ش سSتون دو ص ‏Sتون هSر ‏Sطر وو هم س هم س ‏Sه اگSر ‏Sنیم .البت می ک حSذف حSداقل مشSابه حSداقل سSطر کمSترین هSای روش نکت ه: کنیم. دلخواه ‏SترابSا به یکی فقط مقایسSه ی هزینSه هSا در کSل جSدول میSای حذفبSه ج ‏Sاوت کSه این تف ‏Sه اس هزین در نظSر می را مقایسهSتون ‏Sطر یSا س ‏SذفبهیSک س سطرصوSلیا از ح ‏Sدول حا سوم: کنیم ستون ستون سطرج به گام را هزینه ها گرفتSه دوبSاره بSه گSام اول برمیگSردیم .این رونSد را تSا پایSان جSدول و پیSدا مثا ل روش کمترین هزینه تقاضا 100 230 50 120 30 18 8 20 15 2 10 5 23 8 7 3 6 20 10 9 12 32 18 7 30 170 140 100 60 عرضه روش کمترین هزینه مثا ل تقاضا 100 230 50 120 30 18 8 20 15 2 10 5 23 8 7 3 6 20 10 9 12 32 18 7 30 170 140 100 60 عرضه مثا ل روش کمترین هزینه تقاضا 100 230 200 50 120 18 8 20 15 30 10 5 23 8 7 3 6 20 10 9 12 32 18 7 2 30 30 0 170 140 100 60 عرضه روش کمترین هزینه مثا ل تقاضا 100 230 200 50 120 18 8 20 15 30 10 5 23 8 7 3 6 20 10 9 12 32 18 7 2 30 30 0 170 140 100 60 عرضه مثا ل روش کمترین هزینه تقاضا 100 230 200 50 120 30 18 8 20 15 2 10 30 5 23 8 7 3 6 20 10 9 12 32 18 7 30 0 170 140 100 60 عرضه مثا ل تقاضا روش کمترین هزینه 100 200 230 50 0 120 30 18 8 20 15 2 10 30 5 23 8 7 3 6 20 10 9 12 32 18 7 30 0 50 170 120 140 100 60 عرضه مثا ل روش کمترین هزینه تقاضا 100 200 230 50 0 120 30 18 8 20 15 2 10 30 5 23 8 7 3 6 20 10 9 12 32 18 7 30 0 50 170 120 140 100 60 عرضه روش کمترین هزینه مثا ل تقاضا 100 230 200 60 50 0 30 18 8 2 10 30 5 7 3 9 12 14 20 15 23 8 0 120 30 0 50 170 120 6 20 10 32 18 7 140 0 100 60 عرضه روش کمترین هزینه مثا ل تقاضا 100 230 200 60 50 0 120 60 30 18 8 2 10 30 5 7 3 9 12 14 20 15 23 8 0 30 0 50 170 120 6 20 10 32 18 7 140 0 100 60 60 0 عرضه روش کمترین هزینه مثا ل تقاضا 100 200 0 60 230 50 0 120 60 8 30 18 2 10 30 60 7 3 50 9 12 5 14 20 15 23 8 0 30 0 170 120 60 6 20 10 32 18 7 140 0 100 60 60 0 عرضه مثا ل روش کمترین هزینه تقاضا 100 0 30 18 0 8 2 10 30 60 5 7 9 20 10 15 0 200 0 60 230 50 0 120 60 14 23 8 0 30 0 3 50 6 20 10 12 60 32 18 7 170 120 60 140 0 100 0 60 60 0 عرضه روش وگلSه پیچیSده تSر از روش هSای قبلی اسSت امSا معمSوًال روش اگSر چ این تقریب نسSبت بSه روش هSای دیگSر بSه ویSژه در مسSائل بSزرگ جSواب پایSه آغSازین بهSتری را ارائSه می دهSد .روش تقSریب فوگSل از اطالعSات مربSوط بSه هزینSه بSا بSه کSارگیری مفهSوم هزینSه ی فرصSت از دسSت رفتSه بSرای تعSیین جSواب شSدنی آغSازین اسSتفاده می کنSد .این روش تفSاوت بین دو مSورد از کم هزینSه تSرین خانSه هSا را در هSر سSتون و هSر سSطر مSورد بررسSی قSرار می دهSد و می کوشSد از تخصSیص بSه خانSه هSای پرهزینSه جلوگSیری کنSد این تفSاوت ،حSداقل هزینSه فرصSتی (کSه در اینجSا بSا مفهSوم جریمSه بیان می شود) ناشی از عدم تخصیص صحیح را بیان می دارد. گام اول :بSرای هSر سSطر و سSتون جریمSه ی حاصSل از تفاضSل دو خانSه ای کSه کمSترین هزینSه را در آن سSطر یSا سSتون دارد محاسSبه می کنیم. گام دوم :سSطر یSا سSتونی کSه دارای بیشSترین جریمSه اسSت را انتخSاب می کSنیم و کم هزینSه تSرین خانSه از آن سSطر یSا سSتون را انتخSاب می کSنیم و حSداکثر مSیزان ممکن را بSرای آن خانSه تخصSیص می دهیم. اگSر در یSک سSطر یSا سSتون تنهSا یSک خانSه بSاقی مانSده باشSد مSا آن خانSه را روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 18 30 20 8 15 100 230 50 120 2 10 5 23 8 7 3 6 20 10 9 12 32 18 7 30 170 140 100 60 جریمه 1 جریمه عرض جریمه 2 روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 7 100 230 50 120 18 30 20 8 15 2 10 5 23 8 7 3 6 20 10 9 12 32 18 7 30 170 140 60 100 1 جریمه 1 جریمه عرض جریمه 2 روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 7 100 3 230 3 50 2 120 30 8 18 15 20 2 10 5 23 8 7 3 6 20 10 9 12 32 18 7 30 170 140 100 5 7 1 2 60 1 جریمه 1 جریمه عرض جریمه 2 روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 7 100 3 230 3 50 2 120 30 8 18 15 20 2 10 5 23 8 7 3 6 20 10 9 12 32 18 7 30 170 140 100 5 7 1 2 60 1 جریمه 1 جریمه عرض جریمه 2 روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 7 7 100 3 3 230 200 2 ـ 3 50 0 2 2 120 30 8 18 15 20 10 5 23 8 7 3 6 20 10 9 12 32 18 7 30 0 30 50 120 170 140 100 60 7 2 3 2 1 جریمه 2 جریمه عرض 5 7 1 2 1 جریمه 1 روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 7 7 7 100 3 3 3 230 200 2 ـ ـ 3 50 0 5 2 2 120 30 8 18 15 20 10 5 23 8 7 3 6 20 10 9 12 32 18 7 30 0 30 50 120 170 140 100 60 7 2 3 2 1 جریمه 2 ـ 2 3 2 1 جریمه عرض 5 7 1 2 1 جریمه 1 روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 3 7 7 7 100 0 2 3 3 3 230 200 2 30 8 18 10 20 15 0 10 5 23 8 ـ ـ ـ 3 50 0 7 3 6 20 10 5 5 2 2 120 60 9 12 32 18 7 30 50 60 روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 2 3 7 7 7 100 0 13 2 3 3 3 230 200 80 30 8 18 10 20 15 0 2 30 10 12 5 23 8 0 ـ ـ ـ ـ 3 50 0 7 3 6 5 5 2 2 120 60 9 12 50 6 20 10 32 18 7 60 روش تقریب وگل ج 5 ج 4 ج 3 ج 2 ج 1 تقاضا 2 3 7 7 7 100 0 13 2 3 3 3 230 200 40 80 ـ ـ ـ ـ 3 50 0 6 5 5 2 2 120 60 0 30 8 18 10 0 20 15 0 2 30 10 12 5 23 0 7 3 9 12 50 8 40 6 20 32 18 10 60 7 60 حل مسأله به روش شدنی گام اول :پیدا کردن یک جواب پایه آغازین سیمپلکس ‏z c محاسبه ی گام دوم: ‏ij ‏zij  cij بهینگی نا مثبت بودند جواب  cij بهینهzijحاصل شده است و توقف اگر تمام می کنیم را انتخاب و اگر همگی نامثبت نبودند در این صورت مثبت ترین متغیر غیر پایه ای متناظر را به عنوان وارد شونده انتخاب می کنیم. گام سوم :متغیر خارج شونده را پیدا می کنیم جواب پایه ای شدنی فعلی را حساب کرده و به گام دوم می رویم. در اسالید های قبلی ما یک سری خصوصیات برای yijرا بیان و اثبات کردیم.پس در پله سنگی هم می گویند به این روش روش این صورت خواهیم داشت ‏ij برای متغیر های غیر پایه ای و بررسی ‏zij  cij cB B  1aij  cij ‏cB yij  cij ‏zij  cij (cuj  cus  cls  clk  cik )  cij بردار yijبوسSیله یSک دور منحصSر بSه فSرد از درآیSه ی ( )i,jو بSرخی بSردار هSای پایSه مشSخص می شSود .بSه این روش روش دور یا مسیر بسته گفته می شود. حل مسأله به روش سیمپلکس برای تعSیین متغSیر خSارج شSونده طبSق آنچSه کSه قبًال در مSورد روش سSیمپلکس میSدانیم. فSرض کنیSد متغSیر وارد شSونده ی xijمشSخص شSده اسSت .اگSر هماننSد فصSل سSوم متغSیر غSیر پایSه ای وارد شSونده افSزایش یابSد و درآیSه -yijk 1باشSد در این صSورت مقSدار متغSیر هSای پایSه نSیز افSزایش می یابSد امSا اگSر درآیSه +yijk 1باشSد افSزایش متغSیر غSیر پایSه ای ‏x ‏x̂lk ‏Sادیر پایSه را lkکSاهش می دهSدتا جSایی کSه یSک متغSیر پایSه بSه عنSوان متغSیر وارد شSونده مق مسSدود کننSده صSفر می شSود .اگSر مقSدار افSزایش متغSیر غSیر پایSه ای وارد شSونده ∆ باشSد و در تکSرار ˆفعلی سSیمپلکس باشSد،در این صSورت بSا آزمSون میSنیمم م ‏Sدار min{ xlk : basic cell (l , ‏hasق) k ‏a 1 نسبت خواهیم داشت: ‏in representation of }) the nonbasic cell(i, j حال در جSدول جدیSد بSرای متغSیر هSای پایSه ای کSه در دور شSرکت کSرده بودنSد مقSدار ∆ را از خانSه هSای بSا ضSریب +1کم کSرده و مقSدار ∆ را بSه خانSه هSای بSا ضSریب -1اضSافه کنیSد .جSدول جدیSد را تشSکیل دهیSد .پایSه هSا و مقSادیر آنهSا را در آن مشSخص کنیSد و دوبSاره بSه گSام دوم برویSد و تا رسیدن به بهینگی این عمل را تکرار کنید مثال 30 پایه ی شدنی به روش گوشه چپ باال بدست استz آمده ij  cij 20 را مقدار برای خانه های غیر پایه محاسبه می کنیم متغیر وارد z22 شونده است min{ x12, x23} min{10,20} 10 5 ‏B 5 ‏B 3 7 ‏B 10 4 4 15B 2 20 25 15 10 ‏z21  c21 4 5 3  2 0 ‏z22  c22 7 5 3  4 1 30 5 20 3 7 )x12  xˆ12   10 100 (leaves the basis ‏x13  xˆ13   5 1015 4 5 15 2 4 10 25 10 10 15 ‏x23  xˆ23   20 1010 )(unchanged ‏x22  تباهیدگی در مسأله حمل و نقل همSانطور کSه در روش سSیمپلکس دیSده شSده در این جSا هم حSالت تباهیSدگی وجSود دارد .البتSه این وضSعیت مشSکل چنSدانی در حSالت عملی بSرای حSل مسSأله بوجSود نمی آورد .نشSانه حSالت تباهیدگی وجود مقدار صفر در یک متغیر پایه است. پایهنقل رخ حمل و کردنجدول تباهیدگی در دو حالت دهد :طSور کSه در روش هSای مSذکور بSرای آغازین:میهمSان جواب مرحله پیدا دردر چیSدا کSردن جSواب پایSه اولیSه دیSدیم بSرخی اوقSات در پیSدا کSردن یSک خانSه پایSه مقSدار عرضSه و تقاضSا بSاهم صSفر می شSوند .یکی از این هSا حSذف و مقSدار صSفر دیگSر بSه مرحلSه بعSدی می رود. در مرحلSه یSا مراحSل بعSدی حتمًSا یSک مقSدار صSفر بSرای خانSه ای کSه در سSطر یSا سSتون صSفر واقSع شده تعلق خواهد گرفت. در مرحله بهبود جواب :هSر گSاه در زمSان بدسSت آوردن متغSیر خSروجی بSا آزمSون میSنیمم مقSدار بSرای خانSه هSای بSا ضSریب +1دو خانSه (پایSه) بSرای انتخSاب داشSته باشSیم .لSذا در گSام بعدی که جدول به روز می شود یک مقدار صفر را برای یک خانه پایه خواهیم داشت. 0 0 10 10 15 10 0 10 15 8 7 0 10 8 7 0 10 تباهیدگی در مسأله حمل و نقل ش رط الزم ب رای تباهی دگی در مس أله حم ل و نق ل :فSرض کنیSد در یSک تکSرار الگSوریتم حمSل و نقSل مSا بSا یSک پایSه شSدنی تباهیSده روبSرو شSویم (ماننSد آنچSه در شSکل می بیSنیم). بSا حSذف خانSه (سSلول) تباهیSده درخت مربSوط بSه پایSه بSه دو مؤلفSه جSدا از هم (جنگSل) تبSدیل می شSود .مجمSوع متغیرهSای پایSه ی موجSود در مؤلفSه ی C1را بSا هم جمSع می کSنیم .در این صSورت ‏dj ‏xij  ‏Si مؤلفSه  xij  لذا داریم Si  d j : ‏ ‏ داشت: خواهیم همچSنین بSرای همSان ‏C1 ‏C1 ‏C1 ‏C1 ‏C1 ‏C1 داریم: پس یک شرط الزم برای تباهیدگی آن است که یک زیرمجموعه مناسب از سطر ها و ستون ها (عرضه ها و تقاضا ها) مجموع یکسانی داشته باشند. گامهای روش راسل .5بعSد از کم کSردن مقSدار تخصیصSی ،اگSر تقاضSا صSفر شSده باشSد بایSد خانSه هSای خSالی سSتون مربوطSه را حSذف کSرد .اگSر ظSرفیت صSفر شSده باشSد بایSد خانSه هSای خSالی سSطر مربوطSه را حSذف کSرد .اگSر تقاضSا و ظSرفیت همزمSان صSفر شSدند یکی را بSه دلخSواه انتخSاب می کSنیم .سSپس بSه گSام 1رفتSه و آنقSدر الگSوریتم را تکرار می کنیم تا تمامی ظرفیت و تقاضاها صفر شوند مثالی از روش راسل ظرفی ت ‏C ‏A ‏B 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 300 360 تقاضا مثالی از روش راسل 24 ظرفی ت ‏C ‏A ‏B 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 300 360 تقاضا مثالی از روش راسل 24 15 ظرفی ت ‏C ‏A ‏B 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 300 360 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 300 360 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 300 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 300 18 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 24 300 18 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B -36 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 24 300 18 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B -30 -36 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 24 300 18 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B -30 -24 -36 400 24 12 15 1 300 15 8 7 2 100 800 21 18 27 3 800 140 24 300 18 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B -30 -24 -36 400 24 12 15 300 15 8 7 2 100 800 21 18 27 3 800 140 24 300 18 -35 360 27 1 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏A ‏B -30 -24 400 24 12 -25 -36 15 -35 1 300 15 8 7 2 100 800 21 18 27 3 800 140 24 300 18 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏B -30 -24 400 24 -24 ‏A 12 -25 -36 15 -35 1 300 15 8 7 2 100 800 21 18 27 3 800 140 24 300 18 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏B -30 -24 400 24 -24 ‏A 12 -25 -36 15 300 15 8 7 100 800 21 18 27 800 140 24 300 18 -35 -27 1 2 3 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C ‏B -30 -24 400 24 300 15 8 100 800 21 18 800 -24 140 24 ‏A 12 -25 -27 -36 15 7 -35 -27 27 300 18 1 2 3 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C 400 300 15 100 800 21 800 ‏B -30 -24 24 -24 -30 ‏A 12 8 -25 -27 18 140 24 -36 15 7 -35 -27 27 300 18 1 2 3 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏C 400 300 15 100 800 21 800 ‏B -30 -24 24 -24 -30 ‏A 12 8 -25 -27 18 140 24 -36 15 7 -35 -27 27 300 18 1 2 3 360 27 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏B ‏C ‏A 36 0 40 400 24 12 15 300 15 8 7 2 100 800 21 18 27 0 3 800 140 24 300 18 360 27 1 تقاضا مثالی از روش راسل 24 15 27 ظرفی ت ‏B ‏C ‏A 36 0 40 400 24 12 300 15 8 2 100 800 21 18 3 800 140 24 15 300 18 0 360 27 1 تقاضا مثالی از روش راسل 24 24 15 15 21 27 ظرفی ت ‏C -30 -24 40 24 300 15 100 800 21 800 ‏B -24 -24 12 -25 8 15 ‏A 36 0 1 2 -21 3 18 140 24 300 18 0 27 24 18 - تقاضا مثالی از روش راسل 24 24 15 15 21 27 ظرفی ت 0 ‏B 40 ‏C 40 24 12 300 15 8 2 100 800 21 140 24 18 260 300 18 3 0 27 24 18 - 800 15 ‏A 36 0 1 تقاضا مثالی از روش راسل 24 24 15 15 21 27 ظرفی ت 0 ‏C 40 ‏B 40 15 12 ‏A 36 0 1 300 15 8 2 100 800 21 140 24 18 260 300 18 3 0 27 24 18 - 800 تقاضا مثالی از روش راسل - 24 24 15 15 15 21 21 27 ظرفی ت ‏C 0 ‏B 40 -24 300 15 100 800 21 800 -21 12 -25 8 15 ‏A 36 0 1 2 -21 3 18 140 24 260 18 0 27 24 18 - 21 18 - تقاضا مثالی از روش راسل - 24 24 15 15 15 21 21 27 ظرفی ت ‏C 0 40 300 15 100 800 21 800 ‏B 40 26 12 0 8 140 24 18 0 15 ‏A 36 0 1 2 3 260 18 0 27 24 18 - 21 18 - تقاضا مثالی از روش راسل - 24 24 15 15 15 21 21 27 ظرفی ت ‏C 0 40 300 15 100 800 21 800 ‏B 40 26 12 0 8 15 ‏A 36 0 1 2 3 140 24 0 260 18 0 27 24 18 - 21 18 - تقاضا مثالی از روش راسل - 24 24 15 15 15 21 21 27 ظرفی ت ‏C 0 0 40 40 15 ‏B 40 26 12 0 8 15 ‏A 36 0 1 2 3 21 100 800 800 100 140 24 0 18 0 27 24 18 - 21 18 - تقاضا مثالی از روش راسل - 24 24 15 15 15 21 21 ظرفی ت 0 ‏C 40 0 10 15 27 0 0 21 100 800 800 0 100 24 ‏B 40 26 12 0 8 15 ‏A 36 0 1 2 3 0 18 0 27 24 18 - 21 18 - تقاضا مثالی از روش راسل ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 26 12 0 8 7 2 18 27 3 300 15 ‏A 36 0 360 1 تقاضا گامهای روش پله سنگ .1انتخاب یک خانه خالی جدول (خانه ای که مقدار نگرفته است) .2رسم پله سنگ برای خانه خالی مربوطه .1.2بSرای رسSم پلSه سSنگ خانSه خSالی ،از آن خانSه شSروع بSه حSرکت کSرده و بSا حرکتهSای افقی و عمSودی از روی خانSه هSای پر (متغیر اساسی) باید به آن خانه برگردیم. .2.2در رسSم پلSه سSنگ ،تغیSیر جهت فقSط روی خانSه هSای پSر صورت می گیرد. .3.2از خانه های خالی فقط عبور می توان کرد. .4.2از روی خانSه هSای پSر می تSوان عبSور کSرد یSا تغیSیر جهت داد. گامهای روش پله سنگ .3عالمت گذاری پله سنگ :خانه خالی مربوطه را عالمت +و به بقیه خانه ها یکی در میان – و +می دهیم. .4محاسSبه ارزش پلSه سSنگ :جمSع جSبری هزینSه تمSامی گوشSه هSا با توجه به عالمت آنها .5انجام گامهای 1تا 4برای تمامی خانه های خالی جدول .6انتخاب پله سنگ با منفی ترین ارزش .1.6انتخSاب متغSیر ورودی :خانSه خSالی پلSه سSنگ مربوطه .2.6انتخSاب متغSیر خSروجی :کوچکSترین ُپر خSالی بSا عالمت منفی گامهای روش پله سنگ .7بهبود پله سنگ :مقدار متغیر خروجی به خانه های با عالمت +اضافه و از خانه های با عالمت – کم می شود .8گامهای 1تا 8آنقدر تکرار می شوند تا هیچ پله سنگی با ارزش منفی وجود نداشته باشد مثالی از مسیریابی ظرفی ت ‏G ‏F ‏E 100 ‏D ‏C * * 200 ‏B 1 * 300 * 400 * 100 * * * 2 3 4 500 100 ‏A 200 * * 100 100 200 * 5 * 6 600 300 تقاض ا مثالی از مسیریابی ظرفی ت ‏G ‏F ‏E 100 ‏D ‏C * * 200 ‏B 1 * 300 * 400 * 100 * * * 2 3 4 500 100 ‏A 200 * * 100 100 200 * 5 * 6 600 300 تقاض ا مثالی از مسیریابی ظرفی ت ‏G ‏F ‏E 100 ‏D ‏C * * 200 ‏B 1 * 300 * 400 * 100 * * * 2 3 4 500 100 ‏A 200 * * 100 100 200 * 5 * 6 600 300 تقاض ا مثالی از مسیریابی ظرفی ت ‏G ‏F ‏E 100 ‏D ‏C * * 200 ‏B 1 * 300 * 400 * 100 * * * 2 3 4 500 100 ‏A 200 * * 100 100 200 * 5 * 6 600 300 تقاض ا مثالی از مسیریابی ظرفی ت ‏G ‏F ‏E 100 ‏D ‏C * * 200 ‏B 1 * 300 * 400 * 100 * * * 2 3 4 500 100 ‏A 200 * * 100 100 200 * 5 * 6 600 300 تقاض ا مثالی از روش پله سنگ فرض کنیSد جوابهSای اولیSه زیSر از روش راسSل بدسSت آمSده انSد و قرار است با روش پله سنگ بهبود پیدا کنند ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 26 12 0 8 7 2 18 27 3 300 15 ‏A 36 0 360 1 تقاضا خانه های خالیهای خانه پر مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 26 12 0 8 7 2 18 27 3 300 15 ‏A 36 0 1 تقاضا 360 + 1C - + مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 26 12 0 8 7 2 18 27 3 300 15 ‏A 36 0 1 تقاضا 360 + 2A - + مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 26 12 0 8 7 2 18 27 3 300 15 ‏A 36 0 1 360 تقاضا + - + 3A - + مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 26 12 0 8 7 2 18 27 3 300 15 ‏A 36 0 1 تقاضا 360 + 3B - + مثالی از روش پله سنگ 1C 2A 3A 3B مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 ‏B 40 26 12 0 8 7 2 18 27 3 140 26 0 15 ‏A 36 0 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 ‏B 40 26 12 0 8 18 140 26 0 ‏A 36 0 26 15 0 7 2 27 3 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 ‏B 40 12 8 18 140 26 0 ‏A 36 0 26 15 0 7 2 27 3 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 12 8 18 140 26 0 ‏B 30 0 ‏A 36 0 26 15 0 7 2 27 3 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 12 8 18 140 26 0 ‏B 30 0 ‏A 10 0 26 15 0 7 2 27 3 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 15 100 800 21 - 800 40 10 0 140 + ‏B 30 0 12 8 18 + 300 2B + - - + - 3B 2 27 3 360 2C + - + ‏A 10 0 26 15 0 7 - 1 تقاضا + - + 3A - + مثالی از روش پله سنگ - + 2C - این جواب بهینه است - + + 2B + - + 3A - + - + - 3B + + مثالی از روش پله سنگ ظرفی ت ‏C 400 24 300 10 15 0 21 100800 800 40 140 12 ‏B 30 0 8 18 300 ‏A 10 0 26 15 0 7 2 27 3 360 1 تقاضا مثالی از روش پله سنگ جواب اولیSه مسSئله زیSر را از روش گوشSه شSمالغربی بدسSت آورده و با روش پله سنگ بهبود دهید؟ ظرفی ت ‏C ‏A ‏B 300 15 12 9 1 200 8 11 7 2 200 17 18 10 3 240 200 260 تقاضا گامهای روش توزیع تعدیل شده .1.3رسم پله سنگ برای خانه خالی آن .2.3انتخاب متغیر ورودی :خانه خالی پله سنگ مربوطه .3.3انتخSاب متغSیر خSروجی :کوچکSترین خانSه پSر بSا عالمت منفی گامهای روش توزیع تعدیل شده .4بهبود پله سنگ :مقدار متغیر خروجی به خانه های با عالمت +اضافه و از خانه های با عالمت – کم می شود .5گامهای 1تا 5آنقدر تکرار می شوند تا هیچ پله سنگی با ارزش منفی وجود نداشته باشد مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 26 12 0 8 7 2 18 27 3 300 15 ‏A 36 0 360 1 تقاضا مثالی از روش توزیع تعدیل شده مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 26 12 0 8 7 2 18 27 3 300 15 ‏A 36 0 360 1 تقاضا مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 ‏B 40 40 10 0 140 متغیر خروجی 26 0 26 12 0 8 7 2 18 27 3 300 + 360 2A - 15 ‏A 36 0 + 1 تقاضا 36 0 متغیر ورودی مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 ‏B 40 26 12 0 8 18 140 26 0 ‏A 36 0 26 15 0 7 2 27 3 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 ‏B 40 12 8 18 140 26 0 ‏A 36 0 26 15 0 7 2 27 3 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 12 8 18 140 26 0 ‏B 30 0 ‏A 36 0 26 15 0 7 2 27 3 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 متغیر خروجی 40 10 0 12 8 18 140 26 0 ‏B 30 0 ‏A 10 0 26 15 0 7 2 27 3 300 + 2A - تقاضا 360 + 1 36 0 متغیر ورودی مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 12 ‏B 30 0 8 18 300 ‏A 10 0 26 15 0 7 2 27 3 360 1 تقاضا مثالی از روش توزیع تعدیل شده مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 15 100 800 21 800 40 10 0 140 ‏B 40 12 8 18 300 ‏A 36 0 26 15 0 7 2 27 3 360 1 تقاضا جواب بهینه است مثالی از روش توزیع تعدیل شده ظرفی ت ‏C 400 24 300 10 15 0 21 100800 800 40 140 12 ‏B 30 0 8 18 300 ‏A 10 0 26 15 0 7 2 27 3 360 1 تقاضا