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