- เอกสารนี้เป็นส่วนหนึ่งของวิชา 01204512
เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph ที่มีน้ำหนัก บนเส้นเชื่อม
เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้ เราจะให้ตัวแปร มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก
- Minimize
- Subject to:
- For all ,
- For all ,
- For all