X
تبلیغات
رایتل

IDS: Intrusion Detection System

چرا منطق فازی - مجموعه های فازی

چرا منطق فازی
منطق فازی به سیستم های کامپیوتری کمک می کند تا مانند یک انسان تصمیم بگیرند و استنتاج نمایند.برای مثال هنگامی که یک دستور العمل آشپزی را دنبال می کنیم در واقع از نوعی استنتاج انسانی بهره می گیریم .مثلا سرآشپز می گوید کمی نمک این اصطلاح برای انسان ها آشناست و قابل درک اما برای کامپیوتر ها نه.منطق فازی به کمک ما می آیند تا قسمتی از استنتاج انسانی  را برای سیستم های هوش مصنوعی فراهم سازد.با یک مثال این مورد را توضیح می دهم.در خصوص اندازه گیری هوش مصنوعی با سه گروه روبه رو هستیم باهوش ، حد متوسط و کودن در واقع با سه مجموعه سر و کار داریم پس طبق تعریف مجموعه های کلاسیک هر شخص عضو یکی از این مجموعه هاست و اگر عضو  یکی بود نمی تواند عضو مجموعه دیگری باشد. سه مجموعه را به صورت زیر تعریف می کنیم :
کودن={۷۰ ،۷۱ …..۷۹}
حد متوسط = {۸۰ ،۸۱ ،…..۱۰۹}
باهوش= {۱۱۱،۱۱۰، …...،۱۳۰}

که نحوه نمایش گرافیکی این مجموعه های کلاسیک (CRISP SET ) به صورت زیر است.

به شکل توجه کنید که درجه عضویت هر عنصر از یک مجموعه ۰ یا ۱ است.بر این اساس هوشمندی یک شخص را می توان با نسبت دادن آنها بر اساس نمره IQ که به دست آورده اند به یکی از این مجموعه ها بدست آورد.فقط یکی از مجموعه ها.حالا حالتی را در نظر می گیریم که شخص نمره تست هوش برابر ۱۰۹ دارد.مسلما هوش او بالاتر از هوش افراد حد متوسط است و شاید حتی بتوان او را جز افراد باهوش در نظر گرفت زیرا هوش او از شخصی که درای نمره هوش ۹۲ است بسیار بیشتر است اگرچه با استفاده از مجموعه  های کلاسیک این دور هر دو در یک رده هوشی قرار خواهند داشت.حالا فرض کنیم شخصی دارای نمره هوشی ۷۹ و دیگری نمره ۸۰ است مسلم است که مقایسه این دو و به این نتیجه رسید که یکی باهوش و دیگری کودن است نیز عقلانی به نظر نمی رسد و این همان نقطه است که مجموعه های کلاسیک از درک آن عاجز هستند و نقطه سقوط آنهاست.مجموعه های فازی به عناصر اجازه می دهند که یک درجه اهمیت به آنها نسبت داده شود  و مرزهای فازی با استفاده از توابع عضویت (membership function ) تعریف شوند. یک مجموعه فازی بوسیله تابع عضویت آن تعریف می شود.این توابع می توانند هر شکل دلخواهی داشته باشند اما معمولا پرکاربردترین آنها مثلثی و ذوذنقه ای هستند. نکته قابل توجه در همه اشکال منطق فازی انتقال تدریجی از نواجی کاملا خارج از یک مجموعه به نواحی کاملا داخل مجموعه می باشد که در شکل ذیل که مربوط به نمایش مثلی عبارات زبانی کودن ، حد متوسط و باهوش است قابل مشاهده است که این روند یک مقدار را قادر می نماید تا در یک مجموعه دارای عضویت بخشی ( جزیی) Partial membership باشد.در این شکل خط نقطه چین نشان دهنده چگونگی وضعیت مغزی شخص است.کسی که تست هوش وی برابر با ۱۱۵ باشد عضو دو گروه خواهد بود اما با درجه عضویت های متفاونت.همانگونه که نقطه تقاطع خط چین با مجموعه ها نشان می دهد درجه عضویت وی در مجموعه باهوش ها برابر با ۰.۷۵ و درجه عضویت وی در مجموعه حد متوسط ها برابر ۰.۲۵ است .این روش دقیقا مشاهبه عملکر استنتاج انسانی در خصوص هوشمندی افراد است.


انسان این شخص را بیشتر باهوش می داند تا دارای هوش متوسط و این چیزی است که می تان از مقادیر عضویت مجموعه فازی وی می توان استنباط نمود.


