Online User برنامه ریزی خطی - مدیریت صنعتی Industrial Management

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

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

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

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

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

(400 کلمه)

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

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


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

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

...


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

(550 کلمه)

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

مطلب مرتبط قبلی: سه ویژگی مهم جواب های گوشه ای موجه


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

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

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

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

فرمت: PDF

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

حجم: Mb 7.7 

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

 

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


 
 
سه ویژگی مهم جواب های گوشه ای موجه
نویسنده : محسن - ساعت ۸:٤٤ ‎ب.ظ روز ۱۳٩۱/۱/٢۳
 

در اینجا قصد داریم به معرفی سه ویژگی مهم و کلیدی جواب های گوشه ای موجه (جواب های CPF) بپردازیم که در هر مسئله برنامه ریزی خطی دارای فضای موجه کراندار صدق می کند...

  

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

(1000 کلمه)

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

مطلب مرتبط قبلی: جواب های گوشه ای موجه مجاور در فضای چند بعدی


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

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

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

(760 کلمه)

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

مطلب مرتبط قبلی: تفاوت روش نقاط داخلی و روش سیمپلکس


 
 
تفاوت روش نقاط داخلی و روش سیمپلکس
نویسنده : محسن - ساعت ۸:٠٠ ‎ب.ظ روز ۱۳٩٠/٩/۱٩
 

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

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

(670 کلمه)

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

مطلب مرتبط قبلی: روش نقاط داخلی


 
 
روش نقاط داخلی (Interior-point approach)
نویسنده : محسن - ساعت ٩:۳٦ ‎ب.ظ روز ۱۳٩٠/٩/٥
 

جالب‌ترین روشی که در دهه 1980 برای حل مسائل برنامه ریزی خطی ابداع شد روشی بود به نام روش نقاط داخلی (Interior-point approach) که توسط یک ریاضیدان جوان به نام نارندرا کارمارکار در آزمایشگاه AT&T Bell در سال 1984 معرفی شد. اگر چه این روش در ابتدا در مقایسه با روش سیمپلکس توجه‌ها را به خود جلب ننمود اما اصول و مفاهیم کلیدی به کار رفته در آن که در ادامه نیز به آن‌ها می‌پردازیم نشان می‌داد که این روش خاص پتانسیل حل مسائل برنامه ریزی خطی بسیار بزرگ را به گونه‌ای دارد که روش سیمپلکس به سختی آن‌ها را حل می‌کند.

 

 

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

(588 کلمه)

مطلب مرتبط بعدی: تفاوت روش نقاط داخلی و روش سیمپلکس

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


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

فرض تقسیم پذیری

فرض اساسی دیگری که در مدل برنامه ریزی خطی مطرح است، فرض تقسیم پذیری[1] است که به مقادیر قابل قبول متغیرهای تصمیم می پردازد:

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

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

فرض معین بودن

آخرین فرضی که باید برقرار گردد مربوط است به پارامترهای مدل که شامل ضریب تابع هدف، cj، ضرایب محدودیت های ساختاری، aij و مقادیر سمت راست محدودیت های ساختاری، bi است.این فرض اغلب به این صورت بیان می شود:

مقادیر اختصاص یافته به پارامترهای مدل برنامه ریزی خطی باید ثابت و معین باشند.

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

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

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



[1] Divisibility assumption

[2] integer programming models

[3] certainty assumption

[4] sensitivity analysis

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

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


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

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

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

برای توضیح بیشتر این فرض و پاسخ به این سوال که چرا باید در مدلسازی به این فرض توجه شود در ادامه مثال هایی ارائه شده است. جدول 1 مواردی از حالات ممکن تابع هدف مسئله شرکت ویندور را نشان می دهد. در همه موارد اگر تنها یک محصول تولید شود سود حاصل برای محصول اول 3x1 و برای محصول دوم 5x2 است. تفاوتهای این موارد در سطر آخر، که نشاندهنده Z است، زمانی بوجود می آید که بخواهیم هر دو محصول را با هم تولید کنیم. ستون جمع پذیری رضایت بخش موردی را نشان می دهد که مقدار تابع هدف Z=3x1+5x2، به سادگی با جمع دو سطر اول (3+5=8) بدست می آید. در مقابل دو ستون بعدی دو مورد فرضی را نشان می دهند که فرض جمع پذیری درباره آنها صدق نمی کند.

