به علت برخی مشکلات سیاسی در کشور «یوتوپیا»، بین نمایندگان مجلس این کشور اختلاف افتاده است به‌طوری‌ که هر نماینده مجلس با تعدادی از نمایندگان دیگر مشکل پیدا کرده است و حاضر به نشستن با هیچ‌یک از آن‌ها سر یک میز نیست. رئیس‌جمهور این کشور برای حل این مشکل به شرکت «زتروس» روی آورده است. این شرکت دو ماشین قابل برنامه‌ریزی $A$ و $B$ را خریداری کرده است. هر برنامه‌ای که به این ماشین‌ها داده می‌شود از چهار قسمت تشکیل‌شده است:

• قسمت اول شامل تعدادی متغیر است که باید نام‌های آن‌ها به ماشین داده شوند.
• در قسمت دوم تعدادی نابرابری به ماشین داده می‌شود که همگی باید به شکل زیر باشند:

$$a_1 x_1+a_2 x_2+⋯+a_k x_k≥b$$ توجه کنید که جهت بزرگ‌تر نابرابری‌ها باید رو به متغیرها باشد. در نابرابری بالا $k$ یک عدد طبیعی دل‌خواه است. همچنین $a_1$ ،$a_2$ ، …، $a_k$ و $b$ اعداد حقیقی دل خواه و $ x_1$،$x_2$، …، و$x_k$ تعدادی از متغیرها هستند.

• در قسمت سوم یکی از دو کلمه‌ی minimum و یا maximum به ماشین داده می‌شود.
• در قسمت چهارم تعدادی از متغیرها به‌عنوان «متغیرهای اصلی» به ماشین معرفی می‌شوند.

اگر چنین برنامه‌ای را به ماشین $A$ بدهیم، این ماشین به هر یک از متغیرها یک مقدار حقیقی نامنفی طوری نسبت می‌دهد که اولاً تمامی نابرابری‌ها برقرار باشند و ثانیاً مجموع متغیرهای اصلی برحسب این‌که کلمه‌ی انتخاب‌شده minimum یا maximum بوده، کم‌ترین یا بیش‌ترین مقدار ممکن خود را داشته باشد. در پایان، ماشین مقادیر نسبت داده‌شده به متغیرها و مجموع متغیرهای اصلی را چاپ می‌کند.

فرق ماشین $B$ با ماشین $A$ تنها در این نکته است که این ماشین به‌جای مقادیر حقیقی نامنفی، فقط می‌تواند یکی از دو مقدار ۰ یا ۱ را به متغیرها نسبت دهد. این ماشین نیز مانند ماشین $A$ کم‌ترین یا بیش‌ترین مقدار مجموع متغیرهای اصلی را با حفظ درستی نابرابری‌ها به دست می‌آورد.

برای مثال برنامه‌ی زیر را در نظر بگیرید:

با دادن این برنامه به ماشین $A$، ماشین عدد $\frac 53$ را به‌عنوان بیش‌ترین مقدار ممکن برای $y+z$ چاپ می‌کند، که مثلاً به ازای $x=\frac16$ ، $y=0$، و $z=\frac53$ به دست می‌آید. (توجه کنید که مقادیر دیگری نیز برای $x$، $y$، و $z$ وجود دارند که در نابرابری‌ها صدق کنند و مجموع $y+z$ را برابر $\frac53$ قرار دهند. ولی نمی‌توان مقادیری برای متغیرها یافت که نابرابری‌ها برقرار بمانند و $y+z$ از $\frac 53$ بیش‌تر شود.)

حال اگر همین مسأله را به ماشین $B$ بدهیم، عدد ۰ را به‌عنوان جواب اعلام می‌کند که مثلاً به ازای $ x=1$، $y=0$، و $z=0$ به دست می آید.

شرکت زتروس اعلام کرد که حاضر است مسائل پیشنهادشده توسط دولت را حل کند. اولین مسأله‌ای که پیشنهاد شد از طرف وزارت بهداشت بود. در این مسأله وزارت بهداشت قصد داشت در بعضی از شهرهای کشور مقداری دارو برای مواقع اضطراری ذخیره کند به‌گونه‌ای که مجموع داروی موجود در هر شهر و تمام شهرهایی که بین آن‌ها و این شهر پرواز مستقیم وجود دارد بیش‌تر از ۱۰۰تن باشد. هدف این بود که مجموع کل داروهای ذخیره‌شده در تمام شهرها کم‌ترین مقدار ممکن را داشته باشد. توجه کنید که اگر از شهر $a$ به $b$ پرواز مستقیم وجود داشته باشد، از $b$ نیز به $a$ پرواز مستقیم وجود دارد.

زتروس برای حل این مسأله با استفاده از ماشین $A$ برنامه‌ای به این منظور طراحی کرد. در این برنامه به هر شهر یک متغیر نسبت داده‌شده که نشان‌گر مقدار دارویی است که باید در آن شهر ذخیره شود. به این ترتیب اگر $n$ را تعداد شهرها فرض کنید، آن‌گاه متغیرهای برنامه $ x_1$، $x_2$، …، و $x_n$ می‌باشند.

