Siguiente: Combinatoria Un nivel arriba: Algunos problemas principales completos-NP Anterior: Algunos problemas principales completos-NP

Programación lineal

Un funcional lineal en $I\!\! R^n$ está dado por un vector $\mbox{\bf c}\in I\!\! R^{n}$ , mediante la aplicación $\mbox{\bf x} \mapsto \mbox{\bf c}^T\mbox{\bf x}$ . El problema de la programación lineal entera consiste en decidir si existe un vector con coordenadas enteras en un poliedro determinado por un conjunto de desigualdades lineales, con coeficientes enteros, que hace tomar a un funcional lineal un valor suficientemente grande. Formalmente:

Instancia:
$\begin{pagi}{34}Una matriz $\mbox{\bf A}\in Z\!\!\!Z^{m\times n}$ , % un vector ... ...\mbox{\bf c}\in Z\!\!\!Z^{n}$\space y % un valor \lq\lq grande'' $v\in Z$ .\end{pagi}$
Solución:
$\begin{pagi}{34}$\left\{\begin{array}{ll} 1 &\mbox{\rm si $\exists\mbox{\bf x}\... ...x}\geq v)$ , } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$\end{pagi}$

Guillermo Morales-Luna
2000-07-10