Así que he estado buscando en Internet algunas respuestas a esto, pero actualmente tengo un conjunto de restricciones lineales: $Ax = b, Cx \le d$ para las matrices $A \in \mathbb{R}^{n \times m}$ , $b\in \mathbb{R}^{n}$ , $C \in \mathbb{R}^{p \times m}$ y $d \in \mathbb{R}^{p}$ . Me gustaría deducir una fórmula para el volumen del conjunto de factibles $x$ que satisfacen estas restricciones. Sería estupendo si alguien pudiera indicarme una buena dirección, tal vez esto no se pueda resolver analíticamente, en este caso, ¿quizás haya una aproximación?
Respuestas
¿Demasiados anuncios?
Peter
Puntos
1681
He aquí un documento, cuya introducción le llevará a otros:
Lasserre, Jean B., y Eduardo S. Zeron. "Un nuevo algoritmo para el volumen de un politopo convexo". arXiv math/0106168 (2001).
Si quieres un algoritmo más rápido pero aproximado:
Emiris, Ioannis Z., y Vissarion Fisikopoulos. "Métodos eficientes de paseo aleatorio para aproximar el volumen de los politopos". En Actas del 13º Simposio de Geometría Computacional , p. 318. ACM, 2014. Enlace ACM .
También se aborda en una pregunta de MO de 2009: " Algoritmo para encontrar el volumen de un politopo convexo ."
Reddog
Puntos
121
El volumen del politopo convexo resultante viene dado por el coeficiente principal del El (cuasi)polinomio de Ehrhart si todas las matrices de su descripción del semiespacio son racionales (es decir, sólo tienen entradas racionales) y el poliedro resultante es compacto. Los cuasipolinomios de Ehrhart se pueden calcular utilizando Normaliz o Latte . Estos programas son de código abierto, así que si te interesa saber cómo funcionan los algoritmos, sólo tienes que echarle un vistazo.
