Online User مدلسازی - مدیریت صنعتی Industrial Management

مدیریت صنعتی Industrial Management

مدیریت صنعتی - تحقیق در عملیات - مدیریت تولید - ...

مدلسازی توابع غیر خطی به روش تقریب
نویسنده : محسن رحیمی - ساعت ٦:٢٥ ‎ب.ظ روز ۱۳٩٤/٤/۱٩
 

یکی از کاربردهای مهم مدلسازی توابع خطی تکه ای که در مطلب مرتبط قبلی به آن پرداختیم، تقریب توابع غیر خطی است. شکل 1، یک تابع غیرخطی (مربوط به سود) را که مشابه آن در دنیای واقعی بسیار دیده می شود را در نظر بگیرید. برای تقریب خطی این تابع به سادگی می توان از یک تابع خطی تکه ای پیوسته استفاده نمود. برای تقریب خطی تابع مورد نظر لازم است آن را به چند بخش (نه لزوماً مساوی) تقسیم نماییم. فرض کنید ...

برای مطالعه متن کامل روی "ادامه مطلب" کلیک نمایید.

(400 کلمه)

مطلب مرتبط بعدی: منتشر نشده است

مطلب مرتبط قبلی: مدلسازی توابع خطی تکه ای


 
 
ترجمه جزوه بهینه سازی عدم قطعیت دانشگاه MIT
نویسنده : محسن رحیمی - ساعت ٥:۳٦ ‎ب.ظ روز ۱۳٩۱/۱٠/٢٩
 

جزوه ای که در این مطلب ارائه شده است ترجمه بخش "بهینه سازی عدم قطعیت" (optimization under Uncertainty) جزوه درس بهینه سازی سیستم ها: مدل ها و محاسبات دانشگاه MIT آمریکا است که توسط دکتر Robert M.Freund در سال 2004 تدریس شده است.  این بخش از جزوه توسط نویسنده وبلاگ ترجمه شده و در 23 صفحه و در قالب  PDF ارائه می گردد.

   فهرست مطالب و یک صفحه نمونه را می توانید در ادامه مطلب ببینید.

جهت دریافت اطلاعات نحوه خرید این فایل با m.rahimi.m@gmail.com تماس بگیرید.


 
 
مدلسازی توابع خطی تکه ای (Piecewise Linear Functions)
نویسنده : محسن رحیمی - ساعت ٩:۱٤ ‎ب.ظ روز ۱۳٩۱/۱٠/۱٥
 

بسیاری از مسائل دنیای واقعی را می توان به صورت توابع خطی تکه ای پیوسته (Piecewise Linear Function) مدل نمود. برای مثال در مواردی که تغییر مقیاس تولید منجر به افزایش و یا کاهش هزینه ها می شود، به نوعی با توابع خطی تکه ای روبرو هستیم. برای اینکه بیشتر با توابع خطی تکه ای آشنا شویم، نمونه ای از آن را در شکل مجاور نشان داده ایم. همان طور که می بینید تابع مورد نظر یک تابع خطی سه تکه است که میزان سود را بر اساس سطح فعالیت شرکت ...

جهت مطالعه متن کامل روی گزینه "ادامه مطلب" کلیک کنید.

(400 کلمه)

مطلب مرتبط بعدی: مدلسازی توابع غیر خطی به روش تقریب

مطلب مرتبط قبلی: مدلسازی و ایجاد رابطه بین محدودیت ها و تابع هدف


 
 
مدلسازی و ایجاد رابطه بین محدودیت ها و تابع هدف
نویسنده : محسن رحیمی - ساعت ۱۱:۱٧ ‎ب.ظ روز ۱۳٩۱/٦/۱٧
 

استفاده از متغیرهای باینری باعث می شود مدلسازی بسیاری از موقعیت های واقعی ساده تر انجام شود و حتی می توان گفت مدلسازی برخی مسائل پیچیده، بدون آنها غیر ممکن می نماید. یکی از مشهورترین مسائلی متغیر باینری در آن نقش بسزایی ایفا می کند مسئله موسوم به fixed-charge یا طبق ترجمه تحت الفظی، مسئله هزینه ثابت است. 

برای مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(700 کلمه)

مطلب مرتبط بعدی: مدلسازی توابع خطی تکه ای

مطلب مرتبط قبلی: مدلسازی گزینه های ناسازگار و تصمیم گیری مشروط


 
 
مدلسازی گزینه های ناسازگار و تصمیم گیری مشروط
نویسنده : محسن رحیمی - ساعت ٩:٠٧ ‎ب.ظ روز ۱۳٩٠/۱٢/٦
 

گاهی اوقات در مدلسازی ریاضی، با موقعیت هایی روبرو هستیم که در آنها باید گزینه های ناسازگار و تصمیم گیری های مشروط را در نظر بگیریم. گزینه های ناسازگار می توانند هم در سطح متغیرهای تصمیم و هم در سطح محدودیت ها مطرح شوند. در ...

جهت مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(500 کلمه)

 

مطلب مرتبط بعدی: مدلسازی و ایجاد رابطه بین محدودیت ها و تابع هدف

مطلب مرتبط قبلی: مدلسازی توابعی با N مقدار ممکن


 
 
مدلسازی توابعی با N مقدار ممکن
نویسنده : محسن رحیمی - ساعت ۱٠:۱۳ ‎ب.ظ روز ۱۳٩٠/۱۱/۱۱
 

یکی از تکنیک های مدلسازی تکنیک مدل کردن تابعی است که می تواند مقادیر گسسته مختلفی را بگیرد. منظور تابعی است که بر اساس تغییر شرایط می توان نتایج مختلف اما گسسته ای ارائه دهد. برای مثال فرض کنید شرکتی بخواهد کالایی را خریداری کند. اما تامین کننده کالا شرط گذاشته است که تعداد ...

برای مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(380 کلمه)

مطلب مرتبط بعدی:

مطلب مرتبط قبلی: محدودیت های تصمیم گیری بله - خیر


 
 
محدودیت‌های تصمیم گیری بله- خیر (Yes-or-No Decisions)
نویسنده : محسن رحیمی - ساعت ٩:۱۳ ‎ب.ظ روز ۱۳٩٠/۱٠/۱٢
 

مسائل تصمیم گیری زیادی وجود دارند که شامل تعدادی تصمیم گیری بله – خیر هستند. در چنین تصمیم گیری‌هایی، تنها دو گزینه بله و خیر وجود دارد. برای مثال اینکه در پروژه‌ای خاص سرمایه گذاری کنیم یا خیر؟ یا فرد خاصی را استخدام کنیم یا خیر؟ یا ...

جهت مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(470 کلمه)

مطلب مرتبط بعدی: مدلسازی توابعی با N مقدار ممکن

مطلب مرتبط قبلی: محدودیت های انتخاب K از N


 
 
محدودیت‌های انتخاب K از N
نویسنده : محسن رحیمی - ساعت ۱٠:٠٧ ‎ب.ظ روز ۱۳٩٠/٩/٢٦
 

مسئله‌ای را در نظر بگیرید که در مدل ریاضی آن، یک مجموعه Nتایی محدودیت وجود دارد ولی تنها Kمحدودیت از آن‌ها می‌توانند فعال باشند (K<N). در نتیجه مدل باید به صورتی نوشته شود که فرآیند بهینه سازی، ترکیبی از Kمحدودیت را به ترتیبی انتخاب کند که بهترین جواب بهینه ممکن برای مدل به دست آید. تعداد N-K محدودیتی که انتخاب نمی‌شوند، در ...

برای مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(450 کلمه)

مطلب مرتبط بعدی:محدودیت های تصمیم گیری بله - خیر

مطلب مرتبط قبلی: محدودیت های یا این یا آن


 
 
محدودیت های یا این یا آن (Either-or Constraints)
نویسنده : محسن رحیمی - ساعت ٦:٢٦ ‎ب.ظ روز ۱۳٩٠/٩/۱٦
 

در هنگام برنامه ریزی و کنترل پروژه، ممکن است به دلایلی به این نتیجه برسیم که دو یا چند فعالیت مشخص را نتوان به صورت همزمان اجرا نمود و بنابراین باید مشخص شود کدام فعالیت بر دیگری ارجحیت دارد. با فرض اینکه فعالیت های مورد نظر مستقل از یکدیگر باشند، از لحاظ اجرایی تفاوتی نمی کند که کدام فعالیت زودتر انجام شود. اما مسلماً یکی از این انتخاب ها منجر به جواب بهینه بهتری خواهد شد. سوال اینجاست که مدل مسئله را چگونه بنویسیم که این نکته را در نظر بگیرد...

جهت مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(480 کلمه)

مطلب مرتبط بعدی: محدودیت‌های انتخاب K از N

مطلب مرتبط قبلی: محدودیت های ترجیح


 
 
محدودیت های ترجیح (Precedence Constraints)
نویسنده : محسن رحیمی - ساعت ٥:٢٧ ‎ب.ظ روز ۱۳٩٠/٩/٤
 

در برنامه ریزی تولید و یا برنامه ریزی پروژه، کارها، وظایف و فعالیت ها باید بر اساس ترتیب خاصی انجام گیرند. ترتیب انجام کارها در مواردی از قبل تعیین شده است مثل پروژه ها و در مواردی نیز هنگام انجام کارها، ترتیب مورد نظر مشخص می شود. برای نمونه هایی که ترتیب از قبل تعیین شده، مثلاً به دلایل فنی، محاسبه زمان شروع و پایان هر فعالیت از ...

برای مطالعه متن کامل این مقاله روی "ادامه مطلب" کلیک کنید.

(220 کلمه)

مطلب مرتبط بعدی: محدودیت های یا این یا آن (Either-or Constraints)

مطلب مرتبط قبلی: مدلسازی مسائل مدیریت پروژه


 
 
محصول هفته: کتاب مدلسازی ریاضی مسائل بهینه سازی (جلد اول)
نویسنده : محسن رحیمی - ساعت ۱٠:٢٠ ‎ب.ظ روز ۱۳٩٠/۸/٢۳
 

عنوان: مدلسازی ریاضی مسائل بهینه سازی (جلد اول)

مولف: محسن رحیمی (نویسنده وبلاگ)

فرمت: PDF

تعداد صفحات: 94

حجم: Mb 1.8

فهرست کتاب را می توانید از اینجا دانلود کنید.

 

  جهت دریافت اطلاعات نحوه خرید این کتاب با m.rahimi.m@gmail.com تماس بگیرید.


 
 
مدلسازی مسائل مدیریت پروژه
نویسنده : محسن رحیمی - ساعت ٧:٤٦ ‎ب.ظ روز ۱۳٩٠/۸/٧
 

منظور از پروژه، مجموعه ای از وقایع و فعالیت های تعریف شده با آغاز و پایان مشخص است که به منظور دستیابی به یک هدف معین توسط انسان برنامه ریزی و هدایت می شود به گونه ای که عواملی مانند زمان انجام پروژه، هزینه ها، منابع و کیفیت آن رضایت بخش باشد. اغلب می توان فعالیت های مربوط به یک پروژه را به آسانی توسط یک جریان شبکه ای، به صورت ترسیمی مدل نمود.

برای مطالعه متن کامل این مقاله روی گزینه "ادامه مطلب" کلیک کنید.

(1000 کلمه)

مطلب مرتبط بعدی: محدودیت های ترجیح (Precedence Constraints)

مطلب مرتبط قبلی: مدلسازی مسائل جابجایی


 
 
مدلسازی مسائل جابجایی (Transshipment Problem)
نویسنده : محسن رحیمی - ساعت ٧:٢٥ ‎ب.ظ روز ۱۳٩٠/٧/۳٠
 

مسئله جابجایی نوع عمومی تری از مسئله حمل و نقل است که در آن کالاها می توانند در مسیر از مبداء به مقصد، به نقاط میانه و واسطه نیز وارد و از آن خارج شوند. همانطور که در ادامه خواهید دید بسیاری از مسائل جریان شبکه ای را می توان با تغییراتی مختصر به مسئله جابجایی تبدیل و سپس به شیوه حل مربوط به این مسائل آنها را مدلسازی و حل نمود. در حقیقت با درک چگونگی مدلسازی مسائل جابجایی، به راحتی می توان انواع دیگر مسائل شبکه ای را مدلسازی نمود.

برای مطالعه متن کامل مقاله روی گزینه "ادامه مطلب کلیک کنید"

(767 کلمه/1 شکل/1 جدول)

مطلب مرتبط بعدی: مدلسازی مسائل مدیریت پروژه

مطلب مرتبط قبلی:مدلسازی مسائل تخصیص


 
 
مدلسازی مسائل تخصیص
نویسنده : محسن رحیمی - ساعت ٧:٥٠ ‎ب.ظ روز ۱۳٩٠/٧/٢٦
 

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

...

 

برای مطالعه متن کامل این مقاله روی گزینه "ادامه مطلب" کلیک کنید.

(552 کلمه/0 عکس/ 2 جدول)

 مطلب مرتبط بعدی: مدلسازی مسائل جابجایی (Transshipment Problem)

مطلب مرتبط قبلی: مدلسازی مسائل حمل و نقل


 
 
مدلسازی مسائل حمل و نقل
نویسنده : محسن رحیمی - ساعت ۸:۳٧ ‎ب.ظ روز ۱۳٩٠/٧/٩
 

مسئله حمل و نقل، مسئله انتقال کالا از چندین مبداء یا تولید کننده به چندین مقصد یا مصرف کننده با حداقل هزینه است. در این نوع خاص از مسائل برنامه ریزی خطی، کالاها تنها اجازه دارند که مستقیماً از مبداء به مقصد جابجا می شوند و این یعنی در این مسائل اجازه جابجایی کالا بین ایستگاه های مبداء یا بین ایستگاه های مقصد وجود ندارند. در این مسائل اغلب ظرفیت ایستگاه های مبداء که عمدتاً محدود است، تقاضای ایستگاه های مقصد و هزینه انتقال هر واحد کالا از مبداء خاص به مقصدی خاص مشخص هستند. تعریف و خصوصیات ذکر شده در بالا ساختاری خاص و شناخته شده برای مسائل حمل و نقل است و هرگونه تغییری در آن باعث تغییر در فرآیند مدلسازی و ساختار شبکه خواهد شد که در نتیجه برخی از این تغییرات باعث می شوند نتوان این مسائل را در حوزه مسائل حمل و نقل قرارداد.

مثال: نمونه ای از مسئله حمل و نقل

شرکت فولادی دارای دو کارخانه لوله سازی در مکان های P1 و P2 است که ظرفیت تولید آنها به ترتیب 100 و 120 تن لوله (با قطر ثابت) در روز می باشد. این شرکت دارای سه مرکز پخش در مکان های DC2, DC1 و DC3 است. این مراکز پخش به 80، 120 و 60 تن لوله در روز نیازمند هستند که در صورت امکان باید این تقاضا برای آنها برآورده شود. هزینه حمل از هر کارخانه به هر مرکز پخش به صورت دلار برتن در جدول زیر داده شده است:

جدول 1. اطلاعات هزینه حمل و نقل

از / به

1

2

3

4

1

5

 

