تحقیق در مورد برنامه خطی اعداد صحیح دوتایی ( BILP )

بخشی از مقاله

برنامه خطي اعداد صحيح دوتايي (BILP)

يك مورد خاص ILP زماني اتفاق مي افتد كه همه متغيرهاي نمونه بتوانند فقط يك يا دو رقم 0 يا 1 را قبول كنند . چنين متغيرهايي متغيرهاي دوتايي ناميده مي شوند ، و نمونه ها ، برنامه ها ، برنامه هاي 1-0 يا برنامه هاي خطي اعداد صحيح دو تايي (BILPS) ناميده مي شوند . هر حالتي كه بتواند با بله / نه ، (خوب / بد) يا 0/1 نمونه‌برداري شود به عنوان متغيردوتايي شناخته مي شود . در زير نمونه هاي زيادي از متغيرهاي دوتايي ذكر شده كه ممكن است در طرح تجاري يافت شود :

، اگر يك طرح مراقبت سلامتي جديد پذيرفته شود .
، اگر پذيرفته نشود .

، اگر مجلس خط B براي توليد نمونه هاي كولس به كار رود .
، اگر به كار نرود .
، اگر يك ايستگاه پليس جديد در پايين شهر شناخته شود .
، اگر ساخته نشود .
، اگر توليد يك اجناس به عنوان نوع «خوب» قابل قبول باشد .

، اگر به اين صورت نباشد .
، اگر بزرگراه 50 ، در سفر بين ددو شهر به كار رود .
، اگر به اين صورت نباشد .
، اگر محدوديت خاصي باشد .

، اگر آن محدوديت نياز نباشد .
، اگر يك گياه جديد در گاري هندوستان پرورش يابد .
، اگر به اين صورت نباشد .
، اگر سومين انتقال به كار رود .

، اگر به اين صورت نباشد .
همانطور كه اين مثالها نشان مي دهند ، خيلي ساده است كه متغير دوتايي را به عنوان يك تحقيق در نظر مي گيريم يعني اين كه اين تحقيق قبول شده ، يعني اين تحقيق قبول نشده است . با تفاسير داده شده در مورد متغيرها ، اكنون ما چند نوع اجبار را مورد آزمايش قرار مي دهيم ، كه تحت بررسي شوراي شهر در «سالم اورگون» مي باشد .

شوراي شهر سالم :
در آخرين جلسه مالياتي سال ، شوراي شهر «سالم» ، طرح هايي مختص سرمايه باقي مانده در بودجه يك سال ارائه كرده است . نه تحقيق تحت بررسي كامل يك سال قرار گرفته اند . براي آمارگيري حمايت مردم از تحقيق هاي مختلف ، پرسشنامه هايي به طور تصادفي به راي دهندگان در كل شهر فرستاده مي شود و از آنها خواسته مي شود كه تحقيق ها را به ترتيب از خوب به بد طبقه بندي كنند . ( بالاترين تقدم ، پايين ترين تقدم ) شورا امتيازها را بر اساس 500

پاسخي كه دريافت مي كند تطبيق مي دهد .با اين وجود هيئت شورا مكرراً متذكر مي شود كه تنها به نتايج پرسش‌نامه‌ها اكتفا نمي كند . آنها در حاليكه تخصيص هاي بودجه را تهيه مي كنند ، مسائل ديگر را هم محاسبه مي كنند . براي تخمين هزينه هر تحقيق ، ميزان تخميني ثابت هر شغل جديد بايد فراهم شده ، و تطبيق امتياز پرسشنامه ها در جدول 3-5 خلاصه شده است.

هدف هيئت شورا بالا بردن حمايت كل راي دهندگان دريافت شده (داشتن پرسشنامه به عنوان مدرك) و دادن محدوديت ها و مطالب قابل توجه ديگر هيئت شورا مي باشد كه به شرح زير است :
• 900.000 دلار باقيمانده در صندوق

• نيازهاي هيئت شورا براي ايجاد حداقل 10 شغل جديد .
• با وجوديكه جلوگيري از جنايت ، براي مردم از اهميت بيشتري برخوردار است ، هيئت شورا براي بخش هاي ديگر خدمات مردم بايد به خوبي عمل كند . بنابراين اميد مي رود كه در بيشتر تحقيق هاي مربوط پليس سرمايه گذاري شود .

