Transformación del Modelo Primal al Modelo Dual

• El número de restricciones del modelo primal es igual al número de variables del modelo dual.
• El número de variables del modelo primal es igual al número de restricciones del modelo dual.
• Se cambia el tipo de la Función Objetivo (FO): si es de Maximización (Max) a Minimización (Min), y viceversa.
• Los coeficientes de las restricciones de cada variable primal (x_i) son iguales a los coeficientes de las variables duales (y_i) en las restricciones del modelo dual.
• Los coeficientes de la Función Objetivo del modelo dual son iguales a los lados derechos de las restricciones del modelo primal.
• Si la Función Objetivo es de Minimización en el modelo primal, las restricciones del modelo dual son del tipo <=, y viceversa.
• Los coeficientes de la Función Objetivo del modelo primal son iguales a los lados derechos de las restricciones del modelo dual.
• Las variables duales (y_i) pertenecen a los números reales.

Método Simplex Dual

• Estandarización de las restricciones:
  • Para <= se añade una variable de holgura (s).
  • Para >= se resta una variable de exceso (-s) y se añade una variable artificial (r).
  • Para = se añade una variable artificial (r).
• Si existe una variable de exceso (-s), se multiplica la fila correspondiente por -1.
• Variables Básicas Iniciales: Z, s_i, r_i.
• Despejar Z (Función Objetivo).
• Construcción de la tabla inicial con los valores de la función objetivo despejada y las restricciones estandarizadas.
• Criterio de Salida: La variable básica que tenga el valor más negativo en la columna de la solución (lado derecho).
• Criterio de Entrada: El menor valor absoluto del cociente entre los coeficientes de la fila Z (costos reducidos) y los coeficientes correspondientes de la fila pivote (la fila que sale), considerando solo los cocientes negativos.
• Elemento Pivote: La intersección de la fila que sale y la columna que entra.
• Fila Pivote: Dividir todos los elementos de la fila pivote por el elemento pivote.
• Convertir en cero todos los valores por encima y por debajo del elemento pivote utilizando operaciones de fila (método de Gauss-Jordan).
• Condición de Parada: El proceso termina cuando no hay valores negativos en la columna de la solución. Si aún existen valores negativos, se repite el proceso.

Método Simplex Estándar

• Estandarización de las restricciones:
  • Para <= se añade una variable de holgura (s).
  • Para >= se resta una variable de exceso (-s) y se añade una variable artificial (r).
  • Para = se añade una variable artificial (r).
• Variables Básicas Iniciales: Z, s_i, r_i.
• Construcción de la tabla inicial.
• Criterio de Entrada:
  • Para Maximización (FO Max): Entra la variable no básica con el coeficiente más negativo en la fila Z.
  • Para Minimización (FO Min): Entra la variable no básica con el coeficiente más positivo en la fila Z.
• Criterio de Salida: La variable básica asociada al menor cociente no negativo entre los valores de la columna solución (lado derecho) y los coeficientes positivos correspondientes de la columna que entra (columna pivote). Se excluyen los valores negativos, cero y el valor de la fila Z.
• Elemento Pivote: La intersección de la fila que sale y la columna que entra.
• Fila Pivote: Dividir todos los elementos de la fila pivote por el elemento pivote.
• Convertir en cero todos los valores por encima y por debajo del elemento pivote utilizando operaciones de fila (método de Gauss-Jordan).
• Condición de Parada: El proceso termina cuando no hay variables candidatas a entrar en la fila Z (para Maximización, no hay valores negativos; para Minimización, no hay valores positivos). Si aún existen variables candidatas, se repite el proceso.

Análisis de Sensibilidad en Programación Lineal

1. Cambios que Afectan la Factibilidad

a. Cambios en los Lados Derechos de las Restricciones

• Se proporciona una tabla simplex final y un modelo de programación lineal con cambios en los lados derechos de las restricciones.
• Se aplica el cambio en el vector de lados derechos.
• Se utiliza la fórmula: (Matriz Inversa de la Base) * (Vector de Lados Derechos Modificado) = (Nuevo Vector de Lados Derechos de las Restricciones).
• La Matriz Inversa de la Base se obtiene de los coeficientes de las variables de holgura/exceso/artificiales (S) en la tabla simplex final, excluyendo la fila Z y la columna de la solución.
• Se actualiza la columna de la solución en la tabla simplex con el nuevo vector de lados derechos. El nuevo valor de Z se recalcula sustituyendo los valores de las variables básicas en la Función Objetivo original.
• Si el nuevo vector de lados derechos contiene valores negativos, se aplica el método Simplex Dual para recuperar la factibilidad.

