Maximální párování
Úloha číslo: 3253
Zformulujte problém nalezení maximálního párování v následujícím grafu jako problém celočíselného lineárního programování. Jak byste postupovali obecně?
Řešení
Pro každou hranu \(e\) zavedeme proměnnou \(x_i\), která udává, je-li hrana \(e_i\) ve vybraném maximálním párování. Úloha pak zní: \[\begin{eqnarray*} \max \sum_{e\in E} x_i w_i \\ \forall v_j\in V: \sum_{i:v_j\in e_i} x_i & \le & 1 \\ \forall e_i\in E: x_i & \in & \{0{,}1\} \end{eqnarray*}\]
Pro náš příklad máme úlohu \[\begin{eqnarray*} \max 7x_1 + 6x_2 + x_3 + 5x_4 + 3x_5 + 4x_6 + x_7 \\ x_1 + x_2 + x_3 & \le & 1\\ x_4 + x_5 & \le & 1\\ x_1 + x_4 & \le & 1\\ x_3 + x_5 + x_7 & \le & 1\\ x_2 + x_6 & \le & 1\\ x_6 + x_7 & \le & 1\\ x_i & \in & \{0{,}1\} \end{eqnarray*}\] s optimálním řešením \(\mathbf x=(1{,}0,0{,}0,1{,}1,0)\) o váze 14.
Všimněte si, že úloha hledání perfektního párování by měla v první skupině podmínek všude rovnost \(\forall v_j\in V: \sum_{i:v_j\in e_i} x_i = 1\).
Dále platí, že je-li graf bipartitní (jako náš příklad), má navíc každý vrchol mnohostěnu přípustných řešení celočíselné koeficienty (s netriviálním důkazem). Simplexovou metodou bychom tedy mohli takovou úlohu vyřešit.
