در این مقاله یك روش جدید برای مسأله ای با تابع هدف كسری خطی كه محدودیت های آن به شكل نا مساوی های خطی اند ارائه می شود.
مسایل ماكزیمم سازی كسری خطی ، پژوهش و علاقه قابل ملاحظه ای را به خود اختصاص داده اند ، زیرا آنها در برنامه ریزی تولید ، برنامه ریزی مشاركتی ومالی ، برنامه ریزی بیمارستانی و مراقبت از سلامت مفید می با شند.
چند روش برای حل این مسأله در سال 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 – NOVAES . BITRAN
دوگان و تحلیل حساسیت با تابع هدف كسری:1976- MAGNANTY . BITRAN
برنامه ریزی با توابع كسری خطی:1962-COOPER . CHANERS
شرط بهینگی در برنامه ریزی گویا. ( ژورنال قضیه بهینه سازی و كاربردها) :SING
|
تبلیغات 
منوی اصلی
نویسنده :