b. Adición de Nuevas Restricciones

• Se parte de una tabla simplex óptima.
• Se estandariza la nueva restricción.
• Se prepara una nueva fila para la tabla simplex, correspondiente a la nueva restricción.
• Se identifican las variables básicas actuales que aparecen en la nueva restricción.
• Se expresan estas variables básicas en términos de las variables no básicas, utilizando las ecuaciones de la tabla simplex final.
• Se sustituyen estas expresiones en la nueva restricción y se realizan los cálculos.
• Los coeficientes resultantes se añaden como una nueva fila a la tabla simplex final.
• Si la nueva restricción no es satisfecha por la solución actual (resultando en un valor negativo en la columna de la solución para esta nueva fila), se aplica el método Simplex Dual.

2. Cambios que Afectan la Optimidad

a. Cambios en los Coeficientes de la Función Objetivo (c_j)

• El análisis consiste en identificar qué ocurre con la actual solución básica óptima en el caso que se cambien uno o varios de los coeficientes de la función objetivo. La actual solución óptima seguirá siéndolo en la nueva situación, siempre y cuando los costos reducidos correspondientes a los nuevos coeficientes, sean mayores o iguales a cero. El valor de la función objetivo cambia al cambiar los coeficientes en la nueva solución óptima.

b. Cambios en los Coeficientes Tecnológicos (a_ij) para Variables No Básicas

• Se proporciona una tabla simplex final, un modelo de programación lineal y el cambio en un coeficiente tecnológico (a_ij) de una variable no básica.
• Nota Importante:
  • Las variables duales (Y_i), o precios sombra, se obtienen de los coeficientes de las variables de holgura/exceso en la fila Z de la tabla simplex final.
  • Los coeficientes que acompañan a las Y_i en la restricción dual son los nuevos coeficientes tecnológicos (a_ij) de la variable afectada en las restricciones.
  • El término independiente de la restricción dual es el nuevo coeficiente de la variable afectada en la Función Objetivo (c_j).
  • La desigualdad de la restricción dual depende del tipo de Función Objetivo: >= para Maximización, <= para Minimización.
• Se formula la restricción dual asociada a la variable afectada, utilizando los nuevos coeficientes.
• Se despeja el costo reducido (C) de la variable afectada.
• Para calcular los nuevos coeficientes (a₁, a₂, etc.) en la tabla simplex, se utiliza la fórmula: (Matriz Inversa de la Base) * (Vector de Coeficientes Tecnológicos Modificados de la Variable) = (Nuevo Vector de Coeficientes en la Tabla).
• Se actualiza la columna de la variable afectada en la tabla simplex con los nuevos valores de c (costo reducido), a₁, a₂, etc.
• Condición de Optimidad:
  • Si la Función Objetivo es de Maximización y el costo reducido (C) es negativo, se itera con el Método Simplex.
  • Si la Función Objetivo es de Maximización y el costo reducido (C) es positivo o cero, la solución sigue siendo óptima.
  • Si la Función Objetivo es de Minimización y el costo reducido (C) es negativo o cero, la solución sigue siendo óptima.
  • Si la Función Objetivo es de Minimización y el costo reducido (C) es positivo, se itera con el Método Simplex.

c. Adición de Nuevas Actividades (Variables)

• Se proporciona una tabla simplex final, un modelo de programación lineal y los coeficientes de una nueva variable en la Función Objetivo y en las restricciones.
• Se conceptualiza el modelo de programación lineal con la nueva variable incorporada en la Función Objetivo y en las restricciones.
• Se prepara una nueva columna en la tabla simplex para la nueva variable, con los espacios para su costo reducido (c) y sus coeficientes (a₁, a₂, etc.).
• Nota Importante:
  • Las variables duales (Y_i), o precios sombra, se obtienen de los coeficientes de las variables de holgura/exceso en la fila Z de la tabla simplex final.
  • Los coeficientes que acompañan a las Y_i en la restricción dual son los coeficientes tecnológicos (a_ij) de la nueva variable en las restricciones.
  • El término independiente de la restricción dual es el coeficiente de la nueva variable en la Función Objetivo (c_j).
  • La desigualdad de la restricción dual depende del tipo de Función Objetivo: >= para Maximización, <= para Minimización.
