Verdadero o Falso: 15 Afirmaciones sobre Investigación de Operaciones

Verdadero o Falso: Afirmaciones sobre Investigación de Operaciones

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.

Un problema de emparejamiento no puede tener soluciones propias múltiples. FALSO, no hay ninguna relación entre ambas cuestiones.

Todo grafo finito débilmente conexo también es un árbol. FALSO, un árbol es un grafo finito débilmente conexo sin ciclos.

Un problema de transporte entero no puede tener soluciones propias múltiples. FALSO, no hay ninguna relación entre ambas cuestiones.

Un grafo finito con estructura de árbol también es un bosque. VERDADERO, dado que un árbol es un grafo débilmente conexo sin ciclos mientras que un bosque es un grafo sin ciclos.

El algoritmo simplex no converge en presencia de ciclado. VERDADERO, dado que ante una situación de ciclado cambiar de base no implica cambiar de vértice, de modo que al cabo de un cierto número de iteraciones se tendrá una secuencia repetida de tablas, ninguna de las cuales será terminal.

Si en un problema lineal de asignación se han hallado dos vértices que son óptimos, su combinación lineal convexa también será óptima. FALSO, puesto que en los problemas lineales de asignación, por ser binarios, la combinación convexa de dos puntos puede generar vectores con alguna componente que no sea ni 0 ni 1.

En un problema de transporte entero la unimodularidad total de la matriz de restricciones constituye una condición suficiente para la existencia de una solución propia. FALSO, la condición necesaria y suficiente para que un problema de transporte posea solución propia es que esté equilibrado. La unimodularidad total de la matriz de restricciones da lugar a que el problema de transporte entero se pueda reformular de modo equivalente omitiendo la condición de entereridad.

En un problema lineal continuo con solución propia, el multiplicador de Lagrange asociado a la restricción i-ésima del problema permite calcular el efecto marginal sobre la función objetivo de un cambio unitario en el término independiente de dicha restricción. FALSO, puesto que si el cambio unitario en el término independiente provoca un cambio de base, el multiplicador de Lagrange asociado a la tabla óptima anterior no permite computar el efecto marginal considerado.

Los problemas lineales enteros en forma estándar cuya matriz de restricciones es unimodular total poseen solución propia. FALSO, la unimodularidad total no es condición necesaria ni suficiente para la existencia de solución propia.

La igualdad entre el número de orígenes y destinos es una condición necesaria y suficiente para que un problema de emparejamiento posea solución propia. VERDADERO, dado que un problema de emparejamiento es un caso particular de un problema de asignación, para los cuales la igualdad de orígenes y destinos es condición necesaria y suficiente para la existencia de solución propia.

En un problema lineal continuo, una condición necesaria para que X sea un punto óptimo del problema es que sea un vértice del conjunto de soluciones posibles. FALSO, en el caso de soluciones múltiples, hay puntos que son óptimos pero no vértices.

En un problema lineal con solución propia, el valor del precio dual proporcionado por LINGO, asociado a una determinada restricción del problema, indica siempre cuál es la variación del valor óptimo de la función objetivo inducida por un cambio unitario en el término independiente de dicha restricción. FALSO, por cuanto una variación unitaria del término independiente de la restricción i-ésima no necesariamente tiene que pertenecer al intervalo de variación compatible con la base.

Una condición necesaria y suficiente para que un problema de emparejamiento posea solución propia es que esté equilibrado. VERDADERA, la condición enunciada se corresponde con un teorema de existencia de solución propia para cualquier problema de transporte (respecto de los cuales los problemas de emparejamiento son un caso particular).

Una condición necesaria para que un vector del conjunto de restricciones sea una solución óptima del problema es que sea un punto de adherencia de dicho conjunto. En programación lineal continua, toda solución óptima es siempre un punto de borde del conjunto de restricciones. A su vez, los puntos de borde son puntos frontera que pertenecen al conjunto de restricciones. Puesto que ser un punto frontera constituye una condición suficiente para ser punto de adherencia, se colige que toda solución óptima debe ser también punto de adherencia y por tanto que la proposición es verdadera.

Una condición suficiente para que una decisión no sea óptima es que sea un punto interior del conjunto de restricciones. En programación lineal continua, una condición necesaria para la optimidad es pertenecer al borde del conjunto de restricciones. Por otra parte, los puntos del conjunto de restricciones que no pertenecen al borde de dicho conjunto son puntos interiores del conjunto. En consecuencia, no pertenecer al borde del conjunto de un punto y por lo tanto, la proposición es verdadera.

Si un vector del conjunto de restricciones es un óptimo local del problema no es necesariamente tiene por qué ser un óptimo global. Los problemas lineales continuos son programas convexos que por lo tanto satisfacen el teorema fundamental de la convexidad, el cual, entre otras cuestiones, permite asegurar que todo óptimo local de un programa convexo sea también global. Por lo tanto, la proposición es falsa.

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 predominando el tipo de solución que puede tener el problema.