Feasible region — ขอบเขตของคำตอบที่ยอมรับได้

ขอบเขตของคำตอบที่ยอมรับได้ (หรือ เซตของคำตอบที่ยอมรับได้, อังกฤษ: Feasible region, feasible set) — ในการวิจัยการดำเนินงาน การหาค่าเหมาะสม และการสร้างแบบจำลองทางคณิตศาสตร์ คือเซตของคำตอบที่เป็นไปได้ทั้งหมด (ชุดของค่าตัวแปร) ที่ ทุก ข้อจำกัดที่กำหนดไว้ในปัญหาได้รับการตอบสนอง

ขอบเขตของคำตอบที่ยอมรับได้คือปริภูมิย่อยที่ใช้ค้นหาคำตอบที่เหมาะสมที่สุด คำตอบใดก็ตามที่อยู่นอกขอบเขตนี้ถือว่าไม่ยอมรับได้

คำนิยามและการก่อตัว

ขอบเขตของคำตอบที่ยอมรับได้เกิดขึ้นจากการตัดกันของเซตที่กำหนดโดยข้อจำกัดแต่ละข้อของปัญหา ข้อจำกัดอาจอยู่ในรูปแบบต่าง ๆ ดังนี้:

• อสมการ: กำหนดขอบเขตบนหรือล่างสำหรับค่าของตัวแปรหรือการรวมกันของตัวแปร (เช่น "การใช้ทรัพยากร A ต้องไม่เกิน 100 หน่วย", "จำนวนสินค้าที่ผลิตต้องไม่น้อยกว่า 50 ชิ้น")
• สมการ: กำหนดให้เงื่อนไขต้องได้รับการตอบสนองอย่างแม่นยำ (เช่น "ปริมาณการขนส่งรวมต้องเท่ากับ 1,000 ตัน", "ความสมดุลของกระแสเข้าและออกเท่ากับศูนย์")
• เงื่อนไขเกี่ยวกับเครื่องหมายของตัวแปร: บ่อยครั้งตัวแปรต้องมีค่าไม่เป็นลบ เป็นจำนวนเต็ม หรืออยู่ในเซตแบบไม่ต่อเนื่องที่กำหนด

จุด (หรือเวกเตอร์ของค่าตัวแปร) อยู่ในขอบเขตของคำตอบที่ยอมรับได้ก็ต่อเมื่อมันตอบสนองข้อจำกัดทั้งหมดเหล่านี้พร้อมกัน

การแปลความทางเรขาคณิต

ขอบเขตของคำตอบที่ยอมรับได้มักมีการแปลความทางเรขาคณิตที่ชัดเจน โดยเฉพาะในปัญหาที่มีตัวแปรจำนวนน้อย:

• ในปริภูมิสองมิติ (2 ตัวแปร): ข้อจำกัดเชิงเส้นแต่ละข้อในรูปอสมการกำหนดครึ่งระนาบ ขอบเขตของคำตอบที่ยอมรับได้คือการตัดกันของครึ่งระนาบเหล่านี้ ซึ่งเป็นรูปหลายเหลี่ยมนูน (อาจไม่มีขอบเขตหรือว่างเปล่าได้)
• ในปริภูมิสามมิติ (3 ตัวแปร): ข้อจำกัดเชิงเส้นแต่ละข้อในรูปอสมการกำหนดครึ่งปริภูมิ ขอบเขตของคำตอบที่ยอมรับได้คือการตัดกันของครึ่งปริภูมิเหล่านี้ ซึ่งเป็นทรงหลายหน้านูน (polyhedron)
• ในปริภูมิหลายมิติ: ขอบเขตของคำตอบที่ยอมรับได้ที่กำหนดโดยข้อจำกัดเชิงเส้นคือทรงหลายหน้านูน (polytope)

ในกรณีของข้อจำกัดแบบไม่เชิงเส้น ขอบเขตของคำตอบที่ยอมรับได้อาจมีรูปร่างที่ซับซ้อนกว่าและไม่เป็นแบบนูน

บทบาทในการหาค่าเหมาะสม

ขอบเขตของคำตอบที่ยอมรับได้มีบทบาทพื้นฐานในการหาค่าเหมาะสม:

1. การกำหนดปริภูมิการค้นหา: คำตอบที่เหมาะสมที่สุดของปัญหา (หากมีอยู่) จะอยู่เสมอ ภายในขอบเขตของคำตอบที่ยอมรับได้หรือบนขอบเขตของมัน อัลกอริทึมการหาค่าเหมาะสมค้นหาค่าสุดขีดของฟังก์ชันวัตถุประสงค์ในบริเวณนี้ 2. การตรวจสอบการมีอยู่ของคำตอบ: หากขอบเขตของคำตอบที่ยอมรับได้เป็นเซตว่าง (กล่าวคือ ข้อจำกัดขัดแย้งกัน) ปัญหาก็ไม่มีคำตอบที่ยอมรับได้ และด้วยเหตุนี้จึงไม่มีคำตอบที่เหมาะสมที่สุดเช่นกัน 3. อิทธิพลต่อคำตอบที่เหมาะสมที่สุด: รูปร่างและขนาดของขอบเขตของคำตอบที่ยอมรับได้ส่งผลโดยตรงต่อความเป็นไปได้ในการบรรลุค่าสุดขีดของฟังก์ชันวัตถุประสงค์และต่อค่าของค่าสุดขีดนั้น

คุณสมบัติของขอบเขตของคำตอบที่ยอมรับได้ (ในการโปรแกรมเชิงเส้น)

ในปัญหาการโปรแกรมเชิงเส้น (Linear Programming) ที่ข้อจำกัดและฟังก์ชันวัตถุประสงค์ทั้งหมดเป็นเชิงเส้น ขอบเขตของคำตอบที่ยอมรับได้มีคุณสมบัติที่สำคัญ:

• ความนูน: หากจุดสองจุดอยู่ในขอบเขตของคำตอบที่ยอมรับได้ ส่วนของเส้นตรงทั้งหมดที่เชื่อมสองจุดนั้นก็อยู่ในขอบเขตด้วยเช่นกัน คุณสมบัตินี้รับประกันว่าคำตอบที่เหมาะสมที่สุด (หากมีและเป็นหนึ่งเดียว) จะอยู่ที่จุดยอดใดจุดยอดหนึ่งของทรงหลายหน้าของขอบเขตของคำตอบที่ยอมรับได้
• ความปิด: ขอบเขตของคำตอบที่ยอมรับได้รวมขอบของมันไว้ด้วย (เนื่องจากอสมการที่ไม่เข้มงวด ≤, ≥ และสมการ)

ขอบเขตของคำตอบที่ยอมรับได้อาจเป็น:

• มีขอบเขต: มีขนาดจำกัด
• ไม่มีขอบเขต: ขยายออกไปอย่างไม่สิ้นสุดในทิศทางหนึ่งหรือหลายทิศทาง
• ว่างเปล่า: ไม่มีจุดใดอยู่เลย

เอกสารอ้างอิง

• Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988.
• Акоф Р., Сасиени М. Основы исследования операций. — М.: Мир, 1971.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

ดูเพิ่มเติม

• การวิจัยการดำเนินงาน
• การหาค่าเหมาะสม
• แบบจำลองทางคณิตศาสตร์
• ข้อจำกัด
• คำตอบที่ยอมรับได้
• คำตอบที่เหมาะสมที่สุด
• ฟังก์ชันวัตถุประสงค์
• การโปรแกรมเชิงเส้น
• เซตนูน