• Author / Uploaded
• Ronald Zegarra

• Categories
• Investigación de operaciones
• Física y matemáticas
• Matemática
• Cognición
• Sicología y ciencia cognitiva

Citation preview

UNIVERSIDAD NACIONAL SAN AGUSTIN ESCUELA PROFESIONAL DE INGENIERIA DE SISTEMAS

GUIA DE PRÁCTICAS PROGRAMACION MATEMÁTICA

DOCENTE: DRA. NORKA BEDREGAL ALPACA

AREQUIPA -2011

1

INTRODUCCION

Esta guía ha sido elaborada teniendo como guía la Sumilla de la asignatura Programación Matemática de la Escuela de Ingeniería de Sistemas de la Universidad Nacional de San Agustín. Existen muchas teorías y tratados que proponen que el aprendizaje no es casual sino el resultado de varias componentes: currículos académicos, profesores, materiales de enseñanza y soporte académico. Algunos autores han sugerido que el aprendizaje ocurrirá si el material de soporte está cuidadosamente y secuencialmente elaborado, aunado a un proceso de estímulo al estudiante. Otros ven el aprendizaje como una actividad manejable no por el estímulo, sino por el propio estudiante, quien debe querer aprender y participar en el proceso de aprendizaje, si es que quiere lograr un progreso real. Otros han estado de acuerdo en aplicar la ciencia en la práctica educacional, diciendo que se deben incluir procedimientos y técnicas. En la elaboración de esta guía se han tomado en consideración, entre otras, estas teorías. Para facilitar el proceso de aprendizaje de la Programación Matemática se ha preparado este material de apoyo, de fácil lectura, y donde se han considerado puntos esenciales. En su elaboración, cada punto particular tiene un orden de prioridad de ideas, hasta culminar la presentación total del material contenido en el capítulo. En cada capítulo se numeran los contenidos, para expresar en forma corta cada concepto o punto particular y para poder tener puntos referenciales al realizar ejercicios prácticos de los contenidos. Cumpliendo con el objetivo que se expone, cada capítulo tiene una parte de teoría y otra de práctica en cada sección que así lo amerite. Esta forma de presentación pretende facilitar la lectura de contenidos y hacer notar la secuencia entre la teoría y la práctica. El desarrollo del material de la asignatura, se hace considerando la Investigación de Operaciones como una ciencia basada en el enfoque científico, para resolver problemas y proporcionar ayuda para la toma de decisiones.

2

PRIMER CAPITULO: INVESTIGACIÓN DE OPERACIONES – PROGRAMACION LINEAL Objetivos Específicos: 1. Presentar conceptos y aspectos relevantes del enfoque cuantitativo en la toma de decisiones 2. Proveer al estudiante con un entendimiento básico de las habilidades iniciales necesarias para realizar análisis cuantitativo, con Investigación de Operaciones, mediante la teoría 3. Presentar casos prácticos.

PRACTICA I: FORMULACION MODELOS EN I.O.

I.

Marco Teórico (Conceptos y aspectos relevantes de la teoría)

La Investigación de Operaciones es una ciencia gerencial, enfocada hacia la toma de decisiones gerenciales, basada en el método científico para resolver problemas. La Investigación de Operaciones no es sólo un conjunto de herramientas matemáticas. De hecho, es un enfoque sistemático que usa herramientas analíticas para resolver problemas. En la toma de decisiones el análisis puede tomar dos formas: cualitativo y cuantitativo. El análisis cualitativo se basa principalmente en el juicio y experiencia de la gerencia, incluye sentimientos intuitivos sobre el problema tratado y es más un arte que una ciencia. El análisis cuantitativo se concentra en hechos cuantitativos o datos asociados con los problemas y desarrolla expresiones matemáticas que describen las relaciones existentes en ellos. Seguidamente, utilizando métodos cuantitativos, obtiene resultados con los que se hacen recomendaciones basadas en los aspectos cuantitativos del problema. El papel del análisis cuantitativo en la toma de decisiones puede variar dependiendo de la importancia de los factores cualitativos. En algunas situaciones, cuando el problema, el modelo y los insumos permanecen iguales, el análisis cuantitativo puede hacer automática la decisión con los resultados obtenidos al usar métodos cuantitativos. En otros casos, el análisis cuantitativo es sólo una ayuda para tomar la decisión y sus resultados deben ser combinados con información cualitativa. Los modelos matemáticos son la base del análisis cuantitativo. La esencia de la Investigación de Operaciones es el uso de modelos. 3

Un modelo es una representación simplificada de un sistema de la vida real, de una situación o de una realidad integral del enfoque científico para tomar decisiones gerenciales. Este análisis es racional y lógico. Consiste en: a) Definir claramente un problema, que previamente se ha determinado que existe, b) Desarrollar un modelo, c) Recolectar los datos de insumo, d) Solucionar el Modelo, e) Validar resultados, Interpretarlos y f) Implementarlos en la ejecución de una decisión. Al definir el problema se deben identificar alternativas, criterios para evaluar esas alternativas, y seleccionarlas La optimización es un criterio utilizado y es sinónimo de maximización o minimización. La evaluación de las alternativas se hace con modelos La definición de un problema determinará el tipo de modelo a usar. Los modelos pueden ser objeto de diversa clasificación. Tres formas de modelo son: Icónico, Analógico y Matemático. Los icónicos son representaciones a escala (réplicas físicas) de objetos reales. Los analógicos o esquemáticos son modelos físicos en cuanto a la forma pero no son semejantes físicamente al objeto que está siendo modelado ( mapas de carreteras). Los modelos matemáticos (llamados también simbólicos) representan sistemas del mundo real; cuantifican sus variables y las combinan en expresiones y fórmulas matemáticas. Son idealizaciones de problemas de la vida real basados en supuestos claves, estimados y/ó estimaciones estadísticas. Los modelos matemáticos son los que, tradicionalmente, han sido más comúnmente identificados con la Investigación de Operaciones. Los modelos matemáticos, base para el análisis cuantitativo, contienen variables y parámetros. Relacionan variables de decisión (Insumos Controlables) con parámetros o coeficientes fijos (Insumos Incontrolables) y frecuentemente buscan maximizar o minimizar una función objetivo sujeta a restricciones. Formular y construir el modelo son procesos integrados. La formulación es el aspecto lógico conceptual y la construcción es la expresión de las relaciones lógicas en el lenguaje simbólico de la Matemática. Las principales razones para usar modelos, en lugar de trabajar directamente sobre la realidad, son las siguientes: a) Ahorro de dinero, tiempo u otro bien de valor; b) Evitar riesgos de daños al sistema cuando se está solucionando el problema; c) Para entender mejor el ambiente real cuando éste es muy complicado. La solución de modelos matemáticos, bien documentada en la bibliografía de Investigación de Operaciones, incluye un algoritmo o serie de cálculos específicos que deben realizarse. Cada modelo usa un particular algoritmo. Muchos de ellos contienen pasos repetitivos y por eso se les llama iterativos, esto permite su fácil implementación en la computadora. Los modelos deben ser probados para su validez interna o externa. En sentido interno, las representaciones matemáticas deben tener sentido unas con respecto a las otras. En sentido externo, los resultados obtenidos del modelo deben tener sentido cuando se comparan con la realidad de la situación que es estudiada.

4

II.

III.

Mapa Conceptual

Problemas Resueltos

Problema 1: Un expendio de carnes de la ciudad acostumbra preparar la carne para albondigón con una combinación de carne molida de res y carne molida de cerdo. La carne de res contiene 80% de carne y 20% de grasa, y le cuesta a la tienda 8 soles por libra; la carne de cerdo contiene 68% de carne y 32% de grasa, y cuesta 6soles por libra. Formule un modelo que le permita determinar la cantidad de cada tipo de carne debe emplear la tienda en cada libra de albondigón, si se desea minimizar el costo y mantener el contenido de grasa no mayor de 25%

