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

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

Primal และ Dual linear programs

เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

G=(U\cup V,E)

ที่มีน้ำหนัก

Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 929686278 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Fri, 11 Sep 2026 16:58:08 GMT Sensitive client information IP address: 158.108.32.49

บนเส้นเชื่อม

(u,v)\in E

เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้ เราจะให้ตัวแปร $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

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)$

Complementary slackness

เงื่อนไข complementary slackness บอกเราว่าที่คู่ของคำตอบที่เป็น optimal solutions ของคู่ primal/dual linear programs, ถ้าตัวแปรใน primal มีค่าไม่เท่ากับศูนย์ เงื่อนไขที่สอดคล้องกับตัวแปรนั้นใน dual จะต้อง tight, นั่นคือเป็นจริงด้วยเครื่องหมายเท่ากับ

ในกรณีนี้ นั่นคือ ใน optimal solution ถ้า $x(u,v)\neq 0$ , แล้วเราจะได้ว่า $a(u)+b(v)=w(u,v)$

เราจะพยายามใช้ complementary slackness นำทางเราไปสู่คำตอบ โดยเราจะเลือกเส้นเชื่อมใส่ใน matching ก็ต่อเมื่อตัวแปร dual ของเราบนเส้นเชื่อมนั้นสอดคล้องกับ complementary slackness นั่นคือ เส้นเชื่อมนั้น tight (i.e., $a(u)+b(v)=w(u,v)$ )

@@ แถว 1: / แถว 1: @@
 : ''เอกสารนี้เป็นส่วนหนึ่งของวิชา [[01204512]]''
+==Primal และ Dual linear programs==
 เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching  ให้ bipartite graph <math>G = (U\cup V,E)</math> ที่มีน้ำหนัก <math>w(u,v)</math> บนเส้นเชื่อม <math>(u,v)\in E</math>
@@ แถว 5: / แถว 7: @@
 เราเขียน 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>
+==Complementary slackness==
+เงื่อนไข complementary slackness บอกเราว่าที่คู่ของคำตอบที่เป็น optimal solutions ของคู่ primal/dual linear programs, ถ้าตัวแปรใน primal มีค่าไม่เท่ากับศูนย์  เงื่อนไขที่สอดคล้องกับตัวแปรนั้นใน dual จะต้อง tight, นั่นคือเป็นจริงด้วยเครื่องหมายเท่ากับ
+ในกรณีนี้ นั่นคือ ใน optimal solution ถ้า <math>x(u,v)\neq 0</math>, แล้วเราจะได้ว่า <math>a(u)+b(v)=w(u,v)</math>
+เราจะพยายามใช้ complementary slackness นำทางเราไปสู่คำตอบ โดยเราจะเลือกเส้นเชื่อมใส่ใน matching ก็ต่อเมื่อตัวแปร dual ของเราบนเส้นเชื่อมนั้นสอดคล้องกับ complementary slackness นั่นคือ เส้นเชื่อมนั้น tight (i.e., <math>a(u)+b(v)=w(u,v)</math>)
+==Primal-dual algorithms==

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

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

Primal และ Dual linear programs

Error

Error

Complementary slackness

Primal-dual algorithms

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