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

یک مورد خاص 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 تحقق یافته است) پس یک روش دو مرحله ای می تواند برای تغییر محدودیت های عملی بالا برای تحقق اهداف به کار رود .

مرحله 1 : افزایش هر با یک رقم بزرگ که به عنوان M شناخته شده و مراحل زیر را انجام می دهد : 1-اگر محدودیت متقابل یک محدودیت «» است ، واژه را به سمت راست محدودیت اضافه کنید .

(پس اگر است‌ ، سمت راست خود محدودیت خیلی بزرگ است ، بنابراین نیاز نیست که حالت اصلی بماند) 2-اگر محدودیت متقابل یک محدودیت «» است ، واژه از سمت راست محدودیت کم می شود .

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

3-اگر محدودیت متقابل یک محدودیت «=»باشد ، ابتدا محدودیت را به دو محدودیت «» و «» تبدیل کنید .

سپس حالتهای (1) و (2) را با استفاده از همان متغیرهای دوتایی در هر اختلاف جدید ایجاد شده ، به کار ببرید .

مرحله 2 : محدودیت را به محدودیت های عملی اضافه کنید .

از آنجا که حداقل محدودیت های K خارج از N باید برآورد شود ، تعداد کل این محدودیت ها که برآورد می شود () حداکثر به محدود می شود .

این روش دو مرحله ای که برای موقعیت شورای شهر سالم به کار می رود ، به شرح زیر است : مرحله 1 : تبدیل پنج محدودیت نامعلوم به این صورت : مرحله 2 : محدودیتی که به حداقل سه محدودیت از پنج محدودیت باقیمانده نیاز دارد، را اضافه کنید (حداکثر دو محدودیت باقی نماند) تکمیل نمونه برای شورای شهر سالم تکمیل نمونه برای شورای شهر سالم که شامل کاربرد هدف ، محدودیت های نامعلوم و کاربردی و محدودیت های دوتایی است اکنون به صورت زیر محاسبه می شود : حداکثر ST همه و یا هستند .

چون همه متغیرها (هم و هم ) محدود به 0 یا 1 هستند .

این مشکل BILP است .

این مشکل با استفاده از WINQSB حل می شود که در شکل 11-5 نشان داده شده است .