• Se formula la restricción dual asociada a la nueva variable, utilizando sus coeficientes.
• Se despeja el costo reducido (C) de la nueva variable.
• Para calcular los coeficientes (a₁, a₂, etc.) de la nueva variable en la tabla simplex, se utiliza la fórmula: (Matriz Inversa de la Base) * (Vector de Coeficientes Tecnológicos de la Nueva Variable) = (Nuevo Vector de Coeficientes en la Tabla).
• Se actualiza la columna de la nueva variable en la tabla simplex con los valores de c (costo reducido), a₁, a₂, etc.
• Condición de Optimidad:
  • Si la Función Objetivo es de Maximización y el costo reducido (C) es negativo, se itera con el Método Simplex.
  • Si la Función Objetivo es de Maximización y el costo reducido (C) es positivo o cero, la solución sigue siendo óptima.
  • Si la Función Objetivo es de Minimización y el costo reducido (C) es negativo o cero, la solución sigue siendo óptima.
  • Si la Función Objetivo es de Minimización y el costo reducido (C) es positivo, se itera con el Método Simplex.

Fundamentos Teóricos del Análisis de Sensibilidad

Cambios que Afectan la Factibilidad

Cambios en el Lado Derecho de las Restricciones (Recursos b_j)

Interesa determinar si las actuales variables básicas se mantienen luego de aumentar o disminuir uno o más valores en el lado derecho de las restricciones del modelo. Hay que calcular nuevamente la columna de recursos de la tabla simplex. Si todos son positivos, la solución actual sigue siendo óptima pero cambiando los valores de las variables básicas y la función objetivo. Si algún valor se hace negativo, se pierde la factibilidad, la cual se recupera utilizando el método Simplex Dual.

Inclusión de una Nueva Restricción

Hay que determinar si la actual solución básica óptima se mantiene después de incorporar una nueva restricción al problema. Se evalúa la solución actual para verificar si satisface la nueva restricción. En caso afirmativo, la actual solución básica también lo será aun cuando se incluya la nueva restricción (es una restricción redundante). En caso de no cumplirse la restricción, se incorpora la nueva restricción a la tabla final Simplex y se procede a las iteraciones necesarias para encontrar la nueva solución básica óptima (se utiliza el método Simplex Dual).

Cambios que Afectan la Optimidad

Cambios en los Coeficientes de la Función Objetivo (c_j)

El análisis consiste en identificar qué ocurre con la actual solución básica óptima en el caso que se cambien uno o varios de los coeficientes de la función objetivo. La actual solución óptima seguirá siéndolo en la nueva situación, siempre y cuando los costos reducidos correspondientes a los nuevos coeficientes, sean mayores o iguales a cero. El valor de la función objetivo cambia al cambiar los coeficientes en la nueva solución óptima.

Cambios en el Uso de Recursos por Parte de las Actividades (a_ij)

Este cambio afecta la optimidad ya que afecta el lado izquierdo de las restricciones duales. El análisis se hace únicamente para las variables no básicas, ya que un cambio en los coeficientes de las variables básicas afecta la matriz inversa con la consiguiente complicación de cálculo. Si se pierde la optimidad, los cálculos para volver a obtenerla son los mismos que se hacen cuando se agrega una nueva variable o actividad.

Inclusión o Introducción de una Nueva Variable o Actividad

Se evalúa si la nueva variable hace un aporte significativo a la solución óptima del modelo original. Se pasa a calcular el costo reducido de la nueva variable, para decidir si la actual solución básica sigue siendo óptima en el problema aumentado con la nueva variable. La adición de una nueva actividad es equivalente a combinar el análisis de hacer cambios en la función objetivo y en el uso de los recursos.

Etiquetas: Análisis de Sensibilidad, Método Simplex, programación lineal, Simplex Dual