0% encontró este documento útil (0 votos)
67 vistas8 páginas

Ensayo 1

Descargar como docx, pdf o txt
Descargar como docx, pdf o txt
Descargar como docx, pdf o txt
Está en la página 1/ 8

UNIVERSIDAD POLITÉCNICA DE TULANCINGO

Ingeniería Industrial

Materia:

U Optimización y Mejora de procesos

Alumnos:

Jessica Martinez Mendoza

Grupo:

82

P Profesora:

Mtra. Reyna Adriana Marroquín Gayoso

Fecha:

28 de Marzo de 2020

T
DUALIDAD Y ANALISIS DE SENSIBILIDAD
La solución óptima de una programación lineal se basa en una toma instantánea
de las condiciones que prevalecen en el momento de formular y resolver el
modelo. En el mundo real los ambientes de decisión rara la vez permanecen
estáticos y es esencial determinar cómo cambia la solución óptima, cuando
cambian los parámetros del modelo.
Esto es lo que hace el análisis de sensibilidad. Proporciona técnicas de computo
eficientes para estudiar el comportamiento dinámico de la solución óptima, que
resulta al hacer cambios en los parámetros del modelo.
Todo problema de optimización (primal), tiene un problema asociado (dual) con
numerosas propiedades que los relacionan y nos permiten hacer un mejor análisis
de los problemas. A continuación, se describen los resultados que se ocuparan en
la resolución de los problemas.

Construcción de un problema dual


Bastante en general, para encontrar el dual de un problema lineal:
1. Si es problema de minimización el dual será de maximización y viceversa.
2. En el dual habrá tantas variables como restricciones 2 en el primal.
3. En el dual habrá tantas restricciones como variables en el primal.
4. Los coeficientes de la función objetivo del dual vendrán dados por los
coeficientes del lado derecho de las restricciones del primal.
5. Los coeficientes del lado derecho del dual vendrán dados por los coeficientes
de la función objetivo del primal.
6. Los coeficientes que acompañarán a las variables en una restricción del dual
corresponderán a aquellos coeficientes que acompañan a la variable primal
correspondiente a la restricción dual 3.
7. Para saber si las restricciones duales son de ≤, = o ≥, se recurre a la tabla de
relaciones primal-dual.
8. Para saber si las variables duales son ≤ 0, = 0 o ≥ 0, se recurre a tabla de
relaciones primal dual.
Tabla Tucker
Maximización Minimización
≤ ≥
Restricciones ≥ ≤
= ><
≥ ≥
Variables ≤ ≤
>< =

Relación entre primal y Dual


Estas relaciones nos permiten pasar de un problema de primal a su dual en forma
bastante algorítmica, tanto para problemas de minimización como de
maximización.
Problema de minimización Problema de maximización
Restricciones Variables
≥ ≥0
= Irrestricta
≤ ≤0
Variables Restricciones
≥0 ≤
Irrestricta =
≤0 ≥

Teoremas de dualidad
Teorema de la coincidencia. El máximo (o mínimo) de la función objetivo del
problema primal coincide con el mínimo (o máximo) de la función objetivo del
problema dual.
Teorema de la correspondencia. Los valores de las variables duales en el
óptimo del problema dual coinciden con los rendimientos marginales de las
variables de holgura en el óptimo del problema primal.
A los valores de las variables del problema dual se les llama precio de referencia,
precio teórico o precio sombra de los factores productivos.
Consideremos el siguiente par primal-dual:
(P) min z = c * x (D) max w=y*
s.a A * x >= b s.a At * y <= c
xi >= 0 yi <= 0
Teorema Débil de Dualidad
Si ¯x e ¯y son factibles para (P) y (D) respectivamente, entonces z(¯x) ≥ w(¯y).
Teorema Fundamental de Dualidad
Dados un par de problemas primal-dual, si uno de ellos admite solución óptima,
entonces el otro también la admite y los respectivos valores óptimos son iguales.
Dados un par de problemas primal-dual, si uno de ellos admite solución óptima,
entonces el otro también la admite y los respectivos valores óptimos son iguales.
Teorema de existencia.
La condición necesaria y suficiente para que un problema de programación lineal
tenga solución es que, tanto el conjunto de oportunidades del primal (S) como en
conjunto de oportunidades del dual (S’) no sean vacíos, es decir, que ambos
problemas sean factibles.
∃ ( x* , λ* ) ←→ S ≠ ∅ ∧ S’ ≠ ∅
Teorema del Holgura complementaria.
La condición necesaria y suficiente para que (x*, λ*) sean soluciones óptimas del
programa primal y dual, es que satisfagan las condiciones de holgura
complementaria:
( c - λ* A ) x* = 0 λ* ( b - A x* ) = 0

Condiciones de holgura complementaria


Nos permite encontrar la solución óptima del Problema Dual cuando conocemos la
solución óptima del Problema Primal (y viceversa) a través de la resolución de
un sistema de ecuaciones conformado por las variables de decisión (primales y
duales) y las restricciones (del modelo primal y dual).

Interpretación económica de la dualidad


La solución óptima de un modelo determina la asignación óptima de recursos
limitados. El valor óptimo de las variables duales indica si es o no conveniente
cambiar el nivel de recursos en el modelo.

