Соседние грани многогранника в n-мерном пространстве (алгори

[PAV]

На самом деле я бы решал так (начинал решать). Берется требуемая грань, в соответствующем неравенстве ставится знак равенства, одна из переменных исключается из всей системы.

Далее поочередно перебирается каждая другая грань. Аналогично исключаем из системы одно уравнение и одну переменную.

Остается система неравенств, число переменных на две меньше, и требуется определить размерность области, которую эти неравенства ограничивают. Вот как это сделать просто я сообразить не могу.

[igrishin]

Я так тоже пробовал делать, но при большой размерности очень много приходится перебирать. Вот если бы был какой-то признак смежной грани!

[незваный гость]

igrishin писал(а):

Вот если бы был какой-то признак смежной грани!

То задача линейного программирования была бы весьма простой.

На самом деле даже просто заменять неравенство на равенство нельзя: нет никакой гарантии, что получившаяся гиперплоскость содержит грань…

[Vassil]

worm2 сослал на один перевод на русском языке Часто задаваемых вопросов по лин. прогр.: http://www.sampo.ru/~alexeyf/lp_faq.html

Там есть раздел:

В6.7: “Ищу алгоритм, находящий выпуклую оболочку
конечного числа точек в n-мерном пространстве”

Не помогает ли он найти ответ Вашему вопросу?

[igrishin]

Спасибо за ссылку! Попробуем использовать этот материал, а также программы, которвые предлагаются там.