معرفی منطق فازی

مقدمه :

سیستم های منطق فازی (fuzzy logic systems -fls) یک خروجی قابل قبول اما قطعی در پاسخ به یک ورودی ناقص ، مبهم ، تحریف شده و یا نادرست (fuzzy) تولید می کنند.

منطق فازی چیست ؟
منطق فازی (Fuzzy Logic -FL) یک نوع مدل  استدلال است که استدلال انسانی را شبیه سازی می کند.شیوه منطق فازی راه حل تصمیم گیری انسانی  را تقلید می‌کند به طوری که همه امکان های میانی بین مقادیری دیجیتال بله یا خیر را  در نظر گرفته و در حل مسائله درگیری می کند.
بلاک منطقی مرسوم که یک کامپیوتر آن را درک می‌کند و متوجه می‌شود یک ورودی قطعی را دریافت می‌کند و یک خروجی صریح را تولید می‌کند که این خروجی صحیح( TRUE ) یا غلط است ( FALSE). این خروجی ها شبیه  بله یا خیر انسانی هستند.مخترع منطق فازی ،پرفسور  لطفی زاده ، کشف نمود که بر خلاف کامپیوتر ها ، تصمیم های گرفته شده توسط بشر شامل یک محدوده از چیز های ممکن  در میان  بله و خیر است.از قبیل :
CERTAINLY YES -قطعا بله
POSSIBLY YES – احتمالاً بله
CANNOT SAY – نمیشه گفت
POSSIBLY NO -احتمالا نه
CERTAINLY NO – قطعاً بله

منطق فازی بر روی همه سطوح موارد(جواب های ) ممکن برای ورودی  به منظور بدست آوردن یک خروجی قطعی عمل می کند.


 پیاده‌سازی و اجرا :

سیستم منطقی فازی می‌تواند در سیستم‌هایی با اندازه ها   و محدوده توانایی متفاوت از میکرو کنترلر های کوچک تا بزرگ ، شبکه ، سیستم‌های کنترلر مبتنی بر ایستگاه کاری  پیاده‌سازی و اجرا شود.
سیستم منطق فازی می‌تواند در سخت‌افزار ها ، نرم‌افزار های و ترکیبی از هر دو پیاده‌سازی و اجرا شود.

چرا منطق فازی ؟
منطق فازی برای اهداف تجاری و علمی و کاربردی مفید است
  • می‌تواند برای کنترل ماشین‌ها و محصولات مصرف کننده به کار گرفته شود
  • ممکن است که استدلال دقیقی در اختیار قرار ندهد ، اما در نهایت یک استدلال قابل قبول تولید می‌کند
  • منطق فازی یکی از روشها یی است که می‌تواند در محیط های غیر قطعی کاربرد داشته باشد
معماری سیستم‌های فازی :

یک سیستم منطق فازی ۴ بخش اصلی دارد که در ذیل به آن می‌پردازیم.


1- ماژول فازی سازی (Fuzzification Module)
این قسمت از سیستم منطق فازی ورودی های سیستم را که اعداد Crisp ( همان مجموعه اعداد معمولی ) را به مجموعه فازی تبدیل می کند. این ماژول سیگنال ورودی را به ۵ مرحله تقسیم می‌کند ، از جمله :
LP     x is Large Positive        X مثبت بزرگ است
MP     x is Medium Positive        X  مثبت متوسط است
S     x is Small            X کوچک است
MN     x is Medium Negative    X متوسط منفی است
LN     x is Large Negative        X بزرگ منفی است

2-پایگاه دانش : Knowledge Base

در پایگاه دانش قوانین IF-THEN هایی که توسط شخص خبره تهیه و تدوین شده‌اند قرار می گیرد.


3- موتور استنتاج (Inference Engine) :

موتور استنتاج پروسه استدلال انسانی را بوسیله ایجاد استنتاج فازی بر روی ورودی و قوانین IF-THEN شبیه سازی می‌کند


4- ماژول غیر فازی ساز (Defuzzification Module ):
ماژول غیر فازی ساز در نهایت مجموعه فازی تولید شده بوسیله موتور استنتاج را به مقداری عددی معمولی (Crisp ) تبدیل می کند.



