Gestión de Operaciones II IN4704 - U-Cursos · IN4704-Gestión de Operaciones II Entonces comparamos el óptimo de la solucion para cada subproblema y elegimos el mejor. Cada subproblema

Gestión deOperaciones II

IN4704

Profesor: Fernando Ordoñez P.Auxiliar: Felipe Lagos G.Semestre: Otoño 2012

IN4704 - Gestión de Operaciones II

1. Métodos para programación entera

Cortes de gomory

Sea x∗ una solución óptima factible y B su matriz asociada. Se particiona x en un vectorpara las variables básicas, xB, y uno para las no básicas, xN.

Ax = b

B−1Ax = B−1b

xB + B−1ANxN = B−1b

Sea aij = (B−1Aj)i y ai0 = (B−1b)i. Consideremos una ecuación donde ai0 es fracción:

xi + ∑j∈N

aijxj = ai0

Como xj debe ser entero se debe cumplir que:

xi + ∑j∈Nbaijcxj ≤ bai0c

puesto que en el óptimo x∗i = ai0, x∗j = 0 para todo j ∈ J no básico y bai0c < ai0.Agregando estas restricciones sistemáticamente se logra resolver el problema de pro-

gramación entera.

Branch and bound

Branch and bound usa un enfoque "dividir y conquistar"para explorar un conjuntofactible de soluciones enteras. Para no revisar todo el junto, utiliza cotas del óptimo paradescartar conjuntos.

Consideremos un conjunto F factible para el siguiente problema

mın c′xs.t. x ∈ F

Si dividimos F en un conjunto finito de subconjuntos, Fi con i = 1, ..., k y se resuelvenseparadamente cada uno

mın c′xs.t. x ∈ Fi i = 1, ..., k

2


Entonces comparamos el óptimo de la solucion para cada subproblema y elegimos elmejor. Cada subproblema se supone que es tan complejo como el inicial, teniendo que serresueltos con el mismo método. Cada subproblema puede generar más subproblemas.

Además se asume que se tiene un algoritmo relativamente eficiente, el cual para cadaFi calcula la cota inferior, b(Fi)

b(Fi) ≤ mınx∈Fi

c′x

La idea básica es que mientras el costo óptimo puede que sea difícil de calcular exac-tamente, la cota inferior debería ser fácil de obtener.

El método más conocido para encontrar una cota inferior del problema, es la relajaciónlineal.

Además, para descartar conjuntos es necesario comparar los óptimo con un óptimofactible, U. En efecto, si para algún i se cumple que b(Fi) ≥ U, este subproblema no debeseguir siendo considerado, pues la mejor solución que puede entregar este subconjuntonunca va a ser mejor que la que ya tenemos.

Inicialmente U es algún costo factible conocido para el problema o simplemente ∞. Elalgoritmo funciona de la siguiente forma:

1. Seleccionar un subconjunto activo de Fi.

2. Si el subproblema es infactible, se debe borrar; en caso contrario, calcular b(Fi) cor-respondiente.

3. Si b(Fi) ≥ U, borrar el subproblema.

4. Si b(Fi) < U, se puede tanto obtener una solución óptima del subproblema, comodividir este problema en sus subproblemas, los cuales son añadidos a la lista desubproblemas activos.

Existen muchas variantes de este algoritmo. Algunas consideraciones son:

(a) Existen muchas formas de elegir el subproblema activo. Se puede usar "Búsquedapor nivel.o "Búsqueda por profundidad".

(b) Se puede obtener la cota inferior de varias maneras. La más popular es la relaciónlineal.

(c) Para dividir un subproblema se pueden usar varios métodos

Si para encontrar la cota inferior del problema usamos la relajación lineal, sabemosque al momento de encontrar una solución con valores enteros, se debe actualizar U ypodemos borrar el subproblema. Si encontramos una solución no entera, x∗, elegimos unacomponente no entera x∗i y creamos dos subproblemas, con las siguientes restricciones:

3


xi ≥ bx∗i c, o xi ≥ dx∗i e

A pesar de que Branch & Bound puede tomar un tiempo exponencial en encontrar unasolución, produce soluciones aceptables en un tiempo pequeño.

Pregunta 1

Se debe decidir que objetos llevar a un paseo a la playa, los cuales se deben transportaren un bolso de capacidad total de 150 unidades de volumen. Cada uno de estos objetosreporta una utilidad por llevarlos, pero también tienen un costo en volumen. Las cosasque puede llevar son: un Quitasol, 6 Parlantes, 3 Toallas y un Notebook.

Índice Objeto Cantidad Utilidad Espacio1 Quitasol 1 40 902 Parlantes 6 5 203 Toallas 3 15 104 Notebook 1 25 40

Determine la máxima utilidad posible, sin sobrepasar la capacidad del bolso.

1. Escriba la Rejación Lineal del problema.

2. ¿Existe alguna forma simple de obtener la solución óptima del problema relajado,sin realizar ningún algoritmo?, ¿Cómo es? Resuelva mediante este método el prob-lema.

3. Resuelva el problema utilizando el algoritmo Branch & Bound, resolviendo cada no-do mediante el método desarrollado en la parte anterior.

Solución

1. La Relajación Lineal del problema es:

max z = 40x1 + 5x2 + 15x3 + 25x4

s.a. 90x1 + 20x2 + 10x3 + 40x4 ≤ 150x2 ≤ 6x3 ≤ 3x1, x2 ∈ [0, 1]

x2, x3 ∈ R+0

4


2. La forma más sencilla de resolver el problema es rankear los objetos según la razónBeneficio-Capacidad, que en este caso es la razón Utilidad-Espacio.

Índice Objeto Cantidad Utilidad Espacio Razón1 Quitasol 1 40 90 0.442 Parlantes 6 5 20 0.253 Toallas 3 15 10 1.54 Notebook 1 25 40 0.63

Luego se llevan en primer lugar todos las Toallas que se puedan, es decir, 3, uti-lizando 30 unidades de volumen. En segundo lugar se agrega el Notebook, con loque solo quedan 80 unidades de volumen. Luego se agrega el Quitasol pero comono cabe entero, se agregan 8/9 de este objeto, para satisfacer la restricción de capaci-dad. Con esto queda la siguiente solución:

x1 = 8/9, x2 = 0, x3 = 3 x4 = 1

3. Se inicializa el incumbente (mejor solución entera encontrada hasta ahora) en z =−∞.

Observaciones:

Las variables xi son binarias, por lo tanto alramificar hay solo dos opciones. Engeneral para variables enteras se ramifica utilizando desigualdades.

Llamamos solución entera a aquella en la cual TODAS las variables toman val-ores enteros.

Los 3 criterios para dejar de ramificar son: Solución entera, Solución peor queel incumbente y Solución Infactible.

En este caso de haber resuelto P6 antes que P3 no habría sido necesario re-solver P4 ni P5 ya que P3 hubiese caído en el criterio ”Solución peor que elincumbente”.

Pregunta 2

Considere el siguiente problema de programación entera:

5


P0 z = 105.5x1 = 8/9 x3 = 3

x2 = 0 x4 = 1

P1 z = 90x1 = 0 x3 = 3x2 = 4 x4 = 1

P2 z = 103.8x1 = 1 x3 = 3x2 = 0 x4 = 3/4

P6 z = 95x1 = 1 x3 = 2x2 = 0 x4 = 1

P3 z = 92.5x1 = 1 x3 = 3

x2 = 3/2 x4 = 0

P4 z = 90x1 = 1 x3 = 3x2 = 1 x4 = 0

P5 z = 80x1 = 1 x3 = 2x2 = 2 x4 = 0

Sol. Entera

Sol. Entera

Sol. Entera

Sol. EnteraPeor que incumbente

x1 = 0 x1 = 1

x4 = 0 x4 = 1

x2 ≤ 1 x2 ≥ 2

Figura 1: Branch and Bound para la Pregunta 1

mın x1 − 2x2

s.a. − 4x1 + 6x2 ≤ 9x1 + x2 ≤ 4x1, x2 ≥ 0x1, x2 enteros

1. Resuelvalo usando Cortes de Gomory.

2. Resuelvalo usando Branch & Bound.

Solución

6


1. Se comienza transformando el problema a su forma estándar:

mın x1 −2x2s.a. −4x1 +6x2 +x3 = 9

x1 +x2 +x4 = 4x1, ..., x4 ≥ 0x1, ..., x4 enteros

Se resuelve relajando linealmente el problema con lo que se obtiene un óptimo x1 =(15/10, 25/10). La ecuación que se obtiene de juntar las primeras dos igualdades es:

x2 +1

10x3 +

410

x4 =2510

Tomando parte entera a esta ecuación y usando las condiciones de corte, se obtienela siguiente desigualdad:

x2 ≤ 2

En su forma estándar, se debe agregar la variable x5 ≥ 0 y la restricción x2 + x5 = 2.El nuevo óptimo, con esta restricción es x2 = (3/4, 2).

Tomemos la desigualdad recién agregada y−4x1 + 6x2 + x3 = 9. Sacando x2 se llegaa:

x1 −14

x3 +64

x5 =34

Nuevamente tomando parte entera y cosiderando los cortes de Gomory:

x1 − x3 + x5 ≤ 0

Lo cual si dejamos en función de x1 y x2 es simplmente:

−3x1 + 5x2 ≤ 7

Con esta nueva restricción se llega finalmente al óptimo buscado: x3 = (1, 2).

7


2. Iniciamos el incumente en z = ∞. Resolviendo la relajación lineal se obtiene x1 =(1.5, 2.5). La función objetivo correspondiente es z = −3.5.

Con esto, se generan dos subproblemas, uno con la restricción z2 ≥ 3 (subproblemaF1) y x2 ≤ 2 (subproblema F2). F1 es infactible por lo que se saca de la lista. Lasolución óptima de F2 es x2 = (3/4, 2), lo que genera un z = −3.25. Nuevamente segeneran dos restricciones y dos subproblemas, x1 ≥ 1 (F3) y x1 ≤ 0 (F4), por lo que lalista de problemas a resolver consiste en {F3, F4}. El problema F3 tiene como soluciónx3 = (1, 2), el cual es entero y por lo tanto actualizamos el incumbente. z = −3.Sacamos F3 de la lista y vemos F4. EL óptimo de este problema es x4 = (0, 3/2) y suz = −3. Dado que z ≥ U, no exploramos F4 y ya no quedan problemas por resolver.La solución final es x3 = (1, 2)

x1

x2

x2 ≤ 2

−3x1 + 5x2 ≤ 7

x1

x2

x3

(a)

x1

x2

x2 ≤ 2

x2 ≥ 3

x1 ≥ 1

x1 ≤ 0

x1

x2

x3

(b)

Figura 2: En (a) restricciones generadas por Cortes de Gomory, en (b) por Branch & Bound

8


2. Revenue Management

El problema que se estudia es revenue management para un único recurso basadoen la cantidad, y donde se debe administrar diferentes clases de demandas. Existen dosejemplos clásicos en que se aplica: un vuelo sin escalas y reserva de habitaciones para unafecha determinada.

Vamos a asumir que existe una capacidad para n distintas clases, las cuales son per-fectamente segmentadas. Además, asumiremos que las unidades de capacidad son ho-mogéneas y que cada cliente utiliza un cupo. El problema principal es cómo reservaróptimamente este recurso para la demanda.

Existen distintos mecanismos para controlar la disponibilidad. Algunos son:

Booking Limits: Es una forma de controlar la disponibilidad a través de la capaci-dad para una clase en algún momento del tiempo. Este control puede ser particionadoo anidado. El particionado divide la capacidad disponible en bloques separados y so-lo pueden ser vendidos a la clase asignada. Esto significa que no importa si quedadisponibilidad en otras clases cuando la una de ellas ya esta copada, igual no sevenderá un cupo más.

Con el control anidado, la capacidad disponible a diferentes clases sí puede super-ponerse, pero de una forma jerárquica según las clases. Supongamos que bj es ellímite anidado. Entonces bj es el número máximo de capacidad que está disponiblepara las clases j, j + 1, ..., n.

Este método evita el problema de capacidad para las clases superiores cuando quedanunidades en clases "menores".

Niveles de protección: Es muy parecido a booking limits solo que este caso se defineyj como la cantidad reservada para las clases j, j− 1, ..., 1 combinada. La relación conbj,

bj = C− yj−1 j = 2, ..., n

donde C es la capacidad. Por conveniencia definimos b1 = C y yn = C.

Standard versus theft nesting: El proceso estándar para usar booking limits o nive-les de protección es el siguiente. Se comienza con C unidades de capacidad y secomienzan a recibir reservas. Se acepta la reserva de la clase j si (1) existe capacidaddisponible, (2) el número total de de pedidos aceptados por la clase j hasta el mo-mento es menor que el límite bj o la capacidad restante es mayor o igual a yj−1 paralas clases mayores que j.

Otra alternativa es theft nesting. Este proceso no solo reduce disponibilidad para laclase j, sino también roba"disponibilidad a todas las demás clases menores, en estecaso j + 1, j + 2, ..., n.

9


Bid prices: Lo que distingue bid-prices de booking limits y niveles de protecciónes que bid-price está basado en los ingresos esperados, en vez de los controles porclases. Este sistema de control establece un precio umbral (el que puede dependerde la capacidad remanente, tiempo, etc), con el cual se acepta una venta siempre ycuando supere este umbral. Este sistema puede ser más simple que los otros dos,puesto que lo único que requeriere en un momento determinado es un precio um-bral, en vez de un conjunto de capacidades para las clases.

Generalmente se establece una función π(x), donde x es la capacidad restante.Además, se puede considerar el tiempo como criterio para definir un precio.

Para exponer algunos modelos se asumen ciertos supuestos:

1. La demanda para diferentes clases llega en intervalos que no se superponen en eltiempo.

2. La demanda son variables aleatorias independientes.

3. La demanda no depende de la capacidad restante.

4. Se asume que la demanda llega de forma agregada en una sola etapa, y la decisiónes cuántos clientes aceptar.

5. No existen grupos de clientes que aceptar.

6. Se asume un modelo neutro al riesgo.

Modelo para dos clases de LittlewoodSe asume un solo recurso y dos clases con precios p1 > p2. La capacidad es C y no

hay cancelaciones ni sobreventa. La demanda de la clase j es Dj, la distribución se denotapor Fj(·). La demanda por la clase dos llega primero. El problema es cuánto vender a estaclase antes de que llegue la clase 1.

Este problema es muy similar al problema de Newsvendor problem ya que la decisiónse debe tomar en base a un análisis marginal. Supongamos que tenemos x unidades decapacidad restantes y que recibimos una reserva de la clase 2. Si aceptamos la reservarecolectamos p2. Si no la aceptamos, venderemos la unidad x-ésima solo si la demandade la clase 1 es igual o mayor a x, es decir, D1 ≥ x. Por lo tanto, la ganancia esperadapor reservar la x-ésima unidad a la clase 1 (el valor marginal esperado) es p1P(D1 ≥ x).Aceptaremos vender la unidad a 2 si el precio p2 excede este valor marginal,

p2 ≥ p1P(D1 ≥ x)

Se debe notar que el lado derecho es decreciente en x, por lo tanto existe un nivel y∗j , talque aceptaremos la clase 2 si la capacidad restante sobrepasa este nivel. En otras palabrasse cumple que:

p2 < p1P(D1 ≥ y∗1) y p2 ≥ p1P(D1 ≥ y∗1 + 1)

10


Si la función de distribución F1(x) es continua, entonces,

p2 = p1P(D1 > y∗1)

o, equivalentemente,

y∗1 = F−1(

1− p2

p1

)Esta expresión se conoce como regla de Littlewood, y es óptimo para y∗1 .Alternativamente, usando bid-price,

π(x) = p1P(D1 > x)

Este resultado es un caso especial para el modelo de n clases.

Modelo para n clasesNuevamente se asume que las n clases llegan en n etapas, ordenadas según los valores

de venta. Se cumple que p1 > p2 > · · · > pn. Por lo tanto, la primera en llegar es laclase n, seguida por n− 1, así hasta que lleguen todas. Con estos supuestos se plantea unproblema de programación dinámica, el cual en el caso de demanda continua, se puedeencontrar el óptimo. El vector y∗ = (y∗1 , y∗2 , ..., y∗n), cumple que

P(Bj(y∗, D)) =pj+1

p1∀j

donde

Bj(y, D) ≡ {D1 > y1, D1 + D2 > y2, ..., D1 + · · ·+ Dj > yj}

Como se mencionó anteriormente para n = 2, recuperamos la regla de Littlewood.Cabe destacar que

Bj(y, D) = Bj−1(y, D) ∩ {D1 + · · ·+ Dj > yj}

por lo que es necesario que se cumpla Bj−1(y, D) para que se cumpla Bj(y, D).Este problema se puede resolver según dos enfoques, programación dinámica o Monte

carlo.

El algoritmo se puede representar en seudocódigo de la siguiente forma:

11


Algorithm 1: Monte carlo para RM

1 Generar y guardar K vectores de demanda aleatorios dk = (dk1, ..., dk

n)2 k = 1, j = 13 while k ≤ K y j ≤ n− 1 do4 Calcular la suma: Sk

j = dk1 + dk

2 + ... + dkj

5 Formar el vector Sk = (Sk1, ..., Sk

n)

6 Inicializamos el conjunto K′ = {1, ..., K} y j = 17 while j ≤ n− 1 do8 Ordenar los vectores Sk, k ∈ K′ por la j-ésima componente, Sk

j9 Se llamará [l] al l-ésimo elemento de K′ en esta lista ordenada

10 Buscamos el índice l∗ =⌊

pj+1pj· |K′|

⌋y calculamos yj =

12(S

[l∗]j + S[l∗+1]

j )

11 Actualizamos K′, esto es, quitando los valores tales que Skj < yj

12 j=j+1

Para encontrar intervalos de confianza para estos parámetros debemos hacer esta sim-ulación varias veces, con datos distintos generados a partir de las distribuciones.

HeurísticasLa mayoría de los sistemas implementados para encontrar los límites de venta, uti-