Precios sombra
Los valores de las variables duales en el óptimo tienen una interpretación
económica interesante en problemas de programación lineal: Corresponde a las
tasas marginales de variación del valor de la función objetivo ante variaciones
unitarias del lado derecho de una restricción. Por este motivo se le llama precio
sombra al vector de variables duales en el óptimo.

Método simplex dual 


Es una estrategia algorítmica eficiente cuando luego de llevar un modelo de
programación lineal a su forma estándar, la aplicación del método simplex no es
inmediata o más bien compleja.
El algoritmo para resolver un modelo es:
Paso 1: Hallar una solución básica inicial infactible e inmejorable
Escribir el tablero inicial tomando a las variables de holgura y de exceso como
variables básicas iniciales

Paso 2: Prueba de factibilidad


 Si todas las variables básicas son no negativas, la actual solución es la
óptima.
 Si hay al menos una variable básica negativa, seleccionar como variable de
salida,
 (llamémosla (XB)s ), a aquella con el valor más negativo. Los empates se
pueden romper arbitrariamente.
Paso 3: Prueba de inmejorabilidad
 Sí en el renglón de la variable básica de salida (XB)s todos los coeficientes
de reemplazo con las variables no básicas son no negativos, la solución del
modelo es óptima ¡limitada. Se termina el proceso.
 Si en el renglón de la variable básica de salida (XB)s, hay al menos un
coeficiente de intercambio negativo, se efectúan los cocientes entre el efecto
neto de cada variable no básicas y su correspondiente coeficiente de
intercambio negativo. Es decir, siendo (XB)s la variable de salida se calculan
todos los cocientes.

 Se toma como variable de entrada (Llamémosla Xe) a aquella que


corresponda al mínimo de los cocientes del anterior conjunto
 Si la variable de entrada es Xe el elemento pivote será el elemento (Se)s
 El empate se puede romper arbitrariamente.
 Aplicar la operación de pivoteo para generar la nueva tabla, en la cual
aparezca Xe como variable básica en lugar de la variable de salida (XB)s
 Repetir el algoritmo a partir del paso 2.

Método de la restricción artificial


A cada problema de optimización lineal le corresponde otro que se denomina
problema dual. En forma canónica. La correspondencia es biunívoca. El dual del
dual es el primal

Efecto de la restricción artificial


Este completa el algoritmo simplex dual cuando es necesario, cuando la variable
de holgura de la restricción artificial no está en la base optima puede ser por dos
razones: M no es suficientemente grande o la solución es no acotada.

Análisis de sensibilidad
En este ámbito, podemos distinguir 2 tipos de análisis:
Análisis de sensibilidad: Consiste en determinar cuál es el rango de variación de
los parámetros del problema de modo que la base ´optima encontrada siga siendo
óptima.
Análisis post optimal: Consiste en determinar cómo varía la base ´optima si
cambia alguno de los parámetros del problema.
En la presente sesión nos concentraremos en análisis de sensibilidad dejando el
análisis post optimal para un poco más adelante.
Consideremos la forma estándar siguiente:
(P) min z = c*x
s.a A*x = b
x >= 0
Sea B la base óptima. Nos interesa estudiar el rango de variación de los
parámetros c y b de modo que B siga siendo ´optima 5.
Variación en el parámetro b.
Buscamos el rango en el que puede tomar valores b de modo que la base B siga
siendo ´optima. Para ello debemos verificar:
1. Factibilidad: xB = B−1b ≥ 0
2. Optimalidad: ¯ cR = cR −cBB−1R ≥ 0 Como en la ecuación
2. no hay dependencia explicita de b, no impone condiciones y por tanto solo
debemos verificar 1.

Variaciones en el parámetro c.
Buscamos el rango en el que puede tomar valores c de modo que la base B siga
siendo ´optima. Para ello debemos verificar:
1. Factibilidad: xB = B−1b ≥ 0
2. Optimalidad: ¯ cR = cR −cBB−1R ≥ 0

Análisis de dualidad en la programación lineal


Problema primal Problema dual

Max (o min) Min(o max)

Coeficientes de la función objetivo Términos independientes de las


restricciones

Términos independientes de las Coeficientes de la función objetivo


restricciones

Matriz ( n * m) de los coeficientes de Matriz ( m * n) transpuesta de los


las restricciones coeficientes de las restricciones

Numero de variables Numero de restricciones

Numero de restricciones Numero de variables

Sentido de la inecuación Sentido de la inecuación


≤ (≥) ≥ (≤) y variables negativas
Ecuaciones (=) Variables sin restricción de signos

Todo problema de programación lineal tiene, asociado a él, un problema de


programación lineal dual. Existen ciertas relaciones útiles entre el problema
original (primal) y su problema dual que refuerzan la habilidad para analizar el
problema primal. Por ejemplo, la interpretación económica del problema dual
proporciona los precios sombra que miden el valor marginal de los recursos en el
problema primal, al igual que permiten dar una interpretación del método símplex.
Puesto que el método símplex se puede aplicar directamente a cualquiera de los
dos problemas para obtener la solución de ambos al mismo tiempo, es posible
ahorrar una gran cantidad de esfuerzo computacional si se maneja directamente el
problema dual. La teoría de dualidad, que incluye el método símplex dual para
trabajar con soluciones básicas superóptimas, juega un papel de gran importancia
en el análisis de sensibilidad.

También podría gustarte