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

ปัญหาการปกคลุมเซต () เป็นปัญหาในทฤษฎีความซับซ้อน วิทยาการคอมพิวเตอร์ และคณิตศาสตร์เชิงการจัด และได้รับการพิสูจน์ว่าเป็นปัญหาเอ็นพีบริบูรณ์ในพ.ศ. 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

อ้างอิง