Feeds:
Posts
Comments

¿Qué es la Investigación Operativa?

La Investigación Operativa o Investigación de Operaciones es una disciplina moderna que mediante el uso de modelos matemáticos, estadística y algoritmos modela y resuelve problemas complejos determinando la solución óptima y permitiendo, de esta forma, la toma de decisiones.

Actualmente la Investigación Operativa incluye gran cantidad de ramas como la Programación Lineal, Programación No Lineal, Programación Dinámica, Simulación, Teoría de Colas, Teoría de Inventarios, Teoría de Grafos, etc.

Aunque su nacimiento como ciencia se establece durante la Segunda Guerra Mundial y debe su nombre a las operaciones militares, los verdaderos orígenes de la Investigación Operativa se remontan mucho más atrás en el tiempo, hasta el siglo XVII. Sin embargo su auge es debido, en su mayor parte, al gran desarrollo de la informática, gracias a la cual es posible resolver problemas en la práctica y obtener soluciones que de otra forma conllevarían un enorme tiempo de cálculo. Debido al gran éxito de la Investigación Operativa en el campo militar, esta se extendió a otros campos tales como la industria, física, informática, economía, estadística y probabilidad, ecología, educación, servicio social, …, siendo hoy en día utilizada prácticamente en todas las áreas.

I. PROGRAMACIÓN LINEAL ENTERA

INTRODUCCION:

El problema con la programación lineal entera, es que no existe un algoritmo rápido para hallar la solución. El método más frecuentemente utilizado, se llama el de ramificar y acotar y es una adaptación de la solución continua. Este algoritmo toma la solución del programa continuo y la divide en dos problemas si ésta no fue entera (si lo hubiera sido ya habríamos terminado, pero eso sólo sucede en las películas), cada uno con una restricción de más.  Por   ejemplo, si la solución continua fue X1 = 7.25, se dividiría en dos problemas, uno con la restricción X1<=7 y el otro con la restricción X1 >= 7 . Se encuentran las soluciones, para estos problemas y se comparan, le mejor gana; si no es entera se repite el proceso de nuevo. Como se puede ver, éste método consume muchos más recursos de máquina; en un problema de Planeación Agregada, con unas cien variables y unas sesenta restricciones, y algo de  mala suerte, se podrían estar resolviendo unos cuantos miles de problemas continuos asociados, y cada uno de estos podría consumir bastante tiempo. Tal vez con los nuevos estudios en métodos de punto interior, como el de Karmakar, se pueda derivar un método mucho más eficiente que el de ramificar y acotar.

A propósito, Solver utiliza ramificar y acotar para la programación lineal entera.

Resolver:

Max Z = 3 X1 + 4X2
4 X1 + 2X2  <=  8
2X1   + 5X2  <=  10

X1, X2 enteros positivos.

Lo modelamos de igual manera que el ejemplo continuo, y en las restricciones especificamos que X1 y X2 son enteros. No es más.

Y en las restricciones…

Para los programas Lineales enteros es muy importante que Solver, esté debidamente configurado para un número suficiente de iteraciones, de tiempo,  de precisión y de convergencia, para esto ver los detalles de Solver.

EJEMPLO  DE RAMIFICACIÓN Y ACOTACIÓN

A través d e un ejemplo de Programación Lineal entera mixta  aplicada a la Planeación Agregada se utilizara el siguiente  modelo matemático para explicar el algoritmo de Ramificar y Acotar:

Min Z = 800T1 +800T2 + 800T3+800T4+800T5+800T6 (el total de salarios en tiempo normal)

+200C1 +200C2+200C3+200C4+200C5+200C6 (el costo de contratar C empleados por mes)

+500D1 +500D2+500D3 +500D4 +500D5 +500D6 (el costo de despedir D empleados por mes)

+0.06i1 +0.06i2 +0.06i3 + 0.06i4 + 0.06i5+0.06i6 (costo de llevar inventario cada mes)

+7.5H1 +7.5H2 +7.5H3+7.5H4+7.5H5 +7.5H6 (costo de utilizar H horas extras en el mes)

Sujeto a:

T1          – C1 +D1 = 70
T2 – T1  -C2  +D2 = 0
T3 – T2  -C3  +D3 = 0
T4 – T3  -C4  +D4 = 0
T5 – T4  -C5  +D5 = 0
T6 – T5  -C6  +D6 = 0

I1 –  100T1  –  0.625 H1           =  1.000
I1 + 100T2  + 0.625 H2 – I2   = 10.000
I2 + 100T3  + 0.625 H3 – I3   = 12.000
I3 + 100T4  + 0.625 H4 – I4   =    8.000
I4 + 100T5  + 0.625 H5 – I5   =    6.000
I5 + 100T6  + 0.625 H6 – I6   =    5.000

H1 – 32T1 <= 0
H2 – 32T2 <= 0
H3 – 32T3 <= 0
H4 – 32T4 <= 0
H5 – 32T5 <= 0
H6 – 32T6 <= 0

En el contexto de este modelo las variables T representan el número de trabajadores que se deben tener en cada periodo (T1 en enero, T2 en febrero, …), por lo tanto estas variables deben ser enteras.

Árbol de Solución:

Los números dentro de los círculos significan el orden de los pasos a seguir:

1. Resolver el problema Original Continuo. Z nos dio 332 620 pero las cuatro primeras variables nos dieron no enteras. Entonces toca ramificar por cualquiera de ellas… para no pensar mucho, escojamos siempre la primera de izquierda a derecha. En este caso ramificamos por T1 cuya respuesta original fue de 72.5 así es que resolveremos dos subproblemas, en uno le agregaremos a las restricciones que ya tiene la restricción T1<=72 y al otro la restricción T1 >= 73.  Podemos escoger cualquiera de las dos ramas para comenzar a solucionar y seguir… de nuevo para no pensar mucho, escojamos siempre la rama de la izquierda (no importa cuál se escoja, aunque el no de iteraciones es diferente según la rama, no hay forma de saber cuál es la más rápida, así es que aquí la escogimos por capricho esa).  Escogiendo la rama de la izquierda se solucionará el problema agregándole la restricción T1<=72 y se sigue en el paso 2.

2. Se solucionó el problema con Z =332 730 pero de la segunda a la cuarta variable no son enteras. Así es que debemos de nuevo ramificar… dijimos que escogeríamos primero la primera variable no entera de la izquierda a la derecha, en este caso T2. Si ramificamos por T2 resolveremos dos problemas uno con la restricción T2 <= 72 (rama izquierda) y el otro T2 >= 73 (rama derecha). Resolver rama izquierda

3. Resulta la rama izquierda Z = 332 958 y todas las variables enteras. Como todas las variables nos dieron enteras ya no se sigue ramificando por esa rama, es decir se agota esa rama, y como es la primera solución entera que hemos encontrado esta solución es la que va ganando con Z = 332 958 (anotamos en un papelito el valor de Z para que no se nos olvide). De ahora en adelante, cualquier rama que de un Z mayor que 332 958 no la seguimos ramificando, no nos interesaría por que como estamos minimizando no nos interesan valores más grandes del que ya obtuvimos. Claro que si llegamos a una solución entera más pequeña que esta, no nos dará ningún remordimiento olvidarla por completo y llevar esa como mejor. Como esta rama se agota pasemos a lo otra rama de T2>=73.

4. Se resuelve el problema con las restricciones que había en el paso 2  agregándole la restricción T2>= 73. Ojo! No las restricciones que habían en el paso 3, como la rama nace del paso 2 se tomarán esas más la de T2>= 73. Okay, al resolver da Z = 332 952 y todas las variables enteras. Como el Z es menor que el que teníamos como mejor de 332 958 nos olvidamos de ese otro y ahora tendremos como mejor el de 332 952 con T1=71, T2=73, T3=73, T4=73,T5=60,T6=50. Agotada toda la rama izquierda del problema original resolvemos la rama derecha agregándole la restricción T1>=73.

5. Se resolvió con Z = 332 976 y las variables de la 2 a la 4 dieron no enteras, pero no importa, no seguiremos ramificando por que el Z que dio es mayor que el que ya tenemos de 332 952.

Finalmente:

Después de 5 iteraciones se encontró el óptimo con Z = 332 952 y T1=71, T2=73, T3=73, T4=73,T5=60,T6=50.

Este es un ejemplo minimizando. Para Maximizar lo único que cambia es que ya no se prefieren las Z más pequeñas sino las más grandes.

II.    TEORÍA DE DECISIONES

1.  INTRODUCCIÓN:

La mayoría de las decisiones administrativas complejas se toman bajo incertidumbre. Los gerentes autorizan inversiones sustanciales de capital con un conocimiento que no es completo acerca de la demanda del producto.Los funcionarios gubernamentales toman decisiones importantes acerca del medio ambiente que afectara nuestras vidas por muchos años, sin embargo ellos no tienen disponible un conocimiento preciso sobre el futuro…….

2.  FASES EN EL ENFOQUE DE LA TEORÍA DE DECISIONES.

El enfoque de la teoría de decisiones generalmente involucra 3 fases; presentaremos estos mediante el ejemplo de un fabricante de CDs y tarjetas de video que está considerando varios métodos alternativos de expandir su producción para adecuar una demanda creciente para sus productos.

Fase I.- La primera acción que debe considerar el que va a tomar las decisiones es listar todas las alternativas viables que se deben contemplar en la decisión.

Ejemplo:

  1. Expandir la Planta.
  2. Construir Planta Nueva.
  3. Encargar la Producción de CDs y tarjetas de videos a una empresa subcontratista.

Fase II.- Habiendo identificado todas las alternativas viables, el tomador de decisiones debe ahora listar los eventos futuros que pueden ocurrir.

Generalmente los que toman decisiones están en condiciones de identificar la mayoría de los eventos futuros que pueden ocurrir; la dificultad está en identificar que evento en particular ocurrirá. Estos eventos futuros (que no están bajo el control del que toma la decisión) se llaman estados de la naturaleza en la literatura de la teoría de decisiones. En este listado incluimos todo lo que puede suceder; también suponemos que los estados de la naturaleza se definen de tal modo que solo uno de ellos puede ocurrir, en el caso de nuestro fabricante de cintas y discos la mayor incertidumbre se asigna a la demanda futura del producto.

  1. Demanda Alta (total aceptación del producto en el mercado).
  2. Demanda Moderada (aceptación moderada o regular del producto en el mercado).
  3. Demanda Baja (Escasa aceptación del producto en el mercado).
  4. Falle (que no existe demanda de productos).

Fase III.- El tomador de decisiones construye ahora una tabla de beneficios.

Una tabla que muestra los beneficios (expresado en utilidades o en cualquier otra medida que sea apropiada a la situación), que resultaría de cada posible combinación de alternativas de decisión y estados de la naturaleza. La tabla siguiente ilustra los 12 beneficios posibles en la decisión de expansión de la compañía de CDs y tarjetas de videos

Tabla de Beneficios para la Expansión de la Compañía de CDs y tarjetas

Alternativas del Tomador de Decisiones Estados de la Naturaleza (demanda)
Alta Mediana Baja Falla
Expandir 500000 250000 -250000 -450000
Construir 700000 300000 -400000 -800000
subcontratar 300000 150000 -100000 -100000

3. DIFERENTES AMBIENTES EN QUE SE TOMAN LAS          DECISIONES:

Los que toman las decisiones deben funcionar en 3 tipos de ambientes. En cada uno de estos ambientes el conocimiento sobre los estados de la naturaleza es distinto.

4.  DISPONIBILIDAD DE INFORMACIÓN PERFECTA:

Disponibilidad de Información Perfecta             Decisiones Bajo Certidumbre o Certeza.

Sea (Xj) Problema de Mezcla de Productos:

Puede suponerse que el beneficio por unidad de un j – ésimo producto es Cj, el cual es un valor real fijo. Si Xj es la variable de decisión que representa el nivel de producción para el producto j, la contribución al beneficio total del producto j – ésimo es Cj . Xj el cual de nuevo, es un valor fijo para un valor dado de Xj.

5. LA DISPONIBILIDAD DE INFORMACIÓN IMPERFECTA

Sobre un problema nos presenta 2 categorías de casos en la toma de decisiones.

5.1 Decisiones con Riesgo: El grado de ignorancia se expresa como una función  de densidad de probabilidad que representa los datos.

Cj: Variable aleatoria.

FD: f (Cj)

  • Determinar más de un estado de la naturaleza (Debe Suponer)
  • Determinar la probabilidad de ocurrencia.
  • Cuando hablamos de decisiones de riesgo nos referimos a la clase de problemas de decisión para los cuales hay más de un estado de la naturaleza y para los que tenemos la suposición de que el que toma la suposición pueda estimar la probabilidad con que ocurrirá todo estado de la naturaleza.

EJEMPLO: Supóngase que hay m > 1 estados de la naturaleza y sea pj la probabilidad de que ocurra el estado “j”, podemos entonces usar la siguiente ecuación para calcular UEi, que es el rendimiento esperado cuando tomamos la decisión “i”.

Σ rij Pj = ri1 P1 + ri2 P2 + … + rim Pm

Donde:

Pj es probable ocurrencia.

rij es probable retribución.

En este tipo de problemas el administrador debe entonces tomar la decisión que maximice el rendimiento esperado, dicho de otra manera, hallar la decisión óptima, es decir que UEi = máxima sobre todo “i” de UEi

Es decir:

UEi = Max sobre todo i de UEi

CASO DE ESTUDIO:

EL PROBLEMA DEL VENDEDOR DE PERIÓDICOS

El problema que afronta Cesar y su personal es un clásico de la ciencia de la administración conocido como el problema del vendedor de periódicos. En este el vendedor de periódicos compra “Q” periódicos del camión de repartos al comenzar el día. Los vende en el transcurso de la mañana. No conoce por anticipado cuantos venderá. Al final del día, los periódicos carecen de valor. Si compra más de los que vende, pierde el dinero correspondiente a los periódicos que le hayan sobrado. Si no compra suficientes pierde las utilidades potenciales de las ventas adicionales.

Supóngase que paga “C” $ por cada periódico y los vende en “S” $ cada uno.

Sea:

C = $ 0.10

S = $ 0.25

COMPONENTES DEL PROBLEMA DEL VENDEDOR DE PERIÓDICOS:

