Investigación de operaciones modelos y aplicaciones de programación lineal (página 2)

 EJEMPLO 3.2:

Max Z = 3×1 + 5×2

Sujeto a:

X1 -2×2 <= 5

2×1 <= 12

X1, x2 >= 0

Forma típica:

Z -3×1 – 5×2 = 0

X1 -2×2 + x3 = 5

2×1 + x4 = 12

X1, x2, x3, x4 >= 0

X3, x4 variables de holgura.

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

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

EJEMPLO 3.3: Múltiples soluciones óptimas

Max z = 2×1 + 4×2

Sujeto a:

x1 + 2×2 <= 12

2×1 + 2×2 <= 12

x1, x2 >= 0

Forma típica:

Z – 2×1 – 4×2 = 0

X1 + 2×2 + x3 = 12

2×1 + x2 + x4 = 12

Primera iteración:

Variable no básica entrante x2

 Segunda iteración:

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

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

EJEMPLO 3.4:

  Max 2×1 + 3×2

Sujeto a:

X1 + 2×2 + x3 = 4

X1 + x2 = 3

X1, x2, x3 >=0.

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

X1 + x2 + x4 = 3

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

 Al modificar la función objetivo queda así:

Z = 2×1 + 3×2 – Mx4

 Primera iteración:

Segunda iteración:

Solución optima:

x1 = 2, x2 = 1, z = 7

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

III.1 EL METODO SIMPLEX DE DOS FASES

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

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

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

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

Min z = 4×1 + x2

Sujeto a:

3×1 + x2 = 3

4×1 + 3×2 >= 6

x1 + 2×2 <= 4

x1, x2 >= 0

Forma estándar con variables artificiales:

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

Sujeto a:

3×1 + x2 + R1 = 3

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

x1 + 2×2 + x4 = 4

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

FASE I:

Min r = R1 + R2

Sujeto a:

3×1 + x2 + R1 = 3

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

x1 + 2×2 + x4 = 4

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

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

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

Tabla inicial:

La tabla optima se obtiene en dos iteraciones:

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

 Luego en la fase II resolvemos:

Min z = 4×1 + x2

Sujeto a:

x1 + 1/5 x3 = 3/5

X2 – 3/5 x3 = 6/5

X3 + x4 = 1

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

 Obteniéndose la tabla inicial para la fase II:

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

III.2 DEFINICION DEL PROBLEMA DUAL

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

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

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

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

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

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

Sujeto a S j =1..naijxj = bi

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

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

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

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

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

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

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

EJEMPLO 3.2.1:

Max z = 3×1 + 5×2

Sujeto a:

x1 + 10×2 < 80

2×1 + 3×2 < 45

4×1 – 2×2 <  25

3×2 <60

x1, x2 > 0

Aplicando las reglas :

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

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

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

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

Problema dual:

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

Sujeto a:

Y1 + 2y2 + 4y3 > 3

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

y1, y2, y3, y4 > 0

2. Max Z = 3×1 + 7×2

Sujeto a:

2×1 + 5×2 = 15

x1 + 8×2 < 30

x1, x2 > 0

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

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

• Aplicando las reglas y la nota:

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

Problema dual:

Min Y= 15y1 + 30y2

Sujeto a:

2y1 + y2 ³ 3

5y1 + 8y2 ³ 7

y1 sin restricción de signo (irrestricta)

y2 ³ 0.

III.3 ANALISIS DE SENSIBILIDAD

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

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

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

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

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

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

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

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

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

EJEMPLO 3.3.1:

1. Cambios en los coeficientes objetivo:

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

Sujeto a

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

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

-x1 + x2 + h3 = 1 (demanda)

x2 + h4 = 2 (demanda)

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

Tabla primal Óptima:

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

XB = (x2, x1, x5, x6)

CB = (4, 5)

Y = (y1, y2, y3, y4)

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

Los nuevos coeficientes de la función objetivo son

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

IV. MODELO DE TRANSPORTE

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

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

EJEMPLO 4.1:

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

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

El modelo típico tiene cuatro componentes:

