مسايل ماكزيمم سازي كسري خطي ، پژوهش و علاقه قابل ملاحظه اي را به خود اختصاص داده اند ، زيرا آنها در برنامه ريزي توليد ، برنامه ريزي مشاركتي ومالي ، برنامه ريزي بيمارستاني و مراقبت از سلامت مفيد مي باشند.
چند روش براي حل اين مسأله در سال 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