• هيئت شورا مايل است كه تعداد وسايل نقليه اضطراري شهر را افزايش دهد ولي اكنون با توجه به مطالب ديگر ، فقط يكي از دو تحقيق در مورد وسايل نقليه اضطراري بايد سرمايه گذاري كند . پس دو ماشين پليس و دو ماشين آتش نشاني هم بايد خريداري شود .

• هيئت شورا معتقد است در صورتيكه تصميم بگيرد نزولهاي سرمايه را از برنامه‌هاي ورزشي در مدارس برگرداند ، نزولهاي سرمايه از برنامه هاي موسيقي هم بايد برگردانده شوند و برعكس .

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

براي نشان دادن مسئوليت پذيري مالي :
• هيئت شورا مايل است حداقل 250.000 دلار به بودجه سال بعدي انتقال دهد . بنابراين براي بقيه سال حداكثر اينقدر باقي مي ماند :
• 650.000$ = 250.000$ - 900.000$ .

براي نشان دادن ارتباط بين سلامت عموم :
• هيئت شورا مايل است حداقل در سه تحقيق آتش سوزي و پليسي سرمايه گذاري كند .
• آنها اميدوارند هفت افسر پليس جديد اضافه كنند .

براي نشان دادن علائق در رشد مشاغل :
• هيئت شورا مايل است حداقل 15 شغل جديد تمام وقت فراهم آورد .
براي اثبات حساسيت مطالب تحصيلي :

• هيئت شورا مايل است كه در هر سه تحقيق تحصيلي سرمايه گذاري كند .
اعضاي هيئت شورا تشخيص مي دهند كه سرمايه كافي براي تحقق اين پنج هدف موجود نمي باشد ، ولي آنها احساس مي كند كه اگر حداقل سه تحقيق از پنج تحقيق قابل قبول باشد ، راي دهندگان با نظر مساعدي به آن توجه مي كنند .

راه حل
هيئت شوراي شهر سالم بايد تحقيق هايي را براي سرمايه گذاري انتخاب كنند . هدفش تشخيص ارتباطات و محدوديت هايي است كه قبلاً ذكر شده است . يك سري تحقيق هايي كه حمايت عموم مردم را از طريق پرسش نامه هاي داده شده ، بالا مي‌برند .
متغيرهاي راي

متغيرهاي ، يك سري متغيرهاي راي دوتايي هستند : است . اگر‌روي تحقيق j سرمايه گذاري شود ، و 0= است اگر روي تحقيق j سرمايه‌گذاري
نشود .
نقش هدف
هدف هيئت شورا بالا بردن همه امتيازات تحقيق هاي سرمايه گذاري شده است :
بالا بردن

محدوديت ها
قبلاً ، ما محدوديت و ارتباطات مختلفي در شوراي شهر «سالم» فهرست بندي كرديم . در اينجا ما آنها را طبق انواع محدوديت BILP طبقه بندي مي كنيم .
1-محدوديت هاي مختص منبع

نمونه هاي محدوديت هاي مختص منبع كه شامل رسيدگي هايي مثل بودجه كردن سرمايه (مثل بالا بردن بودجه محدود سرمايه تحقيق) يا تحقيق اهداف (مثل پايين آوردن تعداد شغلهاي جديد فراهم آمده) .
A1-محدوديت هاي بودجه سرمايه
ماكزيمم ميزان سرمايه هايي كه بايد اختصاص يابند از 900.000$ بيشتر نمي شود اگر ضرايب ميزان هزاران دلار را نشان دهند ، اين محدوديت به اين گونه است :


B1-محدوديت هاي تحقيق اهداف
تعداد شغلهاب جديد فراهم آمده بايد حداقل 10 باشد :

2-k خارج از /N محدوديت هاي انحصاري متقابل
بعضي مواقع محدوديت ها روي تعداد تحقيق هايي كه بايد اجرا شوند (K) در يك زير مجموعه خاص (N) تحقيق ها ، واقع مي شوند . تحقيق هاي N ، اگر دقيقاً ، تحقيق هاي N بايد اجرا شوند و محدوديت انحصاري‌متقابل ناميده مي‌شوند.
A2-ماكزيمم K خارج از N محدوديت هاي تحقيق

ميزان فعاليت هاي مربوط به پليس كه بايد سرمايه گذاري شود حداكثر 3 است : .
B2-محدوديت هاي تحقيق انحصاري متقابل