Si se define Z: costo de una libra de albondigón en soles entonces el objetivo es minimizar el costo, z, de una libra de albondigón, donde: Z = 8 veces el número de libras de carne molida de res, más 6 veces el número de libras de carne molida de cerdo empleadas.

Si se define: X1 = número de libras de carne molida de res empleadas en cada libra de albondigón. X2 = número de libras de carne molida de cerdo empleadas en cada libra de albondigón, el objetivo se expresa como: minimícese: z = 8X1 + 6X2

5

Cada libra de albondigón tendrá 0.20 x1, libras de grasa provenientes de la carne de res y 0.32 x2 libras de grasa de la carne de cerdo. El contenido total de grasa de una libra de albondigón no debe ser mayor de 0.25 libras. Entonces: 0.20X1 +0.32X2 = 0 y X2 >= 0. Combinando estas condiciones se tiene: minimícese: z = 8X1 + 6X2 con las condiciones: 0.20X1 + 0.32X2 0 Donde A es una matriz (mxn); x es un vector columna (nx1); b es vector columna (mx1) y c es un vector fila (1x n). El número de variables es n y el número de restricciones es m. El Método Simplex funciona, en forma general, de la siguiente forma: Calcula una solución posible inicial y determina sí esa solución es óptima. Si no lo es, se mueve a un punto extremo adyacente, en el conjunto convexo de soluciones posibles, y calcula la nueva solución en ese punto. De nuevo determina si esa solución es o no óptima; si no lo es, repite el proceso anterior. Así continúa sucesivamente hasta encontrar un punto extremo cuyo valor objetivo no pueda ser mejorado y allí concluye, determinando así que ha encontrado la solución óptima. Para calcular la solución posible inicial le otorga valor cero a las variables que no son básicas y resuelve para las otras variables básicas. Cada solución posible satisface todas las restricciones. Para determinar si la solución inicial es óptima, calcula los llamados coeficientes relativos de las variables. Estos valores informan en cuanto variaría el objetivo por cada unidad en que se incremente el valor de la variable a la que se refiere ese coeficiente relativo. Si la solución no es óptima, al moverse a otro punto extremo adyacente en el conjunto convexo, el Método Simplex efectúa un intercambio de una variable básica por una no-básica. Para determinar cual variable no-básica debe entrar a formar parte de una nueva solución, como variable básica, se utiliza como criterio el seleccionar la variable que mejore en mayor cantidad el objetivo. La medida utilizada para aplicar este criterio son los llamados Coeficientes Relativos de las variables. Para determinar cuál variable básica debe salir de una solución, para pasar a ser variable nobásica, se utiliza como criterio el seleccionar a la variable básica que se hace cero al introducir la nueva variable básica. La medida utilizada para aplicar este criterio es el llamado Ratio Mínimo de la variable. Además de indicar la variable que se hace cero, el Ratio Mínimo informa cuál será el valor de la variable entrante en la nueva solución. Para calcular una nueva solución posible efectúa operaciones matemáticas que transforman el sistema actual de ecuaciones, en un sistema de ecuaciones equivalente. Este es un proceso iterativo. En cada iteración intercambia una variable básica por una no-básica. Los Coeficientes Relativos y los Ratios Mínimos tiene fórmulas matemáticas para calcularlos.

17

En cada iteración intercambia una variable básica por una no-básica. En cada solución los Coeficientes Relativos informan si se ha llegado o no al óptimo. Coeficientes Relativos y los Ratios Mínimos tiene fórmulas matemáticas para calcularlos. En las Tablas Simplex se reconoce que hay una solución óptima ÚNICA cuando los coeficientes relativos de variables no-básica tienen valor > que cero en minimización y < que cero en maximización. Esto indicaría que ninguna de esas variables IGUALARÍA el valor óptimo encontrado y por lo tanto, es única. Se reconoce que hay una solución óptima ALTERNA cuando por lo menos uno de los coeficientes relativos de variables no-básica tiene valor igual a cero Esto indicaría que esa variables IGUALARIA el valor óptimo encontrado y por lo tanto, es alterna. Se reconoce que hay una solución óptima con valor INFINITO cuando por lo menos uno de los coeficientes relativos de variables no-básica tiene un valor que indique que la solución actual puede ser mejorada. Pero al calcular el Ratio Mínimo, éste indica que esa variable puede crecer indefinidamente y por lo tanto también el valor del objetivo. Se reconoce que hay una solución óptima IMPOSIBLE cuando todos los coeficientes relativos indican que la solución es óptima pero, por lo menos, una variable artificial permanece en la solución con valor mayor que cero. Se reconoce que hay una solución óptima DEGENERADA cuando por el número de variable básicas con valor mayor que cero es menor que el número de restricciones en el modelo.

II.

Mapa Conceptual

Elabore un mapa conceptual empleando los conceptos y aspectos relevantes de la teoría del Método Simplex.

III.

Problemas Resueltos:

Problema Guía: Resolver por el método simplex Maximizar Z = 40 x1+ 60 x2 sujeto a 2x1 + x2 < = 70 x1 + x2 < = 40 x1 + 3x2 < = 90 x1>= 0, x2 >= 0

Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3.

18

Transformar un sistema de desigualdades en otro de ecuaciones con variables de holgura: 2x1 + x2 + x3 + 0x4 + 0x5 = 70 x1 + x2 + 0x3 + x4 + 0x5 = 40 x1 + 3x2 + 0x3 + 0x4 + x5 = 90

Igual a cero la función objetivo a maximizar: Z = 40 x1+ 60 x2 entonces z - 40x1 - 60x2 + 0x3 + 0x4 + 0x5

De esta forma queda definida la tabla inicial del método de la siguiente forma:

X3 X4 X5

X1 -40 2 1 1

X2 -60 1 1 3

X3 0 1 0 0

X4 0 0 1 0

X5 0 0 0 1

Valor 0 70 40 90

Inicialmente, las variables x3 70, x4 = 40 , x5 = 90, x1 y x2, que no están en la base, valen 0. En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2. Luego, para escoger que variable básica deja la base debemos buscar el mínimo cociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. A la posición que se alcanza el mínimo cociente se le llama "Pivote" (marcado con rojo) el cual sirve para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración:

X3 X4 X2

X1 -20 5/3 2/3 1/3

X2 0 0 1 0

X3 0 1 0 0

X4 0 0 1 0

X5 20 -1/3 -1/3 1/3

Valor 1800 40 10 30

La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:

19

X1 0 0 1 0

X3 X1 X2

X2 0 0 0 1

X3 0 1 0 0

X4 30 -5/2 3/2 -1/2

X5 10 1/2 -1/2 1/2

Valor 2100 15 15 25

Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguales que cero). Nótese que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas soluciones".

