Conceptos Fundamentales y Errores Comunes en Programación Lineal y Optimización

Fundamentos de Programación Lineal: Verdad o Falsedad

Este documento aborda y corrige doce afirmaciones clave relacionadas con la Programación Lineal (PL), el algoritmo Simplex, la dualidad y las características de las soluciones en problemas de optimización discretos y continuos.

Sección 1: Dualidad, Simplex y Soluciones Continuas

1. Afirmación 1: Variable Dual y Efecto Marginal

   En un problema lineal continuo con solución propia, la variable dual asociada 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 deja de ser válido para calcular dicho efecto marginal.

2. Afirmación 2: Costo Reducido y Solución Impropia

   Cuando la tabla terminal del algoritmo Simplex de un problema lineal continuo presenta algún costo reducido no adecuado al óptimo, la solución es impropia.

   Verdadero. Debido a que no existe ninguna variable de bloqueo que limite el valor de la variable entrante (lo que indica que la función objetivo puede crecer o decrecer sin límite).

3. Afirmación 4: Región Factible y Solución Impropia

   En un problema lineal continuo solo es posible obtener una solución impropia si la región factible correspondiente no es acotada.

   Verdadero. Una solución impropia (que no tiene solución finita) solo es posible si la Región Factible (RF) no está acotada, de forma que la función objetivo crece o decrece sin límites.

4. Afirmación 5: Número de Soluciones Factibles Básicas (SFB)

   En un problema lineal continuo con solución múltiple no acotada, el número de soluciones factibles básicas es infinito.

   Falso. El número de Soluciones Factibles Básicas (SFB) siempre es un número finito y está acotado por $\binom{n}{m}$, donde $n$ es el número de variables y $m$ el de restricciones.

5. Afirmación 8: Vértices y Solución Múltiple No Acotada

   Una condición necesaria para que la solución de un problema lineal continuo estandarizado sea propia múltiple no acotada es que su conjunto de restricciones posea infinitos vértices.

   Falso. La condición necesaria es que el conjunto de restricciones del problema lineal sea un conjunto no acotado. El número de vértices no puede ser infinito; estará acotado por $\binom{n}{m}$, donde $n$ es el número de variables y $m$ el de restricciones.

6. Afirmación 9: Variables Artificiales y Solución Propia

   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.

7. Afirmación 12: Multiplicador de Lagrange y Cambio de Base

   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.

Sección 2: Programación Binaria y Entera

3. Afirmación 3: Combinación Convexa en Problemas Binarios

   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. Esto es cierto en problemas lineales continuos. Pero en problemas binarios, al no ser la Región Factible (RF) convexa, esto no se cumple. 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.

4. Afirmación 6: Combinación Convexa en Problemas Enteros

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

   Falso. Pues al ser un problema lineal entero, pueden existir puntos de combinación lineal que no pertenezcan a la Región Factible (RF).

Sección 3: Problemas de Transporte y Asignación

7. Afirmación 7: Condición de Equilibrio en Emparejamiento

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

8. Afirmación 10: Soluciones Múltiples en Transporte Entero

   Un problema de transporte entero no puede tener soluciones propias múltiples.

   Falso. No hay ninguna relación que impida la existencia de soluciones propias múltiples en un problema de transporte entero.

9. Afirmación 11: Orígenes y Destinos en Asignación

   La igualdad entre el número de orígenes y destinos es una condición necesaria y suficiente para que un problema de asignación 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.