دو ماشين پليس و دو ماشين آتش نشاني بايد خريداري شود . دقيقاً مي توان گفت كه تعداد تحقيق هاي خريد ماشين به علاوه تعداد تحقيق هاي خريد ماشين آتش نشاني كه بايد سرمايه گذاري شود دقيقاً برابر با 1 است : . (رجوع شود به صفحه 3)
3-محدوديت تحقيق هاي پيش نياز و هم نياز

زماني انتخاب تحقيق ها ممكن است ، تحت تاثير ترتيب هاي مورد نياز باشد . بخصوص بعضي مواقه تحقيق ها ملزم به انجان تحقيق هاي معين ديگر هم مي باشد . كه اين تحقيق ها به تحقيق هم نياز معروف هستند . در مواقع ديگر يك تحقيق يا چند تحقيق قبل از اينكه امكان انجام تحقيق بعدي فراهم شود ، بايد انجام شوند . اولين تحقيق نسبت به تحقيق بعدي ، پيش نياز ناميده مي شود . لازم به ذكر است كه اگر يك تحقيق پيشنياز انجام شود . به اين معني نيست كه تحقيق بعدي انجام خواهد

شد .
A3-محدوديت هاي تحقيق هاي هم نياز :
اگر سرمايه هاي ورزشي برگردانده شوند ، سرمايه هاي موسيقي هم برگردانده خواهند شد . و اگر سرمايه هاي ورزشي برگردانده نشوند ، سرمايه هاي موسيقي هم برگردانده نخواهند شد . اين محدوديت حاكي از تعداد برابر تحقيق هاي سرمايه موسيقي برگردانده شده و تحقيق هاي سرمايه ورزشي مي باشند . كه است يا .

B3-محدوديت تحقيق هاي پيش نياز :
سرمايه ورزش و سرمايه موسيقي ، قبل از اينكه تجهيزات جديد كامپيوتر خريداري شود بايد برگردانده شوند . اين ارتباط مي تواند به عنوان دو اجبار پيش نياز مشخص شود : ميزان سرمايه تحقيق هاي ورزشي بايد حداقل برابر ميزان سرمايه تحقيق هاي خريداري تجهيزات كامپيوتر باشد ( ) و ميزان سرمايه تحقيق هاي موسيقي بايد حداقل برابر سرمايه تحقيق هاي خريداري تجهيزات كامپيوتر باشد . ( )
يا :

و
توجه داشته باشيد كه رويهم رفته اين محدوديت به اين معني است كه اگر باشد ، پس و هر دو بايد برابر 1 باشند ، ولي اگر و باشند ، نيازي نيست كه برابر 1 باشد .

4-محدوديت هاي K خارج از N بايد نگهداشته شوند
بعضي مواقع وقتي محدوديت هاي عملي براي يك برنامه رياضي فرمول بندي مي‌شوند (خطي ، عدد صحيح ، دو تايي ، غير طولي) ، فقط بعضي از (K) زيرمجموعه خاص محدوديت هاي (N)بايد نگهداشته شوند . (اگر باشد ، محدوديت ها بعضي مواقع به هر دو محدوديت ها بر مي گردند ) ما موقعيت شوراي شهر سالم را شرح مي دهيم و فقط محدوديت هايي به كار مي برند كه متغيرهاي دوتايي داشته باشند ، ولي مفهوم مرتبط با هر نمونه برنامه رياضي است . شوراي شهر مايل است كه حداقل سه محدوديت از پنج محدوديت را راضي كند .

1-داشتن حداقل 250.000$ ذخيره ، يا كل مقدار خرج شده روي اين تحقيق ها در يك سال نمي تواند از 650.000$=250.000$-900.000$ بيشتر شود :
2-حداقل روي سه تحقيق پليس و آتش نشاني بايد سرمايه گذاري شود :

3-تحقيق كه شامل اضافه كردن هفت افسر پليس جديد است بايد سرمايه گذاري شود:
4-حداقل 15 شغل جديد بايد فراهم شود (نه فقط 10تا) :

5-سه تحقيق تحصيلي كه بايد سرمايه گذاري شوند :

حالتي كه حداقل سه هدف از پنتج هدف تحقق يافته با معرفي متغيرهاي دوتايي ، ، ، ، مشخص مي شود . در اينجا :
است اگر محدوديت i ناديده گرفته شود (هدف تحقق نيافته است)
است اگر به محدوديت توجه شود (هدف IS تحقق يافته است)
پس يك روش دو مرحله اي مي تواند براي تغيير محدوديت هاي عملي بالا براي تحقق اهداف به كار رود .