lizan heurísticas para ello. Tienen varias ventajas como códigos simples de utilizar, sonde rápida ejecución y obtienen valores muy cercanos al óptimo. Existen dos conocidasheurísticas: EMSR-a y EMSR-b, las cuales se adaptan a los supuestos mencionados ante-riormente.

EMSR-aEs la heurística más utilizada, a pesar de que EMSR-b obtiene mejores resultados.Está basada en la idea de aplicar la regla de Littlewood sucesivamente a pares de

clases. Consideremos la etapa j + 1 en que la j + 1-ésima clase llega, con el precio pj+1.Intentamos calcular cuánto se debe reservar a las demás clases j, j− 1, ..., 1, es decir, en-contrar yj para la clase j y mayores. Para ello, consideremos una clase k y las restantesclases j, j− 1, ..., 1 y comparemos k con j + 1 de forma aislada. Usando la regla de Little-wood y la cantidad yj+1

k (correspondiente a la cantidad que le reserva j + 1 a k) se cumpleque,

P(Dk > yj+1k ) =

pj+1

pk

Repitiendo para cada clase k = j, j− 1, ..., 1, se consigue encontrar cuál es la capacidadque tienen disponibles las clases j, j− 1, ..., 1 simplemente sumando,

yj =j

∑k=1

yj+1k

12


Durante un tiempo se pensó incluso que este era un óptimo, pero tiempo después secomprobó que no era así. En efecto, esta heurística tiene el problema de ser demasiadoconservadora, ya que no considera el efecto de la demanda agregada. Esto quiere decirque arroja malos resultados cuando los precios de las demandas futuras son muy pare-cidos. Por ejemplo, para j + 1 supongamos que pj = pj−1 = · · · = p1 = p, en vez deconsiderar estas j clases como una sola, realiza el cálculo para cada una, por lo que yj serámayor de lo que debería.

EMSR-bEs una alternativa que intenta evitar el efecto agregado de EMSR-a. Este método tam-

bién utiliza Littlewood para dos clases, pero lo hace agregando la demanda por niveles.Además, usa el precio de venta ponderado según la esperanza de la demanda de cadauna de las demandas futuras.

Consideremos la etapa j + 1 en la cual queremos determinar el nivel de protección yj.Definamos la demanda agregada de j como

Sj =j

∑k=1

Dk

y el precio ponderado, pj, como

pj =∑

jk=1 pkE(Dk)

∑jk=1 E(Dk)

Lo niveles yj se elijen usando la siguiente ecuación:

P(Sj > yj) =pj+1

pj

Pregunta 1

Considere cuatro clases con una demanda normalmente distribuida y con precios deventa que aparecen en la siguiente Tabla:

Datos demandaj pj µj σj1 1050 17.3 5.82 567 45.1 153 534 39.6 13.24 520 34 11.3

Cuadro 1: Modelo estático de un solo recurso

13


Encuentre los niveles yj a reservar usando EMSR-a, EMSR-b y el óptimo a través desimulación.

Solución

Comencemos con EMSR-a:Para y1, se cumple que y1 = y2

1 = µ1 + φ−1(

1− p2p1

)σ1. Al reemplazar se obtiene

y1 = 16.71, lo cual corresponde a la cantidad reservada exclusivamente para la clase 1.Para la clase 2 el cálculo es el siguiente:

y31 = µ1 + φ−1

(1− p3

p1

)σ1

= 17.1

y32 = µ2 + φ−1

(1− p3

p2

)σ2

= 21.5

y2 = y31 + y3

2 = 38.7

Finalmente para la clase 3,

y41 = µ1 + φ−1

(1− p4

p1

)σ1

= 17.4

y42 = µ2 + φ−1

(1− p4

p2

)σ2

= 24.3

y43 = µ3 + φ−1

(1− p4

p3

)σ3

= 13.99

y3 = y41 + y4

2 + y43 = 55.68

Usando EMSR-b, se consiguien los siguientes yj:Para la clase 1 es el mismo cálculo que en EMSR-a, por lo tanto, y1 = 16.71.Para la clase 2,

y2 = µ1 + µ2 +√

σ21 + σ2

2 · φ−1(

1− p3 · (µ1 + µ2)

µ1p1 + µ2p2

)= 50.94

mientras que para la 3,

y3 = µ1 + µ2 + µ3 +√

σ21 + σ2

2 + σ21 · φ

−1(

1− p4 · (µ1 + µ2 + µ3)

µ1p1 + µ2p2 + µ3p3

)= 83.15

14


La tabla de resumen es la siguiente:

Niveles de protección

j OPT EMSR-a EMSR-a1 16.71 16.71 16.712 42.5 38.7 50.93 72.3 55.6 83.14

Cuadro 2: Tabla resumen niveles obtenidos

Pregunta 2

Suponga que quedan 3 asientos por vender en un vuelo que pueden ser vendidos aprecio completo por US$1.000 o a precio descontado por US$400. Suponga además que laprobabilidad que lleguen 0, 1, o 2 clientes que compran a precio completo es 0.1, 0.25, y0.35, respectivamente. Utilice la regla de Littlewood para decidir si se vende el pasaje siel siguiente cliente quiere comprar a precio descontado.

¿Qué dificultades se enfrenta cuando uno trata de implementar la regla de Littlewooden la práctica?

Solución

Sea pk la probabilidad de que al menos lleguen k clientes a comprar a precio completo.Se tiene que: p0 = 1, p1 = 0.9, p2 = 0.65 y p3 = 0.3 (pi = 0, ∀i ≥ 4).

Se debe buscar k∗ tal que:

maxk

1000pk ≥ 400

Lo que se cumple con k∗ = 2. Esto quiere decir que se deben reservar dos de los tresasientos que quedan, por lo tanto se le vende el asiento al cliente con precio descontado.

Esta regla presenta algunos problemas tales como:

Se debe conocer la demanda y la probabilidad de que llegue una cierta cantidad declientes.

Es óptimo para 2 precios y es útil para condiciones simples. Para varios precios ydemandas puede que no sea tan claro aplicar esta regla.

15


Son problemas que por lo general dependen del tiempo y por lo tanto son dinámicosy requieren que la solución se vaya actualizando.

Pregunta 3

Se desea simular el efecto de un sistema de RM en la venta de entradas a un cine (Joik)con capacidad C. En este sistema los clientes pueden comprar entradas para un showdesde 14 hasta 1 dia antes de la función con un descuento o en el momento de la funcióna precio completo.

Suponga que conoce p(i, q), la probabilidad que al menos i personas aparezcan a com-prar entradas al momento de la función, si q entradas se han vendido con descuento. Noteque p(0, q) = 1 para todo q ∈ {0, . . . , C} y suponga que estas funciones son constantesdurante las 2 semanas.

1. Utilize Littlewood para definir cuantas entradas reservar para precio completo si elprecio de descuento por internet tiene un 50 % de descuento y se han vendido 10entradas con descuento. Respuesta en función de p(i, q).

2. Deseamos hacer una simulación del período de venta de entradas. Suponga que eltiempo entre clientes en internet sigue una distribución exponencial con tasa λd quedepende del dia d. ¿Cuáles son las variables de estado, eventos y los estadísticos deinteres en una simulación con incrementos variables de tiempo?

Solución

1. Si el precio completo es c, Littlewood dice que se vende con descuento si cp(i, 10) <.5c, es decir si p(i, 10) < 0.5. El número de asientos que se debería guardar para pre-cio completo entonces es el mayor i tal que p(i, 10) ≥ 0.5. Note que por su definiciónp(i, 10) es decreciente en i.

2. variables de estado: q número de asientos vendidos, d el día de la simulacíon.

Eventos: 1. la llegada de un cliente a comprar en internet. Seguido del cálculode la cantidad de asientos que se reservan para precio completo. 2. Cambio dedia, pues cambia la tasa de llegada. 3. El día de la función: generar llegadas declientes a tiempo completo.

estadístico de interés son los ingresos por entradas. También para medir la cali-dad de servicio puede ser en número de clientes con precio entero y de internetque no pueden comprar entrada.

Pregunta 4

16


MegaRed es un canal de televisión que cada tarde tiene 25 espacios publicitarios de30 segundos. Suponga que estamos en marzo y que la empresa se encuentra vendiendopor adelantado publicidad para los primeros días de julio, siendo el valor cada espaciode 30 segundos igual a $USD 4,000. No obstante, se sabe que el 9 de julio habrá un eventodeportivo muy importante y que el canal podría llegar a vender a último minuto espaciospublicitarios a prestigiosas empresas deportivas por un precio de $USD 10,000 cada uno.Teniendo en cuenta los antecedentes proporcionados responda:

1. ¿Cuántos espacios publicitarios debería el canal vender en forma anticipada? Supon-ga que un espacio publicitario que no se vende vale 0.

2. Ahora suponga que si un espacio publicitario no es vendido anticipadamente o aúltimo minuto puede ser utilizado para promocionar programas del canal, siendovalorado en $USD 2,500. ¿Cómo cambia su respuesta a la pregunta anterior?

Utilice la siguiente distribución de probabilidad para las ventas de último minuto:

Demanda [unids.] 8 9 10 11 12 13 14 15 16 17 18 19Probabilidad .0 .05 .1 .15 .2 .1 .1 .1 .1 .05 .05 .0

Cuadro 3: Distribución de probabilidad de la demanda

Solución

1. Para determinar la cantidad de espacios publicitarios se debe conocer la Pr(D ≥ k),∀k. Sea pk la probabilidad de que al menos lleguen k empresas.

k 8 9 10 11 12 13 14 15 16 17 18 19pk 1 1 .95 .85 .7 .5 .4 .3 .2 .1 .0.5 .0

Cuadro 4: Valores de pk para cada k

Se busca la cantidad k∗ tal que

4.000 ≥ 10.000Pr(D ≥ k∗ + 1)4.000 < 10.000Pr(D ≥ k∗)

Lo que se cumple con k∗ = 13.

2. En este caso tenemos un precio de salvataje de $USD 2,500. En este caso esper-aríamos que la cantidad reservada para empresas deportivas sea mayor. Si se vendea precio anticipado, el ingreso extra que se genera es de $USD1,500, y si se espera aúltimo minuto, en caso de ser vendido, se obtienen $USD7,500.

17


El problema entonces:

1.500 ≥ 7.500Pr(D ≥ k∗ + 1)1.500 < 7.500Pr(D ≥ k∗)

La cantidad a reservar es k∗ = 15.

Pregunta 5

Considere cuatro clases con una demanda normalmente distribuida y con precios deventa que aparecen en la siguiente Tabla:

Datos demandak pk µk σk1 40 5.6 1.22 20 18.6 7.93 5 41.7 15.4

Cuadro 5: Modelo estático de un solo recurso

1. Encuentre los niveles yj a reservar usando EMSR-a, EMSR-b.

2. Encuentre el óptimo usando datos simulados.

Solución

1. Comencemos con EMSR-a:

Para y1, se cumple que y1 = y21 = µ1 + φ−1

(1− p2

p1

)σ1. Al reemplazar se obtiene

y1 = 5.6, lo cual corresponde a la cantidad reservada exclusivamente para la clase1.

Para la clase 2 el cálculo es el siguiente:

y31 = µ1 + φ−1

(1− p3

p1

)σ1

= 6.98

y32 = µ2 + φ−1

(1− p3

p2

)σ2

= 23.9

y2 = y31 + y3

2 = 30.9

Usando EMSR-b, se consiguien los siguientes yj:

18


Para la clase 1 es el mismo cálculo que en EMSR-a, por lo tanto, y1 = 5.6.

Para la clase 2,

y2 = µ1 + µ2 +√

σ21 + σ2

2 · φ−1(

1− p3 · (µ1 + µ2)

µ1p1 + µ2p2

)= 30.8

2. El modelo para n clases nos dice que se deben cumplir las siguientes igualdades:

Pr(D1 > y1) =p2

p1

Pr(D1 > y1, D1 + D2 > y2) =p3

p1

La primera igualdad es simplemente la regla de Littlewood, mientras que la segun-da la podemos reescribir como:

Pr(D1 > y1, D1 + D2 > y2) =p3

p1

⇐⇒ Pr(D1 + D2 > y2|D1 > y1)Pr(D1 > y1) =p3

p1

⇐⇒ Pr(D1 + D2 > y2|D1 > y1) =p3

p1Pr(D1 > y1)=

p3

p2

Esta última condición lo que nos dice es tenemos que encontrar un y2 tal que dadoque D1 > y1, el número de veces que D1 + D2 > y2 debe ser igual a p3

p2.

Se generaron 100 valores de demanda para D1 y D2, a partir de los parámetros delas distribuciones. En el gráfico 3 estos valores están graficados. En el eje horizontalestá el valor de S1 = D1 y en el vertical, S2 = D1 + D2.

Primero buscamos el valor de y∗1 . Para ello, debemos usar el ratio p2p1

= 0.5. Estoquiere decir que tenemos que encontrar el valor de S1 que está en la mitad de losdatos y asignárselo a y∗1 , para que así Pr(D1 > y1) = 0.5. Ordenamos los datos ytomamos el que está entre el 50 y el 51, y los promediamos. Con esto obtenemosy∗1 = 5.94.

Una vez que tenemos este número, calculamos y2. La condición nos dice que hayque utilizar solo los S2 tales que D1 > y1, por lo tanto, solo nos quedamos con losdatos a la derecha de y∗1 , es decir, con 50 números.

El ratio p3p2

= 0.25 nos dice que debemos escoger el y2 tal que solo un 25 % de los S2

queden fuera, una vez que los hemos ordenado. Como tenemos 50 datos, buscamos

19


S1

S 2

3 4 5 6 7 8 9

13

16

19

22

25

28

31

34

37

40

y∗1

y∗2

Figura 3: Gráfico con los valores de demanda simulados y los yi óptimos

el valor en la posición l∗ =⌊

p3p2· N⌋= b12.5c = 12, y l∗ + 1 = 13, y los promedi-

amos. Esto nos da y∗2 = 30.2.

Pregunta 6

Suponga que una cadena de hoteles nos ha pedido que le ayudemos con sus políti-cas de reservas en una fecha determinada. Vamos a tomar en cuenta que solo existen 3clases de clientes, 1, 2 y 3, con precios a pagar distintos y distribuciones de demanda conparámetros diferentes. Para este problema supondremos que las demandas son variablesaleatorias uniformes.

La siguiente tabla resume los parámetros del problema:

clase precio distribución1 10 U(0, 10)2 5 U(0, 50)3 1 U(40, 100)

Cuadro 6: Parámetros para el problema de hoteles

Encuentre los niveles y∗ para cada clase, usando el criterio que permite obtener elóptimo del problema.

20


SoluciónLos y∗ deben satisfacer las siguientes igualdades:

Pr(D1 > y1) =p2

p1

Pr(D1 > y1, D1 + D2 > y2) =p3

p1

La última igualdad la podemos reescribir como:

Pr(D1 + D2 > y2|D1 > y1) =p3

p2

Comenzamos calculando y∗1 :

Pr(D1 > y∗1) = 0.5∫ 10

y∗1

110

dx = 0.5

110

(10− y∗1) = 0.5

y∗1 = 5

Con este valor claro, ahora debemos calcular y∗2 :

Pr(D1 + D2 > y∗2 |D1 > 5) = 0.2∫ 10

5Pr(x + D2 > y∗2)

dx10

= 0.2∫ 10

5

∫ 50

y∗2−x

dy50

dx10

= 0.2∫ 10

5

150

(50− y∗2 + x)dx10

= 0.2

1500

((50− y∗2)(10− 5) +

102 − 52

2

)= 0.2

250− 500 · 0.2 +752

= 5y∗2

y∗2 = 37.5

21


3. Newsvendor problem

Pregunta 1

Considere un problema de Newsvendor, donde la demanda por productos está dadapor la v.a. continua D con soporte positivo y función de densidad f (x) y distribución F(d)(= P{D ≤ d} =

∫ d0 f (x)dx). La utilidad esperada se puede expresar como:

π(Q) = pE(Ventas) + vE(Sobras)− cQ, (1)

donde E(Ventas) =∫ Q

0 x f (x)dx +∫ ∞

Q Q f (x)dx y E(Sobras) =∫ Q

0 (Q− x) f (x)dx son elvalor esperado de las unidades vendidas y sobrantes, respectivamente. Además, c es elcosto de producción, p es el precio de venta, v es el precio de reventa y Q es la cantidadordenada. Definimos además el costo de ’underage’ Cu = p − c, el costo de ’overage’Co = c− v, y el costo de incertidumbre como :

CI(Q) = Cu

∫ ∞

Q(x−Q) f (x)dx + Co

∫ Q

0(Q− x) f (x)dx, (2)

1. Explique la ecuación (2) y muestre que CI(Q) = πIP − π(Q) donde πIP = (p− c)µes la utilidad esperada con información perfecta yµ =

∫ ∞0 x f (x)dx es la demanda

esperada.

2. Dada la ecuación (2), demuestre que la cantidad Q∗, que maximiza π(Q) viene dadopor:

Q∗ = F−1(

Cu

Co + Cu

),

donde F−1 es la inversa de la funcion distribucion F

3 Suponga ahora que D sigue una distribución Normal de media µ y varianza σ2.Nos interesa el costo de incertidumbre relativo, dado por CI(Q∗)

πIP=(

φ(z)Φ(z)

)×(

σµ

),

donde φ(z) y Φ(z) son la densidad y distribución de la normal estándar (media 0 yvarianza 1), y z = (Q∗ − µ)/σ.

Considere los siguientes productos mostrados en la tabla a continuacion. Ordenelos productos de acuerdo al ratio CI(Q∗)/πIP. Justifique su respuesta.

p c v µ σ

Producto 1 15000 7000 5000 300 150Producto 2 6000 3000 2500 2000 500Producto 3 10000 6000 5000 1500 375

22


HINT: Use el hecho que el término (φ(z)/Φ(z)) es decreciente en z (este término esla tasa de riesgo de la normal estándar).

Solución

1. La primera integral en (2) es el valor esperado de por cuanto la demanda supera elpedido que hicimos. A esto se cobra el beneficio perdido que es el precio de ventamenos el costo de ordenar (p − c). La segunda integral es el numero esperado depedidos que no fueron vendidos. Esta cantidad genera un costo que es igual al costode ordenar menos el precio de reventa (c− v).