جدول 1. نمونه هایی از رعایت فرض جمع پذیری و عدم رعایت آن در تابع هدف

(x1,x2)

مقدار Z

جمع پذیری رضایتبخش

انحراف از جمع پذیری

مورد اول

مورد دوم

(1,0)

3

3

3

(0,1)

5

5

5

(1,1)

8

9

7

 ستون مربوط به مورد اول جدول 1 مربوط است به تابع هدفی به شکل Z=3x1+5x2+x1x2 به طوریکه برای (x1,x2)=(1,1) داریم Z=3+5+1=9 و در نتیجه از فرض جمع پذیری انحراف دارد. از آنجا که همه متغیرها دارای توان یک هستند فرض تناسب در این تابع رعایت شده است. این مورد زمانی پیش می آید که برای مثال دو کالا از لحاظ اقتصادی مکمل یکدیگر باشند و سود را افزایش دهند. برای مثال فرض کنید تبلیغات برای یکی از کالاها منجر شود که به طور موثری هر دو کالا فروش روند. از آن جهت که هزینه های تبلیغاتی برای یکی از کالا ها حذف شده است، در نتیجه سود کل حاصل از فروش هر دو کالا بیشتر از مجموع سود حالاتی است که محصولات یک و دو به تنهایی تولید شوند.

ستون مربوط به مورد دوم جدول 1 نیز مربوط است به تابع هدفی به شکل Z=3x1+5x2-x1x2 به طوریکه برای (x1,x2)=(1,1) داریم Z=3+5-1=7 و در نتیجه از فرض جمع پذیری انحراف دارد. برعکس مورد اول، این مورد زمانی پیش می آید که برای مثال دو کالا حالت رقابتی داشته باشند و سود حاصل از تولید هردو محصول کمتر از مجموع سود حالاتی است که محصولات یک و دو به تنهایی تولید شوند. برای مثال فرض کنید هر دو محصول برای تولید احتیاج به یکی از تجهیزات کارخانه داشته باشند. اگر تصمیم گرفته شود تنها یکی از محصولات تولید شود، این ماشین تمام وقت در اختیار تولید محصول مورد نظر خواهد بود. اما در صورتی که تصمیم گرفته شود هر دو محصول تولید شوند این ماشین باید در ساعاتی از روز به تولید محصول اول و در ساعاتی از روز به تولید محصول دوم بپردازد و این کار مستلزم از دست رفتن زمان و همچنین صرف هزینه های خاموش کردن و راه اندازی مجدد آن است. به دلیل وجود این هزینه های اضافی، سود حاصل از تولید هر دو محصول کمتر از مجموع سود حالاتی است که محصولات یک و دو به تنهایی تولید شوند که احتیاج به صرف هزینه های خاموش کردن و راه اندازی مجدد ندارند.

در توابع محدودیت نیز حالات مشابهی از تعامل بین متغیرها می تواند منجر به انحراف از فرض جمع پذیری گردد. برای مثال، محدودیت ساختاری سوم مسئله شرکت ویندور، 3x1+2x2<=18، را در نظر بگیرید. این محدودیت تنها محدودیتی در مسئله است که هر دو متغیر را شامل می شود. این محدودیت مربوط است به محدودیت ظرفیت زمانی کارخانه سوم که بیشتر از 18 ساعت در هفته نمی تواند در فرآیند تولید شرکت کند و عبارت سمت راست این محدودیت، 3x1+2x2، نشان می دهد که برای تولید یک دسته در هفته از هر محصول به چه مقدار زمان نیاز است. ستون جمع پذیری رضایتبخش در جدول 2 حالت بالا را نشان می دهد و دو ستون بعدی مواردی را نشان میدهند که در تابع محدودیت آنها عبارات ضربی به کار رفته است و در نتیجه فرض جمع پذیری در رابطه با آنها صدق نمی کند. برای هر سه ستون سهم مجزای هر محصول از ظرفیت زمانی کارخانه سوم همانند آنچه در جدول 1 آمده است ارائه شده است، یعنی برای محصول اول 3x1 و برای محصول دوم 2x2 و یا 3(2)=6 به ازای x1=2 و 2(3)=6 به ازای x2=3. همچنین همانند جدول 1 اعدادی که در سطر آخر ارائه شده است مربوط است به مقدار کل تابع محدودیت زمانی که هر دو محصول با هم تولید شوند.