La solución alcanzada es X1* = 15, X2* = 25 con V(Z*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico.

IV.

Problemas Propuestos:

Problema 1: Se va a mezclar mineral proveniente de 4 minas diferentes para fabricar bandas para un nuevo producto de la GMC. Los análisis han demostrado que para producir una banda con las cualidades adecuadas de tensión y los requerimientos mínimos se debe contar con 3 elementos básicos: A, B, C. En particular, cada tonelada de mineral debe contener, por lo menos, 5 libras de elemento básico A, por lo menos 100 libras del elemento B, y al menos 30 libras del elemento C. El mineral de cada una de las 4 minas contiene los 3 elementos básicos, pero en distintas proporciones. Sus composiciones en libras/toneladas, y los costos de extracción de los minerales de cada mina son:

Elemento Básico A B C

1 10 90 45

MINA 2 3 3 8 150 75 25 20

4 2 175 37

MINA 1 2 3 4

Costos en U$/Ton de mineral 800 400 600 500

La GMC desea hallar la combinación (mezcla) de costo mínimo para fabricar la banda. Plantee el problema como un PPL.

20

Problema 2: Un proveedor debe preparar con 5 bebidas de fruta en existencias, al menos 500 galones de un ponche que contenga por lo menos 20% de jugo de naranja, 10% de jugo de toronja y 5% de jugo de arándano. Si los datos del inventario son los que se muestran en la tabla siguiente ¿Qué cantidad de cada bebida deberá emplear el proveedor a fin de obtener la composición requerida a un costo total mínimo?

Jugo de Naranja

Jugo de Toronja

Jugo de Arándano

Existencia [gal]

Costo [$/gal]

40 5 100 0 0

40 10 0 100 0

0 20 0 0 0

200 400 100 50 800

1,50 0,75 2,00 1,75 0,25

Bebida A Bebida B Bebida C Bebida D Bebida E

Nota: Las tres primeras columnas indican el porcentaje de un tipo de jugo dentro de una determinada bebida Problema 3: Un producto se puede formar de 4 unidades del componente A1 junto con 3 unidades del componente B1, o se pueden utilizar 3 unidades del componente A2 junto con 4 unidades del componente B2. En cualquiera de las dos opciones, usted puede suponer que la calidad del producto es la misma. Las componentes A1 y B1 se fabrican en la Fábrica UNO y las componentes A2 y B2 se fabrican en la Fábrica DOS. Cada componente necesita 3 materiales P, Q y R. Sin embargo, se utilizan en diferentes proporciones. Las cantidades usadas dependen del lugar y del tipo de componente a elaborar. Actualmente se dispone de 400 unidades de P, 300 de Q y 500 de R. Plantear el problema de programación lineal asociado que permita determinar el número de corridas de producción en cada fábrica, tal que maximice la producción total del producto terminado, si se conoce la siguiente tabla: Fábrica

Unidades requeridas por corrida

Unidades producidas por corrida

P

Q

R

A1

B1

A2

B2

UNO

7

3

10

5

6

0

0

DOS

5

6

5

0

0

7

8

Material

Problema 4: Una familia campesina es propietaria de 125 acres y tiene fondos por $40000 para invertir. Sus miembros pueden producir un total de 3500 horas-hombre de mano de obra durante los meses de invierno (mediados de junio a mediados de septiembre) y 4000 horas-hombre durante el verano. En caso de que se necesite una parte de estas horas hombre, los jóvenes de la familia las emplearán para trabajar en un campo vecino por $5.00 la hora durante los meses de invierno y por $6.00 la hora en el verano. Pueden obtener el ingreso en efectivo a partir de tres tipos de cosecha y dos tipos de animales de granja: vacas lecheras y gallinas ponedoras. Para las cosechas no se necesita inversión, pero cada vaca requerirá un desembolso de $1200 y cada gallina costará $9. 21

Cada vaca necesita 1.5 acres, 100 horas-hombre durante el invierno y otras 50 horas-hombre en el verano; cada una producirá un ingreso anual neto de $1000 para la familia. Las cifras correspondientes para cada gallina son nada de terreno, 0.6 horas-hombre en el invierno, 0.3 horas-hombre en el verano y un ingreso anual neto de $5. Caben 3000 gallinas en el gallinero y el corral limita el ganado a un máximo de 32 vacas. Las estimaciones de las horas-hombre y el ingreso por acre plantado con cada tipo de cosecha son: Horas-hombre en invierno Horas-hombre en verano Ingreso neto anual [$]

Soya 20

Maíz 35

Avena 10

50

75

40

600

900

450

La familia quiere determinar cuántos acres debe sembrar con cada tipo de cosecha y cuántas vacas y gallinas debe mantener para maximizar su ingreso neto. Formule el modelo de programación lineal para este problema.

22

TERCER CAPITULO: DUALIDAD Y ANALISIS DE SENSIBILIDAD Objetivos Específicos: 1. Formular e interpretar modelos de programación dual 2. Explicar la importancia de encontrar soluciones de programación lineal usando el dual 3. Explicar cómo cambia la solución óptima al realizar cambios en la estructura del modelo

Contenidos: 1. 2. 3. 4. 5.

Programación dual Construcción de un modelo dual Condiciones óptimas para los modelos primal y dual Ventajas computacionales de la programación dual Análisis de sensibilidad

PRACTICA V: DUALIDAD, METODO DUAL SIMPLEX

I.

Marco Teórico (Conceptos y aspectos relevantes de la teoría)

Dualidad: 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. La Dualidad en Programación Lineal tiene su esencia en el hecho de existir dos modelos lineales cuando se ha planteado sólo uno para resolver un problema específico. El modelo Lineal asociado al Modelo Lineal Original o Principal se denomina Modelo Dual. Cuando se obtiene la solución de uno, se está obteniendo también la solución del otro. El Modelo Dual contiene: a) Una cantidad de variables igual a la cantidad de restricciones que existan en el modelo original, b) Una cantidad de restricciones igual a la cantidad de variables que existan en el modelo original. Construcción del problema dual: Para encontrar el dual de un problema lineal: 1. 2. 3. 4.

Si es problema de minimización el dual será de maximización y viceversa. En el dual habrá tantas variables como restricciones 2 en el primal. En el dual habrá tantas restricciones como variables en el primal. 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.

23

6. Los coeficientes que acompañarán a las variable en una restricción del dual corresponderán a aquellos coeficientes que acompañan a la variable primal correspondiente a la restricción dual. 7. Para saber si las restricciones duales son de , se recurre a la tabla de relaciones primal-dual. 8. Para saber si las variables duales son < 0, = 0 ó > 0, se recurre a tabla de relaciones primal dual. Precio Sombra: Se define como la proporción con que mejora el valor de la función objetivo a partir de la i - ésima restricción, dependiendo si se trata de maximización tiende a aumentar y a disminuir cuando es de minimización Interpretación de los precios sombra: Los valores de las variables duales en el óptimo tienen una interpretación económica interesante en problemas de programación lineal: Corresponden 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. Relación de la solución óptima del problema dual con la solución óptima del problema primal: La relación principal entre ellos es que tanto el problema primal como el dual buscan el valor óptimo del sistema. Interpretación del problema dual. Para ver cómo la interpretación del problema primal conduce a una interpretación económica del problema dual. Nótese el valor de Z como: Z = W1b1 + W2b2 + W3b3 + ... + Wmbm donde cada bi Wi puede interpretarse como la contribución a la ganancia por disponer de bi unidades del recurso i. Wi se interpreta como la contribución a la ganancia por unidad del recurso i ( i = 1 , 2, . . . , m), cuando se usa el conjunto actual de variables básicas para obtener la solución primal. ujeto a: unidades del m recurso i-ésimo Valor unitario Ganancia asignada j = 1,..., n Suma utilizado por * del recurso = a cada unidad de i =1 unidad de la i-ésimo la actividad j-ésima actividad j-ésima

Valor unitario i - 1, ..., m * del recurso >= 0 i-ésimo La restricción j-ésima del dual indica que el valor total de los recursos consumidos para elaborar una unidad de la j-ésima actividad, debe ser al menos tan grande como la ganancia asignada a cada unidad de la actividad j-ésima. A partir de lo visto anteriormente se puede interpretar el problema dual en los siguientes términos: ” Dados unos recursos bi y un límite inferior para la ganancia Cj, asignada a cada unidad de la actividad j-ésima ¿Qué valor, Wi, se debe asignar a cada unidad del recurso i-ésimo de forma que se minimice el valor total de los recursos?.” La solución del Modelo Dual provee información adicional para la decisión que se tomará con la solución del modelo original.

24