Para mostrar la equivalencia, desarrollamos (2) obteniendo

CI(Q) = (p− c)∫ ∞

Qx f (x)dx− p

∫ ∞

QQ f (x)dx + cQ

∫ ∞

0f (x)dx− c

∫ Q

0x f (x)dx

−v∫ Q

0(Q− x) f (x)dx

el último termino corresponde a vE(Sobras). Sumando y restando la cantidad p∫ Q

0 x f (x)dxa esta expresión obtenemos:

CI(Q) = (p− c)∫ ∞

0x f (x)dx− p

(∫ Q

0x f (x)dx +

∫ ∞

QQ f (x)dx

)+ cQ− vE(Sobras)

= (p− c)µ− pE(Ventas) + cQ− vE(Sobras)= πIP − π(Q)

2. Dada que la cantidad Q∗ que maximiza π(Q) también minimiza CI(Q) (debido aque CI(Q) = πPI − π(Q)), encontramos la solución óptima al derivar e igualar acero: d(CI(Q))/dQ = 0, donde

ddQ

CI(Q) = −Cu

∫ ∞

Qf (x)dx + Co

∫ Q

0f (x)dx

= −Cu

(1−

∫ Q

0f (x)dx

)+ Co

∫ Q

0f (x)dx

= −Cu(1− F(Q)) + CoF(Q) = 0

simplificando esta expresion obtenemos F(Q) = Cu/(Cu + Co) de donde se obtieneel resultado.

3. Utilizamos los datos para calcular las distintas partes del ratio CI(Q∗)πIP

. Utilizamosque Cu/(Cu + Co) = (p − c)/(p − v). Ademas, como F(Q∗) = P{D ≤ Q∗} =P{(D−µ)/σ ≤ (Q∗−µ)/σ} = Φ(z∗) tenemos que (Q∗−mu)/σ = z∗ = Φ−1(Cu/(Cu +Co)).

23


σ/µ Cu/(Cu + Co) z∗

Producto 1 1/2 4/5 0.84Producto 2 1/4 6/7 1.07Producto 3 1/4 4/5 0.84

Como el término (φ(z)/Φ(z)) es decreciente en z, tenemos que el producto 2 es elque tiene el menor ratio CI(Q∗)

πIP, seguido por producto 3 y el producto 1 es el que

tiene este ratio mayor.

Pregunta 2

1. Demuestre que la siguiente ecuación tiene como solución Q∗ que maximiza las util-idades en el problema de Newsvendor, donde p es el precio de venta, c es el costo,v el precio de reventa, todos valores fijos.

(p− c)P(lleguen por lo menos Q) = (c− v)P(lleguen menos de Q)

2. Usando la expresión para Q∗ calculada en la pregunta anterior, encuentre el canti-dad que se debe ordenar para los siguientes valores. Si encuentra algún problema,explique qué está fallando.

p c vItem 1 200 181 180Item 2 200 190 195Item 3 400 240 150Item 4 150 240 150

3. Ahora suponga que el precio depende de la cantidad demandada, según la relaciónp(x) = αx con α > 0. Suponga además que la demanda se distribuye uniforme-mente en un intervalo (0, T), con T > 0, y que los costos dependen linealmente deQ, c(Q) = αT

2 Q. Por último, considere que v, el precio de reventa, es fijo.

a) Encuentre el Q∗ que maximiza las utilidades.

b) ¿Cuál es el valor de Q∗ cuando α = 1, T = 10 y v = 2?

c) ¿Qué pasa cuando v = α. Explique.

Solución

24


1. Primero se debe notar que c− v = Co y que p− c = Cu. Además la probabilidad deque lleguen al menos Q corresponde a F(Q). Con esto reescribimos la ecuación

Cu(1− F(Q)) = CoF(Q)

Cu = (Co + Cu)F(Q)

F(Q) =Cu

Co + Cu

Q = F−1(

Cu

Co + Cu

)2. Por Item tenemos:

Item 1. Q∗ = F−1(

1920

)Item 2. Aquí tenemos un problema ya que v > c. En este caso siempre se tienen utili-

dades por los productos, así que conviene pedir lo máximo posible.

Item 3. Q∗ = F−1(

160250

)Item 4. En este caso el costo es mayor al precio de venta, por lo que nunca conviene

pedir. Q∗ = 0.

3. a) La utilidad se escribe como

π(Q) =∫ Q

0αx · x dx

T+∫ T

QαxQ

dxT

+ v∫ Q

0(Q− x)

dxT− αT

2Q

=αQ3

3T+

αQ2T

(T2 −Q2) +vQ2

2T− αT

2Q

=⇒ dπ(Q)

dQ=

αQ2

T+

αT2− 3αQ2

2T+

vQT− αT

2

= −αQ2

2T+

vQT

Lo cual al igual a cero, y descartando la solución Q∗ = 0, nos queda:

Q∗ =2vα

b) Reemplazando obtenemos que Q∗ = 4.

25


c) Cuando v = α, Q∗ ya no depende de los parámetros y es constate igual a 2.Cuando se cumple esta condición el tomador de decisiones se vuelve indifer-ente al precio de venta, a los costos y el precio de reventa, por lo que es neutroa las condiciones del mercado.

Pregunta 3

Un micro empresario posee una producción de un licor llamado “Efimerouse”, el cualtiene la característica de que luego de una semana de producción, perece convirtiéndoseen una solución que no puede ser vendida, pero sí reutilizado para la producción desiguientes unidades. Considere que cada día Lunes se pone en venta una cierta cantidadpara ser vendida durante la semana, a un precio de $3500 la unidad, mientras que el costounitario es de $1000 y el valor estimado de una botella vencida es de $375. Suponga quela demanda sigue una distribución (continua) uniforme en [0, 100].Hint: Si X ∼ U[a, b], entonces F−1(p) = a + (b− a)p para p ∈ [0, 1].

a) Determine la cantidad óptima de botellas a vender cada día Lunes.

Suponga que la fábrica posee un límite de producción semanal de 240 unidades comomáximo.

b) Determine el número óptimo de unidades a producir bajo este escenario.

c) Encuentre las utilidades esperadas para los casos de las partes a) y b) a obtener enuna semana. Si no es capaz de obtener los valore precisos, también se dará puntajepor escribir las expresiones.

Suponga al igual que en la parte b) que la fábrica posee un límite de producción sem-anal de 60 unidades. Por otro lado, se tiene la posibilidad de hacer una inversión por unmonto fijo de $500000 tal que la fábrica alcanza una capacidad extra de producción de 60unidades. Es decir, en caso de hacer la inversión, el vendedor podría producir semanal-mente cualquier cantidad entre 0 y 120 unidades. Considerando además un factor de de-scuento de 0.99 del dinero en cada semana (es decir, si en cada semana futura desde i ≥ 0recibo un monto esperado de m, entonces el monto en valor presente es de ∑i≥0 m · 0.99i).Haga el supuesto de que las compras, e ingresos por venta y salvataje de referentes decada semana son realizados en esa semana.

d) Determine si es o no conveniente hacer la inversión, considerando el valor presentedel dinero.

Solucón:

26


a) Se tiene que p = 3500, c = 1000 y s = 375, luego:

Cu = p− c = 3500− 1000 = 2500Co = c− s = 1000− 375 = 625

Luego la cantidad óptima es:

Q∗ = F−1(

Cu

Co + Cu

)= F−1

(2500

625 + 2500

)= F−1(0.8)= 80

b) Dado que el valor óptimo es de 80 unidades cuando no hay restricción de capacidad,entonces con un capacidad de 60 unidades, se deberán producir hasta ese número.

c) La expresión de las utilidades es la siguiente:

πQ = p∫ +∞

0mın{Q, x} f (x)dx + s

∫ +∞

0max{Q− x, 0} f (x)dx− cQ

= p∫ Q

0x

1100

dx +∫ 100

QQ

1100

dx + s∫ Q

0(Q− x)

1100

dx− cQ

Donde Q es la cantidad a producir.Para la parte a) es:

π80 = p(∫ 80

0x

1100

dx + p∫ 100

8080

1100

dx)+ s

∫ 80

0(80− x)

1100

dx− 80c

= 3500((

802

2− 02

2)

1100

+ 80(100− 80))+ 375

(−0 +

(80− 0)2

2

)1

100− 80 · 1000

= 100000

Para la parte b) es:

π60 = p(∫ 60

0x

1100

dx + p∫ 100

6060

1100

dx)+ s

∫ 60

0(60− x)

1100

dx− 60c

= 3500((

602

2− 02

2)

1100

+ 60(100− 60))+ 375

(−0 +

(60− 0)2

2

)1

100− 60 · 1000

= 93750

Como es de esperar, la utilidad da más en la parte a), en donde se produce la canti-dad óptima que no está sujeta a la restricción de capacidad.

27


d) Para esto, debemos comparar ambos escenarios. Sean π80 y π60 las utilidades se-manales que se obtienen según las partes a) y b) respectivamente. Si no se hace lainversión, entonces la utilidad en valor presente es:

πs/inv = π60 ∑i≥0

0.99i = π601

1− 0.99= 100π60 = 9375000

πc/inv = π80 ∑i≥0

0.99i − 5000000 = π801

1− 0.99− 500000 = 100π80 − 500000

= 10000000− 500000 = 9500000

Por ende conviene hacer la inversión.

28


4. Descomposición de benders

Se utiliza este algoritmo para resolver problemas de la forma:

mın c′x +K

∑w=1

αwf′yw

s.a. Ax = bBwx + Dyw = dw ∀wx ≥ 0yw ≥ 0 ∀w

Este problema se divide en un problema principal (problema maestro)y en varios sub-problemas.

Los subproblemas, para cada w son:

mın f′yws.a. Bwx + Dyw = dw

yw ≥ 0

De cada subproblema se obtiene su dual, que es de la forma

max p′w(dw − Bwx)s.a. p′wD ≤ f′

Sea P = {p | p′D ≤ f′}. Sea también pi un punto extremo y wj un rayo extremo delconjunto P. Este es el conjunto de solución para el problema dual para cada w. Si comosolución se obtiene zw(x) = ∞, o equivalentemente el problema primal no es factible,entonces se debe agregar restricciones del tipo:

(wj)′(dw − Bwx) ≤ 0, ∀ j

Cada vez que el zw(x) sea finito, entonces se trata de un punto extremo del conjuntoP. En particular zw(x) es el mínimo valor que cumple

(pi)′(dw − Bwx) ≤ zw(x), ∀ i

El problema maestro, finalmente, es:

29


mın c′x +K

∑w=1

αwzw

s.a. Ax = b

(pi)′(dw − Bwx) ≤ zw, ∀ i, w

(wj)′(dw − Bwx) ≤ 0, ∀ j, w

El algoritmo de D. de Benders:

1. Se comienza con una solución incial (x∗, z∗), que cumpla con el problema maestrorelajado.

2. Para cada w se soluciona el subproblema

mın f′yw

s.a. Dyw = dw − Bwx∗

yw ≥ 0

del cual se obtienen las soluciones duales.

3. Si para cada w su correspondiente subproblema es factible y el costo óptimo esmenor o igual a z∗w, entonces se encontró la solución al problema principal y al al-goritmo termina.

4. Si para algún w el valor encontrado de costo es mayor que z∗w entonces se debeagregar al problema maestro la siguiente restricción

(pi(w))′(dw − Bwx) ≤ zw(x)

5. Si para algún w el problema es infactible, entonces para el problema dual existe unrayo extremo wj(w) al cual se le debe asociar la restricción que se debe incluir en elproblema maestro

(wj(w))′(dw − Bwx) ≤ 0

Pregunta 1

Se tiene un problema de generación electrica con dos fuentes de producción: una cen-tral térmica y una hidráulica. La central hidráulica puede producir a los más 5 unidadesen el primer perído, y en el segundo puede producir a lo más 5 + rs − h1, donde rs es una

30


variable aleatoria que está determinada por el escenario s. La térmica no tiene límite deproducción para ningún período.

En la primera etapa se debe satisfacer toda la demanda que es de 10, y para el segundose debe satisfacer una demanda ds

2.El siguiente PPL resume lo descrito. Resuélvalo usando Descomposición de Benders.

mın 3x1 +18

8

∑s=1

cs2xs

2

x1 + h1 ≥ 10h1 ≤ 5xs

2 + hs2 ≥ ds

2 ∀s = 1, ..., 8hs

2 ≤ 5 + rs − h1 ∀s = 1, ..., 8

x1, h1, xs2, h2

2 ≥ 0

Los escenarios están determinados por la siguiente Tabla:

s 1 2 3 4 5 6 7 8ds

2 15 10 15 10 15 10 15 10cs

2 1 1 5 5 1 1 5 5rs 0 0 0 0 10 10 10 10

Cuadro 7: Valores que toman las v.a. para cada escenario

Solución

Se plantea primero el Problema Maestro.

mın 3x1 +18

8

∑s=1

γs

x1 + h1 ≥ 10h1 ≤ 5γs ≥ ds

2πs + (5 + rs − h1)γs ∀s = 1, ..., 8

x1, h1, γs ≥ 0

El Subproblema, para cada s:

φs(x1, h1) = mın cs2xs

2xs

2 + hs2 ≥ ds

hs2 ≤ 5 + rs − h1

hs2, xs

2 ≥ 0

⇐⇒

φs(x1, h1) = max ds2πs + (5 + rs − h1)γ

s

πs ≤ cs2

πs + γs ≤ 0πs ≥ 0, γs ≤ 0

31


Notar que ∀(x1, h1), φ(x1, h1) es siempre factible (xs2, hs

2) = (ds2, 0). Por lo tanto, no son

necesarios cortes de factibilidad (dual tiene óptimo factible).

πs

γs

cs2

πs + γs ≤ 0

(0, 0)

(cs2,−cs

2)

Figura 4: Conjunto factible del dual del Subproblema

Iteraciones

mın 3x1x1 + h1 ≥ 10h1 ≤ 5x1, h1 ≥ 0

Una solución para este problema podría ser: (x∗1 , h∗1) = (5, 5) γ∗s = −∞ ∀s.Los subproblemas:

(15, 1, 0) φ1(5, 5) = 15 · 1 + (5 + 0− 5)(−1) = 15(10, 1, 0) φ2(5, 5) = 10 · 1 + (5 + 0− 5)(−1) = 10(15, 5, 0) φ3(5, 5) = 15 · 5 + (5 + 0− 5)(−5) = 75(10, 5, 0) φ4(5, 5) = 10 · 5 + (5 + 0− 5)0 = 50(15, 1, 10) φ5(5, 5) = 15 · 1 + (5 + 10− 5)(−1) = 5(10, 1, 10) φ6(5, 5) = 10 · 1 + (5 + 10− 5)(−1) = 0(15, 5, 10) φ7(5, 5) = 15 · 5 + (5 + 10− 5)(−5) = 25(10, 5, 10) φ8(5, 5) = 10 · 5 + (5 + 10− 5)(−5) = 0

Como γ∗s < φ(5, 5) para todo s, agregamos restricciones al maestro:

32


mın 3x1 +18

8

∑s=1

γs

x1 + h1 ≥ 10h1 ≤ 5x1, h1 ≥ 0γ1 ≥ 15− (5− h1) = 10 + h1γ2 ≥ 10− (5− h1) = 5 + h1γ3 ≥ 75− 5(5− h1) = 50 + 5h1γ4 ≥ 50− 5(5− h1) = 25 + 5h1γ5 ≥ 15− (15− h1) = h1γ6 ≥ 10− (15− h1) = −5 + h1γ7 ≥ 75− 5(15− h1) = 5h1γ8 ≥ 50− 5(15− h1) = −25 + 5h1γ1, ..., γ8 ≥ 0

Segunda Iteración de Benders

Sumando ∑ γs podemos escribir el maestro como

mın 3x1 +18(60 + 24h1) = 3x1 + 3h1 +

152

x1 + h1 ≥ 10h1 ≤ 5

x1, h1 ≥ 0

Todas soluciones tales que x1 + h1 = 10 (h1 ≤ 5 y x1, h1 ≥ 0) son óptimos. La soluciónal problema Maestro, 30 + 15

2 .Claramente si usamos (x∗1 , h∗1) = (5, 5) voy a tener que γ∗s = φ(5, 5) ya que esta solu-

ción fue usada en la iteración anterior (se repite lo que está en la iteración anterior).Tenemos entonces la solución óptima del maestro.Si usamos (x∗1 , h∗1) = (10, 0), entonces

(15, 1, 0) φ1(5, 5) = 15 · 1 + (5 + 0− 0)(−1) = 10(10, 1, 0) φ2(5, 5) = 10 · 1 + (5 + 0− 0)(−1) = 5(15, 5, 0) φ3(5, 5) = 15 · 5 + (5 + 0− 0)(−5) = 50(10, 5, 0) φ4(5, 5) = 10 · 5 + (5 + 0− 0)(−5) = 25(15, 1, 10) φ5(5, 5) = 15 · 1 + (5 + 10− 0)(−1) = 0(10, 1, 10) φ6(5, 5) = 10 · 0 + (5 + 10− 0)(−5) = 0(15, 5, 10) φ7(5, 5) = 15 · 5 + (5 + 10− 0)(−5) = 25(10, 5, 10) φ8(5, 5) = 10 · 0 + (5 + 10− 0)(0) = 0

33


Escenarios 6 y 8 tiene γ∗s < φs(10, 0), entonces se agregan al maestro los cortes:

γ6 ≥ 10 · 0 + (15− h1)0 = 0γ8 ≥ 10 · 0 + (15− h1)0 = 0

Al agregar estas restricciones al maestro se obtiene que la única solución posible es(x∗1 , h∗1) = (5, 5).

Pregunta 2

Encuentre una cota inferior y una superior para el problema original de minimización,usando la información proporcionada por los subproblemas y el problema maestro, cuandose utiliza la descomposición de Benders.

Solución

Cota inferior:Sabemos que al problema maestro de la D. B. se le van agregando restricciones por cada

