• Author / Uploaded
• CAYVI

Citation preview

Clave 9013 Práctica No.

6

Nombre de la Unidad de Aprendizaje Investigación de Operaciones I Título de la Práctica

Página 78 de 89 Duración:

Análisis Dual. Simplex Dual

2 horas

Formuló

Cuerpo Académico

M.C. Teresa Carrillo Gutiérrez Dra. Karina C. Arredondo Soto Dra. Ma. Marcela Solís Quinteros

Innovación de Procesos y Productos

Autorizó Dr. Luis E. Palafox Maestre DIRECTOR DE LA FACULTAD DE CIENCIAS QUÍMICAS E INGENIERÍA

COMPETENCIA

Plantear y resolver problemas lineales duales, utilizando el paquete computacional, que a través de un análisis crítico, entender los diferentes aspectos del problema dual.

I. DESCRIPCIÓN DE LA PRÁCTICA

Se obtendrán los programas duales de distintos programas lineales y se resolverán mediante el uso del paquete computacional.

II. ANTECEDENTES TEÓRICOS

Relaciones primal-dual Asociado a cada problema lineal existe otro problema de programación lineal denominado problema dual (PD), que posee importantes propiedades y relaciones notables con respecto al problema lineal original, problema que para diferencia del dual se denomina entonces como problema primal (PP).

Las relaciones las podemos enumerar como siguen: a) El problema dual tiene tantas variables como restricciones tiene el programa primal. b) El problema dual tiene tantas restricciones como variables tiene el programa primal c) Los coeficientes de la función objetivo del problema dual son los términos independientes de las restricciones o RHS del programa primal. d) Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo del problema primal. e) La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema primal. f) El sentido de las desigualdades de las restricciones del problema dual y el signo de las

variables del mismo problema, dependen de la forma de que tenga el signo de las variables del problema primal y del sentido de las restricciones del mismo problema. g) Si el programa primal es un problema de maximización, el programa dual es un problema de minimización. h) El problema dual de un problema dual es el programa primal original. El problema de programación lineal dual que se define a partir de un problema original (primal), comparte con él los mismos coeficientes tanto de la función objetivo como de las restricciones, pero en diferente posición como más adelante se especificará. Por otra parte, es importante tener presente que: • Si un problema tiene solución óptima y factible, el problema dual también la tiene. • Si un problema tiene solución factible pero no óptima, entonces el problema dual no tiene solución factible. A manera de síntesis, lo que se desea recuperar del análisis de dualidad es: Cuando se tiene un modelo de programación lineal en el que el objetivo es minimizar, llamaremos a este modelo primal¸ y obtendremos el modelo dual asociado que es un modelo de maximización, el cual puede resolverse con el método dual-símplex; y al obtener la solución del problema dual encontraremos la del modelo primal. Existen otros aspectos importantes del análisis de dualidad que es necesario tener presentes, por ejemplo, para el modelo primal el objetivo es minimizar y las restricciones son del tipo ≥ (mayor o igual que), mientras que para el modelo dual el objetivo es maximizar y las restricciones son del tipo ≤ (menor o igual que). Lo anterior se ilustra en la siguiente figura, donde se aprecian estas diferencias en las representaciones matriciales de los modelos.

Problemas primal y dual asociados a un mismo problema real.

Observe que el problema primal no se encuentra en la forma estándar necesaria para aplicar el método dual-símplex, y es por esto que se genera el problema dual. Además en el problema dual se emplea AT que es la matriz transpuesta de la matriz de coeficientes del sistema de restricciones. De manera desarrollada los problemas se ven como: Problema primal

Mientras que el problema dual se verá en la forma estándar. Problema dual

Cabe resaltar que si el modelo primal tiene n variables y m restricciones, el modelo dual tendrá m variables y n restricciones, como se puede observar en los problemas primal y dual desarrollados. La solución óptima de un problema corresponde a la solución del otro, como ya se ha mencionado, y de este resultado se desprende la siguiente sección. Propiedad de las soluciones básicas complementarias Cada solución básica óptima en el problema primal tiene una solución básica óptima complementaria en el problema dual, en donde los valores respectivos de las funciones objetivos son iguales, Z min = Z max, y el valor de las restricciones del problema primal serán los coeficientes de las variables artificiales (yi ). Esto quiere decir que los valores de las restricciones del modelo primal son los valores que se encuentran en el renglón R0 en las columnas de las variables artificiales de la tabla símplex del modelo dual. A continuación se presenta el algoritmo para generar el modelo dual a partir del problema primal, para lo cual utilizaremos la tabla primal-dual.