تابع عضویت بر روی مجموعه های فازی از متغیر ها ،یکسری عملیات  را  انجام می‌دهند.
تابع عضویت :
تابع عضویت به ما اجازه می‌دهد تا که یک مجموعه فازی را به صورت گرافیکی نمایش بدهیم و موارد زبان‌شناسی مربوط به آن را تعیین کنیم.تابع عضویت برای یک مجموعه فازی مثل A بر روی متغیر universe of discourse مثل X به صورت :µA:X → [0,1] تعریف می شود.که در آن هر عنصر از X به مقداری بین ۰ و ۱ نگاشت می شود. که مقدار عضویت یا درجه عضویت نامیده می شود.که درجه عضویت عنصری در X را در مجموعه فازی A معین می کند.
  • محمور X نشان دهنده  universe of discourse است.
  • محور Y نشان دهنده درجه عضویت است که بین   ۰ تا ۱ متغیر است. [0,1 ].
ممکن است که چنید تابع عضویت برای فازی نمودن مقداری عددی به کار برده شود. همه توابع عضویت برای  LP, MP, S, MN و LN در شکل زیر نشان داده شده است .


تابع عضویت مثلثی شکل در میان دیگر شکل‌های تابع عضویت مثل ذوذنقه ای ، تک صفحه (singleton) و گواسین (Gaussian) عمومیت بیشتری دارند.
در این شکل ورودی برای ۵ سطح فازی کننده از -۱۰ ولت تا +۱۰ ولت متغیر است.بنابراین خروجی متناظر نیز متغیر است.

مثالی از یک سیستم منطق فازی :

اجازه بدهید تا یک سیستم تهویه هوا را با پنج سطح سیستم منطق فازی مورد بررسی قرار دهیم.این سیستم دمای سیستم تهویه هوا را با مقایسه دمای اتاق و مقدار دمای مورد نظر ( هدف) تنظیم می کند.

الگوریتم
تعریف متغیر های زبانی و شرایط ( موارد)
ساختن توابع عضویت برای آن‌ها
ساختن پایگاه داده دانش قوانین
تبدیل داده‌های معمولی (Crisp Data ) به مجموعه های داده فازی با استفاده از توابع عضویت ( فازی سازی)
ارزیابی قوانین در پایگاه قانون (موتور استنتاج)
ترکیب نتابج هر یک از قانون ها (موتور استنتاج)
تبدیل خروجی داده به مقادیر غیر فازی (غیر فازی سازی )



توسعه منطق :مرحله اول : تعریف متغیر های زبانی و شرایط ( موارد)
متغیر های زبانی ، متغیر های ورودی و خروجی در شکل کلمات ساده یا جملات هستند.برای دمای اتاق ، سرد ، گرم و غیره و غیره موارد زبانی هستند.
Temperature (t) = {very-cold, cold, warm, very-warm, hot}
هر عضوی از این مجموعه یک مورد زبانی است و می‌تواند بخشی از مقادیر دما را به طور کلی پوشش دهد.

مرحله ۲ : تولید توابع عضویت برای آن‌ها :

توابع عضویت متغیر دما در ذیل نشان داده شده است

مرحله ۳ :
ایجاغد یک ماتریکس از مقادیر دمای اتاق در مقابل مقادیر دمای هدفی که از سیستم تهویه انتظار داریم برای ما فراهم کند
دمای هدف / دمای اتاق
                                      

دمای هدف / دمای اتاق

Very_Cold

Cold

Warm

Hot

Very_Hot

Very_Cold

No_Change

Heat

Heat

Heat

Heat

Cold

Cool

No_Change

Heat

Heat

Heat

Warm

Cool

Cool

No_Change

Heat

Heat

Hot

Cool

Cool

Cool

No_Change

Heat

Very_Hot

Cool

Cool

Cool

Cool

No_Change


مجموعه قوانی را پایگاه دانش به شکل IF-THEN-ELSE تولید و ایجاد می کنیم.

Sr. No.

Condition

Action

1

IF temperature=(Cold OR Very_Cold) AND target=Warm THEN

Heat

2

IF temperature=(Hot OR Very_Hot) AND target=Warm THEN

Cool

3

IF (temperature=Warm) AND (target=Warm) THEN

No_Change



مرحله ۴ : بدست آوردن مقدار فازی
عملیات های مجموعه فازی ارزیابی قوانین را انجام می دهند. عملیات استفاده شده برای OR و AND به ترتیبی بیشینه max و کمینه MIN  می باشد.همه نتایج ارزیابی به شکل نتیجه نهایی ترکیب می شوندواین تنتیجه یک مقدار فازی است.

