Fundamentos de Programación Lineal y Aplicaciones del Algoritmo Simplex

Ejercicios de Programación Lineal y Algoritmo Simplex

1. Objetivos de las Fases del Algoritmo Simplex

Describa el objetivo de la Fase I y el de la Fase II del algoritmo Simplex (3 puntos)

R:

• Fase I: El objetivo es encontrar una primera solución básica factible para el problema o, en su defecto, concluir que el problema no tiene solución (es infactible).
• Fase II: El objetivo es que, a partir de la solución factible obtenida en la fase anterior, se encuentre la solución óptima (o soluciones óptimas alternativas) o bien se concluya que el problema es no acotado.

2. Condiciones y Definiciones del Precio Sombra Negativo

Indique en qué condiciones un precio sombra es negativo y exponga una de las dos definiciones de ese precio sombra negativo (3 puntos)

R:

Un precio sombra es negativo cuando se varía el término libre de una restricción activa que representa un requerimiento del tipo mayor o igual (≥).

Definiciones:

• Definición 1: Es la tasa de empeoramiento que experimenta el valor óptimo de la función objetivo cuando se aumenta en una unidad el término libre de la restricción.
• Definición 2: Es la tasa de mejoramiento que experimenta el valor óptimo de la función objetivo cuando se disminuye en una unidad el término libre de la restricción.

3. Relación entre Problema Dual y Primal

¿Qué representa el problema DUAL de un modelo PRIMAL? (2 puntos)

R: Es el modelo matemático necesario para calcular los precios sombra de las restricciones del problema primal, proporcionando una perspectiva económica y de sensibilidad sobre los recursos.

4. Análisis de Tabla Simplex y Condiciones de Optimalidad

Suponga que en un problema de maximización usted ha obtenido la siguiente tabla:

Indique las condiciones que deben cumplir las constantes literales: a1, a2, c1, c2 y b; para que las siguientes aseveraciones sean verdaderas: (7 puntos)

a. Solución óptima y alternativa

La presente solución es óptima y existe una solución óptima alternativa que se obtiene haciendo entrar X1 a la base y haciendo salir H3 de ella. (2 puntos)

R: c1 = 0; a2 > 0; c2 > 0; b ≥ 0; a1 = cualquiera.

b. Mejora de la función objetivo

La presente solución básica es factible pero la función objetivo puede ser mejorada reemplazando H1 por X2 como variable básica. (3 puntos)

R: c1 > 0; a2 = cualquiera; c2 < 0; a1 > 0; b ≥ 0; (b / 5) < (20 / a1).
R: c1 > 0; a2 = cualquiera; c2 < 0; a1 > 0; b ≤ 0; b ≥ 0.

c. Problema no acotado

La presente solución básica es factible pero el problema de programación lineal es no acotado. (2 puntos)

R: c1 < 0; a2 > 0; a2 < 0; c2 > 0; a1 = cualquiera; b ≥ 0.

5. Modelado de Transporte y Carga

R:

Sean Xij = Cantidad de toneladas de la carga i que se llevará en el compartimiento j (donde i = 1, 2, 3, 4; y j = D, C, T).

Función Objetivo:
MAX Z = 320(X1D + X1C + X1T) + 400(X2D + X2C + X2T) + 360(X3D + X3C + X3T) + 290(X4D + X4C + X4T)

Sujeto a:

• X1D + X1C + X1T ≤ 20
• X2D + X2C + X2T ≤ 16
• X3D + X3C + X3T ≤ 25
• X4D + X4C + X4T ≤ 13
• X1D + X2D + X3D + X4D ≤ 12
• X1C + X2C + X3C + X4C ≤ 18
• X1T + X2T + X3T + X4T ≤ 10
• 500X1D + 700X2D + 600X3D + 400X4D ≤ 7000
• 500X1C + 700X2C + 600X3C + 400X4C ≤ 9000
• 500X1T + 700X2T + 600X3T + 400X4T ≤ 5000

Restricciones de equilibrio:

• (X1D + X2D + X3D + X4D) / 12 = (X1C + X2C + X3C + X4C) / 18
  O bien: 18(X1D + X2D + X3D + X4D) - 12(X1C + X2C + X3C + X4C) = 0
• (X1C + X2C + X3C + X4C) / 18 = (X1T + X2T + X3T + X4T) / 10
  O bien: 10(X1C + X2C + X3C + X4C) - 18(X1T + X2T + X3T + X4T) = 0

6. Resolución y Análisis de Resultados

R b) Resolviendo el sistema de ecuaciones entre B y E se obtiene para el punto de máximo: X1 = 13,46; X2 = 15 y Z = 632,36.

Resolviendo el sistema de ecuaciones entre A y F se obtiene para el punto de mínimo: X1 = 3,3; X2 = 4,08 y Z = 165,45.

R c) Si la restricción E no existe, el punto óptimo se traslada a la intersección de B con C. Resolviendo el sistema de ecuaciones entre B y C se obtiene para el punto de máximo: X1 = 9,49; X2 = 18,84 y Z = 660,59. Esto implica un diferencial de mayor ganancia de 28,22, que sería lo máximo que se estaría dispuesto a pagar por eliminar la restricción E.

7. Formulación del Problema Dual

R d) MAX Y = 60P1 + 812P2 + 56P3 + 72P4 + 15P5 + 90P6

Sujeto a:

• 12P1 + 28P2 - 8P3 + 6P4 + 5P6 ≤ 18
• 5P1 + 29P2 + 7P3 - 12P4 + P5 + 18P6 ≤ 26
• P1, P6 ≥ 0
• P2, P3, P4, P5 ≤ 0

Condiciones adicionales: 0; ≥ 0; > 0;