مسئله را برای حداقل نمودن کل هزینه حمل و نقل مدلسازی نمایید.

مسئله بالا را می توان به کمک شبکه نشان داده شده در شکل زیر بیان نمود:

 

 بردارها مشخص کننده مسیرهای ممکن و جهت جریان کالا می باشند. این مسئله را همچنین می توان به شکل جدول زیر نیز نشان داد:

جدول 2. نمایش جدولی مثال

به

از

ظرفیت عرضه 

100 

120 

ظرفیت تقاضا

80 

120 

60 

220

260

 ردیف های 2 و 3 به منابع عرضه کننده تخصیص یافته اند یعنی هر مبداء با یک ردیف مشخص شده است. ستون های 2، 3 و 4 نیز به مقصد ها تخصیص یافته و هر ایستگاه مقصد با یک ستون نمایش داده شده است. ستون پنجم (سطرهای 2 و 3) ظرفیت هر کارخانه را نشان می دهد و سطر چهارم (ستون های 2، 3 و 4) نیز تقاضای هر مرکز پخش را مشخص کرده است.

در هر سلول هزینه حمل و نقل از مقصد به مبداء آن سلول نوشته شده است. سلول گوشه سمت چپ و پایین جدول تقاضای کل و عرضه کل مسئله را بیان می کند.

تعریف متغیرها:

جدول حمل و نقل با متغیرهای تصمیم در جدول زیر ارائه شده است.

جدول 3. نمایش جدولی مثال همراه با متغیرهای تصمیم

به

از 

ظرفیت عرضه 

1

2

3

100 

4

1

5

120 

ظرفیت تقاضا

80 

120 

60 

220

260 

 تابع هدف:

هدف مسئله حداقل نمودن هزینه کل حمل و نقل است که به راحتی می توان متغیرهای تصمیم را در هزینه حمل و نقل هر واحد مرتبط به آن ضرب کرد و با هم جمع نمود.

محدودیت ها:

در مسئله حمل و نقل تنها محدودیت های مربوط به عرضه و تقاضا مطرح هستند. در کل در مسائل حمل و نقل سه حالت ممکن بین عرضه کل و تقاضای کل وجود دارد.

  • عرضه کل کمتر از تقاضای کل باشد:

در این صورت همه تقاضا بوسیله عرضه موجود برآورده نمی شود. در این صورت محدودیت های عرضه باید دارای علامت مساوی باشند و محدودیت های تقاضا به صورت کوچکتر مساوی نوشته شوند.

  • عرضه کل برابر با تقاضای کل باشد:

در این صورت عرضه و تقاضا برابر است و کل تقاضا برآورده می شود. در این حالت همه محدودیت ها، چه عرضه و چه تقاضا به صورت مساوی نوشته می شوند.

  • عرضه کل بیشتر از تقاضای کل باشد:

در این حالت با مازاد عرضه مواجه هستیم و محدودیت های تقاضا باید به صورت مساوی و محدودیت های عرضه به صورت کوچکتر مساوی نوشته شود.

در مثال حاضر، تقاضای کل (260) بیشتر از عرضه کل (220) است. بنابراین محدودیت های عرضه را با علامت مساوی و محدودیت های تقاضا را به صورت کوچکتر مساوی به صورت زیر می نویسیم.

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

محدودیت های تقاضا: تقاضای کل هر مرکز توزیع باید بزرگتر مساوی مجموع کالای رسیده از همه مبداء ها به آن باشد:

در نتیجه مدل نهایی به صورت زیر نوشته خواهد شد:

در این مدل ضریب هر متغیر در محدودیت ها عدد یک است و هر متغیر دو بار تکرار می شود؛ یک بار در محدودیت های تقاضا و یک بار در محدودیت های عرضه. اگر چه مدل بالا نیز قابلیت حل به صورت مسائل برنامه ریزی خطی را دارد اما ساختار خاص مطرح شده باعث شده است روش های حل موثرتر و ساده تری برای مسائل حمل و نقل کشف و توسعه یافته اند که در بخش تحقیق در عملیات به آنها پرداخته خواهد شد.

مطلب مرتبط بعدی: مدلسازی مسائل تخصیص

مطلب مرتبط قبلی: مدلسازی مسائل چند هدفه


 
 
مدلسازی مسائل چند هدفه
نویسنده : محسن رحیمی - ساعت ٩:۱٤ ‎ب.ظ روز ۱۳٩٠/٧/٤
 

برنامه ریزی آرمانی مدلی را ارائه می دهد که در آن تابع هدف مسئول حداقل نمودن مجموع متغیرهای نامطلوب است. در مطلب مرتبط قبل به کمک برنامه ریزی آرمانی مسئله ای را مدل کردیم که در تابع هدف آن بین سود، سرمایه موجود و در گردش ارتباط برقرار نمودیم. به عبارت دیگر تابع هدف به طور مستقیم به حداکثر نمودن سود، سرمایه موجود و سرمایه در گردش می پردازد. چنین مدل هایی را می توان به شکل مدل های چند هدفه نیز فرموله کرد.

مثال: مسئله چند هدفه ترکیب محصول

مثال ارائه شده در مطلب مرتبط قبلی را به خاطر آورید. مسئله را با در نظر گرفتن تمام اهداف آن به صورت یک مسئله چند هدفه مدلسازی می کنیم. هدف مدلساز این است که تا حد ممکن سود، سرمایه موجود و سرمایه در گردش را افزایش دهد. به جای محدودیت های آرمانی، سه تابع هدف را به شکل زیر خواهیم نوشت:

در نتیجه مدل نهایی عبارت خواهد بود از:

مطلب مرتبط بعدی: مدلسازی مسائل حمل و نقل

مطلب مرتبط قبلی: مدلسازی مسئله ای بدون فضای جواب شدنی با برنامه ریزی آرمانی


 
 
مدلسازی مسئله ای بدون فضای جواب شدنی با برنامه ریزی آرمانی
نویسنده : محسن رحیمی - ساعت ٩:۳٤ ‎ب.ظ روز ۱۳٩٠/٦/۳٠
 

به دلایل بسیاری مانند مدلسازی نادرست، اطلاعات غلط و یا محدودیت های متناقض و نشدنی، مدل برنامه ریزی ریاضی می تواند به حلی غیر قابل قبول منجر شود. به کمک کنترل مجدد و خط به خط مدل در بسیاری از موارد می توان مدل را اصلاح کرد و از حالت نشدنی خارج نمود. با این حال اگر در مسئله محدودیت های نشدنی وجود داشته باشند نمی توان به راه حل موجه ای رسید و در بسیاری از مسائل با تعداد محدودیت های بسیار زیاد یافتن آنها کاری مشکل و وقت گیر است. مشکل حل غیر قابل قبول و نشدنی را در ادامه با مثالی بهتر نشان می دهیم و راه حلی برای گذر از این مشکل ارائه خواهیم کرد:

مثال: مسئله ترکیب محصول

مدل برنامه ریزی خطی زیر را که در آن هدف حداکثر نمودن سود حاصل از تولید چهار محصول است در نظر بگیرید. این مدل دارای دو محدودیت مربوط به سرمایه در دسترس و سرمایه در گردش و سه محدودیت فنی طبق زیر است:

متغیرهای تصمیم:

میزان تولید از محصول iام

 

تابع هدف:

حل بهینه مدل بالا به شرح زیر است:

 

بعد از نوشتن این مدل مشخص شد که سرمایه لازم برای تولید باید از 67000 دلار به 72000 دلار افزایش یابد. این تغییر باعث می شود که مدل از حالت شدنی خارج شده و دارای فضای موجه نباشد. کاملاً واضح است که از بین رفتن منطقه موجه ناشی از تغییر در محدودیت مربوط به سرمایه موجود است. بنابراین راهکار LP بیش از این به کار این مسئله نمی آید. به جای کم کردن RHS مربوط به محدودیت سرمایه موجود برای رسیدن به منطقه موجه، راهکار دیگری لازم است که بتواند برنامه تولید را با برنامه مالی سازمان هماهنگ سازد. در چنین مواردی، برنامه ریزی آرمانی (GP) می تواند راهکاری مناسب برای یافتن جواب قابل قبول باشد.

مدلسازی برنامه ریزی آرمانی:

محدودیت های فنی را بدون تغییر در مدل وارد می کنیم. بنابراین شبیه به معادلات مدل LP آنها را در GP وارد می کنیم.

محدودیت های آرمانی (محدودیت های منعطف):

سرمایه موجود :

فرض کنید سرمایه مهمترین و ارجح ترین آرمان باشد.

تبدیل خواهد شد به:

d1+ و d1- نیز عبارتند از فاکتور های سطح دستیابی کمتر و بیشتر (متغیرهای انحراف) به سرمایه موجود.

دیگر محدودیت های آرمانی به ترتیب اهمیت عبارتند از:

سرمایه در گردش

که تبدیل خواهد شد به :

d2+ و d2- نیز عبارتند از فاکتورهای سطح دستیابی کمتر و بیشتر به سرمایه در گردش مورد نظر.

تابع هدف سود در مدل LP

d3+ و d3-نیز عبارتند از فاکتورهای سطح دستیابی کمتر و بیشتر به آرمان سود که آرمان سود را در اینجا عدد 23000 دلار در نظر می گیریم زیرا مشخصا بیش تر از حل بهینه حاصل از LP است.

تابع هدف برنامه ریزی آرمانی:

هدف عبارت است از حداقل نمودن مجموع متغیرهای انحراف نامطلوب همراه با وزن مربوط به هر یک از آنها:

در این مسئله، متغیرهای انحراف نامطلوب، d1-و d2- و d3- هستند. به همین ترتیب w2, w1 و w3 نیز وزن آرمان های اول، دوم و سوم بوده که رابطه w3<w2<w1 بین آنها برقرار است. مدل برنامه ریزی آرمانی نهایی عبارت است از:

مطلب مرتبط بعدی: مدلسازی مسائل چند هدفه

مطلب مرتبط قبلی: تکنیک های ساده مدلسازی: مدلسازی مسائل چند مرحله ای


 
 
تکنیک های ساده مدلسازی: مدلسازی مسائل چند مرحله ای
نویسنده : محسن رحیمی - ساعت ۸:٢٠ ‎ب.ظ روز ۱۳٩٠/٦/٢٤
 

پاره ای از مسائل برنامه ریزی شامل چند مرحله می باشند. در اکثر برنامه ریزی های چند مرحله ای، تعدادی دوره زمانی در آینده در نظر گرفته می شود. در چنین مواردی به کمک مدل های ریاضی فرایند برنامه ریزی برای یک دوره زمانی خاص حل می شود و سپس این فرآیندهای برنامه ریزی از یک دوره زمانی به دوره بعدی ارتباط داده می شوند. در مواردی که پارامترهای یک مدل مانند تقاضا، سطح تولید، قیمت و دیگر فاکتورهای مشابه از دوره ای به دوره دیگر تغییر کنند و نوسان داشته باشند، مدلسازی مرحله ای راهکاری بسیار مفید و موثر خواهد بود.

مسئله برنامه ریزی تولید چند مرحله ای

شرکت NSPL تولیدکننده شیر کنترل می باشد. فرآیند تولید از نوع سفارشی بوده به این معنی که تعداد تولید شرکت بر اساس سفارش مشتریان تعیین می شود. مشتریان سفارش خود را به طور هفتگی به مدیر فروش اعلام می کنند و تقاضای هفتگی آنها نیز ثابت نمی باشد. با این حال ظرفیت تولید شرکت محدود و حداکثر 1000 شیر در هفته است. تقاضای کل مشتریان در چهار هفته آینده به قرار جدول زیر است:

جدول 1. اطلاعات مسئله برنامه ریزی تولید چند مرحله ای

هفته

تقاضا 

800 

700 

1200 

1100 

 هزینه تولید هر شیر کنترل 50 دلار است. شرکت قابلیت تولید بیشتر از تقاضای هفتگی را نیز دارد به طوریکه می تواند بیش تر از تقاضای هفتگی تولید و به منظور فروش در هفته های آینده انبار کند. هزینه ذخیره سازی، جابجایی و بیمه هر واحد که به طور کلی به آن هزینه انبارداری خواهیم گفت 5 دلار است. هزینه راه اندازی نیز ناچیز فرض شده است. برنامه تولید این شرکت را به گونه ای مدلسازی نمایید که حداقل هزینه ممکن برای شرکت ایجاد شود و تقاضای مشتریان نیز برآورده شود.

فرضیات:

  • محصولات یا تحویل مشتری می شوند و یا در پایان هفته به انبار فرستاده می شوند.
  • در شروع تولید هیچ محصولی در انبار وجود ندارد و ذخیره پایانی برنامه ریزی نیز باید صفر باشد.

متغیرهای تصمیم:

تعداد واحد های تولید شده در هفته iام

تعداد واحد های انبار شده در پایان هفته iام

تابع هدف:

هدف حداقل نمودن هزینه های تولید به همراه هزینه های ذخیره سازی است.

محدودیت ها:

ظرفیت تولید

در هر هفته، میزان تولید نباید از ظرفیت تولید کارخانه بیشتر باشد.

برآورده نمودن تقاضا

میزان تولید شده در هر هفته به اضافه تعداد محصولات ذخیره شده در انبار از هفته های قبل باید برابر باشد با تقاضای هفته جاری به اضافه تعداد محصولاتی که برای استفاده در هفته های آینده به انبار فرستاده می شوند.

و یا

و همچنین

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

مطلب مرتبط بعدی: مدلسازی مسئله ای بدون فضای جواب شدنی با برنامه ریزی آرمانی

مطلب مرتبط قبلی: تکنیک های ساده مدلسازی: توابع maxi-min و mini-max


 
 
تکنیک های ساده مدلسازی: توابع هدف Maxi-Min یا Mini-Max
نویسنده : محسن رحیمی - ساعت ٧:٠٧ ‎ب.ظ روز ۱۳٩٠/٦/۱٩
 

در مواردی لازم است حداکثر (حداقل) دو یا چند متغیر یا تابع محدودیت را حداقل (حداکثر) نماییم. برای توضیح اینکه برای مدلسازی این موارد چگونه می توان عمل کرد به مثال زیر توجه کنید:

مسئله برنامه ریزی تولید

مسئله آورده شده در مطلب مرتبط قبلی را با تابع هدف جدیدی در نظر می گیریم. فرض کنید از شما خواسته شده است که این مسئله را به گونه ای مدلسازی کنید که ساعت کاری هر دستگاه مشخص گردد و هدف آن نیز حداکثر نمودن تعداد محصول نهایی مونتاژ شده از دو قطعه P1 و P2 در طول یک روز کاری 8 ساعته باشد.

واضح است که تعداد محصول نهایی مونتاژ شده نمی تواند از حداقل تعداد قطعات P1 و P2 تولید شده فراتر رود. بنابراین تابع هدف، حداکثر نمودن حداقل x1 و x2 خواهد بود:

این تابع یک تابع غیر خطی است. برای تبدیل آن به ساختار خطی می توان به شکل زیر عمل نمود:

متغیری با نام y را در نظر بگیرید که تعداد محصولات نهایی مونتاژ شده را نشان می دهد.