مرحله ۵ : انجام عملیات غیر فازی نمودن
غیر فازی نمودن انجام عملیات بر اساس تابع عضویت برای متغیر خروجی می‌باشد

انتخاب والد در الگوریتم های ژنتیک

انتخاب والد :
انتخاب والد پروسه‌ای انتخاب والدینی است که قرار است با یکدیگر ترکیب شده و اولاد هایی را برای نسل بعدی ایجاد کنند. انتخاب والد برای نرخ همگرایی یک الگوریتم ژنتیک بسیار حیاتی است و  انتخاب خوب والدین الگوریتم ژنتیک را به  راه حل های بهتر و مناسبتر سوق می دهد.
انتخاب یک راه حل در جمعیتی با تعداد کمی از نسل ها می‌تواند میزان تنوع در راه حل‌ها را بکاهد.بنابراین حفظ تنوع خوب در جمعیت در موفقیت الگوریتم ژنتیک بسیار حیاتی است .در نظر گرفته شدن کل یک جمعیت بوسیله یک راه حل بسیار خوب تحت نام همگرایی نابهنگام (premature convergence) نامیده می‌شود که یک وضعیت نامطلوب در الگوریتم ژنتیک است.
انتخاب مناسب برازش (Fitness Proportionate Selection)
انتخاب برازش مناسب یکی از شیوه‌های مرسوم در انتخاب والد می باشد.در این روش هر شخصی می‌تواند با توجه به احتمال متناسب با برازش خود یک والد باشد.بنابراین اشخاص مناسبتر دارای شانس بالاتر برای زاد و ولد و انتشار ویژگی‌های خود به نسل های بعدی دارند.بنابراین این استراتژی در انتخاب موجب می‌شود که افرادی که درای شایستگی بیشتری در جمعیت هستند انتخاب شوند و ویژگی های این افراد در طول زمان رشد و نمود پیدا کند
یک چرخ دایره‌ای شکل را در نظر بگیرید.چرخ به n تکه تقیسیم شده است.در واقع n نشان دهنده شماره شخص در جمعیت می باشد.هر شخص یک قسمت از دایره را در اختیار دارد که فضایی که در اختیار شخص است نشان دهنده تناسب مقدار برازش آن شخص می باشد.دو شیوه برای انتخاب برازش مناسب امکان‌پذیر می‌باشد

انتخاب چرخ رولت.Roulette Wheel Selection

در انتخاب چرخ رولت ، چرخ دایره‌ای (مدور) به همان شکلی که قبلاً توضیح داده شد تقسیم شده است.همانگونه که در شکل نشان داده خواهد شد یک نقطه ثابت در پیرامون چرخ انتخاب می‌شود و سپس چرخ ، چرخانیده می‌شود .ناحیه ای از چرخ که در جلوی نقطه ثابت در نظر گرفته شده قرار گیرد به عنوان والد انتخاب می شود.برای انتخاب والد دوم رویه ای مشابهی تکرار می شود. در شکل زیر  استفاده از روش چرخ رولت نشان داده شده است


واضح است که فرد مناسبتر دارای سهم بزرگتری در چرخ است و بنابراین شانس بیشتری هم برای ایستادن در مقابل نقطه ثابت هنگامی که چرخ ، چرخانیده می‌شود دارد.شانس انتخاب یک فرد به طور مستقیم وابسته به مقدار برازش آن است.
در قسمت ذیل یک شبکه کد برای انتخاب توسط چرخ رولت آورده شده است :


for all members of population

     sum += fitness of this individual

end for


for all members of population

probability = sum of probabilities + (fitness / sum)

sum of probabilities += probability

end for


loop until new population is full

do this twice

number = Random between 0 and 1

for all members of population

if number > probability but less than next probability then you have been selected

end for

end

create offspring

end loop


نمونه برداری فراگیر تصادفی :Stochastic Universal Sampling (SUS)
.
نمونه برداری فراگیر تصادفی کاملاً مشابه روش انتخاب والد به شیوه چرخ رولت است ، هرچند بجای اینکه تنها یک نقطه ثابت بر روی چرخ داشته باشیم در این شیوه همانگونه که در شکل نشان داده شده است چندین نقطه ثابت بر روی چرخ داریم.بنابراین همه والد ها تنها در یک چرخش از چرخ(دایره) انتخاب می شوند.این شیوه از انتخاب والد اجازه می‌دهد که افراد که لیاقت بالایی دارند حد اقل یک بار شانس انتخاب شدن داشته باشند.



