Conceptos Fundamentales y Resolución de Problemas en Programación Lineal

A continuación, se abordan preguntas y conceptos esenciales en el ámbito de la programación lineal, incluyendo el método simplex, simplex dual, y la interpretación de variables y soluciones.

Soluciones Óptimas y Alternativas

1. ¿Cómo identificar un problema con infinitas soluciones?

Respuesta: Un problema tiene infinitas soluciones cuando, en el tableau final óptimo, existen variables NO básicas con costo reducido igual a cero. Estas variables permiten generar soluciones óptimas alternativas.

Método Simplex de Dos Fases e Infactibilidad

2. ¿Cómo comprobar la infactibilidad de un problema usando el método simplex de dos fases?

Respuesta: En la fase I, si en el tableau final hay variables artificiales en la base, la función objetivo artificial (min(w)) será distinta de cero. Esto indica que no existe una Solución Factible (ESF) y, por lo tanto, el problema es infactible.

Precios Sombra y Restricciones Activas

3. ¿Puede una restricción activa tener un precio sombra asociado igual a cero?

Respuesta: Sí, es posible. Los precios sombra representan los costos reducidos del problema dual y, por ende, el valor marginal de los recursos del primal. Un precio sombra de cero indica que no se está dispuesto a pagar por una unidad adicional de ese recurso.

Costo Reducido y Variables Entrantes

4. ¿Es incorrecto elegir una variable entrante con costo reducido negativo que no sea el más negativo?

Respuesta: No es incorrecto. Aunque se llegará al resultado óptimo, se requerirán más iteraciones en comparación con la elección de la variable con el costo reducido más negativo.

Condiciones de Borde para las Funciones Objetivo Primal y Dual

5. Límites o condiciones de borde para las funciones objetivo del problema primal y dual:

• Si la solución NO es óptima: min Z > max V
• Si la solución es óptima: min Z = max V
• Si el primal tiende a –∞: el dual es infactible
• Si el primal tiende a ∞: el dual es no acotado

Método Simplex-Dual e Infactibilidad

6. ¿Cómo comprobar la no factibilidad de un problema usando el método simplex-dual?

Respuesta: Se utiliza el criterio de factibilidad: min(θ) = {Cj / Asj} con Asj < 0. Si todos los Asj >= 0, la solución no es factible.

Conceptos Clave en Programación Lineal

7. Definiciones y comentarios:

• Solución básica degenerada: Ocurre cuando en la solución óptima, B=0, o una restricción es linealmente dependiente de otra (redundancia geométrica).
• Problema no acotado: Las variables pueden incrementarse indefinidamente sin violar restricciones. Usualmente indica un modelo mal construido.
• Problema sin solución óptima en fase II simplex: Ocurre cuando hay Cj<0 y todos los aj asociados son <= 0, impidiendo la entrada de variables.
• Soluciones óptimas alternativas: Se presentan cuando todos los Cj >= 0 y una variable no básica tiene Cj = 0.
• Problema con solución óptima en fase I, con w>0: Indica que el problema real es infactible, ya que se busca min(w) = 0 para pasar a la fase II.

Variables de Holgura y Artificiales

8. Diferencia entre variables de holgura y variables artificiales:

Respuesta: Las variables de holgura representan el exceso o escasez de recursos, transformando desigualdades en igualdades. Las variables artificiales se utilizan para construir una solución básica inicial, especialmente útil cuando no se dispone de una solución factible evidente.

Solución en Fase 2 del Método Simplex

9. Problema sin solución en fase 2 simplex:

En la fase 2, una solución óptima factible debe cumplir con las condiciones de optimalidad y factibilidad. Si el Espacio de Soluciones Factibles (ESF) no está acotado, la función objetivo puede aumentar o disminuir indefinidamente, indicando que no hay solución óptima.

Variables de Holgura y Duales en un Contexto Real (Operaciones Mineras)

10. Representación de las variables de holgura y duales en una PPL de operaciones mineras:

Variables de holgura: Indican la diferencia entre los recursos disponibles y los utilizados. Por ejemplo, la capacidad de chancado versus las toneladas efectivamente chancadas.

Variables duales: Reflejan el valor marginal por unidad de recurso adicional. Representan el precio máximo que se estaría dispuesto a pagar por una unidad adicional de un recurso (e.g., una tonelada más de mineral).

Condiciones de Borde y Factibilidad en Problemas Primal y Dual

11. Condiciones de borde de las funciones objetivo en términos de factibilidad:

• Si ambos problemas (primal y dual) son factibles, ambos tienen solución óptima finita.
• Si el primal no es factible y el dual es factible, el dual tiene un ESF no acotado.
• Si el primal es factible y el dual no es factible, el primal tiene un ESF no acotado.
• Si ambos problemas no son factibles, ambos tienen valores objetivos infinitos.

Variables Artificiales y Método Simplex de Dos Fases

12. Variables artificiales y el método de dos fases:

Variables artificiales: Inicialmente, cumplen la función de las variables de holgura en problemas con soluciones iniciales no evidentes. Luego, se eliminan.

Método de dos fases: La fase I busca una solución básica inicial. Si se encuentra, la fase II resuelve el problema original.