Cada variable Dual informa en cuánto variará la Función Objetivo del modelo original por cada unidad en que se incremente el lado derecho de la restricción, del modelo original, a la que se refiere esa variable dual. Siempre y cuando esa unidad de incremento sea realmente utilizada. Esto permite determinar la conveniencia o no de incrementar un determinado lado derecho de una restricción. Los incrementos permitidos, en el lado derecho de las restricciones, los informará el rango dado por el análisis de sensibilidad de la solución cuando estos elementos cambian. Más allá de esos montos, la solución básica cambiará. Las variables duales son válidas sólo para la respectiva solución básica óptima. Si la solución básica óptima cambia, las variables duales cambian. Sólo en un mínimo número de casos permanecen con sus valores.

II.

Interpretación de Teoremas:

Interprete y ejemplifique cada uno de los siguientes teoremas: • Teorema Débil de Dualidad • Teorema Fundamental de Dualidad • Teorema de Holgura Complementaria

III.

Mapa Conceptual

Elabore un mapa conceptual empleando los siguientes conceptos y aspectos relevantes de la teoría de dualidad y del método dual simplex.

IV.

Problemas Resueltos:

Problema 1: Considere el siguiente problema primal: Maximizar : Z = 60 X1 + 30 X2 + 20 X3 sujeto a: 8X1 + 6X2 + X3 = 30 W1 + 1.5W2 + 0.5W3 >= 20 W1, W2, W3>= 0

25

Problema 2: Considerar el problema siguiente.

Comenzando con la solución básica en que las variables básicas son las variables de holgura.

Las soluciones óptimas de los problemas duales son x* = (11/5; 2/5; 0) e y* = (8/5; 1/5) con valor óptimo 28/5.

V.

Problemas Propuestos:

Problema 1: Construir el dual de los siguientes problemas de programación lineal:

26

Problema 2: Una compañía metalúrgica elabora cuatro productos, A;B;C y D, usando dos productos cobre y zinc como materias primas. Las cantidades de materia prima que precisa cada unidad de cada producto, los beneficios unitarios y la cantidad máxima de cobre y zinc se dan en la siguiente tabla:

a) Comprobar que fabricar 500 unidades del B y 150 del D es la solución óptima. b) Escribir el dual e identificar su solución óptima con los datos de la tabla simplex óptima del primal. c) ¿Cuál es el máximo beneficio? ¿Cuánto aumentaría este beneficio si se dispusiera de una unidad adicional de cobre?

Problema 3: Dado el problema

27

comprobar, aplicando las condiciones de la holgura complementaria, si x1 = 4, x2 = 4, x3 = 4 es una solución óptima

Problema 4: Resolver por el método dual simplex los siguientes problemas

28

PRACTICA VI: ANALISIS DE SENSIBILIDAD I.

Marco Teórico (Conceptos y aspectos relevantes de la teoría)

Análisis de Sensibilidad, llamado también Análisis de Post-optimización, es una estrategia utilizada para tomar en consideración los cambios que pueden ocurrir en los elementos componentes del modelo. Permite conocer cuán sensible es la solución óptima a cambios que ocurran en coeficientes, variables, restricciones y Función Objetivo. En resumen, el Análisis de Sensibilidad se interesa en ver como se ve afectada la solución de un problema de optimización si cambia alguno de los parámetros del problema. En este ámbito, se puede 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 óptima encontrada siga siendo óptima. Análisis post optimal: Consiste en determinar cómo varía la base óptima si cambia alguno de los parámetros del problema.

En el análisis de sensibilidad, interesa: • Variación en la disponibilidad de recursos. • Variaciones en los costos unitarios • Adición de nuevas restricciones • Variaciones en un coeficiente tecnológico Cada caso conlleva un tratamiento diferente

II.

Mapa Conceptual

29

III.

Problemas Resueltos:

Problema 1: Una florista sabe hacer solo 2 tipos distintos de arreglos florales (x1 y x2) para los cuales dispone de 3 tipos distintos de flores: rozas, tulipanes e ibizcos. Los requerimientos de flores para cada arreglo, la disponibilidad de flores y los precios de cada arreglo vienen dados por:

1. Formule un PPL que resuelva el problema de maximización de ingresos por ventas sujeto a la disponibilidad de recursos. 2. ¿Cuál es el problema dual asociado? ¿Qué situación podría estar optimizando? 3. Usando el teorema de holgura complementaria, encuentre el ´optimo del problema dual sabiendo que el ´optimo primal viene dado por (x1 = 80, x2 = 60). 4. Suponga que retorna frustrado después que una bella dama le cerrara la puerta cuando usted le llevaba amablemente una rosa, un tulipán y un ibizco. Si se encuentra con la florista, ¿Cuanto cree que estaría dispuesta a pagar ella por sus flores?

La formulación del PPL es:

Para encontrar el dual, se procede a aplicar las relaciones de dualidad:

Esta formulación resuelve el problema de un agente externo que quiere saber qué precio unitario ofrecer por cada una de las flores si quiere comprarle todas las flores a la florista. Así, y1, y2 e y3 son los precios asociados a las rozas, tulipanes e ibizcos. La florista ha encontrado su combinación óptima (x1 = 80, x2 = 60). Se sabe que en el óptimo se cumple el teorema de holgura complementaria. Entonces, se le puede aplicar:

30

Como x1 = 80 y x2 = 60, se tiene que:

Resolviendo el sistema:

Notar que z(¯ x) = w(¯ y) = 220000

¿Cómo se interpreta esto?. La florista venderá rosas y tulipanes a un precio de $500 cada una y entregará como oferta los ibizcos gratis, pero esto solo si se vende todo como un paquete. Esto toma sentido pues si vende todas las rosas y tulipanes (dado que solo sabe hacer los arreglos florales descritos) no podrá sacarle provecho alguno a los ibizcos. Asumiendo los paradigmas de competencia perfecta, la florista ofrecerá por las flores una cantidad idéntica a lo que ella ganará por ellas. Este valor viene dado nuevamente por los óptimos duales o precios sombras: y1 = 500 ¯ y2 = 500 ¯ y3 = 0

Problema 2: Considerar el problema siguiente:

Donde la tabla simplex óptima es:

Para estudiar mediante análisis de sensibilidad el cambio de c1 = 3/2, se actualiza la tabla simplex óptima del problema de partida en dos pasos:

31

Se aplica el método simplex a la tabla actualizada:

Con lo que se obtiene la solución óptima Si se desea calcular el intervalo de variación de c1 sin que se modifique la solución óptima, se estudia el cambio

Es necesario actualizar la tabla simplex óptima del problema de partida en dos pasos:

Luego c1 pertenece al intervalo [3/4; 3].

IV.

Problemas propuestos:

Problema 1: Dado el programa lineal

a) Resolverlo por el método simplex. b) Añadir la restricción 6x1 + 5x3 = -1 y x2>= -2. e) Suponer que x3 no está restringida en signo.

32

Problema 2: Una compañía se dedica a la fabricación de tres tipos de artículos A; B y C a fin de maximizar el beneficio total a través del siguiente PL

donde xi representa el número de unidades del artículo i. La tabla óptima es:

a) Encuentre el intervalo para el beneficio unitario de A, c1, que no varíe la solución óptima. Determinar la solución óptima si c1 = 2. b) Se pueden obtener 15 unidades de material con un coste adicional de 10 unidades ¿resulta beneficioso llevar a cabo esa opción? c) Hallar la solución óptima si la disponibilidad de material es de 60 unidades. d) Si las unidades de material necesarias para fabricar una unidad de B se reducen a 2 ¿afecta este hecho a la solución óptima? e) Si se añade una restricción de control 2x1+x2+3x3 0 ; i = 1,2,3,4 ; j = 1,2,3,4,5

