#part_304=e= Finding a tight cut
⚠️⁉️ سوال:
سلام. فرض كنيد سيستم معادلات زير مفروض است.
آيا ميتوان برشي تعريف كرد كه حالات زير را در بر داشته باشد؟
* براي هيچ يك از چهار سيستم با جواب فوق صادق نباشد.
* تنها براي دو مورد از جوابهاي فوق صادق باشد.
* براي هر چهار سيستم صادق باشد.
* تنها براي زير سيستمهاي 1 و 4 صادق باشد.
* تنها براي زير سيستمهاي 2 و 3 صادق باشد.
✅✅ پاسخ:
1) باتوجه به شكل (1) هر محدوديتي به فرم x>1 و y>1 ميتواند در قالب چنين كاتي قرار گيرد.
2) كاتهايي نظير x=1 و y=1 در چنين دسته اي قرار دارند.
3) كاتهايي مانند x<=1 و y<=1 در اين خانواده قرار دارند.
4) كاتهايي در خانواده نامساوي هاي اشتقاقي در اين دسته قرار ميگيرند. به عنوان مثال x=y را ميتوان به عنوان دو كات اشتقاقي (x>=y or x<= y) نوشت كه دو نقطه قطري را در بر خواهد داشت. متناظر ان كات اشتقاقي (y= 1-x) است.
5) باتوجه به شكلهاي 2 و 3 و 4 و دستگاه نامعادلات ذيل ميتوان فضا را به سه نقطه تعميم داد. شرايط ذكر شده براي اين دستگاه نيز قابل بررسي است.
پليتوپ دستگاه در شكل و توسط دو معادله اول ساخته ميشود. كات سوم (محدوديت سوم) امكان برقراري حالت پنجم را نيز خواهد داشت. اگر (0و1) و (1و0) را در اين محدوديت جايگزاري كنيم به ترتيب دو محدوديت اول و حد بالاي متغيير z را نقض خواهد كرد كه نتيجه ان، برقراري حالت پنجم خواهد بود. البته بند اخر بخش چهارم نيز بيانگر همين موضوع با استفاده از كاتهاي اشتقاقي است.
x-y+z <=1
-x+y+z <=1
0.5x-0.5y+z <=1
x,y,z in {0,1}
با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir