نویسنده : مانوئل ا.
مقدمه
در برنامه ریزی خطی می توان مسائل مختلف از قبیل ترکیب تولید ، سرمایه گذاری ، بازار یابی ، حمل و نقل ، فرمولاسیون محصول ، زمان بندی چند دوره ای و ... را مدل سازی کرده با استفاده از نرم افزارهای مربوطه به حل آن بپردازیم.
دراین مقاله ضمن آموزش نرم افزار لینگو در قالب فلش، به حل نمونه ای از مسئله برنامه ریزی خطی پرداخته میشود.
فرم عمومی برنامه ریزی خطی
1- تابع هدف Objective Function
سیاست و هدف از طرح مسئله است که در اغلب مسائل به صورت ماکسیمم (حداکثر سود ، بازدهی و ...) و در برخی موارد (مانند حداقل هزینه ) این تابع مینیمم در نظر گرفته می شود.
2- متغیر های تصمیم Decision Variable
متغیر هایی هستند که تاثیر مستقیم بر تابع هدف دارند و محدودیتها بر اساس آنها لحاظ می گردد. انتخاب متغیرهای تصمیم برای حل مدل برنامه ریزی خطی بسیار حائز اهمیت می باشد.
متغیر های تصمیم غالبا به صورت غیر منفی در نظر گرفته می شوند و در برخی موارد نیز می توانند آزاد در علامت ( غیر مثبت ) باشند.
3- محدودیت ها Constraints
شامل محدودیتها و سیاست های مختلفی است که جهت تحقق تابع هدف با استفاده از متغیر های تصمیم درنظر گرفته می شود .
تعاریف مختلف
- جواب :
کلیه مقادیری که متغیرهای تصمیم اختیار میکنند به تنهایی یک جواب محسوب می شوند.
- جواب موجه :
جوابی است که در تمام محدودیت ها صدق می کند.
- منطقه موجه :
ناحیه ای از جواب های موجه است که در همه محدودیت ها صادق است.
- جواب غیر موجه :
کلیه مقادیری که خارج از منطقه موجه قرار دارند.
- جواب بهینه :
جوابی است که به ازای آن مقدار تابع هدف مطلوب ترین و بهینه ترین وضعیت خود را داراست. ( برای تابع هدف ماکسیمم ، جواب هایی که تابع را حد اکثر و برای مینیمم ، حداقل کنند )
به عبارتی دیگر هر یک از جواب های بهینه مشخص می کند که از هر متغیر تصمیم چه تعداد (مقدار ) تخصیص یابد تا تابع هدف ماکسیمم یا مینیمم شود .
جواب های بهینه اصلی ترین هدف تشکیل مدل برنامه ریزی خطی است .
قابل ذکر است نرم افزار لینگو ( که فایل آموزش آن در این مقاله ضمیمه شده است ) ، جواب های بهینه را در اختیار ما قرار میدهد.
- جواب های بهینه مدل برنامه ریزی خطی ، ممکن است انواع مختلفی داشته باشند که به شرح ذیل بیان می گردد....
الف : جواب بهینه چند گانه داشته باشد:
ممکن است بیش از یک جواب موجه مقدار تابع هدف را مطلوب ترین نماید که در این صورت همه ی آنها جواب بهینه خواهند بود .
ب : فاقد جواب بهینه باشد :
در این حالت مدل جواب بهینه ندارد و این در واقعیت امکان پذیر نیست ، در چنین صورتی باید مجددا مسئله را فرموله و حل نماییم .
ج: ناحیه جواب ، بی کران باشد :
چنانچه با این حالت مواجه شویم باید بر مشاهده و تعریف مدل بازنگری کنیم که قطعا اشتباهی رخ داده و باید رفع شود .
4 - متغیر های کمکی
از آنجا که مدودیت ها در مدل باید بصورت تساوی باشند ، لذا برای استاندارد کردن آنها از متغیر های کمکی استفاده می شود که بر دو نوع است :
Slack Variable 1-4 متغیرهای لنگی
برای استاندارد کردن محدودیت هایی که به صورت کوچکتر یا مساویند استفاده می شود . متغیر های لنگی همواره بزرگتر از صفرند.
Artificial Variable 2-4 متغیرهای مصنوعی
برای استاندارد سازی محدودیت های تساوی ( به محدودیت افزوده میشوند ) و محدودیت های بزگتر مساوی ( یک لنگی اضاف و یک مصنوعی از محدودیت کاسته) ،استفاده می شوند .
گفتنی است متغیر های کمکی فقط در محاسبات دستی کاربرد دارند و محاسبات نرم اقاری خود به خود لحاظ می شود .
بعد از آن که مسئله مورد نظر را با رعایت فرم عمومی مدل برنامه ریزی خطی فرموله کردیم ، حاصل را در نرم افزارهای مربوطه وارد کرده و جواب های بهینه را استخراج میکنیم .
حل یک مسئله نمونه با استفاده از نرم افزار لینگو :
صورت مسئله :
شرکتی مونتاژ محصول را که شامل قاب – میله فلزی و بلبرینگ است ، برعهده دارد . شرکت میله ی فلزی و قاب را تولید می کند و بلبرینگ را از تولید کننده دیگری خریداری می کند ، هر میله ی فلزی باید مراحل ماشین سندان ، ماشین تراش و ماشین تبزکن را بگذراند ، این مراحل به ترتیب 1/2 ساعت ، 0/2 ساعت و 0/3 ساعت برای هر میله ی فلزی وقت می گیرد . هر قاب نیز 0/8 ساعت در ماشین سندان ، 0/1 ساعت در ماشین سوراخ کننده ، 0/3 ساعت در آسیاب و 0/5 ساعت در ماشین تبزکن ، وقت می گیرد .
شرکت 5 ماشین تراش ، 10 ماشین تیزکن ، 20 ماشین سندان و 3 ماشین سوراخکن و 6 آسیاب دارد ، برآورد شده است هر ماشین ماکزیمم 2400 ساعت در هر سال کار می کند .
مسئله را برای ماکزیمم تعداد مولفه های محصول تولید به مونتاژ حل می کنیم ...
حل مسئله :
گام اول : انتخاب متغیر های تصمیم
A : تعداد میله فلزی که در یک سال باید تولید شود
B : تعداد قاب که در یک سال باید تولید شود د
گام دوم : محاسبات لازم
ماکزیمم ساعت کار 20 ماشین سندان در یکسال 48000= 20 * 2400
ماکزیمم ساعت کار 5 ماشین تراش در یکسال 12000= 5 * 2400
ماکزیمم ساعت کار 10 ماشین تیز کن در یکسال 24000= 10 * 2400
ماکزیمم ساعت کار 3 ماشین تراش در یکسال 12000= 3 * 2400
ماکزیمم ساعت کار 6 ماشین آسیاب در یکسال 14400= 6 * 2400
گام سوم : تشکیل تابع هدف
گام چهار : شروع کار با نرم افزار
مدل تایپ شده زیر را عینا در نرم افزار تایپ می کنیم .
می توانید فایل آموزش Lingo 10.0 را از لینک های زیر دانلود نمایید
( فایل های آموزشی فوق توسط اینجانب به صورت کاملا مالتی مدیا در قالب فلش تهیه گردیده است .)
درس اول : آشنایی با نوار ابزار و گزینه های مهم در لینگو
فرمت فایل دانلودی : Zip ، بعد از دانلود آنرا از حالت فشرده در بیاورید .
سایز فایل دانلودی: 1.72 MB
درس دوم : اصول وارد کردن اطلاعات و مدل مورد نظر
فرمت فایل دانلودی : Zip ، بعد از دانلود آنرا از حالت فشرده در بیاورید .
سایز فایل دانلودی: 1.48 MB
درس سوم : اعمال تنظیمات روی مدل و دریافت جواب های بهینه
فرمت فایل دانلودی : Zip ، بعد از دانلود آنرا از حالت فشرده در بیاورید .
سایز فایل دانلودی: 1.65 MB
منبع : مرجع مهندسی صنایع
© تمام حقوق این اثر متعلق به گروه مانو تک و پرتال اینن می باشد ...
هرگونه سئوال ، پیشنهاد و انتقاد خود را در رابطه با این مقاله و فایل آموشی و یا خود برنامه ، می توانید از طریق همین بخش ارائه نمایید ...
مقدمه
در برنامه ریزی خطی می توان مسائل مختلف از قبیل ترکیب تولید ، سرمایه گذاری ، بازار یابی ، حمل و نقل ، فرمولاسیون محصول ، زمان بندی چند دوره ای و ... را مدل سازی کرده با استفاده از نرم افزارهای مربوطه به حل آن بپردازیم.
دراین مقاله ضمن آموزش نرم افزار لینگو در قالب فلش، به حل نمونه ای از مسئله برنامه ریزی خطی پرداخته میشود.
فرم عمومی برنامه ریزی خطی
1- تابع هدف Objective Function
سیاست و هدف از طرح مسئله است که در اغلب مسائل به صورت ماکسیمم (حداکثر سود ، بازدهی و ...) و در برخی موارد (مانند حداقل هزینه ) این تابع مینیمم در نظر گرفته می شود.
2- متغیر های تصمیم Decision Variable
متغیر هایی هستند که تاثیر مستقیم بر تابع هدف دارند و محدودیتها بر اساس آنها لحاظ می گردد. انتخاب متغیرهای تصمیم برای حل مدل برنامه ریزی خطی بسیار حائز اهمیت می باشد.
متغیر های تصمیم غالبا به صورت غیر منفی در نظر گرفته می شوند و در برخی موارد نیز می توانند آزاد در علامت ( غیر مثبت ) باشند.
3- محدودیت ها Constraints
شامل محدودیتها و سیاست های مختلفی است که جهت تحقق تابع هدف با استفاده از متغیر های تصمیم درنظر گرفته می شود .
تعاریف مختلف
- جواب :
کلیه مقادیری که متغیرهای تصمیم اختیار میکنند به تنهایی یک جواب محسوب می شوند.
- جواب موجه :
جوابی است که در تمام محدودیت ها صدق می کند.
- منطقه موجه :
ناحیه ای از جواب های موجه است که در همه محدودیت ها صادق است.
- جواب غیر موجه :
کلیه مقادیری که خارج از منطقه موجه قرار دارند.
- جواب بهینه :
جوابی است که به ازای آن مقدار تابع هدف مطلوب ترین و بهینه ترین وضعیت خود را داراست. ( برای تابع هدف ماکسیمم ، جواب هایی که تابع را حد اکثر و برای مینیمم ، حداقل کنند )
به عبارتی دیگر هر یک از جواب های بهینه مشخص می کند که از هر متغیر تصمیم چه تعداد (مقدار ) تخصیص یابد تا تابع هدف ماکسیمم یا مینیمم شود .
جواب های بهینه اصلی ترین هدف تشکیل مدل برنامه ریزی خطی است .
قابل ذکر است نرم افزار لینگو ( که فایل آموزش آن در این مقاله ضمیمه شده است ) ، جواب های بهینه را در اختیار ما قرار میدهد.
- جواب های بهینه مدل برنامه ریزی خطی ، ممکن است انواع مختلفی داشته باشند که به شرح ذیل بیان می گردد....
الف : جواب بهینه چند گانه داشته باشد:
ممکن است بیش از یک جواب موجه مقدار تابع هدف را مطلوب ترین نماید که در این صورت همه ی آنها جواب بهینه خواهند بود .
ب : فاقد جواب بهینه باشد :
در این حالت مدل جواب بهینه ندارد و این در واقعیت امکان پذیر نیست ، در چنین صورتی باید مجددا مسئله را فرموله و حل نماییم .
ج: ناحیه جواب ، بی کران باشد :
چنانچه با این حالت مواجه شویم باید بر مشاهده و تعریف مدل بازنگری کنیم که قطعا اشتباهی رخ داده و باید رفع شود .
4 - متغیر های کمکی
از آنجا که مدودیت ها در مدل باید بصورت تساوی باشند ، لذا برای استاندارد کردن آنها از متغیر های کمکی استفاده می شود که بر دو نوع است :
Slack Variable 1-4 متغیرهای لنگی
برای استاندارد کردن محدودیت هایی که به صورت کوچکتر یا مساویند استفاده می شود . متغیر های لنگی همواره بزرگتر از صفرند.
Artificial Variable 2-4 متغیرهای مصنوعی
برای استاندارد سازی محدودیت های تساوی ( به محدودیت افزوده میشوند ) و محدودیت های بزگتر مساوی ( یک لنگی اضاف و یک مصنوعی از محدودیت کاسته) ،استفاده می شوند .
گفتنی است متغیر های کمکی فقط در محاسبات دستی کاربرد دارند و محاسبات نرم اقاری خود به خود لحاظ می شود .
بعد از آن که مسئله مورد نظر را با رعایت فرم عمومی مدل برنامه ریزی خطی فرموله کردیم ، حاصل را در نرم افزارهای مربوطه وارد کرده و جواب های بهینه را استخراج میکنیم .
حل یک مسئله نمونه با استفاده از نرم افزار لینگو :
صورت مسئله :
شرکتی مونتاژ محصول را که شامل قاب – میله فلزی و بلبرینگ است ، برعهده دارد . شرکت میله ی فلزی و قاب را تولید می کند و بلبرینگ را از تولید کننده دیگری خریداری می کند ، هر میله ی فلزی باید مراحل ماشین سندان ، ماشین تراش و ماشین تبزکن را بگذراند ، این مراحل به ترتیب 1/2 ساعت ، 0/2 ساعت و 0/3 ساعت برای هر میله ی فلزی وقت می گیرد . هر قاب نیز 0/8 ساعت در ماشین سندان ، 0/1 ساعت در ماشین سوراخ کننده ، 0/3 ساعت در آسیاب و 0/5 ساعت در ماشین تبزکن ، وقت می گیرد .
شرکت 5 ماشین تراش ، 10 ماشین تیزکن ، 20 ماشین سندان و 3 ماشین سوراخکن و 6 آسیاب دارد ، برآورد شده است هر ماشین ماکزیمم 2400 ساعت در هر سال کار می کند .
مسئله را برای ماکزیمم تعداد مولفه های محصول تولید به مونتاژ حل می کنیم ...
حل مسئله :
گام اول : انتخاب متغیر های تصمیم
A : تعداد میله فلزی که در یک سال باید تولید شود
B : تعداد قاب که در یک سال باید تولید شود د
گام دوم : محاسبات لازم
ماکزیمم ساعت کار 20 ماشین سندان در یکسال 48000= 20 * 2400
ماکزیمم ساعت کار 5 ماشین تراش در یکسال 12000= 5 * 2400
ماکزیمم ساعت کار 10 ماشین تیز کن در یکسال 24000= 10 * 2400
ماکزیمم ساعت کار 3 ماشین تراش در یکسال 12000= 3 * 2400
ماکزیمم ساعت کار 6 ماشین آسیاب در یکسال 14400= 6 * 2400
گام سوم : تشکیل تابع هدف
Max = A + B
0.2*A<=12000
0.3*A+0.5*B<=24000
0.1*B<=7200
0.3*B<=14400
A>=0 , B>=0
گام چهارم : اعمال محدودیت ها
0.5*A+0.8*B<=480000.2*A<=12000
0.3*A+0.5*B<=24000
0.1*B<=7200
0.3*B<=14400
A>=0 , B>=0
گام چهار : شروع کار با نرم افزار
مدل تایپ شده زیر را عینا در نرم افزار تایپ می کنیم .
Max = A + B ;
0.5*A+0.8*B<=48000;
0.2*A<=12000;
0.3*A+0.5*B<=24000;
0.1*B<=7200;
0.3*B<=14400;
A>=0;
B>=0
0.5*A+0.8*B<=48000;
0.2*A<=12000;
0.3*A+0.5*B<=24000;
0.1*B<=7200;
0.3*B<=14400;
A>=0;
B>=0
می توانید فایل آموزش Lingo 10.0 را از لینک های زیر دانلود نمایید
( فایل های آموزشی فوق توسط اینجانب به صورت کاملا مالتی مدیا در قالب فلش تهیه گردیده است .)
درس اول : آشنایی با نوار ابزار و گزینه های مهم در لینگو
فرمت فایل دانلودی : Zip ، بعد از دانلود آنرا از حالت فشرده در بیاورید .
سایز فایل دانلودی: 1.72 MB
درس دوم : اصول وارد کردن اطلاعات و مدل مورد نظر
فرمت فایل دانلودی : Zip ، بعد از دانلود آنرا از حالت فشرده در بیاورید .
سایز فایل دانلودی: 1.48 MB
درس سوم : اعمال تنظیمات روی مدل و دریافت جواب های بهینه
فرمت فایل دانلودی : Zip ، بعد از دانلود آنرا از حالت فشرده در بیاورید .
سایز فایل دانلودی: 1.65 MB
منبع : مرجع مهندسی صنایع
© تمام حقوق این اثر متعلق به گروه مانو تک و پرتال اینن می باشد ...
هرگونه سئوال ، پیشنهاد و انتقاد خود را در رابطه با این مقاله و فایل آموشی و یا خود برنامه ، می توانید از طریق همین بخش ارائه نمایید ...