Cálculo de la Solución Inicial por el método de Esquina Nor-occidental: Tomando la tabla de costos correspondiente al problema: Se asigna en la fila 1, columna 1 lo máximo posible entre 40 y 30 o sea 30 unidades; X11=30 variable básica. Se actualiza la oferta y la demanda, quedando éstas en: 10 y 0 y si se desea se rellena con cero el resto de la columna 1, ya que la demanda de 30 unidades quedó satisfecha

36

Terminando el método, el tablero aparecerá así:

Se obtiene una solución básica factible no degenerada, porque se satisface todas las demandas y ofertas, todas las Xij > 0 y el número de variables básicas es m+n-1 = 4+5-1 = 8 X11 = 30 X12 = 10 X22 = 30 X23 = 30 X33 = 20 X34 = 40 X35 = 10 X45 = 50

Cálculo de una Solución Inicial por el método de Vogel: Algoritmo 1. Construir una tabla de disponibilidades (ofertas), requerimientos (demanda) y costos. 2. Calcular la diferencia entre el costo mas pequeño y el segundo costo más pequeño, para cada fila y para cada columna. 3. Escoger entre las filas y columnas, la que tenga la mayor diferencia (en caso de empate, decida arbitrariamente). 4. Asigne lo máximo posible en la casilla con menor costo en la fila o columna escogida en el punto 3. 5. asigne cero (0) a las otras casillas de la fila o columna donde la disponibilidad ó el requerimiento quede satisfecho. 6. Repita los pasos del 2 al 5, sin tener en cuenta la(s) fila(s) y/o columna(s) satisfechas, hasta que todas las casillas queden asignadas.

37

La mayor diferencia la tiene la columna 4 con un valor de 19, escogido entre 2, 2, 3, 0, 15, 13, 19 y 16. El menor costo de la columna 4 es cero (0), se asigna lo máximo posible entre 50 y 40, que es 40, se satisface la columna y se actualiza la oferta y la demanda.

Ahora se re-calcula las diferencias, sin tener en cuenta la columna 4, que está satisfecha. Una vez ejecutado todo el algoritmo hasta asignar todas las casillas, se obtiene la siguiente asignación básica y factible inicial.

38

Notar que el número de variables básicas es: m+n-1=8, entonces la solución es básica factible no degenerada: X15=40; X21=30 ; X23=20 ; X25=10 ; X32=40 ; X33=30 ; X44=40 ; X45=10 Z = 16(40) + 15(30) + 13(20) + 16(10) + 15(40) + 18(30) + 0(40) + 0(10) = 2.650

Cálculo de la Solución Optima por el Algoritmo de Transporte Se construye una tabla de costos para las variables básicas y en ella se calcula los ui y los vj que cumplan Cij – ui – vj = 0 Tabla de costos para las variables básicas

Se calcula los ui y vj de tal forma que Cij – ui – vj = 0. Se asigna el primer valor de ui ó de vj arbitrariamente, Preferentemente 0 (Puede ser cualquier valor) en la fila ó columna, que tenga la mayor cantidad de asignaciones (Variables Básicas), para este caso, fila 3 ó columna 5. Con base en éste primer valor, se calcula todos los ui y vj , aplicando Cij – ui – vj = 0, para ui = Cij – vj ó vj = Cij – ui luego: V1 = C21 – u2 = 15 - 0 = 15

u1 = C15 – v5 = 16 - 16 = 0

V2 = C32 – u3 = 15 - 5 = 10

V3 = C23 – u2 = 13 - 0 = 13

u3 = C33 – v3 = 18 -13 = 5

V5 = C45 – u5 = 0 – (-16) = 16

V5 = C25 – u2 = 16 - 0 = 16

u5 = C45 – v5 = 0 – 16 = -16

Se calculan los costos para las variables no básicas Cij-ui-vj, así: C11 – u1 – v1 = 20 – 0 – 15 = 5 C12 – u1 – v2 = 19 – 0 – 10 = 9 C13 – u1 – v3 = 14 – 0 – 13 = 1 C14 – u1 – v4 = 21 – 0 – 16 = 5 C22 – u2 –v2 = 20 – 0 – 10 = 10 C24 – u2 –v4 = 19 – 0 – 16 = 3 C31 – u3 – v1 = 18 – 5 – 15 = -2 C34 – u3 – v4 = 20 – 5 – 16 = -1 39

C35 – u3 – v5 = M – 5 –16 = M-21 C41 – u4 – v1 = 0 – (-16) – 15 = 1 C42 – u4 – v2 = 0 – (-16) – 10 = 6 C43 – u4 – v3 = 0 – (-16) – 13 = 3 Se construye una tabla de costos ó coeficientes en la función objetiva para las variables no básicas cuyo valor es Cij – ui – vj:

La variable que al crecer hace que Z disminuya más es X31, luego se escoge ésta variable para entrar a la base.

Z=2.650 ; Variable que entra X31. Fíjese que a medida que X31 crece, X21 y X33 decrecen en la misma cantidad. Aquí X21 y X33 llegan a cero al mismo tiempo. Se escoge arbitrariamente a X33 como variable que sale y a X21 al restarle 30 quedará con un valor de ε ≅ 0

Z=(40)(15)+(0)(15)+(50)(13)+(10)(16)+(30)(18)+(40)(15)+(40)(0)+(10)(0) = 2.590 • • •

Fíjese que m+n-1=8 X21 es variable básica = 0 La oferta es igual a la demanda. 40

•

Z disminuye en 60 unidades; 2(30)=60 ⇒ 2.650 – 60 = 2.590

¿Ésta es la solución óptima?, la respuesta se conoce cuando se calcula la nueva tabla de costos para las variables no básicas. Tabla de costos para las variables básicas: Cij – ui – vj = 0

Tabla de costos para las variables no básicas: Cij – ui – vj

Fíjese que todos son > 0 ⇒ Es la solución óptima. Solución óptima: X15* = 40

X21* = ε = 0

X54* = 40

X55* = 10

X23* = 50

X25* = 10

X31* = 30

X32* = 40

Z* = 40(16)+0(15)+50(13)+10(16)+30(18)+40(15)+ 40(0) +10(0) = 2.590 Interpretación de la solución: La forma óptima de hacer los envíos desde las fábricas (1, 2, 3) a los distribuidores (1, 2, 3, 4, 5) para que los costos totales del transporte sean mínimos es: Desde la fábrica 1 al distribuidor 5 enviar 40 unidades, a un costo de: $ 640 Desde la fábrica 2 al distribuidor 3 enviar 50 unidades, a un costo de: $ 650 Desde la fábrica 2 al distribuidor 5 enviar 100 unidades, a un costo de: $ 160 Desde la fábrica 3 al distribuidor 1 enviar 30 unidades, a un costo de: $ 540 Desde la fábrica 3 al distribuidor 2 enviar 40 unidades, a un costo de: $ 600 Total de unidades enviadas 170, a un costo total de $2.590 Observe que el distribuidor 4 se quedará sin sus 40 unidades y que el distribuidor 5 sin sus 10 unidades, en total quedará una demanda insatisfecha de 50 unidades (Información que se conoce desde el principio), lo relevante aquí, es que ahora se sabe a quién no enviarle las 50 unidades que no tienen los distribuidores y que se puede tomar decisiones administrativas referentes a la demanda no cubierta, tales como:

41

1. Conseguir las 50 unidades a través de la competencia agremiada, como consecuencia de acuerdos previamente establecidos. 2. Acordar con el distribuidor 4 y 5 cubrir dicha demanda en el periodo de producción siguiente. 3. Otras decisiones podrán ser tomadas en concordancia con la situación real.

IV.

Problemas propuestos:

Problema 1: Una empresa de desarrollo de software cuenta con personal distribuido entre 3 centros de trabajos: Santiago, Valparaíso y Concepción. Actualmente, se encuentran planificando hacia qué zonas enfocar su trabajo, pues el tener gente trabajando en otros lugares distintos a los anteriormente mencionados implica costos de traslado, comida y de permanencia, que al final se traducen en un costo mayor de desarrollo del software. Para esto, ha decidido realizar un cálculo para determinar cómo debe hacer la asignación de su gente entre las distintas ciudades de modo de hacerlo al costo mínimo. Las zonas de trabajo de interés son Arica, Copiapó, Rancagua y Talca en las cuales requieren 20, 65, 55 y 25 personas respectivamente. A su vez, se cuenta con 75 personas disponibles en Santiago, 60 en Valparaíso y 30 en Concepción. Los costos asociados son:

Arica

Copiapó

Rancagua

Talca

Santiago

11

22

5

5

Valparaíso

16

30

13

15

Concepción

10

22

4

9

A partir de estos datos se pide: a) b) c) d)

Realice un modelo de programación lineal que permita resolver el problema. Encuentre una solución inicial mediante el Método de la esquina Noroeste. Determine si la solución anterior es óptima o no. ¿Existe solución alternativa a la anterior? De ser así, determine cuál es.

Problema 2: Considere el problema de transporte que se originan debido a un accidente. Existen tres ambulancias con distintas capacidades para trasladar heridos hacia cuatro Servicios de Urgencia. La siguiente tabla presenta la capacidad de las Ambulancias y los Servicios de Urgencia.

42

Ambulancia Capacidad

Servicio de Urgencia Demanda

1

3

1

4

2

7

2

3

3

5

3

4

4

4

Los costos generados por el transporte se muestran en la siguiente tabla.

SU 1

SU 2

SU 3

SU 4

Ambulancia 1

2

2

2

1

Ambulancia 2

10

8

5

4

Ambulancia 3

7

6

6

8

Utilizando el Método de Voguel, encuentre la solución inicial. ¿Es óptima? Si no es así encuentre la solución óptima Problema 3: Una firma que produce un único producto tiene 3 plantas y 4 clientes. Las 3 plantas producirán 3000, 5000 y 5000 unidades respectivamente durante el siguiente período de tiempo. La firma ha realizado un contrato para vender 4000 unidades al cliente 1, 3000 unidades al cliente 2 y al menos 3000 unidades al cliente 3. El cliente 4 está dispuesto a comprar las unidades que sobren. En la siguiente tabla se encuentran los costos asociados a las distintas rutas.

CLIENTE 1

CLIENTE 2

CLIENTE 3

CLIENTE 4

PLANTA 1

65

63

62

64

PLANTA 2

68

67

65

62

PLANTA 3

63

60

59

60

A partir de los datos entregados se pide determinar lo siguiente: a) Formular un modelo de programación lineal que permita satisfacer la demanda a un costo mínimo. b) Encontrar una primera solución factible y determinar si la solución es óptima, en caso contrario determinar la solución óptima. Indique el costo total involucrado.

43

Problema 4: Estudie la forma en que se realiza el análisis de sensibilidad en problemas transporte y responda a las siguientes interrogantes: Respecto al problema 2: Realice un análisis de sensibilidad y determine los costos que permitan a las ambulancias estar indiferentes con respecto a los Servicios de Urgencia. Respecto al problema 1: ¿En qué rango debería encontrarse el costo de la ruta entre Valparaíso y Talca para que convenga utilizarla? Respecto al problema 3: a) Determine el valor mínimo en que debiera disminuir la ruta entre la planta 3 y el cliente 4, de tal forma que sea conveniente utilizarla. b) Interprete el valor de e11 y e14. Explique. c) Si la planta 3 decide aumentar su oferta y el cliente 1 decide aumentar su demanda. Determine el valor del aumento de cada uno, tal que la asignación óptima se mantenga.

44

PRACTICA VIII: ASIGNACION

I.

Marco Teórico (Conceptos y aspectos relevantes de la teoría)

Asignar n orígenes (individuos, tareas etc.) a n destinos (tareas, máquinas etc.) con el objetivo de minimizar el costo de asignación. La Asignación se realiza uno a uno. Variables de decisión.

cij: costo de asignar el origen i al destino j. Modelo lineal.

Algoritmo: Método Hungaro Paso 1. Equilibrar el problema. Hacer cij >= 0; para todo i; j. Paso 2. Restar en cada fila el mínimo. Paso 3. Restar en cada columna el mínimo. Paso 4. Asignación de ceros. Elegir la o columna con menor número de ceros. Asignar uno y eliminar los ceros de la misma fila y columna. Repetir hasta que no haya ceros para asignar. Si todas las filas tienen cero asignado
solución óptima. Parar. Si no, ir al paso 5. Paso 5. Marcar líneas. (a) Marcar las filas que no tienen ceros asignados. (b) Marcar las columnas que tienen ceros eliminados en las filas las marcadas en el paso anterior. (c) Marcar las filas que tienen ceros asignados en las columnas marcadas en el paso anterior. Repetir (b) y (c) hasta que ya no se puedan marcar más filas o columnas. Cubrir las no marcadas y columnas marcadas. Ir a 6. 45

Paso 6. Crear nuevos ceros. Elegir el elemento mínimo que no está cubierto. Restarlo a todos los elementos de las filas no cubiertas y sumarlo a los elementos de las columnas cubiertas. Ir al paso 4.

II.

Mapa Conceptual

Elabora un mapa conceptual para el problema de asignación y otro para el algoritmo de que soluciona el problema

III.

Problemas Resueltos:

Problema 1:

Formule y equilibre, si es necesario, el siguiente problema Existen cuatro operarios que se pueden asignar al trabajo con tres máquinas. Un estudio de tiempos y movimientos ha arrojado los siguientes tiempos por operario para las tres máquinas. Indicar que operario debe trabajar en que máquina y cuál de ellos no será asignado a ninguna. Máquina 1 Máquina 2 Máquina 3 Operario 1

10

7

9

Operario 2

7

5

8

Operario 3

9

8

10

Operario 4

8

9

7

Como la matriz no está balanceada, es necesario incluir una máquina ficticia: (esto es fundamental para asegurar que haya una respuesta. Si la matriz no está balanceada, el problema no será factible de resolver) Máquina 1 Máquina 2 Máquina 3 Máquina Ficticia Operario 1 10

7

9

0

Operario 2 7

5

8

0

Operario 3 9

8

10

0

Operario 4 8

9

7

0

Xij = Se debe asignar el operario i a la máquina j? Sí o no?

46

La formulación del problema: Min Z =

10X11 + 7X12 + 9X13 + 7X21 + 5X22 + 8X23 + + 8X41 + 9X42 + 7X43

9X31 + 8X32 + 10X33

Como cada operario sólo puede estar asignado a una máquina.... X11 + X12 + X13 + X14 = 1 X21 + X22 + X23 + X24 = 1 X31 + X32 + X33 + X34 = 1 X41 + X42 + X43 + X44 = 1 Y como cada máquina solo puede tener un operario asignado... X11 + X21 + X31 + X41 = 1 X12 + X22 + X32 + X42 = 1 X13 + X23 + X33 + X43 = 1 X14 + X24 + X34 + X44 = 1 Las restricciones de signo Xij = 1 o 0 para toda i,j.

Problema 2: Una fábrica dispone de cuatro obreros para completar cuatro trabajos. Cada obrero solo puede hacer uno de los trabajos. El tiempo que requiere cada obrero para completar cada trabajo se entrega en el Cuadro