iteración, por lo que el conjunto de solución es cada vez más pequeño. Luego, para unaiteración dada, la solución del problema maestro va a ser mejor solución que la óptima delproblema completo.

Cota superior:Los subproblemas utilizan el valor de x∗ como dado, por lo que su solución es peor

que la que encontraría el problema que considera el valor de x como una variable. De estaforma, el valor de zi encontrado en cada iteración es mayor de lo que podría ser cuandose resuelve el problema original.

La cota se puede escribir como:

c′x +K

∑w=1

αwz∗w

donde los zw son los encontrados en cada subproblema.

Pregunta 3

Una empresa de generación eléctrica debe decidir la capacidad a instalar de dos gen-eradores (indexados por j = 1, 2) con diferentes costos fijos y de operación, de forma desatisfacer la demanda de la zona. Cada día se divide en 3 partes de igual duración, in-dexados por i = 1, 2, 3. Estos corresponden a las partes del día en los cuales la demandapuede ser baja, media o peak respectivamente. Los costos fijos por unidad de capacidad

34


del generador j es amortizada por su vida útil en una suma cj por día. Los costos deoperación del generador j durante la parte i-ésima del día es fij. Si la demanda durantela i-ésima parte del día no puede ser satisfecha, se incurre en un costo adicional gi parasuplirla. Finalmente, la capacidad de cada generador j debe ser al menos bj.

Hay dos fuentes de incertidumbre, la demanda di durante cada parte del día, y ladisponibilidad aj del generador j. La demanda di durante el día puede tomar cuatro val-ores di,1,...,di,4, con probabilidad pi,1,...,pi,4, respectivamene. La disponibilidad del gener-ador 1 es a1,1,...,a1,4, con probabilidad q1,1,...,q1,4, para cada uno de los eventos. Similar-mente, la disponibilidad del generador 2 es a2,1,...,a2,5, con probabilidad q2,1,...,q2,5.

1. Formule un problema de programación estocástica que minimice los costos y cumplacon las restricciones.

2. Escriba el problema Maestro y el Subproblema de la descomposición de Benders paraeste problema.

3. Encuentre la solución incial y haga una iteración del algoritmo de Benders. Escribael problema Maestro modificado.

Solución

1. Se utilizará la variable xj, j = 1, 2 para indicar las unidades de capacidad instaladade cada generador. También se incluirá la variable yw

ij para denotar los niveles deoperación del generador j durante la parte i-ésima del día, bajo el escenario w. Fi-nalmente, la variable sw

i es la capacidad extra necesaria en el escenario w, durante laparte i del día.

mın2

∑j=1

cjxj + E

[3

∑i=1

(2

∑j=1

fijywij + gisw

i

)]s.t. xj ≥ bj ∀j

ywij ≤ aw

j xj ∀i, j, w2

∑j=1

ywij + sw

i ≥ dwi ∀i, w

xj, ywij s

wi ≥ 0 ∀i, j, w

2. La cantidad de escenarios w es 43 · 4 · 5 = 1280. Cada Subproblema se ve de la sigu-

35


iente forma:

mın3

∑i=1

(2

∑j=1

fijywij + gisw

i

)s.t. yw

ij ≤ awj xj ∀i, j

2

∑j=1

ywij + sw

i ≥ dwi ∀i

ywij , sw

i ≥ 0 ∀i, j

Recordando que cada subproblema se resuelve considerando xj, j = 1, 2, fijo.

Si utilizamos πwij y σw

i como las variables duales, el dual para cada w es

max3

∑i=1

(2

∑j=1

awj xjπ

wij + σw

i dwi

)= zw

s.t. πwij + σw

i ≤ fij ∀i, j

σwi ≤ gi ∀i

πwij ≤ 0 ∀i, j

σwi ≥ 0 ∀i

El Problema Maestro es, por lo tanto,

mın2

∑j=1

cjxj +W

∑w=1

ζwzw

s.t. xj ≥ bj ∀j3

∑i=1

(2

∑j=1

awj xjπ

wij + σw

i dwi

)≤ zw ∀w

xj ≥ 0 ∀j

La segunda desigualdad puede considerar un rayo extremo, con lo cual debe im-ponerse que la parte izquierda de la desigualdad sea menor a 0.

3. Una posible solución inicial puede ser xj = bj, j = 1, 2 y zw = −∞, ∀w. Con esto el

36


dual para cada subproblema w es

max3

∑i=1

(2

∑j=1

awj bjπ

wij + σw

i dwi

)s.t. πw

ij + σwi ≤ fij ∀i, j

σwi ≤ gi ∀i

πwij ≤ 0 ∀i, j

πwi ≥ 0 ∀i

Considerando el óptimo πw∗ij , ∀i, j, w y σw∗

i , ∀i, w finito, el valor z∗w es mayor a −∞por lo que se agregan al problema Maestro.

3

∑i=1

(2

∑j=1

awj xjπ

w∗ij + σw∗

i dwi

)≤ zw ∀w

Pregunta 4

Utilice Revenue Management para decidir una politica de arriendo de C habitacionesen un hotel en Viña del Mar. Suponga que para el mes de Enero hay tres tipos de clientes,los que arriendan por el fin de semana de año nuevo (F), los que arriendan por losprimeros 21 días del mes (T) y los que arriendan por el mes completo (M). Suponga que silas utilidades por arrendar el fin de semana de año nuevo son uF = X, entonces arrendarpor tres semanas uT = 3X y por mes uQ = 5X. Suponga que la probabilidad de que almenos i clientes de tipo k aparezcan cuando faltan t días para Enero está dada por pk,t(i).

1. En cuanto a las propiedades de pk,t(i), responda lo siguiente: ¿Cuánto es pk,t(0)?¿Son las pk,t(i) monótonas en i? Cuando t = 1 ¿cuál debería ser mayor pF,t(i), pT,t(i)o pM,t(i)? (Justifique sus respuestas)

2. Suponga las siguientes probabilidades (posiblemente artificiales) pF,t(i) = (1/2)i,pT,t(i) = 1/(i + 1) y pM,t(i) = (3/5)i. Utilice EMSRa para definir el numero dehabitaciones que se debe reservar para cada clase.

3. (0,5 pts) Deseamos ahora formular un problema de optimización estocástica quemaximice las utilidades. Suponga que t días antes que comience Enero tiene Chabitaciones disponibles y que el número de clientes de cada tipo que aparecerán esuna cantidad incierta. Suponga que las habitaciones no arrendadas al comienzo delmes pueden ser arrendadas con probabilidad 1 a un descuento que nos entrega unautilidad de uD = 0, 2X.

37


4. Describa el problema maestro y el subproblema de la descomposición de Benderspara este problema estocástico.

5. Si supone que la primera solución del maestro es el vector de ceros, haga una it-eración del algoritmo de Benders y escriba el problema Maestro modificado.

Solución

1. Claramente pk,t(0) = 1 pues representa la probabilidad de que al menos lleguen0 clientes, lo cual siempre ocurre. De la misma forma pk,t(i) es la probabilidad deque al menos lleguen i clientes, por lo que es esperable que a medida que crece i laprobabilidad disminuya, concluyendo que es una función decreciente.

t = 1 significa que se está a solo 1 día de que comience Enero, entonces se espera queaparezcan en mayor medida los que buscan vacaciones más cortas (los más sensiblesal precio) que los que están dispuestos a gastar mucho en sus vacaciones. Por lotanto, las probabilidades deberían estar en el siguiente orden: pF,1(i) ≥ pT,1(i) ≥pM,1(i).

2. Se plantéan las desigualdades para F con respecto a las otras dos clases:

maxm

5x ·(

35

)m≥ x =⇒ m = 3

maxt

3x · 1t + 1

≥ x =⇒ t = 2

Finalmente se debe comparar los clientes que arriendan los primeros 21 días y losque arriendan el mes completo.

maxn

5x ·(

35

)n≥ 3x =⇒ n = 1

Con esto se deduce que los clientes M tienen 4 cupos en total (los 3 que se obtuvieronen la primera comparación y el que le dejan los clientes T), los T tienen 1 cupo (losdos que tenían y el que cedieron) y el resto es para los clientes F.

3. Se plantea el siguiente problema:

Variablesxm, xt, x f cantidad fijada para cada clase.yw

m, ywt , yw

f cantidades vendidas en cada escenario w para cada clase.

Función Objetivo

max ∑w

pw(5x · ywm + 3x · yw

t + x · ywf + 0.2x · (C− yw

m − ywt − yw

f ))

38


Restricciones Cada escenario w tiene una demanda por un tipo de arriendo dwk ,

k = m, t, f .

xm + xt + x f ≤ C

ywm ≤ xm ∀w

ywt ≤ xt ∀w

ywf ≤ x f ∀w

ywm ≤ dw

m ∀wyw

t ≤ dwt ∀w

ywf ≤ dw

f ∀w

ywt , yw

f , ywm, xm, x f , xt ≥ 0

4. Las variables xk son globales para el problema, mientras las ywk dependen del esce-

nario. El problema maestro queda:

max ∑w

pwγw + 0.2xC

s. a xm + xt + x f ≤ C

xm, xt, x f ≥ 0

Y los subproblemas

max 5x · ywm + 3x · yw

t + x · ywf + 0.2x · (−yw

m − ywt − yw

f )

s. a ywm ≤ xm

ywt ≤ xt

ywf ≤ x f

ywm ≤ dw

m

ywt ≤ dw

t

ywf ≤ dw

f

ywt , yw

f , ywm ≥ 0

El dual asociado a cada escenario es:

mın z1 · xm + z2 · xt + z3 · x f + z4 · dwm + z5 · dw

t + z6 · dwf

s. a z1 + z4 ≥ (5x− 0.2x)z2 + z5 ≥ (3x− 0.2x)z3 + z6 ≥ (x− 0.2x)zi ≥ 0

39


5. La solución inicial corresponde a: x∗k = 0 y γw∗ = ∞. El dual para cada subproblema

se simpifica a:

mın z4 · dwm + z5 · dw

t + z6 · dwf

s. a z1 + z4 ≥ (5x− 0.2x)z2 + z5 ≥ (3x− 0.2x)z3 + z6 ≥ (x− 0.2x)zi ≥ 0

El óptimo es simplemente: z∗1z∗2z∗3z∗4z∗5z∗6

=

(5x− 0.2x)(3x− 0.2x)(x− 0.2x)

000

Con un valor γ∗w = 0, menor al obtenido anteriormente por lo que se agregan lasrestricciones:

(5x− 0.2x) · xm + (3x− 0.2x) · xt + (x− 0.2x) · x f ≥ γw ∀w

El problema maestro para esta iteración:

max ∑w

pwγw + 0.2xC

s. a xm + xt + x f ≤ C

(5x− 0.2x) · xm + (3x− 0.2x) · xt + (x− 0.2x) · x f ≥ γw ∀w

xm, xt, x f ≥ 0

Pregunta 5

Considere el siguiente problema estocástico con x ∈ R:

mınx12 x + ∑S

i=1 piQ(x, ξ i)s.t. 0 ≤ x ≤ 10

40


Supondremos que este problema tiene tres escenarios equiprobables con ξ1 = 1, ξ2 =2, y ξ3 = 4.

En el caso en que Q(x, ξ) = |x − ξ|, resuelva este problema usando el algoritmo deBenders. Para esto, indique la forma del subproblema de generación de cortes; escriba elmaestro al comienzo de cada iteración; y los cortes generados. Resuelva los problemaslineales por inspección.

Pregunta 6

Usted debe visitar a n clientes distribuidos geograficamente con K vehiculos. Supongaque todos los vehiculos comienzan localizados en el depot y que viajar entre el cliente iy el cliente j toma tij unidades de tiempo y cuesta cij. Suponga además que cada clientei debe ser visitado en el intervalo de tiempo [ai, bi]. Llegar antes incurre una multa de αpor unidad de tiempo y llegar tarde una multa de β.

1. Escriba el problema de ruteo de vehiculos que minimiza los costos de viaje y multaspor no llegar en la ventana de tiempo acordada.

2. Suponga ahora que los tiempos de viaje son inciertos. De hecho se dispone de Sescenarios de tiempos de viajes correspondientes a lo ocurrido en los ultimos S dias.Es decir existen datos de ts

ij correspondiente al tiempo de viaje entre i y j durante elescenario s. Si suponemos que el escenario s ocurre con probabilidad ps, escriba elmodelo de optimización estocástica de dos etapas que minimiza el costo esperadode la ruta. Suponga que la ruta se decide en la primera etapa y que los costos deviolar las ventanas de tiempo se ajustan en la segunda etapa.

3. Describa el método de Benders’ para resolver el problema estocástico descrito arri-ba. Para eso:

a) Indique cual es el subproblema de generación de restricciones, y cuando estegenera restricciones de factibilidad y de optimalidad.

b) Escriba el problema maestro.

4. Considere ahora el caso con ventanas de tiempo duras (esto es, α = β = ∞). ¿Quémodificaciones sufren los cortes generados por el método de Benders’.

Solución

1. Variables:

xijk ={

1 si se va del cliente i a j0 si no

wi = tiempo de llegada al cliente i

41


ei = unidades de tiempo de anticipación en la llegada a i

li = unidades de tiempo de atraso en la llegada a i

Restricciones:

∑j

xoj ≤ K

∑i

xij = ∑l

xjl ∀j

∑j

xij = 1 ∀i 6= 0

wi ≥ wj + tij −M(1− xij) ∀i, j

ai ≤ wi + ei ∀iwi ≤ bi + li ∀iwi, li, ei ≥ 0 ∀ixij ∈ {0, 1}

Función Objetivo

∑ij

cijxij + ∑i

αei + βli

2. Variables: Ahora las variables wsi , es

i y lsi dependen del escenario s ∈ S.

Restricciones: Las restricciones que solo se relacionan con xij se mantienen iguales,las que cambian son

wsi ≥ ws

j + tsij −M(1− xij) ∀i, j, s

ai ≤ wsi + es

i ∀iws

i ≤ bi + lsi ∀i

wsi , ls

i , esi ≥ 0 ∀i

Función Objetivo

mın ∑ijk

cijxij + ∑s

ps

(∑

iαes

i + βlsi

)

3. a) Planteamos un subproblema para cada escenario s

42


mın ∑i

αesi + βls

i

wsi ≥ ws

j + tsij −M(1− x∗ij) ∀i, j

ai ≤ wsi + es

i ∀iws

i ≤ bi + lsi ∀i

wsi , ls

i , esi ≥ 0 ∀i

Su dual correspondiente:

max ∑ij

zij

(M(1− x∗ij)− ts

ij

)+ ∑

iλiai − σibi

λi ≤ α ∀iσi ≤ β ∀i

∑j

zij −∑k

zki + λi − σi ≤ 0 ∀i

σi, λi ≥ 0 ∀izij ≤ 0 ∀i, j

Los cortes de factibilidad entonces son:

γs ≥∑ij


ij

)z∗ij −∑

ibiσ∗i + ∑

iaiλ∗i

donde (z∗ij, σ∗i , λ∗i ) ∀i, es un punto extremo del problema dual.

Para cortes el factibilidad se debe cumplir:

0 ≥∑ij


ij

)p∗ij −∑

ibi p∗i + ∑

iair∗i

donde (p∗ij, q∗i , r∗i ) ∀i es un rayo extremo.

b) El problema maestro es:

43


mın ∑ij

cijxij + ∑s

psγs

∑j

xoj ≤ K

∑i

xij = ∑l

xjl ∀j

∑j

xij = 1 ∀i 6= 0

γs ≥∑ij


ij

)z∗ij −∑

ibiσ∗i + ∑

iaiλ∗i ∀i

0 ≥∑ij


ij

)p∗ij −∑

ibi p∗i + ∑

iair∗i ∀i

xij ∈ {1, 0} ∀i, j

4. Como α = β = ∞ el problema es:

mın ∑ij

cijxij

∑j

xoj ≤ K

∑i

xij = ∑l

xjl ∀j

∑j

xij = 1 ∀i 6= 0

wsi + ts

ij − wj ≤ M(1− xij) ∀i, j

ai ≤ wi ≤ bi ∀ixij ∈ {1, 0} ∀i, j

Por lo tanto, no hay costo futuro por escenarios. El método de Bender’s solo gener-ará cortes de factibilidad.

El subproblema queda:

max ∑ij

zij


ij

)+ ∑

iλiai − σibi

∑j

zij −∑k

zki + λi − σi ≤ 0 ∀i

σi, λi ≥ 0 ∀izij ≤ 0 ∀i, j

44


problema que solo tendrá como valor óptimo 0, o +∞, por lo que solo generarácortes de factibilidad.

45


5. Generación de columnas

Considere un problema en forma estándar con muchas variables, es decir, con n >>m,

mın c′xAx = bx ≥ 0

En general, en el óptimo, el número de variables básica es, a lo más al número derestricciones, lo que deja una gran cantidad de variables no básicas que no participan dela solución óptima y, por lo tanto, no necesitan ser consideradas explícitamente. La ideade Generación de columnas es solo trabajar con la cantidad mínima de variables necesariaspara hallar la solución óptima, incorporando una a una las que presenten costos reducidosnegativos, dejando implícitas las demás variables no básicas.

Recordando que el problema se puede descomponer en variables básicas básicas y nobásicas, reescribimos el problema,

mın c′Bxb + c′Nxn

ABxB + Anxn = bx ≥ 0

despejando las variables básicas de la segunda ecuación se obtiene,

xb = A−1b b−A−1

B ANxN

Reemplanzando en la primera ecuación el problema depende solo de las variables nobásicas

mın c′BA−1B b + (c′N − c′BA−1

B AN)xn = c′BA−1B b + mın(c′N − c′BA−1

B AN)xN

= y′b + mın(c′N − y′AN)xN

donde y′ = cBA−1B corresponde al valor de las variables duales en el óptimo. ¯cN =

c′N − y′AN los costos reducidos asociados a las variables no básicas.De la última ecuación se puede apreciar que si existe algún costo reducido negativo,

el valor de la función objetivo se puede reducir, aumentando la variable correspondiente,es decir, haciéndola entrar a la base.

El algoritmo de generación de columnas elige la variable no básica con menor costoreducido, resolviendo el siguiente problema de optimización, conocido como Subproblema