این نکته را باید بازگوکنم  که متدهای انتخاب برازش مناسب در مورادی که برازش می‌تواند مقدار منفی دریافت کند عمل نمی کنند.



انتخاب مسابقه‌ای (تورنومنتی)
در انتخاب K-Way تورنومنتی ، تعداد k شخص را از بین جمعیت به شکل تصادفی انتخاب می‌کنیم و بهترین آن‌ها را به عنوان والد بر می گزینیم.پروسه ای مشابه برای انتخاب والد بعدی به همین صورت تکرار می شود.شیوه انتخاب به صورت تورنومنتی برای موقعیت هایی که برازش مقدار منفی دارد نیز مناسب است.



انتخاب رتبه ای (Rank Selection)
انتخاب رتبه ای(رتبه بندی) هم مثل انتخاب مسابقه‌ای با مقادیر برازش منفی کار می‌کند و اغلب هنگامی که در جمعیت مقادیر برازش ها به هم خیلی نزدیک هستند ( اغلب در پایان اجرای الگوریتم رخ می دهد) مورد استفاده است.در این شیوه هر شخص یک تکه مساوی از دایره را به اشتراک می گیرد.همانگونه که در شکل زیر نشان داده شده است .بنابراین مقدار برازش هر شخص در انتخاب او به عنوان والد مهم نیست و همه در انتخاب از احتمال یکسانی برخوردار هستنددر .این شیوه انتخاب فشاری برای انتخاب شخص واجد شرایط تر وجود ندارد و انتخاب والد در الگوریتم ژنتیک را در برخی موقعیت ها با ضعف مواجه می‌کند . در این روش مفهوم مقدار برازش در انتخاب والد حدف می شود.هر چند برای در شخص در جمعیت یک رتبه بر اساس مقدار برازش آن در نظر گرفته می شود.انتخاب والدین بسته به مقدار رتبه هر فرد می‌باشد نه مقدار برازش آن.فرد با مقدار رتبه بالاتر بر فرد با رتبه پایینتر ارجحیت داده می شود

تابع برازش (Finness function)

تابع برازش (Finness function) 
تعریف ساده از تابع برازش ، تابعی است که راه حل کاندید برای یک مسائله را به عنوان ورودی دریافت می‌کند و یک خروجی را که میزان خوب بودن راه حل را مشخص می‌کند ارایه می‌کند که این کار با توجه به مسائله ای که با آن سر و کار داریم در نظر گرفته می شود..محاسبه مقدار برازش (fitness) مکرراً در یک الگوریتم ژنتیک انجام می‌شود و بنابراین باید به اندازه کافی سریع باشد.محاسبه  آهسته و کند مقدار برازش(Finness) می‌تواند اثر منفی روی الگوریتم ژنتیک داشته باشد و الگوریتم را فوق‌العاده کند نماید.
در اغلب مواقع تابع برازش (fitness function) و تابع هدف(objective function) شبیه یگدیگر هستند و هر دوی آن‌ها تابع مقصود داده شده را کمینه یا پیشنه می کنند.برای مسائل پیچیده با چنید هدف و محدودیت(constraints) طراح الگوریتم ممکن است تابع های برازش مختلفی را انتخاب نماید.
تابع برازش  باید دارای ویژگی‌های زیر باشد :
  • تابع برازش باید به اندازه کافی برای محاسبه سریع باشد.
  • تابع برازش باید بصورت کمی چگونگی بدست آوردن راه حل مناسب یا چگونگی تولید افراد مناسب از راه حل بدست آمده را اندازه‌گیری نماید
در اغلب موارد ، محاسبه تابع برازش به دلیل پیچیدگی ذاتی مشکلی که با آن رو به رو هستیم به صورت مستقیم امکان ندارد.در  چنین مواردی از تخیمین برازش (fitness approximation) برای برآورده نمودن نیاز های خود استفاده می کنیم.
در  شکل زیر محاسبه برازش  برای مسائله کوله پشتی 0-1 نشان داده شده است.این یک تابع برازش ساده است که تنها مقادیر ارزش آیتم هایی که انتخاب شده‌اند را جمع می بندد(آنهایی که در کروموزوم با ۱ نشان داده شده اند) ، عناصر از چپ به راست اسکن می‌شوند تا زمانی که کوله پشتی پر شود.

مسائله کوله پشتی Knapsack Problem (KP)

مسائله کوله پشتی  Knapsack Problem (KP)

