برنامه ریزی جزئی اساسی از مدیریت در سازمان می باشد ، اما پیش از آن تصمیم گیری درباره چگونگی ترکیب و عملکرد و مشخص کردن اهداف پیش شرطی برای برنامه ریزی در سازمان می باشد . از این جهت یکی از مسائل مهمی که در سازمان باید مورد نوجه مدیران قرار گرفته و در آینده به عنوان یکی از روش های اصلی برای تصمیم گیری مدیران از آن استفاده شود مدل سازی ریاضی از طریق فنون تحقیق در عملیات (Operational Research ) است . این روش در واقع از طریق طراحی مدل های ریاضی که به سه صورت احتمالی ، قطعی و یا می باشد این امکان را برای مدیر فراهم می آورند تا با استفاده از این روش علاوه بر تصمیم گیری صحیح در زمان تصمیم گیری با توجه به محدودیت های منابع و با هدف حداکثر کردن سود یا حداقل کردن هزینه یکی از بهترین روش ها برای تخصیص آسان منابع در زمینه های نیروی انسانی و حمل و نقل را فراهم می آورد . را در هر زمان برای سازمان اتخاذ نماید . از ویژگی های این روش نگرش سیستمی به مسائل و بررسی چند رشته ای و بین رشته ای از طریق مدل های ریاضی است . همچنین با توجه به اینکه علم کامپیوتر امروز می تواند کمک موثری در سرعت و دقت تصمیمات مدیریتی ایجاد کند ، برخی کمپانی ها در این زمینه نرم افزار هایی را تولید کرده اند که از مهمترین آنها می توان به نرم افزار های Matlab , QSB , Lindo , Lingo ,DS , Tora , Gaps و ... اشاره نمود . در اینجا به برخی از مفاهیم و بنیان های ریاضی این فن جهت اشنایی بیشتر اشاره می نماییم .
مفهوم برنامه ریزی خطی :
رده ای یا دسته ای از مدل های برنامه ریزی ریاضی است که مربوط می شود به مناسب ترین ترکیب از منابع محدود به فعالیت های معلوم به منظور دست یابی به هدفی مطلوب . مانند ماکزیمم کردن سود یا مینیمم کردن هزینه .خصوصیت بارز برنامه ریزی خطی این است که در آنها برنامه معرف هدف برنامه ریزی یا محدودیت ها و یا و یا قید و منابع خطی بوده و متغیر ها نیز مجهول هستند . هر تصمیم گیرنده منابعی از قبیل سرمایه یا پول ، نیروی انسانی یا کار ، مواد خام اولیه یا منابع طبیعی ماشین آلات و تجهیزات و تکنولوژی اطلاعات و مدیریت در اختیار دارد کههمگی از لحاظ کمیت و کیفیت محدود می باشند .
ویژگی های برنامه ریزی خطی :
1- مشخص بودن تابع هدف به صورت خطی
2- موجود بودن راه حل های مختلف در برنامه ریزی
3- مشخص بودن محدودیت های منابع به صورت معادلات یا نامعادلات خطی
4- موجود بودن روابط ریاضی بین متغیر ها
5- غیر منفی بودن متغیر ها
مدل عمومی
Max یا Min z = c1x1 + c2x2 + … + cjxj + … + cnxn تابع هدف
به شرطی که :
A11x1+a12x2…+a1jxj+…+ a1nxn =< b1
A21x1+a22x2…+a2jxj+…+ a2nxn =< b2
Ai1x1+ai2x2…+aijxj+…+ ainxn =< b1i
Am1x1+am2x2…+amjxj+…+ amnxn =< bm
مدل سازی
برای استفاده از روش برنامه ریزی خطی می بایست ، مدل مورد نیاز برای بهینه سازی بر اساس هدف طراحی نمود . در اینجا نمونه کوچکی از مدل سازی را برررسی می کنیم .
مثال : یک کارخانه صنایع چوبی دو نوع محصول (میز و صندلی ) تولید می کند برای تولید هر واحد میز و صندلی تصور نمایید به دو نوع مواد اولیه (چوب بلوط و چوب کاج ) و میزان متفاوتی از نیروی انسانی نیاز است . برای تولید هر واحد میز به 5 فوت چوب بلوط و 2 فوت چوب کاج و 2 نفر ساعت نیروی انسانی نیاز است . میزان منابع نیروی انسانی کارخانه در طول هفته 80 نفر ساعت است و ضمناً از چوب بلوط و کاج به ترتیب 150 واحد و 100 واحد در اختیار است . مدیریت کارخانه می خواهد بداند چه تعداد میز و چه تعداد صندلی تولید نماید تا سود او حداکثر شود . با توجه به اینکه سود حاصل از فروش هر میز و صندلی به ترتیب معادل 12 و 8 واحد پول قرار دادی است . مطلوب است فقط مدل سازی مسئله .
سود آوری حاصل از فروش نیروی انسانی چوب کاج چوب بلوط
12 4 2 5 X1 میز
8 2 3 2 X2 صندلی
Maxz = 12X1 + 8 X2
S.t : 5X1 + 2X2 =<150
2X1 + 3X2 =<100
4X1 + 2X2 =< 80
X1, X2 =>
حل مسائل برنامه ریزی خطی :
روش اصلی در حل مسائل برنامه ریزی خطی ، روش سیمپلکس می باشد . در این روش ابتدا به بررسی فرم مدل طراحی شده می پردازیم . درصورتی که مدل از فرم استاندارد پیروی کند . آن را به روش سیمپلکس ساده حل می نماییم و درصورتی که مدل از فرم غیر استاندارد پیروی کند می توان از روش های سیمپلکس M بزرگ یا از روش دو فازی و یا از روش تجدید نظر شده استفاده نمود .روش جدید برای حل مسائل برنامه ریزی خطی (LP)
مسايل ماكزيمم سازي كسري خطي ، پژوهش و علاقه قابل ملاحظه اي را به خود اختصاص داده اند ، زيرا آنها در برنامه ريزي توليد ، برنامه ريزي مشاركتي ومالي ، برنامه ريزي بيمارستاني و مراقبت از سلامت مفيد مي با شند.
چند روش براي حل اين مسأله در سال 1962 پيشنهاد شد.
چارنز و كوپر روششان را كه تبديل اين
به يك برنامه خطي معادل بستگي داشت ، پيشنهاد دادند.
روش ديگري كه روش تابع هدف -- ناميده مي شود توسط بيت ران و نوواييز در سال 1973 كشف شد ، كه در آن حل اين مسأله كسري خطي بوسيله حل يك دنباله از برنامه هاي خطي فقط با محاسبه مجدد جدول محلي تابع هدف صورت مي پذيرد.
همچنين بعضي از جنبه هاي ارتباط دوگان و تحليل حساسيت در مسأله كسري خطي توسط بيت ران و مگنانت در سال 1976 به بحث گذاشته شد.
ساي نيز در سال 1981 در مقاله اش يك مطاله مفيد در مورد شرط بهينگي در برنامه ريزي كسري ارايه كرد.
2. تعاريف و نكات :
مسأله مربوط زماني بوجود مي آيد كه يك تابع كسري خطي بايد روي يك چند وجهي-ماكزيمم شود.
اين مسأله مي تواند به شكل رياضي به صورت زير فرمولبندي شود و با
نشان داده مي شود: (LFP)
: كه
C,d , b
اسكالر هستند.
متذكر مي شويم كه شرايط نامنفي در مجموعه محدوديت ها قرار مي گيرند.
:امين سطر ماتريس j
فرض مي شود كه مجموعه جواب شدني – يك مجموعه فشرده است يعني بسته و
كراندار مي باشد. علاوه بر اين
هرجا در --
اين مسأله مي تواند به شكل زير فرمولبندي شود:
دراينجا
امين سطر ماتريس – است كه در تباهيدگي بايد مورد توجه قرار گيرد. i
يك نقطه رأسي ازناحيه شدني – در بعضي از مجموعه هاي مستقل – خطي – قرار
مي گيرد .در(2.2) ما فرض خواهيم كرد كه
(*)
پس يك شكل معادل براي (2.2) مي تواند به صورت زير فرمولبندي شود:
(2.3)
اگر ما تعريف كنيم:
سپس (2.3 ) مي تواندبفرم زير نوشته شود:
كه:
در تعريف بالاي – مي توانيم به
برسيم.
با ضرب مجموعه محدوديت هاي اين مسأله دوگان بوسيله –كه
ما داريم:
در اين مورد موقعي كه
ماتريس – از درايه ها ي نا منفي تعريف مي شود بطوريكه
.اين ماتريس يك نقش مهم براي يافتن مقدار بهينه مسأله ماكزيمم
مقدار – روي بازه اعداد حقيقي كه بوسيله
تعريف مي شود
بطور ساده نمايش بالا مي تواند به شكل
نوشته شود.
همچنين يك زير ماتريس – از ماتريس داده شده – كه در
صدق مي كند براي تعيين مقدار دوگان مورد نياز براي حل
برنامه ريزي كسري (2.1) مهم خواهد بود.
اين مقادير دوگان براي يك نقطه – كه يك جواب بهينه مسأله بالا (2.5) است
به خوبي در شرايط 2و3 كان-تاكر صدق مي كنند. ما بايد داشته باشيم :
يا به طور ساده:
در اينجا – يك زير ماتريس ، ماتريس داده شده – فقط شامل ضرايب مجموعه محدوديت ها ي فعال در نقطه كنوني – است. همچنين از قضيه مكمل زايد داريم :
برا ي هر مجموعه بالااز محدوديت هاي فعال مقادير دوگان متناظر بايد مثبت باشند.ازاين رو يك زير ماتريس – از ماتريس – داده شده كه در
صدق مي كند براي يافتن مقادير دوگان مورد نياز براي تعيين
مجموعه محدوديت هاي فعال متناظر با مقادير دوگان مثبت بخاطر قضيه
مكمل زايد براي مجموعه بالا از محدوديت هاي فعال اهميت خواهد داشت.
روشمان را براي حل مسايل ( )بصورت زير خلاصه مي كنيم:
را محاسبه مي كنيم.
2- ماتريس – از درايه هاي نامنفي را كه – است پيدا مي كنيم.
3- يك زير ماتريس – از ماتريس داده شده – كه در –صادق باشد ر ا پيدا مي كنيم.
4-در سطر هاي – براي هر درايه مثبت محدوديت فعال متناظر در ماتريس- را تعيين مي كنيم.
5-يك دستگاه – از معادلات خطي را براي رسيدن به جواب بهينه – حل مي كنيم.بنابراين با استفاده از (2.6) به جواب بهينه مسأله () كه بوسيله (2.1)
تعريف مي شود مي رسيم.
3.نكته ها:
نكته(3.1):
ماتريس – از درايه هاي نامنفي كه – رابه عنوان ماتريس قطبي ، ماتريس – در نظر مي گيريم.
نكته(3.2):
با – در () مسأله بالا به يك مسأله برنامه ريزي خطي () تقليل مي يابد و از اين رو روشمان ميتواند براي حل – به عنوان حالت خاصي از – به استفاده از بحثي مشابه مورد استفاده قرار بگيرد.
4.به مثال زير توجه كنيد:
مسأله دوگان فعالند. محدوديت هاي 1 و 3
چارنز و كوپر روششان را كه تبديل اين
به يك برنامه خطي معادل بستگي داشت ، پيشنهاد دادند.
روش ديگري كه روش تابع هدف -- ناميده مي شود توسط بيت ران و نوواييز در سال 1973 كشف شد ، كه در آن حل اين مسأله كسري خطي بوسيله حل يك دنباله از برنامه هاي خطي فقط با محاسبه مجدد جدول محلي تابع هدف صورت مي پذيرد.
همچنين بعضي از جنبه هاي ارتباط دوگان و تحليل حساسيت در مسأله كسري خطي توسط بيت ران و مگنانت در سال 1976 به بحث گذاشته شد.
ساي نيز در سال 1981 در مقاله اش يك مطاله مفيد در مورد شرط بهينگي در برنامه ريزي كسري ارايه كرد.
2. تعاريف و نكات :
مسأله مربوط زماني بوجود مي آيد كه يك تابع كسري خطي بايد روي يك چند وجهي-ماكزيمم شود.
اين مسأله مي تواند به شكل رياضي به صورت زير فرمولبندي شود و با
نشان داده مي شود: (LFP)
: كه
C,d , b
اسكالر هستند.
متذكر مي شويم كه شرايط نامنفي در مجموعه محدوديت ها قرار مي گيرند.
:امين سطر ماتريس j
فرض مي شود كه مجموعه جواب شدني – يك مجموعه فشرده است يعني بسته و
كراندار مي باشد. علاوه بر اين
هرجا در --
اين مسأله مي تواند به شكل زير فرمولبندي شود:
دراينجا
امين سطر ماتريس – است كه در تباهيدگي بايد مورد توجه قرار گيرد. i
يك نقطه رأسي ازناحيه شدني – در بعضي از مجموعه هاي مستقل – خطي – قرار
مي گيرد .در(2.2) ما فرض خواهيم كرد كه
(*)
پس يك شكل معادل براي (2.2) مي تواند به صورت زير فرمولبندي شود:
(2.3)
اگر ما تعريف كنيم:
سپس (2.3 ) مي تواندبفرم زير نوشته شود:
كه:
در تعريف بالاي – مي توانيم به
برسيم.
با ضرب مجموعه محدوديت هاي اين مسأله دوگان بوسيله –كه
ما داريم:
در اين مورد موقعي كه
ماتريس – از درايه ها ي نا منفي تعريف مي شود بطوريكه
.اين ماتريس يك نقش مهم براي يافتن مقدار بهينه مسأله ماكزيمم
مقدار – روي بازه اعداد حقيقي كه بوسيله
تعريف مي شود
بطور ساده نمايش بالا مي تواند به شكل
نوشته شود.
همچنين يك زير ماتريس – از ماتريس داده شده – كه در
صدق مي كند براي تعيين مقدار دوگان مورد نياز براي حل
برنامه ريزي كسري (2.1) مهم خواهد بود.
اين مقادير دوگان براي يك نقطه – كه يك جواب بهينه مسأله بالا (2.5) است
به خوبي در شرايط 2و3 كان-تاكر صدق مي كنند. ما بايد داشته باشيم :
يا به طور ساده:
در اينجا – يك زير ماتريس ، ماتريس داده شده – فقط شامل ضرايب مجموعه محدوديت ها ي فعال در نقطه كنوني – است. همچنين از قضيه مكمل زايد داريم :
برا ي هر مجموعه بالااز محدوديت هاي فعال مقادير دوگان متناظر بايد مثبت باشند.ازاين رو يك زير ماتريس – از ماتريس – داده شده كه در
صدق مي كند براي يافتن مقادير دوگان مورد نياز براي تعيين
مجموعه محدوديت هاي فعال متناظر با مقادير دوگان مثبت بخاطر قضيه
مكمل زايد براي مجموعه بالا از محدوديت هاي فعال اهميت خواهد داشت.
روشمان را براي حل مسايل ( )بصورت زير خلاصه مي كنيم:
را محاسبه مي كنيم.
2- ماتريس – از درايه هاي نامنفي را كه – است پيدا مي كنيم.
3- يك زير ماتريس – از ماتريس داده شده – كه در –صادق باشد ر ا پيدا مي كنيم.
4-در سطر هاي – براي هر درايه مثبت محدوديت فعال متناظر در ماتريس- را تعيين مي كنيم.
5-يك دستگاه – از معادلات خطي را براي رسيدن به جواب بهينه – حل مي كنيم.بنابراين با استفاده از (2.6) به جواب بهينه مسأله () كه بوسيله (2.1)
تعريف مي شود مي رسيم.
3.نكته ها:
نكته(3.1):
ماتريس – از درايه هاي نامنفي كه – رابه عنوان ماتريس قطبي ، ماتريس – در نظر مي گيريم.
نكته(3.2):
با – در () مسأله بالا به يك مسأله برنامه ريزي خطي () تقليل مي يابد و از اين رو روشمان ميتواند براي حل – به عنوان حالت خاصي از – به استفاده از بحثي مشابه مورد استفاده قرار بگيرد.
4.به مثال زير توجه كنيد:
مسأله دوگان فعالند. محدوديت هاي 1 و 3
نتيجه گيري:
يك روش جديد براي حل توابع كسري خطي كه محدوديت هاي آن به شكل نامساوي هاي خطي اند ، داده شده است. هدف روش به طور اصلي حل جبري با استفاده از مفهوم دوگان مي باشد.
چون روش هاي پيشين كه بر پايه اطلاعات – هستند ممكن است در ضمن اينكه مسأله اندازه افزايش مي يابد مشكلاتي را داشته باشند ، بنظر مي رسد كه روش ما حساسيت كمتري نسبت به مسأله اندازه داشته باشد.