برای y می توان نوشت:

و یا

و یا

 و هدف عبارت است از:

بنابراین مدل LP اصلاح شده به صورت زیر خواهد بود:

مطلب مرتبط بعدی: تکنیک های ساده مدلسازی: مدلسازی مسائل چندمرحله ای

مطلب مرتبط قبلی: تکنیک های ساده مدلسازی: وجود قدر مطلق در محدودیت ها


 
 
تکنیک های ساده مدلسازی: وجود قدرمطلق در محدودیت ها
نویسنده : محسن رحیمی - ساعت ۱٠:۱۱ ‎ب.ظ روز ۱۳٩٠/٦/۱٢
 

در برخی مسائل شرایط و محدودیت هایی وجود دارد که تبدیل آنها به تابع ریاضی تنها به صورت تابع قدرمطلقی ممکن است. از آنجا که وجود قدر مطلق در مدل نهایی مسئله منجر به غیر خطی بودن مدل می شود لذا بهتر است با انجام عملیات مناسب، تابع را به چند تابع خطی تبدیل نمود. یکی از این راه ها تعریف متغیر جدید و وارد کردن آن به مسئله است. برای آشنایی با این روش به مثال زیر توجه کنید.

مسئله برنامه ریزی تولید

تولید کننده ای دارای یک ماشین مته کاری و پنج ماشین آسیاب می باشد که از آنها جهت تولید محصول نهایی خود که از دو قطعه P1 و P2 تشکیل شده است استفاده می کند. زمان لازم برای تولید قطعات مذکور توسط دو دستگاه مختلف و همچنین سودآوری هر قطعه در جدول زیر ارائه شده است:

جدول 1. اطلاعات مسئله برنامه ریزی تولید

قطعه 

سود

(دلار برای هر قطعه)

