انجام پایان نامه بهینه سازی برنامه‌ریزی
مسائل عمومی بهینه سازی برنامه‌ریزی درجه دوم صفر و یک ۰-۱ از سوی تعداد زیادی از نویسندگان مورد مطالعه قرار گرفته است؛ مثلا رج.ع کنید به تحقیقات Hammer and Rudeanu [3] and Hansen [4]. شکل آن چنین است:
که در آن A یک ماتریس عددی متقارن n*n است و Bn مجموعۀ تمام بردارهای ۰-۱ بُعد n به شکل x = x۱, x۲, . . . , xn)) است. زمانیکه متغیرهای ۰-۱ تساوی را برقرار سازند، بخش درجه دوم معادلۀ مدنظر آشکارا حاوی یک تابع خطی هم هست. مسئلۀ برنامه‌ریزی درجه دوم ۰-۱ (۱)مشهور است که جزء NP-hard می‌باشد.
مسئلۀ بیشترین اکیپ در حل برنامه‌ریزی درجه دوم
آنچنانکه -مثلاً- مسئلۀ بیشترین اکیپ «گروه/دسته»[۱] یک مورد خاص است. Hammer [2] و همکارانش نشان دادند که این مسئله در زمرۀ NP-hard باقی می‌ماند حتی اگر تابع هدف در (۱) حاصل دو تابع خطی ۰-۱۱ باشد.
یکی دیگر از دسته‌جات مهم و خاص مسائل بهینه سازی ۰-۱ راجع به بیشینه‌سازی نسبت دو تابع خطی است که ضرایب عددصحیح a۰, . . . , an و b۰, . . . , bn دارند:
مسئلۀ (۲) چند جمله‌ای
این مسئله تحت عنوان مسئلۀ برنامه‌ریزی درجه دوم ۰-۱ تک نسبتی بدون محدودیت[۲] هم مشهور است. اگر مقسوم علیه که برابر است با برای همۀ مثبت باشد، آنگاه مسئلۀ (۲۲) چند جمله‌ای قابل حل است. این مسئله، در حالت کاملا عمومی آن (که چند جمله‌ای هم می‌تواند مقادیر مثبت بگیرد هم مقادیر منفی)، با این حال NP-hard است؛ میتوانید به تحقیقات Boros and Hammer [1] هم رجوع کنید.
مسائل NP-hard
یکتائی جواب‌های بهینه. بحث Pardalos and Jha [7] در خصوص پیچیدگی این مطلب است که آیا مسائل بهینه سازی درجه دو (۱) یک جواب بهینۀ یکتا دارند؛ آنها NP-hard بودن این سوال را ثابت کرده‌اند.
Prokopyev, Huang and Pardalos [8] پیچیدگی این مطلب را تحلیل کرده‌اند که آیا مسائل بهینه‌سازی چندجمله‌ای (۲) یک جواب بهینۀ یکتا دارند، همچنین اثبات کنند که این مسئله، از نوع NP-hard است. (همچنین یادآوری می‌شویم که مقالات [۷,۸] ثابت کرده‌اند مسائل درجه دوم ۰-۱ و برنامه‌های ۰-۱ کسری[۳]، همچنان NP-hard می‌مانند حتی اگر معلوم شود که یک جواب بهینۀ یکتا دارند).
اثبات غیریکتائی
دلیلی ندارد باور کنیم که مسائل پیرامون یکتائی در زمرۀ پیچیدگی طبقۀ NP (یا طبقۀ بسیار مرتبط با آن یعنی coNP) قرار می‌گیرند: برای اثبات غیریکتائی در یک مثال نقض، ظاهرا فرد باید دو جواب ممکن را نشان دهد (که کار آسانی است زیرا در زمرۀ NP است) بعلاوۀ یک گواهی که بیان کند این دو جواب حقیقتاً بهینه هستند (که بخش مشکل کار اینجاست).
اثبات اینکه جوابی بهینه است بر می‌گردد به اثبات اینکه جواب بهتری وجود ندارد، که به نظر می‌رسد به یک گواهی coNP نیاز داشته باشد. چنین ترکیبی از گواهی‌های NP و coNP بیانگر آن است که این سوالات از نظر طبقۀ پیچیدگی، مافوق طبقۀ NP و coNP قرار می‌گیرند، برای دیدن مثال به کتاب Papadimitriou فصل ۱۷ مراجعه کنید.
مقدمه
یکی از طبقات مهم و طبیعی پیچیدگی، Δ۲P است، طبقۀ همۀ مسائلی که می‌توانند هنگام استفاده از یک پاسخ مبهم[۴] از NP، در زمانی معادل زمان چندجمله‌ای‌ها حل شوند، رجوع به مرجع [۶۶].
آشکار شده که Δ۲P دربر دارندۀ تمام سلسله مراتب بولی[۵] در NP است، همچنین ساده‌ترین طبقۀ پیچیدگی هم هست که NP را شامل می‌شود و تحت اجتماع[۶]، اشتراک[۷] و متمم[۸]، بسته است.
طبق گفته‌های شهودی (و فرض P≠NP)، این ظبقۀ Δ۲P بسیار گسترده‌تر از NP بوده و در بر دارندۀ مسائلی است که بسیار دشوارتر از همۀ مسائل NP و coNP هستند. نتیجۀ برجسته‌ای که Papadimitriou [5] در این حوزه گرفت نشان داد که آیا مثال مفروض در مورد مسئلۀ بهینه سازی فروشندۀ دوره‌گرد (TSP) یک جواب بهینۀ یکتا دارد.
که Δ۲P –complete است؛ به بیان دیگر، جستجوی یکتائی برای TSP جزء سخت‌ترین سوالات Δ۲P است و از این رو در طبقۀ Δ۲P سختی کامل[۹] دارد.
مسئلۀ کوله‌پشتی
مرجع [۵] همچنین به عنوان نتیجۀ جانبی، کامل‌بودن Δ۲P را اثبات کرد که هم جواب بهینۀ یک برنامۀ عددصحیح و یا یک مسئلۀ کوله‌پشتی یکتا خواهد بود؛ نتیجۀ جانبی در مورد مسئلۀ کوله‌پشتی، نقطۀ آغاز اثبات ما است:
مثالی از مسئلۀ (استاندارد) کوله‌پشتی شامل n آیتم است که اوزانی نامنفی و عددصحیح به شکل w۱,…,wn و سودهائی نامنفی و عددصحیح به شکل p۱, . . . , pn دارند، علاوه بر اینکه اوزان در حیطۀ WW قرار دارند.
برای زیرگروهی به صورت ما اوزان را به شکل و سودها را به صورت w(I)=W بیان می کنیم. با افزودن آیتم‌های موهومی مناسب که سود صفر داشته باشند، ما می توانیم فرض کنیم که حداقل یک زیرمجموعۀ امکان‌پذیر وجود دارد (همین کار را هم می کنیم). در مسئلۀ کوله‌پشتی، هدف این است که یک زیرمجموعۀ I را بیابیم که p(I) را بیشینه سازد.
قضیه ۲.۱
(Papadimitriou [5]). Δ۲P کامل «همان مبنائی» است که آیا یک مثال مفروض در زمینۀ مسئلۀ کوله‌پشتی یک جواب بهینۀ یکتا دارد.
انجام پایان نامه ریاضی در دکتر تحقیق؛ انجام مقاله های حرفه ای ریاضیات!
[۱] maximum clique problem
[۲] unconstrained single-ration hyperbolic 0–۱ programming problem
[۳] quadratic 0–۱ and fractional 0–۱ programs
[۴] oracle
[۵] Boolean hierarchy
[۶] union
[۷] intersection
[۸] complement