Método dual-símplex Tabla primal-dual Partiendo de un modelo con el objetivo de minimizar, se utiliza la llamada tabla primal-dual para trasladar el problema a maximización y volver al uso del mismo algoritmo.

Si tenemos el modelo primal de minimización:

Problema primal

Para formar la tabla primal-dual se procede como sigue: El tamaño de la tabla es de m+2 renglones y n+2 columnas. (n número de variables y m número de restricciones del problema primal). 1. La celda de la esquina superior izquierda se divide en dos con una diagonal, en la parte superior escribimos la palabra primal (min) y en la parte inferior dual (max). 2. En la celda de la esquina superior derecha se escribe el símbolo ≥ , mientras que en la primera columna en el último renglón se escribe el símbolo ≤ . 3. En la primera columna a partir del segundo renglón se escriben los nombres de las variables del problema dual (m variables artificiales). 4. En el primer renglón se escriben los nombres de las variables del problema primal (n variables).

5. Se escriben los coeficientes de la función objetivo del modelo primal en el último renglón.

6. Se escribe cada uno de los coeficientes de las restricciones del problema primal en forma horizontal, ocupando los renglones de la tabla. 7. En la última columna se escriben las cantidades limitantes de las restricciones del modelo primal. 8. De esta tabla podemos obtener el modelo dual, lo único que debemos hacer es leer el modelo de manera vertical y los coeficientes de la función objetivo se obtienen de la última columna.

Ejercicio de ejemplo: Resolver el siguiente modelo de programación obteniendo el modelo dual y aplicando el método dual-símplex. Min Z = 12x1 + 7x2 Sujeto a: 4x1 + 2x2 ≥ 80 3x1 + 4x2 ≥ 90 x1 , x2 ≥ 0 Solución

La tabla dual está dada por:

Entonces, el modelo dual de maximización es: Max Z = 80y1 + 90y2

Sujeto a: 4 y1 + 3y2 ≤ 12 2y1 + 4 y2 ≤ 7 y1, y2 ≥ 0 Ahora se utiliza el método dual-símplex para resolver el modelo dual. La tabla inicial de este modelo es:

El primer elemento pivote de la tabla inicial es:

Con operaciones entre renglones se obtiene la siguiente tabla:

Como en el renglón asociado a la función objetivo todavía se encuentran coeficientes negativos, no se ha completado el proceso, por lo que se identifica un nuevo pivote en la tabla obtenida. El nuevo pivote se encuentra en:

De manera similar con el primer pivote, con operaciones básicas entre renglones se resuelve la tabla símplex:

En esta iteración, todos los coeficientes del renglón de la función objetivo son no negativos, es decir, mayores o iguales a cero, por lo que el proceso del método dual-símplex ha concluido. Cabe recordar que estamos resolviendo un valor de los coeficientes asociados a las variables de holgura que den el renglón de la función objetivo. Es decir:

Por lo que al transferir la solución de la tabla símplex a las variables originales del problema primal se tiene:

Con la transferencia de la solución de la tabla a las variables del problema primal concluye la aplicación del método dual-símplex primal-dual. PROBLEMA RESUELTO (GUÍA CON POM QM) El desarrollo de tres estrategias de un proceso administrativo de fondos de inversión a largo plazo causa costos de 1, 3 y 2 millones de pesos por año de procesamiento, respectivamente. Cada estrategia genera 10, 20 y 40 millones en beneficios por año, en el mismo orden, y se requiere un nivel mínimo de 800 millones en beneficios para que el negocio sea conveniente a los inversionistas. Por último, se sabe que la diferencia entre el triple de la duración de la estrategia con costo de 3 millones menos la duración de la estrategia de 2 millones debe ser de por lo menos 10 años. ¿Cuál es la duración óptima de cada estrategia que garantiza los beneficios esperados y minimiza los costos de administración?

• Para resolver este problema, primero identificamos que el objetivo del planteamiento es minimizar el importe de los costos totales. • Las restricciones están relacionadas con el nivel mínimo de beneficios y la duración de cada estrategia. Obtener el modelo primal y el dual. Resolver con un software. X1= La duración de estrategia 1 que garantiza los beneficios esperados X2= La duración de estrategia 2 que garantiza los beneficios esperados X3= La duración de estrategia 3 que garantiza los beneficios esperados Z = Minimizar costos totales