زمان تولید (دقیقه بر قطعه 

مته کاری 

آسیاب 

4

3

20

5

5

15

 

درخواست شده است که بار روی دستگاه ها متوازن گردد به این صورت که زمان استفاده از هیچ دستگاهی در روز بیش از 30 دقیقه طولانی تر از زمان استفاده از دستگاه دیگری نگردد. بار تولیدی بخش آسیاب باید بر هر پنج دستگاه تقسیم شود. مدل مربوط به این مسئله را به گونه ای بنویسید که در نهایت ساعت کاری هر دستگاه مشخص گردد و در عین حال سود حاصل از یک روز کاری 8 ساعته را حداکثر نماید.

متغیرهای تصمیم:

تعداد تولید شده از قطعه iام در روز (i=1 برای P1 و i=2 برای P2)

 تابع هدف:

هدف حداکثر نمودن سود است.

محدودیت ها:

  • محدودیت های بارگذاری:

بار وارد بر دستگاه آسیاب (به دقیقه)

بار وارد بر دستگاه مته کاری (به دقیقه)

 بنابراین محدودیت زمان استفاده از هر دستگاه آسیاب به صورت زیر است:

به همین ترتیب برای دستگاه مته کاری داریم:

  • محدودیت توازن بار ماشین ها:

طبق توضیحات مسئله شرط لازم برای متوازن ساختن بار تولیدی دستگاه ها را می توان به شکل زیر نوشت:

یا

محدودیت بالا یک محدودیت غیر خطی است. مفهوم این محدودیت آن است که اگر

باشد آنگاه عبارت

مقداری مثبت خواهد شد که باید کوچکتر یا مساوی مقدار 30 باشد و اگر

باشد آنگاه عبارت

مقداری مثبت خواهد گرفت و این عبارت باید کمتر یا مساوی با عدد 30 قرار گیرد. این محدودیت غیر خطی را می توان با محدودیت های خطی زیر جایگزین نمود:

که x3 نشان دهنده اختلاف مثبت دو عبارت x1 و 2x2 است.

بنابراین مدل LP این مسئله به صورت زیر خواهد بود:

مطلب مرتبط بعدی: تکنیک های ساده مدلسازی: توابع هدف Maxi-Min یا  Mini-Max

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


 
 
تکنیک های ساده مدلسازی: وجود نسبت های مشخص بین محدودیت ها
نویسنده : محسن رحیمی - ساعت ٩:۳٥ ‎ب.ظ روز ۱۳٩٠/٦/٧
 

در دو مطلب مرتبط قبل عنوان کردیم که در برخی از مسائل روابطی بین یک متغیر با متغیر دیگر و یا با گروهی از متغیرها وجود دارد. همین حالت ممکن است در مورد توابع محدودیت نیز اتفاق بیفتد. برای نمونه زمانی که باید بین میزان کار یا بار تولیدی بخش های مختلف یک سازمان تعادل برقرار باشد این حالت پیش می آید. به مثال زیر توجه نمایید.

مثال: مسئله ترکیب محصول

شرکت NQAI که در زمینه کشاورزی مشغول است دارای سه زمین کشاورزی می باشد که از لحاظ شرایط آب و هوایی و نوع خاک مشابه یکدیگرند. هر مزرعه دارای مساحت مشخص و محدود و همچنین میزان آب مشخصی برای آبیاری است. اطلاعات مربوط به مساحت و میزان آب موجود برای هر مزرعه در جدول زیر داده شده است:

جدول 1. اطلاعات مسئله ترکیب محصول

شماره مزرعه 

مساحت (هکتار) 

میزان آب 

1

500

1600

2

600

2000

3

400

1000

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

جدول 2. اطلاعات تکمیلی مسئله ترکیب محصول

نوع محصول 

حداکثر مساحت ممکن 

میزان آب مورد نیاز
(برای هر هکتار)

سود حاصل از کشت
(دلار به ازای هر هکتار)

A

600

5

450

B

700

4

350

300

3

150

 به منظور متعادل ساختن بار تولید در بین مزارع، سیاست شرکت این است که مزرعه ها از لحاظ درصد زمین زیر کشت با هم برابر باشند. با این حال هر مزرعه در انتخاب هر ترکیبی از کشت سه محصول آزاد است. شرکت در پی یافتن پاسخ به این سوال است که چه مساحتی از کدام مزرعه را به چه محصولی اختصاص دهد تا سود کل حداکثر گردد. مدل برنامه ریزی خطی این مثال را بنویسید.

متغیرهای تصمیم:

اگر مزارع سه گانه را با شماره های 2،1 و 3 و محصولات را با نام های B, A و C بشناسیم خواهیم داشت:

تعداد هکتار از مزرعه iام که به محصول jام اختصاص یافته است xij=

تابع هدف:

کل مساحت تخصیص داده شده به محصول A در سه مزرعه

کل مساحت تخصیص داده شده به محصول B در سه مزرعه

کل مساحت تخصیص داده شده به محصول C در سه مزرعه

 هدف حداکثر نمودن سود کل است:

محدودیت ها:

محدودیت آب:

مزرعه شماره 1:

مزرعه شماره 2:

مزرعه شماره 3:

 

محدودیت زمین بدلیل مساحت محدود مزارع:

مزرعه شماره 1:

مزرعه شماره 2:

مزرعه شماره 3:

 محدودیت زمین برای محصولات بدلیل کمبود تجهیزات و نیروی انسانی:

محصول A

محصول B

محصول C

 محدودیت برابر بودن درصد زمین زیر کشت همه مزارع:

یا

و

که می توان به صورت زیر بازنویسی نمود:

بنابراین مدل نهایی به صورت زیر خواهد بود:

مطلب مرتبط بعدی: تکنیک های ساده مدلسازی: وجود قدرمطلق در محدودیت ها

مطلب مرتبط قبلی: تکنیک های ساده مدلسازی: وجود نسبت های مشخص بین متغیرها


 
 
تکنیک های ساده مدلسازی: وجود نسبت های مشخص بین متغیرها
نویسنده : محسن رحیمی - ساعت ۱۱:٠٥ ‎ب.ظ روز ۱۳٩٠/٦/٤
 

در مثال مطلب مرتبط قبل سه محدودیت وجود داشتند که بیانگر روابطی بودند که در آنها یک متغیر باید کوچکتر مساوی (یا بزرگتر مساوی) با n برابر متغیری دیگر باشد در حالی که n>0 است. در بسیاری از مسائل با حالتی روبرو می شویم که نسبت های خاصی باید بین متغیرهایی مانند میزان تولید رعایت شود. برای مثال بنا بر دلایلی مثل دستورالعمل مونتاژ، سه محصول A، B و C باید به نسبت 2:3:4 تولید شوند. برای مدلسازی مسائلی مانند این از تکنیک های ساده ای استفاده می شود که در ادامه نمونه ای از آن آورده شده است:

مسئله ترکیب محصول

شرکتی سه کالای P2,P1 و P3 را تولید و به فروش می رساند. زمان لازم برای تولید یک واحد P1، دو برابر زمان لازم برای تولید یک واحد P2 و سه برابر زمان لازم برای تولید یک واحد P3 است. محصولات باید طبق نسبت 3:4:5(P1:P2:P3) تولید شوند. ماده اولیه مورد نیاز برای هر محصول و همچنین کل ماده اولیه موجود در جدول زیر داده شده است. اگر همه نیروی کار تنها برای تولید کالای P1 مورد استفاده قرار گیرند، به علت محدودیت زمان تنها 1600 واحد از P1 تولید می شود. تقاضا برای P2,P1 و P3 به ترتیب 185، 250 و 200 واحد است که باید برآورده شود و سود حاصل از فروش هر واحد نیز به ترتیب 50$، 40$ و 70$ است. معین کنید چه مقدار از P2,P1 و P3باید تولید شود تا سود شرکت حداکثر گردد؟

 

جدول 1. اطلاعات مربوط به ماده اولیه در مسئله ترکیب محصول

ماده اولیه 

میزان مورد نیاز برای هر واحد از محصول (کیلوگرم) 

کل موجودی (کیلوگرم) 

6

4

6

5000

3

7

6

6000

 

تعریف متغیرها:

x2, x1 و x3 به ترتیب میزان تولید از محصول های P2,P1 و P3را نشان می دهند.

تابع هدف:

هدف مسئله حداکثر نمودن سود است.

محدودیت ها:

محدودیت مواد اولیه:

ماده اولیه R1

ماده اولیه R2

 

محدودیت ظرفیت: از آنجا که محصول P2 به 1/2 و محصول P3 به 1/3 زمان لازم برای تولید P1 نیاز دارند، محدودیت تعداد واحدهای تولیدی با توجه به زمان را می توان به صورت زیر نوشت:

فرض کنید تولید هر واحد از محصول P1 به زمانی معادل t نیاز داشته باشد. بنابراین داریم:

که می توان آن را به شکل زیر بازنویسی کرد:

محدودیت تقاضای بازار:

:تقاضای محصول

:تقاضای محصول

:تقاضای محصول

 

محدودیت نسبت تولید: از آنجائیکه باید برای تولید محصولات باید نسبت 3:4:5(P1:P2:P3) رعایت شود می توان نوشت x1:x2:x3=3:4:5 و یا:

و یا:

 

و یا:

بنابراین محدودیت های مربوط به نسبت ها به صورت زیر خواهند بود:

بنابراین مدل برنامه ریزی خطی نهایی عبارت است از:

 

 

 

 

 

 

 

 

 

 

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

مطلب مرتبط قبلی: تکنیک های ساده مدلسازی: تعریف متغیر به صورت کسری از متغیر دیگر


 
 
تکنیک های ساده مدلسازی: تعریف متغیر به صورت کسری از متغیر دیگر
نویسنده : محسن رحیمی - ساعت ٩:٢۸ ‎ب.ظ روز ۱۳٩٠/٦/۱
 

حالت تعریف متغیر به صورت کسری از متغیر دیگر

در برخی مسائل، شرایط خاصی عنوان می شود که در آن ارزش یک یا چند متغیر بر حسب ارزش یک یا چند متغیر دیگر و به صورت کسری یا درصد بیان می شود. در این مطلب مسئله ای را ارائه می کنیم که دارای چنین شرایطی است:

مسئله مدیریت مالی

شرکت اعتباری ABC قصد دارد، پنج وام مختلف به افراد واجد شرایط ارائه دهد. عنوان این وام ها و همچنین نرخ سود سالیانه هر کدام که باید توسط وام گیرنده علاوه بر مبلغ وام به شرکت بازگردانده شود در جدول زیر آورده شده است:

جدول 1. اطلاعات مسئله مدیریت مالی

شماره وام 

عنوان وام 

بهره سالیانه (%)

1

وام تجاری / صنعتی 

9

2

وام تعمیر خانه 

8

3

وام خرید خانه 

6.5

4

وام ساخت خانه 

7.5

5

وام شخصی 

10

 شرکت اعتباری مذکور برای ارائه این وام ها مبلغ 50 میلیون دلار در نظر گرفته است. هدف شرکت کسب حداکثر سود در واگذاری این وام ها است. این شرکت در ارائه وام سیاست های زیر را دنبال می کند:

  • میزان وام تعمیر خانه نباید بیشتر از 25% میزان وام خرید خانه گردد.
  • وام تجاری / صنعتی باید کمتر یا برابر با وام ساخت خانه باشد.
  • حداقل 70% از کل وام های ارائه شده باید برای وام خرید یا ساخت خانه در نظر گرفته شود.
  • به دلایل فنی به ازای هر دلار وامی که برای ساخت خانه پرداخت می گردد باید حداقل سه دلار برای خرید خانه پرداخت گردد.

تعریف متغیرها:

مبلغی که به عنوان وام شماره i ام در نظر گرفته می شود xi:

تابع هدف:

محدودیت ها:

  • کل پول موجود برای پرداخت وام 50 میلیون دلار است.

  • میزان وام تعمیر خانه نباید بیشتر از 25% میزان وام خرید خانه گردد.

  • وام تجاری/ صنعتی باید کمتر یا برابر با وام ساخت خانه باشد.

  • حداقل 70% از کل وام های ارائه شده باید برای وام خرید یا ساخت خانه در نظر گرفته شود.

  • به دلایل فنی به ازای هر دلار وامی که برای ساخت خانه پرداخت می گردد باید حداقل سه دلار برای خرید خانه پرداخت گردد.

  • محدودیت های غیر منفی

پس از مشخص شدن روابط بین متغیرها، برای نوشتن مدل نهایی باید متغیرها را سمت چپ محدودیت قرار داد که در این صورت مدل نهایی به شکل زیر نوشته خواهد شد:

مطلب مرتبط بعدی: تکنیک های ساده مدلسازی: وجود نسبت های مشخص بین متغیرها

مطلب مرتبط قبلی: تکنیک های ساده مدلسازی:استفاده از عملیات کمکی


 
 
تکنیک های ساده مدلسازی: استفاده از عملیات کمکی
نویسنده : محسن رحیمی - ساعت ۱۱:٤٥ ‎ب.ظ روز ۱۳٩٠/٥/۳٠
 

شاید با در نظر گرفتن مطالب ارائه شده در بخش مدلسازی اینگونه به نظر برسد که تعریف متغیرها و نوشتن توابع محدودیت و هدف مسائل بهینه سازی، کاری بسیار ساده و آسان است. این امر برای مسائل کوچکی که اطلاعات کافی در رابطه با آنها به مدلساز داده شود صحیح است اما در دنیای واقعی معمولاً این اتفاق نمی افتد. در برخی از مسائل بسته به نوع مسئله لازم است برای تعریف متغیرها و نوشتن توابع هدف و محدودیت از عملیات های کمکی استفاده شود. در بسیاری از موارد، در عین سادگی باید از لم های خاصی برای نوشتن مدل استفاده نمود. در ادامه سعی شده است مفهوم عبارات «عملیات کمکی» و «لم های ویژه» را که در موارد بسیاری به کار می آیند، با مثال هایی روشن شوند.

مثال

یک تولیدکننده پارچه سه سفارش زیر را برای رول های پارچه با اطلاعات زیر دریافت کرده است:

جدول 1 اطلاعات مسئله ضایعات پارچه

شماره سفارش 

عرض (متر) 

طول (تعداد رول) 

1

2.5

30

2

3.8

50

3

4.9

10

 

رول ها در دو عرض استاندارد 5 و 10 متر تولید می شوند. سپس با توجه به اطلاعات سفارش دریافتی می توان رول ها را برید و عرض خواسته شده را بدست آورد. هیچ محدودیتی در طول رول ها وجود ندارد و حتی می توان آنها را پیوسته و با طول بینهایت در نظر گرفت. برنامه ای از تولید را مشخص نمایید که ضایعات پارچه در آن حداقل گردد.

این مسئله در عین حالی که ساده به نظر می رسد اما کمی سخت تر از مسائلی است که تاکنون در این وبلاگ به مدلسازی آنها پرداخته شده است. برای مدلسازی این مسئله باید کمی بیشتر و بهتر فکر کرد تا عملیات کمکی مناسب برای تعریف متغیرها و نوشتن توابع هدف و محدودیت ها را به شناسایی کرد.

تعریف متغیرها: متغیرها را می توان به کمک اندیس i که می تواند طیفی از اعداد را شامل شود به صورت زیر معرفی نمود:

 

تعداد رول های تولید شده از یک رول استاندارد پنج متری به شیوه برش iام

تعداد رول های تولید شده از یک رول استاندارد 10 متری به شیوه برش iام

 

برای تولید رول هایی به عرض 3.8, 2.5 و 4.9 متری از یک رول 5 متری می توان از سه شیوه برش و برای تولید از یک رول 10 متری می توان از شش شیوه برش استفاده نمود. برای درک بهتر این موضوع متغیرها در زیر به طور کامل تعریف شده اند.

از یک رول پنج متری می توان به سه زیر برای تولید سفارش های رسیده استفاده نمود:

 

تبدیل رول پنج متری به دو رول 2.5 متری بدون ضایعات

تبدیل رول پنج متری به یک رول 3.8 متری با 1.2 متر ضایعات

تبدیل رول پنج متری به یک رول 4.9 متری با 0.1 متر ضایعات

 

و برای رول 10 متری نیز شش متغیر زیر را داریم:

 

تبدیل رول 10 متری به چهار رول 2.5 متری بدون ضایعات

تبدیل رول 10 متری به دو رول 2.5 و یک رول 3.8 متری با 1.2 متر ضایعات

تبدیل رول 10 متری به دو رول 2.5 و یک رول 4.9 متری با0.1 متر ضایعات

تبدیل رول 10 متری به دو رول 3.8 متری با 2.4 متر ضایعات

تبدیل رول 10 متری به یک رول 3.8 و یک رول 4.9 متری با 1.3 متر ضایعات

تبدیل رول 10 متری به دو رول 4.9 متری با 0.2 متر ضایعات

 

بنابراین 9 متغیر برای مدلسازی این مسئله تعریف کردیم. شیوه های ترکیب برش مختلف به همراه ضایعات حاصل از به کارگیری آنها در جدول زیر خلاصه شده است:

 

جدول 2. نتایج حاصل از شیوه های مختلف برش مربوط به مسئله ضایعات پارچه

عرض مورد تقاضا 

متغیرهای تصمیم 

تعداد رول مورد نیاز 

2.5

2

0

0

4

2

2

0

0

0

30

3.8

0

1

0

0

1

0

2

1

0

50

4.9

0

0

1

0

0

1

0

1

2

10

ضایعات 

0

1.2

0.1

0

1.2

0.1

2.4

1.3

0.2

 

 

تابع هدف: هدف طرح این مسئله حداقل نمودن ضایعات کل می باشد. سطر آخر جدول بالا نشان دهنده میزان ضایعات حاصل از هر متغیر تصمیم است. بنابراین تابع هدف این مسئله را می توان به صورت زیر نوشت:

محدودیت ها:

برای این مسئله سه محدودیت می توان در نظر گرفت که عبارتند از (1) تعداد رول های مورد نیاز 2.5 متری (2) تعداد رول های مورد نیاز 3.8 متری (3) تعداد رول های مورد نیاز 4.9 متری. تعداد رول های 2.5 متری که توسط هر متغیر تصمیم می توان تولید کرد در سطر اول جدول بالا قابل مشاهده است. به همین ترتیب سطرهای دوم و سوم نیز مربوط به رولهای با عرض 3.8 و 4.9 متر می باشد. بنابراین به کمک اطلاعات جدول بالا تعداد رول های مربوط به هر سفارش را می توان به صورت زیر محاسبه نمود:

 

تعداد رول های 2.5 متری تولید شده

تعداد رول های 3.8 متری تولید شده

تعداد رول های 4.9 متری تولید شده

 

و مدل برنامه ریزی خطی مسئله به صورت زیر خواهد بود:

پس از حل کردن این مدل به راحتی می توان تعداد رول های مورد نیاز 5 متری و 10 متری بهینه برای پاسخگویی به هر سه سفارش که کمترین ضایعات را به همراه داشته باشد به صورت زیر بدست آورد.

تعداد رول های 5 متری مورد نیاز

تعداد رول های 10 متری مورد نیاز 

 

همانطور که در حل این مسئله مشاهده شد، تعریف متغیرها احتیاج به نوعی خلاقیت داشت که همان عملیات کمکی مورد نیاز برای حل این مسئله است.

مطلب مرتبط بعدی: تکنیک های ساده مدلسازی: تعریف متغیر به صورت کسری از متغیر دیگر

مطلب مرتبط قبلی:تکنیک های ساده مدلسازی: استفاده از زیرنویس ها


 
 
تکنیک های ساده مدلسازی: استفاده از زیرنویس ها
نویسنده : محسن رحیمی - ساعت ۱۱:٥٥ ‎ب.ظ روز ۱۳٩٠/٥/٢٤
 

برای توضیح چگونگی استفاده از زیرنویس برای متغیرها مطلب مربوط به بودجه بندی سرمایه ای را به یاد آورید. جهت سهولت بررسی، معادلات و مدل مساله در اینجا تکرار شده است:

متغیرها:

 

مدل برنامه ریزی عدد صحیح این مثال به صورت زیر است:

به جای اینکه هر متغیر را به طور مجزا تعریف کنیم می توان همه آنها را با هم و با استفاده از ویژگی های اندیس به صورت زیر نوشت:

 

عبارت «برای همه i ها» در اینجا به معنی i = 1,2,3,4,5 است و معمولاً به جای نوشتن «برای همه»(for all) از نماد استفاده می شود. بنابراین تابع تعریف متغیرها را به صورت زیر نیز می توان نوشت

 بنابراین مدل برنامه ریزی عدد صحیح این مسئله به صورت زیر نوشته می شود:

این مدل را می توان با استفاده از علامت سیگما که در مطالب اینده به آن اشاره خواهد شد خلاصه تر نیز نمود.

مطلب مرتبط بعدی:تکنیک های ساده مدلسازی: استفاده از زیرنویس ها

مطلب مرتبط قبلی: مدلسازی مسائل برنامه ریزی غیرخطی


 
 
مدلسازی مسائل برنامه ریزی غیرخطی
نویسنده : محسن رحیمی - ساعت ٩:٤٧ ‎ب.ظ روز ۱۳٩٠/٥/٢۳
 

مدل برنامه ریزی غیر خطی بسیار شبیه به مدل برنامه ریزی خطی است با این تفاوت که در آن عباراتی غیر خطی (چه در تابع هدف و چه در محدودیت ها) دیده می شود. اگر حتی یکی از عبارات مدل، غیر خطی باشد نیز آن مدل را غیر خطی می نامند.

مثال: مکان یابی

یک شبکه رادویویی که در شهرهای جنوبی استرالیا برنامه پخش می کند قصد دارد تا خدمات و برنامه های خود را به 4 شهر شمالی و غربی نیز گسترش دهد. برای ارائه خدمات مناسب، این شبکه احتیاج به یک برج رادیویی انتقال دهنده دارد که امواج رادیویی را به برج های کوچکتر گیرنده ای که در این چهار شهر وجود دارند برساند. برج رادیویی جدیدی که در نظر گرفته شده است قادر است امواج را تا شعاع k کیلوکتری به خوبی ارسال نماید. بنابراین لازم است محل نصب این برج با هر یک از شهرها حداکثر k کیلومتر فاصله داشته باشد. هدف از مدلسازی این مسئله یافتن محلی است که کمترین فاصله جمعی ممکن را از این 4 شهر داشته باشد.

موقعیت این چهار شهر به صورت مختصات دو بعدی در جدول زیر ارائه شده است:

جدول 1. اطلاعات مسئله مکان یابی

شهر x y
1 10 45
2 15 25
3 20 10
4 55 20

مرحله اول: تعریف متغیرها

هدف یافتن مختصات نقطه نصب برج جدید است. بنابراین متغیرهای تصمیم را می توان به صورت زیر تعریف کرد.

فاصله محل نصب برج تا محور y ها (مولفه اول مختصات نقطه نصب) = x

فاصله محل نصب برج تا محور y ها (مولفه اول مختصات نقطه نصب) = y

مرحله دوم: تعیین تابع هدف

هدف حداقل نمودن فاصله نقطه نصب برج جدید از چهار شهر مورد نظر است. بنابراین می توان نوشت:

اولین عبارت سمت راست تابع هدف فاصله برج از محل شهر اول است و سه عبارت دیگر نیز فاصله برج را به ترتیب از شهر های دو، سه و چهار نشان می دهند.

مرحله سوم: محدودیت ها

برج جدید باید در محلی نصب شود که فاصله آن نقطه تا هر یک از شهرها حداکثر k کیلومتر باشد. بنابراین

بنابراین مدل ریاضی نهایی به شکل زیر خواهد بود:

دقت کنید که تابع هدف و تمام محدودیت ها غیر خطی هستند و k نیز باید مشخص باشد.

مطلب مرتبط بعدی: تکنیک های ساده مدلسازی: استفاده از زیرنویس ها

مطلب مرتبط قبلی: مدلسازی برنامه ریزی آرمانی


 
 
مدلسازی برنامه ریزی آرمانی
نویسنده : محسن رحیمی - ساعت ٩:٢٠ ‎ب.ظ روز ۱۳٩٠/٥/٢٢
 

در مدلسازی ریاضی بین دو عبارت «هدف» و «آرمان» باید تفاوت قائل شد. هدف به شکل یک تابع ارائه می شود که باید حداکثر یا حداقل گردد. به عنوان مثال، رابطه زیر بیانگر یک تابع هدف می باشد.

اما آرمان بیانگر مقداری دلخواه برای مقدار یک تابع است. اگر برای نمونه آرمان ما در سود 2500 دلار باشد به این معناست که باید تا می توانیم سعی کنیم با در نظر گرفتن محدودیت ها مقدار

را به عدد 2500 نزدیک کنیم. در برنامه ریزی آرمانی، هر آرمان با استفاده از یک محدودیت آرمانی ارائه می گردد و در نتیجه می توان در یک مدل چندین آرمان گوناگون را در نظر گرفت. بر خلاف محدودیت های مسائل برنامه ریزی خطی و برنامه ریزی عدد صحیح، در محدودیت های آرمانی امکان کمی تخلف از سوی تصمیم گیرنده وجود دارد. به همین علت، محدودیت های آرمانی را از نوع محدودیت های نرم می دانند.

مثال مطلب قبل را در نظر بگیرید. فرض کنید که این شرکت در بخشی از بودجه سالانه خود مقدار TPC دلار را به عنوان هزینه های تولید خود در نظر گرفته است و همچنین به عنوان یک آرمان در نظر دارد که حداقل از 75% از مجموع ساعات کار عادی نیروی انسانی خود استفاده کند. اگر چه این شرکت انتظار دارد که به آرمان های در نظر گرفته خود برسد اما بنا به شرایط خاص انحراف از این آرمان ها غیر ممکن نیست.

مسئله بالا را می توان به شکل مدل برنامه ریزی آرمانی فرمول بندی کرد. برنامه ریزی آرمانی می تواند خطی، عدد صحیح یا غیر خطی باشد. برای سادگی و درک بهتر، در این بخش برنامه ریزی آرمانی خطی را ارائه می دهیم. اجزای هر مسئله برنامه ریزی آرمانی عبارتند از:

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

در برنامه ریزی آرمانی برای هر محدودیت آرمانی مقداری عددی و معین به عنوان آرمان در نظر گرفته می شود. سپس مسئله به گونه ای مدلسازی می شود که مجموع انحرافات وزنی از این مقادیر با توجه به نوع آرمان حداقل گردد.

در ادبیات بهینه سازی سه نوع آرمان وجود دارد:

  • آرمان یک طرفه پایین: هنگامی که مدلساز نمی خواهد تابع محدودیت از مقدار معینی (آرمان) کمتر شود با این نوع آرمان روبرو هستیم.
  • آرمان یک طرفه بالا: هنگامی که مدلساز نمی خواهد تابع محدودیت از مقدار معینی (آرمان) بیشتر شود با این نوع آرمان روبرو هستیم.
  • آرمان دو طرفه: هنگامی که مدلساز نمی خواهد تابع محدودیت از مقدار معینی (آرمان) نه کمتر و نه بیشتر شود با این نوع آرمان روبرو هستیم.

برای مثال این مطلب، متغیرهای تصمیم (جزء 1) و محدودیت های سیستمی (جزء 3) شبیه به مثال قبل هستند. متغیرهای انحراف (جزء 2) نیز به صورت زیر تعریف می شوند:

برای آرمان هزینه های کل تولید داریم:

متغیر انحرافی اضافی (اگر هزینه های واقعی بیشتر از آرمان مورد نظر گردد) d1+ =

متغیر انحرافی کمبود (اگر هزینه های واقعی کمتر از آرمان مورد نظر گردد) d1- =

برای آرمان ساعات کار عادی

متغیر انحرافی اضافی (اگر ساعات کار عادی بیشتر از آرمان مورد نظر گردد) d2+ =

متغیر انحرافی کمبود (اگر ساعات کار عادی بیشتر از آرمان مورد نظر گردد) d2- =

اکنون می توان محدودیت های آرمانی (جزء 4) را نوشت. آرمان هزینه های تولید از نوع آرمان های یک طرفه بالاست. یعنی شرکت نمی خواهد هزینه های برنامه ریزی از آرمان شرکت بیشتر گردد. همچنین آرمان مربوط به ساعات کار عادی یک آرمان یک طرفه پایین است و شرکت نمی خواهد عدد مربوط به آن از آرمان مورد نظر شرکت کمتر باشد.

تابع هزینه های کل تولید که به صورت زیر است:

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

هر دو متغیر d1- و d1+ باید بزرگتر و یا مساوی صفر باشند و البته یکی از آنها در هر حالت باید برابر با صفر باشد. با کمی دقت متوجه می شوید که چرا لازم است متغیر d1- با علامت مثبت (+) و d1+ با علامت منفی (-) در محدودیت آرمانی ظاهر شوند.

به همین صورت تابع مربوط به ساعات کار عادی را نیز که به صورت زیر است:

می توان به صورت محدودیت آرمانی زیر بازنویسی نمود:

که در آن SFP برابر است با 75% از کل ساعات عادی نیروی کار.

متغیرهای d2- و d2+ نیز بزرگتر یا مساوی صفر هستند و حداقل یکی از آنها باید برابر با صفر باشد. تابع هدف (جزء 5) در یک مسئله آرمانی همیشه به صورت حداقل کردن مجموع وزنی انحرافات نامطلوب نوشته می شود. در محدودیت آرمانی هزینه کل تولید، متغیر انحراف اضافی (d1+) متغیر انحرافی نامطلوب است و در محدودیت آرمانی ساعات عادی کار، متغیر انحراف کمبود (d2-) متغیر انحرافی نامطلوب می باشد. قصد ما حداقل نمودن مجموع این انحرافات نامطلوب است. اغلب این انحرافات دارای درجه اهمیت متفاوتی نسبت به یکدیگر می باشند و به همین منظور به این انحرافات در تابع هدف وزن تعلق می گیرد. برای مثال، در مسئله مورد نظر تابع هدف را می توان به شکل زیر نوشت:

بنابراین مدل آرمانی مسئله به شکل زیر خواهد بود:

نکته قابل توجه در برنامه ریزی آرمانی این مطلب است که مدل آرمانی قادر به ارائه جواب بهینه نمی باشد و تنها جواب راضی کننده و کاربردی ارائه می دهد.

مطلب مرتبط بعدی:مدلسازی مسائل برنامه ریزی غیرخطی

مطلب مرتبط قبلی: مدلسازی مسائل چند هدفه


 
 
مدلسازی مسائل چند هدفه
نویسنده : محسن رحیمی - ساعت ٧:٢٢ ‎ب.ظ روز ۱۳٩٠/٥/٢۱
 

مسائلی را که تاکنون مورد بررسی قرار دادیم تنها دارای یک هدف بودند. امروزه، داشتن تنها یک هدف و برنامه ریزی برای دستیابی آن برای بقای سازمان در یک محیط پویا که همواره در حال تغییر است کافی نیست و بسیاری از شرکت ها و سازمان ها دارای چندین هدف هستند که گاهی این اهداف در مقابل هم قرار می گیرند. معمولاً شناخت صریح و روشن از کلیه اهداف یک سازمان بسیار مشکل است و مدیران شرکت ها اغلب چندین هدف را که برخی از آنها با یکدیگر در تقابل هستند را دنبال می کنند. یک شرکت تولیدی را در نظر بگیرید که اهداف مدیران شرکت عبارت است از کسب سود بیشتر، گسترش سازمان، افزایش تولیدات و نیروی انسانی، ایجاد امنیت شغلی برای پرسنل و ساختن وجهه مناسب از شرکت در جامعه. در اینجا ایجاد وجهه اجتماعی مناسب به معنای پرداخت پول و ارسال کمک های مالی در برنامه ها و مراسم مختلف اجتماعی است که با هدف بدست آوردن سود بیشتر مغایرت دارد.

مثال : مسئله برنامه ریزی تولید

واحد تولید یک شرکت بزرگ سفارشی مبنی بر ساخت و تحویل 300 واحد کالا در مدت یک هفته دریافت کرده است. این شرکت دارای دو خط تولید است که به طور معمول هر کدام 25 ساعت در طول یک هفته مشغول به کار هستند. خط تولید A در هر ساعت 5 واحد کالا تولید می کند و خط تولید B نیز در هر ساعت 4 واحد کالا را تحویل می نماید. هزینه استفاده از خط A ساعتی 40 دلار و هزینه استفاده از خط B ساعتی 44 دلار است. زمان اضافه کاری نیز وجود دارد، به طوریکه خط A می تواند 30 ساعت علاوه بر زمان معمول کاری به تولید ادامه دهد که در این صورت هزینه های استفاده از خط A در اضافه کاری ساعتی 50 دلار خواهد شد. خط B نیز 30 ساعت اضافه می تواند کار کند که هزینه های آن ساعتی 48 دلار خواهد بود. شرکت می خواهد برنامه تولیدی را به گونه ای بنویسد که (1) هزینه های تولید حداقل گردد و همچنین (2) ساعات معمولی کار نیروی انسانی خود را حداکثر نماید. جدول اطلاعات مسئله به شکل زیر است:

جدول 1. اطلاعات مسئله برنامه ریزی تولید

زمان 

واحد در ساعت 

کل ساعات 

هزینه هر واحد 

خط A

خط B

خط A

خط B

خط A

خط B

معمولی 

25 

25 

11 

اضافه کار 

30 

30 

10 

12 

 

مرحله اول: تعریف متغیرها

تعداد واحدهای تولید شده در خط A در ساعت معمولی کار =xAR

تعداد واحدهای تولید شده در خط B در ساعت معمولی کار =xBR

تعداد واحدهای تولید شده در خط A در ساعت اضافه کاری =xAO

تعداد واحدهای تولید شده در خط B در ساعت اضافه کاری =xBO

مرحله دوم: تعیین توابع هدف

تابع هدف اول: حداقل نمودن هزینه کل

تابع هدف دوم: حداکثر نمودن استفاده از ساعات معمولی نیروی کار

مرحله سوم: تعیین محدودیت ها

محدودیت تولید:

محدودیت ساعات معمولی کار:

محدودیت ساعات اضافه کاری:

محدودیت های غیر منفی:

بنابراین این مدل که دارای دو هدف می باشد به صورت زیر خواهد بود:

 مطلب مرتبط بعدی: مدلسازی برنامه ریزی آرمانی

مطلب مرتبط قبلی: مثالی برای مدلسازی عدد صحیح (مسئله بودجه بندی سرمایه ای)


 
 
مثالی برای مدلسازی عدد صحیح (مسئله بودجه بندی سرمایه ای)
نویسنده : محسن رحیمی - ساعت ۱٠:۳۱ ‎ب.ظ روز ۱۳٩٠/٥/۱٩
 

در این مطلب مثالی را برای برنامه ریزی عدد صحیح ارائه می کنیم.

سازمان ها عمدتاً با موقعیت هایی روبه رو می شوند که باید یک یا چند پروژه را جهت سرمایه گذاری از بین چندین پروژه انتخاب نمایند. لیست پروژه های زیر را در نظر بگیرید.

جدول 1. اطلاعات مسئله بودجه بندی سرمایه ای

شماره پروژه 

سرمایه اولیه لازم (میلیون دلار) 

سود قابل انتظار 

18 

18 

16 

3

10 

12 

4

25 

5

14 

اگر کل بودجه سازمان 30 میلیون دلار باشد، کدام پروژه ها باید انتخاب شوند؟

هدف مسئله حداکثر نمودن کل سود مورد انتظار سازمان است. محدودیت اصلی نیز محدودیت میزان بودجه است به طوریکه سرمایه اولیه لازم برای کل پروژه های انتخاب شده نباید از 30 میلیون دلار تجاوز کند. جهت تصمیم گیری لازم است مشخص کنیم یک پروژه خاص باید انتخاب شود یا خیر. بنابراین استفاده از متغیرهای صفر و یک راهکار مناسبی برای مدلسازی این مسئله است.

مرحله اول: تعریف متغیرها

با توجه به اطلاعات مسئله پنج پروژه با شماره های 1، 2، 3، 4 و 5 وجود دارد که باید نسبت انتخاب یا عدم انتخاب آنها تصمیم گیری شود. بنابراین 5 متغیر به صورت x1، x2، x3، x4 و x5 و از نوع صفر و یک را به شکل زیر تعریف می کنیم:

 

به طور مثال اگر پس از حل مسئله مقدار متغیر x2 برابر با یک گردید یعنی بر روی پروژه دوم سرمایه گذاری شود و اگر این متغیر مقدار صفر را گرفت به این معناست که نباید در این پروژه سرمایه گذاری نمود.

مدل برنامه ریزی عدد صحیح این مثال به صورت زیر خواهد بود:

مطلب مرتبط بعدی:مدلسازی مسائل چند هدفه

مطلب مرتبط قبلی: مدلسازی مسئله برنامه ریزی عدد صحیح


 
 
مدلسازی مسئله برنامه ریزی عدد صحیح Integer Programming
نویسنده : محسن رحیمی - ساعت ٩:۱۸ ‎ب.ظ روز ۱۳٩٠/٤/۳۱
 

برنامه ریزی عدد صحیح (IP) نام گروهی از مسائل برنامه ریزی خطی است که در آن کلیه یا تعدادی از متغیرها حتماً باید اعداد صحیح غیر منفی باشند. برای حالت عمومی برنامه ریزی خطی متغیرهای تصمیم بهینه می توانند هر مقدار غیر منفی صحیح یا غیر صحیح باشند. متاسفانه اعداد غیر صحیح (کسری) در بسیاری از مسائل نه عملی هستند و نه معنی دار. این مشکل در اکثر مسائل مربوط به تجارت، مسائل تولیدی و نظامی وجود دارد. برای نمونه اگر در مثال انتخاب تعداد مناسب وسائل نقلیه ها جواب به صورت کسری حاصل شود (مثلاً تعداد ماشین ماک 37.6 محاسبه شود) اصالتاً پاسخ معنی داری نیست. برای حل این معضل برنامه ریزی عدد صحیح که پاسخ های حاصل از آن اعداد صحیح هستند مورد استفاده قرار می گیرد. به طور کلی می توان گفت برنامه ریزی عدد صحیح همان برنامه ریزی خطی است که شرط بخش پذیری برای آن صادق نیست. سه نوع مدل برنامه ریزی عدد صحیح وجود دارد که عبارتند از:

  • برنامه ریزی عدد صحیح عمومی که در این برنامه ریزی همه متغیرها می توانند کلیه اعداد صحیح را به خود بگیرند.
  • برنامه ریزی عدد صحیح صفر و یک محض که در این نوع برنامه ریزی متغیرها تنها می توانند اعداد صفر یا یک را به خود بگیرند. در برخی از مسائل، متغیرها به گونه ای هستند که تنها یک یا دو مقدار را می توانند بپذیرند. برای مثال پاسخ به این سوال که در پروژه آلفا سرمایه گذاری شود یا خیر تنها دارای دو حالت مثبت و منفی است که این دو مقدار را می توان به صفر و یک نسبت داد.
  • عدد صحیح صفر و یک مختلط که در این نوع برنامه ریزی متغیرهای مسئله هم از نوع صفر و یکی هستند و هم از نوع اعداد حقیقی.

مثال های ترکیب محصول و ترکیب وسائل نقلیه و مدل های برنامه ریزی خطی آنها را به خاطر بیاورید. پس از حل این مدلها ممکن است متغیرها اعدادی اعشاری شوند مثلاً 3.6 میز یا 14.2 صندلی، 51.3 ماک و 49.7 مرسدس. در واقعیت چنین ارقامی چون کسری هستند برای این مسائل پاسخ معنی داری نیستند. دقت نمایید که برای مثال برنامه ریزی غذایی اعشاری بودن مقادیر متغیرها مشکلی ایجاد نمی کند. برای جلوگیری از مقادیر اعشاری لازم است که در مدل متغیرها را از نوع عدد صحیح تعریف نماییم. در زیر مثال ترکیب محصول را با توجه به اینکه متغیر ها باید از نوع عدد صحیح باشند بازنویسی کرده ایم.

مدل بالا را می توان یک مدل برنامه ریزی عدد صحیح نامید. همانطور که ملاحظه می شود تفاوت مدل اولیه با این مدل تنها در اضافه نمودن عبارت Integer در انتهای محدودیت غیر منفی بودن متغیرهاست. در نرم افزارهای مختلف حل مسائل برنامه ریزی خطی، راه های گوناگونی جهت تعیین عدد صحیح بودن متغیرها وجود دارد. در این بخش قصد پرداختن به چگونگی حل این مسائل را نداریم. تنها باید به یاد داشته باشیم که در مدلسازی حتماً باید نوع متغیرها مشخص باشد. در صورتی که در رابطه با متغیرها به جز محدودیت غیر منفی بودن قید دیگری ذکر نشده بود، متغیرها از نوع اعداد حقیقی غیر منفی هستند. برای تعیین صفر و یک بودن متغیرها نیز می توانید از عبارت are either 1 or 0 پس از محدودیت غیر منفی بودن استفاده نمایید.

پست مرتبط بعدی:مثالی برای مسئله بودجه بندی سرمایه ای

پست مرتبط قبلی: مدلسازی مسئله انتخاب ترکیب وسائل نقلیه


 
 
مدلسازی مسئله انتخاب ترکیب وسائل نقلیه
نویسنده : محسن رحیمی - ساعت ۱٠:۱۳ ‎ب.ظ روز ۱۳٩٠/٤/٢٩
 

مسئله: یک فرمانده نظامی موظف شده است تا نیروهای خود را به منظور عملیاتی مهم به محل دیگری منتقل کند. این فرمانده مطلع شده است که تنها می تواند از حداکثر 100 وسیله نقلیه برای هر مرحله انتقال استفاده کند. دو نوع وسیله نقلیه مختلف در دسترس می باشد. خودروی ماک که 24 متر مکعب گنجایش دارد و خودروی مرسدس که 16 متر مکعب ظرفیت دارد. تخمین زده شده است که هر خودروی ماک برای هر مرحله انتقال 50 لیتر سوخت و خودروی مرسدس 25 لیتر سوخت نیاز دارد. کل سوخت موجود نیز 4000 لیتر است. وسائل نقلیه بعد از هر مرحله سفر احتیاج به تعمیر و بازبینی دارند. خودروی ماک به سه ساعت و مرسدس به 9 ساعت زمان جهت بازرسی نیاز دارد. زمان کل گروه تعمیرکار نیز 720 ساعت است. برای حداکثر کردن میزان حجم منتقل شده، چه ترکیبی از خودروهای ماک و مرسدس باید توسط فرمانده انتخاب شود؟

مدلسازی مسئله: خلاصه ای از مسئله در جدول زیر نشان داده شده است:

جدول 1. اطلاعات مسئله انتخاب خودرو

پارامتر 

نوع ماشین 

محدودیت 

ماک 

مرسدس 

سوخت (لیتر) 

50

25

4000

تعمیر و نکهداری (ساعت) 

3

9

720

گنجایش (متر مکعب) 

24

16

حداکثر اتومبیل قابل استفاده

100

 

مرحله اول: تعریف متغیرها

تعداد اتومبیل ماک که باید مورد استفاده قرار گیرد x1 =

تعداد اتومبیل مرسدس که باید مورد استفاده قرار گیرد x2 =

مرحله دوم: تعیین تابع هدف

هدف مسئله حداکثر نمودن حجم قابل انتقال است.

مرحله سوم: تعیین محدودیت ها

بنابراین مدل نهایی مسئله به صورت زیر ارائه می گردد:

پست مرتبط بعدی:مدلسازی مسئله برنامه ریزی عدد صحیح

پست مرتبط قبلی: مدلسازی مسئله برنامه ریزی تغذیه


 
 
مدلسازی مسئله برنامه ریزی تغذیه
نویسنده : محسن رحیمی - ساعت ٧:۳۸ ‎ب.ظ روز ۱۳٩٠/٤/٢٧
 

یک متخصص امور تغذیه ورزشی می خواهد برنامه غذایی خاصی بنویسد که شامل سه غذای اصلی A، B و C باشد. هر گرم از A دارای سه واحد پروتئین، دو واحد کربو هیدرات و چهار واحد چربی است. . هر گرم از B دارای یک واحد پروتئین، سه واحد کربو هیدرات و دو واحد چربی است و هر گرم از C دارای سه واحد پروتئین، یک واحد کربو هیدرات و چهار واحد چربی است. این متخصص درصدد است وعده ای غذایی تهیه کند که حداقل دارای 440 واحد چربی، 150 واحد کربوهیدرات و 320 واحد پروتئین باشد. اگر قیمت یک کیلوگرم از A ، 15.60 دلار، یک کیلوگرم از B18.90 دلار و یک کیلوگرم از C12.70 دلار باشد، چند گرم از هر غذا باید در یک وعده سرو شود تا هزینه ها حداقل شده و در عین حال محدودیت های متخصص نیز برآورده شود.؟

برای مسئله ارائه شده اطلاعات مسئله را می توان به شکل خلاصه در جدول زیر مشاهده نمود:

جدول 1. اطلاعات مسئله وعده غذایی

پارامتر

نوع ماده غذایی

مقدار لازم

A

B

C

چربی

4

2

4

+440

کربوهیدرات

2

3

1

+150

هزینه ($/Kg)

15.6

18.9

12.7

 

 قصد داریم این مثال را بدون نشان دادن جزئیات محاسبه مدلسازی نماییم.

مرحله اول: تعریف متغیرها

میزان ماده غذایی A به کیلوگرم  = x

میزان ماده غذایی B به کیلوگرم  =  y

میزان ماده غذایی C به کیلوگرم  =  w

مرحله دوم: تعیین تابع هدف

در این مسئله هدف حداقل نمودن کل هزینه هاست. برخلاف مثال ترکیب محصول که تابع هدف از نوع حداکثر نمودن بود در این مثال هدف حداقل نمودن است. در نتیجه تابع هدف عبارت است از:

مرحله سوم: تعیین محدودیت ها

برای این مسئله سه محدودیت می توان نوشت. محدودیت حداقل میزان چربی، کربوهیدرات و پروتئین که باید میزان آنها بزرگتر یا مساوی حداقل ارائه شده در مثال باشد. بنابراین محدودیت ها را می توان به شکل زیر نوشت:

شکل نهایی مدل نیز به صورت زیر خواهد بود:

 پست مرتبط بعدی: مدلسازی مسئله انتخاب ترکیب وسائل نقلیه

پست مرتبط قبلی: مدلسازی یک مسئله ترکیب محصول


 
 
مدلسازی یک مسئله ساده ترکیب محصول
نویسنده : محسن رحیمی - ساعت ۱٠:٢٥ ‎ب.ظ روز ۱۳٩٠/٤/٢۱
 

مسئله: یک نجار در کارگاه خود میز و صندلی تولید می کند. فرآیند کار عبارت است از ماشین کاری، سنباده زنی و مونتاژ قطعات برای تهیه میز و صندلی. نجار برای تولید هر میز پنج ساعت به ماشین کاری، چهار ساعت به سنباده زنی و سه ساعت به مونتاژ قطعات می پردازد. برای تولید هر صندلی نیز به دو ساعت ماشین کاری، سه ساعت سنباده زنی و چهار ساعت مونتاژ نیاز دارد. شرایط تجهیزات به گونه ای است که در کل برای عمل ماشین کاری 270 ساعت، برای عمل سنباده زنی 250 ساعت و برای مونتاژ 200 ساعت زمان بیشتر وجود ندارد. اگر سود هر میز 100دلار و هر صندلی 60 دلار باشد، این نجار چه تعداد میز و چه تعداد صندلی تولید کند که سود خود را ماکزیمم نماید؟ اگر لازم باشد به ازای هر میز، چهار صندلی نیز تولید شود مدلسازی چه تغییری می کند؟

حل مسئله: در بسیاری از موارد برای ساده سازی فرآیند مدلسازی و فهم بهتر مسئله می توان اطلاعات مسئله را در یک جدول منظم و با صلاحدید مدلساز گردآوری کرد، برای نمونه جدول خلاصه اطلاعات مسئله بالا در جدول 1 آمده است:

جدول 1 اطلاعات مسئله تولید میز و صندلی

میزان منبع موجود (ساعت)

میزان منبع مورد نیاز به ازای هر واحد محصول 

نوع کار 

صندلی 

میز 

270 

ماشین کاری 

250 

سمباده زنی 

200 

مونتاژ 

 

60 

100 

سود هر واحد (دلار) 

 در مدلسازی مسئله، در ابتدا متغیرهای مسئله تعریف می شوند، سپس توابع ریاضی مربوط به محدودیت ها و هدف مسئله استخراج می شوند.

تعریف متغیرها

متغیرهای تصمیم در این مسئله عبارتند از:

 T= تعداد میز هایی که باید تولید شود.

C = تعداد صندلی هایی که باید تولید شود.

T و C متغیر های مجهولی هستند که قصد مدلساز یافتن مقدار مناسب برای آنهاست. برای نام گذاری متغیرها می توان از x1، x2 یا x، y به جای T و C استفاده نمود.

تعیین تابع هدف

همانطور که از مسئله بر می آید، هدف جداکثر نمودن سود حاصل از فروش صندلی ها و میز های تولید شده است. تابع هدف مسئله را می توان به شرح زیر نوشت:

تعداد تولیدی از محصول مورد نظر × سود هر واحد محصول = سود حاصل از تولید محصولی خاص

100T=     سود کل حاصل از فروش میزها

60C =       سود کل حاصل از فروش صندلی ها

100T+60C= سود کل حاصل از فروش میزها و صندلی ها

بنابراین تابع هدف عبارت خواهد بود از:

حرف Z نشاندهنده تابع هدف است و کلمه Maximize که گاهی به صورت اختصاری Max نیز نوشته می شود بیانگر این مطلب است که هدف حداکثر نمودن مقدار تابع هدف است.

تعیین محدودیت ها

برای این مسئله سه محدودیت ذکر شده است. ساعت های موجود برای ماشین کاری، سمباده زنی و مونتاژ قطعات.

محدودیت مربوط به مرحله ماشین کاری:

برای عملیات ماشین کاری 270 ساعت در نظر گرفته شده است. برای تولید هر میز احتیاج به 5 ساعت عملیات ماشین کاری است و در مقابل برای تولید هر صندلی این زمان 2 ساعت می باشد. بنابراین کل مدت زمانی که برای عملیات ماشین کاری صرف خواهد شد به صورت زیر قابل محاسبه است:

تعداد محصول × زمان لازم برای ماشین کاری هر واحد محصول = کل زمان ماشین کاری محصول

5T= کل زمان لازم برای ماشین کاری میزها

2C= کل زمان لازم برای ماشین کاری صندلی ها

5T+2C= کل زمان لازم برای ماشین کاری میزها و صندلی ها

بنابراین محدودیت مربوط به زمان ماشین کاری به صورت زیر خواهد بود:

LHS این محدودیت بیانگر کل مدت زمان لازم برای عملیات ماشین کاری است و RHS بیانگر کل مدت زمان در دسترس برای این عملیات است. علامت کوچکتر مساوی بین RHS و LHS نشان دهنده این مطلب است که مدت زمان لازم برای عملیات ماشین کاری نباید بیشتر از کل زمان در دسترس برای این عملیات باشد.

محدودیت مربوط به مرحله سمباده زنی:

برای عملیات سمباده زنی 250 ساعت وجود دارد. برای تولید هر میز به 4 ساعت و برای تولید هر صندلی به 3 ساعت سمباده زنی احتیاج است. بنابراین محدودیت مربوط به این عملیات را می توان به صورت زیر نوشت:

محدودیت مربوط به مرحله مونتاژ قطعات:

برای مونتاژ تنها 200 ساعت زمان وجود دارد. تولید هر میز به 3 ساعت و تولید هر صندلی به 4 ساعت مونتاژ نیاز دارد. بنابراین محدودیت مونتاژ به صورت زیر خواهد بود:

محدودیت غیر منفی بودن:

باید به این نکته توجه داشت که تعداد میز ها یا صندلی ها نمی تواند منفی باشد بنابراین T و C باید غیر منفی (صفر و یک) باشند. بسیاری از نرم افزارهای طراحی شده برای حل این مسائل این شرط را برای حل مدل ها به صورت پیش فرض در نظر می گیرند. محدودیت های غیر منفی بودن متغیرهای مسئله به صورت زیر نوشته می شوند:

بنابراین شکل کلی مدل ریاضی این مسئله خواهد شد:

این مدل نشان می دهد که مقدار Z باید با توجه به سه محدودیت ماشین کاری، سمباده زنی و مونتاژ حداکثر گردد. به جای عبارت subject to در برخی از موارد از علامت عضویت نیز استفاده شده است. در حل مدل بالا هدف یافتن مقادیر عددی برای T و C است به طوریکه هم در محدودیت ها صدق کند و هم مقدار تابع هدف را بهینه سازد.

تعاریف ارائه شده برای C و T را در نظر بگیرید. شما می توانید با دقت در مدل ریاضی بالا، مسئله مورد نظر را بدون آنکه آن را قبلاً شنیده باشید حدس بزنید. با این حال شما می توانید مسائل گوناگونی را بنویسید که با مدل بالا همخوانی داشته باشند. همانطور که می دانید مدل بالا یک ارائه ریاضی از مسئله است. نکته مهم آن است که برای یک مسئله مدل ریاضی منحصربفرد وجود ندارد و با توجه به نوع متغیرهای تصمیم تعریف شده و فرضیات مدلساز، مدل می تواند اشکال گوناگونی به خود بگیرد. گاهی ممکن است شما به عنوان مدلساز احساس کنید به متغیرهای دیگری علاوه بر متغیرهای وجود نیاز دارید. برای نمونه در مسئله تولید میز و صندلی متغیری با تعریف کل ساعات ماشین کاری مورد نیاز و یا ساعات استفاده نشده از سهمیه زمان ماشین کاری در نظر بگیرید. این دو متغیر را می توان به راحتی از محدودیت ماشین کاری، در صورتی که C و T معین باشند محاسبه کرد و این به یعنی به منظور خلاصه کردن مدل می توان از بکاربردن چنین متغیرهایی جلوگیری کرد. چون یکی از عوامل پیچیدگی محاسباتی یک مدل ریاضی، تعداد متغیرها و محدودیت های مدل است، انتظار می رود که مدلساز سعی کند مدل ریاضی خود را با حداقل تعداد متغیرها و محدودیت ها کامل کند.

در عبارت پایانی مسئله، این سوال مطرح شده است که اگر قرار باشد برای هر میز حتماً چهار صندلی نیز تولید شود، مدلسازی مسئله چگونه صورت خواهد گرفت. این عبارت محدودیتی جدید به مدل اضافه می کند که موجب می شود به ازای هر میز، 4 صندلی نیز وجود داشته باشد. این شرط را به صورت ریاضی می توان چنین نوشت:

برای کنترل صحت این رابطه می توان فرض کرد 5 میز تولید شده باشد یعنی T = 5، آنگاه طبق رابطه بالا C برابر با 20 گردد و این یعنی تولید 20 صندلی به ازای تولید 5 میز.

از آنجا در اکثر نرم افزارهای بهینه سازی دستورالعمل این است که همه متغیرهای تابع محدودیت در LHS باشند و اعداد ثابت نیز در RHS، رابطه بالا را باید به صورت زیر بازنویسی کرد:

در نهایت مدل ریاضی جدید به صورت زیر خواهد بود:

پست مرتبط بعدی: مدلسازی مسئله برنامه ریزی تغذیه

پست مرتبط قبلی: اجزای مدل ریاضی برنامه ریزی خطی: محدودیت


 
 
اجزای مدل ریاضی برنامه ریزی خطی : محدودیت ها
نویسنده : محسن رحیمی - ساعت ٧:۳٢ ‎ب.ظ روز ۱۳٩٠/٤/۱۸
 

محدودیت ها همانطور که از نامشان پیداست موانع و قیودی هستند که در مسئله وجود دارند. هر محدودیت معمولاً از دو بخش اصلی تشکیل شده است.؛ یک رابطه تابعی و یک عدد ثابت، که بوسیله علامت مساوی و یا نامساوی با هم ارتباط دارند. برای نمونه فرض کنید یکی از مواد اولیه مورد نیاز برای تولید محصولی دارای تعداد محدودی باشد. برای نوشتن مدل این مسئله باید محدودیت ماده اولیه (محدودیت منبع) را در نظر گرفت، به این صورت که بخش رابطه تابعی محدودیت، نشاندهنده ماده اولیه مورد نیاز بر حسب متغیرهای تصمیم است و بخش عدد ثابت محدودیت نیز برابر با مقدار کل ماده اولیه موجود را می باشد. برای شکل گیری توابع محدودیت به پارامترهایی مانند میزان ماده اولیه مورد نیاز برای تولید یک واحد محصول نیاز است که این پارامترها را در اصطلاح «ضرایب محدودیت» و یا «ضرایب فنی[1]» می گویند. دقت داشته باشید که اکثر نرم افزارهای بهینه سازی موجود، طبق یک توافق نا نوشته بخش تابعی محدودیت را در سمت چپ عبارت مساوی و یا نامساوی قرار می دهند و به همین دلیل به آن LHS می گویند و مقادیر ثابت محدودیت ها را در سمت راست آن قرار می دهند و به آن RHS می گویند.



[1] Technological Coefficient

پست مرتبط بعدی:

پست مرتبط قبلی: اجزای مدل برنامه ریزی خطی: تابع هدف


 
 
اجزای مدل ریاضی برنامه ریزی خطی : تابع هدف
نویسنده : محسن رحیمی - ساعت ٧:٥٠ ‎ب.ظ روز ۱۳٩٠/٤/۱٦
 

تابع هدف رابطه ای است ریاضی، که برحسب متغیرهای تصمیم نوشته می شود و هدف مسئله را بیان می کند و تصمیم گیرنده به کمک تکنیک های شناخته شده مختلف، سعی در حداکثر نمودن (Maximize) و یا حداقل نمودن (Minimize) تابع هدف دارد. برای نمونه حداکثر کردن درآمد و یا حداقل نمودن هزینه تولید محصولی خاص. برای شکل دهی تابع هدف تشخیص پارامترهایی مانند سود (برای حداکثر کردن) و یا هزینه (برای حداقل کردن) تولید یک کالا پارامترهایی ضروری هستند. پس از تشخیص، این پارامترها با متغیرهای تصمیم مناسب همبسته می شوند و تابع هدف نهایی ایجاد می شود. به این پارامترها در اصطلاح ضرایب (سود یا هزینه) تابع هدف می گویند.

پست مرتبط بعدی:اجزای مدل ریاضی برنامه ریزی خطی : محدودیت ها

پست مرتبط قبلی: اجزای مدل ریاضی برنامه ریزی خطی : متغیر تصمیم


 
 
اجزای مدل برنامه ریاضی برنامه ریزی خطی: متغیر تصمیم
نویسنده : محسن رحیمی - ساعت ٩:۱٥ ‎ب.ظ روز ۱۳٩٠/٤/۱٥
 

مدل های ریاضی شامل سه جزء اصلی هستند: متغیرهای تصمیم (مجهولات مسئله)، تابع هدف (که باید آن را بهینه نمود) و محدودیت ها (شرایط محدود کننده مسئله). این اجزاء در این مطلب و دو مطلب مرتبط آینده به طور خلاصه تشریح می شوند.

متغیرهای تصمیم

 متغیر تصمیم می تواند میزان تولید یک کالا باشد، می تواند تعداد افراد تخصیص یافته به یک کار باشد و یا هر دو. اینکه متغیر تصمیم چگونه تعریف شود بستگی به نوع مسئله و مجهولات آن دارد. هدف تصمیم گیرنده یافتن مجموعه ای از مقادیر برای متغیرهای مجهول مسئله است به طوریکه بتوانند جوابی بهینه برای مسئله مورد نظر ارائه دهند. متغیر های تصمیم را معمولاً به شکل های x1، x2 و x3 . یا x، y و z نشان می دهند. با این حال مدلساز در نمادگذاری متغیرها آزاد است. اما باید در نظر داشت برخی از نرم افزارهای موجود برای نام متغیرهای تصمیم محدودیت هایی از جمله در طول این عبارات دارند. در مقابل نرم افزارهایی نیز وجود دارند که به مدلساز اجازه نام گذاری با هر طول از حروف و یا حتی عبارات ترکیبی شامل حروف و اعداد را می دهند. در برخی از مسائل بهتر است برای متغیرها اسامی معنی دار و مفهوم انتخاب گردد. استفاده از نام های کوتاه برای متغیرهای تصمیم به 2 دلیل عمده ترجیح داده می شود: (1) استفاده از نام های کوتاه امکان اشتباه در نوشتن و یا تایپ کردن را کاهش می دهد و (2) مدل را فشرده تر و مختصر می سازد.

مطلب مرتبط بعدی: اجزای مدل برنامه ریاضی برنامه ریزی خطی: تابع هدف

مطلب مرتبط قبلی: دسته بندی مسائل بهینه سازی


 
 
دسته بندی مسائل بهینه سازی
نویسنده : محسن رحیمی - ساعت ۱۱:٢٧ ‎ب.ظ روز ۱۳٩٠/٤/۱٤
 

مسائل بهینه سازی را می توان طبق نمودار شکل زیر تقسیم بندی نمود. پیش از این دسته بندی بر اساس تعداد تابع هدف (تک هدفه و چند هدفه) و نوع آن (ماکزیمم و مینیمم) را شرح دادیم. در مسائل چند هدفه عموماً توابع هدف با یکدیگر در تناقض هستند. در غیر این صورت می توان چند هدف را تبدیل به یک هدف نمود. اینکه مسئله دارای محدودیت است یا خیر نوع دیگری از دسته­بندی مسائل را تعریف می کند. برخی از کارشناسان معتقدند که در دنیای واقعی هیچ مسئله ای بدون محدودیت نیست و همه مسائل حداقل دارای یکی از محدودیتهای تابعی یا حدی (مرز بالا و پایین متغیر تصمیم) هستند. مطالعه مسائل بدون محدودیت یا به عبارت دیگر مسائل نامقید از آن جهت اهمیت دارد که بسیاری از الگوریتم های بهینه سازی مسائل مقید را با تبدیل آنها به یک یا مجموعه ای از مسائل نامقید حل می کنند. علاوه بر این بسیاری از تکنیک های بهینه سازی مسائل مقید بر اثر تغییرات خلاقانه ای که بر تکنیک های بهینه سازی نامقید صورت گرفته، ایجاد شده اند.

همچنین متغیرهای تصمیم مسئله را نیز می توان به سه دسته، حقیقی، عدد صحیح و یا ترکیبی از هر دو تقسیم نمود. با این حال بسیاری از مدلسازان دسته بندی دیگری با موضوعات پیوسته، گسسته (مسائل عدد صحیح) و ترکیبی از این دو را بیشتر می پسندند. در مسائلی با متغیرهای پیوسته (حقیقی)، اصولاً در پی یافتن مجموعه ای از اعداد حقیقی هستیم. میائل بهینه سازی با متغیرهای گسسته یا عدد صحیح را مسائل ترکیبی می گویند. در مسائل ترکیبی به دنبال هدف بهینه از بین یک مجموعه محدود یا غیرمحدود هستیم، که می تواند یک عدد صحیح، یک مجموعه و یا حتی یک گراف باشد. این دو نوع مسئله ذات کاملاً متفاوتی دارند و روش های حل آنها نیز کاملاً متفاوت است.

 طبقه بندی توابع اساساً با ویژگی های ریاضی تابع که از منظر شیوه حل بسیار اهمیت دارد، در ارتباط است. توابع هدف و محدودیت ها می توانند خطی، غیر خطی یا ترکیبی از هر دو باشند. اگر همه توابع مدل خطی باشند به آن مدل برنامه ریزی خطی می گویند. اگر حداقل یکی از توابع مدل خاصیت غیرخطی داشته باشند، مدل را مدل غیر خطی می نامند. روش های حل مسئله های غیرخطی کاملاً متفاوت و پیچیده تر از روش های حل مسائل خطی است. یک مسئله نامقید تک هدفه از نقطه نظر علم بهینه سازی ساده ترین نوع مسئله برای حل است ولی اگر همین مسئله نامقید از نوع غیرخطی باشد می تواند تا بالاترین سطح دشواری مسائل بهینه سازی پیش رود. اثبات این ادعا نیز مطالعات و مقالات فراوانی است که در رابطه با روش های حل این نوع مسئله ارائه شده است.

ویژگی محدب بودن یکی از مهمترین مشخصه های بهینه سازی کلاسیک است به طوریکه بسیاری از تکنیک ها و الگوریتم های بهینه سازی با این فرض می توانند استفاده شوند که توابع محدب هستند. در بهینه سازی، روش های حل را می توان در دو گروه اساسی قرار داد: روش های مشتق پایه و روش های آزاد از مشتق. برای استفاده از تکنیک های مشتق پایه، لازم است که توابع مشتق پذیر باشند. لازمه مشتق پذیری تابع نیز پیوستگی آن است. مباحث مربوط به مشتق پذیری، پیوستگی و تحدب توابع را می توانید در بسیاری از مراجع و کتابهای ریاضی دانشگاهی مطالعه کنید.

به عنوان مثال یک مسئله تک متغیره مقید با متغیرهای تصمیم پیوسته می تواند غیرخطی، محدب و مشتق پذیر باشد. به علاوه بر اساس دسته بندی بالا، دامنه مسائل بهینه سازی ویژگی های بسیاری از تابع، مثل تک نمایی بودن یا چند نمایی بودن، ایستا بودن یا پویا بودن و حتی ویژگی محدودیت ها مثل نرم بودن یا سخت بودن آنها را می تواند در بر گیرد. تابعی را که دارای تنها یک پیک (محلی یا سراسری) باشد در اصطلاح تک نمایی می گویند و تابعی را که بیش از یک پیک داشته باشد، تابع چند نمایی می گویند. اگر تابعی در طول زمان تغییر کند آن را پویا و در غیر صورت آن را ایستا می گویند. در این کتاب ما تنها به توابع ایستا می پردازیم. محدودیت هایی که جواب نهایی مسئله حتماً باید در آنها صدق کند را محدودیت های سخت گویند و محدودیت های نرم محدودیت هایی هستند که کمی انحراف جواب نهایی از آنها به میزان مشخصی و یا طبق شرایطی قابل قبول است. 

پست مرتبط بعدی: اجزای مدل برنامه ریزی خطی: متغیر تصمیم

پست مرتبط قبلی: مفهوم بهینه سازی


 
 
مفهوم بهینه سازی
نویسنده : محسن رحیمی - ساعت ٩:٥۱ ‎ب.ظ روز ۱۳٩٠/٤/۱۳
 

مفهوم اساسی بهینه سازی یافتن بهترین پاسخ ممکن برای یک مسئله یا مدل مشخص است که این بهترین پاسخ می تواند یک نقطه در صفحه مختصات باشد و هم می تواند یک گزینه از میان چندین مورد باشد. برای این کار، باید همه حالت های ممکن را بررسی نمود و ثابت کرد که جواب انتخاب شده بهترین است. در مسئله ارائه شده در پست قبلی، هدف یافتن مقدار x به نحوی است که TCS مینیمم گردد و همچنین محدودیت های حدود پایین و بالای متغیر نیز رعایت گردد. برای درک بهتر وظیفه بهینه سازی، پارامترهای TCS، TOC و TIC را با توجه به x تحلیل می کنیم. از آنجا که TPC مستقل از x است و بر فرآیند بهینه سازی تاثیری ندارد می توان آن را حذف نمود و مدل بازنویسی شده زیر را ارائه کرد:

برای راحتی تحلیل، این مسئله را با کمک اطلاعات فرضی تبدیل به یک مثال عددی می کنیم. این مسئله می تواند به مثالهای عددی متنوعی تبدیل شود ولی در اینجا فرض کنید با قراردادن D=100، F=4، h=8، lb=1 و ub=15 بخواهیم مثال عددی تولید کنیم. با این اطلاعات x به صورت زیر محاسبه می شود:

x مقادیر بین یک تا 15 را می تواند به خود بگیرد که با در نظر گرفتن x به عنوان عددی صحیح تنها 15 گزینه وجود خواهد داشت. بنابراین به راحتی و طبق جدول 1 برای همه 15 حالت x محاسبه خواهد شد.

جدول 1. مقادیر TOC، TIC و TCS محاسبه شده برای x های مختلف در مثال پست قبلی

400 

404 

200 

208 

33/133 

12 

33/145 

100 

16 

116 

80 

20 

100 

67/66 

24 

67/90 

14/57 

28 

14/85 

50 

32 

82 

44/44 

36 

44/80

10 

40 

40 

80 

11 

36/36 

44 

36/80 

12 

33/33 

48 

33/81 

13 

77/30 

52 

77/82 

14 

57/28 

56

57/84

15 

67/26 

60 

67/86 

 

از جدول 1 می توان نتیجه گرفت مینیمم مقدار برای هزینه کل سیستم برابر با 80 دلار است که در ازای x=10 حاصل می گردد. در حقیقت این جواب بهینه مسئله عددی فوق است و به این معناست که فروشگاه باید در هر بار سفارش 10 عدد کالا خریداری شود. یافتن جواب این مسئله بسیار ساده و راحت است. متاسفانه این روش کار برای همه مسائل بهینه سازی کارساز نیست زیرا اغلب مسئله ها و مدل ها دارای تعداد حالات و گزینه های ممکن بیشتری هستند و کار ارزیابی همه آنها بسیار مشکل است.

به منظور به کاربردن روش ها و الگوریتم هایی که با ارزیابی زیرمجموعه ای از کل گزینه های ممکن قادر به یافتن جواب بهینه هستند لازم است اطلاعاتی راجع به ویژگی ها و خواص توابع داشته باشیم. جهت بررسی رفتار توابع TOC،TIC وTCS نمودار آنها بر حسب x (در بازه 6 تا 15) در شکل 1 رسم شده است. همانطور که مشاهده می کنید TIC به صورت خطی افزایش یافته، TOC نزولی است و TCS (که جمع TIC و TOC است) در ابتدا حالت نزولی و سپس حالت صعودی می گیرد.

شکل 1. نمودار توابع TOC، TIC و TCS بر حسب x

 

در اینجا بر روی نمودار تابع TCS و نقطه ای که این تابع در آن به مقدار مینیمم خود می رسد تمرکز می کنیم. شکل 2 نمودار این تابع را با جزئیات بیشتری نشان می دهد.

از شکل 2 مشخص می شود که تابع TCS تابعی هموار، پیوسته و محدب است که دارای یک نقطه مینیمم در x=10 است که همان پاسخ بهینه مثال عددی بالا می باشد. ترسیم توابعی با سه متغیر به دلیل سه بعدی بودن مشکل است و برای توابعی که بیشتر از سه متغیر دارند این کار عملی نیست. در این مثال، یافتن و تحلیل پاسخ کاملاً به ویژگی های ریاضی تابع وابسته است.

شکل 2. نمودار تابع TCS بر حسب x

 

تابع TCS برای x حقیقی مشتق پذیر است. پس از مشتق گیری از تابع TCS بر حسب x، خواهیم داشت:

 

 

در اصطلاح ریاضی، d(TCS)/dx را گرادیان تابع x می گویند. اگر گرادیان تابع مذکور را در نقاط x=8، x=10 و x=12 محاسبه کنیم خواهیم داشت:

می توان مشاهده کرد که گرادیان در نقطه بهینه (مینیمم) برابر است با صفر، برای x های کمتر از x نقطه بهینه، عددی منفی و برای x های بزرگتر از x نقطه بهینه عددی مثبت است. یعنی برای یافتن جواب بهینه باید به دنبال نقطه ای بگردیم که گرادیان تابع در آن نقطه برابر با صفر باشد.

پست مرتبط بعدی: دسته بندی مسائل بهینه سازی

پست مرتبط قبلی: مثالی ساده از مدل ریاضی برنامه ریزی خطی


 
 
مثالی ساده از مدل ریاضی برنامه ریزی خطی
نویسنده : محسن رحیمی - ساعت ٧:٤۱ ‎ب.ظ روز ۱۳٩٠/٤/٧
 

فروشگاهی تقاضای خود از یک محصول خاص را به صورت عمده از کارخانه تولید کننده تامین و سپس به صورت تک فروشی به مشتریان عرضه می نماید. تقاضای این محصول تقریباً در طول زمان ثابت است. مدیر فروشگاه ترجیح می دهد سفارش خرید کالا را به صورت عمده ای و با فاصله زمانی ثابت به کارخانه اعلام نماید و سپس آنها را در فروشگاه انبار نماید تا کلیه کالاها فروش رود. این مدیر می خواهد تعیین کند در هر بار سفارش چه تعداد کالا باید خریداری شود و همچنین فاصله زمانی بین سفارش ها باید چه مدت باشد؟

فرض کنید x تعداد کالا در هر بار سفارش باشد. مسلماً هر یک از فعالیت های مربوط به خرید، انبار و اداره فروشگاه هزینه هایی در پی دارند. برای ساده بودن مثال، به طور خلاصه هزینه ها شرح داده می شوند. از آنجا که نرخ فروش مشخص و ثابت است لذا تقاضای سالانه، D، قابل محاسبه می باشد. بنابراین تعداد دفعات سفارش در طول یک سال، n، برابر خواهد بود باD/x. هزینه ای ثابت معادل F ریال برای هر بار سفارش وجود دارد که مستقل از تعداد کالای سفارش داده شده است. واضح است که هر چه x کاهش یابد، n یعنی تعداد دفعات سفارش و در پی آن هزینه کل سفارش در سال، TOC، افزایش خواهد یافت. با افزایش x، هزینه کل انبارداری در سال، TIC، نیز به طور خطی افزایش می یابد. فرض کنید h هزینه انبارداری یک واحد کالا در سال باشد. با توضیحات بالا معادلات زیر را می توان برای هزینه ها نوشت:

که x/2 معادل میانگین کالای انبار شده در طول هر دوره سفارش است. با فرض اینکه p قیمت کالاست، کل هزینه خرید برابر است با TPC=Dp

بنابراین هزینه کل سیستم، TCS، برابر است با:

یعنی باید تعداد کالا در هر بار سفارش، x، به گونه ای محاسبه شود که TCS مینیمم گردد. مدل ریاضی مسئله را می توان به شکل زیر نوشت:

محدودیت ارائه شده بیان می کند که مقدار سفارش،x، باید از حداقل میزان سفارش، lb، بیشتر و از حداکثر میزان سفارش، ub، کمتر باشد. بسته به نوع مسئله x می تواند حقیقی یا عدد صحیح باشد.

پست مرتبط بعدی: مفهوم بهینه سازی

پست مرتبط قبلی:  مدل ریاضی برنامه ریزی خطی و مشخصات آن


 
 
مدل ریاضی برنامه ریزی خطی و مشخصات آن
نویسنده : محسن رحیمی - ساعت ۸:٤٧ ‎ب.ظ روز ۱۳٩٠/٤/٦
 

ساختار عمومی مدل ریاضی که با عنوان مدل برنامهریزی خطی نیز شناخته می شود به صورت زیر می باشد:

x را بیابید به طوریکه:

که در این مدل تابع هدف، f تابعی است از متغیر x و توابع محدودیت gi و hi نیز توابعی عمومی از متغیر x است. عبارات سمت راست معادلات، یعنی gbi و hbi، معمولاً ثابت و معین هستند. اعمال محدودیت غیر منفی، x≥0، برای بسیاری از مسائل واقعی لازم و ضروری است زیرا تعداد بسیار زیادی از متغیرها نمی توانند مقدار منفی بگیرند مثل فاصله. مدل استاندارد بالا ممکن است به شکل های زیر تغییر کند:

  • وجود کران بالا و پایین برای متغیر x، به جای محدودیت غیر منفی بودن.
  • وجود کران بالا و پایین برای متغیر x، به عنوان یکی از محدودیت های اصلی
  • وجود چندین متغیر در مدل استاندارد بالا با امکان وقوع یا عدم وقوع دو حالت قبل

با فرض اینکه "x بار" نمایانگر مجموعه ای از متغیرها به صورت "x=(x1,x2,…,xn) بار" است آنگاه مدل بالا را می توان برای متغیرهای چندگانه به صورت زیر بازنویسی نمود:

ویژگی های اصلی مدل ریاضی را می توان به شرح زیر معرفی کرد:

  • مقدار منابع موجود، محدود بوده و این مقادیر اغلب در عبارت سمت راست محدودیت ها آورده می شوند.
  • منابع محدود، برای انجام فعالیت ها مورد استفاده قرار می گیرند و متغیرهای تصمیم مسئله عموماًٌ مقدار مصرف این منابع را در فعالیت خاص بیان می کنند.
  • راه های مختلفی جهت اختصاص منابع به فعالیت ها وجود دارد.
  • هر فعالیت با توجه به اینکه چه مقدار ازمنابع به آن اختصاص یافته خروجی مربوط به خود را دارد که مجموعه خروجی فعالیت ها تابع هدف را تشکیل می دهند.
  • نحوه تخصیص منابع به فعالیت ها باید تحت شرایط و با توجه به رعایت ملاحظاتی صورت گیرد که به عنوان محدودیت شناخته می شوند.

فرض کنید توابع در مدل بالا توابعی خطی هستند و به صورت زیر قابل نمایش هستند:

در محدودیت g1، a11 برابر است با مقدار موردنیاز از منبع gb1 جهت انجام یک واحد از فعالیت x1، a12 برابر است با مقدار موردنیاز از منبع gb1 جهت انجام یک واحد از فعالیت x2 و ... . در تابع هدف f، c1 برابر است با خروجی حاصل از انجام یک واحد از فعالیت x1، c2 برابر است با خروجی حاصل از انجام یک واحد از فعالیت x2 و ... . ciو ain به ترتیب با نام های ضرایب تابع هدف و ضرایب محدودیت شناخته می شوند. فرضیات عمومی برای فرموله کردن یک مدل ریاضی به شرح زیر است:

  • خروجی حاصل از تخصیص منابع به فعالیت های مختلف با معیار یکسان سنجیده می شوند (مثل دلار، ریال، کیلوگرم و ...) و قابل مقایسه با یکدیگرند.
  • منابع باید به اقتصادی ترین شیوه ممکن مورد استفاده قرار گیرند.
  • همه اطلاعات اعدادی قطعی هستند و بنابراین مسئله از نوع قطعی است.
  • متغیرهای تصمیم یا حقیقی هستند یا عدد صحیح و یا ترکیبی از این دو.
  • مدل ارائه شده مدلی عمومی می باشد و محدود به یک نوع خاص از مسئله نیست.

 پست مرتبط بعدی: مثالی ساده از مدل ریاضی برنامه ریزی خطی

پست مرتبط قبلی: مسائل بهینه سازی


 
 
مسائل بهینه سازی
نویسنده : محسن رحیمی - ساعت ۱۱:۱٤ ‎ق.ظ روز ۱۳٩٠/٤/۳
 

تابعی ریاضی را در نظر بگیرید که از تعدادی متغیر تشکیل شده است. اگر مسئله یافتن سطح متغیرها در نقطه یا نقاط ماکزیمم و یا مینیمم این تابع با در نظر گرفتن محدودیت هایی مشخص باشد، می توان آن را مسئله بهینه سازی نامید. بسیاری از مسائل دنیای واقعی و مسائل تئوری را می توان در این ساختار کلی مدل نمود.

به طور معمول از اصطلاح نقطه بهینه به جای عباراتی مانند نقطه ماکزیمم، مینیمم، بیشینه و یا کمینه استفاده می شود. در اصطلاح به تابعی که باید بهینه شود تابع هدف[1] می گویند. تابع هدف عموماً از ترکیب خطی یا غیرخطی چندین متغیر بوجود آمده است. البته تابع هدف می تواند تنها دارای یک متغیر باشد اما واضح است که اینگونه توابع از نقطه نظر بهینه سازی در گروه مسائل پیچیده و مشکل قرار نمی گیرند و می توان با روش های معمول مانند مشتق گیری نقطه مکزیمم یا مینیمم آنها را محاسبه نمود. برخی از مسائل بهینه سازی به دلایل مختلف ممکن است بیش از یک تابع هدف داشته باشند که به آنها مسائل بهینه سازی چند هدفه[2] می گویند.

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

توابع هدف و محدودیت ها ممکن است خطی یا غیر خطی باشند. همچنین با توجه به خصوصیات مسئله این توابع ممکن است دارای الگوهای مختلفی باشند برای مثال پیوسته یا نا پیوسته باشند، مشتق پذیر یا مشتق ناپذیر باشند، محدب یا نامحدب باشند، یک نمایی یا چند نمایی باشند. این ویژگی ها در پست های آینده تشریح خواهند شد.



[1] Objective function

[2] Multi-objective optimization problems

 

 پست مرتبط بعدی:

پست مرتبط قبلی: تاریخچه بهینه سازی


 
 
تاریخچه بهینه سازی
نویسنده : محسن رحیمی - ساعت ٥:۱٩ ‎ب.ظ روز ۱۳٩٠/٤/۱
 

برخی از تکنیک های بهینه سازی قدمتی بیش از یک قرن دارند. در ابتدا برای یافتن ماکزیمم و مینیمم یک تابع، از ریاضیات دیفرانسیلی استفاده می شد که در بسیاری از مسائل تجربی و تئوری کاربرد مناسبی نداشت. آغاز قرن بیستم را می توان آغاز توسعه استفاده از مدل های ریاضی و تکنیک های بهینه سازی دانست. در سال 1900 گانت[1] نمودار هایی را برای برنامه ریزی ساعت کار ماشین ها به صورت اثربخش استفاده نمود که امروزه به عنوان «گانت چارت[2]» شناخته می شود. در سال 1915 هریس[3] فرمول بندی ریاضی خاصی را برای محاسبه میزان اقتصادی سفارش قطعه از تامین کننده ارائه نمود که امروزه با اصطلاح «مقدار اقتصادی سفارش[4]» در مدیریت موجودی شناخته می شود و در سال 1917 ارلانگ، فرمولی ریاضی را برای تحلیل مسئله محاسبه تعداد تماس های وارده به یک تلفن خودکار استخراج نمود که توسعه آن منجر به محاسبات و تحلیل های مربوط به صف و در نهایت ایجاد موضوعی به نام تئوری صف گردد.

 

دولت بریتانیا در جنگ جهانی دوم تیمی از مهندسان عمران را جهت ارائه مشاوره به فرماندهان در حل مسائل پیچیده، استراتژیک و تاکتیکی تشکیل داد. هدف از این کار حداکثر نمودن قوای جنگی با استفاده از منابع محدود در دسترس بود. موفقیت گروه بریتانیایی باعث شد ایالت متحده آمریکا نیز گروهی مشابه را در 1942 تاسیس کند، اگرچه تشکیل گروه کوچکتری نیز در سال 1937 گزارش شده است. جامعه دانشمندان بریتانیا به مجموعه فعالیت های این تیم ها اصطلاح «تحقیق عملیاتی[5]» را اختصاص داد، در حالیکه در ایالت متحده از اصطلاح «تحقیق در عملیات[6]» استفاده شد. در پی موفقیت های فراوان فعالیت این تیم ها، موضوعی با نام «تحقیق در عملیات» به صورت مجزا در مجموعه عای آموزشی، دانشگاه ها و دانشکده ها معرفی گردید. لازم به ذکر است که بهینه سازی[7] به عنوان زیرمجموعه ای از علم تحقیق در عملیات مطرح است.

 پس از جنگ جهانی دوم،... (در ادامه مطلب)



[1] H.L. Gantt

[2] Gantt Chart

[3] F.W. Harris

[4] Economic Order Quantity

[5] Operational Research

[6] Operation Research

[7] Optimization

 

پست مرتبط بعدی:

پست مرتبط قبلی: رابطه مدلسازی و بهینه سازی


 
 
رابطه مدلسازی و بهینه سازی
نویسنده : محسن رحیمی - ساعت ٥:٢۱ ‎ب.ظ روز ۱۳٩٠/۳/۳۱
 

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

از آنجا که حل مسائل مدل شده به کمک ساده سازی و تخمین، پاسخ هایی ارائه می دهد که ممکن است تفاوت معنی داری با پاسخ های واقعی مسئله اصلی داشته باشند، ممکن است منجر به اتخاذ تصمیمات نادرست گردد. تصمیم گیرنده همیشه باید به این نکته توجه داشته باشد که مدلی که برای مسئله ساخته شده است تا چه حد با واقعیت همخوانی دارد. امکان وقوع این اشکال در بسیاری از تصمیم گیری های عملی و یا فرآیندهای طراحی وجود دارد. با نگاهی به بیشتر کتابهای نوشته شده در زمینه بهینه سازی و مدلسازی، مجلات علمی، مقالات و کنفرانس های بهینه سازی می توان دریافت که تلاش بسیار زیادی به ویژه در نیم قرن اخیر بر توسعه روش های مدلسازی و همچنین روشهای حل این مدل ها صورت گرفته است اما توجه زیادی به صحت و درستی مدلسازی و تکنیک های آن نشده است. در حقیقت مدلسازی ریاضی را می توان به عنوان یک هنر تصور نمود که همچنان جنبه های گوناگونی از آن کشف نشده مانده است.

 

پست مرتبط بعدی: تاریخچه بهینه سازی

پست مرتبط قبلی: مقدمه ای بر مدلسازی


 
 
مقدمه ای بر مدلسازی
نویسنده : محسن رحیمی - ساعت ۱۱:۳۳ ‎ب.ظ روز ۱۳٩٠/۳/٢٩
 

تعاریف و مباحث مختلفی در رابطه با تعریف و تشریح عبارت «مدل ریاضی» در کتب و مراجع مختلف عنوان شده است. اما به طور کلی می توان گفت به هر عبارت، رابطه یا ابزار ریاضی که برای کمک به حل مسائلی طراحی شده باشند که در آنها تصمیم گیرنده باید منابعی محدود را به طور بهینه به فعالیت های مختلف تخصیص دهد، مدل ریاضی می گویند. در پست های آینده به مشخصه ها و ویژگی های اساسی مسائلی که می توان بوسیله مدلسازی ریاضی حل نمود و همچنین به فرضیات لازم جهت شکل گیری و توسعه مدل های ریاضی اشاره خواهیم کرد. همچنین تعدادی از انواع مختلف مدل های ریاضی مانند برنامه ریزی خطی، برنامه ریزی عدد صحیح، برنامه ریزی آرمانی و برنامه ریزی غیر خطی را معرفی خواهیم کرد و به جزئیات بیشتری از این تکنیک ها اشاره می کنیم.

امروزه استفاده از مدل های ریاضی به ویژه برنامه ریزی خطی آنچنان معمول شده است که در هر شرکت یا مجموعه ای که مجهز به حتی یک کامپیوتر نیز باشد، می توانید نرم افزاری مربوط به بهینه سازی را بیابید. البته لازم به ذکر است این فراگیر بودن همیشه منشا خیر نبوده و گاهی موجب استفاده نادرست از تکنیک های مدلسازی شده است برای نمونه استفاده از نرم افزارهای طراحی شده جهت مدلسازی و حل مسائل خاص و ویژه برای حل مسئله نامرتبط باعث می شود تصمیم گیرنده با گزینه های غیر واقعی و نادرست روبه رو شود و البته در شرایط خاص وجود یک گزینه اشتباه در مجموعه گزینه های پیش روی تصمیم گیرنده می تواند بسیار گران تمام شود.

در پست بعدی موضوع مدلسازی به تشریح اجزای گوناگون یک مدل ریاضی می پردازیم و سپس به انواع مدل های ریاضی اشاره نموده و برای چند مسئله ساده، مدل ریاضی می نویسیم.

 

پست مرتبط بعدی: رابطه مدلسازی و بهینه سازی