ผลต่างระหว่างรุ่นของ "01204512/weight bipartite matching"

รุ่นแก้ไขเมื่อ 04:34, 8 สิงหาคม 2555

เอกสารนี้เป็นส่วนหนึ่งของวิชา 01204512

เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph $G=(U\cup V,E)$ ที่มีน้ำหนัก $w(u,v)$ บนเส้นเชื่อม $(u,v)\in E$

เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้ เราจะให้ตัวแปร $x(u,v)$ มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก

Maximize $\sum _{(u,v)\in E}w(u,v)\cdot x(u,v)$
Subject to:
- for all $u\in U$ , $\sum _{(u,v)\in E}x(u,v)=1$
- for all $v\in V$ , $\sum _{(u,v)\in E}x(u,v)=1$
- for all $(u,v)\in E$ , $x(u,v)\in \{0,1\}$

เราจะ relax ปัญหาให้เป็น linear program โดยเปลี่ยนเงื่อนไขสุดท้ายเป็น

- For all $(u,v)\in E$ , $x(u,v)\geq 0$

จาก linear program ดังกล่าว เราสามารถหา dual program ได้ โดยสร้างตัวแปร $a(u)$ สำหรับทุก ๆ $u\in U$ (เงื่อนไขแรก) และตัวแปร $b(v)$ สำหรับทุก ๆ $v\in V$ (เงื่อนไขที่สอง) เนื่องจากเงื่อนไขเป็นสมการ (ไม่ใช่ อสมการ) ตัวแปร dual ทั้งสองจะเป็นแบบไม่ระบุขอบเขต

ด้านล่างเป็น dual linear program

Minimize $\sum _{u\in U}a(u)+\sum _{v\in V}b(v)$
Subject to:
- for all $(u,v)\in E$ , $a(u)+b(v)\geq w(u,v)$

@@ แถว 5: / แถว 5: @@
 เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้  เราจะให้ตัวแปร <math>x(u,v)</math> มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก
-* Minimize <math>\sum_{(u,v)\in E} w(u,v)\cdot x(u,v)</math>
+* Maximize <math>\sum_{(u,v)\in E} w(u,v)\cdot x(u,v)</math>
 * Subject to:
-** For all <math>u\in U</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
+** for all <math>u\in U</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
-** For all <math>v\in V</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
+** for all <math>v\in V</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
-** For all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>x(u,v)\in\{0,1\}</math>
+** for all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>x(u,v)\in\{0,1\}</math>
 เราจะ relax ปัญหาให้เป็น linear program โดยเปลี่ยนเงื่อนไขสุดท้ายเป็น
 ** For all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>x(u,v)\geq 0</math>
+จาก linear program ดังกล่าว เราสามารถหา dual program ได้ โดยสร้างตัวแปร <math>a(u)</math> สำหรับทุก ๆ <math>u\in U</math> (เงื่อนไขแรก) และตัวแปร <math>b(v)</math> สำหรับทุก ๆ <math>v\in V</math> (เงื่อนไขที่สอง)  เนื่องจากเงื่อนไขเป็นสมการ (ไม่ใช่ อสมการ) ตัวแปร dual ทั้งสองจะเป็นแบบไม่ระบุขอบเขต
+ด้านล่างเป็น dual linear program
+* Minimize <math>\sum_{u\in U} a(u) + \sum_{v\in V} b(v)</math>
+* Subject to:
+** for all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>a(u)+b(v)\geq w(u,v)</math>

ผลต่างระหว่างรุ่นของ "01204512/weight bipartite matching"

รุ่นแก้ไขเมื่อ 04:34, 8 สิงหาคม 2555

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