جدول 2. نمونه هایی از رعایت فرض جمع پذیری و عدم رعایت آن در محدودیت ها

(x1,x2)

مقدار منبع استفاده شده

جمع پذیری رضایتبخش

انحراف از جمع پذیری

مورد سوم

مورد چهارم

(2,0)

6

6

6

(0,3)

6

6

6

(2,3)

12

15

8/10

 ستون مربوط به مورد سوم جدول 2 مربوط است به محدودیتی به شکل 3x1+2x2+0.5x1x2 به طوریکه برای (x1,x2)=(2,3) داریم 6+6+3=15 و در نتیجه از فرض جمع پذیری 6+6=12 انحراف دارد. این حالت دقیقاً مانند مورد دوم جدول 1 زمانی پیش می آید که باید زمانی را صرف خاموش کردن و دوباره راه اندازی کردن دستگاهی نمود تا بتوان هر دو محصول را تولید کرد. عبارت ضربی حاضر در تابع محدودیت، (0.5x1x2)، بیانگر میزان زمان هدر رفته در این فرآیند است. دقت داشته باشید که زمان هدر رفته به دلیل تغییر محصول با علامت مثبت در تابع محدودیت آورده شده است زیرا مقدار این تابع، زمان تولید است در حالیکه در مورد دوم جدول 1  عبارت ضربی با علامت منفی در تابع هدف ظاهر می شود چون این تابع سود را اندازه گیری می کند.

ستون مربوط به مورد چهارم جدول 2 مربوط است به محدودیتی به شکل 3x1+2x2-0.1x12x2 به طوریکه برای (x1,x2)=(2,3) داریم 6+6-1.2=10.8 و در نتیجه از فرض جمع پذیری 6+6=12 انحراف دارد. این مورد نیز در مواردی مشابه مورد سوم بروز می کند فرض کنید هر دو محصول برای تولید به به یکی از تجهیزات کارخانه نیازمند باشند ولی زمان لازم برای تغییر کاربری دستگاه ناچیز باشد. از آن جهت که هر محصول برای تولید از رشته ای از تجهیزات عبور می کند، زمان هایی وجود خواهد داشت که یک دستگاه تولیدی بلا استفاده باشد. بنابراین می توان از این زمان های به اصطلاح مرده برای تولید محصول دیگر استفاده نمود. در نتیجه کل زمان تولید مورد استفاده برای تولید دو محصول کمتر از مجموع زمان لازم برای تولید دو محصول در حالتی است که تنها تولید شوند.

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

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


[1] Additivity assumption

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

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


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

 این پروژه تحقیقی, با نام «برنامه ریزی خطی فازی» در فرمت PDF به حجم 225 KB و در 14 صفحه با فهرست زیر تنظیم شده است:

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

 برای نمونه صفحه شماره 8 این پروژه در عکس زیر ارائه شده است.

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


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

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

فرض تناسب

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

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

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

برای تشریح بیشتر فرض تناسب، عبارت اول (3x1) تابع هدف مسئله شرکت ویندور (Z=3x1+5x2) را در نظر بگیرید. این عبارت بیانگر سود حاصل شده در هفته (به هزار دلار) در اثر تولید محصول جدید اول با نرخ تولید x1 در هفته است. در ستون تناسب رضایت بخش جدول 1 مورد ارائه شده در مسئله شرکت ویندور آورده شده است که در آن سود کاملاً با x1 متناسب است. سه ستون بعدی نیز نتایج حاصل از سه مورد فرضی آورده شده است که فرض تناسب در آنها رعایت نشده است.

جدول 1. نمونه هایی از رعایت فرض تناسب و عدم رعایت آن

تناسب رضایتبخش

مثال هایی از عدم رعایت فرض تناسب

مورد اول

مورد دوم

مورد سوم

0

0

0

0

0

1

3

2

3

3

2

6

5

7

5

3

9

8

12

6

4

12

11

18

6

ستون مربوط به مورد اول را در جدول 1 در نظر بگیرید. این مورد می تواند زمانی پیش بیاید که برای تولید محصول اول نیاز به صرف هزینه های راه اندازی باشد، برای مثال اگر برای تنظیم تجهیزات و دستگاه ها برای شروع کار تولید لازم باشد هزینه ای صرف شود و یا اگر لازم باشد برای توزیع محصول مراکز توزیع جدید ایجاد شود. از آنجا که تنها برای یک بار این هزینه ها پرداخت می شوند، برای وارد کردن آنها در تابع هدف، واحد هزینه های راه اندازی باید بر پایه هزینه بر هفته تغییر یابند تا قابل اضافه شدن در تابع هدف Z که سود بر هفته است باشند. فرض کنید این تغییر واحد صورت گرفته باشد و کل هزینه راه اندازی که باید از کاسته شود معادل عدد یک محاسبه شده باشد. به این ترتیب سهم تولید محصول اول در تابع هدف Z، باید به صورت 3x1-1 برای x1>0 باشد و برای زمانی که محصول یک تولید نشود یعنی x1=0، این سهم به صورت 3x1=0 باید محاسبه شود. این تابع سود که در شکل 1 رسم شده است مشخصاً با x1 متناسب نیست و در نتیجه فرض تناسب در مورد آن رعایت نشده است. اگر سهم محصول اول در Z به ازای همه x1>=0 برابر بود با 3x1-1 آنگاه می توانستیم عدد ثابت، -1، را از تابع هدف حذف کنیم بدون اینکه تغییری در جواب بهینه حاصل شود و همچنین فرض تناسب نیز رعایت شده است. اما از آنجا که برای x1=0 شرط بالا صحیح نیست در نتیجه نمی توان از این تکنیک استفاده نمود.

شکل 1. ترسیم مثال مورد اول انحراف از فرض تناسب در جدول 1

مورد دوم جدول 1 نیز شباهت زیادی با مورد اول دارد، با این حال این مورد در شرایط کاملاً متفاوت ظهور می کند. در این مورد هیچ هزینه راه اندازی وجود ندارد و سود حاصل از تولید اولین دسته از محصول برابر است با 3 (هزار دلار) است که با مثال دارای فرض تناسب یکسان است. با این حال در این مورد افزایش نرخ سود وجود دارد به این معنا که شیب تابع سود محصول یک (در شکل 2 ببینید) با افزایش x1 افزایش می یابد. این نوع انحراف از فرض تناسب ممکن است در اثر صرفه جویی در مقیاس حاصل شود که گاهی در سطوح بالای تولید ایجاد می شود. صرفه جویی در مقیاس در اثر مواردی مانند استفاده از اتوماسیون و تجهیزات حجم بالای با کیفیت، خرید ارزان تر حجم زیادی از مواد اولیه و یا اثر منحنی یادگیری نیروی کار که باعث می شود نیروی کار در اثر تجربه بیشتر اثربخشی و کارایی بالاتری داشته باشند، ایجاد می شود. به عبارت دیگر در هر شرایطی که با افزایش تولید، نرخ رشد هزینه ها کاهش یابد و قیمت فروش کالا ثابت بماند، نرخ رشد سود افزایش می یابد و می تواند مثالی از مورد دوم جدول 1 باشد.

شکل 2. ترسیم مثال مورد دوم انحراف از فرض تناسب در جدول 1