La fábrica desea minimizar el tiempo total dedicado a los cuatro trabajos. Encuentre la mejor asignación de los obreros. En primer lugar se debe definir las variables de decisión necesarias para representar las posibles alternativas de asignación. Evidentemente, de acuerdo a la naturaleza del problema conviene emplear variables binarias. Sea: xij = asignación de obrero i a trabajo j La variable binaria xij valdría 1 si se asigna al obrero i al trabajo j y 0 en caso contrario. En primer lugar se busca el mínimo por filas en la matriz de costos.

47

Luego se resta el valor determinado en cada fila y se busca el mínimo por columna:

Se resta el menor costo por columna y se trazan el menor número de líneas que cubran todos los ceros de la matriz de costos reducida:

Luego, de los coeficientes no tarjados el menor es 1. Se resta a todos los no tarjados 1 y se suma 1 a los tarjados dos veces. Volvemos a trazar el número mínimo de líneas que cubran todos los ceros.

Como el número de líneas trazadas es igual a la dimensión de la matriz se ha encontrado el óptimo. Se determina la asignación correspondiente:

Lo que implica obrero1 – trabajo 2, obrero 2 – trabajo 4, obrero 3 – trabajo 3 y finalmente obrero 4 – trabajo 1

48

IV.

Problemas propuestos:

Problema 1: Para participar en el próximo campeonato de bridge, el Club universitario debe enviar un equipo de cuatro personas. Hay seis jugadores disponibles, cuyos rendimientos relativos en cada una de las posiciones se ha evaluado, arrojando los resultados siguientes:

N

E

S

O

Juan

8

5

8

5

Pedro

7

4

2

6

Raúl

5

4

7

5

Sergio

3

2

4

4

Arturo

4

5

4

4

Carlos

8

3

7

4

Determine el mejor y peor equipo que se podría enviar al campeonato.

Problema 2: Un bufete de abogados ha aceptado 5 nuevos casos, cada uno de los cuales puede ser llevado adecuadamente por cualquiera de los 5 asociados más recientes. Debido a la diferencia de experiencia y práctica, y debido a la corrupción que experimentan algunos de los que practican la teoría de leyes, los abogados emplearán distintos tiempos en los casos. Uno de los asociados más experimentados ha estimado las necesidades de tiempo (en horas) como sigue:

Caso 1

Caso 2

Caso 3

Caso 4

Caso 5

Abogado 1

145

120

130

95

115

Abogado 2

80

63

85

48

78

Abogado 3

121

107

93

69

95

Abogado 4

118

83

116

80

105

Abogado 5

97

75

120

80

111

49

a) ¿Cuál es la mejor asignación posible? b) ¿Qué pasa si el abogado 2 no puede tomar el caso 4, con respecto a la solución anterior? c) Si el abogado 1 debe tomar el caso 1 ¿qué ocurre con respecto a la solución encontrada en a)? d) ¿Cuál es la peor asignación posible? e) ¿Cuál es la mejor asignación sin considerar al abogado 2? f) ¿Qué pasa si el abogado 4 no puede tomar el caso 2 y el caso 5 debe ser tomado por el abogado 3? Problema 3:

Una compañía llamó a licitación para realizar cuatro trabajos de construcción. Tres personas se han presentado. Las propuestas en miles de dólares están dadas en la tabla siguiente, donde * indica que la persona no ofrece nada para ese trabajo. ¿Cuál es la mejor asignación, desde el punto de vista de la compañía, si todas las personas deben realizar al menos un trabajo? Trabajo 1

Trabajo 2

Trabajo 3

Trabajo 4

Persona 1

55

49

46

46

Persona 2

51

48

44

*

Persona 3

*

47

45

45

50

QUINTO CAPITULO: REDES DE OPTIMIZACION Objetivos Específicos: 1. Presentar los métodos y modelos asociados a las redes de optimización 2. Explicar las características de un modelo de flujo máximo, de costo mínimo y problemas de flujos múltiples

Contenidos: 1. 2. 3. 4. 5.

Conceptos elementales Problema de flujo máximo Problemas de flujo a costo mínimo Problemas de flujo máximo a costo mínimo Árbol mínimo de comunicación en una red

Descripción: En este capítulo se trata de resolver problemas de redes. Debido a la complejidad de los algoritmos ya la gran cantidad de cálculos, se utilizará mayormente apoyo informático para la solución de los problemas propuestos. Sin embargo, se desarrolla manualmente uno de los temas: el problema de flujo máximo.

PRACTICA IX: OPTIMIZACION DE REDES I.

Marco Teórico (Conceptos y aspectos relevantes de la teoría)

Una red es un grafo orientado a cuyos arcos se les ha asociado una capacidad. Para un arco genérico (i,j) dicha capacidad será denotada por qij. Las capacidades representarán la máxima cantidad de flujo que puede pasar por los diferentes arcos de la red. Si no existe limite de capacidad entre nodo i y j
se asignará una capacidad qij muy grande M. Si los nodo si y j se encuentran conectados por un arco no orientado de capacidad qij,  dos arcos orientados qij=qji El flujo de una red es una asignación a cada par de nodos (i,j) de una cantidad no negativa xij. Si el nodo i no está conectado al j




xij=0

Por definición, el flujo no excederá a la capacidad. En toda red existirán por lo menos un nodo de salida s denominado fuente en el que E(s)=0 y por lo tanto no le llega ningún flujo. Similarmente, existirán un nodo de entrada e denominado sumidero en el que S(e)=0 no saliendo de el ningún flujo.

51

El resto de los nodos debe cumplir con la ley de Kirchhoff, o sea el flujo no puede crearse ni destruirse. Definiciones matemáticas: A(j) y D(j) son los conjuntos de nodos que son orígenes y destinos de arcos de entrada y salida:

A( j ) ={i | i ∈ N ;(i, j ) ∈ L}

D( j ) ={k | k ∈ N ;( j , k ) ∈ L} La ley de Kirchhoff, para un nodo genérico j, puede definirse por:

∑

k∈D ( j )

x jk −

∑

i∈ A ( j )

xij = 0

En el nodo fuente, la ley de conservación será

∑

F=

k∈D (1)

x1k =

∑

k∈D ( s )

xsk = 0

Y en el nodo sumidero:

−

∑

j∈ A ( k )

x jk = − F = −

∑

j∈ A ( e )

x je

En este problema se desea encontrar la cantidad máxima de flujo que puede circular en la red desde el nodo de salida s al de entrada e.

Maximizar F s.a.

 F si j = s,  x jk − ∑ x ij = 0 si j ≠ s, e, ∑ k∈D(j) i∈A(j) − F si j = e,  0 ≤ xij ≤ qij

∀i, j = 1, 2,..., n

Si existe más de un nodo fuente produciendo flujos se puede transformar la red a otra de única fuente añadiendo un nodo ficticio con nuevos arcos que lo conecten a los originales con capacidades qs1, qs2, …, qsr. Análogamente, en el caso en el que se tenga varios nodos sumideros, se puede añadir otro nodo ficticio unido a ellos por medio de arcos adicionales. La capacidad de estos arcos se considerará sin limite. (M muy grande) El problema es un problema de optimización lineal que se puede resolver con Simplex, sin embargo existen otros métodos más eficaces para su resolución. Flujo de un corte Si se define por ( X , X ) cualquier cortadura en una red G, tal que el nodo de salida pertenezca a

X , s ∈ X y el nodo de entrada pertenezca a X , e ∈ X

los flujos que atraviesan el corte

vendrán definidos por:

f (X, X ) =

∑

( i , j )∈( X , X )

f ( X, X ) =

xij , 52

∑

( j ,i )∈( X , X )

x ji

Si el conjunto X solo contiene al nodo de salida se puede verificar que:

f ( s, D ( s ) ) =

∑

j∈D ( s )

xsj = F ,

y si el conjunto X solo contiene al nodo de entrada:

f ( A(e), e ) =

∑

j∈ A ( e )