• Un conjunto de m fuentes

• Un conjunto de n destinos

• Costos de transporte entre las fuentes y los destinos

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

El modelo general que representa el modelo de transporte es:

Min z = S iS j cijxij

Sujeto a:

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

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

             xij >= 0

IV.1 MODELOS BALANCEADOS Y NO BALANCEADOS

IV.1 MODELOS BALANCEADOS Y NO BALANCEADOS:

Un modelo de transporte se llama balanceado cuando:

S i ai = S j b

Esto significa que la suma de los suministros de todas las plantas debe ser igual a la suma de las demandas de todos los almacenes.Sin embargo en problemas de la vida real, esta igualdad rara vez se satisface.

Lo que se hace entonces es balancear el problema.

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

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

Recíprocamente, si los suministros exceden a los requerimientos, se agrega un almacén ficticio que absorberá el exceso.El costo unitario de transporte desde las plantas al almacén ficticio es cero.

 Ejemplo 4.1.1

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

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

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

       Min z = 80×11 + 215×12 + 100×21 + 108×22 + 102×31 + 68×32

        Sujeto a:

                        x11 + x12 = 1000

                        x21 + x22 = 1500

                        x31 + x32 = 1200

                        x11 + x21 + x31 = 2300

                        x12 + x22 + x32 = 1400

                        xij >= 0 para toda i, j.

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

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

Como siempre, se entiende mejor con un ejemplo:La más famosa empresa dentro de las aulas universitarias, la Empresa Gerconsa, tiene tres fabricas donde manufactura su famosísimo producto P, con capacidades de producción de 25 (unidades por micronanosegundo, por segundo, hora, año… no importa, es lo mismo para todos), 25,10 y debe surtir a 4 almacenes con demandas de 20,15,20,5 (unidades por micronanosegundo, segundos.. o lo que sea, siempre y cuando se maneje la misma unidad temporal en todo el problema). Los costos de enviar desde cualquier fábrica a cualquier almacén se pueden ver en la tabla abajo.

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

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

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

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

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

 V. EL PROBLEMA DE LA ASIGNACIÓN

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

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

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

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

V.1 FORMULACION DE PROGRAMACION LINEAL

EJEMPLO 5.1.1: Existen cuatro operarios que se pueden asignar al trabajo con tres máquinas.  Un estudio de tiempos y movimientos ha arrojado los siguientes tiempos por operario para las tres máquinas. Indicar que operario debe trabajar en que máquina y cuál de ellos no será asignado a ninguna.

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

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

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

Así por ejemplo:

10X11 + 7X12 + 9X13 + 0X14

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

Restricciones:

Como cada operario sólo puede estar asignado a una máquina….

X11 + X12 + X13 + X14 = 1X21 + X22 + X23 + X24 = 1X31 + X32 + X33 + X34 = 1X41 + X42 + X43 + X44 = 1

Y como cada máquina solo puede tener un operario asignado…

X11 + X21  + X31 + X41 = 1X12 + X22  + X32 + X42 = 1X13 + X23  + X33 + X43 = 1X14 + X24  + X34 + X44 = 1

Xij = 1 o 0 para toda i,j.

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

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

 V.2 ALGORITMO HUNGARO

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

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

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

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

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

• Realizar la Asignación de la siguiente manera:

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

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

V.2.1 MÉTODO DE FLOOD:

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

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

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

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

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

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

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

V.3 PROGRAMACION BINARIA EN EL PROBLEMA DE ASIGNACION

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

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

EJEMPLO 5.3.1:

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

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

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

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

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

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

Ahora en Excel…

Este puede ser el formato:

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

Luego de hacer click en resolver…

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

VI. BIBLIOGRAFIA

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

Administrativa

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

Edicion, 1991_MC_Graw_Hill

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

Edicion, 1984, CECSA

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

Administración. Primera Edicion, 1983

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

Iberoamericana, 1989, EUA.

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

Casos. Editorial Limusa, 1996, México

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

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

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

9. Web Site:

• www.elprisma.com

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

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

Autor:

German J. Huaman