mınj

cj − yAj

Luego la variable (o columna) encontrada entra en el problema Maestro y se vuelve aresolver.

46


Problema maestromın c′xs.a. Ax ≥ b

x ≥ 0

Generador de columnasmax cj − yAj

s.a. wAj ≤Wa ∈ N0

Variables Dualesyi

ColumnasAj

Figura 5: Iteración generación de columnas

Cutting stock problemSe tienen trozos de metal de largo L y existe una demanda por piezas de ciertos

tamaños determinados li. El problema consiste en determinar cómo cortar las piezas demodo que el desperdicio de material sea mínimo.

La formulación del problema maestro es la siguiente

mın ∑j

xj

∑j

aijxj ≥ di ∀i

xj ∈ N0

donde xj es la cantidad de veces que se usa el patrón j, aij es la cantidad de piezas de

tamaño li en el patrón j y di es la demanda por piezas de tamaño li.El subproblema debe generar un patrón factible con el mínimo costo reducido. Si lla-

mamos yi al costo dual óptimo asociado a la i-ésima restricción del problema maestro setiene:

mın 1−∑i

yiaij

∑i

liaij ≤ L

aij ∈ N0

o equivalentemente

max ∑i

yiaij

∑i

liaij ≤ L

aij ∈ N0

47


donde el costo reducio será 1−∑i yiaij.

EjemploSe tienen barras de metal de largo 218cm y se requieren las siguientes piezas:

Tamaño Demanda81cm 4470cm 368cm 48

Cuadro 8: Tamaño y cantidad demandada

Iteración 1Se comienza con patrones que permitan resolver el problema. Utilizaremos unos que

solo consideran una pieza por barra. Con esto el problema maestro queda

mın x1 + x2 + x3

x1 ≥ 44x2 ≥ 3x3 ≥ 48x1, x2, x3 ≥ 0

El dual de este problema

max 44y1 + 3y2 + 48y3

y1 ≤ 1y2 ≤ 1y3 ≤ 1y1, y2, y3 ≥ 0

Al resolver este problema se obtiene que y = (1, 1, 1). Luego el subproblema queda:

max a1 + a2 + a3

81a1 + 70a2 + 68a3 ≤ 218a1, a2, a3 ∈ N0

donde el nuevo patron está dado por Aj = (0, 0, 3) y su costo reducido es 1− (a∗1 + a∗2 +a∗3) = −2 < 0.

Iteración 2

48


Se agrega el nuevo patrón al problema maestro

mın x1 + x2 + x3 + x4

x1 ≥ 44x2 ≥ 3x3 + 3x4 ≥ 48x1, x2, x3, x4 ≥ 0


max 44y1 + 3y2 + 48y3

y1 ≤ 1y2 ≤ 1y3 ≤ 13y3 ≤ 1y1, y2, y3 ≥ 0

Con estas modificaciones se obtiene que y = (1, 1, 13). Luego el subproblema queda:

max a1 + a2 +13

a3

81a1 + 70a2 + 68a3 ≤ 218a1, a2, a3 ∈ N0

El nuevo patron será Aj = (0, 3, 0) y su costo reducido es 1− (a∗1 + a∗2 +13 a∗3) = −2 < 0.

Iteración 3

mın x1 + x2 + x3 + x4 + x5

x1 ≥ 44x2 + 3x5 ≥ 3x3 + 3x4 ≥ 48x1, x2, x3, x4, x5 ≥ 0


max 44y1 + 3y2 + 48y3

y1 ≤ 1y2 ≤ 1y3 ≤ 13y3 ≤ 13y2 ≤ 1y1, y2, y3 ≥ 0

49


Se obtiene y = (1, 13 , 1

3). Luego el subproblema queda:

max a1 +13

a2 +13

a3

81a1 + 70a2 + 68a3 ≤ 218a1, a2, a3 ∈ N0

El nuevo patrón será Aj = (2, 0, 0) y su costo reducido es 1− (a∗1 +13 a∗2 +

13 a∗3) = −1 <

0.

Iteración 4

mın x1 + x2 + x3 + x4 + x5 + x6

x1 + 2x6 ≥ 44x2 + 3x5 ≥ 3x3 + 3x4 ≥ 48x1, x2, x3, x4, x5, x6 ≥ 0


max 44y1 + 3y2 + 48y3

y1 ≤ 1y2 ≤ 1y3 ≤ 13y3 ≤ 13y2 ≤ 12y1 ≤ 1y1, y2, y3 ≥ 0

Se obtiene y = (12 , 1

3 , 13). Luego el subproblema queda:

max12

a1 +13

a2 +13

a3

81a1 + 70a2 + 68a3 ≤ 218a1, a2, a3 ∈ N0

El nuevo patrón será Aj = (1, 0, 2) y su costo reducido es 1− (12 a∗1 +

13 a∗2 +

13 a∗3) =

−16 < 0.

Se debe continuar hasta obtener un costo reducido positivo.

50


Pregunta 1

Ud. está a cargo de la logística de la repartición de las pruebas de la PSU. Supongaque cada día de la PSU se reparten las pruebas de ese dia entre las 0 y las T horas de lamañana del mismo día. Dado que se opera con un sistema de arriendo de vehículos parala repartición de los enunciados, se desea realizar la labor con el mínimo de éstos. Por lodemás, la capacidad de cada vehículo es de s [pruebas], los que saldrán desde un únicopunto (nodo 0) hacia el conjunto de centros C donde se rinde la prueba. Cada uno de estoscentros posee una demanda igual a dc [pruebas] (dc ≤ s ∀c ∈ C), los cuales deberán seratendidos dentro de una ventana de tiempo entre lc y uc. Considere que el tiempo de viajede un centro a otro es de tij, con i, j ∈ C∪ {0}, y que el tiempo en descargar las pruebas encada centro es αdc [horas] (las pruebas deben ser descargadas antes que uc en cada centroc y todas deben haber sido descargadas antes del tiempo T).

1. Plantee el problema de optimización que represente este problema de ruteo de ve-hículos. Suponga que la empresa de arriendo de vehículos dispone de un set K deéstos.

El resto de esta pregunta considera el uso de generación de columnas para resolver larelajación lineal de una reformulación de este problema. Considere la siguiente versiónde este problema de VRP en términos de patrones/rutas por vehículo (conocida como elset-covering formulation):

mınp∈P ∑p∈P zps.t. ∑p∈P apijzp = 1 ∀i ∈ C

zp ∈ {0, 1} ∀p ∈ P

Donde P el conjunto de todos los patrones posibles y api vale 1 si patrón p pasa por elnodo i.

2. ¿Qué representa un patrón en este problema? ¿Qué variables o coeficientes son losque poseen la información de dicho patrón?

3. ¿Cómo inicializaría la resolución del problema?

4. Considere ahora el problema maestro relajado (zp ≥ 0 y solo se consideran I ⊂ Ppatrones). Suponga que la solución primal-dual de este problema maestro relajadoes (z∗, π∗). Escriba la función objetivo del subproblema de generación de columnas.

5. Escriba en detalle el problema maestro y el subproblema de generación de columnaspara este problema.

51


6. Una vez resuelto el subproblema, complete una iteración del método de generaciónde columnas (hasta antes de resolver el maestro nuevamente). ¿Qué cotas se ob-tienen del valor óptimo en una iteración?

Solución

1. Variables de decisión:

xijk vale 1 si el vehículo k va desde el cliente i al j.

wi, tiempo en el cual se llega al centro i.

mın ∑j,k

x0jk

s.t. ∑i∈C0,k

xijk = 1 ∀j ∈ C

∑j∈C0,k

xijk = 1 ∀i ∈ C

∑i∈C0

xijk = ∑i∈C0

xjik ∀j ∈ C, k ∈ K

∑i∈C0

xijkdj ≤ s ∀j ∈ C, k ∈ K

wj ≥ wi + tij + αdi + M

(1− ∑

k∈Kxijk

)∀i ∈ C0, j ∈ C

li ≤ wi ≤ ui − αdi ∀i ∈ Cwi + αdi ≤ T ∀i ∈ Cxijk ∈ {0, 1} ∀i, j ∈ C0, k ∈ K

wi ≥ 0 ∀i ∈ C0

donde C0 = C ∪ {0}.

2. En este caso un patrón representa una ruta en la cual se visita a un conjunto decentros, los cuales serán atendidos en un viaje de un vehículo. Un patrón vienedefinido por los coeficientes de la matriz del problema maestro, en particular unpatrón en especifico corresponderá a una columna de coeficientes en especifico dellado izquierdo del problema maestro.

3. Partiría con un conjunto de patrones fáciles de encontrar, como por ejemplo el con-junto de de patrones en donde cada uno corresponde a ir a un cliente en particulary volver al nodo 0. Esto sirve, pues así tengo claramente una solución factible delproblema maestro.

52


4. Debemos tener una expresión para los costos reducidos de las variables no-básicas:

cj = cj − π∗Ty = 1− π∗Ty

Luego, la función objetivo del subproblema es maximizar π∗Ty.

5. Luego el subproblema queda:

mın π∗Ty

s.t. ∑i∈C0

yij ≤ 1 j ∈ C

∑j∈C0

yij ≤ 1 ∀i ∈ C

∑i∈C0

yij = ∑i∈C0

yji ∀j ∈ C

∑i∈C0

yijdj ≤ s ∀j ∈ C

wj ≥ wi + tij + αdi + M(1− yij

)∀i ∈ C0, j ∈ C

li ≤ wi ≤ ui − αdi ∀i ∈ Cwi + αdi ≤ T ∀i ∈ Cyij ∈ {0, 1} ∀i, j ∈ C0

wi ≥ 0 ∀i ∈ C0

6. Sea w∗ el valor óptimo obtenido de la función objetivo del subproblema, luego, si1−w∗ ≥ 0, entonces terminamos de iterar dado que la última solución al problemamaestro es exactamente el óptimo. En caso contrario, si 1− w∗ < 0, ingresamos lanueva variable (y) al problema maestro como una nueva columna de parámetros,para la nueva variable que corresponde entonces a un nuevo patrón p, luego I ←I ∪ {p}.

Pregunta 2

Considere el problema de satisfacer la demanda de una serie de componentes al mín-imo costo, en que los componentes deben ser empaquetados en bins o containrs para suenvío, más conocido en la literatura como binpacking.

Específicamente, considere que se tienen tres tipos de bins, los que se caracterizan porsu color (Rojo, Azul o Verde), tamaño y tipos de items que pueden almacenar. El costo porutilizar cada bin depende del color, siendo para los Rojos de $10, para los Azules de $20y para los verdes de $30. Para determinar los componentes que pueden ser almacenadosen cada bin, así como el tamaño de éste, se debe seguir el siguiente procedimiento. Sea

53


una lista de N componentes ordenada según sus pesos, el 40 % más pequeño de la lista,puede ser almacenado en los bins de color rojo, el 40 % más grande de la lista puedeser almacenado en los bins de color Verde. Mientras que el 60 % del centro puede seralmacenado en los bins de color Azul. El tamaño de cada bin se determina como n-veces eltamaño del componente más pesado que puede almacenar dicho bin, con n dependiendode la cantidad de componentes N.

Por otra parte, para asegurar un mínimo de variedad en cada bin, se ha impuesto quea lo más se pueden incluir 15 componentes del mismo tipo en los bins Rojos, 10 en losAzules y 5 en los Verdes.

1. Plantee el modelo de programación lineal mixto.

2. Plantee el modelo de generación de columnas. En particular escriba el problemamaestro y el subproblema.

Solución

1. Variables:

xkij =

