ปัญหาการปกคลุมเซต

ปัญหาการปกคลุมเซต (อังกฤษ: set covering problem) เป็นปัญหาในทฤษฎีความซับซ้อน วิทยาการคอมพิวเตอร์ และคณิตศาสตร์เชิงการจัด และได้รับการพิสูจน์ว่าเป็นปัญหาเอ็นพีบริบูรณ์ในพ.ศ. 2515

ปัญหาการปกคลุมเซตหมายถึง แบบจำลองทางคณิตศาสตร์ ซึ่งใช้ในการแก้ปัญหาการตัดสินใจ โดยใช้เมตริกซ์ 0-1 ช่วยในการจำลองสถานการณ์ โดยมีวัตถุประสงค์ให้ตัวแทนที่เลือกมามีความครอบคลุมกลุ่มเป้าหมายทั้งหมด ซึ่งอาจมีตัวแทนได้มากกว่า 1 เช่น การตั้งศูนย์บริการใหม่ให้มีความครอบคลุมกลุ่มลูกค้า อย่างน้อย 1 แห่ง กำหนดให้หากศูนย์บริการ j สามารถให้บริการได้ถึงพื้นที่ i ให้มีค่าเท่ากับ 1, หากไม่ใช่ให้มีค่าเท่ากับ 0

ณกร อินทร์พยุง (2548) กล่าวไว้ว่า ในปัญหาการตัดสินใจที่มีเงื่อนไขแบบ Set Covering (SCP) เราพิจารณาว่าปัญหานั้นมีลักษณะเป็นเมตริกซ์ 0-1 ที่มีแถว i โดยที่ { i = 1,2,3…,m} และมีคอลัมน์ j โดยที่ { j = 1,2,3..,n} เรากำหนดให้ X เป็นตัวแปรในการตัดสินใจที่มีค่าแบบไบนารี Xj = 1 ถ้า คอลัมน์ j (ซึ่งมีค่าใช้จ่าย Cj ) ถูกเลือก Xj = 0 ในกรณีอื่น ๆ สมมติว่าเราต้องการแก้ปัญหาการตัดสินใจที่ต้องการคำตอบที่มีค่าน้อยที่สุด (Minimization problem) เราสามารถเขียนฟังก์ชันวัตถุประสงค์และเงื่อนไขให้อยู่ในรูปสมการทางคณิตศาสตร์ได้ดังนี้

ฟังก์ชันวัตถุประสงค์ (Objective function) : Min ∑ Cj Xj

ภายใต้เงื่อนไข (Constraints) : ∑ Aij Xj ≥ 1

Xj = {0, 1} ; j = 1,2,3…,n

โดยที่ Aij คือ เมตริกซ์ 0,1 ขนาด i x j และ Cj คือ ค่าใช้จ่ายของคอลัมน์ j