Resolución de Problemas de Programación Lineal: Conceptos y Ejemplos

Problemas de Transporte y Unimodularidad

– Los problemas de transporte enteros pueden resolverse mediante algoritmos de programación lineal continua dado que su matriz de restricciones es unimodular total: CIERTO. 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 integralidad para su resolución no redunda en una pérdida de contenido matemático del problema.

– 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 integralidad.

Problemas Lineales Binarios y Continuos

– 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, dado que la combinación lineal convexa de vectores binarios no es, en general, binaria. Como ilustración, considérense los vectores (1, 0) y (0, 1): para ₁ = ₂ = 0.5, el vector que se genera por combinación lineal convexa es (0.5, 0.5).

– Los problemas lineales continuos siempre poseen solución propia: FALSO. Considérese como contraejemplo el siguiente problema lineal continuo, cuya solución es impropia.

Problemas de Asignación y Emparejamiento

– La condición necesaria y suficiente para que un problema de asignación posea solución propia viene dada por m = n (donde m designa el número de orígenes y n el de destinos): CIERTO, puesto que en los problemas de asignación s_i = 1; d_j = 1 y, por lo tanto, se verifica la condición de equilibrio exigida para tener solución propia.

– 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 sea igual al de destinos.

– Si un problema de emparejamiento tiene tantos orígenes como destinos, se puede demostrar que poseerá solución propia: CIERTO, 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 equilibrio, que a su vez es la condición necesaria y suficiente para la existencia de solución propia en tal tipo de problemas.

– Una condición necesaria y suficiente para que un problema de emparejamiento posea solución propia es que esté equilibrado: CIERTO. 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).

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

– 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: CIERTO, 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.

Multiplicadores de Lagrange y Variables Artificiales

– 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 de Lagrange está vinculado a una restricción del problema, no a las variables artificiales.

– 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.

– En un problema lineal continuo con solución propia, el multiplicador de Lagrange (variable dual) asociado a la restricción i-ésima del problema permite en todos los casos 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.

– En un problema lineal continuo con solución propia, el multiplicador de Lagrange (variable dual) 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.

– En un problema lineal continuo, el número de multiplicadores de Lagrange (variables duales) 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.

– 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.

Resolución y Teoremas

– 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, en tal supuesto, se puede demostrar algebraicamente que la restricción de que las variables sean enteras queda asegurada pese a no formularse explícitamente. Este es el caso de los problemas de transporte enteros.

– En un problema lineal continuo, una condición necesaria para que un vector 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.

– Analice si el problema verifica el teorema de Weierstrass. ¿Qué implicaciones tiene ese hecho para la resolución del problema? El conjunto de restricciones es cerrado, tal como sucede con el conjunto de restricciones de cualquier problema lineal continuo (recuérdese que dicho conjunto, de no ser vacío, siempre puede expresarse como intersección finita no vacía de semiespacios cerrados engendrados por hiperplanos). Por otra parte, dicho conjunto es acotado. Considere, por ejemplo, una bola abierta con centro en el punto (0, 0) y radio 10.

– ¿Para qué valor de c₂ el problema poseerá una solución propia múltiple no acotada? Una condición necesaria para que un problema lineal continuo tenga solución propia múltiple no acotada es que el conjunto de restricciones, siendo no vacío, no esté acotado. Este hecho no se verifica en nuestro caso, tal como se desprende de la respuesta a la cuestión anterior, por lo que no es posible tener una solución propia múltiple no acotada.

– ¿Cuál es la expresión analítica de la solución si c₂ = 1? Cuando los problemas lineales continuos poseen solución propia, ésta se encuentra en al menos un vértice del conjunto de restricciones (recuérdese el teorema de caracterización de los problemas lineales continuos). En nuestro caso, el valor de la función objetivo en los distintos vértices es: f(0, 0) = 0; f(2.5, 2.5) = 2.5 + 2.5c₂ y f(5, 0) = 5. Si c₂ = 1 entonces la función objetivo vale 5 en los vértices (2.5, 2.5) y (5, 0). Puesto que los problemas lineales continuos son programas convexos y, por lo tanto, satisfacen el teorema fundamental de la convexidad, también será óptima cualquier combinación lineal convexa de los dos vértices indicados, siendo la expresión analítica de la solución (geométricamente es el segmento que une los vértices en cuestión):

Otros Conceptos

– 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.

– El algoritmo simplex no converge en presencia de ciclado: CIERTO, 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.

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

– 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.

– Una condición suficiente para que un problema lineal continuo posea solución propia única es que esté estandarizado: FALSO. Son cuestiones que no tienen ningún tipo de relación.