Дискретная оптимизация
Господа математики, а также технари и экономисты! Думаю, все Вы так или иначе
сталкиваетесь с задачами дискретной оптимизации, и ломаете голову над тем, как
же получить хотя бы приближенное (субоптимальное решение). Я лично вот в свое
время сломал зубы, хвост и все остальное, подыскивая метод для решения задачи
распределения множества потребителей ресурсов по множеству поставщиков ре-
сурсов, причем сами ресурсы - многомерные. Причем понятное дело, что ни потре-
бителей, ни поставщиков нельзя было делить на какие-либо составляющие части,
например нельзя распределить 2,81 специалистов на 3,72 проектов, или же в моем
случае, нельзя распределить 5,5 виртуальных машин на 2,7 физических компьютера.
Короче, надеюсь, все поняли, о чем речь. Вопрос - как Вы решаете подобные задачи.
Особенно интересуют жадные алгоритмы, которые согласно учебникам дают гаранти-
рованно оптимальный результат, если подмножество допустимых вариантов (удовле-
творяющих системе ограничений) является специальной структурой - матроидом...
Мне не очень понятно, как именно образом можно определить (причем, чтобы это не
оказалось по сложности сопоставимо с решением самой задачи), является ли допус-
тимая область матроидом или не является. В общем буду благодарен за любые мысли.
|