سپس به ازای هر شهر یک نابرابری در برنامه قرار داده شد به این ترتیب که مجموع متغیر مربوط به آن شهر و متغیر مربوط به شهرهایی که بین آن‌ها و این شهر پرواز مستقیم وجود دارد، بزرگ‌تر یا مساوی ۱۰۰ باشد. در پایان کلمه‌ی minimum به ماشین داده شد و تمامی متغیرها به‌عنوان متغیرهای اصلی معرفی گردیدند.

برای مثال اگر کشور، پنج شهر داشته باشد و بین شهرهای ۱ و ۲، شهرهای ۲ و ۳، شهرهای ۳ و ۴، و شهرهای ۳ و ۵ پرواز مستقیم وجود داشته باشد، برنامه‌ای که به ماشین داده می‌شود به‌ صورت زیر است:

که جواب ماشین برابر ۲۰۰ است که به ازای مثلاً $x_1=100$، $x_2=0$، $x_3=100$، $x_4=0$، و $x_5= 0$ به دست می‌آید. مسأله ی بعدی توسط وزارت مبارزه با قاچاق پیشنهاد شد. این وزارت قصد داشت در بعضی از فرودگاه‌های کشور مراکز مبارزه با قاچاق تأسیس کند به‌طوری‌ که تعداد این مراکز تا حد امکان کم باشد و در حداقل یکی از فرودگاه‌های مبدأ یا مقصد هر پرواز یک مرکز مبارزه با قاچاق وجود داشته باشد.

زتروس برای حل این مسأله با استفاده از ماشین $B$ برنامه‌ای ارائه داد. در این برنامه به ازای هر فرودگاه یک متغیر وجود داشت. در این صورت اگر $n$ فرودگاه داشته باشیم، متغیرها $x_1$، $x_2$، …، و $x_n$ خواهند بود. سپس برای هر پرواز بین فرودگاه $i$ و $j$، نابرابری $1 \le x_i + x_j$ در برنامه قرار داده شد. در پایان کلمه‌ی minimum به ماشین داده شد و همه‌ی متغیرها به‌عنوان متغیرهای اصلی معرفی شدند.

عددی که ماشین $B$ به‌عنوان کم‌ترین مقدار ممکن برای مجموع متغیرهای اصلی اعلام کرد، برابر کم‌ترین تعداد مراکزی بود که باید تأسیس می‌شدند، و متغیرهایی که مقدار ۱ گرفتند، فرودگاه‌هایی را تعیین کردند که باید در آن‌ها مرکز مبارزه با قاچاق تأسیس می‌شد.

اکنون شما باید زتروس را یاری کنید که بتواند مسأله‌های پیشنهادی دیگری را نیز با موفقیت به انجام برساند. همان‌طور که در مثال‌های بالا ملاحظه کردید طراحی برنامه‌ها باید به‌گونه‌ای باشد که نوشتن برنامه‌ی نهایی از روی اطلاعاتی که در دسترس شرکت قرار می‌گیرد، به‌سادگی امکان‌پذیر باشد.

الف) رئیس‌جمهور یوتوپیا با مشاهده‌ی موفقیت این شرکت در حل مسائل یادشده، مسأله‌ی زیر را به این شرکت پیشنهاد داد: آقای رئیس‌جمهور می‌خواهد تعدادی از نمایندگان مجلس را به جلسه‌ای دعوت کند ولی به علت مشکلی که در ابتدا گفته شد، او نمی‌خواهد که جلسه به مشاجره کشیده شود و از طرفی قصد دارد که حداکثر تعداد نمایندگان ممکن را دعوت کند. به همین خاطر، او لیست نمایندگانی را که باهم خصومت دارند تهیه کرده و به شرکت داده و از آن خواسته است که بیش‌ترین تعداد نمایندگانی را تعیین کند که هیچ دوتای آن‌ها با هم خصومت نداشته باشند. با استفاده از ماشین $B$ به زتروس کمک کنید که این مسأله را حل کند.

ب) وزارت کار هم مسأله‌ای مطرح کرده است. این وزارت تعدادی پروژه دارد که می‌خواهد آن‌ها را به چند شرکت واگذار کند. هر شرکت لیست پروژه‌هایی را که توانایی انجام آن‌ها را دارد به این وزارت داده است. این وزارت قصد ندارد به هیچ شرکتی بیش از یک پروژه واگذار کند و یا پروژه‌ای را به بیش از یک شرکت واگذار کند. از طرفی می‌خواهد تعداد پروژه‌های واگذارشده بیش‌ترین تعداد ممکن باشد. این مسأله را با استفاده از ماشین $B$ حل کنید.

ج) ثابت کنید که اگر در مسأله ی وزارت مبارزه با قاچاق، برنامه‌ی تهیه شده برای ماشین $B$ اشتباهاً به ماشین $A$ داده شود، جواب به دست آمده کم‌تر نصف جواب به دست آمده از ماشین $B$ نخواهد بود. (یعنی مجموع متغیرهای اصلی در جواب ماشین $A$ کم‌تر از مجموع متغیرهای اصلی در جواب ماشین $B$ نخواهد بود).

• سوال قبل