Minimizar Z= 1000000 X1 + 3000000 X2+ 2000000 X3 Sujeto a: 10000000 X1 + 2000000 X2 + 40000000 X3 >= 800000000 3 X2 – 1 X3 >=10 X1, X2, X3 >= 0

SOLUCION: USAR POM-QM

LISTA DE SOLUCIONES

RESULTADOS

Conclusión La duración óptima debe ser ___, ____ y ____ para garantizar los beneficios esperados y minimiza los costos de administración en ______; también ___________________________________________________.

• LECTURAS Y VIDEOS RECOMENDADOS



Leer el tema: El Problema de la dualidad página 37 del libro: Inzunza V., López F., De la Vega E., Inzunza X. (2012). Investigación de Operaciones. Pearson educación y Universidad de Sonora: México.



Ver los siguientes videos: https://www.youtube.com/watch?v=XpJAMMjYzrI Modelo primal y dual en PL. https://youtu.be/tAdaNMoSeVU

III. PREEVALUACIÓN (PREPARACIÓN A LA REALIZACIÓN DE LA PRÁCTICA EN EL LABORATORIO)

Formular los modelos matemáticos del problema planteado en el desarrollo de esta práctica. IV. PROCEDIMIENTO EQUIPO



Computadora

MATERIAL



PHP Simplex, POM QM

CONSIDERACIONES DE SEGURIDAD

Aplicar las normas de seguridad e higiene en laboratorios de cómputo presentadas en el Anexo B. DESARROLLO DE LA PRÁCTICA

 Convertir a su forma dual. Ejercicio 1.

Ejercicio 4.

Sujeto a:

Sujeto a:

Ejercicio 2. Ejercicio 5. Sujeto a: Sujeto a:

Ejercicio 3. Sujeto a:

Ejercicio 6. Sujeto a:

Problema 1 La National Bisness Machine (NBM) produce y vende dos tipos de máquinas de escribir: manual y eléctrica. Cada máquina de escribir manual es vendida con un ingreso de $40 y cada máquina de escribir eléctrica produce un ingreso de $60, ambas máquinas tienen que ser procesadas (ensambladas y empacadas) a través de dos operaciones diferentes O1 y O2. La NBM tiene las siguientes capacidades mensuales: 2000 hrs. O1 y 1000 hrs. O2. El número de horas de operación 1 y 2 requeridas para producir un modelo terminado se da en la siguiente tabla:

Operación

hrs. máquina manual

hrs. máquina eléctrica

hr.

O1

3

2

2000

O2

1

2

1000

Obtener el modelo primal y el dual. Resolver con un software.

Problema 2 TOYCO arma tres juguetes: trenes, camiones y coches, con tres operaciones. Los límites diarios de tiempo disponible para las tres operaciones son 430, 460 y 420 minutos, respectivamente, y las utilidades por tren, camión y coche de juguete son $3, $2 y $5, respectivamente. Los tiempos de armado por tren, en las 3 operaciones son 1, 3 y 1 minutos, respectivamente. Los tiempos respectivos por camión y por coche son (2, 0, 4) y (1, 2, 0) minutos (un tiempo de cero indica que no se usa la operación). Obtener el modelo primal y el dual. Resolver con un software.

V. RESULTADOS Y CONCLUSIONES

El reporte final de la práctica de laboratorio incluye los resultados y conclusiones. Los reportes se presentarán en un documento pdf por equipo en archivo digital de acuerdo a los lineamientos presentados en el Anexo B. VI. ANEXOS

Anexo A. Seguridad e higiene en el laboratorio de cómputo. Anexo B. Lineamientos del reporte de práctica de laboratorio.

VII. REFERENCIAS



Hillier F. y Lieberman G. (2010). Introducción a la Investigación de Operaciones. México: McGraw Hill.



Inzunza V., López F., De la Vega E. e Inzunza X. (2012). México: Pearson.



Muñoz R., Ochoa M. y Morales M. (2011). Investigación de Operaciones.México: McGraw Hill.



Sitio web www.phpsimplex.com



Taha H. (2012). Investigación de Operaciones. México: Pearson.



Winston W. (2005). Investigación de Operaciones. Aplicaciones y algoritmos. México: Thompson.