Investigación de Operaciones - Rodolfo Valentín Muñoz Castorena
Investigación de Operaciones - Rodolfo Valentín Muñoz Castorena
Investigación de Operaciones - Rodolfo Valentín Muñoz Castorena
de operaciones
02/03/11 01:53 PM
02/03/11 01:53 PM
Investigacin
de operaciones
02/03/11 01:53 PM
INVESTIGACIN DE OPERACIONES
Primera edicin
Prohibida la reproduccin total o parcial de esta obra,
por cualquier medio, sin la autorizacin escrita del editor.
ISBN: 978-607-15-0598-9
All rights reserved
1098765432
1098765432101
Impreso en Mxico
Printed in Mexico
02/03/11 01:53 PM
COntEnidO
2
2
3
4
4
5
Unidad II
2.1
2.2
2.3
2.4
2.5
2.6
Unidad III
35
38
42
46
53
54
61
62
02/03/11 01:54 PM
VI
Contenido
Unidad IV
67
68
68
70
70
70
71
71
71
71
72
74
77
77
77
78
79
79
80
Glosario ...................................................................................................... 81
Bibliografa ................................................................................................ 82
ndice ......................................................................................................... 83
02/03/11 01:54 PM
VII
02/03/11 01:54 PM
INtrOducciN
El objetivo principal de este trabajo es servir como libro de consulta para el curso de
Investigacin de operaciones, el cual se orienta a estudiantes de licenciatura y, fundamentalmente, a las reas de estudio como Negocios internacionales, Administracin y
Marketing. Los prerrequisitos son lgebra lineal, matemticas y estadstica.
El texto proporciona suficiente material para el curso, tratando de desarrollar en
cada unidad numerosos ejemplos basados en la realidad para una mejor comprensin
de los contenidos de esta disciplina.
Si se analizan los ejemplos, el lector adquirir capacidad para resolver problemas
matemticos y conocer las principales reas que componen la Investigacin de operaciones (desde el anlisis del problema, la recopilacin de la informacin, la formulacin del modelo y el anlisis de resultados).
Esta ltima etapa se destaca por su importancia, por lo que se expondrn en forma
amplia temas como el de anlisis de sensibilidad.
VIII
02/03/11 01:54 PM
Unidad
Qu es la investigacin
de operaciones?
Al finalizar el estudio de esta unidad, se espera que el lector sea capaz de:
explicar qu se entiende por investigacin de operaciones.
describir qu es un modelo.
mencionar algunas aplicaciones de la investigacin de operaciones.
explicar los diferentes tipos de modelos.
disear modelos para casos especficos.
Algunos autores utilizan el trmino ciencias de la administracin como sinnimo de investigacin de operaciones.2
La IO se define como un conjunto de modelos matemticos aplicables a la solucin de ciertos problemas orientados a la toma de decisiones, en los que se involucran variables de decisin en los cuales
se desea optimizar:
1. El uso de los recursos para lograr un determinado fin cuantificable.
2. Los problemas ms o menos complejos que se presentan en una organizacin social cuya solucin
emprica resulta demasiado costosa e inadecuada.
1
2
02/03/11 01:55 PM
UNIDAD I
Qu es la investigacin de operaciones?
1.2 Modelo
Modelo. Representacin simplificada o
idealizada de una parte de la realidad.
Los modelos, que se definen como una funcin objetivo y restricciones que se expresan en
trminos de las variables alternativas de decisin del problema (vase figura 1.1), deben contener los siguientes tres elementos:
3
4
Op. cit., p. 3.
Real Academia Espaola, Diccionario de la lengua espaola, vigsima segunda edicin, http://buscon.rae.es/draeI/SrvltConsulta?TIPO_
BUS=3&LEMA=modelo, consultado el 4 de octubre de 2010.
02/03/11 01:55 PM
1.2
Modelo
Figura 1.1
Analiza
Problema simplificado
Llega
Modelo
Juan Pilar Tormos, Investigacin operativa para ingenieros, Espaa, Ed. Universidad Politcnica de Valencia, p. 33.
02/03/11 01:55 PM
UNIDAD I
Qu es la investigacin de operaciones?
Adems de la clasificacin anterior, existen otras que son independientes de los modelos
matemticos que se mencionaron y que pueden agruparse bajo la perspectiva de uno o varios
de los trminos que aparecen en la tabla 1.1.
Tabla 1.1 Trminos de los modelos matemticos
Trmino
Definicin
Modelos fsicos
Modelos abstractos
Modelos estticos
Modelos dinmicos
Modelos determinsticos
Modelos aleatorios
Desventajas
Permiten apreciar cules son las variables importantes del problema y cmo se relacionan entre s.
1.3 Optimizacin
Optimizar. Logro de mayores beneficios
con una mnima inversin de recursos.
tambin denominada programacin matemtica, sirve para encontrar la respuesta que proporciona el mejor resultado, la que obtiene mayores ganancias, mayor produccin o felicidad o la que logra
el menor costo, desperdicio o malestar. Con frecuencia, estos problemas implican utilizar de la manera ms eficiente los recursos, tales como dinero, tiempo, maquinaria, personal, existencias, etc. Los
02/03/11 01:55 PM
Actividades de la unidad I
Problemas de optimizacin
En un problema se trata de maximizar o minimizar una cantidad especfica llamada objetivo,
la cual depende de un nmero finito de variables de entrada. stas pueden ser independientes
entre s o relacionarse a travs de una o ms restricciones.
1
El problema: Minimizar: Z = x1 + x2
Sujeto a: x1 x2 = 3
x2 2
ste es un problema de optimizacin del objetivo z, en el que las variables de entrada son x1
y x2. Se desean obtener valores de las variables de entrada que minimicen el objetivo principal,
sujetos a las limitaciones impuestas por las restricciones.
Un programa matemtico como el del ejemplo anterior es lineal si f(x1, x2, , xn) y cada
gi(x1, x2, , xn) donde (i = 1, 2, , m) se dan como funciones matemticas y como ilaciones
funcionales (como sucede en el primer ejemplo).
2
Maximizar Z = 4x1 + 5x2
Sujeto a: 3x1 + 2x2 15
2x1 + 3x2 4
x1, x2 0
Cabe sealar que la ltima restriccin, de no negatividad, indica que las variables que se utilizaron en
el modelo deben ser positivas o ceros puesto que, si se deseara producir, por ejemplo, dulces, no se podran
producir 4 dulces.
02/03/11 01:55 PM
02/03/11 01:55 PM
Unidad
II
Programacin
lineal
Al finalizar el estudio de esta unidad, se espera que el lector sea capaz de:
explicar qu entiende por programacin lineal.
exponer los pasos para plantear un problema dado.
explicar cmo se forman las restricciones y la funcin objetivo.
mencionar la estructura general de un modelo de programacin lineal.
resolver e interpretar problemas mediante el empleo del concepto de mtodo grfico.
resolver e interpretar problemas mediante el empleo del concepto de mtodo smplex.
02/03/11 01:56 PM
UNIDAD II
Programacin lineal
Las variables de decisin son las cantidades desconocidas que deben determinarse en la solucin de un problema cuyo modelo se plantea. Un ejemplo
para definir una variable de decisin podra ser la cantidad de un determinado
producto que debe fabricarse en una operacin de produccin que involucra
diversos productos a partir de un mismo recurso bsico (vase figura 2.1).
Escritorios
Recurso
bsico
Mano de obra
Mesas
Figura 2.1
En la figura 2.1 se indica que, a partir de un recurso bsico, que en este ejemplo es la mano
de obra, pueden fabricarse diversos productos (escritorios y mesas).
Los parmetros son los valores que describen la relacin entre las variables
de decisin y que permanecen constantes en cada problema, pero varan en
Parmetros. Valores que especifican
problemas distintos. Por ejemplo, las horas de mano de obra que se requieren
la relacin entre las variables de
para elaborar cada uno de estos productos. Supongamos que en la produccin
decisin.
de cada mesa se emplean 6 horas y en la de cada escritorio, 8 horas; en consecuencia, la relacin funcin de mano de obra es la siguiente:
Mano de obra para fabricar los productos
6x1 + 8x2
Si reunimos toda la informacin descrita en una tabla, sta tendra la forma y los contenidos siguientes:
Tabla 2.1 Reunin de datos importantes de una restriccin
Producto
Horas laboradas
Operacin
Total de horas a la
semana
Mesa
6x1 + 8x2
80
Escritorio
02/03/11 01:56 PM
2.3
210x1 + 360x2 = Z,
cuyo propsito principal es maximizar las utilidades que genera la fabricacin de mesas y escritorios.
22 2
2n n
.
.
.
.
.
.
am1x1 + am2x2 ++ amnxn
x1, x2,, xn > 0
<, =, > b1
<, =, > b2
>, =, > bm
(restriccin de no negatividad)
Los pasos bsicos que se deben dar para plantear un problema en trminos de un modelo
de programacin lineal (MPL) son los siguientes:
1. Identificar las variables importantes del problema (variables de decisin) y seleccionar una
notacin adecuada para ellas.
2. Plantear la funcin objetivo en trminos de las variables de decisin.
3. Identificar los recursos limitantes para, de esta manera, plantear cada una de las restricciones.
4. Formular el modelo de acuerdo con la estructura general.
1
Una fbrica de muebles se especializa en la produccin de dos tipos de comedores; cada uno requiere de
un tiempo de construccin y otro diferente de pintura. Un comedor tipo 1 demanda 6 horas de produccin y
8 horas de pintura; en la construccin de un comedor tipo 2 se emplean 12 horas y 4 horas para la pintura.
El departamento de construccin cuenta con 120 horas diarias disponibles mientras que el de pintura slo
dispone de 64 horas. La compaa desea determinar el nmero de unidades de cada tipo de comedor que
debe producir por da, de tal manera que las utilidades totales sean mximas.
La compaa logra una utilidad de $2 000 por cada comedor tipo 1 y $2 400 por cada comedor tipo 2.
Plantee el modelo de programacin lineal (MPL) correspondiente.
Solucin:
Primero deben definirse las variables de decisin que se emplearn.
Sea x1 = nmero de comedores tipo 1 que se deben producir
Sea x2 = nmero de comedores tipo 2 que se deben producir
Cuando se definen las variables debe tomarse en cuenta que, en la mayora de los casos, son numricas, por lo que es importante especificar cules son las cantidades que se deben producir.
En el momento en que nos indican costos o utilidades, es indispensable precisar cuntas variables se
van a utilizar en el problema.
02/03/11 01:56 PM
10
UNIDAD II
Programacin lineal
La frase La compaa obtiene una utilidad de $2 000 por cada comedor tipo 1 y $2 400 por cada comedor
tipo 2 refleja con claridad cuntas variables de decisin se usarn y, a su vez, cul ser la funcin objetivo.
Otro aspecto que debe definirse con claridad es el objetivo del problema que se va a resolver; en este
caso, se tiene:
Objetivo = maximizar utilidades
Por lo tanto, las utilidades totales se obtienen mediante la siguiente ecuacin:
2 000x1 + 2 400x2
sujeta a las restricciones de tiempo disponible para construccin y pintura.
En el caso de la construccin de comedores existe la siguiente restriccin:
6x1 + 12x2 120
Para la pintura, la restriccin es:
8x1 + 4x2 64
Luego de reunir todos los datos y de acuerdo con la estructura general de un MPL, se obtiene lo siguiente:
Maximizar z = 2 000x1 + 2 400x2
Sujeto a:
6x1 + 12x2 120
8x1+ 4x2 64
x1, x2 0
2
Una compaa de zapatos, especialista en la fabricacin de botas, no vende en forma directa al pblico, sino
que lo hace a travs de tiendas al menudeo. Segn las fluctuaciones de los costos de la materia prima la
empresa ha observado que el costo de produccin vara de un mes a otro.
Debido a esas variaciones y a que el costo unitario del manejo y almacenamiento es de $11.00 por
mes, la compaa considera que resulta conveniente fabricar pares de botas dems en algunos meses para
venderlos en meses posteriores.
Los administradores han pronosticado la demanda y los costos de produccin de los siguientes 8 meses. Adems, desean programar la produccin de este periodo para minimizar los costos totales de produccin y almacenamiento, como se muestra en la tabla 2.2.
Tabla 2.2 Costos proyectados por mes
Mes
Demanda pronosticada
360
150 000
420
110 000
380
180 000
400
100 000
350
200 000
390
180 000
370
110 000
410
170 000
02/03/11 01:56 PM
2.3
11
02/03/11 01:56 PM
12
UNIDAD II
Programacin lineal
3
En su proceso de produccin, una pequea empresa que elabora diversos productos qumicos utiliza 3 materiales para elaborar 2 productos, un aditivo y un disolvente.
El aditivo se vende a empresas petroleras y se emplea en la produccin de diesel y otros combustibles
similares. El disolvente se vende a empresas qumicas para elaborar productos de limpieza industrial y para
el hogar. Para formar el aditivo y el disolvente se mezclan las tres materias primas en forma especfica.
La tabla 2.3 muestra que una tonelada de aditivo se obtiene mezclando 37 de 1 000 kg de la materia
prima 1; y 47 de 1 000 kg de la materia prima 3; una tonelada de disolvente se logra con la mezcla de 14 de
7
1 000 kg de la materia prima 1, 25 de 1 000 kg de la materia prima 2 y 20
de 1 000 kg de la materia prima 3.
Debido al deterioro y a la naturaleza del proceso de produccin, cualquier materia prima que no se use
para la produccin actual debe desecharse. La utilidad asciende a $4 000.00 por cada tonelada de aditivo y
a $3 000.00 por cada tonelada de disolvente. Despus de un anlisis de la demanda potencial, la administracin de la empresa ha concluido que cuenta con las siguientes cantidades de materia prima:
Tabla 2.3 Cantidad de kilogramos disponibles de cada materia prima
Materia prima
Materia prima 1
20 000.00 kg
Materia prima 2
5 000.00 kg
Materia prima 3
21 000.00 kg
Materia prima 1
Materia prima 2
Materia prima 3
Aditivo
3
7
4
7
Disolvente
1
4
2
5
7
20
Una vez elaborada la tabla 2.4 se deben definir las variables de decisin que se utilizarn:
Sea: x1 = 1 000 kg de aditivo que se producirn
x2 = 1 000 kg de disolvente que se producirn
Proceso de restricciones:
En el caso de la materia prima 1, la restriccin es:
3
x + 1 x 20 000 kilogramos
7 1 4 2
02/03/11 01:56 PM
2.4
Mtodo grfico
13
El propsito de la empresa es maximizar las utilidades. Por ello, obtiene la funcin objetivo siguiente:
Max Z = 4 000x1 + 3 000x2
La expresin anterior significa que va a ganar $4 000 por cada tonelada de aditivo y $3 000 por cada
tonelada de disolvente.
Por ltimo, agregamos la restriccin de no negatividad:
x1, x2 0
02/03/11 01:56 PM
14
UNIDAD II
Programacin lineal
4. Ubicar el o los puntos factibles que den el mejor valor de la funcin objetivo.
A este punto se le conoce como punto ptimo.
Punto ptimo. Punto factible que
brinda el mejor valor de la funcin
objetivo.
Suponga que x1 es el nmero de sillas tipo 1 que se van a producir y que x2 es el nmero de sillas tipo 2 que
se elaborarn.
Sea el modelo lineal:
Max Z = 4x1 + 3x2
Sujeto a:
2x1 + 3x2 6
3x1 + 2x2 3
2x1 + x2 4
2x1, x2 0
Como primer paso, es necesario determinar el conjunto de soluciones de cada una de las restricciones.
Para obtener el conjunto de soluciones de una desigualdad en el plano cartesiano (R2), primero debemos
considerarlo como una ecuacin con objeto de graficar la recta que limitar al semiplano correspondiente a
la solucin de la desigualdad.
Para la primera restriccin
2x1 + 3x2 6
2x1 + 3x2 = 6
Al quitar la desigualdad
Despejamos a x1 sin tomar en cuenta el valor de x2:
2x1 = 6
x1 =
6
2
3x2 = 6
Se puede observar que x1 = 3 y x2 = 2. La grfica de la restriccin quedara como se muestra en la figura 2.2.
x2
5
4
Va hacia la izquierda
Regin factible
2
1
1
Figura 2.2
x1
Primera restriccin.
02/03/11 01:56 PM
2.4
Mtodo grfico
15
Para saber dnde se ubica la regin factible debe tomarse un valor antes y uno despus del de x1, si es
que existe; de no ser as, podemos tomar x2; es decir, si en este caso el valor de x1 es de 3, se toma el valor de
2 y 4, respectivamente, y se sustituyen en la restriccin 1.
Restriccin 1
2x1 + 3x2 6
3x1 + 2x2 3
3x1 + 2x2 = 3
Al quitar la desigualdad
Luego, despejamos x1 sin tomar en cuenta el valor de x2:
3x1 = 3
x1 =
3
y se obtiene x1 = 1
3
2x2 = 3
3
2.5
2
1.5
1
5 4 3 2 1
Figura 2.3
x1
Segunda restriccin.
Para saber hacia dnde se encuentra la regin factible debe tomarse un valor antes y uno despus del
valor de x1, si es que existe x1; si no se tiene x1 podemos tomar x2, es decir, si en este caso el valor de x1 es de
1, se toma el valor de 2 y 0, respectivamente, y se sustituyen en la restriccin 2.
Restriccin 2
3x1 + 2x2 3
02/03/11 01:56 PM
16
UNIDAD II
Programacin lineal
Restriccin 3
2x1 + x2 4
2x1 + x2 = 4
Eliminamos la desigualdad
Luego despejamos x1 sin tomar en cuenta el valor de x2:
2x1 = 4
x1=
4
y obtenemos que x1 = 2
2
Observe que x1 = 2 y x2 = 4. Por lo tanto, la grfica de la restriccin quedara como muestra la figura 2.4.
x2
5
4
3
2
1
1
Figura 2.4
x1
Tercera restriccin.
Para saber hacia dnde se localiza la regin factible, debe tomarse un valor antes y uno despus del
valor de x1, si es que existe x1; si no es as podemos tomar x2, es decir, si en este caso el valor de x1 es 2, se
toma el valor de 1 y 3, respectivamente, y se sustituyen en la restriccin 3.
Restriccin 3
2x1 + x2 4
02/03/11 01:56 PM
2.4
Mtodo grfico
17
x2
3
5
2
4
1
3
2
1.5
Regin factible
B
A
D
1 1.5 2 3
Figura 2.5
x1
En la grfica pueden observarse cuatro puntos ptimos posibles: A, B, C y D, de los cuales slo se deducen A y D, ya que intersecan el eje x1 y el x2; por otra parte, los valores de los puntos B y C los tenemos que
obtener por medio de un mtodo de resolucin de ecuaciones.
En nuestro ejemplo utilizaremos el mtodo de suma y resta para obtener los valores de los puntos B y C. El
primero de ellos interseca con las restricciones 1 y 2, mientras que el segundo interseca las restricciones 1 y 3.
El punto B tiene el siguiente sistema de ecuaciones, el cual resolveremos por el mtodo de suma y resta:
2x1 + 3x2 = 6 restriccin 1
3x1 + 2x2 = 3 restriccin 2
Como se puede observar slo se tiene que multiplicar por 3 la restriccin 1 y por 2 la restriccin 2 para
poder eliminar una variable, a partir de lo cual se obtiene:
6x1 + 9x2 = 18 (se multiplica por 3)
6x1 + 4x2 = 6 (se multiplica por 2)
Note que no es necesario multiplicar por un valor negativo puesto que ya lo tiene
Despus de multiplicar la restriccin 1 por 3 y la restriccin 2 por 2, se tiene lo siguiente:
6x1 + 9x2 = 18
6x1 + 4x2 = 6
13x2 = 24
De este resultado, si despejamos el valor de x2:
x2 =
24
13
Para encontrar el valor de x1 se sustituye x2 en cualquiera de las dos ecuaciones iniciales. En este caso
sustituiremos el valor en la restriccin 1, despejaremos la variable x1 y, por ltimo, determinaremos el valor
del punto B.
2x1 + 3x2 = 6
2x1 + 3
( 2413 ) = 6
2x1 = 6
2x1 =
6
13
x1 =
3
13
72
13
( 133 , 2413 )
02/03/11 01:56 PM
18
UNIDAD II
Programacin lineal
El punto C tiene el siguiente sistema de ecuaciones, el cual resolveremos por el mtodo de suma y resta:
2x1 + 3x2 = 6 restriccin 1
2x1 + x2 = 4 restriccin 3
Como se puede observar, cualquier restriccin debe multiplicarse por 1, puesto que los dos valores de
x1 son iguales.
2x1 + 3x2 = 6
2x1 + x2 = 4 (1)
Luego de multiplicar la restriccin 3 por 1, se logra lo siguiente:
2x1 + 3x2 = 6
2x1 x2 = 4
2x2 = 2
De este resultado, despejamos el valor de x2 para obtener:
x2 =
2
2
x2 = 1
Ahora, para encontrar el valor de x1 se sustituye x2 en cualquiera de las dos ecuaciones iniciales. En
este caso, sustituiremos el valor en la ecuacin 1, despejaremos la variable x1 y, finalmente, obtendremos
el valor del punto C.
2x1 + 3x2 = 6
2x1 + 3 (1) = 6
2x1 = 6 3
2x1 = 3
x1 =
Luego, el punto queda as: C
( 32 )
( 32 , 1)
Como ya determinamos los valores de los cuatro posibles puntos ptimos, procederemos a obtener la Z
final que satisfaga nuestras expectativas de maximizar utilidades.
Sustituyendo en la funcin objetivo los valores de los puntos A, B, C y D obtenemos:
Z = 4x1 + 3x2
Entonces,
( 32 ) = 92 ) = 4.5
84
3
24
= 6.4615
Z = 4( ) + 3( ) =
13 )
13
13
3
Z = 4( ) + 3(1) = 9
2
ZA = 4(0) + 3
B
ZD = 4(2) + 3(0) = 8
Z Max = 9
Punto ptimo
3
2
02/03/11 01:56 PM
2.5
19
Variable de holgura
Sujeto a: xi + xj s1 = b1
xi + xj + s2 = b2
xi, xj, s1, s2 0
Suponga que usted produce galletas y que gana $6.00 por cada galleta cuadrada y $5.00 por cada galleta
redonda. El modelo del problema se resume a continuacin:
Observe que x1 es el nmero de galletas cuadradas y x2 de galletas redondas unido a la ganancia de cada
galleta.
Max Z = 6x1 = + 5x2
Sujeto a: x1 + x2 9
x1 x2 1
x1, x2 0
Para resolver este problema, en primer lugar debemos convertir la funcin objetivo a la forma estndar.
Cmo se lleva a cabo esta tarea?
La funcin objetivo Max Z = 6x1 + 5x2 deber cambiar de signo; es decir, si son valores negativos, la
funcin tomar valores positivos; y si son valores positivos, la funcin asumir valores negativos, segn sea
el caso. As, tenemos:
Max Z = 6x1 5x2
Continuemos ahora con las restricciones. La primera restriccin x1 + x2 9 debe convertirse a la forma
estndar, el valor de x1 y x2 no cambia. Por lo tanto, queda x1 + x2 = 9, pero tenemos que quitar la desigualdad
agregando una variable de holgura, la cual llamaremos s1, tarea que se debe repetir con cada restriccin; si
la desigualdad de la restriccin es , la variable de holgura tomar un signo positivo, es decir, se suma a la
restriccin y queda de la siguiente forma:
x1 + x2 + s1 = 9
02/03/11 01:56 PM
20
UNIDAD II
Programacin lineal
Ahora, en el caso de la segunda restriccin, la variable de holgura asumir un valor negativo ya que la
desigualdad es y queda de la siguiente forma:
x1 x2 s2 = 1
En la figura 2.6 se muestra la conversin final del modelo a la forma estndar.
Forma original
Forma estndar
Genera
Sujeto a: x1 + x2 9
x1 x2 1
x1, x2 0
Figura 2.6
Sujeto a: x1 + x2 + s1 = 9
x1 x2 s2 = 1
x1, x2, s1, s2 0
El siguiente paso es introducir los valores del modelo de la forma estndar a la tabla smplex.
Nombre que se
les da:
Restriccin 1
Restriccin 2
x1
x2
s1
s2
Solucin
s1
s2
Ya con los valores en la tabla se debe resolver este problema de acuerdo con los siguientes pasos:
Paso 1. Elegir el valor de Z ms negativo.
El valor de Z que se elija indicar la columna que se debe y se llamar columna pivote o columna de
entrada. En la siguiente tabla smplex se muestra cmo se llev a cabo este paso.
Columna de entrada o pivote
x1
x2
s1
s2
Solucin
s1
s2
Ms negativo
En la tabla anterior puede observarse que x1 es la variable de entrada.
Paso 2. Se determina la variable de salida mediante la divisin de la columna solucin de las restricciones entre la columna pivote o de entrada. Recuerde que este procedimiento slo se aplica a las restricciones,
no a la funcin objetivo Z.
02/03/11 01:56 PM
2.5
21
s1
x1
x2
s1
s2
Solucin
9 entre 1 = 9
s2
x1
x2
s1
s2
Solucin
1 entre 1 = 1
Observe que los resultados son 9 y 1, por lo que se elige el valor positivo ms pequeo sin tomar en
cuenta valores negativos o ceros.
x1
x2
s1
s2
Solucin
s1
9/1 = 9
s2
1/1 = 1
Aqu se observa que s2 es la variable que debe salir y la que entra es x1.
Paso 3. A la interseccin entre la columna de entrada y el rengln de salida se le llama pivote.
x1
s2
Pivote
Paso 4. Es muy importante que el pivote tome el valor 1; si ste no tiene dicho valor, convirtalo a 1
dividiendo todo el rengln entre el valor del pivote.
En este caso, el pivote ya es 1; por lo tanto, el rengln queda igual.
Paso 5. Hacer ceros los dems valores de la columna de entrada o pivote cambiado slo el nombre de
la restriccin de s2 a x1.
Columna de entrada o pivote
Note el
cambio del
nombre de la
variable
x1
x2
s1
s2
Solucin
s1
s1
x1
Pivote
x1
Pivote
Convertirlos
en ceros
02/03/11 01:56 PM
22
UNIDAD II
Programacin lineal
En primer trmino, se tiene que multiplicar el rengln x1 por el inverso del valor que se har cero y sumrselo al rengln que desea convertirse; es decir, si queremos hacer cero al 1, multiplicamos al rengln x1
por 1, que es el inverso de 1 y el resultado se lo sumamos a s1.
x1
x2
s1
s2
Solucin
s1
x1
(1)(pivote)
(1)(1) = 1 + 1 = 0
Valor buscado
x2
s1
s2
Solucin
s1
x1
Ya es cero
(1)(1) = 1 + 1 = 2
(1)(0) = 0 + 1 = 1
(1)(1) = 1 + 0 = 1
(1)(1) = 1 + 9 = 8
Una vez terminado el rengln s1, continuamos con el rengln Z multiplicando al rengln x1 por 6 ya que
es el inverso de 6. Adems, el rengln x1 es el que tiene el pivote.
x1
x2
s1
s2
Solucin
x1
Inverso de 6
6* 1
6* 1
6* 0
6*1
6* 1
Multiplicar por 6
y sumar a Z
= 6 + (6) = 0
= 6 + (5) = 11
=0+0=0
= 6 + 0 = 6
=6+0=6
lo cual genera:
x1
x2
s1
s2
Solucin
x1
11
Note que ya
son ceros
x1
x2
s1
s2
Solucin
s1
x1
11
02/03/11 01:56 PM
2.5
23
Paso 6. Si en el rengln de Z an existen valores negativos, regrese al paso 1, hasta que el rengln Z no
tenga valores negativos.
Como el rengln Z todava tiene valores negativos, regresamos al paso 1, el cual indica que se tiene que
elegir el mayor valor negativo. En este caso, se tienen 2 valores, 11 y 6, y el valor que elegimos es 11.
La nueva columna entrante es:
Nueva columna de entrada o pivote
x1
x2
s1
s2
Solucin
s1
x2
11
8 =4
2
1 = 1
1
Rengln elegido
No se toma en
cuenta ya que
es negativo
Pivote
En este punto ya se han definido todas las variables; la variable que entra es x2 y la que sale es s1. Ahora, debemos realizar nuevamente las operaciones correspondientes y hacer que el rengln pivote tenga un
valor de 1 y los dems valores de la columna de entrada o pivote tengan valores de 0.
En primer lugar, debe convertirse el rengln pivote en 1. Se divide todo el rengln entre 2.
Cambi de s1 a x2
x2
x1
x2
s1
s2
Solucin
0/2 = 0
2/2 = 1
1
2
1
2
8
2
=
=
1
2
1
2
0
=0
2
2
=1
2
1 1
=
2 2
1 1
=
2 2
8
=4
2
=4
A continuacin se introducen los valores que obtuvimos para ubicarlos en el rengln pivote, lo que genera:
x2
x1
x2
s1
s2
Solucin
1
2
1
2
Pivote
x1
11
Valores a
convertir
en ceros
En seguida, se debe multiplicar al rengln x2 por el inverso de cada valor que se convertir en cero y
sumrselo al rengln que se desea convertir; es decir, si queremos hacer cero al 1, debemos multiplicar el
rengln x1 por 1 y sumrselo al rengln x1.
02/03/11 01:56 PM
24
UNIDAD II
Programacin lineal
x1
x2
s1
s2
Solucin
x2
1
2
1
2
x1
1* 0
1* 1
1*
1*
=0+1=1
= 1 + (1) = 0
1
2
1
2
1
2
1
2
+0=
1
= 2 + (1) = 2
1* 4
=4+1=5
x2
s1
s2
Solucin
x2
1
2
1
2
x1
1
2
1
2
Una vez terminado el rengln x1, continuamos con el rengln Z multiplicando al rengln x2 por 11 ya que
es el inverso de 11.
x1
x2
s1
s2
Solucin
x2
1
2
1
2
11
11* 0
11* 1
11*
11*
Multiplicar por 11
y sumrselo a Z
=0+0=0
= 11+ (11) = 0
1
2
1
2
=
=
11* 4
11
2
11
2
+0=
11
2
1
+ 6 = 2
= 44 + 6 = 50
x2
s1
s2
Solucin
x2
1
2
1
2
11
2
1
2
50
Note que ya
son ceros
x1
x2
s1
s2
Solucin
x2
1
2
1
2
x1
1
2
1
2
11
2
1
2
50
02/03/11 01:56 PM
2.5
25
Como podemos observar, an tenemos valores negativos en el rengln Z; por lo tanto, tenemos que
realizar de nueva cuenta las operaciones correspondientes hasta lograr que el rengln Z no tenga ningn
valor negativo.
Columna de entrada o pivote
x1
x2
s1
s2
Solucin
x2
1
2
1
2
4/
x1
1
2
1
2
5/
11
2
1
2
50
Rengln
elegido
1
=8
2
1
= 10
2
Pivote
1
En principio, debemos ubicar las variables de entrada que, en este caso, es s2, que tiene el valor de 2 ;
ste es el nico valor negativo que queda en el rengln Z.
1
El rengln de salida es x2 y el pivote es 2 .
Con base en el regln pivote, debemos hacer que el pivote tenga el valor 1 y los dems valores que
componen la columna de entrada o pivote obtengan valores de 0.
1
Para convertir el rengln pivote en 1 es necesario dividir el rengln pivote entre 2 . Queda como sigue:
x2
0/
1
2
=0
1/
1
2
=2
1
2
1
2
1
2
1
2
4/
1
2
x1
x2
s1
s2
Solucin
1
2
1
2
=1
0
1
2
=1
=0
1
2
1
2
1
2
=2
1
2
1
2
=1
=1
4
1
2
=8
=8
x2
x1
x2
s1
s2
Solucin
Pivote
Note que ya cambi a 1
El siguiente paso implica convertir a ceros los valores de la columna de entrada o pivote utilizando el
pivote para hacerlo:
x2
x1
Z
Pivote
1
2
1
Valores a
convertir
en ceros
02/03/11 01:56 PM
26
UNIDAD II
Programacin lineal
En seguida, debe multiplicarse al rengln x2 por el inverso de los valores que se harn cero y sumrselos
1
al rengln que se convertir; es decir, si queremos hacer cero al 2 , entonces debemos multiplicar el rengln
1
x2 por 2 y sumarlo a x1.
1
2
1
2
1
2
1
2
1
2
x1
x2
s1
s2
Solucin
s2
x1
1
2
1
2
Multiplicar por
y sumar a x1
1
2
*0=0+1=1
*2=1+0=1
*1=
*1=
1
2
1
2
1
2
+ (
=1
1
2
)= 0
*8=4+5=9
x2
s1
s2
Solucin
s2
x1
1
2
1
2
1
2
1
2
1
2
x1
x2
s1
s2
Solucin
s2
11
2
1
2
Multiplicar por
y sumar a Z
1
2
ya que es el
1
2
50
*0=0+0=0
*2=1+0=1
*1 =
*1 =
1
2
1
2
11
2
+ (
=6
1
2
)=0
*8 = 4 + 50 = 54
Aqu se genera:
x1
x2
s1
s2
Solucin
s2
54
02/03/11 01:56 PM
2.5
27
x2
s1
s2
Solucin
s2
x1
54
Como se puede observar esta tabla smplex no incluye valores negativos en Z, lo cual indica que el
problema ha sido resuelto.
Cuando no aparece una de las variables bsicas (x1 y x2) en la tabla smplex final, se supone que es igual
a cero. Ahora, slo nos queda resumir los resultados que obtuvimos y dar una conclusin:
x1 = 9
x2 = 0
Z = 54
Como conclusin, puede decirse que deben fabricarse 9 galletas de tipo cuadrada y 0 de tipo redonda,
pues esas cantidades generan una utilidad mxima de $54.00.
Para asegurarnos de que realizamos las operaciones adecuadas, puede hacerse una comprobacin en
cualquiera de las ecuaciones del problema. Vamos a llevarla a cabo en la funcin objetivo original para verificar.
Max Z = 6x1 + 5x2
54 = 6 * 9 + 5 * 0
54 = 54
Hemos finalizado todo el procedimiento por el mtodo smplex.
2
Max Z = 5x1 + 2x2
Forma estndar
Max Z = 5x1 2x2
Sujeto a: 6x1+10x2 30
10x1 + 4x2 20
x1, x2 0
x2
s1
s2
Solucin
s1
10
30
s2
10
20
x1
x2
s1
s2
Solucin
s1
10
30
s2
10
20
30 = 5
6
20
=2
10
Rengln
elegido
02/03/11 01:56 PM
28
UNIDAD II
Programacin lineal
Hasta este momento hemos definido todas las variables; la que entra es x1 y la que sale es s2. Ahora
tenemos que realizar de nueva cuenta las operaciones correspondientes y hacer que el rengln pivote tenga
un valor de 1 y los dems valores de la columna de entrada o pivote posean valores de 0.
Para empezar, debemos convertir el rengln pivote en 1 mediante la divisin de todo el rengln entre 10,
que es el mismo valor del pivote.
x1
10
10
4
10
0
10
1
10
20
10
x1
x2
s1
s2
Solucin
10
20
=1
Cambi de s2 a x1
= 2
5
=0
= 1
10
=2
A continuacin, introducimos los valores que obtuvimos para ubicarlos en el rengln pivote, con lo cual
la tabla queda as:
Note que ya
cambi a 1
x1
x1
x2
s1
s2
Solucin
2
5
1
10
Luego convertimos a ceros los valores de la columna de entrada o pivote usando el pivote para hacerlo:
s1
x1
Pivote
Valores a
convertir
en ceros
A continuacin debe multiplicarse el rengln x1 por el inverso de cada valor que se transformar en cero
y sumarlo al rengln que se convertir.
x1
x2
s1
s2
Solucin
s1
10
30
x1
2
5
1
10
Multiplicar por 6
y sumar a s1
6 * 1 = 6 + 6 = 0
6 *
2
= 12 + 10 = 38
5
5
5
6 * 0 = 0 + 1 =1
6 *
1
3
3
= +0=
10
5
5
6 * 2 = 12 + 30 = 18
02/03/11 01:56 PM
2.5
29
El resultado es el siguiente:
x1
s1
x1
x2
38
5
2
5
s1
1
0
Solucin
s2
3
5
1
10
18
2
Una vez que hemos resuelto el rengln x1, continuamos con el rengln Z. Ahora debemos multiplicar el
rengln x2 por 11 ya que es la inversa de 11.
x1
x2
s1
s2
Solucin
x1
2
5
1
10
s2
Solucin
Multiplicar por 5
y sumarlo a Z
5 * 1 = 5 + (5) = 0
5*
2
= 2+ (2) = 0
5
5*0=0+0=0
5*
1
1
1
= +0=
10 2
2
5 * 2 = 10 + 0 = 10
Esta operacin genera:
x1
x2
s1
s1
2
5
1
10
1
2
2
10
Note que ya
son ceros
x2
x1
x2
38
5
2
5
0
s1
1
0
0
s2
3
5
1
10
1
2
Solucin
18
2
10
Como se puede ver, esta tabla smplex no tiene valores negativos en el rengln Z, lo cual nos indica que
hemos terminado. Ahora slo nos queda resumir los resultados que obtuvimos:
s1 = 18; x1 = 2; s2 = 0; x2 = 0 y Z = 10.
A continuacin, podemos hacer una comprobacin en cualquiera de las ecuaciones del problema para
asegurarnos de que efectuamos las operaciones adecuadas. Para llevarla a cabo vamos a verificar la funcin
objetivo original.
Max Z = 5x1 + 2x2
10 = 5(2) + 2(0)
10 = 10
Hemos finalizado todo el procedimiento por el mtodo smplex.
02/03/11 01:56 PM
30
UNIDAD II
Programacin lineal
3
Max Z = 3x1 + x2
Forma estndar
Max Z = 3x1 x2
Sujeto a: 2x1+ x2 8
2x1 + 3x2 12
x1, x2 0
Sujeto a: 2x1 + x2 + s1 = 8
2x1 + 3x2 + s2 = 12
x1, x2, s1, s2 0
x2
s1
s2
Solucin
s1
s2
12
x1
x2
s1
s2
Solucin
s1
s2
12
8
=4
2
12
=6
2
Rengln
elegido
Hasta este punto hemos definido todas las variables: la que entra es x1 y la que sale es s1; ahora debemos efectuar de nuevo las operaciones correspondientes y hacer que el rengln pivote tenga un valor de 1 y
los dems valores de la columna de entrada o pivote tengan valores de 0.
Para empezar debemos convertir el rengln pivote en 1 mediante la divisin de todo el rengln entre 2,
que es el mismo valor del pivote.
Cambi de s1 a x1
2
2
1
2
1
2
0
2
8
2
x1
x1
x2
s1
s2
Solucin
=1
1
2
1
=
2
=0
=4
Luego de la divisin, introducimos los valores que obtuvimos para ubicarlos en el rengln pivote, actividad que genera la siguiente tabla:
x1
x1
x2
s1
s2
Solucin
1
2
1
2
02/03/11 01:56 PM
2.5
31
Para convertir a ceros los valores de la columna de entrada o pivote, utilizamos el pivote:
x1
Pivote
s2
Valores a
convertir
en ceros
A continuacin debe multiplicarse el rengln x1 por el inverso de cada valor que se transformar en cero
y sumarlo al rengln que se convertir.
x1
x2
s1
s2
Solucin
x1
1
2
1
2
s2
12
Multiplicar por 2
y sumar a s2
2 * 1 = 2 + 2 = 0
1
= 1 + 3 = 2
2
1
2 * = 1 + 0 = 1
2
2 *
2 * 0 = 0 + 1 = 1
2 * 4 = 8 + 12 = 4
La tabla que se obtiene ser:
x1
x2
s1
s2
Solucin
x1
1
2
1
2
s2
Una vez resuelto el rengln x1 continuamos con el rengln Z multiplicando al rengln x1 por 3, ya que es
el inverso de 3.
x1
x2
s1
s2
Solucin
x1
1
2
1
2
Multiplicar por 3
y sumar a Z
3 * 1 = 3 + (3) = 0
1
3
1
= + (1) =
2
2
2
1
3
3
3* = +0=
2
2
2
3*
3*0=0+0=0
3 * 4 = 12 + 0 = 12
02/03/11 01:56 PM
32
UNIDAD II
Programacin lineal
x2
s1
s2
Solucin
x1
1
2
1
2
1
2
3
2
12
x2
s1
s2
Solucin
x1
1
2
1
2
s2
1
2
3
2
12
Como podemos observar, en esta tabla smplex no hay ningn valor negativo en el rengln Z, lo cual nos
indica que hemos concluido. Ahora, slo nos queda resumir los resultados que obtuvimos, a saber:
s1 = 0; x1 = 4; s2 = 4; x2 = 0 y Z = 12.
Ahora podemos hacer una comprobacin en cualquiera de las ecuaciones del problema para asegurarnos
de que efectuamos las operaciones adecuadas; para verificar, nos enfocaremos en la funcin objetivo original.
Max Z = 3x1 + x2
12 = 3(4) + 0
12 = 12
Hemos finalizado todo el procedimiento que seala el mtodo smplex.
2.6 Dualidad
El trmino dualidad seala la existencia de dos fenmenos o caracteres diferentes en un mismo
estado. En este sentido, las nociones del bien y el mal son un ejemplo de dualidad; la filosofa
china tambin cuenta con los conceptos del yin y el yang para resumir la dualidad de todo lo
que existe en el universo.
Dentro de la investigacin de operaciones, el concepto de dualidad desempea un papel
importante tanto en la teora como en la prctica. Todo modelo de programacin lineal est
asociado a otro modelo llamado modelo dual; al modelo de programacin inicial tambin se le
conoce como modelo primal.
Entre otras cosas, las estructuras duales permiten:
Resolver problemas lineales que tienen ms restricciones que actividades. Por ejemplo, el
grado de dificultad para resolver un programa lineal por medio de una computadora que
est en funcin del nmero de filas de la matriz A y no en el nmero de columnas, al aplicar
la dualidad a un problema primario donde m > n, se obtiene otro problema lineal donde
el nmero de columnas m < n. Una vez que se resuelve el problema primario, de manera
automtica se soluciona su correspondiente dual o viceversa.
Hacer interpretaciones econmicas de las soluciones ptimas de los problemas de programacin lineal.
02/03/11 01:56 PM
2.6
Dualidad
33
A=
1
2
15
20
25
10
30
40
Genera
AT =
15
10
20
30
25
40
Min
Cuestin 2. Los coeficientes de la funcin objetivo del problema primal se convierten en los
coeficientes del vector de disponibilidad del problema dual.
Cuestin 3. Los coeficientes del vector de disponibilidad del problema original se convierten
en los coeficientes de la funcin objetivo (vector de costo o precio) del problema dual.
Cuestin 4. Los coeficientes de las restricciones del problema primal sern la matriz de coeficientes del dual.
Cuestin 5. Los signos de desigualdad del problema dual son contrarios a los del primal.
Cuestin 6. Si el primal tiene m restricciones y n variables, el dual tendr n restricciones y
m variables. As, las variables xn del primal se convierten en nuevas variables ym del dual.
Primal
Max Z = Cx
Sujeto a: Ax B
x0
Dual
Min G = BT y
Sujeto a : AT y > CT
y>0
Donde:
C = constante
x = variable
Cx = funcin objetivo
En la figura 2.7 se ilustra quin es A; B; C para, posteriormente, convertirse en su dual.
Primal
Max Z =
C
5x1 + 12x2 + 4x3
A
x1 0
Figura 2.7
02/03/11 01:56 PM
34
UNIDAD II
Programacin lineal
Primal
Dual
Sujeto a: x1 + 2x2 3
2x1 4x2 5
xi 0
Sujeto a: y1 + 2y2 15
2y1 4y2 12
yi 0
2
Dual
Primal
Min Z =
x1 + 3x2 + 2x3
Cabe destacar que, una vez solucionados el dual como el primal por medio del mtodo smplex, la solucin es la misma.
Sujeto a:
7x1 + 3x2 15
3x1 + x2 20
x1 + x2 5
x1, x2 0
Sujeto a:
x1 + 3x2 9
3x1 + 2x2 12
x1, x2 0
Sujeto a:
2x1 + 2x2 150
x1 + 2x2 120
x1, x2 0
Sujeto a:
7x1 + 3x2 x3 15
2x1 2x2 + 3x3 20
x1 + x2 + x3 5
x1, x2, x3 0
Sujeto a:
2x1 x2 + 2x3 2
x1 + 4x3 4
x1, x2, x3 0
02/03/11 01:56 PM
Unidad
III
Transporte
y asignacin
Al finalizar el estudio de esta unidad, se espera que el lector sea capaz de:
explicar qu entiende por modelos de transporte.
desarrollar los pasos para resolver problemas de transporte.
resolver problemas por el mtodo de la esquina noroeste.
solucionar problemas por medio del mtodo de costo menor.
resolver problemas por medio del mtodo Vogel.
exponer el modelo de asignacin.
solucionar problemas de asignacin por medio del mtodo hngaro.
Figura 3.1
a1
a2
am
c11 x11
cmn xmn
b1
b2
bn
Demanda
Oferta
El modelo de transporte es una clase especial de programacin lineal que aborda la situacin en la cual se enva un bien desde los puntos de origen (por ejemplo, fbricas) hasta los puntos de destino (bodegas). El objetivo es determinar
las cantidades que se deben enviar desde cada punto de origen hasta cada punto
de destino que minimicen el costo total del envo y que, al mismo tiempo, satisfagan tanto los lmites de la oferta como los requisitos de la demanda (figura 3.1).
02/03/11 01:57 PM
36
UNIDAD III
Transporte y asignacin
El modelo supone que el costo de envo por una ruta especfica es directamente proporcional al nmero de unidades enviadas (por esa ruta). En general, el modelo de transporte puede
ampliarse a otras reas, entre ellas el control de inventarios, horarios de empleo y asignacin
de personal.
A partir de la figura 3.1 se deduce que:
xij = Cantidad enviada
cij = Constante.
La funcin objetivo se obtiene de la siguiente forma:
Min Z = c11 x11 + c12 x12 ++ cij xij
Una fbrica de autos cuenta con 3 plantas fabriles, una en Guanajuato, otra en Michoacn y otra en Nayarit.
Tambin posee 2 centros de distribucin principales, uno en Mxico y otro en Guadalajara. Las capacidades de produccin de las 3 plantas durante el prximo trimestre son de 2 000, 2 400 y 3 000 automviles,
mientras que la demanda durante el mismo periodo de los 2 centros de distribucin ser de 4 600 y 2 800
automviles.
La tabla 3.1 proporciona la distancia en kilmetros que existe entre las plantas y los centros de distribucin.
Tabla 3.1 Distancia entre plantas y centros de distribucin
Origen
Destino
Guanajuato
2 000
5 380
Michoacn
2 500
2 700
Nayarit
2 550
1 700
La compaa encargada del transporte de los automviles cobra 16 centavos por kilmetro por auto.
Para obtener el costo de envo por cada ruta, debe multiplicarse la distancia por el costo de transporte
que, en este caso, ser de 16 centavos por kilmetro.
Origen
Destino
Mxico
Guadalajara
Guanajuato
2 000 0.16
5 380 0.16
Michoacn
2 500 0.16
2 700 0.16
Nayarit
2 550 0.16
1 700 0.16
Destino
Mxico
Guadalajara
Guanajuato
320
860.8
Michoacn
400
432
Nayarit
408
272
Dado que la tabla de costos puede resolverse por medio del mtodo smplex, elabore el modelo de programacin lineal correspondiente al problema (vase figura 3.2).
02/03/11 01:57 PM
3.1
Guanajuato
320x11
860.8x12
Mxico
Guadalajara
Modelos de transporte
37
400x21
Michoacn
432x22
2
408x31
Figura 3.2
272x32
Nayarit
Sea xij = Nmero de automviles enviados del origen (i) al destino (j).
Donde:
i = Origen (Guanajuato, Michoacn, Nayarit)
j = Destino (Mxico, Guadalajara)
Origen
Destino
Mxico
Guadalajara
Oferta
Guanajuato
320 x11
860.8 x12
2 000
2 000 +
Michoacn
400 x21
432 x22
3 000
3 000 +
Nayarit
408 x31
272 x32
2 400
2 400 =
Demanda
4 600
2 800
7 400
7 400
4 600 +
2 800 =
7 400
Ntese que la demanda
es igual a la oferta
Oferta
Demanda
xij 0
El modelo de programacin lineal puede resolverse con el mtodo smplex; sin embargo, la
estructura especial de las restricciones nos permite solucionarlo de una manera ms conveniente con ayuda de la tabla smplex de transporte que se muestra a continuacin:
Origen
Destino
Guadalajara
Oferta
Guanajuato
320
860.8
2 000
Michoacn
400
432
3 000
Nayarit
408
272
2 400
4 600
2 800
7 400
Demanda
Mxico
02/03/11 01:57 PM
38
UNIDAD III
Transporte y asignacin
Figura 3.3
2
Tenemos 3 granjas de pollos (A, B, C) con una oferta de 120, 130 y 250 pollos cada una, que deben cubrir la
demanda de 3 rosticeras (1, 2, 3) que es de 150, 130 y 220 pollos.
Los costos de envo de la granja A a las rosticeras 1, 2 y 3 son de 10, 15 y 18 pesos por pollo; los de la
granja B son de 1, 5 y 3 pesos y los de la granja C son de 7, 11 y 9 pesos, respectivamente, por pollo.
Elabore el modelo de programacin lineal correspondiente y determine cuntos pollos se deben enviar
desde las granjas (A, B, C) a las rosticeras (1, 2, 3).
02/03/11 01:57 PM
3.1
Rosticera
10
15
18
120
130
11
250
150
130
220
500
Granjas
Demanda (pollos)
Modelos de transporte
39
Oferta (pollos)
Por lo tanto, como la oferta es igual a la demanda, se dice que la tabla est en equilibrio.
Paso 1. Para resolver este problema, en primer lugar se debe asignar tanto como sea posible al cuadro de la
esquina noroeste seleccionado (en este caso sera A, 1) y ajustar las cantidades asociadas de oferta y demanda
mediante la resta de la cantidad asignada.
Rosticera
10
15
18
120
130
11
250
150
130
220
500
Granjas
Demanda (pollos)
Oferta (pollos)
Enviamos 120 pollos a la rosticera 1 que pide 150, con lo cual slo quedan por satisfacer 30 pollos.
Rosticera
Granjas
A
1
10
120
Oferta (pollos)
15
18
120 120 = 0
130
11
250
Demanda (pollos)
150 120 = 30
130
220
380
Observe que, al entregar 120 pollos, la granja A ya no puede vender ms, por lo que se cancelan los dems
espacios.
Paso 2. Tache el rengln o la columna con 0 oferta o demanda para indicar que no pueden hacerse asignaciones adicionales en ese rengln o columna. Si tanto el rengln como la columna, de manera simultnea, dan 0,
tache slo uno de ellos y deje una oferta o demanda de 0 en el rengln o columna no tachados.
02/03/11 01:57 PM
40
UNIDAD III
Se tacha porque se
agota la oferta de la
granja A
Transporte y asignacin
Rosticera
Granjas
10
120
Oferta (pollos)
15
18
120 120 = 0
130
11
250
Demanda (pollos)
150 120 = 30
130
220
380
Paso 3. Si queda sin tachar un rengln o una columna, detngase; de lo contrario, avance al siguiente
cuadro a la derecha si acaba de tachar una columna o al inferior si ha tachado un rengln. Regrese al paso 1.
Como se tach el rengln de la granja A, avanzamos a la siguiente esquina noroeste para satisfacer los
30 pollos que solicita la rosticera 1.
Se tacha porque se
agota la oferta de la
granja A
Rosticera
Granjas
10
120
Oferta (pollos)
15
18
120 120 = 0
130
11
250
Demanda (pollos)
150 120 = 30
130
220
380
Se le asignan 30
ya que la rosticera
1 slo pide 30 y la
granja B tiene 30
disponibles
Se tacha porque
satisface la
demanda de la
rosticera 1
Rosticera
Granjas
Oferta (pollos)
10
120
15
18
11
30
130 30 = 100
11
250
Demanda (pollos)
30 30 = 0
130
220
350
100 pollos
disponibles
que oferta la
granja B
Ahora, la granja A no tiene pollos para vender y la rosticera 1 cubri su demanda. Se avanza a la siguiente rosticera (2) y se le asigna lo ms que se pueda a la granja B.
Rosticera
Granjas
Oferta (pollos)
18
100 100 = 0
10
120
15
11
30
100
11
250
Demanda (pollos)
130 100 = 30
220
250
Se tacha
porque se
agota la
oferta de la
granja B
02/03/11 01:57 PM
3.1
Modelos de transporte
41
La rosticera 2 an necesita 30 pollos, que deben ser proporcionados por la granja C ya que la B agot
su oferta.
Rosticera
Granjas
10
120
11
30
Oferta (pollos)
15
18
250 30 = 220
220
220
100
11
Demanda (pollos)
30 30 = 0
Siguiente esquina
noroeste
No tiene demanda
Rosticera
Granjas
30
10
120
11
30
Demanda (pollos)
No tienen
oferta
Oferta (pollos)
15
18
Oferta
satisfecha
100
11
30
250 30 = 220
220
220
Demanda satisfecha
Debido a que la demanda de la rosticera 2 ya fue satisfecha, se tacha y se avanza a la siguiente rosticera.
Rosticera
Granjas
10
120
11
30
Demanda (pollos)
Oferta (pollos)
15
18
100
11
30
220
220 220 = 0
220 220 = 0
Este punto
es donde se
satisface por
completo la
demanda con la
oferta
A
Granjas de
pollos
30
B
Figura 3.4
100
30
220
Rosticeras
02/03/11 01:57 PM
42
UNIDAD III
Transporte y asignacin
3
Para este tema, retomaremos el ejercicio que se trabaj en la seccin anterior (mtodo de la esquina noroeste).
Tenemos 3 granjas (A, B, C), con una oferta de 120, 130 y 250 pollos, respectivamente, que deben cubrir la demanda de 3 rosticeras (1, 2, 3), que es de 150, 130 y 220 pollos.
Costos de envo de
pollos de las granjas
a las rosticeras
Ejemplo: de la granja
B a la rosticera 2, el
costo de envo por
pollo es de 5 pesos
Rosticera
Oferta (pollos)
10
15
18
120
130
11
250
150
130
220
500
Granjas
Demanda (pollos)
Nota: La oferta
no puede ser
mayor que la
demanda
Paso 1. Asgnele tanto como sea posible al cuadro con el menor costo unitario de toda la tabla y ajuste
las cantidades asociadas de oferta y demanda mediante la resta de la cantidad asignada.
Rosticera
Oferta (pollos)
10
15
18
120
130
11
250
150
130
220
Granjas
Demanda (pollos)
02/03/11 01:57 PM
3.1
Modelos de transporte
43
Paso 2. Tache el rengln o la columna con 0 oferta o demanda para indicar que no pueden hacerse asignaciones adicionales en ellos. Si tanto el rengln como la columna dan 0 de manera simultnea, tache slo
uno de ellos y deje una oferta o demanda de 0 en el rengln o columna no tachados.
Rosticera
Granjas
A
B
Oferta (pollos)
10
15
18
120
130 130 = 0
250
130
11
Demanda (pollos)
150 130 = 20
130
220
Oferta (pollos)
10
15
18
120
Rosticera
Granjas
A
B
130
20
11
250 20 = 230
130
220
370 20 = 350
Demanda (pollos)
20 20 = 0
Rosticera
Granjas
A
Oferta (pollos)
10
15
18
120
130
20
11
Demanda (pollos)
130
Rosticera
A
230 220 = 10
350 220 = 130
Oferta (pollos)
10
15
18
120
130
20
Demanda (pollos)
220
220 220 = 0
Granjas
Se tacha porque se
agota la oferta de la
granja B
11
10
130 10 = 120
220
10 10 = 0
Se tacha porque se
agota la oferta de la
granja B
130 10 = 120
02/03/11 01:57 PM
44
UNIDAD III
Transporte y asignacin
Paso 3. Si queda sin tachar un rengln o una columna, detngase; de lo contrario, avance al siguiente
cuadro con el costo ms bajo por unidad de la tabla no tachada. Regrese al paso 1.
Rosticera
Granjas
10
15
11
130
20
Demanda (pollos)
120
5
11
10
120 120 = 0
Oferta (pollos)
18
120 120 = 0
0
0
220
120 120 = 0
4
Tres fbricas de calzado (1, 2, 3) con una oferta de 15, 25 y 10 mil pares de zapatos, respectivamente, deben
cubrir los pedidos de 4 tiendas (A, B, C, D), cuyas demandas ascienden a 5, 15, 15 y 15 mil pares de zapatos
cada una.
Elabore el modelo de programacin lineal correspondiente y determine cuntos pares de zapatos se
van a enviar desde las fbricas (1, 2, 3) a cada una de las tiendas (A, B, C, D).
Tienda
Fbrica
Oferta (miles)
20
11
15 15 = 0
10
12
20
25
14
16
18
10
Demanda
15
15
15
50 15 = 35
Oferta (miles)
20
11
Tienda
Fbrica
C
15
10
12
20
25
14
16
18
10 5 = 5
15
15
35 5 = 30
3
Demanda
55=0
15
La oferta de
la fila 1 llega
al lmite
02/03/11 01:57 PM
3.1
Tienda
Fbrica
Oferta (miles)
10
15
20
11
15 15 = 0
12
20
25
14
16
18
10
15 15 = 0
15
15
30
Demanda
Modelos de transporte
45
Fbrica
10
15
12
Demanda
Oferta (miles)
20
11
20
25 15 = 10
15
14
16
18
10 5 = 5
15 15 = 0
15
30 15 = 15
Fbrica
10
12
Demanda
B
2
20
15
16
11
10
20
15
14
Oferta (miles)
18
15 15 = 0
25 15 = 10
15 5 = 10
55=0
15 5 = 10
Fbrica
10
15
12
3
Demanda
20
9
15
14
16
11
Oferta (miles)
10
20
18
0
10 10 = 0
10 10 = 0
Llega al lmite
La oferta de la fila 3
0
10 10 = 0
02/03/11 01:57 PM
46
UNIDAD III
Transporte y asignacin
Tienda
Fbrica
10
15
12
Demanda
20
9
11
16
10
20
15
14
Oferta (miles)
18
0
0
5
Para explicar este tema se retomarn los ejercicios que se trabajaron en las dos secciones anteriores (mtodo de la esquina noroeste y mtodo del costo menor) para, al final, poder hacer una comparacin entre los
mtodos que se utilizaron.
Tres granjas de pollos (A, B, C), con una oferta de 120, 130 y 250, respectivamente, deben cubrir la
demanda de 3 rosticeras (1, 2, 3) que es de 150, 130 y 220 pollos.
Rosticera
Oferta pollos
10
15
18
120
130
11
250
150
130
220
500
Granjas
Demanda (pollos)
Costos de envo de
pollos de las granjas
a las rosticeras
02/03/11 01:57 PM
3.1
Modelos de transporte
47
Paso 1. En el caso de cada rengln o columna con una oferta o una demanda estrictamente positiva,
establezca una medida de penalidad mediante la resta del elemento de menor costo unitario del rengln o
columna del siguiente elemento de costo ms bajo.
Rosticera
Oferta (pollos)
Penalidad 1
10
15
18
120
15 10 = 5
130
31=2
11
250
97=2
Demanda (pollos)
150
130
220
380
Penalidad 1
71=6
11 5 = 6
93=6
Granjas
Costos ms bajos
por rengln y
columna
Paso 2. Identifique el rengln o columna con penalidad ms grande y asgnele tanto como sea posible a
la variable con el costo ms bajo. Ajuste la oferta y demanda y tache el rengln o columna satisfechos; si se
satisfacen de manera simultnea un rengln y una columna, slo se tacha uno de ellos.
En esta tabla se puede observar que la mayor penalidad es 6 en 3 diferentes lugares; por ello, debemos
elegir slo una de las tres posibilidades y buscar el costo menor de estas tres.
Se elige esta columna pues el costo menor elegido es 1, mientras
que los dems son 5 y 3, aunque las penalidades sean 6
Rosticera
Oferta (pollos)
Penalidad 1
10
15
18
120
15 10 = 5
130
31=2
11
250
97=2
Demanda (pollos)
150
130
220
380
Penalidad 1
71=6
11 5 = 6
93=6
Granjas
Despus de elegir el costo menor (1), se le asigna lo ms que se pueda al rengln elegido (B); en este
caso, 130 de los 150 pollos que se piden.
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 1
10
15
18
120
15 10 = 5
130
31=2
97=2
130
11
250
Demanda (pollos)
150
130
220
380
Penalidad 1
71=6
11 5 = 6
93=6
02/03/11 01:57 PM
48
UNIDAD III
Transporte y asignacin
Ya asignada la cantidad de 130, se ajustan las cantidades de oferta y demanda como se muestra a
continuacin.
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 1
10
15
18
120
15 10 = 5
130 130 = 0
31=2
97=2
130
11
250
Demanda (pollos)
150 130 = 20
130
220
380
Penalidad 1
71=6
11 5 = 6
93=6
Luego, se tachan los renglones o columnas satisfechos con cero oferta o cero demanda.
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 1
10
15
18
120
15 10 = 5
130 130 = 0
31=2
97=2
130
11
250
Demanda (pollos)
150 130 = 20
130
220
380
Penalidad 1
71=6
11 5 = 6
93=6
La siguiente etapa implica regresar al paso 1 y encontrar otra penalidad (penalidad 2) mediante la resta
de los dos valores ms pequeos por rengln y por columna.
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 2
10
15
18
120
15 10 = 5
130 130 = 0
130
11
250
Demanda (pollos)
150 130 = 20
130
220
380
Penalidad 2
10 7 = 3
15 11 = 4
18 9 = 9
97=2
02/03/11 01:57 PM
3.1
Modelos de transporte
49
Una vez que se eligi la columna, se asigna al valor ms pequeo lo ms que se pueda.
Valor ms pequeo de la columna no tachado
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 2
10
15
18
120
15 10 = 5
130 130 = 0
130
11
250
Demanda (pollos)
150 130 = 20
130
220
380
Penalidad 2
10 7 = 3
15 11 = 4
18 9 = 9
97=2
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 2
10
15
18
120
15 10 = 5
130 130 = 0
220
250
130
11
Demanda (pollos)
150 130 = 20
130
220
Penalidad 2
10 7 = 3
15 11 = 4
18 9 = 9
97=2
380
Luego de asignar la cantidad de 220, se ajustan las cantidades de oferta y demanda como se muestra
a continuacin.
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 2
10
15
18
120
15 10 = 5
130 130 = 0
220
250 220 = 30
130
11
Demanda (pollos)
150 130 = 20
130
220 220 = 0
Penalidad 2
10 7 = 3
15 11 = 4
18 9 = 9
97=2
380
02/03/11 01:57 PM
50
UNIDAD III
Transporte y asignacin
Luego, se tachan los renglones o columnas satisfechos con cero oferta o cero demanda.
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 2
10
15
18
120
15 10 = 5
130 130 = 0
220
250 220 = 30
130
11
Demanda (pollos)
150 130 = 20
130
220 220 = 0
Penalidad 2
10 7 = 3
15 11 = 4
18 9 = 9
97=2
380
La siguiente etapa exige regresar al paso 1 y encontrar otra penalidad (penalidad 3) mediante la resta
de los dos valores ms pequeos por rengln y por columna.
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 3
10
15
18
120
15 10 = 5
130 130 = 0
13
11
Demanda (pollos)
150 130 = 20
130
Penalidad 3
10 7 = 3
15 11 = 4
220
250 220 = 30
220 220 = 0
97=2
380
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 3
10
15
18
120
15 10 = 5
130 130 = 0
130
11
Demanda (pollos)
150 130 = 20
130
Penalidad 3
10 7 = 3
15 11 = 4
220
220 220 = 0
250 220 = 30
11 7 = 4
380
02/03/11 01:57 PM
3.1
Modelos de transporte
51
Granjas
A
B
Oferta (pollos)
Penalidad 3
10
15
18
120
15 10 = 5
130 130 = 0
130
11
Demanda (pollos)
150 130 = 20
130
Penalidad 3
10 7 = 3
15 11 = 4
220
220 220 = 0
250 220 = 30
11 7 = 4
380
Al cuadro elegido se le asignan 20 pollos pues es lo ltimo que se pide aunque A ofrezca an 120 pollos.
Rosticera
Granjas
Oferta (pollos)
Penalidad 3
15 10 = 5
10
20
15
18
120
130
130 130 = 0
11
Demanda (pollos)
150 130 = 20
130
Penalidad 3
10 7 = 3
15 11 = 4
220
220 220 = 0
250 220 = 30
11 7 = 4
380
Luego, se tachan los renglones o columnas satisfechos con cero oferta o cero demanda.
Rosticera
Granjas
A
B
Oferta (pollos)
Penalidad 3
10
15
18
120 20 = 100
15 10 = 5
130 130 = 0
130
11
Demanda (pollos)
150 130 = 20
20 20 = 0
130
Penalidad 3
10 7 = 3
15 11 = 4
220
220 220 = 0
250 220 = 30
11 7 = 4
380
02/03/11 01:57 PM
52
UNIDAD III
Transporte y asignacin
De inmediato se regresa al paso 1, pero como ya slo queda una columna no tachada se contina el
proceso por medio del mtodo del costo menor.
Rosticera
Granjas
A
B
Oferta (pollos)
10
15
18
120 20 = 100
130 130 = 0
130
11
Demanda (pollos)
150 130 = 20
20 20 = 0
130
220
220 220 = 0
250 220 = 30
380
Columna no tachada que se resuelve por medio del mtodo de costo menor
El mtodo de costo menor establece que se debe elegir el costo ms pequeo de entre todos los elementos. En este caso se elige el costo menor de la columna no tachada.
Rosticera
Granjas
A
B
Oferta (pollos)
10
15
18
120 20 = 100
130 130 = 0
130
11
Demanda (pollos)
150 130 = 20
20 20 = 0
130
220
220 220 = 0
250 220 = 30
380
Se le asigna lo ms que se pueda al cuadro elegido, en este caso, 30 pollos, con lo cual el cuadro queda
de la siguiente forma.
Rosticera
Granjas
A
B
Oferta (pollos)
10
15
18
120 20 = 100
130 130 = 0
130
11
Demanda (pollos)
150 130 = 20
20 20 = 0
130
220
220 220 = 0
250 220 = 30
380
02/03/11 01:57 PM
3.2
53
En seguida se tachan los renglones o columnas satisfechos con cero oferta o cero demanda.
Rosticera
Granjas
Oferta (pollos)
10
20
15
18
120 20 = 100
130
130 130 = 0
11
Demanda (pollos)
150 130 = 20
20 20 = 0
30
130 30 = 100
220
250 220 = 30
20 20 = 0
220 220 = 0
380
Por ltimo, se asignan 100 pollos al cuadro final no tachado y se ajustan las ofertas y demandas correspondientes.
Rosticera
Granjas
10
20
130
Demanda (pollos)
150 130 = 20
20 20 = 0
15
100
5
11
30
130 30 = 100
100 100 = 0
Oferta (pollos)
18
120 20 = 100
100 100 = 0
130 130 = 0
220
250 220 = 30
30 30 = 0
220 220 = 0
380
En el problema de los modelos anteriores (modelos de la esquina noroeste, del costo menor y modelo de Vogel, respectivamente) se manej el mismo ejemplo para poder hacer una
comparacin entre estos tres mtodos y, como puede observarse, ninguno de ellos es cien por
ciento seguro ya que tendra que hacerse una comprobacin previa antes de poder tomar una
decisin.
02/03/11 01:57 PM
54
UNIDAD III
Transporte y asignacin
1
Con los datos del problema que se incluyen en la tabla siguiente, determine la solucin ptima.
Origen
Oferta
10
10
55
20
30
20
80
10
20
30
75
Demanda
70
100
40
En este caso aplicaremos el mtodo del costo mnimo para asignar los valores a la tabla, de lo cual resulta:
Origen
s1
s2
s3
Demanda
D1
5
55
20
10
D2
D3
Oferta
10
10
55
30
20
40
20
15
70
60
100
40
30
80
75
40
02/03/11 01:57 PM
3.2
55
Recuerde que, para conocer los ndices de mejoramiento nos debemos enfocar en los costos, no en las
cantidades que hemos asignado a cada una de las celdas.
Origen
s1
D1
5
55
s2
s3
20
10
D2
D3
Oferta
10
Inicio
10
55
30
40
20
15
Demanda
20
70
60
100
40
30
Note la trayectoria
de la celda (S1, D2)
80
75
40
Nota: Las flechas indican la trayectoria que debe seguirse para asignar nuevos valores. La flecha roja especifica dnde comienza la trayectoria.
D1
5
55
20
10
D2
D3
Oferta
10
10
Inicio
55
30
20
40
20
15
70
60
100
40
30
Note la trayectoria
de la celda (S1, D3)
80
75
40
D1
5
55
D2
D3
Oferta
10
10
55
20
Inicio
30
10
20
15
70
20
40
60
100
40
30
80
Note la trayectoria
de la celda (S2, D1)
75
40
02/03/11 01:57 PM
56
UNIDAD III
Transporte y asignacin
D1
5
55
20
10
D2
D3
Oferta
10
10
55
30
20
40
40
60
30
Inicio
20
15
70
100
80
75
40
Origen
s1
D1
55
s2
D2
Oferta
D1
Inicio
10
20
40
30
10
60
20
40
10
55
20
80
30
75
15
s3
70
100
40
Los costos de la trayectoria de esta celda son: 10, 5, 10 y 20. Como corresponde, tomaremos el costo
ms bajo de la trayectoria, es decir, 5.
02/03/11 01:57 PM
3.2
57
Paso 4. En este caso, el costo ms bajo es 5, por lo cual debemos asignar la cantidad que tiene esta
celda (55) a la variable de entrada y, por lo tanto, reasignar los valores de manera que queden con los totales
que la tabla exige. La nueva tabla queda como se presenta a continuacin:
Origen
D1
s1
s2
20
s3
D2
10
0 + 55
30
Oferta
10
55
20
40
10
40
20
15
Demanda
D3
30
60
70
100
80
75
40
Nota: Recordemos que reasignamos el 55 a la celda vaca porque sta tena un valor negativo en su ndice de
mejoramiento y que reacomodamos los valores de la tabla de tal modo que cada columna y fila quedaran satisfechas con el valor asignado. Para reasignar los valores con los que quedar la tabla para satisfacer los requisitos de
la tabla total, slo debemos mover los valores sobre los cuales se movi la trayectoria y todos los dems por los que
no pasaba permanecern iguales.
Es por eso que a la celda (S3, D1), que al inicio tena un valor de 15, al reasignarle el valor de 55 para
satisfacer la columna, debemos sumarle 15 + 55 = 70. La celda (S3, D2) tambin debe ser reasignada y, por
esa razn, debemos restar los 55 que reubicamos, de lo cual resulta: 60 55 = 5.
Origen
s1
s2
s3
D1
D2
10
55 55
30
20
Oferta
10
55
20
40
10
Demanda
0 + 55
D3
40
20
15 + 55
60 55
70
100
30
80
75
40
Observe que los valores de la tabla, tanto de la oferta como de la demanda, quedan satisfechos.
Ahora, la nueva tabla quedara de la siguiente forma:
Origen
s1
s2
s3
Demanda
D1
D2
10
0
55
30
20
55
20
20
70
70
10
40
10
Oferta
D3
5
100
40
30
80
75
40
Para obtener de nueva cuenta el costo total del problema se debe realizar la siguiente operacin:
Z = (55)(10) + (40)(30) + (5)(20) + (70)(10) + (40)(20) = 3 350
02/03/11 01:57 PM
58
UNIDAD III
Transporte y asignacin
Como en este caso no obtuvimos ningn valor negativo, el resultado final nos indica que el valor de Z
es 3 350.
2
Con los datos relativos al problema de transporte elaboramos la siguiente tabla:
Origen
s1
s2
s3
Demanda
Oferta
D1
D2
D3
$8.00
$6.00
$10.00
$4.00
$9.00
$8.00
$7.00
$6.00
$5.00
110
85
175
125
150
95
En este caso utilizaremos el mtodo de costo mnimo para asignar valores a la tabla, que quedar as:
Origen
s1
s2
s3
D1
D2
10
85
125
40
8
110
7
Oferta
D3
150
40
6
95
95
Demanda
110
85
175
D1
D2
10
Inicio
4
85
9
40
8
110
7
Oferta
D3
40
6
5
95
110
85
125
150
95
175
02/03/11 01:57 PM
3.2
59
D1
D2
10
85
9
110
Oferta
D3
40
8
Inicio
6
40
5
95
Demanda
110
85
175
D2
D3
125
150
95
IM22 = 9 8 + 10 6 = 4
Origen
s1
s2
s3
D1
8
10
85
40
8
110
7
40
6
Inicio
Demanda
Oferta
95
110
85
175
D2
D3
125
150
95
IM31= 7 4 + 8 5 = 6
Origen
s1
s2
s3
Demanda
D1
8
10
85
40
8
110
7
40
6
5
Inicio
110
Oferta
85
95
125
150
95
175
IM32 = 6 6 + 10 5 = 5
En este caso, ninguno de los ndices de mejora muestra valores negativos; por lo tanto, la solucin ptima indica que Z tiene un valor de 2 145.
02/03/11 01:57 PM
60
UNIDAD III
Transporte y asignacin
3
Una cervecera cuenta con 3 plantas de embotellamiento de marcas genricas, desde las cuales se distribuye el producto a 5 bodegas. La siguiente tabla sintetiza los costos de distribucin, las capacidades mensuales de las plantas y las necesidades de cada bodega expresadas todas ellas en cientos de cajas.
Bodega
Planta
Capacidad
mensual
$20.00
$35.00
$30.00
$40.00
$42.00
400
$45.00
$30.00
$42.00
$36.00
$38.00
350
$38.00
$40.00
$36.00
$35.00
$50.00
450
Necesidad
mensual
150
300
200
250
175
Se puede observar que, en este ejercicio, las cantidades de la demanda y la oferta no son iguales; por
lo tanto, debemos igualarlas. Para hacerlo, aadiremos otra columna antes de los valores finales con la cantidad que hace falta, que en este caso es 125.
Agregando la bodega ficticia, queda de la siguiente forma:
Bodega
Ficticia
Capacidad
mensual
Planta
20
35
30
40
42
400
45
30
42
36
38
350
38
40
36
35
50
450
Necesidad
mensual
150
300
200
250
175
125
1
20
2
35
3
30
150
45
4
40
5
42
200
30
42
40
36
38
36
35
300
50
350
200
250
0
75
175
Capacidad
mensual
400
50
250
150
0
50
300
38
Ficticia
125
450
125
02/03/11 01:57 PM
3.3
Modelo de asignacin
61
Luego de equilibrar los valores, procederemos a asignar valores a la tabla. Al final, insertaremos la columna de la bodega ficticia para equilibrar la tabla.
A continuacin debemos calcular los ndices de mejoramiento de cada una de las celdas vacas que son:
IM12 = 35 42 + 38 30 = 1
IM14 = 40 42 + 50 35 = 13
IM21 = 45 20 + 42 38 = 29
IM23 = 42 30 + 42 38 = 16
IM24 = 36 38 + 50 35 = 13
IM31 = 38 20 + 42 50 = 10
IM32 = 40 30 + 38 50 = 2
IM33 = 36 30 + 42 50 = 2
Como aparecieron valores negativos, es necesario reasignar valores a la tabla mediante el mtodo de
asignacin.
Bodega
Planta
1
2
3
Necesidad
mensual
1
20
35
30
150
45
4
40
5
42
200
30
42
40
400
36
38
350
125
36
75
150
Capacidad
mensual
50
225
38
Ficticia
300
35
50
250
200
250
0
125
175
450
125
02/03/11 01:57 PM
62
UNIDAD III
Transporte y asignacin
Aunque este tipo de problemas podra resolverse con el mtodo de transporte, existe uno
ms eficiente, al que se conoce como mtodo hngaro.
1
Cuatro vendedores (A, B, C, D), deben asignarse a cuatro destinos (1, 2, 3, 4). Los costos de la asignacin
aparecen en la tabla que a continuacin se presenta:
Destinos
Vendedores
16
10
14
10
11
12
Vendedores
16
10
14
10
11
12
02/03/11 01:57 PM
3.3
Destinos
Vendedores
Modelo de asignacin
63
16 7 = 9
77=0
10 7 = 3
97=2
44=0
14 4 = 10
84=4
74=3
95=4
10 5 = 5
55=0
11 5 = 6
44=0
64=2
84=4
12 4 = 8
El resultado es el siguiente:
Destinos
Vendedores
10
Vendedores
10
Nota: Como el costo menor en cada columna es 0, slo se proceder a restar donde no tenga cero dicha columna; en este caso, sera la 4:
Destinos
Vendedores
10
02/03/11 01:57 PM
64
UNIDAD III
Transporte y asignacin
Paso 3. Elimine todos los ceros de la tabla que desarroll cruzndolos con el menor nmero de lneas
horizontales o verticales.
Destinos
Vendedores
10
Como el nmero de lneas no es igual a m (4 vendedores), debe restarse el menor costo no cubierto por
una lnea y luego sumarlo a las intersecciones de las lneas, luego de lo cual el cuadro queda como sigue:
Destinos
Vendedores
9 + 1 = 10
3+1=4
10 1 = 9
11=0
51=4
41=3
21=1
61=5
Nota: En este caso, el costo menor no cubierto por ninguna lnea es el nmero 1 ubicado en B,4; como se mencion, se suma dicho nmero en donde hay interseccin y a los nmeros que no fueron cubiertos por las lneas se
les restar el costo menor.
El resultado es el siguiente. Cabe recordar que debe procederse a trazar las lneas en donde hay ceros.
Destinos
Vendedores
10
En este caso, como el nmero de filas es igual a m (4), debe hacerse la asignacin:
Destinos
Vendedores
10
02/03/11 01:57 PM
65
La asignacin quedara as: el vendedor A se dirige al destino 2 con un costo de 7 (que es el valor inicial
de la primera tabla), el B al punto de arribo 4 con un costo de 7, el C al 3 con un costo de 5 y el vendedor D va
al destino 1 con un costo de 4.
Destinos
Vendedores
16
10
14
10
11
12
Luego de sumar los costos de cada vendedor en relacin con cada uno de los destinos se obtiene:
7 + 7 + 5 + 4 = 23
1. Una empresa que fabrica automviles cuenta con 3 plantas de produccin, una en Toluca, otra en Coahuila y otra en San Luis Potos. Sus centros de distribucin principales estn ubicados en las ciudades de
Mxico y Monterrey. Las capacidades de las tres plantas durante el trimestre prximo son de 5 000, 4 500
y 3 200 automviles. Las demandas trimestrales en los dos centros de distribucin son de 7 300 y 5 400
vehculos, respectivamente. El envo de automviles se realiza por va frrea con un costo aproximado
de 8 centavos por cada 2 000 km. El diagrama de la distancia que existe entre las plantas y los centros de
distribucin es el siguiente:
Ciudad de Mxico
a)
b)
c)
d)
Monterrey
Toluca
75 km
875 km
Coahuila
993 km
348 km
407 km
501.2 km
2. Encuentre la solucin inicial mediante cualquiera de los mtodos que se expusieron en el captulo (esquina noroeste, costo menor y Vogel) y utilice el mtodo de cruce del arroyo para encontrar la solucin
ptima del siguiente problema.
10
12
C
Demanda
Oferta
11
600
14
20
20
100
16
18
140
120
80
100
540
02/03/11 01:57 PM
66
UNIDAD III
Transporte y asignacin
3. Utilizando el mtodo hngaro encuentre la asignacin ptima asociada de cada uno de los trabajos a cada
una de las mquinas y calcule el costo final.
Mquina
14
10
12
15
13
16
02/03/11 01:57 PM
Unidad
IV
Modelos de optimizacin
de redes
Al finalizar el estudio de esta unidad, se espera que el lector sea capaz de:
explicar qu entiende por red.
explicar qu es una ruta, nodo, arco, rbol, lazo.
resolver problemas mediante el algoritmo de Dijkstra.
resolver problemas mediante el algoritmo de Floyd.
resolver problemas mediante el algoritmo de flujo mximo.
resolver problemas mediante los mtodos PERT y CPM
N = 1, 2, 3, 4, 5
A = (1, 3) (1, 2) (3, 5) (3, 4) (4, 5) (2, 3) (2, 4)
4
2
Nodo
Figura 4.1
Arco o rama
67
02/03/11 01:58 PM
68
UNIDAD IV
Por qu el arco (3, 1) no est en el conjunto A? Porque se repetira el arco puesto que el
(1, 3) s existe.
En general, el flujo de una red est limitado por la capacidad de sus arcos, los cuales pueden ser finitos e infinitos.
Se dice que un arco est dirigido u orientado si permite un flujo positivo en una direccin
y un flujo 0 en la direccin opuesta; una red dirigida tiene todas las ramas orientadas.
Ruta
Una ruta es una secuencia de ramas distintas que unen a dos nodos sin que
importe la direccin del flujo de cada rama. Una ruta forma un lazo o ciclo si
conecta un nodo consigo mismo, como muestra la figura 4.2.
Figura 4.2
Lazo o ciclo.
Lazo dirigido
Lazo dirigido (circuito). Crculo en el
que todas las ramas se orientan en la
misma direccin.
Red conectada. Es aquella en la cual
dos nodos se encuentran unidos, por
lo menos, por una ruta.
rbol. Red conectada que puede contener slo un subconjunto de todos los
nodos de la red.
rbol de expansin. El que une todos
los nodos sin permitir ningn lazo.
Un lazo dirigido o circuito es un crculo en el cual todas las ramas estn orientadas en la misma direccin.
Red conectada
Una red conectada es aquella en la cual dos nodos se encuentran unidos, por lo
menos, por una ruta.
rboles
Por su parte, un rbol es una red conectada que puede incluir slo un subconjunto de todos los nodos de la red, mientras que un rbol de expansin une
todos los nodos sin permitir ningn lazo entre ellos.
Si se observa la figura 4.1, se obtiene lo siguiente (vase figura 4.3):
Figura
1
1
2
2
4
3
rbol
Figura 4.3
6
3
rbol de expansin
02/03/11 01:58 PM
4.1
Modelos de redes
69
En el caso de la siguiente figura, determine el conjunto de N, A y determine una ruta, un rbol de expansin,
un rbol y un lazo o circuito.
2
N = 1, 2, 3, 4, 5
1
Ciclos:
1, 2, 5, 1
1, 3, 5, 1
1, 3, 4, 5, 1
Rutas:
1, 2, 5
1, 3, 5
rbol:
1, 2, 5
1, 3, 5, 2
1, 3, 5
4
5
2
5
Red
Una red es la representacin grfica de un proyecto; las actividades que se desarrollan en ella se simbolizan mediante crculos (nodos), mientras que las relaciones de secuencia entre actividades con segmentos dirigidos (aristas).
Ruta
02/03/11 01:58 PM
70
UNIDAD IV
Algoritmo de Dijkstra
Los clculos del algoritmo de Dijkstra avanzan de un nodo i a un nodo siguiente j, por medio
de un procedimiento especial de clasificacin. La clasificacin de nodos de acuerdo con el algoritmo de Dijkstra se representa en dos formas:
Temporales
Permanentes
Una clasificacin temporal puede ser remplazada por otra si se puede encontrar una ruta
ms corta al mismo nodo. Si se llega al punto en el cual es evidente que no existe una ruta mejor, el estado temporal cambia a permanente.
1
Permanente = 15
Permanente = 10
i=1
j = 2, 3
dij = 30
15
2
100
Ruta: 1, 3, 4, 2
Costo: 55
1
i
20
4
10
30
50
60
5
j
Permanente = 30
Algoritmo de Floyd
El algoritmo de Floyd es ms general que el de Dijkstra ya que determina la ruta ms corta entre cualesquiera dos nodos de la red. Este algoritmo representa una red de N nodos como una
matriz cuadrada con N renglones y N columnas. La entrada (i, j) de la matriz de la distancia
02/03/11 01:58 PM
4.4
CPM y PERT
71
dij del nodo i al nodo j, que es finito. Por su parte, i est elaborado directamente con j; de lo
contrario, es infinito.
02/03/11 01:58 PM
72
UNIDAD IV
Actividades
de proceso
Clculos
de la red
Programas de tiempos
tiempo
Figura 4.4
Las tcnicas CPM y PERT difieren en que la primera supone duraciones deterministas de la
actividad; en cambio, la segunda supone duraciones probabilsticas.
3
2
Figura 4.5
2
A
3
2
3
B
3. Por definicin, una actividad simulada normalmente se representa por medio de una flecha de lneas punteadas, la cual no consume tiempo ni recursos. La figura 4.5 muestra
cmo debe utilizarse una actividad simulada para representar dos actividades concurrentes
(A y B).
Al insertar una actividad simulada en una de las tres reglas anteriores, mantenemos la concurrencia de A y B, es decir, proporcionamos los nodos finales nicos para las dos actividades
concurrentes.
Para mantener las relaciones de precedencia correctas, se deben responder las siguientes
preguntas a medida de que se aade cada actividad en la red.
Cul actividad debe preceder inmediatamente a la actual?
Cul actividad debe seguir a la actual?
Cules actividades deben ocurrir de forma concurrente a la actual?
02/03/11 01:58 PM
4.4
CPM y PERT
73
Las respuestas a estas preguntas pueden requerir el empleo de actividades simuladas para
asegurar la presencia empleada entre las actividades.
Por ejemplo, supongamos que debe satisfacerse la siguiente precedencia. La actividad C
puede comenzar inmediatamente despus de que se hayan completado las actividades A y B.
La actividad D puede empezar inmediatamente despus de haberse completado slo la
actividad B (vase figura 4.6).
Figura 4.6
Las flechas indican la trayectoria de las actividades, las cuales, a su vez, se representan con
crculos.
1
Un editor tiene un contrato con un autor para publicar un libro de texto. Las actividades simplificadas que se
asocian con la produccin del libro de texto se desarrollan y proporcionan a continuacin.
Desarrolle la red que represente el proyecto.
Actividades
Predecesoras
Duracin en semanas
Diseo de la portada
A, B
G, H
C, I
Para poder elaborar la red, primero debe asignarse el punto de origen (nodo 1). Despus, deben tomarse
las actividades que no tengan ninguna actividad precedente; en este caso, seran A, B, C, D. Al finalizar estas
actividades, comienzan a ubicarse las siguientes como:
E
F
G
H
I
J
02/03/11 01:58 PM
74
UNIDAD IV
Con ello, se concluye la trayectoria de la red de dicho proyecto (vase figura 4.7).
E
A
3
B
1
I
H
Figura 4.7
2
Calcule la ruta crtica dada la siguiente red.
3
2
2
4
Respuesta: Ruta: 1, 3, 4, 5, 6, 7 = 19
02/03/11 01:58 PM
Actividades de la unidad IV
75
1. Una compaa de televisin por cable est en proceso de proporcionar servicio a cinco nuevas reas
habitacionales. La figura siguiente representa los enlaces posibles de televisin entre las cinco reas. La
extensin de los cables se muestra en cada uno de los arcos. Determine la red de cable ms econmica
en las conexiones de cable de la compaa:
3
2
1
9
1
5
10
3
5
8
3
2. Una compaa que renta automviles desea desarrollar un plan de reposicin de su flotilla para un horizonte
de planeacin de 4 aos, que comienza el 1 de enero de 2006 y termina el 31 de diciembre de 2010. Al
iniciar cada ao se decide si un auto se debe mantener en operacin o se debe sustituir. Cada vehculo debe
estar en servicio durante 1 ao como mnimo y 3 aos como mximo. La figura siguiente muestra el costo
de reposicin en funcin del ao de compra del vehculo y los aos que tiene en funcionamiento.
El problema se formula como una red, en la cual se representan por los nodos del 1 al 5 los aos de
2006 a 2010. Determine la ruta ms corta entre los nodos 1 y 5:
9 800
7 100
5 000
4 000
4 300
4 800
4 900
6 200
8 700
3. Considere la siguiente figura. Luego, encuentre la ruta ms corta del nodo 1 al 15.
6
8
10
12
2
14
15
13
11
5
7
02/03/11 01:58 PM
76
UNIDAD IV
4. Resuelva el problema de recorrido mnimo en la red que se muestra en la figura siguiente. Los nmeros
sobre las ramas representan los costos de incluir estas ramas en la red final.
10
8
7
10
F
3
4
3
5. En la figura siguiente, identifique una ruta del origen A al destino G que permita un flujo positivo.
B
3
5
2
E
1
4
2
1
1
6
F
10
02/03/11 01:58 PM
Ejercicios
Problema 1
Afianzadora Insurgentes evala 3 proyectos de crecimiento; adems, elabor una planificacin de
5 aos para acrecentar su rentabilidad. A continuacin se muestra una tabla de estimacin de las
utilidades que proporcionar cada proyecto y los egresos que se relacionan con cada uno de ellos
y que se consideran anuales. Plantee el modelo de programacin lineal.
Egresos (miles p)
Proyecto
1
2
3
Fondos disponibles
1
25
18
16
120
2
27
22
27
140
3
28
21
21
120
4
30
28
34
150
5
28
31
24
110
Utilidad
215
320
270
x1 = proyecto 1
x2 = proyecto 2
x3 = proyecto 3
Objetivo: maximizar
Max Z = 215x1 + 320x2 + 270x3
S.A.
25x1 + 18x2 + 16x3 120
27x1 + 22x2 + 27x3 140
28x1 + 21x2 + 21x3 120
30x1 + 28x2 + 34x3 150
28x1 + 31x2 + 24x3 110
xi 0
Problema 2
La compaa Higiene y Limpieza Institucional (HLI) desea evaluar y proyectar las utilidades de
cada uno de sus productos Fabuloso, as como su proceso de elaboracin durante 5 aos; se nos
proporcionan las utilidades esperadas de cada producto. Plantee el modelo de programacin
lineal entero.
Tipo de Fabuloso
Ao 1
Ao 2
Ao 3
Ao 4
Ao 5
Utilidades
Mar fresco
10 000
Lavanda
9 500
Frutas
7 000
Canela
14 000
11 500
Naranja
Fondos disponibles
20
28
26
30
37
77
05 Munoz EJERCICIOS.indd 77
02/03/11 01:59 PM
78
Ejercicios
Sea:
x1 = Fabuloso mar fresco
x2 = Fabuloso lavanda
x3 = Fabuloso frutas
x4 = Fabuloso canela
x5 = Fabuloso naranja
Objetivo: maximizar
Max Z = 10 000x1 + 9 500x2 + 7 000x3 + 14 000x4 + 11 500x5
1x1 + 1x2 + 1x3 + 2x4 + 2x5 20
2x1 + 1x2 + 1x3 + 5x4 + 2x5 28
3x1 + 4x2 + 1x3 + 3x4 + 2x5 26
1x1 + 1x2 + 1x3 + 2x4 + 2x5 30
1x1 + 1x2 + 1x3 + 1x4 + 2x5 37
xi 0
Problema 3
Se analizan cuatro medios electrnicos de comunicacin para lanzar la nueva campaa publicitaria de Desechables Jaguar. La campaa tendr una duracin de 3 meses. La siguiente tabla
proporciona los alcances totales y los costos mensuales presupuestados de cada medio. Elabore
el modelo de programacin lineal entero.
Nmero
Medio de comunicacin
2do. mes
3er. mes
TV
35 000
22 000
16 000
3 425 000
Radio
16 000
10 000
5 000
275 000
TV por cable
18 000
14 000
9 000
49 000
Peridico
15 000
9 000
7 000
781 550
84 000
55 000
37 000
Sea:
x1 = medio 1
x2 = medio 2
x3 = medio 3
x4 = medio 4
Max Z = 3 425 000x1 + 275 000x2 + 49 000x3 + 781 550x4
S.A.
35 000x1 + 16 000x2 + 18 000x3 + 15 000x4 84 000
22 000x1 + 10 000x2 + 14 000x3 + 9 000x4 55 000
16 000x1 + 5 000x2 + 9 000x3 + 7 000x4 37 000
xi 0
05 Munoz EJERCICIOS.indd 78
02/03/11 01:59 PM
Ejercicios
79
Problema 4
Una compaa area debe evaluar tres proyectos promocionales, los cuales se llevarn a cabo
en los siguientes 12 meses y, para ello, cuenta con un capital limitado para cada mes, por lo cual
debe elegir la opcin que ms se adapte a sus necesidades. Los datos se muestran en la siguiente
tabla:
Valor actual 3
meses
(en pesos)
12
TV y prensa
8 000
16 000
15 000
18 000
25 000
Radio y prensa
6 000
7 000
12 000
10 000
4 000
Radio y TV
10 000
10 000
13 000
18 000
25 000
30 000
40 000
35 000
50 000
Fondo disponible
Sea:
x1 = TV y prensa
x2 = Radio y prensa
x3 = Radio y TV
Min Z = 8 000x1 + 6 000x2 + 10 000x3
Sujeto a: 16 000x1 + 7 000x2 + 10 000x3 30 000
15 000x1 + 12 000x2 + 13 000x3 40 000
18 000x1 + 10 000x2 + 18 000x3 35 000
25 000x1 + 4 000x2 + 25 000x3 50 000
xi 0
Problema 5
La empresa Sueo desea importar colchones de Tailandia, para lo cual debe evaluar las posibles
agencias aduanales a las que acudir para ello.
A la compaa le interesa cumplir con los pedidos que tiene, as que uno de los factores ms
importantes para elegir agencia es el tiempo en que llega el pedido al almacn de la tienda, sin
olvidar el costo y la utilidad.
La empresa est comprometida a entregar sus pedidos en no ms de una semana y no puede gastar ms de 25 000 pesos por pedido.
La tabla ilustra las caractersticas de cada agencia aduanal.
Agencia aduanal
05 Munoz EJERCICIOS.indd 79
Tiempo de entrega
Ganancia
Tipo 1
4 das
24 000
10 000
Tipo 2
5 das
20 000
13 000
Tipo 3
5 das
19 500
12 000
02/03/11 01:59 PM
80
Ejercicios
Problema 6
La empresa de telemarketing Atel trata de reducir sus costos; la estrategia es escoger la compaa telefnica que le ofrezca ms llamadas a un costo reducido. Son tres las compaas telefnicas: Telmex, que cobra 360 pesos por mes. AT&T, 450 pesos fijos al mes, y Avantel, cuya tarifa
fija es de 280 pesos mensuales.
La compaa debe cumplir con sus clientes, pero, debido a que la competencia ha aumentado, tiene que ofrecerles planes muy atractivos. Ello significa un precio considerable para la
promocin o ventas de los productos de sus clientes, aunque sin poner en riesgo la buena promocin de los productos.
Para que la empresa cumpla con sus clientes, debe hacer un promedio de 400 llamadas
al mes por empleado, pero sus costos extras no deben exceder de 2 000 pesos. En la siguiente
tabla se presentan los beneficios que se obtienen con cada una de las compaas telefnicas.
Compaa
Renta mensual
Telmex
350
350
2.00
AT&T
400
300
1.50
Avantel
280
300
2.20
Cmo debe repartir las llamadas la empresa para minimizar los costos?
Sea:
x1= contratar lnea telefnica con Telmex
x2= contratar lnea telefnica con AT&T
x3= contratar lnea telefnica con Avantel
Min Z = 350x1 + 400x2 + 280x3
S.A.
350x1 + 300x2 + 300x3 400
2x1 + 1.5x2 + 2.2x3 2 000
x1 0
05 Munoz EJERCICIOS.indd 80
02/03/11 01:59 PM
A
Actividad crtica. Ocurre cuando no hay libertad para determinar los tiempos de
inicio y terminacin en un proyecto.
rbol. Red conectada que puede contener
slo un subconjunto de todos los nodos
de la red.
rbol de expansin. El que une todos los
nodos sin permitir ningn lazo.
C
Cola. Lnea de espera.
CPM y PERT. Mtodos basados en redes
que ayudan a planificar, programar y
controlar proyectos.
D
Destino. Nodo en el cual todos los arcos sealan hacia el nodo.
E
Evento. Punto en el tiempo en el que se
concluyen determinadas actividades y
empiezan otras.
F
Fuente. Nodo en el que todos los arcos apuntan hacia el exterior.
I
Investigacin. Actividad que tiene por fin
ampliar el conocimiento cientfico sin
perseguir, en principio, ninguna aplicacin prctica.
Investigacin de operaciones (IO). Disciplina que divide un problema concreto
en pequeas partes a las que analiza
para obtener un problema abstracto o
un modelo y as ofrecer acciones o alternativas de solucin.
L
Lazo dirigido (circuito). Crculo en el que
todas las ramas se orientan en la misma
direccin.
M
Mtodo de cruce de arroyo. Mtodo a travs
del cual debe encontrarse un procedi-
O
Operacin. Conjunto de reglas que permiten, a partir de una o varias cantidades
o expresiones, llamadas datos, obtener
otras cantidades o expresiones denominadas resultados.
Optimizar. Logro de mayores beneficios con
una mnima inversin de recursos.
P
Parmetros. Valores que especifican la relacin entre las variables de decisin.
R
Red. Representacin grfica de un proyecto.
Red conectada. Es aquella en la cual dos
nodos se encuentran unidos, por lo menos, por una ruta.
Ruta. Secuencia de ramas diferentes que
enlazan dos nodos sin que importe la
direccin del flujo de cada rama. Secuencia entre actividades que se desarrollan en una red
T
Teora de colas. Conjunto de modelos matemticos que describen sistemas de
81
06 Munoz GLOSARIO-BIBLIO.indd 81
02/03/11 01:59 PM
82
Bibliografa
06 Munoz GLOSARIO-BIBLIO.indd 82
V
Variables de decisin. Cantidades que se
desconocen y que deben determinarse
en la solucin de un problema cuyo modelo se plantea.
02/03/11 01:59 PM
ndice
A
Actividad crtica, 74, 81
Algoritmo
de Dijkstra, 67, 70
de Floyd, 67, 70
de flujo mximo, 67
de la ruta ms cercana, 70
rbol, 67, 68, 69, 81
de expansin, 68, 69, 81
Arco, 67, 68, 71
Arista, 69
Arsham Hossein, 4
C
Clculo de la ruta crtica (CPM), 74
Ciclo, 68
Ciencias de la administracin, 1
Circuito, 68, 69, 81
Cola, 81
Conjunto de restricciones, 7, 8
D
Destino, 71, 81
Dualidad, 32
E
Ecuaciones de restriccin, 38
Eficacia, 8
Espacio de soluciones factibles, 13
Evento, 74, 81
F
Fuente, 71, 81
Funcin, 2
Funcin exponencial, 3
Funcin objetivo, 7-11, 13, 19, 20, 27, 29,
32, 33, 36
G
George B. Dantzig, 2, 19
I
ndice de mejoramiento (IM), 55, 56, 57,
59, 61
Investigacin de operaciones (IO), 1-6, 81
Iteracin, 2
M
Mtodo
celda de piedra, 53
CPM (Critical Path Method), 67, 71, 72, 81
de asignacin, 61
de costo menor, 35, 38, 42, 46, 52, 54,
58, 65, 81
de cruce de arroyo, 53, 54, 65, 81
de la esquina noroeste, 35, 38, 42, 44,
46, 65
de la ruta crtica, 71
de piedra rodante, 53
de suma y resta, 18
de transporte, 61, 62
dual smplex, 33
grfico, 7, 13, 34, 81
grfico en actividad, 13
grfico en recursos, 13
hngaro, 35, 62, 66
PERT (Program Evaluation and Review
Technique), 67, 71, 72, 81
smplex, 1, 7, 19, 29, 34, 36, 37, 71, 81
Vogel, 35, 38, 46, 65
Modelos, 1, 2, 3, 4, 81
abstractos, 4, 81
a escala, 2
aleatorios, 4, 81
de asignacin, 35, 61, 81
de flujo mximo, 71
de programacin lineal (MPL), 9-13, 32,
36-38, 44, 65, 77, 78
descriptivo, 81
desventajas, 4
determinsticos, 4, 81
de transporte, 35, 36, 81
dinmicos, 4, 81
dual, 32
estticos, 4, 81
fsicos, 4, 81
lineal, 14, 19
matemticos, 2, 81
descriptivos, 3
normativos, 3
predictivos, 3
mentales, 2
normativo, 81
predictivo, 81
primales, 32, 34
ventajas, 4
N
Nodo, 67-72
permanentes, 70
06 Munoz GLOSARIO-BIBLIO.indd 83
temporales, 70
No negatividad, 5, 9, 13
Nmero de restricciones, 13
O
Objetivo, 5, 11
Operacin, 81
Optimizacin, 3, 5, 33
Optimizar, 4, 9, 81
Organigrama, 3
P
Parmetros, 7, 8, 81
Patrn de flujo ptimo, 71, 81
Pivote, 20, 21, 23, 24, 28, 30, 31
Plano cartesiano, 13, 14
Problemas lineales, 5, 13
Problemas no lineales, 5, 7
Programacin lineal, 7, 9, 33, 35, 81
Programacin matemtica, 4
Proyecto, 71, 81
Punto ptimo, 14, 17, 18
R
Ramas, 67, 68, 76
Rango, 13
Red, 67-74, 76, 81
conectada, 68, 81
residual, 71
Regin factible, 13-16
Restricciones, 5, 7, 9, 10, 12, 13, 14, 15, 20
Ruta, 67, 68, 69, 81
S
Sistema, 4
Solucin factible, 13
Solucin factible degenerada, 13
Solucin factible no degenerada, 13
T
Tabla smplex, 20, 27, 29, 30, 32, 37, 38
Tcnica de evaluacin y revisin de
programas, 71
Teora de colas, 81
Trayectoria aumentada, 71, 82
V
Variables, 5, 9, 13
de decisin, 7-13, 81
de holgura, 19, 20
numricas, 9
02/03/11 01:59 PM
06 Munoz GLOSARIO-BIBLIO.indd 84
02/03/11 01:59 PM