ปัญหาการปกคลุมเซต (อังกฤษ: 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
อ้างอิง - [https://web.archive.org/web/20090623074522/http://www.logistics-adviser.com/ Archived 2009-06-23 ที่ เวย์แบ็กแมชชีน ที่มาแหล่งอ้างอิง อนุญาตให้เผยแพร่ตามสัญญาเอกสารเสรีของกนู]
ญหาการปกคล, มเซต, บทความน, องการการจ, ดหน, ดหมวดหม, ใส, งก, ภายใน, หร, อเก, บกวาดเน, อหา, ให, ณภาพด, ณสามารถปร, บปร, งแก, ไขบทความน, ได, และนำป, ายออก, จารณาใช, ายข, อความอ, นเพ, อช, ดข, อบกพร, องบทความน, อาจต, องเข, ยนใหม, งหมดเพ, อให, เป, นไปตามมาตรฐานค, ณภา. bthkhwamnitxngkarkarcdhna cdhmwdhmu islingkphayin hruxekbkwadenuxha ihmikhunphaphdikhun khunsamarthprbprungaekikhbthkhwamniid aelanapayxxk phicarnaichpaykhxkhwamxunephuxchichdkhxbkphrxngbthkhwamnixactxngekhiynihmthnghmdephuxihepniptammatrthankhunphaphkhxngwikiphiediy hruxkalngdaeninkarxyu khunchwyeraid hnaxphiprayxacmikhxesnxaenapyhakarpkkhlumest xngkvs set covering problem epnpyhainthvsdikhwamsbsxn withyakarkhxmphiwetxr aelakhnitsastrechingkarcd aelaidrbkarphisucnwaepnpyhaexnphibriburninph s 2515pyhakarpkkhlumesthmaythung aebbcalxngthangkhnitsastr sungichinkaraekpyhakartdsinic odyichemtriks 0 1 chwyinkarcalxngsthankarn odymiwtthuprasngkhihtwaethnthieluxkmamikhwamkhrxbkhlumklumepahmaythnghmd sungxacmitwaethnidmakkwa 1 echn kartngsunybrikarihmihmikhwamkhrxbkhlumklumlukkha xyangnxy 1 aehng kahndihhaksunybrikar j samarthihbrikaridthungphunthi i ihmikhaethakb 1 hakimichihmikhaethakb 0nkr xinthrphyung 2548 klawiwwa inpyhakartdsinicthimienguxnikhaebb Set Covering SCP eraphicarnawapyhannmilksnaepnemtriks 0 1 thimiaethw i odythi i 1 2 3 m aelamikhxlmn j odythi j 1 2 3 n erakahndih X epntwaeprinkartdsinicthimikhaaebbibnari Xj 1 tha khxlmn j sungmikhaichcay Cj thukeluxk Xj 0 inkrnixun smmtiwaeratxngkaraekpyhakartdsinicthitxngkarkhatxbthimikhanxythisud Minimization problem erasamarthekhiynfngkchnwtthuprasngkhaelaenguxnikhihxyuinrupsmkarthangkhnitsastriddngnifngkchnwtthuprasngkh Objective function Min Cj Xjphayitenguxnikh Constraints Aij Xj 1Xj 0 1 j 1 2 3 nodythi Aij khux emtriks 0 1 khnad i x j aela Cj khux khaichcaykhxngkhxlmn j 1 xangxing aekikh https web archive org web 20090623074522 http www logistics adviser com Archived 2009 06 23 thi ewyaebkaemchchin thimaaehlngxangxing xnuyatihephyaephrtamsyyaexksaresrikhxngknu ekhathungcak https th wikipedia org w index php title pyhakarpkkhlumest amp oldid 9651027, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม