Politopo convexo

Archiu:3dpoly.svg

Un politopo convexo 3-dimensional

Un politopo convexo és un cas especial de politopo, que té la propietat adicional de que també és un conjunt convexo de punts en un espai $n$-dimensional ${ℝ}^n$. Alguns autors usen els térmens "politopo convexo" i "poliedre convexo" de manera intercanviable, mentres que uns atres preferixen fer una distinció entre les nocions de poliedre i de politopo.

Ademés, alguns texts requerixen que un politopo siga un conjunt acotat, mentres que atres (inclós este artícul) permeten que els politopos no tinguen llímits. Els térmens "politopo convexo acotat/no acotat" s'usaran a continuació quan el llímit siga crític per al problema tractat. No obstant, atres texts tracten un n-politopo convexo com una superfície o una (n-1)-varietat.

Els politopos convexos eixerciten un paper important tant en vàries branques de les matemàtiques com en ciències aplicades, especialment en programació llineal.

Un llibre complet i influent sobre el tema, cridat Convex Polytopes, va ser publicat en 1967 per Branko Grünbaum. En 2003 es va publicar la segona edició del llibre, en un important material adicional aportat pels nous redactors.

En el llibre de Grünbaum, i en alguns atres texts sobre geometria discreta, els politopos convexos a sovint es diuen simplement "politopos". Grünbaum senyala que açò és solament per a evitar la repetició interminable de la paraula "convexo", i que la discussió deu entendre's com a aplicable solament a la varietat convexa.

Un politopo es diu de dimensió total si és un objecte $n$ dimensional en Rⁿ.

Eixemples

• Numerosos eixemples de politopos convexos acotats es poden trobar en l'artícul poliedre.
• En el cas bidimensional, eixemples de politopos de dimensió completa són: un semiespacio, una franja entre dos llínees paraleles, una forma d'àngul (l'intersecció de dos semiplanos no paralels), una forma definida per una cadena poligonal convexa en dos rajos conectats als seus extrems, i un polígon convexo.
• Els casos especials d'un politopo convexo no acotat són una franja definida entre dos hiperplanos paralels, una falca definida per dos semiespacios no paralels, un cilindre (o prisma infinit) i un con polièdric (con infinit) definit per tres o més semiespacios que passen per un punt comú.

Definicions

Un politopo convexo es pot definir de vàries maneres, depenent de lo que siga més adequat per al problema en qüestió. La definició de Grünbaum és en térmens d'un conjunt convexo de punts en l'espai. Atres definicions importants són: com l'intersecció de semiespacios (representació de semiespacios) i com l'envolvente convexa d'un conjunt de punts (representació de vèrtiços).

Representació de vèrtiços (caixco convexo)

En el seu llibre Convex polytopes, Grünbaum definix un politopo convexo com un espai compacte convexo en un número finito de punts extrems:

Un conjunt $K$ de ${ℝ}^n$ és convexo si, per a cada parell de punts distints $a,b\in K$, el segment tancat en punts finals a i b està totalment contingut dins de $K$.

Açò equival a definir un politopo convexo acotat com l'envolvente convexa d'un conjunt finito de punts, a on el conjunt finito deu contindre el conjunt de punts extrems del politopo. Dita definició es denomina representació de vèrtiços (representació en V o descripció en V). Per a un politopo convexo compacte, la descripció en V mínima és única i està donada pel conjunt de vèrtiços del politopo.

Intersecció de semiespacios

Un politopo convexo pot definir-se com una intersecció d'un número finito de semiespacios. Dita definició es denomina representació de semiespacios (H-representació o H-descripció). Existixen infinites H-representacions d'un politopo convexo. No obstant, per a un politopo convexo de dimensió total, la descripció H mínima és de fet única i ve donada pel conjunt dels semiespacios que definixen els seus facetes.

Un semiespacio pot denotar-se com una desigualtat llineal:

$a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n\le b$

a on n és la dimensió de l'espai que conté el politopo donat. Per lo tant, un politopo convexo tancat pot considerar-se com el conjunt de solucions per a la desigualtat llineal:

$\begin{array}{cccccccccccccc}{a}_{11}{x}_1& & +& & a_{12}{x}_2& & +\cdots +& & a_{1n}{x}_n& & \le & & & b_1\\ a_{21}{x}_1& & +& & a_{22}{x}_2& & +\cdots +& & a_{2n}{x}_n& & \le & & & b_2\\ ⋮& & & & ⋮& & & & ⋮& & & & & ⋮\\ a_{m1}{x}_1& & +& & a_{m2}{x}_2& & +\cdots +& & a_{mn}{x}_n& & \le & & & b_m\\ \end{array}$

a on m és el número de semiespacios que definixen el politopo. Açò es pot escriure de forma concisa com la desigualtat matricial:

$Ax\le b$

a on A és una matriu d'orde m&claves;n, a on x és un vector columna de variables d'orde n&claves;1, i b és un vector columna de constants d'orde m&claves;1.

Un politopo obert convexo es definix de la mateixa manera, utilisant en les fòrmules desigualtats estrictes en lloc de les no estrictes.

Els coeficients de cada fila de A i b es corresponen en els coeficients de la desigualtat llineal que definix el semiespacio respectiu. Per lo tant, cada fila en la matriu es correspon en un hiperplano de respal del politopo, un hiperplano que delimita un semiespacio que conté el politopo. Si un hiperplano de soport també es creua en el politopo, es denomina un "hiperplano de delimitació" (ya que és un hiperplano de soport, solament pot intersecar el politopo en el llímit del politopo).

La definició anterior assumix que el politopo és de dimensió total. Si no ho és, llavors la solució de Ax ≤ b es troba en un espai afí propi de Rⁿ i la discussió del politopo pot estar restringida a este subespacio.

En general, l'intersecció de semiespacios arbitraris no necessita estar delimitada. No obstant, si es desija tindre una definició equivalent a la d'un caixco convexo, llavors el llímit deu ser considerat explícitament.

Teorema de base finita

La teorema de base finita és una extensió de la noció de descripció en V per a incloure politopos infinits. La teorema establix que un poliedre convexo és la combinació convexa dels seus vèrtiços més la suma cònica dels vectorés de les seues vores infinites.