{1 Si incluyo una unidad del componente i ∈ N en el k− esimo bin de tipo j ∈ B = R ∪ A ∪V0 Si no

wkj =

{1 Si uso k− esimo bin de tipo j ∈ B = R ∪ A ∪V0 Si no

ykij = Unidades de componente i ∈ N incluídas en k− esimo bin de tipo j ∈ B =

R ∪ A ∪V

Para definir el número máximo de bins de cada tipo a utilizar, k, se estimó que éste esmenor al peso de la demanda total de productos que pueden ser almacenado en esetipo de contenedor dividido la capacidad de éste, es decir, k = maxj

(∑i Qij·Di·pi

capj

).

Restricciones:

xkij ≤ Qij · wk

j ∀ i, j, k

∑i

ykij · pi ≤ capj · wk

j ∀ j, k

∑j,k

ykij ≥ Di ∀ i

ykij ≤ vj · xk

ij ∀ i, j, k

ykij, ∈ Z+

0 ∀ i, j, k

xkij, wk

j ,∈ {0, 1} ∀ i, j, k

54


Función Objetivo:

mın ∑j,k

wkj · cj

2. Problema Maestro

Para este problema se define la variable xkj que corresponde al número de bins de

tipo j ∈ B = R ∪ A ∪V que son rellenados con el patrón k.

mın ∑j,k

xkj · cj

∑j,k

xkj ak

ij ≥ Di ∀ i

xkj ∈N+

0 ∀ j, k

Subproblema

Por su parte, para el subproblema se define la variable akij que corresponde al número

de unidades de componente i ∈ N que pueden ser incluídas en un bin de tipoj ∈ B = R ∪ A ∪V a través del patrón k. Además, se consideran tres subproblemas,uno para cada tipo de bin j, de tal forma de determinar el patrón óptimo para cadatipo de compartimento. Considerando las variables duales del problema maestro,yi, el problema queda formulado de la siguiente forma:

max ∑i

yi · akij

∑i

akij · pi ≤ capj ∀ j, k

akij ≤ Qij · vij ∀ i, j, k

akij ∈N+

0 ∀ i, j, k

Pregunta 4

Una pequeña empresa de transportes posee un conjunto K de camiones con capaci-dades de carga CAPk, costos dijos CFk y costos variables CVk por kilómetros recorrido. Setiene un conjunto E de entregas a realizar dentro de las ventanas de tiempo [t1

d, t2d] ∀d ∈ E

y un conjunto R de encargos a recoger dentro de la ventana de tiempo [t1d, t2

d] ∀d ∈ R1.

1Para todo nodo de regida i ∈ R llame n + i ∈ E al correspondiente nodo de entrega

55


Para cada demanda d ∈ D = E ∪ R existe un peso wd, un beneficio bd y un tiempo deservicio TSd asociados. Las distancias y los tiempos de viaje están dados por distij y Tij,∀i, j ∈ D, respectivamente.

1. Formule el problema de satisfacer la demanda a costo mínimo, con una cantidadpolinomial de variables.Hint 1: Si le es útil, defina los nodos ficticios Ok y Dk como el nodo inicial y final delcamión k.Hint 2: No olvide considerar el tiempo de llegada y la carga con la que sale uncamión de cada nodo.

2. ¿Cómo cambia el modelo anterior si el objetivo es maximizar beneficios asumiendoque los clientes son opcionales?

3. Formule un modelo de Generación de Columnas para el problema de minimizaciónde costos. Específicamente, defina cuáles serán los patrones para este problema enparticular y escriba el Problema Maestro y el Subproblema que utilizaría.

Solución

1. Variables:

yk={

1 Uso el camión k0 Si no

xkij={

1 Si camión k va de i a j0 Si no

ti,k=Tiempo de llegada del camión k a i

pki =Peso de k cuando llega a i

zki =Distancia recorrida por camión k

Restricciones:

56


∑i,k

xkij = 1 ∀j

yk = ∑j

xkOk j = ∑

ixk

iDk∀k

∑i

xkij = ∑

jxk

j(i+n) ∀k, j

pki + wj −M(1− xk

ij) ≤ pkj ∀i, j, k

ti,k + Tij + TSj −M(1− xkij) ≤ tj,k ∀i, j, k

zki + distij −M(1− xk

ij) ≤ zkj ∀i, j, k

pki ≤ CAPk ∀k, i

ti,k ≤ t2i ∑

jxk

ij ∀k

ti,k ≥ t1i ∑

jxk

ij ∀k

Función objetivo:

max ∑i,j,k

xkijbj −∑

kCFkyk −∑

i,kCVkzk

i

2. En ese caso el único cambio que se debe hacer es quitar la restricción:

∑i,k

xkij = 1 ∀j

3.

57


6. Heurísticas y ruteo

Heurísticas de construcción ruteo

Nearest Neighbor Consiste en secuencialmente buscar el nodo que se encuentramás cerca del nodo que se está analizando. Los pasos son:

1. Elegir un nodo de partida al azar

2. Unir el nodo más cercano al último elegido hasta que se acaben

3. Unir el último nodo con el primero

Para cada nodo es necesario revisar todos los nodos restantes, por lo cual este algo-ritmo tiene una complejidad O(n2).

Multiple Fragment Este algoritmo, a diferencia de anterior, no va arramando la rutade forma ordenada sino que va juntando las nodos con arcos más baratos y los vauniendo, hasta que ya no queden nodos sin unir. Los pasos son:

1. Buscar el arco más barato que no se haya usado

2. Añadir solo si no forma un ciclo

Nearest Addition

1. Elegir un nodo de partida al azar y su nodo más cercano

2. Formar un tour con los nodos agregados

3. Añadir el nodo más cercano al tour

Farthest Addition

1. Elegir un nodo de partida al azar y su nodo más lejano

2. Formar un tour con los nodos agregados

3. Añadir el nodo más lejano al tour

58


Nearest neighbor Farthest Addition

Figura 6: Ejemplo heurísticas de contrucción en ruteo

Heurísticas de mejoramiento ruteo

Explique las siguientes heurísticas de mejoramiento:

2-opt: Intercambiar dos arcos tales que se reduzca el costo total.

Figura 7: 2-opt

3-opt: Intercambiar tres arcos tales que se reduzca el costo.

Figura 8: 3-opt

59


Exchange: Intercambiar vecinos.

Figura 9: Exchange

Pregunta 1Considere un problema de un vendedor viajero que debe visitar ciudades 1,...,n, partien-do de la ciudad 0. El viaje entre la ciudad i y j tiene un costo de cij y demora un tiempotij > 0. Suponga además que debe visitar cada ciudad i ∈ {1, ..., n} antes de una fechalímite li.

1. Formule el problema de vendedor viajero que minimice el costo de viaje y satisfagatodas las restricciones de tiempo.

2. Muestre por qué se pueden eliminar subtours en este problema sin utilizar un númeroexponencial de restricciones.

3. Explique cómo se debe modificar el algoritmo de 2-Opt para el problema del TSPcon restricciones de tiempo. Para esto, asuma que tiene el orden en que se visitanlas ciudades en un arreglo pos[i] con i = 1, ..., n, donde pos[i] es la i-ésima ciudadvisitada en el tour y que para dos ciudades i, j tiene los costos cij y tiempos tij entrei y j. (Asuma por simplicidad que ambos son simétricos i.e. cij = cji y tij = tji).

Solución

1.mın ∑

ijcijxij

s.t.n

∑j=0

xij = 1 i = 0, ..., n

n

∑j=0

xij =n

∑k=0

xki i = 0, ..., n

wi + tij − wj ≤ M(1− xij) i, j = 0, ..., n

wi ≤ li i = 1, ..., n

60


2. Suponga que tiene un subtour que visita los nodos i1, i2, ..., in, entonces el tiempo enque visitamos cada uno de estos nodos satisface

win ≥ win−1 + tin−1in ≥ win−2 + tin−2in−1 + tin−1in ≥ wi1 +n−1

∑j=1

tijij+1

Como luego va de in a i1 también satisface wi1 ≥ win + tini1 , estas dos desigualdadescon el hecho que tij > 0 nos muestra que win > win , una contradicción.

3. En el algoritmo 2-Opt el paso que se ve afectado es determinar qué rutas pertenecena la vecindad de una ruta dada. Para eso, además de recostruir la ruta, se debeverificar si el largo de la ruta es menor a li para todos los nodos que cambian sutiempo de llegada.

Dada una ruta descrita por el arreglo pos[i], si eliminamos los arcos en la l y k, conl < k de la ruta tenemos que la ruta reconstituida desde pos[0] hasta pos[l] es lamisma. Pero luego hay que verificar que wj ≤ lj para todo j en {pos[j]}n

j=l.

Si wi es la variable que contiene el tiempo en que se llega a pos[i], entonces hayque verificar que

wl + tpos[l]pos[k] +k−s

∑h=k

tpos[h]pos[h−1] ≤ lpos[k−s−1] para k− s− 1 ∈ 0, ..., k− l

y también verificar que

wj + tpos[l]pos[k] + tpos[l+1]pos[k+1] − tpos[l]pos[l+1] − tpos[k]pos[k+1] ≤ lj j ∈ k + 1, ..., n

El resto de la rutina es idéntica.

Pregunta 2

Considere un problema de vendedor viajero en n ciudades, partiendo de la ciudad 0,y donde el costo de ir de i a j es cij. Este problema se puede interpretar como schedulingde n trabajos que estan inicialmente todos disponibles en una máquina sin preemptionni deadlines. Para esto debe considerar que todos los trabajos se demoran un tiempoconstante en la máquina pero existe un tiempo de set up al hacer el trabajo j después deli igual a cij.

1. Para este problema de scheduling, describa la heurística Shortest Remaining Process-ing Time (SRPT). ¿A qué tipo de heurística corresponde esta para el problema devendedor viajero original?

61


2. Explique cómo puede utilizar la relajación con preemption de este problema descheduling para obtener una solución factible. ¿Qué tipo de garantías tiene de estasolución?

Solución

1. La heurística SRPT escoje el trabajo que tiene el tiempo de ejecución más corto yhace ese trabajo. Como no hay preemption, solo decide el sgte trabajo una vez queel trabajo anterior ha terminado.

Como no hay release ni due dates, en cada momento están disponibles todos lostrabajos que no han sido realizados, y si el último trabajo que se hizo fue el trabajok, entonces se ejecuta a continuación el trabajo j que tenga el menor ckj entre los jque falta por ejecutar. Al inicio se escoje el trabajo j que tenga el menor c0j.

Esto corresponde a una heurística de vecino más próximo (NN) En cada etapa de laruta visita a continuación al trabajo que se encuentra más cerca del punto actual. Enextenso, visita al j que no ha sido visitado que tiene el menor ckj.

2. Dado que el problema no tiene release ni due dates, no existe ningún motivo parainterrumpir un trabajo. Si un trabajo tenía el menor tiempo de procesamiento y secomienza a ejecutar, durante toda su ejecución continua siendo el trabajo con menortiempo de servicio. Note que asumo que el tiempo de servicio de un trabajo dependedel último trabajo que ha sido completado. Si el último trabajo completo fue i yluego trabajo en j. Mientras quede algo de j los tiempos de procesamiento de losotros trabajos continúa siendo cik ≥ cij. Pero cuando termina j entonces los tiemposde los otros trabajos pasan a ser cjk que pueden estar ordenados differente.

Entonces el problema con preemption obtiene la misma respuesta entera que elproblema sin preemption. Es decir es factible para el problema sin preemption.

Sabemos que la solución sin preemption es mayor el valor óptimo del schedule.

Como esta solución corresponde a la solución que entrega la heurística de vecinomás próximo en el TSP, podemos usar la garantía que nos da esa heurística: I.e.sabemos que NN ≤ 1/2(log2(n) + 1)OPT. para problemas en los que los valores cijsean una distancia euclidiana.

Pregunta 3

Considere un grafo dirigido G = (N, A) con n nodos y m arcos. El siguiente algoritmorealiza una búsqueda en profundidad en el grafo partiendo del nodo 1.

62


Algorithm 2: BUSQUEDA EN PROFUNDIDAD1 VISITA(i)=0; PRED(i)=NULL ∀i ∈ N2 VISITA(1)=1; PRED(1)=0;3 LISTA={1}4 while LISTA 6= ∅ do5 Sea i el último nodo puesto en LISTA6 if i tiene un arco (i, j) ∈ A tal que VISITA(j)=0 then7 VISITA(j)=1; PRED(j)=i;8 LISTA=LISTA∪{j};9 else

10 LISTA=LISTA\{i};

1. Explique que es el problema de búsqueda en profundiad en un grafo, que es unainstancia de este problema y cual es el tamaño de una instancia.

2. Encuentre la menor cota del número de operaciones que realiza el Algoritmo 1 enel peor caso. Considere que todas las operaciones matemáticas y de comparación,asignación, lectura, demoran lo mismo. Utilize la notación O().

Solución

1. El problema encuentra todos los nodos que pueden ser accesados de 1. Lo de pro-fundida se refiere a que después que encuentra un decendiente, digamos j del nodoactual, el algoritmo busca a un decendiente de j antes de buscar a nodos al mismonivel que j. Una instancia es un grafo dado. El tamaño de una instancia es el númerode nodos y el número de arcos, n y m respectivamente.

2. La inicializacion es O(n). El número de iteraciones es a lo más 2n ya que en cadaiteración se agrega o retira un nodo a LISTA y cada nodo es agregado una sola vez(cuando se revisa el arco (i, j) y VISITA(j)=0). Pero el trabajo por iteración puedecambiar ya que encontrar un arco (i, j) tal que VISITA(j)=0 puede requerir mirar to-dos los arcos de i. A lo largo del algoritmo, revisamos cada arco una sola vez (imag-inese que los borra si los reviso en una iteración anterior). PasamosO(m) revisandoarcos y O(n) iteraciones mas para borrar nodos de LISTA. Con esto tenemos que laparte principal del algoritmo demora O(n + m) ya que encontrar el último nodo enLISTA y las asignaciones y evaluaciones de condiciones son a lo maás un númeroconstante en cada iteración (= 6 por iteración). Total del algoritmo O(n + m + n) =O(n + m) =O(m).

Pregunta 4

63


Usted es dueño de un canal, donde debe decidir la programación dentro de los espa-cios publicitarios. Considere que tiene una oferta de un conjunto de publicidades I ={1, . . . , I}, las cuales se deben asignar a un horario h ∈ H = {1, . . . , H}. De esta for-ma, una publicidad i pagará un precio pih si es asignada en el horario h. Es obligaciónaceptar a todas las ofertas publicitarias. Además cada publicidad tiene un largo li, comotambién cada horario es de largo L, de modo que el conjunto de publicidades asignado aun horario no debe exceder L. Por otro lado, hay un conjunto C de conjuntos de a parespublicitarios que no pueden estar en un mismo horario, por ejemplo, si C = {{1, 2}},entonces en cualquier horario en particular, puedo asignar a lo más una sola de estas dospublicidades. LlameAh el conjunto de publicidades asignadas en el horario h, ∀h ∈ H, locual es lo que Ud. como dueño del canal debe decidir. Para esto se pide lo siguiente:

a) Plantee una heurística constructiva de una solución factible, explicando sus clara-mente pasos. Dicha solución factible debe ser “buena” en la lógica de la construcciónde la heurística, en el sentido de que no sea cualquier solución factible.

b) Explique una heurística de mejoramiento de la solución obtenida de la parte a).

c) Aplique su heurística constructiva explicada en la parte a) para hallar una soluciónfactible al problema para la siguiente instancia: H = {1, 2, 3}, I = {a, b, c, d}, C =

{{a, d}}, [pih] =

20 60 540 80 2010 50 270 30 10

, la = 3, lb = 4, lc = 2, ld = 3 y L = 6.

d) Explique que enfoque recomendaría usar y por qué, entre generación de restric-ciones o generación de columnas para resolver el problema.

Solución

a) Heurística constructiva, tratamos de generar de alguna manera una solución factiblepara el problema que sea buena en lo posible (y no cualquier cosa factible al azar).Por ejemplo la siguiente heurística para construir una solución:

SeaR en conjunto de pares publicidad-horario donde ya no se busca el máximo pih.

64


Algorithm 3: Heurística constructivaData:H, I , C, P

1 Inicializar T = I , Ah = φ ∀h ∈ H,R = φ;2 while T 6= φ do3 Tomar i ∈ T y h ∈ H tal que (i, h) = arg maxj∈T ,k∈H,(j,k) 6∈R pjk;4 if li + ∑j∈Ah

lj ≤ L and ∀k ∈ Ah i ∪ k 6∈ C then5 Ah ← Ah ∪ {i} Asigno publicidad i en horario h ;6 T ← T \ {i};7 else8 R ← R∪ {(i, h)}

9 return Ah ∀h ∈ H ;

En palabras:

1. Considero un conjunto de todas las publicidades inicialmente T .

2. Tomo la publicidad en T tal que tenga el máximo precio a pagar dentro laspublicidades en T , sea la publicidad i en el horario h.

3. Asigno la publicidad i en el horario h solo si es que ésta cabe en este horario,y además si es que no hay publicidades ya asignadas en este horario que esténprohibidas con la que estamos agregando. En caso de asignar, retiro del con-junto T la publicidad i. En caso de no asignar, entonces descartar asignar lapublicidad i en el horario h en adelante.

4. Si todavía quedan publicidades en T , volver al paso 2.

También es posible otras heurísticas, que deben estar explicadas claramente paso apaso, en donde se busque una buena solución y no cualquier cosa.

b) Algunas de las heurísticas de mejoramiento que se pueden mencionar:

• Mejoras 2− opt (ó k − opt) donde considero los conjuntos de 2 (ó k) publici-dades asignadas, y ver la mejor reasignación posible entre todas las combina-ciones.

• Swaps o intercambios de a dos publicidades entre sí, realizando el cambio enla medida que se mejore.

• Aplicar una búsqueda local de mejoramiento, de la siguiente forma:

1. Partir con una solución factible s.2. Examinar soluciones s′ en una vecindad N(s) de s (s 6∈ N(s)).3. Moverse a la mejor solución s′ ∈ N(s).4. s = s′ y registrar si s es lo mejor obtenido, ir a 2.

65


En este caso, se debe definir claramente la vecindad, la cual puede ser porejemplo, las soluciones con un intercambio de una sola publicidad, o de k pub-licidades, o cambios en publicidades que estén en k horarios.

• Algún método de búsqueda local tipo TABU, en donde consideramos la listacomo que guarde las publicidades asignadas en las ultimas iteraciones. O bientambién hacer una búsqueda local con simulated anneahling.

c)

Iteración T (i, h) >Agrego? A1 A2 A3 R1 {a, b, c, d} (b, 2) Sí φ {b} φ φ2 {a, c, d} (d, 1) Sí {d} {b} φ φ3 {a, c} (a, 2) No {d} {b} φ {(a, 2)}4 {a, c} (c, 2) Sí {d} {b, c} φ {(a, 2)}5 {a} (a, 1) No {d} {b, c} φ {(a, 2), (a, 1)}6 {a} (a, 3) Sí {d} {b, c} {a} {(a, 2), (a, 1)}7 φ

En palabras, cada iteración:

• Iteración 1, no tengo ninguna publicidad asignada, es decir T = {a, b, c, d},luego veo la que al asignar me de mayores utilidades, es decir, la publicidad ben el horario 2, pues pb2 = 80 es el máximo pago. Hago la asignación pues esposible hacerla. Luego A2 = {b}.• Iteración 2, T = {a, c, d}, el máximo pago es pd1 = 70, y asigno publicidad d a

horario 1. Luego A1 = {d}.• Iteración 3, T = {a, c}, el máximo pago es pa2 = 60, pero no puedo asignar la

publicidad a al horario 2, pues no caben en el horario 2 las publicidades a y bdado que sus largos suman 7, lo que supera a L = 6.

• Iteración 4, T = {a, c}, el máximo pago es pc2 = 50, y asigno publicidad c ahorario 2. Luego A2 = {b, c}.• Iteración 5, T = {a}, el máximo pago es pa1 = 20, pero no puedo asignar la

publicidad a al horario 1, pues no es compatible con la publicidad d.

• Iteración 6, T = {a}, el máximo pago es pa3 = 5, y asigno publicidad a ahorario 3. Luego A3 = {a}.• Termino, pues T = φ.

En este caso, la función objetivo de la solución obtenida es: 5 + 80 + 50 + 70 = 205.

d) Claramente este puede ser abordado mediante generación de columnas, pues sepueden generar patrones de asignaciones de publicidades en horarios, por ejemplo,un patrón podría ser el conjunto de publicidades que se considera para asignar enalgún horario en particular. De modo que habrían muchas variables, las cuales seirán agregando de a poco.

66


Pregunta 5

Considere el problema de rutear K vehículos de capacidad Q para satisfacer clientes{1, ..., n} cada uno con demanda di. Suponga además que los vehículos parten y vuelvena un depósito, el punto 0, adonde hay un inventario I y que el costo de viaje entre lospuntos i y j está dado por cij. Note que el inventario total I y las capacidades de losvehículos Q pueden hacer imposible satisfacer toda la demanda. Se desea resolver esteproblema de ruteo de vehículos de forma que se minimice la demanda insatisfecha de laforma más eficiente posible. Suponga que todos los clientes son visitados por exáctamenteun vehículo. Para balancear estos dos obejtivos se considera α ≥ 0 y la función objetivo:

Demanda insatisfecha + α(Costo de rutas)

1. Escriba un problema de programación entero mixto que represente este problemade ruteo de vehículos. Explique las variables que utiliza y las restricciones

2. ¿Es posible que toda la demanda sea satisfecha? Utilice los parámetros del problemapara encontrar cotas a la demanda insatisfecha.

3. Explique como obtener una cota a este problema en tiempo polinomial.

4. ¿Cómo podría adaptarse la heurística Multiple Fragment a este problema?

Solución

1. Variables

yi = cantidad que hay en el camión cuando llega a i

zi = cantidad con la que parte un camión desde bodega a i

xij =

{1 si viajo de i a j0 si no

δi = demanda insatisfecha de i

Restricciones

∑j xij = ∑k xki ≤ 1 ∀i

∑i x0i = ∑k xk0 ≤ K

yj ≥ yi − di + δi −M(1− xij) ∀i, j

yi ≤ Q ∀i

yi ≤ zi + M(1− x0i) ∀i

∑i zi ≤ I

67


yi ≥ 0, zi ≥ 0, xij ∈ {0, 1}, δi ≥ 0

Función Objetivo

mın ∑i

δi + α ∑ij

cijxij

2. Las cotas a la demanda insatisfecha las dan el inventario y la capacidad de loscamiones. El menor de ellos será el determinante, por lo tanto,

demanda insatisfecha ≥∑i

di −mın {I, kQ}

3. Se puede encontrar una cota de varias formas. Una alternativa es a través de heurís-ticas que garanticen una solución factible. Otra podría ser resolviendo el la relajaciónlineal del problema y mejorar esta solución mediante algoritmos de corte (comoB&B o Gomory).

4. Esta heurística se puede integrar agregando la restricción de capacidad para selec-cionar arcos. El algoritmo sería así: 1) seleccionar el arco de menor costo. 2) probarque el camión que utiliza ese arco es capaz de llevar la nueva demanda. 3) cuan-do ya no queden camiones disponibles o nodos libres (que toda la demanda fuesatisfecha) unir los extremos de las rutas a la bodega en 0.

68


7. Ejercicios

Pregunta 1

1. ¿Cómo perciben la variabilidad en la demanda final, los eslabones de la cadena máslejanos a la misma, con respecto a los más cercanos?. ¿Cómo se puede mejorar estapercepción y cómo se denomina este fenomeno?.

2. ¿Por qué al configurar redes logísticas con foco en los costos de habilitación (con-strucción) y transporte es adecuado utilizar horizontes de planificación superioresa 5 años?

3. Indique cuatro factores en común que tienen las industrias donde Revenue Manag-ment se ha aplicado con éxito.

4. ¿Por qué se justifica la maximización de valor esperado en el problema de venta deasientos en la industria aérea? ¿En qué casos la maximización de valor esperado nose debería aplicar?

5. Considere un sistema de inventario (S, s) con tiempos entre llegadas de clientesexponencialmente distribuidas (con tasa λ), tiempo de pedido exponencial de tasaµ, y con costos de inventario (h), quiebre de stock (b), de orden fijo (A) y de ordenvariable (v). ¿Comó utilizaría el método de reducción de varianza que considera unavariable de control para obtener una estimación del costo total de inventario?