بر خود لازم دیدم قبل از ورود به مباحث پیشرفته تر در خصوص الگوریتم های ژنتیک و با توجه به اینکه  در مطالبی که قبلا آورده شده است و مطالب آتی مسائله کوله پشتی  به کرات مورد استفاده قرار گرفته است  ، تعریف کاملی در خصوص این مسائله برای درک بهتر خواننده داشته باشم.

مسائله کوله پشتی یک نمونه از مسائل بهینه سازی ترکیبی است (combinatorial optimization problem) که در آن بهترین راه حل از میان راه حل‌های دیگر جستجو می شود. در این مسائله یک کوله پشتی که دارای اندازه صحیح مثبت(یا ظرفیت ) است وجود دارد که این ظرفیت با V نشان داده می شود.تعداد n آیتم متفاوت که بطور بالقوه ممکن است در کوله پشتی قرار داده شوند نیز وجود دارد.آیتم I دارای یک اندازه صحیح (ظرفیت) است که با VI  نشان داده می‌شود و  یک عدد صحیح BI که نشان دهنده منفعت ( ارزش) این آیتم است.علاوه بر این‌ها QI کپی از آیتم I در دسترس می باشد.که مقدار QI یک عدد صحیح است که شرط زیر را مهیا نماید
1 ≤ Q i ≤ ∞

اجازه بدهید که XI معین نماید که چه تعداد کپی های آیتم I قرار است در کوله پشتی قرار گیرند و هدف ما به صورت زیر تعریف می‌شود که حاصل عبارت زیر را پیشینه نماییم :(قرار دادن بیشترین آیتم با بیشترین ارزش در کوله پشتی)

با این شرط که آیتم های قرار گرفته از ظرفیت کوله پشتی بیشتر نباشند :

و همچنین شرط زیر نیز صادق باشد :
1 ≤ X i ≤ Q i
اگر یکی یا چند تا از Qi بی نهایت باشند ( نامتنهای) مسائله کوله پشتی را بدون کران می نامند در غیر این صورت مسائله کوله پشتی کراندار خواهد بود.مسائله کوله پشتی کراندار می‌تواند کوله پشتی 1-0 باشد ( 0-1 knapsack) و یا چند محدودیتی .اگر مقدار Qi برابر با ۱ باشد آنگاه با یک مسائله کوله پشتی از نوع 0-1 روبه رو هستیم. در این خاص از مسائله کوله پشتی (0-1) ما نمی‌توانیم بیشتر از یک کپی از یک آیم در کوله پشتی داشته باشیم.
یک مثال برای مسائله کوله پشتی 0-1
فرض کنیم که کوله پشتی در اختیار داریم که ظرفیت آن ۱۳ اینچ مکعبت است و چندین آیتم با سایزها و ارزش‌های مختلف در ختیار داریم.می می‌خواهیم در کوله پشتی تنها آیتم هایی را داشته باشیم که در مجموع دارای یبشترین ارزش باشند با این محدودیت که مجموع ظرفیت آن‌ها از ظرفیت کوله پشتی بیشتر نشود .برای مثال ما سه آیتم وجود دارد که با حروف A,B,C برچست خورده اند.که در جدول زیر ظرفیتها (حجم) و ارزش‌های آن‌ها را مشاهده می کنید :

آیتمABC
ارزش Benefit435
ظرفیت Volume678

ما به دنبال این هستیم که مقدار ارزش‌های آیتم ها را بیشینه نماییم:

البته با رعایت شرایط زیر :


برای مسائله ما 23 زیر مجموعه از آیتم ها وجود دارد که ترکیبی همگی در ذیل آورده شده است :

ارزش مجموعهظرفیت مجموعهCBA
00000
58100
37010
-15110
46001
-14101
713011
-21111

برای بدست آوردن بهترین راه حل مجبور هستیم که زیر مجموعه‌ای از آیتم ها که محدودیت‌های مورد نظر را دارا می‌باشند و جمع ارزش‌های آن‌ها بیشینه است را معین کنیم.در مثال ما تنها سطری که بصورت پر‌رنگ در آمده است شروط مورد نظر را فراهم می کند.بنا براین ارزش بهینه برای محدودیت مورد نظر ما ( V=13) تنها می‌تواند با یک مقدار از A ، یک مدقار از B و هیچ مقدار از C امکان‌پذیر خواهد بود که این مقدار نیز 7 بدست آمد.
1 2 3 >>