http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B0%D1%8F_%D0%BE%D0%B1%D1%89%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C

Здравствуйте. Помогите пожалуйста составить формальную постановку задачи в терминах дискретного программирования.

Поделюсь некоторыми соображениями. Мне кажется задача походит на задачу линейного назначения или задачу нахождения максимального паросочетания в двудольном графе.
Следуя такой логике можно ввести управляемые переменные Xij ={0,1}, которые равны 1 если буква номер i из первой последователности соответствует букве номер j второй. Ц.ф. просто отражает желание, чтобы сумма всех Xij была максимальна. Также имеют место ограничения: для каждой буквы k сумма всех Xkj=1 или Xik=0. Но при такой постановке не хватает ограничений на порядок следования букв. Как записать это требования формально?