6. Suponga que la probabilidad que lleguen al menos i clientes de la clase 1 es p1(i) =1/5i y de la clase 2 es p2(i) = 1/2i. Calcule cuantos asientos se deben reservar entotal para las clases 1 y 2 y no vender a la clase 3 si los precios son c1 = 100, c2 = 80y c3 = 40.

Solución

1. La variabilidad de la demanda se va ampliando a medida que estamos en eslabonesmás distantes de la demanda final. Esto se llama el efecto látigo y se puede mejorarcon mejor integración y comunicación entre los eslabones de la cadena de sumin-istro.

2. Debido a que los costos de habilitación (construcción) son importantes, relativo alos costos operacionales o diarios. Además estas decisiones crean infraestructuraque va a influenciar operaciones por períodos largos, en particular superiores a 5años.

Para medir el impacto de estas decisiones, es necesario comparar los costos de estascon su impacto en los costos operativos por un período importante para determinarsi es conveniente. Períodos demasiado largos resultan irrelevantes por la tasa dedescuento y el aumento de incertidumbre en las condiciones del problema.

69


3. Primero, son industrias donde con altos costos fijos. Segundo, donde ajustar oferta ala demanda es difícil o imposible en el corto plazo. Tercero, costos marginales bajos,es decir, el atender o entregar un bien a un cliente extra tiene costo muy bajo en lamedida que exista capacidad disponible. Cuarto, es posible discriminar clientes dedistintas formas, por ejemplo, cuando realizan su compra, o por pequeñas diferen-cias en el tipo de producto requerido. Quinto, en general, los productos vendidosno son almacenables.

4. Maximización de valor esperado se justifica cuando el agente tomador de decisioneses neutro ante el riesgo. Típicamente esto sucede cuando las decisiones se repitenmuchas veces en un período corto de tiempo, como en el caso de la venta de asientosde una aerolinea aérea, donde un dado vuelo de A a B, en un horario fijo durante lasemana es esencialmente el mismo. Nótese sin embargo que cuando esta simetría sepierde, valor esperado deja de ser atractivo, pues esencialmente, en la medida queuna decisión es única, queremos sacarle el mayor provecho posible, o resguardarnosde las malas situaciones etc.

Por ejemplo, para la venta de pasajes en la semana anterior a navidad, usar valoresperado pierde sentido, o más claramente, al momento de diseñar un sistema deemergencia, uno no considera el caso promedio, si no que los malos escenarios.

5. Si xi son los resultados de costo total de la simulación i, este método utiliza el esti-mador insesgado del costo total dado por Xc = 1/n ∑n

i=1 xi + c(zi − µz), donde z esuna variable aleatoria correlacionada con x y con esperanza conocida.

En este caso z puede ser el tiempo entre la llegada de i− 1 e i, que tiene esperanzaconocida µz = 1/λ.

Se deben correr algunos simulaciones piloto para estimar c = −corr(x, z)/var(z)con la correlación y varianzas empíricas de las corridas piloto.

6. Los asientos que reserva la clase j estan dados por el mayor i tal que cj pj(i) ≥ c3. Sicj pj(i) < c3 preferimos aceptar el cliente de la clase 3.

Con los datos arriba, esto dice que p1(i) = 1/5i > 40/100 = 2/5. Es decir i = 0para la clase 1, y p2(i) = 1/2i ≥ 40/80 = 1/2 es decir i = 1 para la clase 2. En totalEMSRa guardaria 1 asiento para las clases 1 y 2 y no se lo vendería a algún clientede 3 que aparezca.

Pregunta 2

1. En cuanto al modelo de tamaño de flota que se puede decir respecto a: ¿De quétipo de decisón se trata? ¿Estratégica, táctica u operacional?. Mencione que consid-eraciones se deben tener al momento de tomar una decisión?. Proponga formas desolución a este problema.

70


2. Una empresa le pide determinar el número de vehículos que necesita dado que deberealizar viajes desde un conjunto de I productores a un conjunto de J vendedores.Además se cuenta con una estimación del tiempo de viaje desde el origen i al destinoj y un factor de conversión α que relaciona la cantidad de horas viajadas y el númerode vehículos necesario para esa cantidad de horas. Cada punto de origen i tiene unaoferta determinada que se satisface con ai viajes, y cada punto de destino j tiene unademanda que se satisface con bj viajes. Plantée un modelo para encontrar el númerode vehículos óptimo.

Solución

1. Se trata de una decisión táctica- estratégica, pues es una decisión que afecta al me-diano y largo plazo, y que condiciona de gran forma el funcionamiento de una em-presa.

Algunas consideraciones que se deben tener al momento de tomar la decisión son:

Tipos de vehículos (ej. pasajeros, servicios, productos, etc)

Relaciones contractuales (vehículos propios, subcontratados, sistema mixto)

Número de depósitos, de destinos y demanda

Frecuencia de viajes, tiempos y distancias de viaje

Tipos de ruteo

Características de los vehículos (costos, carac. técnicas, etc)

Objetivos (tiempo de llegada, minimizar costos, calidad de servicio, etc)

Algunas soluciones a este problema pueden ser:

Cálculo directo: número aproximado de clientes por vehículo

Simulación: análisis de distintos escenarios

Modelos matemáticos (ejemplo modelo lineal)

2. Variables

xij: número de viajes desde el origen i al destino jN: número de vehículos

Restricciones

71


∑j xij = ai ∀i

∑i xij = bj ∀j

N = ∑i ∑j tijxijα

xij ≥ 0

Función Objetivo

mın N

Pregunta 3

Sea Xc = X + c(Z−E(Z)), tal que Z y X son v.a. que están correlacionadas y dondeademás E(X) = µ. Demuestre que la media de Xc es la misma que la de X y encuentre elpunto de menor varianza de Xc, a partir de c. Explique porqué siempre que X y Z esténcorrelacionadas, la variable Xc tendrá menor varianza.

Solución

Teniendo Xc = X + c(Z−E(Z)), tomemos la esperanza de esta variable.

E(Xc) = E(X) + c(E(Z)−E(Z))= E(X)

= µ

Para encontrar el punto de mínima varianza calculemos Var(Xc) y derivemos en funciónde c.

Var(Xc) = Var(X) + c2Var(Z) + 2cCov(X, Z)

=⇒ dVar(Xc)

dc= 2cVar(Z) + 2Cov(X, Z) = 0

=⇒ −cVar(Z) = Cov(X, Z)

=⇒ c =−Cov(X, Z)

Var(Z)

72


Si reemplazamos en Var(Xc):

Var(Xc) = Var(X) + c2Var(Z) + 2cCov(X, Z)

= Var(X) +

(−Cov(X, Z)

Var(Z)

)2

Var(Z) + 2−Cov(X, Z)

Var(Z)Cov(X, Z)

= Var(X) +Cov(X, Z)2

Var(Z)− 2

Cov(X, Z)2

Var(Z)

= Var(X)− Cov(X, Z)2

Var(Z)

Dado que Cov(X,Z)2

Var(Z) > 0 (X y Z están correlacionadas y Var(Z) > 0) siempre la varian-za de Xc va a ser menor que la de X.

Pregunta 4

1. Dado f , g : N→ R+, demuestre que f (n) + g(n) = O(max f (n), g(n))

2. Ordene en términos de crecimiento asintótico ls siguientes funciones (i.e. ordenadassegún notación O(g)). n3, log(n!), 2log(n), n3+4

√n, 4log(n), n73, n!, log(log(n)), n, 2n,

nlog(log(n)), log(n), 1.

3. Suponga que puede obtener sampleos X1, ..., Xq de una variable aleatoria X de dis-tribución desconocida. Explique como estimar el cuantil 10 % de la distribución (elvalor que es superado un 90 % del tiempo) con una confianza del 95 %.

4. Describa los distintos elementos presentes en una cadena de suministros y comocada uno contribuye al objetivo de la cadena.

Solución

1. Se tiene que:

f (n) ≤ max( f (n), g(n)) ∀ng(n) ≤ max( f (n), g(n)) ∀n

g(n) + f (n) ≤ 2 ·max( f (n), g(n)) ∀n

Siendo 2 una constante, se tiene el resultado por definición.

2. Una transformación útil:

2log(n) = 2log2(n)log210 = n

1log210 = nlog(2)

73


Además de la siguiente desigualdad:

log(n!) =n

∑i=1

log(i) ≤ nlog(n) ≤ n2

Y por último para demostrar que

n3+4√

n ≤ n7√

n ≤ 2n

se considera la siguiente igualdad. Dado que log() es creciente estricta:

lımn→∞

7√

nlog(n)nlog(2)

= lımn→∞

7log(n)√nlog(2)

= 0

Finalmente se tiene:

1 ≤ log(log(n)) ≤ 2log(n) ≤ 4log(n) ≤ n ≤ log(n!) ≤ n3 ≤ n73 ≤ nlog(log(n)) ≤ n3+4√

n ≤ 2n ≤ n!

3. Realizamos varias simulaciones para obtener un set de N sampleos X1,..., Xq/N.Luego se ordenan los Xi de menor a mayor para cada simulación, de modo de poderseparar el 10 % más bajo. Luego, se toman los valores críticos (cada valor que mar-ca el 10 % menor) para cada simulación; se promedian los ∑ X10 %

N y se obtiene sudesviación estándar empírica S10 %.

Para lograr un intervalo de confianza del 95 %, suponemos que el promedio sigueuna distribución normal (implica N mayor que 30), se necesita crear uno que multi-plique por 1, 96 a la desviación. Luego se tiene{

∑X10 %

N− 1, 96 · S10 %, ∑

X10 %

N+ 1, 96 · S10 %

}4. Esta se compone de proveedores, centros de manufactura, bodegas, centros de dis-

tribución y locales de venta.

Además considera materias primas, inventario de productos en proceso y productosterminados que fluyen por las instalaciones.

En general, una cadena de suministros bien articulada, busca reducir costos y tiem-pos de ciclo, como también mejorar la calidad del servicio, en un proceso de repartode productos. Específicamente:

Los proveedores son quienes entregan productos típicamente no procesados ala cadena.

Los centros de manufactura se utilizan para ensamblar o terminar el producto.

74


Las bodegas son utilizadas para almacenar el producto terminado.

Los centros de distribución se encargan de repartir de manera inteligente elproducto a los distintos locales.

En los locales de venta se entrega el producto al cliente.

Pregunta 5

El centro de distribución (CD) de una cadena farmacéutica, se encarga de recibir fár-macos desde distintos laboratorios, para luego repartirlos a diversos locales para su ven-ta, según las necesidades de estos. Una operación importante del CD es la preparaciónde pedidos. La preparación ocurre en cada una de 8 áreas de almacenamiento en el CD.Los operarios de preparación reciben pedidos (guías de despacho) desde los locales conla cantidad y tipo de producto deseado. De modo que el operario debe extraer todo loque se indica, armar un paquete, y despacharlo.

Los fármacos se mantienen en un inventario con un valor máximo por producto deImax. Cada producto se abastece mediante entregas que completan la cantidad a Imax ycuyo tiempo entre llegada sigue una exponencial con media 15 días. El tiempo que demo-ra un operario en armar una guía depende del número k de distintos tipos de fármacos enla guía y se representa por una distribución exponencial de media 2k minutos. Una vezcompleta la guía se pone en un camión que la lleva a destino.

El Jefe de operaciones del CD se ha dado cuenta que existen importantes pérdidas,producto de las horas extras que debe pagar para la preparación. Antes de ajustar el per-sonal ha considerado utilizar los conocimientos de simulación que adquirió en su cursode Ingeniería de Operaciones para identificar los tiempos muertos del sistema y realizarmejoras tecnológicas en aquellas partes del proceso donde existen cuellos de botella.

Suponga que hay 10 fármacos distintos y que las guías de despacho llegan al CDcon una distribución exponencial de media 30 minutos. Para evaluar distintas formasde preparación de guías de despacho, se desea correr simulaciones y estimar:

Tiempo muerto en preparación

Tiempo para completar cada tipo de orden

1. Identifique cuando hay tiempo muerto en el sistema.

2. Describa como haría una simulación para el sistema anterior. ¿Cuáles son las vari-ables de estado del sistema? ¿Cuáles son los eventos importantes? y ¿Cómo se cal-culan los estadísticos requeridos?

3. Describa en grandes razgos el control de flujo o algoritmo de este proceso de sim-ulación. Puede presentar un diagrama explicando el proceso de simulación y losdistintos eventos del sistema.

75


Solución

1. Por definición, tiempo muerto es cualquier momento en el que se desaprovechenrecursos en el sistema. El único recurso son los operarios, luego el tiempo muertorelevante es el tiempo ocioso de cada operario.

2. Variables de Estado:

Número de productos en inventario por cada uno de los fármacos.

Número de guias en cola.

Estado de ocupado, vacio o trabado por cada operario.

Tiempo ocioso de cada operario.

Tiempo en el sistema de cada guia

Cualquier evento que gatille la modificacion de una variable de estado es un eventoimportante. Por ende vamos a describir una simulación que es ”event driven”. Loseventos importantes son:

Llegada de un abastecimiento

Llegada de una guia

Fin de un servicio

Un producto se agota

Los estadisticos requeridos:

Se calculan las diferencias de tiempo cada vez que se cambia de estado, a cada es-tadistico relevante se le suma su delta. Esto se realiza de la siguiente forma: Cuandosucede un evento, queda registrada su hora. Luego el diferencial de tiempo se calcu-la con la resta simple entre la hora del último evento con el penúltimo. Debe existirun contador del tiempo ocioso de cada operario, como también uno del tiempo quelleva en el sistema cada guia.

3. El control de flujo de la simulación consiste en esperar a que ocurra el siguienteevento y cuando este ocurre actualizar las variables de estado.

Una vez concluido un evento, se samplean los tiempos exponenciales de las llegadasde productos, llegadas de una guia, servicios de operarios.

El siguiente evento que ocurre es el evento que logra el menor tiempo entre todas lasvariables aleatorias. En el caso en que el servicio sea el menor y que los inventariossean menores que los requerimientos de la guia en ese operario ocurre el evento enque falta un producto.

Las acciones del control de flujo en los 4 distintos eventos que pueden ocurrir, son:

76


Llegada de una guia:• Se actualizan las diferencias de tiempo.• Caso operario vacio, admite la guia• Caso operarios ocupados, va a la cola.

Llegada de productos:• Se actualizan las diferencias de tiempo.• Se programa ese producto en Imax.• Si producto en ”0”, se completan los pedidos estancados.

Se completa servicio:• Se actualizan las diferencias de tiempo.• Se pone el servidor en vacio.• Si hay cola, se le asigna otro trabajo.• Si no hay cola, se pone en ocio.

Cuando falta producto:• Se actualizan las diferencias de tiempo.• Se pone el servidor en ”trabado”.

Pregunta 61. Explique la diferencia entre (y dé ejemplos de) un modelo de simulación estocastico

dinámico y uno estático.

2. Describa como utilizaría un método de reducción de varianza en un simulador deun sistema M/M/1 con tasa de llegada λ y de servicio µ, si la variable de interés esel tiempo de espera en la primera media hora de funcionamiento. Explique cuál esel estimador que utilizará y por qué tiene menor varianza.

3. Dé un ejemplo de una decisión estratégica, una táctica y una operacional en el con-texto de la logística, explicando las razones de su clasificación.

4. Considere el problema de lineal de obtener el tamaño de una flota visto en clase:

mınx,N

N

s. a ∑j

xij = ai ∀i = 1, . . . , M

∑i

xij = bi ∀j = 1, . . . , M

N = α ∑i,j

tijxij

xij ≥ 0

77


a) Explique qué significa este problema. En particular dé el significado de losparámetros a, b, α y t y de las variables x, N.

b) ¿Cómo modificaría este problema para indicar que deben considerarse dostipos distintos de camiones que difieren en tamaño?

5. ¿A qué corresponde el coeficiente de variación de un producto? ¿Qué impacto teníaéste en las decisiones tomadas en el caso de Sport Obermayer?

Solución

1. Dinámico: El problema cambia de estructura con el tiempo y debe resolversecada vez que cambian los parámetros. Ejemplos: Ruteo de vehículos de emer-gencia, asistencia de fallas.

Estático: La configuración no cambia y basta con resolver una vez el problema.Ejemplo: planificación diaria de despacho de productos.

2. Si se quiere estimar el tiempo de espera antes de salir del sistema utilizando reduc-ción de varianza, entonces se puede utilizar la variable aleatoria Xc = X + c(Z −E(Z)) donde X es el tiempo de espera, Z es una variable que está correlacionadacon X y c = −Cov(X,Z)

Var(Z) una constante a estimar. En este caso Z podría ser el tiempode llegada de los individuos o el tiempo de servicio, pues ambas variables estaráncorrelacionadas con el tiempo de espera. Además se conoce su esperanza por lo quees más fácil generar Xc.

El estimador finalmente sería Xc.

3. Estratégica: Son de gran impacto, afectan de gran medida el largo plazo dela empresa y también el mediano plazo, son de carácter gerencial. Ejemplo:Alianzas con otras empresas, creación de centros de almacenamiento, tamañode flota.

Táctica: Mediano plazo, no tan decisivas como las estratégicas. Ejemplos: Re-ducción o aumento de personal.

Operacional: Día a día, corto plazo. Son decisiones no tan importantes y sontomadas por quienes ejecutan las tareas. Ejemplos: Atraso en entregas, horasextra de trabajo.

4. a) Este problema busca determinar la cantidad mínima de vehículos para satisfac-er la demanda de un conjunto de clientes distribuyendo la oferta de productosde varios centros de producción.N es el número de camiones a comprar, xij representan la cantidad de viajesnecesarios que se deben realizar en la ruta i− > j, por lo que ai y bi repre-sentarán el número esperado de viajes que se tendrán que realizar desde unabodega o hacia un cliente. Esto tiene sentido pues la compra de camiones es

78


una decisión táctica, entonces no existe certeza total sobre la cantidad de bi-enes a transportar, pero sí se puede estimar mejor la cantidad de viajes.α representa un factor de conversión de el número de horas de viajes que se ha-cen al número de vehículos necesarios para realizar esas horas en un periodode tiempo.

