November 22nd, 2013

внутренний мир

За что я люблю математику и дочь её, информатику

"Есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны  и они друг другу. Нужно поженить максимальное число пар со взаимной симпатией. Введём переменные x_{ij}, которые соответствуют паре из i-того юноши и j-той девушки и удовлетворяют ограничениям:






0\leqslant x_{ij}\leqslant 1,



x_{1i}+x_{2i}+\ldots+x_{ni}\leqslant 1,



x_{i1}+x_{i2}+\ldots+x_{im}\leqslant 1,


с целевой функцией f=x_{11}+x_{12}+\ldots+x_{nm}. Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить." (отсюда)

Прекрасный, совершенный, понятный мир.