x je = F

El flujo neto de cualquier cortadura separando el origen y el destino es igual al flujo factible de la red.

F = f (X, X )− f ( X, X ) Capacidad de un corte: Definida una cortadura definida por:

( X , X ) tal que

q(X, X ) =

∑

( i , j )∈( X , X )

s∈ X

qij ,

ye ∈ X

q( X, X ) =

, la capacidad de un corte viene

∑

( j ,i )∈( X , X )

q ji

y como 0 ≤ xij ≤ qij, se tendrá:

q(X, X ) = q( X, X ) =

∑

qij ≥

∑

q ji ≥

( i , j )∈( X , X )

( j ,i )∈( X , X )

∑

xij = f ( X , X )

∑

x ji = f

( i , j )∈( X , X )

( j ,i )∈( X , X )

( X , X )

0 ≤ x ji ≤ q ji

⇒ f 

( X, X ) ≥ 0

Según el teorema del “flujo de un corte” se tiene :

F = f ( X, X )− f ( X , X ) ≤ q( X , X ) −0 El valor de cualquier flujo factible F es menor o igual a la capacidad de cualquier cortadura. Determinación del flujo máximo Uno de los resultados centrales de la teoría de redes es el “teorema del flujo máximo – corte mínimo” que se deriva del siguiente expresión

F = f ( X, X )− f ( X , X ) ≤ q( X , X ) −0 Este teorema establece que el flujo máximo es igual a la capacidad del corte mínimo:

F = mínimo q ( X , X ) X

53

De aquí que interese conocer la cortadura cuya capacidad sea mínima, ya que ésta definirá flujo máximo en la red. Método de Ford-Fulkerson - algoritmo Resumen de resultados previos: previos • • • •

El flujo neto de cualquier cortadura que separe el origen y el destino es igual al flujo factible de la red. la cortadura cuya capacidad sea mínima, define el flujo máximo en la red. La obtención directa de la cortadura de capacidad mínima es inviable para redes de tamaño realista. El algoritmo de Ford--Fulkerson resuelve eficientemente el problema

La solución debe satisfacer:

s ∈ X y s ∉ X y además:

( i, j ) ∈ ( X , X ) ⇒ xij = qij , ( i, j ) ∈ ( X , X ) ⇒ xij = 0,

si si ya que en este caso:

F = q ( X , X ) − q( X , X ) = q ( X , X )

•

i. ii. •

Para obtener la cortadura se parte de una SBF, que podría ser xij=0 para todo los arcos; prosiguiéndose la construcción del conjunto X:

Si el nodo i ∈ X X. Si el nodo i ∈ X X.

y el arco ( i,j ) existe un flujo

0 ≤ xij ≤ qij , el nodo j pertenecerá pertenecer a

y el arco ( j,i ) existe un flujo 0 < x ji ≤ q ji , el nodo j pertenecerá a

Si se obtiene una cortadura en la que e ∈ X , el corte no es mínimo y el flujo puede incrementarse. o Se habrá obtenido una cadena con extremo final el modo e marcado con incremento ( ,∆e)..

Se puede construir otra cortadura en la que e ∉ X , o sea el corte es mínimo, y el flujo no se puede incrementar más. Se ha alcanzado el máximo. 54

El algoritmo:

i. ii.

Marcar el nodo s con la etiqueta

( −, ∞. )

(

+ Comenzando por el nodo s, marcar todos los nodos j conectados con él con la etiqueta s , ∆ j , donde

∆ j = mínimo ( ∆ s , qsj − xsj )

iii.

Nodo genérico i marcando con ( . ,

∆ ) y no explorado: i

1. Marcar todos los nodos j no marcados anteriormente, conectados a él + ,∆ j mediante el arco (i,j) en los que xij0, con la etiqueta (i ,,

∆ j = mínimo ( ∆ i , x ji )

∆ ), donde i

3. Definir dicho nodo i como explorado. iv. v.

Si uno de los nodos j marcados es el nodo de entrada e, ir a v. En caso contrario volver a iii. En el caso en el que no existan nodos explorados ir a vii. Si el nodo e se encuentra marcado, pertenece al conjunto X y el flujo puede incrementarse. +

1. Si el nodo e se encuentra etiquetado como ( j , ∆ ), De indica el incremento e

de flujo permitido y el arco (j,e) soportará un flujo

x je = x je + ∆ e 2. Ir al nodo j: a. Si el nodo j se encuentra etiquetado como (i+,.), el flujo en el arco (i,j) será ahora xij = xij + ∆ e b. Si el nodo j se encuentra etiquetado como (i-,.), el flujo en el arco ( j,i ) será ahora x ji = x ji − ∆ e c. ir al nodo i y repetir ii hasta alcanzar el nodo de salida s. vi.

Si todos los nodos han sido marcados y explorados, y no se ha alcanzado el nodo de entrada e, se ha obtenido el óptimo.

Variables básicas • Una vez obtenido el flujo máximo en una red, las variables básicas serán aquellas que tengan asignados valores ni nulos ( xij > 0 ), y los arcos saturados aquellos que se encuentren a la capacidad máxima ( xij=qij ). • El corte mínimo vendrá definido por la cortadura X , X de la ultima iteración. En X se encontrarán los nodos marcados y en los no marcados. X

(

II.

Mapa Conceptual

55

)

)

Elabora un mapa conceptual para el problema de flujo máximo y otro para el algoritmo de FordFulkerson III.

Problemas Resueltos:

Problema 1:

Modelar matemáticamente la siguiente red:

Maximizar x13 + x12 s.a.

x24 + x23 − x32 − x12 = 0, x34 + x32 − x23 − x13 = 0, 0 ≤ x12 ≤ 4, 0 ≤ x13 ≤ 3, 0 ≤ x 23 ≤ 3, 0 ≤ x 32 ≤ 1, 0 ≤ x 34 ≤ 5, 0 ≤ x 24 ≤ 1.

Problema 2:

En la red representada en la figura, en la que sobre cada arco se indica su capacidad máxima, obtener la capacidad de la cortadura mostrada:

X = (1, 2 ) , X = ( 3, 4,5, 6 )

56

La cortadura viene definida por: Las capacidades del corte por:

q ( X , X ) = 16, q ( X , X ) = 2

Problema 3:

Aplicar el Algoritmo de Ford--Fulkerson a la siguiente red:

Aplicando el algoritmo:

57

Continuar con el algoritmo

IV.

Problemas Propuestos:

Encontrar el flujo máximo en las siguientes redes: 1. Desde una central de despacho (1) se desea enviar a seis mensajeros a seis puntos de una ciudad. Las rutas posibles y las respectivas distancias se ilustran en la figura. Determinar la ruta que debe seguir cada mensajero de modo de minimizar la distancia a recorrer.

17 2 15

7 6

6 5

1

3

10

4

6

4

3

2 5

4

58

2. Suponga que las distancias entre cuatro ciudades vecinas son las que se presentan en el esquema.

2

A

B

6 3

5 7 C

D 6

Suponga que hay interés de pavimentar y conectar estas ciudades a un costo mínimo. Indique cuáles serían las rutas a pavimentar desde un punto de vista gubernamental o del estado y desde un punto de vista de los usuarios

BIBLIOGRAFIA 1. EPPEN, G.D., F. J. Gould, C.P. Schmidt, Jeffrey Moore y Larry Weatherford. Investigación de Operaciones en la Ciencia Administrativa. Editorial Prentice Hall. Quinta. Edición 2. HAEUSSLER, Ernest. Matemáticas para Administración y Economía. Editorial Pearson, décima edición. 3. POLYA, G Cómo plantear y resolver un problema. Edit. Trillas. 4. TAHA, Hamdy. Investigación de Operaciones. Edit. Alfaomega, Quinta edición.

59