b) Se deben crear las variables N1 = número de vehículos de tipo 1 y N2 = númerode vehículos de tipo 2. Además se debe determinar lo transportado por cadavehículo en cada ruta i − j, por lo que se agregan las variables x1

ij y x2ij. Final-

mente el problema se reescribe como:

mın N1 + N2

s. a ∑j

x1ij + x2

ij = ai ∀i = 1, . . . , M

∑i

x1ij + x2

ij = bi ∀j = 1, . . . , M

N1 = α1 ∑i,j

tijx1ij

N2 = α2 ∑i,j

tijx2ij

x1ij, x2

ij ≥ 0

5. El coeficiente de variación representa una medida de la dispersión de la demandacon respecto a la media, dada por σp

µp, con σp la desviación estándar esperada del

producto y µp la demanda media del producto. Coeficientes de variación altos estánasociados a altos costos de errar en calzar demanda con oferta, así que deben ser losproductos a los que más atención se les coloca al momento de decidir las cantidadesa ordenar, según se realizó en el caso de SO.

Pregunta 7

1. Explique la diferencia entre decisiones estratégicas, tácticas y operacionales en laadministración de una cadena de suministro. De un ejemplo de cada tipo de de-cisión.

2. Comente la veracidad de las siguientes afirmaciones:

a) En un sistema de colas con cola única y multiples servidores (e.g. M/M/c), unnivel de utilización de 95 % es riesgoso ya que siempre produce tiempos deespera demasiado altos.

79


b) En el control estadístico de procesos, aumentar el tamaño de la muestra utiliza-da para construir los diagramas de control lleva a una detección mas eficientede procesos fuera control.

3. Considere el problema de optimización con n variables x = (x1, x2, . . . , xn) = (x1, x):

mın c1x1 + cT xs.t. x1 + aT

i x ≤ bi i = 1, . . . m

donde m >> n.

a) Describa el método de generación de restricciones para resolver este problema.Indique cuál es el valor de la cota inferior del valor óptimo que se obtiene encada iteración.

b) Encuentre una cota superior al valor óptimo que se obtiene en cada iteracióncuando c1 < 0. ¿Cuanto es el gap con la cota inferior.?

Solución

1. Diferencias tienen que ver con cuanto tiempo estas decisiones influencian la cadenade suministro ademas de los montos involucrados en las decisiones. Por ejemplo,una decision estratégica seria decidir si extender la red de suministro a un mercadonuevo, lo que involucra inversion en la cantidad de produccion, bodegas, expandirflota, etc para el nuevo mercado. Una decision táctica puede ser decidir con quetransportista establecer un contrato de transporte que dure un periodo (por ejemploun año). una decision operacional puede ser cuanto producir una semana o enviarun dia.

2. a) En un sistema de colas markovianos un nivel de utilización del 95 % no pro-ducirá siempre tiempos de espera altos, pero si genera una espera promedioalta, junto con una prácticamente nula capacidad de respuesta frente a vari-abilidad de la demanda al alza.

b) Dado que los intervalos de confianza del proceso están dados por CL = p ±3√

p(1− p)ni

, con ni, i = 1, . . . , m el tamaño de la sub-muestra dentro de las mmuestras, si se consideran más casos por cada muestra tiene un efecto en lacerteza, pero este efecto debe ser contrapesado con el mayor costo que trae elmuestrear más veces, por lo que no siempre es eficiente en costos.

3. a) El problema maestro del método de generación de restricciones es

mın c1x1 + cT xs.t. x1 + aT

i x ≤ bi i ∈ I

80


donde I ⊂ {1, . . . , m} es un conjunto pequeño de restricciones. Una vez re-suelto el maestro se obtiene una solución x∗ = (x∗1 , x∗) y se debe resolver elsiguiente subproblema:

z = mıni∈{1,...,m}

bi − aTi x∗

Si z ≥ x∗1 entonces tenemos que x∗ es la solución óptima del problema comple-to. Si no, entonces exite un j tal que z = bj − aT

j x∗, agregamos j a I y volvemosa resolver el problema maestro.En cada iteración el valor c1x∗1 + cT x∗ es una cota inferior al valor óptimo delproblema completo, v∗ ya que es la solución de un problema mas relajado (conregión factible mas grande).

b) Dada la solución al maestro x∗ y el valor del subproblema z, tenemos que x =(z, x∗) es factible para el problema completo, por lo tanto v∗ ≤ c1z+ cT x∗. Noteque en una iteración normal z < x∗1 por lo que c1 < 0 es critico para que lascotas superiores e inferiores estén ordenadas ya que en ese caso c1x∗1 < c1z. Elgap es de c1(z− x∗1) > 0.

Pregunta 8

Considere un problema en que rutea K vehículos que salen del nodo 0 para atenderclientes 1, . . . , n. Para cada localidades i y j usted enfrenta un costo de viaje igual a cij yun tiempo de viaje igual a tij. Cada cliente i tiene una ventana de tiempo para ser visitadodada por [ai, bi] y si el vehiculo llega antes incurre un costo de α por unidad de tiempo,mientras que si llega tarde un costo de β por unidad de tiempo.

1. Formule este problema de ruteo de vehículos de forma de minimizar el costo totalde las rutas por viajes y violaciones a las ventanas de tiempo.

2. ¿Tiene sentido llegar antes a un cliente o siempre se puede esperar en la puerta?

3. Cuando α = β = 0 recuperamos el ruteo de vehiculos simple, si α = β = ∞tenemos un problema de ruteo de vehiculos con ventanas de tiempo duras. ¿Cómose comparan los costos de viaje de la ruta óptima cuando α = β = 0, α = β = ∞ yα, β > 0?

4. Muestre la siguiente equivalencia en las restricciones que eliminan sub-tours de unproblema de ruteo de vehiculos:

∑i,j∈S

xij ≤ |S| − 1 ∀ S ⊂ V ⇔ ∑i∈S,j 6∈S

xij ≥ 1 ∀ S ⊂ V

Solución

81


1. usaremos variables binarias xij para indicar si un vehiculo viaja de i a j. Ademasse utilizarán variables continuas wi que indica el tiempo de llegada al cliente i, li elatraso al cliente i, y ei el tiempo que se llega adelantado al cliente i.

mın ∑nij=1 cijxij + ∑n

i=1 αei + βlis.a. ∑n

j=1 xij = ∑nk=1 xki = 1 i = 1, . . . n

∑nj=1 x0j = ∑n

k=1 xk0 = Kwi + tij ≤ wj + M(1− xij) i, j = 1, . . . nwi + ei ≥ ai i = 1, . . . nwi − li ≤ bi i = 1, . . . nwi, li, ei ≥ 0 i = 1, . . . nxij ∈ {0, 1} i, j = 0, 1, . . . n

2. Si, puede ser ventajoso llegar adelantado a un cliente i, e incurrir en el costo α si estoluego permite llegar a tiempo a otro cliente k, posiblemente ahorrando un costo β.Note que hay ejemplos en los que podemos llegar adelantados a un cliente y ’esperaren la puerta’ para ahorrarnos el costo α. En este caso se veria que la restriccion 3tendria holgura y podriamos ahorrarnos la penalidad por llegar antes.

3. En este problema solo deseamos comparar el costo de viaje cTx = ∑ij cijxij de lasrutas óptimas en cada caso. Esto es, como se ordenan cTx0, cTx∞, y cTx∗, donde x0

es la solución óptima cuando α = β = 0 (caso 1), x∞ cuando α = β = ∞ (caso 2) yx∗ para todo los otros α, β > 0(caso3)

Como el problema con restricciones duras de ventanas de tiempo es un problemamás restringido, tenemos que cTx∞ ≥ cTx0, cTx∗ ya que no todas las rutas que sonfactibles en los casos 1 y 3 son factibles en el caso 2. Luego, en el caso 1 solo seesta minimizando cTx (ya que las penalidades por adelantarse o atrasarse son cero)por lo que cTx0 debe ser el valor de la ruta con tiempo de viaje minimo. LuegocTx0 ≤ cTx∗ ≤ cTx∞

4. Dado un conjunto no vacio y estricto, S ⊂ V. Es decir que hay al menos un puntoi ∈ S y un punto j 6∈ S. Tenemos que para todo punto i ∈ S una ruta factible satisfacela restriccion ∑n

j=1 xij = 1, esto quiere decir que para todo i ∈ S tenemos

1 = ∑j∈S

xij + ∑j 6∈S

xij

sumando sobre todos los i ∈ S tenemos

|S| = ∑i,j∈S

xij + ∑i∈S,j 6∈S

xij

Esta equación se utiliza para demostrar la equivalencia de la pregunta.

82


Pregunta 9

1. Describa brevemente como utilizar optimización estocástica para encontrar la solu-ción óptima para el problema del caso Sport Obermayer. En particular indique cualesson las variables de primera etapa, de segunda etapa, la incertidumbre, objetivo yrestricciones.

2. Un cine debe decidir cuantas entradas ofrece atravez de un sistema de ventas colec-tivas con descuento (Grapin) recibiendo $1.000 y cuantas deja para clientes de últi-mo minuto que compran en la boleteria a $5.000. Suponga que siempre vende todaslas entradas ofrecidas por Grapin, que la sala de cine tiene capacidad para 200 per-sonas, y que el número de clientes de último minuto es un número uniformementedistribuido entre 21 y 70. Utilice la regla de Littlewood para determinar cuantosasientos se deben reservar para clientes de último minuto.

3. De dos ejemplos de decisiones estratégicas en la logística de transportes. Indique eltipo de problema que debe ser resuelto para tomar esta decisión y explique porqueson estratégicas y no de otro tipo.

4. Muestre que el sub-problema de generación de columnas es equivalente al sub-problema de generación de restricciones en el dual del problema original. Considerepara esto la generación de columnas en el siguiente PL, donde n >> m:

mınn

∑j=1

cjxj |n

∑j=1

aijxj = bi, i = 1 . . . m, xj ≥ 0, j = 1 . . . n .

5. De un pequeño ejemplo que muestre que la heurística del vecino más cercano puedeno encontrar la solución óptima.

Solución

1. En el caso de S.O. hay que decidir cuanto de distintos productos encargar antes dever una buena approximación de la demanda real en el show de Las Vegas. Luegodel show se pueden encargar más productos sujeto a restricciones de capacidad masestrictas.

Si tomamos la demanda despues del show como la demanda real, esto es un prob-lema de optimización estocástica con dos etapas: la variable de primera etapa sonlos pedidos originales, mientras la variable de segunda etapa son los pedidos quese realizan despues del show conocida la demanda real. La demanda es incierta alhacer los pedidos originales, pero es revelada en el show de las vegas, antes de lasvariables de segunda etapa.

Este modelo busca la solución que maximiza los ingresos esperados, considerandolos costos de overage y underage, dadas realizaciones de demanda.

83


2. El criterio de littlewood dice: si se tienen k asientos disponibles, se debe reservar elúltimo espacio para el cliente de mejor precio (p1) si p1P(d1 ≥ k) ≥ p2. En este casoesto dice que, se debe encontrar el mayor k tal que P(d1 ≥ k) ≥ 1000/5000 = 1/5 =0.2.

Como d1 es un número entero∼ U[21, 70] tenemos que P(d1 = k) = 1/50 para todok ∈ {21 . . . 70}, por lo que P(d1 ≥ k) = (70− k + 1)/50 para todo k ∈ {21 . . . 70}.Con esto vemos que el mayor k que satisface Littlewood es k = 61 donde P(d1 ≥61) = 1/5. Esto implica que se deben guardar 61 asientos para la clase 1 y enviar139 a Grapin.

3. Todos los problemas abajo se pueden representar con modelos de optmizacion lin-eal, algunos con variables enteras. Son principalmente estratégicas por los montosde inversión involucrados en estas decisiones y los horizontes de planificación quedeben ser considerados para estos proyectos. No se pueden tomar estas decisionestodos los días o varias veces al año. Otra generalidad es que dado los horizontesde planificación resulta importante representar la incertidumbre se puede optar amodelos mas simples (flujo en redes) en los que es mas facil considerar la incer-tiumbre. Abajo describo algunos ejemplos de decisiones estrategicas y describo enmas detalle que modelos de optimización servirian.

Comprar una flota o subarrendar el servicio de transporte. Se puede represen-tar el problema de ruteo que se debe hacer como un VRP (con variables enteras)para determinar los costos y nivel de servicio de las distintas alternativos deflota.

Donde construir un depot (bodegas, garage, mantencion vehiculos). Problemasde localizacion, con variables enteras que deciden si un depot se usa o no yalgun modelo de asignación de demanda a depots abiertos.

Como diseñar la red de transporte, por ejemplo usar una bodega de distribu-ción y altos costos de transporte, o muchas bodegas con menores costo de trans-porte pero con mas segmentos. Un problema de flujo en redes en los que tam-bien pueden haber nodos con capacidades que se van a cero.

Determinar los puntos de la demanda que serán cubiertos (determinando can-tidad de transporte necesario). Modelos lineales del costo approximado de sat-isfacer una cierta cantidad de demanda.

4.

5.

Pregunta 10

84


1. Explique cuando es conveniente abordar un problema de decisón con un modelo desimulación, de optimización matemática, o mediante heurísticas.

2. Suponga que quedan 3 asientos disponibles en un vuelo que pueden venderse a pre-cio completo (US$1.000) o en oferta (US$400). Suponga además que la probabilidadque lleguen 0, 1, ó 2 clientes de precio completo es 0,1 , 0,25 y 0,35 , respectivamente.En este momento llega una persona a comprar el pasaje en oferta. Utilice la regla deLittlewood para decidir si se le vende el pasaje o no.

3. Dada esta formulación de el cutting stock problem:

mın ∑Kk=1 yk

s.t. ∑Kk=1 xik ≥ bi ∀i = 1 . . . m

∑ni=1 wixik ≤Wyk ∀k = 1 . . . K

yk ∈ {0, 1} ∀k = 1 . . . Kxik ≥ 0 integer ∀i = 1 . . . m, k = 1 . . . K

a) Formule el problema que es resuelto por generación de columnas. ¿Cómo secompara el valor óptimo con el del problema de arriba?

b) Escriba el problema maestro y el subproblema del método de generación decolumnas.

c) ¿Cómo obtenemos una cota superior al valor óptimo en cada iteración delmétodo de generación de columnas?

d) Al hacer una generación de columnas para resolver el problema, >como obten-emos una cota superior?

Solución

Pregunta 11

1. ¿Cuándo es importante utilizar un método de reducción de varianza en una simu-lación?

2. Suponga que una simulación (con varianza σ2 conocida) arroja un promedio x > 0.¿Cuántas repeticiones de la simulación son necesarias para tener un 95 % de confi-anza que el promedio de la simulación es mayor o igual a zero?

3. ¿El algoritmo de descomposición de Benders es un ejemplo de un método de gen-eración de columnas o de generación de restricciones? Explique brevemente.

4. ¿Por qué se justifica la maximización del valor esperado en el Newsvendor prob-lem? ¿En qué casos maximizar el valor esperado no tiene sentido?

Solución

85


1. Cuando realizar una simulación sea muy costoso o difícil, la reducción de varian-za se convierte en una alternativa para conseguir resultados más robustos, sin lanecesidad de hacer nuevas simulaciones.

2. Sabemos que el estimador x tiene media µ y varianza σ2

n . Para garantizar al % 95 quese el promedio es no negativo se debe cumplir:

P(µ ≥ 0) = 0.95

=⇒ P(

µ−xσ/√

n ≥−x

σ/√

n

)= 0.95

=⇒ 1.64 · σ√n ≤ x

=⇒(

1.64x σ)2≤ n

Gracias a que P(Z ≤ 1.64) = 0.95 cuando Z ∼ N(0, 1)

3. Es un ejemplo de generación de restricciones. Es un método que tiene un proble-ma principal (P. Maestro) al que se le agregan restricciones, en la medida que lossubproblemas no cumplan ciertos criterios.

4. Maximización de valor esperado se justifica cuando el agente tomador de decisioneses neutro ante el riesgo. Típicamente esto sucede cuando las decisiones se repitenmuchas veces en un período corto de tiempo, como en el caso de la venta de asientosde una aerolinea aérea, donde un dado vuelo de A a B, en un horario fijo durante lasemana es esencialmente el mismo. Nótese sin embargo que cuando esta simetría sepierde, valor esperado deja de ser atractivo, pues esencialmente, en la medida queuna decisión es única, queremos sacarle el mayor provecho posible, o resguardarnosde las malas situaciones etc.

Por ejemplo, para la venta de pasajes en la semana anterior a navidad, usar valoresperado pierde sentido, o más claramente, al momento de diseñar un sistema deemergencia, uno no considera el caso promedio, si no que los malos escenarios.

Pregunta 12

Suponga el siguiente problema: Usted tiene N trabajos que procesar en M máquinas.Cada trabajo debe ser procesado en todas las máquinas, pasando siempre primero por lamáquina 1, luego por la máquina 2, y así sucesivamente hasta terminar en la máquina M.

Suponga además que los trabajos deben ser procesados en el mismo orden en todaslas máquinas.

86


El trabajo n toma Tnm en ser procesado en la máquina m.Plantee un problema de programación lineal para determinar el orden en que debe

procesar los trabajos de modo de minimizar el tiempo de tránsito total.

Solución

Las variables son:

xij =

{1 Si el trabajo j se realiza inmediatamente después del i0 Si no

tim = tiempo de comienzo del trabajo i en la máquina m.

t f = tiempo de fin del último trabajo en la última máquina

Las restriciones:

∑Ni=0 xij = 1 ∀j

∑N+1j=1 xij = 1 ∀i

∑Nj=1 x0j = 1

∑Ni=1 xiN+1 = 1

t f ≥ tiM + TiM ∀i

tim+1 ≥ tim + Tim ∀i, m

tjm ≥ tim + Tim − (1− xij)V ∀i, j, m V >> 1

tim ≥ 0, xij ∈ {0, 1} ∀i, j, m

y finalmente la función objetivo

mın t f

87

Documents

Gestión de Operaciones II IN4704 - U-Cursos · IN4704-Gestión de Operaciones II Entonces comparamos el óptimo de la solucion para cada subproblema y elegimos el mejor. Cada subproblema