با بررسی مجدد جدول 1 مشاهده می شود که مورد سوم تقریباً حالت عکس مورد دوم است به این معنا که در آن کاهش رشد نرخ سود وجود دارد. در این مورد شیب تابع سود محصول اول (همانطور که در شکل 3 مشاهده می کنید، با افزایش x1 کاهش می یابد. این انحراف از فرض تناسب می تواند به علت وجود هزینه های تبلیغاتی باشد؛ یعنی شرایط بازار به گونه ای باشد که برای فروش کالای بیشتر باید هزینه های تبلیغاتی را افزایش داد. برای مثال مانند مورد سوم ممکن است فروش محصول اول با نرخ تولید یک دسته در هفته (x1=1)، بدون نیاز به هزینه تبلیغاتی انجام شود، در حالیکه برای فروش این کالا با نرخ تولید 2 دسته در هفته (x1=2)، احتیاج به صرف هزینه های تبلیغاتی باشد و به همین ترتیب برایx1=3 هزینه های بسیار بالای تبلیغاتی لازم باشد و برای x1=4 هزینه ها به حدی افزایش یافته باشند که سود را کاهش دهند.

شکل 3. ترسیم مثال مورد سوم انحراف از فرض تناسب در جدول 1

 

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

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

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

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


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

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



[1] Technological Coefficient

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

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


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

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

جواب موجه جوابی است که در همه محدودیت ها صدق کند و جواب غیرموجه جوابی است که حداقل از یکی از محدودیت ها انجراف داشته باشد و در آن صدق نکند. برای نمونه نقاط (2,3) و (4,1) در شکل 4 جواب های موجه هستند در حالیکه نقاط (-1,3) و (4,4) جواب های غیر موجه هستند. مجموعه همه جواب های موجه را فضای موجه می نامند. در شکل 4 منطقه هاشور خورده معادل فضای موجه است.

ممکن است مسئله ای دارای جواب موجه نباشد. در مثال شرکت ویندور اگر محدویت جدیدی با این عنوان اضافه کنیم که سود حاصل از محصولات جدید باید حداقل 50000 دلار در هفته باشد، رابطه جدیدی به صورت 3x1+5x2>=50 به مدل اضافه میگردد که در صورت رسم آن فضای موجه از بین می رود. به این معنی که هیچ ترکیبی از محصولات جدید نمی تواند در همه محدودیت ها صدق کند. این حالت در شکل 1 قابل مشاهده است.

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

 در صورتی که مسئله دارای فضای موجه باشد، هدف یافتن بهترین جواب موجه است به طوریکه مقدار تابع هدف را به بهترین سطح در جهت مطلوب (ماکزیمم یا مینیمم) برساند. جواب بهینه یکی از جواب های موجه است که مطلوب ترین مقدار ممکن برای تابع هدف را ایجاد کند. مطلوب ترین مقدار ممکن عبارت است از بزرگترین مقدار در صورتی که مسئله ماکزیمم نمودن تابع هدف باشد و کمترین مقدار، اگر مسئله مینیمم نمودن تابع هدف باشد. بسیاری از مسائل تنها دارای یک جواب بهینه هستند ولی ممکن است مسئله ای دارای بیش از یک تابع هدف باشد. برای مثال اگر در مسئله شرکت ویندور سود حاصل از تولید یک دسته از محصول دوم به مقدار 2000 دلار تغییر یابد، تابع هدف نیز به شکل Z=3x1+2x2 تغییر خواهد کرد و بنابراین همه نقاطی که روی پارهخط بین (2,6) و (4,3) هستند جواب بهینه خواهند بود. این حالت را در شکل 2 می توانید ببینید. در اینگونه مسائل تعداد جواب های بهینه بینهایت است که مقادیر تابع هدف حاصل از آنها با هم برابر هستند و در اصطلاح می گویند مسئله دارای جواب بهینه چندگانه است.

شکل 2. وجود چندین جواب بهینه با تغییر تابع هدف مسئله شرکت ویندور

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

 

شکل 3. مسئله شرکت ویندور بدون دو محدودیت ساختاری آخر و دارای Z بیکران

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

شکل 4. پنج نقطه مشخص شده جواب های CPF مسئله شرکت ویندور هستند.

 در ادامه درباره رابطه بین جواب بهینه و جواب CPF توضیح مختصری می دهیم. یک مسئله برنامه ریزی خطی را که دارای جوای های موجه و فضای موجه کراندار است را در نظر بگیرید. این مسئله لزوماً دارای چند جواب CPF و حداقل یک جواب بهینه است. در فصل های آینده ثابت خواهیم کرد که بهترین جواب CPF حتماً یکی از جواب های بهینه این مسئله است. بنابراین اگر مسئله تنها دارای یک جواب بهینه باشد، آن جواب همان بهترین جواب CPF است و اگر جزء مسائل دارای جواب بهینه چندگانه باشد، حداقل دو جواب CPF در بین جواب های بهینه وجود دارد. در مسئله شرکت ویندور تنها یک جواب بهینه، (2,6)، وجود دارد که با مشاهده شکل 4 مشخص می شود که این نقطه یکی از جواب های CPF است. در صورتی که شکل تغییر یافته این مسئله که دارای جواب بهینه چندگانه است را در نظر بگیریم که در شکل 2 نشان داده شده است، مشخص می شود که دو تا از جواب های بهینه (2,6) و (4,3) جواب CPF هستند.

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

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


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

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

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

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


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

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

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

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

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

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


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

حال که به کمک مسئله شرکت ویندور آشنایی اولیه ای با برنامه ریزی خطی و مدل آن بدست آمد، می توانیم مدلی ریاضی برای شکل عمومی مسئله تخصیص منابع به فعالیت ها بسازیم. این مسئله به دنبال یافتن مقادیر مناسب برای x1,x2,…xn است به طوریکه تابع Z ماکزیمم گردد، یعنی:

و همچنین محدودیت های زیر نیز رعایت شود:

و

به این شکل از مدل نویسی قالب استاندارد می گویند. این شکل مدل نویسی در این وبلاگ و در بسیاری از کتاب های تحقیق در عملیات به این نام شناخته می شود البته ممکن است در مراجعی به شکل های دیگری نام قالب استاندارد داده شده باشد. به هر حال به هر مسئله ای که بتوان مدل ریاضی آن را به شکل بالا نوشت، می توان مسئله برنامه ریزی خطی گفت. برای مثال مدل مسئله شرکت ویندور منطبق بر قالب استاندارد است و در آن m = 3 و n = 2 است.

تابعی را که باید ماکزیمم شود، تابع هدف می نامند. قید های ذکر شده در مدل را نیز محدودیت می گویند. m محدودیت اول را ، محدودیتهای تابعی یا محدودیتهای ساختاری می گویند. همچنین به محدودیت های xj>=0، محدودیت های غیر منفی یا شرط غیر منفی بودن می گویند.

قالب های دیگر

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

  • تابع هدف به جای ماکزیمم شدن باید مینیمم گردد:

  • برخی از محدودیتهای تابعی از نوع نامعادلات بزرگتر مساوی هستند:برای تعدادی از iها
  • برخی از محدودیتهای تابعی از نوع معادله هستند:برای تعدادی از iها
  • برای برخی از متغیرهای تصمیم شرط غیر منفی بودن وجود ندارد و در اصطلاح می نویسند:

    برای تعدادی از jها xj آزاد در علامت

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

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

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


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

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

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

اصطلاحات رایج در برنامه ریزی خطی

مسئله شرکت ویندور

مسئله عمومی

ظرفیت تولید کارخانه ها

3 کارخانه

منابع

m منبع

تولید محصولات

2 محصول

نرخ تولید محصول jام، xj

فعالیت ها

n فعالیت

سطح انجام فعالیت jام، xj

سود Z

معیار ارزیابی عملکرد کل سیستم Z

 

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

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

مقدار معیار ارزیابی عملکرد کل سیستم

Z =   

سطح فعالیت jام (برای j = 1,2,…,n)

xj =   

مقدار افزایش Z در اثر افزایش یک واحدی سطح فعالیتj ام

cj =   

مقدار موجود از منبع ام (برای i = 1,2, …, m)

bi =   

مقداری که از منبع Z که برای انجام هر واحد از فعالیتj ام مصرف می شود.

aij =  

از آنجا که هدف برنامه ریزی خطی کمک به تصمیم گیری در مورد انتخاب سطح انجام فعالیت ها است، لذا به x1,x2,…,xn در اصطلاح متغیرهای تصمیم[1] می­گویند. طبق جدول مقادیر cj، bj و aij (برای i=1,2,…,m و j = 1,2,…,n) داده های ثابت مدل هستند که در اصطلاح به آنها پارامترهای مدل می گویند.



[1]  decision variables

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

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


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

مفهوم اساسی بهینه سازی یافتن بهترین پاسخ ممکن برای یک مسئله یا مدل مشخص است که این بهترین پاسخ می تواند یک نقطه در صفحه مختصات باشد و هم می تواند یک گزینه از میان چندین مورد باشد. برای این کار، باید همه حالت های ممکن را بررسی نمود و ثابت کرد که جواب انتخاب شده بهترین است. در مسئله ارائه شده در پست قبلی، هدف یافتن مقدار 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 نقطه بهینه عددی مثبت است. یعنی برای یافتن جواب بهینه باید به دنبال نقطه ای بگردیم که گرادیان تابع در آن نقطه برابر با صفر باشد.

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

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


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

شرکت تولید شیشه ویندور، محصولات شیشه ای مانند در و پنجره شیشه ای تولید می کند. این شرکت سه کارخانه دارد. درکارخانه اول قاب و چارچوب آلومینیومی تولید می شود، کارخانه دوم قاب چوبی تولید می کند و درکارخانه سوم شیشه تولید و محصول نهایی مونتاژ می گردد.

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

محصول جدید اول: در شیشه ای 8 فوت با چارچوب آلومینیومی

محصول جدید دوم: پنجره 4 در 6 فوت با قاب چوبی

محصول اول برای تولید به بخشی از ظرفیت تولید کارخانه 1 و 3 نیاز دارد و به تجهیزات کارخانه 2 احتیاجی ندارد. محصول دوم نیز تنها به کارخانه های 2 و 3 نیاز دارد. گزارش های بازاریابی نشان می دهند، هر تعداد که شرکت بتواند از این دو محصول تولید کند، در بازار به فروش خواهد رسید. با این حال، چون هر دو محصول جدید برای تولید به ظرفیت کارخانه سوم نیاز دارند، مشخص نیست چه تر کیبی از این دو محصول تولید شود تا سود بیشتری حاصل گردد. برای پاسخگویی به این سوال، شرکت یک تیم OR تشکیل داده است.

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

«تعیین کنید چه نرخی از دو محصول جدید باید تولید شوند تا سود کل شرکت ماکزیمم گردد و در عین حال محدودیت های مربوط به ظرفیت تولید هر سه کارخانه نیز در نظر گرفته شود. هر محصول در دسته های 20 تایی تولید می شود، در نتیجه نرخ تولید به صورت تعداد دسته های تولیدی در هر هفته تعریف می شود. همچنین هر ترکیبی از نرخ تولید دو محصول که در محدودیتها صدق کند قابل قبول است و از این نظر محدودیتی وجود ندارد؛ حتی اگر از یک محصول اصلاً تولید نشود و کل ظرفیت به تولید محصول دیگر اختصاص یابد.»

حل این مسئله و تفسیرهای آن در فایل پیوست قابل دانلود است.

دانلود:          PDF - 8 pages - 857Kb

 

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

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


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

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

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

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

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

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

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

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

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


 
 
مقدمه ای بر برنامه ریزی خطی (Linear Programming)
نویسنده : محسن - ساعت ۳:۳۱ ‎ب.ظ روز ۱۳٩٠/٤/٧
 

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

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

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

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


[1] Linear Programming

[2] Simplex

 

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

پست مرتبط قبلی: اثرات تحقیق در عملیات


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

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

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 به ترتیب با نام های ضرایب تابع هدف و ضرایب محدودیت شناخته می شوند. فرضیات عمومی برای فرموله کردن یک مدل ریاضی به شرح زیر است:

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

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

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