Алгоритм перебора соседних вершин многогранника - до 10 тыс. руб.
Здравствуйте!
Дано:
- система линейных неравенств, задающих многогранник
- координаты одной из его вершин
Найти:
- координаты всех соседних с данной вершин
Условия:
- система неравенств (уравнений) будет строиться из транспортной задачи линейного программирования размерности 10x10 - 15x15? т.е. в неравенствах будет от 100 до 225 переменных
- скорость вычислений должна составлять (желательно) не более 10-20 секунд
Дополнительная информация:
- интересует блок-схема, описание, доказательство скорости алгоритма, даже если он в это время не укладывается;
- если алгоритм не укладывается в указанное время, то подойдёт алгоритм, который выдаёт вершины поочереди (по N штук) и идёт искать дальше;
- алгоритм желательно написать в C# или MatLab, другое - по договорённости;
- также интересует теория всего этого вопроса;
- бюджет может быть как уменьшен, так и увеличен в зависимости от объёма работы.
Бюджет - 5-10 тыс.
С уважением, Сергей.
Дано:
- система линейных неравенств, задающих многогранник
- координаты одной из его вершин
Найти:
- координаты всех соседних с данной вершин
Условия:
- система неравенств (уравнений) будет строиться из транспортной задачи линейного программирования размерности 10x10 - 15x15? т.е. в неравенствах будет от 100 до 225 переменных
- скорость вычислений должна составлять (желательно) не более 10-20 секунд
Дополнительная информация:
- интересует блок-схема, описание, доказательство скорости алгоритма, даже если он в это время не укладывается;
- если алгоритм не укладывается в указанное время, то подойдёт алгоритм, который выдаёт вершины поочереди (по N штук) и идёт искать дальше;
- алгоритм желательно написать в C# или MatLab, другое - по договорённости;
- также интересует теория всего этого вопроса;
- бюджет может быть как уменьшен, так и увеличен в зависимости от объёма работы.
Бюджет - 5-10 тыс.
С уважением, Сергей.
- Предложение ещё актуально? Подойдёт ли программа на C++? Можно ли пользоваться сторонними библиотеками? от osseum, 24 февраля 2013 года
Писать такое я не буду - своих дел хватает, но первое что приходит в голову - нужно что-то похожее на симлекс метод.
Спасибо, возможно, что-то похожее. Симплекс идёт по вершинам по направлению оптимального решения, а не по соседним.
to osseum:
Уже есть не протестированный алгоритм, если не получится, обращусь к Вам.
Уже есть не протестированный алгоритм, если не получится, обращусь к Вам.