Problemas Lineales y Optimización: Preguntas Frecuentes

Verdadero o Falso

En todo problema lineal continuo siempre es preciso introducir variables artificiales con objeto de asegurar la obtención de una base canónica del espacio de restricciones

FALSO. Con la inclusión de variables de holgura podemos asegurar, en algunos casos, la obtención de una base canónica del espacio de restricciones.

Si un problema de emparejamiento tiene tantos orígenes como destinos se puede demostrar que poseerá solución propia

VERDADERO. Dado que los problemas de emparejamiento son un caso particular de los problemas de asignación, para los cuales la igualdad entre la cifra de orígenes y destinos se corresponde con la condición de equilibrado, que a su vez es la condición necesaria y suficiente para la existencia de solución propia en tal tipo de problemas.

Los procedimientos algorítmicos de resolución de problemas lineales continuos nunca pueden aplicarse para resolver problemas de transporte enteros

FALSO. También pueden aplicarse sobre problemas lineales enteros cuya matriz de restricciones sea unimodular total, puesto que se puede demostrar algebraicamente que la restricción de que las variables sean tal, puesto que asegura, pese a no formularse explícitamente. Este es el caso de los problemas de transportes enteros.

En un problema lineal continuo el número de multiplicadores de Lagrange es igual al número de restricciones del problema

CIERTO. Por definición, cada multiplicador de Lagrange de un problema lineal continuo con restricciones está vinculado a una restricción del problema.

Una condición suficiente para que un problema lineal continuo posea solución propia única es que este estandarizado

FALSO. Son cuestiones que no tienen ningún tipo de relación.

Los problemas de transporte enteros pueden resolverse mediante algoritmos de programación lineal continua dado que su matriz de restricciones es unimodular total

VERDADERO. Puesto que la matriz de restricciones de cualquier problema de transporte entero es unimodular total, es demostrable en términos algebraicos que la omisión de las restricciones de entereridad para su resolución no redunda en una pérdida de contenido matemático del problema.

Una condición suficiente para que un problema de asignación posea solución propia es que el número de restricciones sea menor que el número de variables

FALSO. La condición necesaria y suficiente para que posea solución propia un problema de asignación es que el número de orígenes tiene que ser igual al de destinos.

En un problema lineal continuo el número de multiplicadores de Lagrange es igual al número de variables artificiales del problema

FALSO. Cada multiplicador está vinculado al número de restricciones, no al número de variables.

Los problemas lineales continuos siempre poseen solución propia

FALSO. Pueden tener solución impropia. Ejemplo: Max f(x1,x2)=x1+x2 s.a x1,x2>=0

La condición necesaria y suficiente para que un problema de asignación posea solución propia viene dada por m=n

VERDADERA. Puesto que los problemas de asignación si=1; dj=1 y, por lo tanto, +si=m, +dj=n verificándose la condición de equilibrio exigida para tener solución propia. 2.3. es un grafo que es un grafo débilmente conexo.

Si en un problema lineal binario se han hallado dos vértices que son óptimos, su combinación lineal convexa también será óptima

FALSO. La combinación lineal convexa de vectores binarios no es binaria.

En un grafo finito todo camino entre dos vértices dados es también una cadena

VERDADERO. Dado que un camino es una secuencia de arcos adyacentes del mismo sentido, por lo que satisface la condición de cadena que exige solamente disponer de una secuencia de arcos adyacentes.

El algoritmo de Kruskal permite obtener el árbol generador óptimo de una red simétrica en n-1 iteraciones siendo n el número de nodos de la red

VERDADERO. Puesto que un árbol generador de una red es un grafo parcial con estructura de árbol y todo árbol con n nodos posee n-1 arcos o aristas. Puesto que en cada iteración el algoritmo selecciona una arista de la red simétrica, se precisan n-1 iteraciones para completar el árbol.

La inclusión de variables artificiales en un problema lineal continuo asegura que la solución del mismo sea propia

FALSO. La inclusión de variables artificiales viene motivada por la necesidad de disponer de una base canónica de vectores, no predeterminando el tipo de solución que pueda tener el problema.