1.-El costo de mantener inventario h, es el precio por unidad para el vendedor de periódico por cada periódico que le sobra.

    h = C = $ 0.10

     

    2.-El costo de Penalización P, es la ganancia que el vendedor pierde en cada periódico que puede haber vendido, pero no lo hizo porque se agotaron

    P = S – C

    P = 0.25 – 0.10

    P = 0.15

     

     

     

     

    3.-La distribución de probabilidad de la demanda:

    • Supóngase que en este caso del Vendedor de Periódicos, emplea una distribución uniforme (por simplicitud) en particular, el piensa que es igualmente probable cualquier demanda entre 1 y 100. por lo tanto:

      Prob. {Demanda = 1} = 1/100

      Prob. {Demanda = 23} = 1/100

      Generalmente: {D = Cualquier entero de 1 a 100} = 1/100

      Por lo tanto: Prob. {Demanda <= 5} = 5/100     = 0.05

      Prob. {Demanda <= 23} = 23/100 = 0.23

      Generalizando:

      = 0 Siendo X <= 0

      Pro. {D <= X}           = X/100 Siendo X = 1,2,..,100

      = 1 Siendo X >= 100

      Recuerde que el Vendedor de Periódicos puede comprar a $0.10 c/u y venderlos a $0.25. Sin embargo la demanda no se conoce con certeza. El supone que es igualmente probable cualquier demanda entre 1 y 100. En concreto sea el estado “j” el evento de que la demanda sea “j” artículos; el supone que para cualquier entero “j” tal que “j” esté comprendido entre 1 y 100, la probabilidad en “j” es = 0.01. Para fines académicos supóngase que el esperaba la siguiente distribución de probabilidad de la demanda:

      P0 = Prob. {D = 0} = 1/10

      P1 = Prob. {D = 1} = 3/10

      P2 = Prob. {D = 2} = 4/10                Estados de la Naturaleza Distintos.

      P3 = Prob. {D = 3} = 2/10

      Entonces la decisión es el número de periódico por ordenar. Los rendimientos o retribución se muestran a continuación.

      Retribuciones para el Problema del Vendedor de Periódicos

      Decisión Estado de la Naturaleza (Demanda)
      0 1 2 3
      0 0 0 0 0
      1 -10 15 15 15
      2 -20 5 30 30
      3 -30 -5 20 45

      UEi para i = 0, 1, 2, 3

      UE0 = 0(1/10) + 0 (3/10) + (4/10) + 0 (2/10) = 0

      UE1 = -10(1/10) + 15(3/10) + 15(4/10) + 15(2/10) = 12.5

      UE2 = -20(1/10) + 5(3/10) + 30(4/10) + 30(2/10 = 17.5 UTILIDAD MAXIMA

      UE3 = -30(1/10) – 5(3/10) + 20(4/10) + 45(2/10) = 12.5

      Ø  LA DECISIÓN OPTIMA ES COMPRAR 2 PERIÓDICOS.

      5.1.1 EL CRITERIO DEL VALOR ESPERADO: Este criterio requiere que el tomador de decisiones calcule el valor esperado para cada alternativa, donde los pesos son los valores de probabilidad asignados por el tomador de decisiones a los estados de la naturaleza que pueden presentarse.

      CASO DE ESTUDIO: VENTA DE FRESAS POR BETH PERRY  (BP)

      BP compra fresas a $3 la caja y las vende a $8 la caja. Este margen alto refleja lo perecedero del artículo y el gran riesgo de almacenarlo; el producto no tiene ningún valor después del primer día en que se ofrece a la venta. BP se enfrenta al problema de cuanto ordenar hoy para los negocios de mañana. Una observación de ventas pasadas por 90 días nos da la información mostrada a continuación:

      Ventas históricas diarias   de fresas (en cajas)

      Ventas Diarias (Caja) N° de Días con esta Venta Probabilidad que se venda cada Número
      10 18 0.20
      11 36 0.40
      12 27 0.30
      13 9 0.10
      Total 90 1.00

      Esta distribución es discreta y aleatoria. Solo hay cuatro valores posibles para el volumen de ventas y no hay patrón discernible en la secuencia en que ocurran estos 4 valores. Si suponemos que BP no tenga argumentos para creer que el volumen de ventas se compartirá en forma diferente en el futuro, su problema es determinar cuantas cajas debe comprar hoy para el negocio de mañana. Si mañana los clientes solicitan más cajas de las que hay almacenadas, las utilidades de BP disminuyen en $5 (precio de venta – precio de costo), por cada venta que no pueda hacer. Por otra parte hay costos que resultan de almacenar demasiados artículos en cualquier día. Suponga que un día dado BP tiene 13 cajas, pero solo vende 10. tiene una utilidad de $50, $5 por caja en 10 cajas, pero esto debe reducirse por $9, el costo de 3 cajas no vendidas y sin valor.

      (I)  CÁLCULO DE LAS UTILIDADES CONDICIONALES:

      Para ilustrar el problema de BP, se construye una tabla que muestra los resultados en dinero de todas las posibles combinaciones de compras y ventas. Los únicos valores de compras y ventas que tienen significado para nosotros son: 10, 11, 12, 13 (cajas). No hay motivo para que ella considere comprar menos de 10 y más de 13 cajas.

      La tabla siguiente llamada tabla de Utilidades Condicionales muestra la utilidad resultante de cualquier combinación posible de oferta y demanda. Las utilidades pueden ser positivas o negativas y son condicionales en el sentido de que una utilidad dada resulta de una acción de almacenamiento específico (ordenar 10, 11, 12, ó 13 cajas). La tabla refleja las pérdidas que ocurren cuando el inventario no se ha vendido al final del día. No refleja utilidades no realizadas por BP a causa de su incapacidad de satisfacer la solicitud de un comprador, esto es, a causa de una condición de falta de inventario.

      Tabla de Utilidades Condicionales (De Rendimientos)

      Demanda Posible (Ventas) Cajas Acciones de Almacenamiento Posibles
      10 Cajas 11 Cajas 12 Cajas 13 Cajas
      10 50 47 44 41
      11 50 55 52 49
      12 50 55 60 57
      13 50 55 60 65

      Esta tabla de utilidades condicionales no le dice a BP el número de cajas que debe almacenar cada día para maximizar sus utilidades. Solo le muestra cuál será el resultado si un número específico de cajas se almacena y un número específico de cajas se vende. Bajo condiciones de riesgo. Ella no sabe por anticipado el tamaño de la demanda de un día dado, pero aún así debe decidir que número de cajas almacenar constantemente, maximizarán las utilidades sobre un periódico dado.

      (II)  DETERMINACIÓN DE LA UTILIDAD ESPERADA

      UEi = 10, 11, 12, 13

      UE10 = 50(0.20) + 50(0.40) + 50(0.30) + 50(0.10) = $50

      UE11 = 47(0.20) + 55(0.40) + 55(0.30) + 55(0.10) = $53.40

      UE12 = 44(0.20) + 52(0.40) + 60(0.30) + 60(0.10) = $53.60  UTILIDAD MAXIMA

      UE13 = 41(0.20) + 49(0.40) + 57(0.30) + 65(0.10) = $51.40

      Ø  LA DECISION OPTIMA ES COMPRAR 12 CAJAS

      5.1.2 OTRO ENFOQUE PARA RESOLVER ESTE PROBLEMA:

      Minimización de Pérdidas.-  existen dos tipos de pérdidas.

      • Pérdidas con Obsolescencia (Sobre Stock)
      • Pérdidas por Oportunidad (Falta Inventarios)

      Tabla de Pérdidas Condicionales

      Demanda Posible (Ventas) Cajas Acciones de Almacenamiento Posibles
      10 Cajas 11 Cajas 12 Cajas 13 Cajas
      10 0 3 6 9
      11 5 0 3 6
      12 10 5 0 3
      13 15 10 5 0

      Cálculo de Pérdidas Esperadas:

      PEi = 10, 11, 12, 13

      PE10 = 0(0.20) + 5(0.40) + 10(0.30) + 15(0.10) = $6.5

      PE11 = 3(0.20) + 0(0.40) + 5(0.30) + 10(0.10) = $3.10

      PE12 = 6(0.20) + 3(0.40) + 0(0.30) + 5(0.10) = $2.90  MINIMO COSTO

      PE13 = 9(0.20) + 6(0.40) + 3(0.30) + 0(0.10) = $5.10

      Ø   LA DECISION OPTIMA ES  COMPRAR 12 CAJAS

      5.1.3 UTILIDADES CONDICIONALES BAJO CERTEZA (INFORMACIÓN PERFECTA)- I.P

      Tabla de utilidades Condicionales

      Demanda Posible (Ventas) Cajas Acciones de Almacenamiento Posibles
      10 Cajas 11 Cajas 12 Cajas 13 Cajas
      10 50 - - -
      11 - 55 - -
      12 - - 60 -
      13 - - - 65

      I. CALCULO DE UTILIDADES ESPERADAS

      UE = 50(0.20) + 55(0.40) + 60(0.30) + 65(0.10) = $56.50

      56.50 – UTILIDAD MAXIMA CON I. P

      53.60    UTILIDAD MAXIMA SIN I .P

      2.90   VALOR MAXIMO DE LA INFORMACION

      5.1.4 ARTÍCULOS QUE TIENEN UN VALOR DE RECUPERACIÓN:

      (VALOR DE SALVAMENTO)

      Si el producto tiene algún valor de recuperación, entonces esta cantidad se debe considerar al calcular las utilidades condicionales por acción de almacenamiento.

      Considere el caso de un producto que se ordena por el detallista y se recibe el día anterior al día de la venta. Cuesta $5 por caja y se vende en $8 por caja, cualquier remanente no vendido al final del día, se puede salir de él al precio de recuperación de $2 por caja. La siguiente tabla nos muestra que las ventas pasadas han variado de 15 a 18 cajas por día. No hay razón para creer que el volumen de ventas tomará cualquier otra magnitud en el futuro.

      Tamaño del Mercado Probabilidad de Tamaño del Mercado
      15 0.10
      16 0.20
      17 0.40
      18 0.30
      66 1.00

      Tabla de Utilidades Condicionales

      Demanda Posible (Ventas) Cajas Acciones de Almacenamiento Posibles
      15 Cajas 16 Cajas 17 Cajas 18 Cajas
      15 45 42 39 36
      16 45 48 45 42
      17 45 48 51 48
      18 45 48 51 54

      UEi = 15, 16, 17, 18

      UE10 = 45(0.10) + 45(0.20) + 45(0.40) + 45(0.30) = $45

      UE11 = 42(0.10) + 48(0.20) + 48(0.40) + 48(0.30) = $47.40

      UE12 = 39(0.10) + 45(0.20) + 51(0.40) + 51(0.30) = $48.60

      UE13 = 36(0.10) + 42(0.20) + 48(0.40) + 54(0.30) = $47.40

      5.1.5 DATOS EXPERIMENTALES EN DECISIONES CON RIESGO

      Probabilidades a Priori                       Experiencia, Datos Históricos

      Experimento (Modificar Prob.)

      Probabilidades a Posteriori

      A priori

      Ejem:   La Probabilidad de tener un lote bueno es de 0.80

      La Probabilidad de tener un lote malo es 0.20

      1. A Posteriori

        Dos Buenos.

      2. Uno Bueno.
      3. Dos Malos.

      Algunas veces es posible realizar un experimento acerca del sistema en estudio y dependiendo de los resultados de dicho experimento, modificar las probabilidades a priori en el sentido de que se puede incluir información importante con respecto al sistema, al calcular las nuevas probabilidades. A estas probabilidades se les conoce como probabilidades a posteriori.

      EJEMPLO: La experiencia en una Empresa Industrial indica que la probabilidad de producción de lotes buenos = 0.95 y la probabilidad de producir un lote malo = 0.05.

      Sea      P(q = q1) = 0.95                     Bueno

      P(q = q2) = 0.05                     Malo

      P(qi)                Probabilidades a Priori

      Probabilidades de Resultado

      1.      Dos Buenas…Z1

      2.      Uno Bueno…Z2

      3.      Dos Malos…Z3

      P (Zj / qi): Probabilidad Condicional.

      P (qi / Zj): Probabilidad a Posteriori.

      Ø  Generalmente:

      Sea:

      q = q1, q2… qn

      z = z1, z2….zn

      P(Zj) = S P(qi, Zj) = S P(Zj / qi) P(qi) Probabilidad a Posteriori

      P(qi / Zj) = P(qi, Zj)/P(Zj) = P(Zj / qi) P(qi)/S P(Zj/qi) P(qi) Probabilidad de Bayes

      Suponga que el % de defectuosos en un lote bueno = 4%

      Suponga que el % de defectuosos en un lote malo = 15%

      Ø  Aplicando Distribución Binomial:

      P(X = k) = (n k) pk qn-k k = 0, 1, 2…n

      P(Z1/q1) = (0.96)2 (0.04) = 0.922

      P(Z2/q1) = (0.96) (0.04) = 0.0768

      P(Z3/q1) = (0.96) (0.04)2 = 0.0016

      P(Z1/q2) = (0.85)2 (0.15)  = 0.7225

      P(Z2/q2) = (0.85) (0.15)   = 0.255

      P(Z3/q2) = (0.85) (0.15)2 = 0.0225

      P(Zj/qi) :

      Z1 Z2 Z3
      q1 0.922 0.0768 0.0016
      q2 0.7225 0.255 0.0225

      Bueno = P(q = q1) = 0.95                       Malo = P(q = q2) = 0.05

      Ø  Hallando las Prob. Conjuntas

      P(qi Zj) = P(Zj / qi) P(qi)

      P(qi, Zj) :

      Z1 Z2 Z3
      q1 0.8759 0.07296 0.00152
      q2 0.036125 0.01275 0.001125

      P(Zj) = S P(Zj / qi) P(qi)

      P(Zj) = S P(qi / Zj)

      P(Z1) =  0.912025

      P(Z2) =  0.08571

      P(Z3) =  0.002645

      P(qi/Zj) = P(qi, Zj) / P(Zj)

      P (qi / Zj) :Prob. a posteriori

      Z1 Z2 Z3
      q1 0.96039 0.85124 0.57467
      q2 0.03961 0.14876 0.42533
      • La probabilidad de sacar dos artículos defectuosos de uno bueno es 0.57467
      • La probabilidad de sacar dos artículos buenos de uno bueno es 0.96039
      • La probabilidad de sacar un artículo bueno de uno malo es 0.85124

      5.2  DECISIONES BAJO INCERTIDUMBRE: No se dispone de ninguna función densidad de probabilidad. No implica ignorancia completa sobre el tema.

      F(Cj): No se conoce o no puede determinarse.

      Se conoce: Cj’, Cj’’; Cj’’’

      1.      Criterio de Laplace.

      2.      Criterio Mínimas.

      3.      Criterio Savage.

      4.      Criterio de Hurwicz.

      Estados de la Naturaleza

      q1 q2 q3
      a1 V(a1, q1) V(a1, q2) V(a1, qn)
      a2 V(a2, q1) V(a2, q2) V(a2, qn)
      am V(am, q1) V(am, q2) V(am, qn)
      • Para el estudio de las decisiones bajo incertidumbre tomamos como base el siguiente tablero (matriz) de posibles acciones y estados de ocurrencia que tendría que tomar el decisor.

      1.CRITERIO DE LAPLACE.- este enfoque interpreta las condiciones de “incertidumbre” como equivalente a supuesto de que todos los estados de la naturaleza tienen la misma probabilidad. El punto de vista de este “Si nada se, entonces todo es igualmente posible” por ejemplo, en el problema del vendedor de periódicos, tenemos la tabla de retribuciones siguiente:

      Decisión Estados de la Naturaleza
      0 0 0 0 0
      1 -10 15 15 15
      2 -20 5 30 30
      3 -30 -5 20 45

      Suponer que todos los estados de la naturaleza tengan la misma probabilidad significa que, dado que son 4, la probabilidad de que ocurran es de 0.25 para c/u. La elección de estas probabilidades convierte al problema en una decisión bajo riesgo y entonces se puede calcular el rendimiento esperado; eligiendo la acción ai que proporciona la ganancia mayor esperada.

      Max ai = 1/n S V(ai, qj)

      Donde 1/n es la probabilidad de que ocurra qj = (0, 1, 2, 3)

      UE0 = 0(1/4) + 0(1/4) + 0(1/4) + 0(1/4) = 0

      UE1 = -10(1/4) + 15(1/4) + 15(1/4) + 15(1/4) = 8.75

      UE2 = -20(1/4) + 5(1/4) + 30(1/4) + 30(1/4) = 11.25 MAXIMA UTILIDAD

      UE3 = -30(1/4) + (-5)(1/4) + 30(1/4) + 45(1/4) = 7.5

      Ø  LA DECISION OPTIMA ES COMPRAR DOS PERIODICOS

      Aunque en algunas situaciones este enfoque de igual probabilidad puede producir resultados aceptables, en otros podría ser inadecuado.

      2. CRITERIO MÍNIMAX (MAXIMÍN).- Este criterio es el más conservador ya que se basa en lograr lo mejor de las peores condiciones posibles. El criterio elige la acción ai asociado a:

      min . max { V(ai, qj)} (Mínimax)

      Donde: V (ai, qj); representa la pérdida para el decisor.

      Ø  No se aplica a una matriz de beneficios o utilidades, sino se aplica para pérdidas y costos.

      En forma análoga si V (ai, qj) representa las ganancias, el criterio elige la acción así asociada a:

      max . min { V(ai, qj)} (Maximin)

      Ejemplo: Considere V(ai, qj) la representación de costo entonces el criterio minimax es aplicable al tablero siguiente:

      q1 q2 q3 q4
      a1 5 10 10 25 25
      a2 8 7 8 23 23
      a3 21 18 12 21 21
      a4 30 22 19 15 30

      3.  CRITERIO DE DEPLORACIÓN DE SAVAGE

      También conocido como Criterio de Deploración Minimax de Savage. El criterio MiniMax es muy conservador a tal punto que puede llevar a conclusiones ilógicas.

      Dado otro ejemplo la matriz de pedidos siguiente (ejemplo clásico)

      V(ai, qj) :

      q1 q2
      a1 11000 90
      a2 10000 10000

      Si aplicamos el criterio MinMax a esta matriz nos da como resultado la opción a2, pero la lógica se inclina por a1. El criterio de Savage rectifica este punto construyendo una matriz de pérdidas en la cual V(ai, qj) se reemplaza por:

      r(ai, qj)            la cual se define como:

      r(ai, qj) =         Max ak {V(ak, qj)} – V(ai, qj)            Si V es beneficio

      V(ai, qj) – Min ak {V(ak, qj)               Si V es costos o pérdidas

      r(ai, qj) es una representación de arrepentimiento del decisor como resultante de perder la mayor solución correspondiente a un estado futuro dado qj.

      La función r(ai, qj) se le conoce como matriz de Deploración.

      Luego mostrando los nuevos elementos r(ai, qj) se tiene lo siguiente:

      r(ai, qj) =

      q1 q2
      a1 1000 0 1000
      a2 0 9910 9910

      Ahora el criterio minimax proporciona a1 como se esperaba.

      Si V(ai, qj) es una función de beneficio o de pérdida, r(ai, qj) es una función de Deploración, la cual en ambos casos representa pérdidas. Por lo tanto únicamente el criterio minimax puede aplicarse a: r(ai, qj)

      4. CRITERIO DE HURWICZ.- Este criterio tiene en consideración un intervalo de actividades desde la más optimista hasta la más pesimista.

      Condición Optimista                         max.max{V(ai, qj)}

      Condición Pesimista                          max.min{V(ai, qj)}

      Suponer que:   V(ai, qj)  Representa beneficio.

      El criterio Hurwicz pondera el optimismo extremo y el pesimismo extremo para los pesos respectivos (a) y (1 – a)

      Donde:  a:  está en el intervalo 0 – 1    :            0 <= a <= 1

      Luego se tiene lo siguiente:

      Si V(ai, qj):  representa beneficio seleccione la acción que proporcione lo siguiente:

      max{a max V(ai, qj) + (1 – a) min V(ai, qj)}

      Para el caso que V(ai, qj) representa un costo, el criterio selecciona la acción que proporciona lo siguiente:

      min{a min V(ai, qj) + (1 – a) max V(ai, qj)}

      El parámetro alfa se le conoce como índice optimista:

      Cuando a = 1 = Criterio demasiado optimista

      a

      Cuando a = 0 = Criterio demasiado pesimista

      Cuando a = ½ sería un criterio razonable.

      Ejemplo: suponer que a = ½ en la matriz de costos siguiente

      V(ai, qj) :

      Matriz de costos

      q1 q2 q3 q4
      a1 5 10 18 25
      a2 8 7 8 23
      a3 21 18 12 21
      a4 30 22 19 15

      Min V(ai, qj)          Max V(ai, qj)              a Min V(ai, qj) + (1 – a) Max V(ai, qj)

      Min ai

      a1        5                                 25                                           15

      a2        7                                 23                                           15

      a3        12                               21                                           16.5

      a4        15                               30                                           22.5

      5.3 ÁRBOLES DE DECISIÓN

      Llamase árboles de decisión a aquellos que contienen tanto las probabilidades de los resultados, como los valores monetarios condicionales de estos resultados de modo que se pueden calcular los valores esperados.

      Valor Esperado

      (i) Probabilidades de Riesgo

      (ii) Valores Monetarios Condicionales del Resultado

      EJEMPLO: Se desea tomar una decisión entre ir al cine o quedarse en casa a ver Tv.

      EJEMPLO: Se desea invertir $1000 ya sea en la compra de acciones o en un depósito de una cuenta de ahorros. Opte por la mayor decisión.

      Supóngase que la cuenta de ahorros nos pagaría un interés del 5% si las acciones suben, se obtendrá  $1400, Si las acciones bajan se obtendrá $ 800

      Ø  RESPUESTA: LA DECISIÓN ES INVERTIR $1000 EN ACCIONES.


      EJEMPLO: Árboles de decisión para un problema de inversión en una planta:

      Stereo Industries LTD.  Debe decidirse si construir una planta grande o pequeña para producir una nueva tornamesa, que se espera tenga una permanencia en el mercado de 10 años.

      Una planta grande costará $2.800.000 en su construcción y puesta en operación, mientras que una planta pequeña costará solo $1.400.000

      El mejor estimado de la compañía da una distribución discreta de las ventas sobre un periodo de 10 años es:

      Demanda alta              = 0.5

      Demanda moderada    = 0.3

      Demanda baja             = 0.2

      El análisis de costo – volumen – utilidad hecho por la gerencia de Stereo Industries LTD. Indica estos resultados condicionales bajo las varias combinaciones de tamaño de planta y tamaño de mercado:

      1.      Una planta grande con una demanda alta producirá utilidades anuales por $1,000.000

      2.      Una planta grande con una demanda moderada producirá utilidades anuales por $600 000

      3.      Una planta grande con una demanda baja producirá pérdidas anuales por $700.000 debido a ineficiencias en la producción.

      4.      Una planta pequeña con una demanda alta solo producirá utilidades anuales  por $250.000 considerando el costo de las ventas perdidas por la inhabilidad de abastecer a los clientes.

      5.      Una planta pequeña con una demanda moderada producirá utilidades anuales de $450.000 porque el costo de las ventas perdidas será algo más bajo.

      6.      Una planta pequeña con una demanda baja producirá utilidades de $550.000 anuales porque el tamaño de la planta y el tamaño del mercado estarían ajustadas casi óptimamente.

      Ø  Se toma la decisión de construir una planta grande con una diferencia de $1,300.000

      $ 3,600.000 –

      $ 2,300.000

      $ 1,300.000

      III. SISTEMAS DE INVENTARIOS

      1.  INTRODUCCIÓN

      • ¿Qué cantidad comprar?
      • ¿Cuándo? Cada que tiempo hacer el pedido

      Ø  SOBREALMACENAMIENTO:

      §  Las frecuencias de pedidos son altas.

      §  El capital invertido por unidad es alto.

      Ventajas:

      §  Bajo costo de escasez de pedidos.

      Desventajas:

      §  Aumento de costo de almacenamiento.

      Ø  SUBALMACENAMIENTO:

      Ventajas:

      §  Baja frecuencia de pedidos.

      §  El capital invertido por unidad es relativamente bajo.

      Desventaja:

      §  Origina costo de escasez.

      Sistema Logístico:(Empresa Industrial)

      2. TÉCNICA ABC.- (TÉCNICA DE WILFREDO PARETO)

      Zona A: El 80% de la inversión total está representada por el 20% del total de artículos

      Zona B: El 15% de la inversión total está representada por el 25% del total de artículos

      Zona C: El 5% de la inversión total está representada por el 55% del total de artículos

      GRÁFICAMENTE:

      EJEMPLO: La siguiente relación muestra el consumo promedio anual de una serie de artículos correspondientes a una serie de construcciones metálicas. Confeccionar un gráfico ABC y recomendar las medidas necesarias para controlar estos stocks de la forma más conveniente posible.

      GRÁFICAMENTE:

      3. MODELO DE INVENTARIO GENERALIZADO

      Ø  Da respuesta a las siguientes preguntas:

      1. ¿Qué cantidad de artículos deben pedirse?
      2. ¿Cuándo debe efectuarse el pedido?

      Ø  Respuestas:

      1. Determinar la cantidad de pedido.
      2. Tipo de Sistema de Inventarios

      Ø  Los sistemas de inventarios pueden ser de 2 tipos:

      a) Sistema de Revisión Periódica con Intervalos de tiempos iguales.- determinar la cantidad a pedirse en el tiempo de manera que coincida con el inicio de cada intervalo de tiempo.

      b) Sistema de Revisión Continua.- determina un punto de pedido en el nivel de inventario.

      Se origina el Costo Total Anual de Inventario(CTAI) :

      CTAI = Costo de Compra + Costo Fijo + Costo de Almacenamiento + Costo de Escasez

      Costo de Compra                              : Precio que se paga por la cantidad a pedirse.

      Costo Fijo                                          : Costo que se incurre cuando hacemos un pedido.

      Costo de Almacenamiento               : Lo que cuesta tener stock el almacén.

      Costo de Escasez    : Cuando no tenemos disponible.


      GRÁFICAMENTE:

      4. COMPLEJIDAD DE LOS MODELOS DE INVENTARIOS:

      DEMANDA:

      Grado o nivel de complejidad matemática de un Sistema de Inventario

      Determinista

      §  Estática

      §  Dinámica

      Probabilística

      §  Estacionaria

      §  No Estacionaria

      Aunque el tipo de demanda es un factor principal del diseño del modelo de inventario, los factores siguientes pueden influenciar también la forma en que se formula el modelo.

      5. OTROS FACTORES:

      1. Demora en la Entrega: cuando se coloca un pedido, puede entregarse inmediatamente o puede requerir algún tiempo antes de que la entrega se efectúe. El tiempo entre la colocación de un pedido y su sentido se conoce como demora en la entrega. En general las holguras de entrega pueden ser determinadas o probabilísticas.

      2. Reabasto de Almacén: Aunque un sistema de inventarios puede operar con demoras en las entregas, el abastecimiento real del almacén puede ser instantáneo o uniforme. El instantáneo ocurre cuando el almacén compra de fuentes externas. El uniforme puede cuando el producto se fabrica totalmente dentro de la organización. En general un sistema puede operar con demanda positiva y también con reaprovisionamiento uniforme de almacén.

      3. Horizonte de Tiempo: El horizonte define el periodo sobre el cual el nivel de inventarios estará controlado, este horizonte puede ser finito o infinito dependiendo de la naturaleza de la demanda.

      4. Abastecimiento Múltiple: Un sistema de inventarios puede tener varios puntos de almacenamiento. En algunos casos estos puntos de almacenamiento están organizados de tal manera que un punto actúa como una fuente de abastecimiento para algunos otros puntos. Este tipo de operación puede repetirse a diferentes niveles de tal manera que un punto de demanda pueda de nuevo llegar a ser un  nuevo punto de abastecimiento. La situación usualmente se denomina sistema de abastecimiento múltiple.

      5. Número de Artículos: un sistema de inventarios puede comprender más de un artículo. Este caso es de interés, principalmente si existe alguna clase de interacción entre los diferentes artículos. Por ejemplo estos pueden competir en espacio o capital total limitados.

      5.1.  MODELOS DETERMINISTAS

      5.1.1  MODELO ESTÁTICO DE UN SOLO ARTÍCULO:
      El tipo más simple de modelo de inventarios ocurre cuando la demanda es constante en el tiempo con reabastecimiento instantáneo y sin escasez.

      Ø  Costo total de inventario CTI(y)

      Parámetros:

      b = Tasa de demanda o consumo.

      K = Costo fijo.

      H = Costo de almacenamiento.

      CTI (y) = K = Costos fijos y costos de almacenamiento por unidad de

      y/b tiempo.

      CTI (y) = K + h (y/2)

      y/b

      Minimizando CTI (y)

      d CTI (y) = d(K/y/b) + d[h (y/2)] = 0

      d CTI (y) = d(Kb/y) + d[h (y/2)] = 0

      d CTI (y) = – Kb/y2 + h/2 =0

      h/2 = Kb/y2

      y* = √ 2Kb/ h Þ Cantidad económica de pedido o modelo de Wilson.

      Fórmula que tiene que ver con el costo óptimo.

      CTI(y*) = √ 2Kbh

      PROBLEMA: La demanda diaria para una mercancía es aproximadamente 100 unidades. Cada vez que se coloca un pedido se origina un costo fijo de $100. el costo diario de mantener el inventario por unidad es de $0.02. si el tiempo de demora es de 12 días, determine el tamaño económico del lote y el punto de reordenación.

      b = 100 u/d

      K = $1000

      h = $0.02

      1) Determinación del lote económico.

      y* = √ 2Kb/ h = √ 2(1000)(100)/0.02

      y* = 1000 unidades

      2) Hallando el ciclo.

      t*0 = y*/ b = 1000u/100u/d

      t*0 = 10 días.    Considerando demora = 12 días

      12 – 10 = 2 días

      2*100 unidades = 200 unidades

      L = 2 días de anticipación.

      RESPUESTA: PEDIR 1000 UNIDADES CUANDO EL NIVEL DE INVENTARIOS LLEGUE A 200 UNIDADES.

      COSTO ÓPTIMO

      CTI (y*) = √ 2Kbh = √ 2(1000)(100)(0.02)

      CTI (y*) = $20 costo óptimo.

      5.1.2 MODELO ESTÁTICO DE MÚLTIPLES ARTÍCULOS CON    LIMITACIONES EN ALMACÉN

      CTU = Costo Fijo  + Costo de Almacenamiento

      CTU = Kb + h (y/2) ————- 1  (Un Artículo)

      y

      CTU (Y1, Y2, Y2, …Yn) = S [ Kibi + hi Yi ]…………..2  (Varios Artículos)

      yi          2

      Si:

      Vi = Volumen de un artículo.

      Yi = Cantidad de Artículos en Inventario.

      Además:

      Q = Volumen Total de Almacenamiento.

      S  Yi Vi <= Q ,  yi > 0

      Min  CTU (Y1, Y2, Y3,…Yn) = S [ Kibi + hi Yi ]

      yi           2

      S a:      S Yi <= Q

      Yi > 0

      1.Método de Lagrange (Multiplicadores de Lagrange (l):

      L(Y1, Y2, Y3,…Yn, l) = S [ Kibi + hiYi ] – l [S Yi Vi – Q]

      yi         2

      Aplicando derivadas para hallar valores Min:

      dL = 0 Þ - Ki bi + hi – l Vi = 0

      dYi                Y2i        2

      hi – l Vi = Ki bi

      2                  Y2i

      Yi =       2 Ki bi

      Ö hi – 2 l Vi

      Y*i =     2 Ki bi Þ  Fórmula  1

      Ö hi – 2 l Vi

      dL = 0 Þ – S Yi Vi – Q = 0  Þ  Fórmula   2

      l < 0

      PROBLEMA: Supóngase una bodega de 25000 m3 de espacio real de almacenamiento de productos agrícolas (maíz, trigo, fríjol).

      Este espacio ya toma una cuenta a lo que se requiere para maniobras de estiba. Las características de estos productos son:

      Demanda de productos agricolas

      Producto Demanda Constante Mensual bi Espacio Ocupado por Tonelada de Grano (Vi) Costo Fijo de Almacén (Ki) Costo de Almacenamiento x Tonelada (hi)
      i = 1 Maíz 2 Tn 1000 m3 $ 10000 $ 300
      i = 2 Fríjol 4 Tn 1000 m3 $ 5000 $ 100
      i = 3 Trigo 3 Tn 1000 m3 $ 15000 $ 200

      ¿Cuál es la Política Óptima del Inventario que minimiza los costos Totales?

      N° de Iteraciones l(l<=) Y*1 Y*2 Y*3 S Yi Vi – Q
      1 0.00 11.2 20.2 21.2 27400
      2 -0.05 10.0 14.1 17.3 16400
      3 -0.10 9.0 11.5 14.9 10400
      4 -0.15 8.2 10.0 13.4 6600
      5 -0.20 7.6 8.9 12.2 3700
      6 -0.25 7.1 8.2 11.3 1600
      7 -0.30 6.7 7.6 10.6 -100

      Valor de l = -0.30 <= l <= -0.25      Se toma –0.30 porque es mucho menor a cero.

      Por lo tanto la empresa debe pedir:

      6.7 Tn de Maíz, 7.6 Tn de Fríjol, 10.6 Tn de Trigo

      El volumen del almacén:

      6.7 x 1000 =   6700

      7.6 x 1000 =   7600

      10.6 x 1000 = 10600

      24900 m3

      5.2  MODELOS PROBABILÍSTICOS

      5.2.1.  MODELO DE LA REVISIÓN CONTINUA:

      Este modelo es un modelo probabilístico en el cual el almacenamiento se realiza continuamente y un pedido de tamaño “y” se coloca cada vez que el nivel de existencias llega a un cierto punto de re orden “R”. El objetivo es determinar los valores óptimos de “y” y de “R” que minimicen los costos esperados de inventario por unidad de tiempo. En este modelo, un año representa una unidad de tiempo.

      Los objetivos del modelo son:

      1. El tiempo de demora entre la colocación de un pedido y se recepción es estático.
      1. La demanda que no se satisface durante el tiempo de demora se deja pendiente para ser satisfecho en periodos posteriores.
      1. La distribución de la demanda durante el tiempo de demora es independiente del tiempo en que ocurre este.

      GRÁFICAMENTE:


      CTAI = Costo Fijo + Costo de Almacenamiento + Costo de Escasez.

      CTA I= Costo Total Anual en función de “y” y “R”

      CTA(y,R) = DK + h (y/2 + R – E {x}) + P D S

      y                                                 y

      x = Demanda (variable)

      y = Cantidad Ordenada x Ciclo.

      D = Demanda Total Esperada x Año.

      h = Costo de Mantenimiento de Inventario.

      K = Costo Fijo.

      P = Costo de Escasez x Unidad x Año.

      S = Cantidad Esperada de Escasez por ciclo (año).

      Inventario Promedio H = y + E(R – X)                              Inventario Inicial

      H = y + E(R – X) + E(R – X) Inventario Final

      2

      H = y/2 + E(R – X)                           Función Continua

      R – R{x}

      S = d S(x) f(x) dx = d (X – R) f(x) dx

      S = Cantidad de Escasez x Ciclo.

      S(x) =0            X <= R

      X – R              X > R

      dCTA (y,R) = 0

      dy

      DK + h PDS =  0   = DK + PDS = h

      y2 2         y2 y2 2

      y* = Ö 2 (DK + PDS) …..  Fórmula N° 1

      h

      dCTA (Y,R) = 0    =  h – (PD/y)  ∫ f(x) dx = 0

      dR

      ∫ f(x) dx = hy* ….        Fórmula N° 2

      PD

      S = Cantidad esperada, escasez = E[S(X)]

      Ø  Cuando S = 0 y R = µ  se convierte en:

      y* = Ö 2DK

      h

      Ø  cuando R = 0

      y* = ŷ  = Ö 2D(K + PE (x)

      h

      Ø  Cuando R = 0

      y* = ŷ  = PD

      h

      Algoritmo de Hadley y  Whitin:

      Si y = ŷ = Existen valore únicos para Y y R

      Si se cumple esta solución se continúa, sino no tiene solución.

      PROBLEMA: Supóngase K = 100, P = 10, h = 2, D = 1000 y la demanda durante un tiempo de entrega es una variable aleatoria con una distribución uniforme dada por:

      f(x) =   1/100; Si  0 <= x <= 100

      0       ; Si  x < 0 ó x > 100

      Paso N° 1:   Verificar si ŷ  >= ŷ

      ŷ = Ö 2D (K + PE(x)

      h

      E(x) = ∫ f(x) dx =  ∫ x/100 dx =  x2/2 0 x2/200 = x2/200

      E(x) = (100)2/200 – 0/200 = 50

      E(x) = 50

      ŷ = Ö 2(1000) (100 + (10) (50))

      2

      ŷ = 774.5 unidades

      Determinando ÿ:

      ÿ = PD/h = (10)(1000)/2 = 5000 unidades

      ÿ >= ŷ , ÿ es mayor e igual a ŷ

      Iteración N° 1:

      y1 = Ö 2DK/h

      y1 = Ö 2(1000)(100)/2 = 316

      R1 = ∫ f(x) dx =  hy1/PD

      ∫  dx/100 =  2(316)/10(1000) = 632/10000

      1/100 [100 – R1] = 0.0632

      R1 = 93.68

      Iteración N° 2:

      y1 = Ö 2D(K + PE[S(x)])/h

      E[S(x)] = ∫ (x – R1) f(x) dx

      ∫ (x – 93.68) (1/100) dx

      E[S(x)] = 0.19971

      y2 = Ö 2(1000) (100 + (10) (0.1971))

      2

      y2 = 319.5 unidades

      hallando R2:

      ∫ f(x) dx =  hy2/PD

      ∫ (1/100) dx =  2(319.5)/10(1000)

      R2 =93.61

      Iteración N° 3

      E[S(x)] = ∫ (x – R2) dx

      ∫ (x – 93.61) (1/100)dx

      E[S(x)] = 0.24016

      y3 = Ö 2(1000) (100 + (10) (0.24016))

      2

      y*3 = 319.8

      R3 = ∫ f(x) dx =  hy2/PD

      ∫ (1/100) dx =  2(319.8)/10(1000)

      R*3=93.604

      | R3 – R2 | = 0

      La cantidad óptima es  y*3 = 319.8

      Re orden óptimo es      R*3 = 93.604

      Y

      T

      5.2.2.  Modelos de un Solo Periodo: Este modelo de inventarios de un solo periodo ocurre cuando un artículo es ordenado una sola vez. Ejemplo: La industria de modas, un modelo determinado de automóvil o también artículos perecederos que tienen una vida corta (vegetales, carne, leche, etc) o artículos que se vuelven obsoletos rápidamente como las computadoras y las copiadoras electrónicas.

      1.  MODELOS DE DEMANDA INSTANTÁNEOS SIN COSTO FIJO: En este modelo se supone que la demanda total se satisface al inicio del periodo. Por lo tanto dependiendo de la cantidad demandada (D), la posición del inventario justamente después que la demanda ocurre, puede ser positiva (excedente o negativa).

      Está representado por la función de probabilidad (función de mantenimiento de inventarios)

      y – D,  si  y > D

      H(y):

      0       , si  y <= D

      0,  si  y > D

      G(y):

      D, si  y <= D

      E {C (y)}= Costo de Compra + Costo de Mtto. de Inventario + Costo de Escasez.

      E {C (y)}= C (y – x) + h ∫ H(y) f(D) dD + P ∫ t(y) f(D) dD

      Minimizando Costos

      d E {C(y)} = E{C(y)} = C(y – x) + h {∫ (y – D) f(D) dD + 0} + P {0 + ∫ (D – y) fD dD}

      dy

      ∫ f(D) dD = P – C

      P + h

      Si P >= C (Definida)

      Si P < C (Descartar el Sistema)

      • El valor de y* se selecciona de tal modo que la probabilidad D <= y* sea igual a:

      q = P – C

      P + h

      , Con P > C

      La política de reordenamiento óptimo dado x antes de que un pedido se coloque es:

      Si  y* > x;  pedir y* – x

      Si y* <= x;  no pedir nada

      • Para el caso discreto se tendrá:

      P (D <= y* – i) <= P – C <= P (D <= y*)

      P + h

      Problema: Considere un artículo que se producirá una sola vez, con una demanda continua de consumo instantáneo, distribuida uniformemente y dada por:

      f(D) =  1/10   0 <= D <= 10

      0        D > 10

      Supóngase que :

      h = $0.5,  P = $4.5,  C = $0.5

      Se pide hallar la política de reordenamiento óptimo.

      Solución:

      P (D <= y*) ∫ f(D) dD = P – C = ∫ 1/10 dD =  4.5 – 0.5 =  y* = 0.8

      P + h                         4.5 + 0.5

      Si x < 8;  Pedir 8 – x

      Si x > 8;  No pedir

      PROBLEMA: Considere un tipo de avioneta que tiene demanda discreta de consumo instantáneo como lo que se describe a continuación, y para lo que el costo unitario de producción es de 2 millones de dólares, el costo unitario de mantenimiento es de 1 millón de dólares y el costo unitario penal (producción extra imprevista) a 4 millones de dólares ¿Qué política óptima de producción de seguirse?

      Demanda de avioneta

      D f(D) f(D) (Acumulado)
      0 0.10 0.10
      1 0.20 0.30
      2 0.20 0.55
      3 0.20 0.75
      4 0.15 0.90
      5 0.10 1.00
      6 o más 0.00 1.00

      h = 1,   P = 4,  C = 2

      P – C/P + h  =  4 – 2/4 + 1  =  2/5 = 0.4

      P{D <= 1} = 0.3 < 0.4 < 0.55 = P{D <= 2}

          • y* = 2 unidades

      2. MODELO DE DEMANDA UNIFORME SIN COSTO FIJO

      Inventario Promedio:

      y = D/2

      Inventario Promedio:

      y2/2D

      Inventario Promedio de Escasez:

      (D – y)2/2D

      Costo Esperado:

      ∫ f(D) dD + y* ∫ f(D)/D dD  =  P – C/P + h = q

      EJEMPLO: Supóngase un producto con demanda aleatoria de consumo uniforme distribuido de la siguiente forma:

      1/10 ;  Si 0 <= D <= 10

      f(D)

      0      ;  Si D < 0 ó D > 10

      h = $0.5,  P = $4.5,  C = $0.5

      ¿Cuál es la política óptima de producción o reorden:

      ∫ 1/10 dD + y* ∫ 1/10D dD  =  4/5  = 0.8

      (1/10) (y* – y* Ln y* + 2.3 y*) = 0.8

      Resolviendo la ecuación por ensayo de error:

      y* = 4.5 unidades

      Si  x < 4.5 = Se ordena un pedido de 4.5 – x.

      Si  x > 4.5 = No se ordena nada.

      3. MODELO DE INVENTARIOS DE DEMANDA INSTANTÁNEA Y COSTO FIJO

      E {C(y)} = k + C (y – x) + h ∫ (y – D) f(D) dD + P ∫ (D – y) f(D) dD

      Gráficamente

      Ø  Se presenta 3 casos:

      Primer Caso:

      Si x < S;  Ordenar S – x

      Segundo Caso:

      S = y*

      Si S <= x <= S

      y* = x

      Tercer Caso:

      Si x > S;  para y > x

      y* = x

      Resumen (Modelo de Inventario s – S)

      Si x <   S;  pedir S – x

      Si x >= S;  no pedir nada

      EJEMPLO: Suponga un artículo de consumo instantáneo, que tiene una producción única y cuyo costo de producción es de k = $25. el costo unitario de mantenimiento es de h = $0.5, el costo unitario penal = P $4.5 y el costo unitario de producción C = “0.5.

      La demanda tiene una distribución dada por:

      f(D)     1/10,  Si 0 <= D <= 10

      0,       Si 10 < D

      Solución:

      1.-  Hallar S:

      ∫ 1/10 dD = 0.8  =  S = 8 Unidades.

      2.- Encontrar el valor de s

      E{C(y)} = 0.5 (y – x) + 0.5 ∫ (y – D) dD + 4.5 ∫ 1/10 (D – y) dD

      E{C(y)} = 0.25 y2 – 4.0 y + 22.5 – 0.5 x

      E{C(s)} = k + E{C(S)}

      E{C(s} = 0.25 S2 – 4.0S + 22.5 – 0.5x = 25 + 0.25S2 – 4.0S + 22.5 – 0.5x

      Reemplazando S = 8

      S2 – 16S – 36 = 0

      S1 = -2                                   S2 = 18       Se elimina porque S2 > S = 18 > 8

      Por definición:            y >= 0

      Entre –2 y 0, nos quedamos con cero y establecemos la siguiente política:

      Si x <= 0;   Ordenar 8 – x

      Si x > 0  ;   No ordenar nada.

      IV. PROYECTOS CON PERT – CPM

      1. CASO DE ESTUDIO: CONSTRUCCION COMPLEJO DEPORTIVO

      Una urbanización está evaluando la construcción de un complejo deportivo de propósitos múltiples. El complejo ofrecerá un gimnasio nuevo para juegos intercolegiales de basketball, oficinas y salones.

      Las actividades que habrá que emprender antes de comenzar la construcción son las que se muestran enseguida.

      Actividad Descripción Predecesores Duración
      A Levantamiento topográfico —– 6
      B Ejecución de diseño —– 8
      C Aprobación del concejo A, B 12
      D Elección del arquitecto C 4
      E Fijación del presupuesto C 6
      F Finalización del diseño D, E 15
      G Obtención del financiamiento E 12
      H Contratación del constructor F, G 8

      a) Desarrolle una red CPM para este proyecto.

      b)
      Identifique la ruta crítica.

      Considere la red de la figura siguiente la cual comienza en el nodo 0 y termina en el nodo 6.

      7

      Consideraciones de Probabilidad en la Programación de Proyectos

      Actividad (i, j) Tiempos Estimados (a, b, m) Actividad (i, j) Tiempos Estimados (a, b, m)
      (0,1) (1; 3; 2) (3, 5) (1; 7; 2.5)
      (0,2) (2, 8 ; 2) (3, 6) (1; 3; 2)
      (1,3) (1; 3; 2) (4, 5) (6; 8; 7)
      (2,3) (1; 11; 1.5) (4, 6) (3; 11; 4)
      (2,4) (0.5; 7.5; 1) (5, 6) (4; 8; 6)
      Actividad (i, j) Dij Vij Actividad (i, j) Dij Vij
      (0,1) 2 0.11 (3, 5) 3 1.00
      (0,2) 3 1.00 (3, 6) 2 0.11
      (1,3) 2 0.11 (4, 5) 7 0.11
      (2,3) 3 2.78 (4, 6) 5 1.78
      (2,4) 2 1.36 (5, 6) 6 0.44

      a = Tiempo Optimista.

      b = Tiempo Pesimista.

      c = Tiempo más Probable.

      Observando los Sesgos

      Dij = a + b + 4m / 6

      Vij = (b – a / 6)2

      Evento Ruta E{ui} Var{ui} Tpi Ki P{Z<=Ki}
      1 (0, 1) 2 0.11 4 6.03 1.00
      2 (0, 2) 3 1.00 2 -1.00 0.159
      3 (0, 2, 3) 6 3.78 5 -0.514 0.304
      4 (0, 2, 3, 4) 6 3.78 6 0.000 0.500
      5 (0, 2, 3, 4, 5) 13 3.89 17 2.028 0.987
      6 (0, 2, 3, 4, 5, 6) 19 4.33 20 0.480 0.684

      Ki = Tpi – E{Ui} / Ö var{Ui}

      Var{Ui} = S Vk

      P{Ui <= Tpi} = P {Z <= Ki}

      2. CONSIDERACIONES DE COSTO EN PROYECTOS

      Pendiente = Cc – Cn / Dn – Dc

      Dn = Duración Normal

      Cn = Costo Normal

      Actividad
      (i, j)
      Normal Mínimo de Duración Costo
      Demanda Costo
      (1,2) 8 100 6 200
      (1,3) 4 150 2 350
      (2,4) 2 50 1 90
      (2,5) 10 100 5 400
      (3,4) 5 100 1 200
      (4,5) 3 80 1 100

      Actividad
      (i, j)
      Pendiente
      (1,2) 50
      (1,3) 100
      (2,4) 40
      (2,5) 60
      (3,4) 25
      (4,5) 10

      Costo = 580 + (18 – 17)50 = $630

      Tiempo = 17 días

      Costo = 630 + (17 – 16)50 = $680

      Tiempo = 16 días

      V. BIBLIOGRAFIA

      1.     Eppen G.D , Gould F.J, Schmidt C.P. Investigaciòn de operaciones en la Ciencia

      Administrativa

      2.     Hiller, Frederics.Introduccion a la Investigación de Operaciones, Quinta

      Edicion, 1991_MC_Graw_Hill

      3.     Kaufman, Arnold.Metodos y Modelos de Investigacion de operaciones,Quinta

      Edicion, 1984, CECSA

      4.     Levin, Richard I. Kirkpatrick, Charles A. Enfoques Cuantitativos a la

      Administración. Primera Edicion, 1983

      5.     Lumberger David, Programación Lineal y no Lineal. Wesley ED Addison,

      Iberoamericana, 1989, EUA.

      6.     Nagui,Mohammad. Investigación de Operaciones. Interpretación de Modelos y

      Casos. Editorial Limusa, 1996, México

      7.     Prawda , Juan. Métodos y Modelos de Investigación de Operaciones, volumen 1:

      Modelos Deterministicos, Octava Reimpresión, 1989, Limusa Mexico.

      8.     Taha, Hamdy A., Investigación de Operaciones. Sexta edición 1999, Alfa y Omega S.A. Mexico

      9.  Web Site:

      Ø http://www.elprisma.com

      Ø http://selva.dit.upm.es/  cd/apuntes/tema3/tema3.html

      Ø http://ekeko.rcp.net.pe/rcp/listas/ioper/iosa.html

      I.    LA INVESTIGACIÓN DE OPERACIONES, USO DE MODELOS Y  METODOS DE OPTIMIZACION

      I.1 INTRODUCCION  A  LA INVESTIGACIÓN DE OPERACIONES

      1. Un poco de Historia

      Se inicia desde la revolución industrial, en los libros se dice que fue a partir de la segunda Guerra Mundial. La investigación de operaciones se aplica a casi todos los problemas. En 1947, en EE.UU., George Datzing encuentra el método simplex para el problema de programación lineal. En la investigación de operaciones, las computadoras son la herramienta fundamental en la investigación de operaciones.

      2. Definición

      La Investigación de Operaciones, es la aplicación del método científico por un grupo multidisciplinario de personas a un problema, principalmente relacionado con la distribución eficaz de recursos limitados (dinero, materia prima, mano de obra, energía), que apoyados con el enfoque de sistemas (este enfoque, es aquel en el que un grupo de personas con distintas áreas de conocimiento, discuten sobre la manera de resolver un problema en grupo.). Puede considerarse tanto un arte como una ciencia. Como arte refleja los conceptos eficiente y limitado de un modelo matemático definido para una situación dada. Como ciencia comprende la deducción de métodos de cálculo para resolver los modelos.

      2.1 Pasos del Método científico en IO

      1. Definición del problema.- Desde el punto de vista de la Investigación de operaciones(IO),esto indica tres aspectos principales:(a)Una descripción de la meta o el objetivo del estudio,(b)Una Identificación  de las alternativas de decisión y (c) Un reconocimiento de las limitaciones, restricciones y requisitos del sistema

      2. Construcción del Modelo._Dependiendo de la definición del problema, el equipo de investigación de operaciones deberá decidir sobre el modelo mas adecuado para representar el sistema (modelo matemático,  modelo de simulación; combinación de modelos matemáticos, de simulación y heurísticos)

      3. Solución del Modelo.- En modelos matemáticos esto se logra usando técnicas de optimización bien definidas y se dice que el modelo proporciona una solución optima. Si se usan los modelos de simulación o heurísticos el concepto de optimalidad no esta bien definido, y la solución en estos casos se emplea para obtener evaluaciones aproximadas de las medidas del sistema

      4.Validación del Modelo.- Un modelo es valido si, independientemente de sus inexactitudes al representar el sistema, puede dar una predicción confiable del funcionamiento del sistema

      5. Implantación de los resultados Finales.-La tarea de aplicar los resultados probados del sistema recae principalmente en los investigadores de operaciones. Esto básicamente implicaría la traducción de estos resultados en instrucciones de operación detallada, emitidas en una forma comprensible a los individuos que administraran y operaran el sistema después. La interacción del equipo de investigación de operaciones y el personal de operación llegara a su máximo en esta fase.

      I.2 TIPOS DE MODELOS  DE INVESTIGACION DE OPERACIONES

      Un modelo es una representación ideal de un sistema y la forma en que este opera. El objetivo es analizar el comportamiento del sistema o bien predecir su comportamiento futuro. Obviamente los modelos no son tan complejos como el sistema mismo, de tal manera que se hacen las suposiciones y restricciones necesarias para representar las porciones más relevantes del mismo. Claramente no habría ventaja alguna de utilizar modelos si estos no simplificaran la situación real. En muchos casos podemos utilizar modelos matemáticos que, mediante letras, números y operaciones, representan variables, magnitudes y sus relaciones.

      Fig.1.2: Representación de un modelo

      1. Modelos Matemáticos

      Un modelo es producto de una abstracción de un sistema real: eliminando las complejidades y haciendo suposiciones pertinentes, se aplica una técnica matemática y se obtiene una representación simbólica del mismo.  Un modelo matemático consta al menos de tres conjuntos básicos de elementos:

      Ø  Variables de decisión y parámetros

      Las variables de decisión son incógnitas que deben ser determinadas a partir de la solución del modelo. Los parámetros representan los valores conocidos del sistema o bien que se pueden controlar.

      Ø  Restricciones

      Las restricciones son relaciones entre las variables de decisión y magnitudes que dan sentido a la solución del problema y las acotan a valores factibles. Por ejemplo si una de las variables de decisión representa el número de empleados de un taller, es evidente que el valor de esa variable no puede ser negativo.

      Ø  Función Objetivo

      La función objetivo es una relación matemática entre las variables de decisión, parámetros y una magnitud que representa el objetivo o producto del sistema. Por ejemplo si el objetivo del sistema es minimizar los costos de operación, la función objetivo debe expresar la relación entre el costo y las variables de decisión. La solución ÓPTIMA se obtiene cuando el valor del costo sea mínimo para un conjunto de valores factibles de las variables. Es decir hay que determinar las variables x1, x2,…, xn que optimicen el valor de Z = f(x1, x2,…, xn) sujeto a restricciones de la forma g(x1, x2,…, xn) £ b. Donde x1, x2,…, xn son las variables de decisión Z es la función objetivo, f es una función matemática.

      EJEMPLO 1.2.1: Sean X1 y X2 la cantidad a producirse de dos productos 1 y 2, los parámetros son los costos de producción de ambos productos, $3 para el producto 1 y $5 para el producto 2. Si el tiempo total de producción esta restringido a 500 horas y el tiempo de producción es de 8 horas por unidad para el producto 1 y de 7 horas por unidad para el producto 2, entonces podemos representar el modelo como:

      MinZ =  3X1 + 5X2       (Costo total de Producción)

      Sujeto a (S.A):

      8X1 + 7X2  £  500    (Tiempo total de producción)

      X1, X2>= 0       (Restricciones de no negatividad)

      EJEMPLO 1.2.2: En una empresa se fabrican dos productos, cada producto debe pasar por una máquina de ensamblaje A y otra de terminado B,antes antes de salir a la venta.El producto 1 se vende a $60 y el otro a $50 por unidad. La siguiente tabla muestra el tiempo requerido por cada producto:

      Producto Maquina A Maquina B
      1 2 H 3 H
      2 4 H 2 H
      Total disponible 48 H 36 H

      Para representar el modelo de este problema primero se debe    determinar      las   variables de decisión: Sea Xi: La cantidad a fabricar del producto 1 y 2 (i=1,2), entonces X1: cantidad a fabricar del producto 1, X2: cantidad a fabricar del producto2, luego el modelo quedaría de la siguiente manera:

      MaxZ =  60X1+ 50X2           (máximo ingreso por ventas)

      S.A:    2X1+ 4X2  <= 48   (disponibilidad horas _maquina A)

      3X1+ 2X2 <= 36  (disponibilidad horas _maquina B)

      X1, X2  >= 0      (Restricciones de no negatividad)

      2. Modelos  de Simulación

      La simulación es una técnica para crear modelos de sistemas grandes y complejos que incluyen incertidumbre. Se diseña un modelo para repetir el comportamiento del sistema. Este tipo de modelamiento se basa en la división del sistema en módulos básicos o elementales que se enlazan entre sí mediante relaciones lógicas bien definidas (de la forma SI / ENTONCES). El desarrollo de un modelo de simulación es muy costoso en tiempo y recursos.

      II. PROGRAMACION LINEAL

      II.1 INTRODUCCION A LA PROGRAMACION LINEAL

      1. INTRODUCION

      La programación Lineal (PL) es una técnica de modelado matemático, diseñada para optimizar el empleo de recursos limitados. La programación lineal se aplica exitosamente en el  ejercito, en la agricultura, la industria, los transportes, la economía, los sistemas de salud, en el ejercito e incluso en los sistemas conductuales y sociales.

      La utilidad de esta técnica se incrementa mediante el uso y disponibilidad de programas de computadora altamente eficientes. De hecho la PL, debido a su alto nivel de eficiencia computacional, es la base para el desarrollo de algoritmos de solución de otros tipos (más complejos) de modelos de IO, incluyendo la programación entera, no lineal y estocástica.

      2. MODELOS DE PROGRAMACION LINEAL

      Para formular un problema de programación lineal se debe tener presente que la función objetivo y  todas las restricciones deben ser lineales y todas las variables deben ser continuas (pueden asumir valores fraccionales).

      2.1 SOLUCIÓN GRAFICA DE PL: Los modelos de PL que se resuelven por el método geométrico o grafico solo son apropiados  para casos en que el número de variables son a lo más dos.

      EJEMPLO 2.1.1: UN PROBLEMA DE MINIMIZACION (Contratación de Personal): El  departamento de control de calidad de la empresa Gerconsa S.A que fabrica autopartes, desea contratar personal tanto senior como junior, para las inspecciones de sus productos.

      El personal senior recibe por su jornada  de 8hrs., $188y realiza su labor a una tasa promedio de 30 inspecciones por hora, con un rendimiento del 99%.en cambio el personal junior, recibe $150 por su jornada, realizando 25 inspecciones por hora, con un rendimiento del 95%.

      La demanda diaria de inspecciones es de 1600 unidades y el personal senior a contratar, no debe ser mayor que el personal júnior.

      Si las ensambladoras aplican una multa  de $5 por cada unidad defectuosa, ¿cuánto de personal senior y júnior, se debe contratar?

      SOLUCION:

      La formulación del modelo al problema de minimización seria:

      Sea Xi: Numero de personal a contratar (i = senior, j = junior o

      i =1,2)

      La función objetivo consistiría en minimizar los costos de salario y los de castigo por unidad defectuosa

      Z = Salario + Multa

      Salario = 118×1+ 150×2

      Multa = (30*8*0.01X1+ 25*8*0.05X2)*5

      Luego la función objetivo es:

      MinZ =  200X1+ 200X2 y sujeta a las restricciones:

      30(8) X1+25(8) X2>=1600 (Demanda diaria)

      X1<= X2                    (Relación personal)

      Finalmente el modelo se reduce a:

      MinZ =  200X1 + 200X2

      S.A.:   6X1+ 5X2 >=40     (1)

      X1 –  X2  <=0       (2)

      X1, X2 >=0

      Gráficamente  y después de haber utilizado el amigable software TORA el problema quedaría así:

      Fig.2.1: Solución grafica (optima) al problema de contratación de personal

      Este modelo pudo haberse resuelto  fácilmente graficando en las coordenadas X1 y X2  y  hallando el punto de intersección común a ambas rectas. Se puede ver que  la intersección de  recta de la función objetivo con las rectas 1 y 2 lo hace dentro de la región factible y en su punto mínimo (punto optimo), después de haber resuelto algebraicamente por sistemas de ecuaciones simultaneas las restricciones 1 y 2 tenemos finalmente el punto optimo mínimo para el problema:

      X1=3.64

      X2=3.64

      Z*=1454.55

      De los resultados puede verse que tenemos valores fraccionarios para un problema de contratación de personal lo cual es inapropiado dado que se trata del recurso humano, sin embargo solo se ha resuelto para efecto demostrativo grafico (además no olvidemos que  en PL las variables son continuas), ya que la programación lineal entera se encarga de darle una solución Optima a este problema.

      EJEMPLO 2.1.2: UN PROBLEMA DE MAXIMIZACION. Javier Cutipe  es un  exitoso vendedor de la distribuidora de gaseosas Gerconsa y  tiene que decidir como asignar sus esfuerzos entre los diferentes tipos de clientes de las zonas de Moquegua que le han dado (san Antonio, san francisco, la villa los ángeles, samegua,  y chen chen).Puede visitar comerciantes y clientes que compran al menudeo. Una visita a un comerciante usualmente le produce S/.400 en ventas, pero la visita en promedio dura 2horas y debe manejar también en promedio, 10 kilómetros. En una visita a un comprador al menudeo le vende S/.500 y requiere de unas 3horas y 20 kilómetros manejando el carro aproximadamente. Javier viaja trabajando como máximo, 600kilometros por semana en su propio carro y prefiere trabajar nomás de 36 horas por semana. Construya un modelo de programación lineal para Javier Cutipe Mamani

      SOLUCION:

      Sea: X1: Numero de comerciantes

      X2: Numero de clientes al menudeo

      El modelo resultante es:

      Max Z= 400X1+500X2           (Ingreso por ventas brutas)

      S.A:       2X1+3X2 <= 36    (restricción de horas semanales)      (1)

      10X1+20X2<=600  (restricción de distancia recorrida)  (2)

      X1,X2>=0           (Restricción de no negatividad)

      Fig.2.2: Solución grafica (optima) al problema de Javier Cutipe

      El modelo anterior se resuelve gráficamente aplicando Tora, también pudo haberse resuelto  fácilmente graficando en las coordenadas X1 y X2  y  hallando el punto de intersección común a la recta (1) con el eje X1, la recta de  la función objetivo alcanza su nivel máximo (punto optimo) en la región factible para X1=18 y X2=0, esto algebraicamente  es después de haber resuelto la restriccion1 (ecuacion1) y haciendo x2=0 en la misma ecuación

      (nótese que la restricción 2 es redundante). Finalmente el punto óptimo mínimo para el problema es de:

      X1=18

      X2=0

      Z*= S/.7200

      Este resultado nos dice que Javier Cutipe deberá concentrar sus esfuerzos solo en la venta a 18 comerciantes dado que alli maximizara sus ingresos por ventas en S/.7200

      2.2 SOLUCIÓN POR COMPUTADORA DE PROBLEMAS DE PL

      En la practica, donde los modelos típicos  de programación Lineal implican cientos, o incluso miles de variables y restricciones, la única forma de resolver estos problemas es utilizando un programa apropiado de computadora. En el mercado informático existen softwares que tienen módulos de programación lineal (PL)  tal como el Tora, Storm, Programas como el lindo, lingo, etc. También se puede hacer uso de Solver en Excel para resolver problemas de PL.

      EJEMPLO 2.2.1: La figura 2.3  presenta la solución de TORA para el problema de contratación de personal del ejemplo 2.1.1

      Fig.2.3: Solución óptima usando TORA

      La información de salida  se divide en dos partes principales (1) resumen de la solución óptima (optimum solution sumary) que comprende los valores óptimos de las variables de decisión y el valor optimo de la función Objetivo y (2) Análisis de sensibilidad (Sensitivity análisis) referente a hacer cambios en el lado derecho(right-and sides) y en los coeficientes de la función objetivo

      EJEMPLO 2.2.2: La figura 2.4  presenta la solución de LINDO para el problema de Javier Cutipe del ejemplo 2.1.2

      LP OPTIMUM FOUND AT STEP      1

      OBJECTIVE FUNCTION VALUE

      1)      7200.000

      VARIABLE              VALUE                         REDUCED COST

      X1                     18.000000                             0.000000

      X2                      0.000000                          100.000000

      ROW            SLACK OR SURPLUS     DUAL PRICES

      2)            0.000000              200.000000

      3)        420.000000                  0.000000

      NO. ITERATIONS=       1

      RANGES IN WHICH THE BASIS IS UNCHANGED:

      OBJ COEFFICIENT RANGES

      VARIABLE            CURRENT        ALLOWABLE      ALLOWABLE

      COEF                 INCREASE           DECREASE

      X1                  400.000000           INFINITY             66.666664

      X2                              500.000000           100.000000            INFINITY

      RIGHTHAND SIDE RANGES

      ROW         CURRENT        ALLOWABLE        ALLOWABLE

      RHS               INCREASE               DECREASE

      2              36.000000            84.000000                        36.000000

      3            600.000000            INFINITY                     420.000000

      Fig.2.4: Solución óptima usando LINDO

      2.3 ANALISIS DE ALGUNOS MODELOS DE PL: Se presentan algunos modelos realistas de  de PL, en los cuales las definición de variables y la construcción de la función objetivo y de las restricciones  no son tan directas como en el caso de los modelos de dos variables. Además la salida de TORA de la computadora para cada modelo permitirá interpretaciones muy claras  de las soluciones.

      EJEMPLO 2.3.1: Un  distribuidor de ferretería planea vender paquetes de tuercas y tornillos mezclados. Cada paquete pesa por lo menos 2 libras. Tres tamaños de tuercas y tornillos componen el paquete y se compran en lotes de 200 libras. Los tamaños 1 ,2 y 3 cuestan respectivamente $20, $80 y $12, además:

      a. El peso combinado de los tamaños 1y 3 debe ser al menos la mitad del peso total del paquete

      b. El peso de los tamaños 1 y 2  no debe ser mayor que 1,6 libras

      c. Cualquier tamaño de tornillo debe ser al menos 10 porciento del paquete total

      ¿Cuál será la composición del paquete que ocasionara un costo mínimo? (formule solamente el modelo de pl.)

      SOLUCION:

      Formulación

      Sea :   X1  =  peso de las unidades de tamaño 1

      X2  =  peso de las unidades de tamaño 2

      X3  =  peso de las unidades de tamaño 3

      De este modo se tendrán las siguientes Restricciones:

      x1+ x2+ x3 >=2 peso mínimo de cada paquete

      X1 +X3  >= (X1+ X2+ X3)/2   Peso combinado d e l os tamaños 1 y 3

      X1+ X2 <=1.6                          Peso combinado de 1 y 2

      X1>=0.10(X1+ X2+ X3)        Condición de peso para cualquier tamaño

      X2>=0.10(X1+ X2+ X3)

      X3>=0.10(X1+ X2+ X3)

      Siendo la función  MinZ =  20X1+ 80X2+ 12X3)/200, en resumen se tiene el siguiente modelo:

      MinZ = 0.1X1+0.04X2+0.06X3

      S.A:      X1+ X2+ X3        >= 2

      X1 – X2+ X3        >=0

      X1+ X2                <=1.6

      0.9X1-0.1X2-0.1X3  >=0

      -0.1X1+0.9X2-0.1X3 >=0

      -0.1X1-0.1X2+0.9X3 >=0

      X1, X2, X3  >=0

      Fig.2.5: Solución óptima usando TORA

      Del resultado del sotware Tora se puede ver que la solución optima es :

      X1* = 0.20

      X2* = 1.00

      X3* = 0.80

      Z*= 0.11

      EJEMPLO 2.3.2: Al mezclar diferentes hidrocarburos se obtiene gasolina de diferentes grados. En este ejemplo se supone que una refinería dispone sólo de dos tipos de gasolina cuyas características se presentan en la siguiente tabla:

      Mezclas disponibles Octanaje Presión de vapor Cantidad disponible (Barriles)
      Tipo 1 104 5 30,000
      Tipo 2 94 9 70,000

      Con la combinación de estos productos se pueden producir dos tipos de gasolina: para automóvil y aviación. Las cualidades de estos productos aparecen en la siguiente tabla:

      Producto final Mínimo octanaje Máxima presión de vapor Máxima venta (Barriles) Precio de venta (Barril)
      Aviación 102 6 20,000 45.10
      Automóvil 96 8 Sin tope 32.40

      El octanaje y la presión de vapor del producto resultante es proporcional a la cantidad de cada gasolina utilizada en la mezcla.

      Por ejemplo para partes iguales de ambas gasolinas:

      Octanaje: 0.5*104 + 0.5*94 = 99

      Presión de vapor: 0.5*5 + 0.5*9 = 7

      La empresa desea maximizar los ingresos por la venta de gasolina como producto final

      Formulación

      Sean x1 el número de barriles de gasolina del tipo 1 para aviación.

      X2 el número de barriles de gasolina del tipo 2 para aviación.

      X3 el número de barriles de gasolina del tipo 1 para automóvil.

      X4 el número de barriles de gasolina del tipo 2 para automóvil.

      La venta correspondiente a gasolina para aviación es 45.10*(x1 + x2) y la venta correspondiente a gasolina para automóvil es 32.40(x3 + x4) entonces la función objetivo es:

      Maximizar:

      Z = 45.10x1 + 45.10x2 + 32.40x3 + 32.40x4

      Existen varias restricciones:

      Demanda de gasolina para aviación:

      X1 + x2 £ 20,000

      Cantidad disponible por tipo de gasolina:

      X1 + x3 £ 30,000

      X2 + x4 £ 70,000

      Restricción de octanaje:

      Aviación: (104x1 + 94x2)/(x1 + x2) ³ 102 Û 2x1 – 8x2 ³ 0

      Automóvil: (104x3 + 94x4)/(x3 + x4) ³ 96 Û 8x3 – 2x4 ³ 0

      Restricción de presión de vapor:

      Aviación: (5x1 + 9x2)/(x1 + x2) £ 6 Û -x1 + 3x2 £ 0

      Automóvil: (5x3 + 9x4)/(x3 + x4) £ 8 Û -3x3 + x4 £ 0

      No negatividad:

      X1, x2, x3, x4 ³ 0

      En Resumen el modelo se presenta de la siguiente manera:

      MaxZ = 45.10x1 + 45.10x2 + 32.40x3 + 32.40x4

      X1 + x2 £ 20,000 Demanda de gasolina para aviación:

      X1 + x3 £ 30,000 Cantidad disponible por tipo de gasolina

      X2 + x4 £ 70,000 Cantidad disponible por tipo de gasolina

      2x1 – 8x2 ³ 0             Restricción de octanaje aviación

      8x3 – 2x4 ³ 0 Restricción de octanaje automóvil

      -x1 + 3x2 £ 0            Restricción de presión de vapor aviación

      -3x3 + x4 £ 0 Restricción de presión de vapor automóvil:

      X1, x2, x3, x4 ³ 0      Restricción de no negatividad

      Una vez Formulado el modelo matemático hacemos uso del  TORA para encontrar una solución óptima:

      X1*=16000.00

      X2*=4000.00

      X3*=4666.67
      X4*=14000.00

      Z*= 1506800.00

      Fig.2.6: Solución óptima usando TORA

      III. EL METODO SIMPLEX

      La idea general del método Simplex es comenzar en un punto extremo y desplazarse hacia un punto extremo adyacente con el objeto de mejorar el valor de la función objetivo, manteniendo la factibilidad. La manera más sencilla de seleccionar un punto extremo inicial es usar la base B constituida por variables de holgura y/o artificiales. De esta forma la base B inicial es la matriz identidad I que obviamente es una base. Los puntos extremos adyacentes se determinan intercambiando un vector de B con un vector no básico que moverá la solución hacia la optimalidad.

      Tabla Simplex en forma matricial

      Expresemos el programa lineal en forma matricial:

      Max z = CX

      Sujeto a: (AI)X =   b

      X >= 0

      Subdividamos el vector X en XI y XII, entonces el problema estándar se puede escribir de la siguiente manera: (I)

      1 -CI -CII z 0
      0 A I XI = b
      XII

      En una iteración cualquiera, sea XB La representación de las variables básicas y B su base asociada, entonces XB representa a m elementos de X y B representa los vectores de (AI) correspondientes a XB, y sea CB el vector de elementos de C asociado a XB.

      Entonces:

      B XB = b y z = CBXB

      o bien:

      1 -CB z = 0
      0 B XB b

      La solución se puede expresar:

      z = 1 CBB-1 0 = CBB-1b
      XB 0 B-1 b B-1b

      Por lo tanto, aplicando este resultado, premultiplicando a (I) se obtiene

      1 CBB-1 1 -CI -CII Z CBB-1b
      0 B-1 0 A I XI = B-1b
      XII

      Esta ecuación matricial se resuelve mediante la iteración simplex general (II):

      Básica XI XII Solución
      z CBB-1A-CI CBB-1-CII CBB-1b
      XB B-1A B-1 B-1b

      Esta tabla muestra los detalles del cálculo del método simplex, es decir, si se conoce B se puede encontrar en cada paso B-1, por lo tanto XB y z.

      Por ejemplo consideremos el método simplex con variables de holgura, en este caso, CII = 0 la solución básica inicial se identifica como:

      XB = XII, CB = CII = 0, B = I, B-1 = I

      Sustituyendo en (II) se obtiene el método simplex general con variables de holgura (III):

      Básica XI XII Solución
      z -CI 0
      XB A I b

      Si utilizamos simplex con variables artificiales (variables utilizadas como variables de holgura para las restricciones que no cumplen la forma estándar). En este caso CII = (-M,-M,…, -M) (coeficientes de penalización para la función objetivo). La solución básica inicial se puede expresar como:

      XB = XII, CB = CII, B = I, B-1 = I

      Sustituyendo en (II) se obtiene el método simplex general con variables artificiales y de holgura (IV):

      Básica XI XII Solución
      z CIIA-CI 0 CIIb
      XII A I b

      EJEMPLO 3.1:

      Max z = 3×1 + 10×2

      Sujeto a:

      X1 + 4×2 <= 8

      X1 + 2×2 <= 4

      X1, x2 >= 0

      Forma típica:

      Z -3×1 – 10×2 = 0

      X1 + 4×2 + h1 = 8

      X1 + 2×2 + h2 = 4

      X1, x2, h1, h2 >=0

      VB x1 x2 h1 h2 Solución
      Z -3 -10 0 0 0
      h1 1 4 1 0 8 8/4=2
      h2 1 2 0 1 4 4/2=2

      Por inspección entra x2 y puede salir tanto h1 como h2, escojamos arbitrariamente h1 y cambiemos x2 por h1.

      Primera iteración:

      VB x1 x2 h1 h2 Solución
      Z -1/2 0 5/2 0 20
      x2 1/4 1 1/4 0 2
      h2 1/2 0 -1/2 1 0

      La solución básica después de la primera iteración es

      X1 = 0, x2 = 2, h1 = 0, h2 = 0

      Ø Al ser h2, variable básica, h2 = 0, se dice que es solución degenerada, es posible que el método itere sin llegar a la solución optima.

      Segunda iteración:

      De la tabla anterior, entra x1 y sale h2:

      VB x1 x2 h1 h2 Solución
      Z 0 0 2 1 20
      x2 0 1 1/2 -1/2 2
      X1 1 0 -1 2 0

      La función objetivo no se ha incrementado, un problema puede ser temporalmente degenerado y luego encontrar la solución óptima.

      EJEMPLO 3.2:

      Max Z = 3×1 + 5×2

      Sujeto a:

      X1 -2×2 <= 5

      2×1        <= 12

      X1, x2 >= 0

      Forma típica:

      Z -3×1 – 5×2 = 0

      X1 -2×2 + x3 = 5

      2×1 + x4 = 12

      X1, x2, x3, x4 >= 0

      X3, x4 variables de holgura.

      VB x1 x2 x3 x4 Solución
      Z -3 -5 0 0 0
      X3 1 -2 1 0 5
      X4 2 0 0 1 12

      X2 es variable entrante, no hay ninguna variable básica saliente, ya que los elementos de la columna pivote son negativos o 0. En este caso se puede observar que el valor óptimo de z es ilimitado, las restricciones en este caso no previenen un aumento ilimitado de la función objetivo.

      En este caso el problema de optimización se encuentra mal formulado.

      EJEMPLO 3.3: Múltiples soluciones óptimas

      Max z = 2×1 + 4×2

      Sujeto a:

      x1 + 2×2  <= 12

      2×1 + 2×2 <= 12

      x1, x2 >= 0

      Forma típica:

      Z – 2×1 – 4×2 = 0

      X1 + 2×2 + x3 = 12

      2×1 + x2 + x4 = 12

      Primera iteración:

      VB x1 x2 x3 x4 Solución
      Z -2 -4 0 0 0
      X3 1 2 1 0 12
      X4 2 1 0 1 12

      Variable no básica entrante x2

      Segunda iteración:

      VB x1 x2 x3 x4 Solución
      Z 0 0 2 0 24
      X2 1/2 1 1/2 0 6
      X4 3/2 0 -1/2 1 6

      Después de la segunda iteración queda la variable no básica x1 con coeficiente 0, podemos hacer una iteración extra:

      VB x1 x2 x3 x4 Solución
      Z 0 0 2 0 24
      X2 0 1 2/3 -1/3 4
      X1 1 0 -1/3 2/3 4

      Siempre que un problema tiene más de una solución óptima, al menos una de las variables no básicas tiene un coeficiente igual a 0 en la ecuación de la función objetivo.

      EJEMPLO 3.4:

      Max 2×1 + 3×2

      Sujeto a:

      X1 + 2×2 + x3  = 4

      X1 + x2 = 3

      X1, x2, x3 >=0.

      VB x1 x2 x3 x4 Solución
      Z -2 -3 0 0 0
      X3 1 2 1 -1/3 4
      ? 1 1 0 2/3 3

      No hay variables de holgura para usarla como variable básica inicial en la ecuación (2) por lo que la restricción se reescribe de la siguiente forma:

      X1 + x2 + x4 = 3

      donde x4 es variable artificial, como x4 no se hace 0 necesariamente sobre el plano (2), debemos penalizar este valor en la función objetivo de manera que x4 se reduzca a 0 al optimizar. Para esto se pone un coeficiente -M grande, en la función objetivo (-M al maximizar, +M al minimizar con M > 0).

      Al modificar la función objetivo queda así:

      Z = 2×1 + 3×2 – Mx4

      VB x1 x2 x3 x4 Solución
      Z -M-2 -M-3 0 0 -3M
      X3 1 2 1 0 4
      X4 1 1 0 1 3

      Primera iteración:

      VB x1 x2 x3 x4 Solución
      Z (-M-1)/2 0 (M+3)/2 0 -M+6
      X2 1/2 1 1/2 0 2
      X4 1/2 0 -1/2 1 1

      Segunda iteración:

      VB x1 x2 x3 x4 Solución
      Z 0 0 1 M+1 7
      X2 0 1 1 -1 1
      X1 1 0 -1 2 2

      Solución optima:

      x1 = 2, x2 = 1, z = 7

      Ø  Para seleccionar la variable que entra en la tabla inicial tomamos el coeficiente más negativo entre -M-2 y -M-3, siendo éste último. Sin embargo si hubiéramos utilizado un número muy grande para M en una computadora, estos coeficientes se habrían considerado como iguales. Para esto se utiliza el método simplex de dos fases.

      III.1 EL METODO SIMPLEX DE DOS FASES

      Una desventaja de la técnica M es el posible error de cálculo que puede resultar al asignarse un valor muy grande a la constante M. Aquí se utilizan las variables artificiales, pero el uso de la constante M se elimina resolviendo el problema en dos etapas:

      FASE I: Agregar variables artificiales para asegurar una solución inicial. Formar una nueva función objetivo para minimizar la suma de las variables artificiales sujeta a las restricciones del problema original con las variables artificiales, si el mínimo es 0 (todas las variables artificiales son 0), el problema original tiene soluciones factibles, entonces seguir con la Fase II, si no detenerse.

      FASE II: Utilizar la solución básica óptima de la FASE I como solución inicial para el problema original

      EJEMPLO 3.1.1: Un problema de penalización en dos fases:

      Min z = 4×1 + x2

      Sujeto a:

      3×1 + x2    = 3

      4×1 + 3×2 >= 6

      x1 + 2×2 <= 4

      x1, x2 >= 0

      Forma estándar con variables artificiales:

      Min z = 4×1 + x2 + MR1 + MR2

      Sujeto a:

      3×1 + x2 + R1 = 3

      4×1 + 3×2 – x3 +R2 = 6

      x1 + 2×2 + x4 = 4

      x1, x2, x3, R1, R2, x4 >= 0

      FASE I:

      Min r = R1 + R2

      Sujeto a:

      3×1 + x2 + R1 = 3

      4×1 + 3×2 – x3 +R2 = 6

      x1 + 2×2 + x4 = 4

      x1, x2, x3, R1, R2, x4 >= 0

      Como R1 y R2 están en la solución inicial, deben sustituirse en la función objetivo:

      R = R1 + R2 = (3 – 3×1 – x2) + (6 – 4×1 – 3×2 + x3) = -7×1 – 4×2 + x3 + 9

      Tabla inicial:

      VB x1 x2 x3 R1 R2 x4 Solución
      r 7 4 -1 0 0 0 9
      R1 3 1 0 1 0 0 3
      R2 4 3 -1 0 1 0 6
      x4 1 2 0 0 0 1 4

      La tabla optima se obtiene en dos iteraciones:

      VB x1 x2 x3 R1 R2 x4 Solución
      r 0 0 0 -1 -1 0 0
      x1 1 0 1/5 3/5 -1/5 0 3/5
      x2 0 1 -3/5 -4/5 3/5 0 6/5
      x4 0 0 1 1 -1 1 1

      Como el mínimo es 0, el problema tiene solución factible y pasamos a la fase II, las variables artificiales sirvieron para encontrar una solución factible básica inicial.

      Luego en la fase II resolvemos:

      Min z = 4×1 + x2

      Sujeto a:

      x1 + 1/5 x3 = 3/5

      X2 – 3/5 x3 = 6/5

      X3 + x4 = 1

      Para esto debemos efectuar las transformaciones correspondientes a la función objetivo, es decir encontrar el coeficiente de las variables no básicas, en este caso x3, esto se logra reemplazando en la función objetivo el valor de x1 y x2 de las ecuaciones.

      Obteniéndose la tabla inicial para la fase II:

      VB x1 x2 x3 x4 Solución
      z 0 0 1/5 0 18/5
      X1 1 0 1/5 0 3/5
      X2 0 1 -3/5 0 6/5
      X4 0 0 1 1 1

      La tabla no es óptima ya que x3 debe entrar en la solución.

      III.2 DEFINICION DEL PROBLEMA DUAL

      El desarrollo de la programación lineal se ha visto reforzado por el descubrimiento de que todo problema de programación lineal tiene asociado otro problema llamado dual.

      El problema original se llama primal, ambos problemas están relacionados de tal manera que la el valor de la función objetivo en el optimo es igual para ambos problemas, y la solución de uno conduce automáticamente a la del otro.

      Las relaciones entre ambos problemas facilitan el análisis de sensibilidad de un problema.

      El dual es un problema de programación lineal se obtiene matemáticamente de un problema primal.

      La forma del problema dual es única y se define en base a la forma estándar general del problema primal:

      Optimizar (Max o Min) z = S j =1..ncjxj

      Sujeto a S j =1..naijxj = bi

      xj >= 0 con i = 1..m, j = 1..n

      donde las n variables xj incluyen los excesos y las holguras.

      El problema dual se construye simétricamente del primal de acuerdo a las siguientes reglas.

      1.     Para cada restricción primal (m restricciones) existe una variable dual yi (m variables), la función objetivo se construye con los valores libres bi como coeficientes de las variables yi.

      2.     Para cada variable primal xj (n variables) existe una restricción dual (n restricciones), la restricción se construye con los m coeficientes de las restricciones primales de esa variable. Los valores libres son los n coeficientes cj.

      3.     Si la optimización primal es una Maximización, el problema dual es una Minimización y las restricciones son >=. (y a la inversa Minimización primal, Maximización dual, restricciones < ).

      Ø Si consideramos los excesos y holguras las variables duales (yi)no tienen restricciones de signo, en caso contrario en ambos problemas se considera variables >0. Por lo que las variables duales correspondientes a restricciones del tipo = deben ser sin restricciones de signo, recíprocamente cuando una variable en el primal no tiene restricción de signo, la restricción correspondiente en el dual debe ser del tipo =.

      EJEMPLO 3.2.1:

      Max z = 3x1 + 5x2

      Sujeto a:

      x1 + 10×2 < 80

      2x1 + 3x2 < 45

      4x1 – 2x2 < 25

      3x2 <60

      x1, x2 > 0

      Aplicando las reglas :

      1.     Para cada restricción primal (4 restricciones) existe una variable dual yi (4 variables) y1 y2 y3 y4, la función objetivo se construye con los valores libres bi (80,45,25,60) como coeficientes de las variables yi.

      2.     Para cada variable primal xj (2 variables sin considerar las variables de holgura) existe una restricción dual (2 restricciones), la restricción se construye con los 4 coeficientes de las restricciones primales de esa variable. Los valores libres son los 2 coeficientes cj (3, 5).

      3.     la optimización primal es una Maximización, el problema dual es una Minimización y las restricciones son > .

      Ø  No hemos considerado las variables de excesos ni holguras las variables duales por lo que en ambos problemas se considera variables ³ 0, no existen restricciones de =.

      Problema dual:

      1. Min Y = 80y1 + 45y2 + 25y3 + 60y4

      Sujeto a:

      Y1 + 2y2 + 4y3 > 3

      10y1 + 3y2 – 2y3 + 3y4 > 5

      y1, y2, y3, y4 > 0

      2.  Max Z = 3x1 + 7x2

      Sujeto a:

      2x1 + 5x2 = 15

      x1 + 8x2 < 30

      x1, x2 > 0

      1.     Para cada restricción primal (2 restricciones) existe una variable dual yi (2 variables) y1 y2, la función objetivo se construye con los valores libres bi (15, 30) como coeficientes de las variables yi.

      2.     Para cada variable primal xj (2 variables sin considerar las variables de holgura) existe una restricción dual (2 restricciones), la restricción se construye con los 2 coeficientes de las restricciones primales de esa variable. Los valores libres son los 2 coeficientes cj (3, 7).

      3. Aplicando las reglas y la nota:

      4.     Nota: Para la segunda restriccion no hemos considerado las variables de excesos ni holguras las variables duales por lo que en el dual y2 ³ 0, la primera restricción es de igualdad por lo que la primera variable no tiene restricción de signo.

      Problema dual:

      Min Y= 15y1 + 30y2

      Sujeto a:

      2y1 + y2 ³ 3

      5y1 + 8y2 ³ 7

      y1 sin restricción de signo (irrestricta)

      y2 ³ 0.

      III.3 ANALISIS DE SENSIBILIDAD

      Una vez obtenida la solución de un problema de programación lineal, es  deseable investigar cómo cambia la solución del problema al cambiar los parámetros del modelo.

      Por ejemplo si una restricción de un problema es 4×1 + 6×2 < 80 donde 80 representa la cantidad de recurso disponible. Es natural preguntarse ¿ que pasa con la solución del problema si la cantidad de recurso (por ejemplo Horas) disminuye a 60?. Otras veces podemos preguntarnos que pasa si cambiamos algunos coeficientes de la función objetivo? O bien si agregamos una restricción o una variable. El estudio de la variación de un problema de programación lineal debido a cambios de los parámetros del mismo, se llama análisis de sensibilidad.

      Una forma de responder estas preguntas sería resolver cada vez un nuevo problema. Sin embargo esto es computacionalmente ineficiente.

      Para esto es preferible hacer uso de las propiedades del método Simplex y de los problemas primal y dual.

      Recordemos que una vez que en un problema lineal se conoce B, CB y XB, la tabla simplex se puede calcular utilizando B-1 y los datos originales del problema.

      El efecto de los cambios en los parámetros del problema del análisis de sensibilidad (posoptimo) se puede dividir en tres categorias:

      1.     Cambios en los coeficientes C de la función objetivo, solo afecta la optimalidad.

      2.     Cambios en el segundo miembro b solo pueden afectar la factibilidad.

      3.     Cambios simultáneos en C y b pueden afectar la optimalidad y la factibilidad.

      EJEMPLO 3.3.1:

      1. Cambios en los coeficientes objetivo:

      Max z = 3×1 + 2×2 (ganancia)

      Sujeto a

      x1 + 2×2 + h1 = 6 (Materia Prima A)

      2×1 + x2 + h2 = 8 (Materia prima B)

      -x1 + x2 + h3 = 1 (demanda)

      x2 + h4 = 2 (demanda)

      x1, x2, x3, x4, x5, x6 > 0

      Tabla primal Óptima:

      VB x1 x2 x3 x4 x5 x6 Solución
      z 0 0 1/3 4/3 0 0 12 2/3
      x2 0 1 2/3 -1/3 0 0 1 1/3
      x1 1 0 -1/3 2/3 0 0 3 1/3
      x5 0 0 -1 1 1 0 3
      x6 0 0 -2/3 1/3 0 1 2/3

      Supongamos que cambiamos la función objetivo de z = 3×1 + 2×2 por z = 5×1 + 4×2, dado el óptimo

      XB = (x2, x1, x5, x6)

      CB = (4, 5)

      Y = (y1, y2, y3, y4)

      = CBB-1 = (1, 2, 0, 0)

      4 5 0 0 1/3 4/3 0 0
      2/3 -1/3 0 0
      -1/3 2/3 0 0
      -1 1 1 0
      -2/3 1/3 0 1

      Los nuevos coeficientes de la función objetivo son

      Y(AI) – C que no es otra cosa que la diferencia entre ambos lados de las restricciones duales.

      IV. MODELO DE TRANSPORTE

      Existen dos aplicaciones importantes de la programación lineal que son el modelo de transportes y el de asignación de recursos. Aún cuando la solución de estos modelos puede obtenerse aplicando el método simplex, se estudian algoritmos especiales para la solución de estos problemas.

      Debido a su estructura especial, hace posible hace posible métodos de solución más eficientes en términos del cálculo.

      EJEMPLO 4.1:

      Suponga que una compañía tiene m plantas de producción (i), de capacidad ai (i = 1…m) y n almacenes de distribución (j), con demanda bj (j = 1…n). El costo de transporte entre la planta i y el almacén es conocido como cij.

      El problema es determinar la cantidad (xij) que debe suministrar la planta i al almacén j, de tal manera que el costo de transporte total sea mínimo. Las consideraciones de costos de producción e inventario se pueden incorporar al modelo básico.

      El modelo típico tiene cuatro componentes:

      1.     Un conjunto de m fuentes

      2.     Un conjunto de n destinos

      3.     Costos de transporte entre las fuentes y los destinos

      4.     Cantidades de producto para enviar entre las fuentes y los destinos.

      El modelo general que representa el modelo de transporte es:

      Min z = S iS j cijxij

      Sujeto a:

      S j xij = ai (fuentes i = 1..m)

      S i xij = bj (destinos j = 1..n)

      xij >= 0

      IV.1 MODELOS BALANCEADOS Y NO BALANCEADOS

      IV.1 MODELOS BALANCEADOS Y NO BALANCEADOS:

      Un modelo de transporte se llama balanceado cuando:

      S i ai = S j b

      Esto significa que la suma de los suministros de todas las plantas debe ser igual a la suma de las demandas de todos los almacenes.

      Sin embargo en problemas de la vida real, esta igualdad rara vez se satisface.

      Lo que se hace entonces es balancear el problema.

      Si los requerimientos exceden a los suministros, se agrega una planta ficticia, que suministrará la diferencia.

      El costo de transporte desde la planta ficticia hacia cualquier almacén es cero.

      Recíprocamente, si los suministros exceden a los requerimientos, se agrega un almacén ficticio que absorberá el exceso.

      El costo unitario de transporte desde las plantas al almacén ficticio es cero.

      Ejemplo 4.1.1

      Considere La Empresa Gerconsa productora de automóviles de tres plantas y dos centros de distribución. Las capacidades de las tres plantas durante un trimestre son de 1000, 1500 y 1200 automóviles, la demanda trimestral en los dos centros de demanda son de 2300 y 1400 vehículos. El costo de transporte en dólares es:

      Planta/Almacén 1 2
      1 80 215
      2 100 108
      3 102 68

      Sea xij el número de automóviles transportados desde la fuente i al destino j. Como la oferta total (1000+1500+1200 = 3700) es igual a la demanda total (2300+1400 = 3700) el modelo de transporte está equilibrado.

      Por lo tanto el siguiente modelo representa la situación descrita:

      Min z = 80x11 + 215x12 + 100x21 + 108x22 + 102x31 + 68x32

      Sujeto a:

      x11 + x12 = 1000

      x21 + x22 = 1500

      x31 + x32 = 1200

      x11 + x21 + x31 = 2300

      x12 + x22 + x32 = 1400

      xij >= 0 para toda i, j.

      Un método más resumido para representar el modelo de transporte consiste en utilizar los que se llama tabla de transporte, esta es una matriz donde las filas representan las fuentes y las columnas el destino. En cada celda se especifica la cantidad xij y el costo cij.:

      Fuente/destino 1 2 Oferta
      1 x11 80 x12 215 1000
      2 x21 100 x22 108 1500
      3 x31 102 x32 68 1200
      Demanda 2300 1400 3700

      El método de transporte es un problema  clásico dentro de la programación matemática; se analiza la manera de obtener el costo mínimo de transportar una serie de productos desde n fabricas, hasta m almacenes; cada envío tiene un costo particular que estará en función de la distancia, el tipo de carretera, la cantidad y otras variables.

      Como siempre, se entiende mejor con un ejemplo:

      • La más famosa empresa dentro de las aulas universitarias, la Empresa Gerconsa, tiene tres fabricas donde manufactura su famosísimo producto P, con capacidades de producción de 25 (unidades por micronanosegundo, por segundo, hora, año… no importa, es lo mismo para todos), 25,10 y debe surtir a 4 almacenes con demandas de 20,15,20,5 (unidades por micronanosegundo, segundos.. o lo que sea, siempre y cuando se maneje la misma unidad temporal en todo el problema). Los costos de enviar desde cualquier fábrica a cualquier almacén se pueden ver en la tabla abajo.
      Capacidad de Producción (u/t)
      Fabrica 1 Fabrica 2 Fabrica 3
      25 25 10
      Demanda de los Almacenes (u/t)
      Almacén 1 Almacén 2 Almacén 3 Almacén 4
      20 15 20 5
      Costo de Transporte desde la Fabrica i al almacén j
      $/unid Almacén 1 Almacén 2 Almacén 3 Almacén 

      4

      Fabrica 1 2 2 0 4
      Fabrica 2 5 9 8 3
      Fabrica 3 6 4 3 2

      Ahora la pregunta es cuánto se debe enviar desde cada fábrica a cada almacén con el fin de obtener el mínimo costo.

      Min Z = 2X11 + 2X12 +0X13 +4X14 +5X21 +9X22 +8X23 +3X24           +6X31+4X32 + 3X33 +2X24
      Sujeto a:
      1. Satisfacer la demanda de los almacenes:
      X11+X21+X31 >=  20
      X12+X22+X32 >=  15
      X13+X23+X33 >=  20
      X14+X24+X34 >=  5
      2. No sobrepasar la capacidad disponible de las fabricas
      X11+X12+X13+X14 <=  25
      X21+X22+X23+X24 <=  25
      X31+X32+X33+X34 <=  10
      3. Por supuesto la condición de no negatividad y todas las   variables enteras.

      Bueno, aquí la formulación es un poco diferente a como lo hicimos en los dos ejemplos anteriores. La idea aquí es la de tener dos matrices y dos vectores; una matriz se corresponderá con las variables de decisión, y la otra matriz con los costos. La primera la dejamos simplemente señalada, con algún formato para distinguirla, y la otra la digitamos. La celda objetivo será la suma del producto de cada una de las posiciones de cada matriz con su correspondiente en la otra; esto lo podemos hacer rápidamente con la función “sumaproducto” del Excel. Las restricciones estarán en las columnas de “Consumo” y de “entregado”. Primero preparemos el formato del problema, así:

      Las variables de decisión están en el rango [B4-E6]. La celda objetivo sería algo así como esto: = B4*B10+ C4*C10+… pero eso sería muy largo. La manera corta es:= SUMAPRODUCTO (B4:E6,B10:E12).La cantidad entregada a cada almacén se ve en la fila 8. Por ejemplo para la celda B8, su fórmula es:=B4+B5+B6. La restricción de la capacidad de las fabricas la escribiremos en función del consumo en la columna G; por ejemplo para la celda G4:=B4+C4+D4+E4. Las restricciones las escribiremos en el cuadro de diálogo como lo entregado debe ser mayor o igual a lo requerido, y lo consumido debe ser menor igual que lo disponible, tal como se puede ver en la captura siguiente:

      Las variables de decisión deben ser enteras. Luego de introducir los datos en éste cuadro de diálogo y de hacer click en resolver, se hallará la siguiente  solución:

      V. EL PROBLEMA DE LA ASIGNACIÓN

      El Problema de la Asignación es un problema clásico de la Investigación de Operaciones y es un caso particular del Problema del Transporte.

      Este problema se trata de asignar una serie de Recursos a una serie de tareas.  Tiene una limitante y es que a cada tarea se le puede asignar sólo un recurso, pueden sobrar recursos o podrían sobrar tareas pero no se le puede asignar dos recursos a una misma tarea, o tres… por ejemplo si se tienen tres operarios con diferentes tiempos de operación en cuatro máquinas el modelo nos diría como asignar los tres operarios a tres máquinas (nos sobraría una) de manera que se minimice el tiempo total, pero no nos diría como asignar dos operarios a dos máquinas y el otro operario a las otras dos máquinas

      Ejemplos de Asignaciones: Operarios a Tareas, Máquinas a Operarios, Nadadores a Estilos,etc.

      El Problema de la Asignación se basa en una información comparativa para tomar la decisión de que asignar a que, por ejemplo una matriz de costos, una matriz de tiempos, de ingresos, etc. Cuando la matriz no está balanceada, es decir, cuando no es cuadrada, cuando sobran filas o columnas, se debe balancear para que tenga solución mediante la inclusión de filas o columnas ficticias, con valores de cero en dicha matriz.

      V.1 FORMULACION DE PROGRAMACION LINEAL

      EJEMPLO 5.1.1: 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 esta 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?

      En matemáticas existen dos números cuyas propiedades hacen que puedan representar estas respuestas son el 1 y el 0, debido a que todo número multiplicado por 1 da el mismo número entonces el 1 se puede reemplazar por la respuesta Sí y como todo número multiplicado por cero da cero entonces se puede reemplazar por la respuesta No.

      Así por ejemplo:

      10X11 + 7X12 + 9X13 + 0X14

      Representa el tiempo sumado  que emplearía el operario1 en operar las máquinas, pero solo una variable de las tres anteriores puede tomar el valor de Sí, o sea de 1 las demás tendrán que tomar el valor de 0, y eso es debido a que el operario 1 sólo puede ser asignado a una máquina, lo que significaría que el tiempo que utilice el operario 1 puede ser ya sea de “10” de “7” o de “9”. Con base en esto podemos formular la función objetivo:

      Min Z = 10X11 + 7X12  +  9X13
      7X21 + 5X22  +  8X23
      9X31 + 8X32 + 10X33
      8X41 + 9X42 +    7X43

      Restricciones:

      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

      Xij = 1 o 0 para toda i,j.

      Al resolver utilizando Software, por ejemplo el Solver del Excel, la respuesta que se obtiene es la siguiente:

      Máquina 1 Máquina 2 Máquina 3 Máquina Fic.
      Operario 1 0 0 0 1
      Operario 2 0 1 0 0
      Operario 3 1 0 0 0
      Operario 4 0 0 1 0

      Esto significa que el Operario 1 queda asignado a la Máquina Ficticia (es decir, es el que sobra), el operario 2 se asigna a la máquina 2, el operario 3 se asigna a la máquina 1 y el operario 4 se asigna a la máquina 3.

      V.2 ALGORITMO HUNGARO

      El Algoritmo Húngaro sirve para reemplazar los métodos tradicionales de la Programación Binaria, que implican muchos cálculos, aprovechando la forma especial que tienen los problemas de Asignación.

      Los siguientes pasos que se presentan a continuación son para minimizar, pero con algunas modificaciones se puede emplear también para maximizar.

      Ø Si la matriz no está balanceada, balancearla incluyendo las filas o columnas ficticias necesarias.

      Ø De cada elemento de la matriz restar el mínimo valor de cada fila

      Ø De cada elemento de la matriz restar el mínimo valor de cada columna

      Ø Realizar la Asignación de la siguiente manera:

      Ø Cada cero que se encuentre en la matriz significa que se puede asignar esa fila a esa columna, pero una vez hecha esta asignación, ya no se tendrá en cuenta todos los demás ceros de esa misma fila y esa misma columna, debido a que sólo se  puede asignar una fila a una columna.

      Ø Buscar de arriba a abajo la fila que tenga menos ceros, pero que mínimo tenga uno. (Pues si no tiene ninguno significa que esa fila no se puede asignar a ninguna columna) y asignar esa fila a la columna donde esta el cero (puede ser el primer cero que encuentre de izquierda a derecha). Tachar esa fila y esa columna para indicar que ya fueron asignados, para que los demás ceros de esa fila y esa columna no se tengan en cuenta. Repetir este paso hasta que haga todas las asignaciones que más pueda. Si todas las filas quedaron asignadas a todas las columnas el problema ha finalizado y esa es la solución óptima, sino será necesario utilizar el método de Flood (también se llama condición de Köning) que se explica a continuación.

      V.2.1 MÉTODO DE FLOOD:

      Ø Señalar todas las filas que no tienen una asignación. (Cuando digo señalar puede ser una pequeña X a la izquierda de la fila o arriba de la columna)

      Ø Señalar todas las columnas que tengan un cero en la columna señalada.

      Ø Señalar todas las filas que tienen una asignación en las columnas indicadas.

      Ø Repetir estos pasos hasta que no pueda señalarse más columnas o filas.

      Ø Dibujar una línea por cada fila NO señalada y por cada columna SI señalada.

      Ø Encontrar el mínimo valor de los elementos no cubiertos y restarlo a todos los elementos no cubiertos, y sumar este valor a cada elemento que se encuentre en la intersección de una línea horizontal  con una línea  vertical.

      Ø Realizar la Asignación… si no es óptima hacer flood, iterar hasta que se pueda hacer la asignación.

      V.3 PROGRAMACION BINARIA EN EL PROBLEMA DE ASIGNACION

      Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o no.  Así es que podemos representar éstas posibilidades con los valores 0 (no) y 1 (si), y aprovechar las matemáticas para que nos den una mano ante decisiones difíciles; a esto es lo que solemos llamar -por obvias razones- Programación Binaria.

      Una de las muchísimas aplicaciones de la Programación Binaria, es el problema de la Asignación.  ¿Se debe asignar el recurso i a la tarea j ? ¿Si o no?

      EJEMPLO 5.3.1:

      Se tienen tres personas (recurso) para asignarlos a tres labores diferentes. Cada uno de ellos puede efectuar cualquiera de las tareas existentes, pero con diferente nivel de especialidad. Sus respectivos jefes los han calificado de 1 a 10, para cada tarea en particular. Por supuesto el objetivo es el de asignar a las personas de manera tal que la calificación en conjunto sea la máxima.  Ver tabla de calificaciones abajo.

      También funciona para minimizar. Por ejemplo, en vez de calificación podrían ser tiempos de manufactura de cualquier tipo de productos, y el objetivo sería el de minimizar el tiempo total de manufactura.

      Calificación de Operario por Tarea
      Tarea 1 Tarea 2 Tarea 3
      Operario 1 8 6 4
      Operario 2 9 7 3
      Operario 3 6 5 7

      Xij = 1 si asignamos el operario i a la tarea j, de lo contrario 0

      En éste orden de ideas, nuestro deseo es maximizar la calificación total al asignar los operarios a las diferentes tareas.

      Max Z =  8X11 + 6 X12 + 4 X13 + 9X21 +7 X22 +3X33 +6X31 +5X32  +7X33
      SUJETO A:
      1. Cada operario sólo puede tener una tarea asignada
      X11 +X12 +X13 = 1  (Es decir, sólo se puede responder Si una sóla vez.)
      X21 +X22 +X23 = 1
      X31 +X32 +X33 = 1
      2. Cada tarea puede tener un sólo operario asignado
      X11 + X21 + X31 = 1
      X12 + X22 + X32 = 1
      X13 + X23 + X33 = 1

      3. La obvia: Xij = 0,1 para toda i y toda j.

      Ahora en Excel…

      Este puede ser el formato:

      Las variables de decisión, están localizadas en el rango de celdas B4:D6, como ya habíamos dicho son binarias, van a tomar el valor de 1 si se asigna ese operario a esa tarea, cero de lo contrario. La calificación que se logre está en la celda B2, y es el resultado de sumar el producto de dichas variables con su respectiva calificación en la matriz de abajo. Ya se había dicho que esto se logra fácilmente así: =SUMAPRODUCTO (B4:D6, B9:D11). Como un operario sólo se puede asignar a una tarea, colocamos una columna de Suma (E), ésta es por ejemplo para la celda E4: =B4+ C4 + D4. Cuando agreguemos las restricciones, ésta columna debe ser igual a uno, pues sólo se puede responder que si una vez, ni más, ni menos. De igual manera agregamos una fila (7), para asegurarnos que a una tarea sólo se asigne un operario, por ejemplo la celda B7: =B4+ B5+ B6 Deberá ser igual a 1.  Ahora en el cuadro de diálogo de los parámetros de Solver, lo colocamos así:

      Luego de hacer click en resolver…

      La calificación máxima lograda es de 22.  Y se asignó el operario 1 a la tarea 2, el operario 2 a la tarea 1 y el operario 3 a la tarea 3.  Para los programas Lineales enteros es muy importante que Solver, esté debidamente configurado para un número suficiente de iteraciones, de tiempo,  de precisión y de convergencia, para esto ver los detalles de Solver

      VI. BIBLIOGRAFIA

      1.     Eppen G.D , Gould F.J, Schmidt C.P. Investigaciòn de operaciones en la Ciencia

      Administrativa

      2.     Hiller, Frederics.Introduccion a la Investigación de Operaciones, Quinta

      Edicion, 1991_MC_Graw_Hill

      3.     Kaufman, Arnold.Metodos y Modelos de Investigacion de operaciones,Quinta

      Edicion, 1984, CECSA

      4.     Levin, Richard I. Kirkpatrick, Charles A. Enfoques Cuantitativos a la

      Administración. Primera Edicion, 1983

      5.     Lumberger David, Programación Lineal y no Lineal. Wesley ED Addison,

      Iberoamericana, 1989, EUA.

      6.     Nagui,Mohammad. Investigación de Operaciones. Interpretación de Modelos y

      Casos. Editorial Limusa, 1996, México

      7.     Prawda , Juan. Métodos y Modelos de Investigación de Operaciones, volumen 1:

      Modelos Deterministicos, Octava Reimpresión, 1989, Limusa Mexico.

      8.     Taha, Hamdy A., Investigación de Operaciones. Sexta edición 1999, Alfa y Omega S.A. Mexico

      9.  Web Site:

      Ø http://www.elprisma.com

      Ø http://selva.dit.upm.es/  cd/apuntes/tema3/tema3.html

      Ø http://ekeko.rcp.net.pe/rcp/listas/ioper/iosa.html

      Follow

      Get every new post delivered to your Inbox.