Resumen Investigacion Operativa

Método Simplex

1. Convertir ecuaciones y agregar nuevas variables a Z

X1 + X2 ≤ 9        →        X1 + X2 + S1 = 9

X1 + X2 ≥ 9        →        X1 + X2 – S2 + μ1 = 9

X1 + X2 = 9        →        X1 + X2 + μ1 = 9                →        [pic 1]

Si termino independiente negativo, multiplico por -1:         X1 + X2 ≤ -9         →        - X1 - X2 ≥ 9

Zmax = 2 X1 + 3 X2        →        Zmax = 2 X1 + 3 X2 + 0 S1 - M μ1 + 0 S2

Zmin = 2 X1 + 3 X2        →        Zmin = 2 X1 + 3 X2 + 0 S1 + M μ1 + 0 S2

1. Armar tabla

1er fila:

• En la primera columna van las S, pero si hay μ, va μ y no su S
• En la primera fila:

• Si no hay μ, se ponen los coeficientes
• Si hay μ:         Z = 80 X1 + 60 X2 + 0 S1 + M μ1

1. Elegir pivot

• 1ro: columna pivot = columna del numero… MAX → más negativo        MIN → más positivo
• 2do: obtengo Φ = columna solu / columna pivot
• 3ro: fila pivot = fila del Φ más chico 

1. Divido fila del pivot por el pivot
2. Diferencia de productos cruzados
3. Tabla optima: MAX → primera fila todo ≥ 0                MIN → primera fila todo ≤ 0
4. Extraer valores de columna solución

Tener en cuenta

• No hay solución: Si la tabla es óptima, pero en la primera columna tengo variable artificial (μ).
• Solución no acotada: Cuando elijo la columna pivot y todos sus valores son negativos.
• Degeneración: Cuando empatan las columnas pivot.

Método Dual

Convertir ecuaciones: Los coeficientes en fila se encolumnan. Si es MIN pasa a MAX  y viceversa.

MIN → ≥        MAX → ≤

Simétrico:

6 X1 + 16 X2 ≤ 48                6 Y1 + 12 Y2 + 9 Y3 ≥ 4[pic 2][pic 3]

12 X1 + 6 X2 ≤ 42                16 Y1 + 6 Y2 + 9 Y3 ≥ 3

9 X1 + 9 X2 ≤ 36                

Zmax = 4 X1 + 3 X2                 Zmin = 48 Y1 + 42 Y2 + 36 Y3

X1, X2 ≥ 0                        Y1, Y2, Y3 ≥ 0

X1 + X2 = 9        →        [pic 4]

Asimétrico:         MAX con =        →        MIN transpuesta con [pic 5]

                MIN con =        →        MAX transpuesta con [pic 6]

No se ponen la CNN.

Pasaje de tabla optima

n = cantidad de variables        X1 = Y1 + n        X2 = Y2 + n        S1 = Y3 - n        S2 = Y4 – n…

1. Las variables cuya primera fila no es 0 pasan a ser 1er columna
2. Las columnas se ordenan: Y1, Y2, Y3, Y4 = S1, S2, X1, X2
3. Para cada elemento dentro de la tabla:

1. fila/columna → columna/fila
2. se multiplica por -1
3. cada elemento consigo mismo es 1
4. todo lo que quede sin completar es 0

1. La primera fila pasa a ser la última columna y viceversa.
2. Si dual MIN → niego 1er fila                MAX → niego última columna

Transporte

1. oferta, demanda, costo, ∑dem=∑of (si ≠ degen*)
2. Elijo cuadrado según criterio
3. Al cuadrado le asigno unidades (las resto de oferta y de demanda pendiente)
4. Fin cuando demandas u ofertas en 0

*si es degenerada agrego fila/columna con el valor faltante y costos 0.

Criterios

• Esquina noroeste

• Inicio por la esquina superior izquierda (A1, B1)

• Si demanda = 0 me muevo a la derecha
• Si oferta = 0 me muevo abajo

• MODI / costo minimo

• Inicio por la primera columna
• Elijo fila de menor costo

• Si demanda = 0, paso a la columna de la derecha
• Si oferta = 0, elijo la siguiente fila de menor costo

• VOGEL

• Obtengo diferencia entre los 2 costos más chicos de cada fila y columna
• Elijo fila y columna con dif más grandes, en caso de empate elijo el de menor costo

• Si demanda = 0, tacho columna y actualizo diferencias
• Si oferta = 0, tacho fila y actualizo diferencias

Asignación

Menor por columna

1. Agarro el menor valor por columna
2. Creo nueva tabla donde c/ valor es la deferencia entre el valor viejo y el menor valor por col
3. Cuento cantidad 0s por fila y columna y los agrego al final
4. Tacho fila o columna con más 0s y actualizo
5. Repetir hasta que quede todo 0
6. El más chico entre todos los no tachados es el valor marginal (VM)
7. Nueva columna (ui) y fila (vj) van al final

1. ui → fila que tache = 0, fila que no tache = VM
2. vj → columna que tache = - VM, columna que no tache = 0

1. Armo nueva tabla con regla: a*ij = aij - (ui + vj)
2. Busco 0s esenciales: único en su fila y columna

1. Obtener tantos 0s como filas/columnas haya tachando 0s según convenga
2. En la posición que tache 0, pongo el valor de dicha posición en la tabla original 

Menor por fila

1. Agarro el menor valor por fila

7.         Nueva columna (ui) y fila (vi) van al final

...