Investigacion de Operaciones para Ingenierias y Administracion de Empresas OA PDF
Investigacion de Operaciones para Ingenierias y Administracion de Empresas OA PDF
Investigacion de Operaciones para Ingenierias y Administracion de Empresas OA PDF
UNIVERSIDAD
NACIONAL
DE COLOMBIA
Sede Palmira
Departamento de Ciencias Bsicas
UNIVERSIDAD NACIONAL DE COLOMBIA
Sede Palmira
ISBN : 958-8095-09-3
Derechos reservados .
LISTA DE FIGURAS 7
INTRODUCCiN. 9
2. PROGRAMACiN LINEAL. 16
3. PROGRAMACiN ENTERA. 73
APNDICE A. 217
BIBLIOGRAFA 230
LISTA DE FIGURAS
,,' igura 12. Cambio de flujo de unidades del segundo tablero. lOS
Figura 13. Sistema de vas para el transporte en autobuses de una ciudad. 120
Figura 14. Posibilidades de construir una red elctrica entre siete municipios. 127
Figura 14-1. Diseo para construir una red elctrica entre siete municipios. 128
Figura 16. Solucin factible para una Red de flujo mximo propuesta. 132
Figura 20. Red sin trayectorias de aumento para el ejemplo de flujo mximo. 135
Figura 22. Hoja de trabajo en EXCEL para el ejemplo de la red de distribucin. 141
Figura 23. Cuadro de dilogo de SOLVER en EXCEL. 142
Figura 24. Hoja EXCEL con la solucin SOLVER para la red de distribucin. 143
Figura 27. Diagrama de red para el proyecto del traslado de las oficinas. 153
Figura 29. Distribucin beta para las tres estimaciones dc tiempo dc PERl'. 162
El texto y el material didctico estn divididos en diez secciones que cubren los temas
del curso de Investigacin de Operaciones para la carrera de Administracin de
Empresas de la Universidad Nacional de Colombia, Sede Palmira.
Cada tema se ilustra con suficientes ejemplos y al final de cada seccin se proponen
ejercicios para que sean resueltos por el lector.
9
1. GENERALIDADES SOBRE INVESTIGACiN DE OPERACIONES.
10
INVESTIGACION DE OPERAC IONES PARA I NGEN IER IAS y ADM IN ISTRACION DE EMPRESAS
11
LU IS ALBERTO RINCON ABR IL
Las etapas esenciales en el uso de cualquiera de las anteriores tcnicas son las
siguientes:
12
INVEST l t'.\C ION DE O I'ER,\C IONES I',\ R,\ I N(;[N IERI ,\ S y , \ I) ~ II N I S ' I R,\C ION DE E~ II'RE S ,\S
1.1.1 Ejemplos.
13
L U IS A L BE RTO RI NCON AB RIL
d) Por aumento en las ventas, una procesadora requiere mayor espacio de bodegas.
Una solucin alternativa considera la compra de un depsito a 10 Km de la fbrica,
para almacenar los productos terminados. Este plan requiere el traslado del
producto terminado desde la planta hasta el depsito. La gerencia debe
determinar el nmero ptimo de camiones que sern alquilados o comprados .
Equivale esto, a estimar:
14
I NYESTIGAC ION DE OPERAC IONES PARA I NGEN I ER I /\S y ADM IN ISTR ACION DE EMPRESAS
15
2. PROGRAMACiN LINEAL.
16
IN\ I S-II G\C!ON Dr: Ol'rlU( ' IO NES I',\RA I NGEN I ER I,\ S y ,\D~I I N I S -II {'\C I() N DC UIPRE~AS
J7
LU IS ALI3ERTO R INCON AI3RIL
La funcin F(Xj ) en las variables X 1, X2, X 3,.... .... ,X n; es lineal , si puede ser
expresada como: F(Xj ) = a1X1 + a2X2 + a3X3 + ........ + anX n
y la condicin de no negatividad :
X>O
J- para todo j = 1, 2, 3,.. .... ,n
En donde:
Xj : Variable de decisin asociada con cada actividad j-sima U=1 ,2,3,... .n) .
18
INVESTI GAC IO N DE O PE RAC ION ES PA R A I NGEN IERI AS y A DMI N ISTR AC ION DE EMPR ESAS
Aunque existen varias tcnicas para lograr el modelo matemtico de cada problema
en particular, se recomienda la siguiente para llegar al propsito.
Es cualquier conjunto de valores positivos para las variables: X 1, X2 , X3 , ... . .... ,X n ; que
cumple cada una y todas las restricciones del modelo matemtico de programacin
Lineal. En caso contrario, es decir, no cumplen la condicin de no negatividad o
algunas de las restricciones, se define como no factible.
19
L U IS ,\ U 3E RTO RI NCON ,\BR IL
Es el conjunto de valores para las variables: X" X2 , X3 , ....... . ,Xn ; que satisfacen el
criterio de factibilidad y optimizan la funcin objetiva del modelo matenltico de
programacin Lineal.
20
INVEST IG\C ION DE OPERAC IO NES P;\RA INGEN IER I ,\S y ;\D~1INISTRACION DE H IPR ES /\S
Variables de decisin.
Restricciones.
21
L U I S 1\l.Ilr.RTO RI NCON ,\I1R II .
Produccin de salchichas
Alternativa Tipo I Tipo 11
Propuesta Ton/sem Ton/sem
1 O O
2 40 60
3 70 80
4 90 90
5 80 90
6 90 80
22
INVEST Il,AC ION DE OPE RAC IONES PA RA ING EN IERI AS y ADM IN ISTR AC ION DE EMPRESAS
Variables de decisin.
Restricciones.
23
I.lIIS ,\ 1 B !. RTO RINCON ,\I3RIL
X1 + X2 2 50
De acero se mezclarn ::; 70 Ton
X1 ::; 70
De chatarra se mezclarn ::; 40 Ton
X2 ::; 40
El tiempo para la produccin ::; 120 horas
2X 1 + 3X 2 ::; 120
La relacin chatarra/acero ::; 7/8
7X 1 - 8X 2 2 O
24
INVEST IGAC ION DE OPERAC IONES PARA I NGEN I ER I AS y ,\DM IN IST RAC ION D E EMPRESAS
Variables de decisin.
X 1 : Ton/semana de tomate A.
X2 : Ton/semana de tomate B.
X3 : Ton/semana de tomate C.
Restricciones.
2S
LUIS ALBERTO RINCON ABR IL
26
IN\TS'II(; ,\C!ON DE OPER ,\CIONES PARA INCEN IERI AS y , \I)~I I N I STR /\CION DE E~ IP RES . \S
Variables de decisin.
X, : Nmero de mesas.
X2 : Nmero de sillas,
X 3 : Nmero de escritorios,
X4 : Nmero de libreros.
Restricciones.
27
LU IS ALBERTO RINCON ABR I L
28
INVEST IGAC ION DE OPERAC I ONES P;\I<A INGEN IERI AS y AD~ II N I STRAC I ON DE EM PRESAS
Ejemplo de solucin factible grfica. Aplicando los conceptos de la seccin 2.4 .1,
la regin solucin para el siguiente conjunto de restricciones se tiene en la figura 1.
2X,+3X 2 ::; 12 R1
3X, + 2X 2 ::; 12 R2
X, + X2 ;c: 2 R3
XI ;c: O para j = 1,2
El grfico se obtiene trazando las rectas correspondientes a las restricciones R1, R2,
R3 Y ubicando el semiplano solucin para cada una de ellas.
29
L U I S I\ L J3ERTO I{ INCON ABR Il.
Uno de los teoremas que se presentar para el mtodo Simplex , considera que la
solucin ptima al Programa Lineal coincide con uno de los puntos extremos del
conjunto de soluciones factibles ; por tanto en los programas de dos variables de
decisin , ser necesariamente uno de los vrtices de la regin solucin. As pues,
para encontrar la solucin ptima basta reemplazar cada uno de los vrtices en la
funcin objetiva y observar cul genera el mayor valor en el caso de maximizar o cul
el menor valor en el caso de minimizar.
30
INVEST IG /\C ION DE OPER /\ClONr.S I',\R ,\ INGEN IER I AS y r\D~ II N I STR ,\C I ON DE H I PRES\S
El cual tiene solucin para Xl = 2.4 Y X2 = 2.4. Con esto los vrtices de la regin
estn determinados y son: A = (0 ,4) , B = (0 ,2) , C = (2,0) , 0 = (4,0) Y E = (2.4 ,2 .4).
Se tendr entonces que: l A = 12 , l B = 6 , l c = 8 , l o = 16 Y lE = 16.8. As que
Max(Z) =16.8, que se obtiene para X1 =2.4 Y X2 =2.4.
31
LU IS 1\ Ll3E RTO RINCO ABRIL
0 11 {l1 2 {I I ~ .. .. . . . . .. 0 1/1
{/ 2 1 {I n {I 23 .......... O 2 /1
A {/ 3 1 0 32 A .1.)
" ....... . .. (l ,
."1
. . . .... . . . . . .. .
XI b,
X2 bo
X = X -', b = b, e - (c
- I Co C,., cJ
X II bJl
= ex
Opt(Z)
sujeto a: AX :s b
x>o
Consiste en escribir el modelo con la Funcin objetiva para maximizar y todas las
restricciones de la forma S, esto es:
Max(Z) = ex
Sujeto a: AX < b
32
INVESTIGACION DE OPERAC IONES PARA INGEN I ER IAS y ADM IN ISTRAC ION DE EMPRESAS
x > O
Max(Z) = 4X 1 + X2
R1 : X1 + X2 <4
R2 : X1 + 2X 2 ~ 6
Xi 2: O para j = 1,2
Z - 4X 1 - X2 =O
R1: X 1 + X2 + X 3 = 4
R2: X1 + 2X 2 + X4 =6
33
1.1 li S ,\'-BERTO RINCON ABR IL
2.5.4.1 Solucin bsica factible. Una solucin bsica factible al programa lineal de
la forma bsica con m restricc iones y n+m variables (n de decisin y m de holgura)
es aquella con no ms de m componentes positivas que satisface cada una de las
restricciones .
34
IN\'EST IU ,\C ION DE O PER,\C IONES P\ R\ I N(iEN IERI ,\S y \mdI N ISTR \C ION DE EMPR ESAS
Considerando el programa lineal en su forma bsica, ste puede ser escrito como:
Z- ex = o
(A I)X = b
X>O
3S
LU IS ALBE RTO RI NCON ABR IL
36
IN\ I S II ( .\C ION DE O prR .\C ION F S P,\ R,\ I N( l .N II' RI.\S y . \ I) ~ II NIST R . \C I ()N DE E~ II' R I S.\S
Se supone que se inicia con una solucin bsica factible dada por BX s = b , que
corresponde a un punto extremo de la regin de factibilidad , el cual si no es ptimo,
deb e moverse a un punto extremo vecino con objeto de mejorar la funcin objetiva.
Esto se puede hacer cambiando un vector de la base B por un vector de N. Hay
varias forma s de hacerlo, pero Dantzig 2 fij la teora que justifica el cambio que
garantiza el mejor incremento en la funcin objetiva. Va se haba obseNado que
cua lquier columna al de S (no en B) puede escribirse aj = LVkjak con k = 1, .... ,m.
Supn gase que el vector que sale de B es a r y que la componente Vr de VI es
di ferente de cero . Entonces se tiene aj =LVkjak + Vrjar con k = 1 ,.... ,m y diferente de r.
(/ (/ )/,
Esto es, (/ , = )' '- "L....)' , 'f Y" * O. Por otro lado la solucin bsica factible puede
1/ ,.,
escribirse LakXbk = b , equivale con arX Sr + LakXbk = b para k=1 ,.... ,m y diferente de
X II Y, {[X II
r. Reemplazando a, en ella se obtiene I (X /Il -
y
"
I}
)u , + '
y
JI
'= iJ, que es una
X Y X
donde se ha definido X, = X - 11", X, = 11, las cuales se requieren
Y" Y" '
positivas. Dado que X Br ~ O, se requiere que Vr > O para que X r ~ O. De otra parte si
todas las Y kl S O para k=1 ,2,.... ,m y k # r, se garantiza que X k ~ O. Sin embargo, qu
, OANTZI G G. B .. Compu tationa l algo rit hm of the revised si mp lex meth od. RANO report RM-1 266.
Cali fornia 1953.
37
L U IS ALBERTO RINCON ,\13R II.
x y
ocurri ra si alguna YkJ < O. Analizando se tiene que X ; - ---.!.' A, ~ O. Y" > O, que
Y"
Xli,
puedo escribir como X ; ~ O. Y" > O, para garantizar que esto se cumpla se
YA, Y"
requiere que X ~ X li, O. Y" > O. De esta condicin slo se puede estar seguro
YA, Y"
Esta regla garantiza que el cambio de un vector de B por otro de N genera una
nueva solucin bsica factible . Como resultado de este cambio se obtiene una
nueva base B que difiere de la base anterior B en un solo vector. Como cada base se
asocia con un extremo de la regin de factibilidad , con el cambio de base el proceso
se ha movido a otro punto extremo XB tal que:
X B = S1b, Z = CBX B
El siguiente anlisis muestra la regla que permite hacer la mejor seleccin del vector
aJ en N que se debe introducir en B. El valor de Z asociado con el punto extremo XB
de la base es Z = CBXB y el asociado con la nueva base X'B ser Z' = C'BX'B. Ya se ha
mencionado que la nica diferencia entre las base B y B' es que se ha sacado el
vector ar y se ha reemplazado por el vector aj de N. Entonces la nica diferencia entre
CB y C'B se encuentra en la r-sima componente, es decir:
38
INVESTI G/\C ION DE O l'lcR/\ C IONES I'\R \ IN(, EN I E RI \ S Y \D ~ II N I S TR AC I ON D E H IPRES/\ S
X Y e X
,
es t e t ermlno, se pue d e escn'b'Ir Z '= "L e X /I! -
"LC m ~Y~-
/JO' "
y- - . con y,,
+ - ,fj, =F O :::::;.
1/ /'1
X
- Z - - n,-
Z '-
y
I ('II!',y + e ,/1,-
X
Y
:::::;. Z '= Z _ X 'J, ~, + e, X n, :::::;. T = Z - ( :: - e ) _
, .1
X
Y
B,
39
L U IS \Lll LRTO RI NCON I\BRIL
El teorema 4 establece las condiciones que debe cumplir una solucin para que sea
la solucin ptima de un programa lineal.
Zj - Cj ~ 0, para todo j.
Definen el cambio de vector a realizar para encontrar la nueva base cuando alguno
de los requisitos del criterio de optimalidad no se cumple.
2.5.7.1 Criterio Primal. Permite mejorar el valor de la funcin objetiva. Debe ser
aplicado cuando se tiene una solucin bsica factible , esto es, Xk ~O, para todo k y
existen algunos ZI - cl < O. Consiste en lo siguiente:
trabajo).
2.5.7.2 Criterio Dual. Permite convertir a factible una solucin bsica no factible. Por
lo tanto debe ser aplicado cada que la solucin bsica obtenida sea no factible .
Consiste en lo siguiente:
1. Sale de la base aquel a, para el que se tenga el XB, ms negativo. (fila de trabajo) .
40
INVESTI(; /\UON DE OPERAC IONES PARA I NGEN I ER I AS y , \I)~ II N I STR I\CION DE E~lPRESAS
Construir el Tablero
Simplex
Es la solucin
ptima? Definir el Elemento Construir el nuevo
Pivot Tablero Simplex
Si
41
LU I S 1\I . JlERTO R INCON MlR IL
z X, X2 X3 Xn X n+, X n+2 X n +3 X n +m
z(c 1 -C l -C2 -C3 -C n O O O O O
a n +, O all a1 2 a1 3 al n 1 O O O b1
a n +2 O a21 a22 a23 a2n O 1 O O b2
a n +3 O a31 a32 a33 a3n O O 1 O b3
En este tablero la base B esta formada por {a n+l , a n+2 , a n+3 ,....... , a n+m }, mientras
que N la forman {al, a2 , a3 ,.... ... , a n }. Equivale a decir que {X n+1 , X n+2 , X n+3 ,... .. .. ,
Xn+m } son las variables bsicas y que {Xl , X2 , X 3 ,.... ... , X n } son variables no
bsicas . Con esto, cada tablero muestra una solucin bsica al asignar el valor O a
cada variable no bsica , para que las variables bsicas tom en como valor el
correspondiente trmino independi ente . As pues, en este primer tablero se tiene que :
42
INY L STIG,\C ION DE OPERAC IONES PARA INGEN IER I AS y ,\D~ II N I STRAC I ON DE EMPRESAS
Cada uno de los criterios primal y dual definieron una fila de trabajo (vector de salida)
y una columna de trabajo (vector de entrada) . Esta posicin de fila y columna en el
tablero determina el elemento pivote. De tal manera que en el siguiente tablero, este
debe pasar a ser 1 y el resto de la columna conformada por ceros.
Debe ser obtenido sobre el elemento pivote previamente definido usando el mtodo
de eliminacin de Gauss que se presenta en el apndice A .
Max(Z) = 6X 1 + 4X 2
2X 1 + 3X 2 S 12
2X 1 + X 2 S 8
X1 ,2 ~ O
Z - 6X 1 - =O
4X 2
2X 1 + 3X 2 + X3 = 12
43
LUIS I\LBERTO RINCON I\BRII _
2X 1 + X2 + X4 = 8
XI ~ O para j = 1,2,3,4
Z X1 X2 X3 X4 b Tablero
Z-c 1 -6 -4 O O O
A3 O 2 3 1 O 12 Inicial
A4 O 2 1 O 1 8
Z--c 1 O -1 O 3 24
A3 O O 2 1 -1 4 Segundo
A1 O 1 Y2 O Y2 4
Z-c 1 O O Y2 5/2 26
A2 O O 1 Y2 Y2 2 Final
A1 O 1 O -1,4 3,4 3
Tablero inicial: Solucin bsica factible pero no ptima, pues Z1 - C1 = -6, Z2 - C2 = -4,
con variables bsicas X3 = 12, X4 = 8 Y variables no bsicas: X1 = X2 = o. Se debe
entonces generar un nuevo tablero (nueva base). De acuerdo con el criterio primal , la
variable X1 (vector a1) entra a la base y el vector a4 sale de la base; el elemento
pivote aparece sealado.
Segundo tablero: La nueva base es {a3 ad. Presenta una solucin bsica factible no
ptima, pues Z2 - C2 = -1 con las variables bsicas X3 = 4, X 1 = 4 Y variables no
bsicas X2 = X4 = o. Se debe entonces generar un nuevo tablero (nueva base). De
acuerdo con el criterio primal , la variable X2 (vector a2) entra a la base y el vector a3
sale de la base; el elemento pivote aparece sealado.
Tablero final : La nueva base es {a2 ad. Presenta la solucin ptima, pues cumple el
criterio de optimalidad, esto es ZI - cI ~ O, para todo j y X Bk ~ O para todo k. Las
variables bsicas X2 = 2, X 1 = 3 Y las variables no bsicas X3 = X4 = O. Adems este
tablero presenta que Max(Z) = 26.
44
l NVrST1(i\C1()N DE OPER/\C10NES P,\Ri\ l NGEN 1ER1 \S y \D~ II N 1 STR\C 10 N DE E~IPRESi\S
Max(Z) = 2X 1 + 5X 2 + 5X 3
X 1 + X2 + X 3 S 60
2X 1 - X 2 S 18
X2 - X3 S 6
Z - 2X 1 - 5X 2 - 5X 3 =O
X 1 + X 2 + X 3 + X 4 = 60
2X 1 - X2 + X5 = 18
X2 - X3 + X6 = 6
Xi?: O para j = 1,2 ,3,4 ,5,6
Z X1 X2 X3 X4 Xs X6 b Tablero
Z -c 1 -2 -5 -5 O O O O
a4 O 1 1 1 1 O O 60 Inicial
as O 2 -1 O O 1 O 18
a6 O O 1 -1 O O 1 6
Z-c 1 -2 O -10 O O 5 30
a4 O 1 O 2 1 O -1 54 Segundo
as O 2 O -1 O 1 1 24
a2 O O 1 -1 O O 1 6
Z-c 1 3 O O 5 O 5 300
a3 O % O 1 % O -% 27 Final
as O 5/2 O O % 1 % 51
a2 O Y2 1 O % O % 33
45
LU IS ALBERTO RINCON ABR IL
Tablero inicial: Base {a4 as a6}. Solucin bsica factible pero no ptima, en donde
las variables bsicas X4 = 60 , Xs = 18, X6 = 6 Y las variables no bsicas X 1 = X2 = X3 =
O. Se debe generar un nuevo tablero (nueva base). De acuerdo con el criterio primal ,
la variables X2 (vector a2) Y X3 (vector a3) cumplen la condicin para entrar a la base;
este empate se rompe arbitrariamente entrando a una de ellas X2, entonces el vector
a6 sale de la base; el elemento pivote aparece sealado.
Tablero final: La base final es {a3 as a2}. Es la solucin ptima, pues cumple el
criterio de optimalidad , esto es z - c 2: O, para todo j y X Bk 2: O para todo k. Las
variables bsicas X3 = 27, Xs = 51 , X2 = 33 Y las variables no bsicas: X 1 = X4 = X6 =
o. Adems Max(Z) = 300.
Min(C) = 2X 1 + 2X2
X 1 + X2 S 12
X 1 + 2X 2 2: 10
3X 1 + 2X 2 2: 12
X1.2 2: O
46
INVESTIGACION DE OPERAC IONES PARA INGEN IER IA S y \D~ II N I STRAC I ON DE EMPRESAS
Z X1 X2 X3 X4 Xs b Tablero
z-c 1 2 2 O O O O
a3 O 1 1 1 O O 12 Inicial
a4 O -1 -2 O 1 O -10
as O -3 -2 O O 1 -12
z-c 1 O 2/3 O O 2/3 -8
a3 O O 1/3 1 O 1/3 8 Segundo
a4 O O -4/3 O 1 -1/3 -6
a1 O 1 2/3 O O -1 /3 4
z-c 1 O O O % % -11
a3 O O O 1 1,4 1,4 13/2 Final
a2 O O 1 O -% 1,4 9/2
a1 O 1 O O % -% 1
Tablero inicial: Base inicial {a3 a4 a5}. Solucin bsica no factible , pues se tiene que
las variables bsicas: X 3 = 12, X4 = -10 , X5 = -12 Y variables no bsicas: X, = X2 = O.
Debe entonces generarse un nuevo tablero (nueva base). De acuerdo con el criterio
dual, sale de la base a5 Y entra la variable X 1 (vector a1) ; el elemento pivote aparece
sealado.
Segundo tablero: La nueva base es {a3 a4 a,}. Solucin bsica no factible, pero
menos "infactible" que la anterior, esto es lo que logra el criterio dual. Con variables
bsicas X3 = 8, X4 = -6, X, = 4 Y variables no bsicas: X2 = X5 = o. Debe generarse un
nuevo tablero (nueva base). De acuerdo con el criterio dual, sale de la base a4 y entra
la variable X2 (vector a2); el elemento pivote aparece sealado.
Tablero final: La base final es {a3 a2 a,}. Solucin ptima , pues cumple el criterio de
optimalidad , esto es z - c ~ O, para todo j y X Bk ~ O para todo k. Las variables
47
LlI lS ,\LBrRT O RI NCON ,\13 1<1 1.
Entre los vectores y matrices de los tableros Simplex hay varias re laciones, (algunas
de las cuales se usaron como elementos matemticos en la demostracin del
mtodo) , que se presentarn en esta seccin y que resultan ser de gran importancia
en anlisis de post-optimizacin , tema que se trata en el apartado 2.7.
Vector fila CN: Conformado con los zJ- cJdel tablero final para las variables de la
base inicial.
Matriz bsica B: Estructurada con los vectores YJ del tablero inicial para la base
final.
Matriz inversa de la bsica B-': Estructurada con los vectores Y del tablero final
para la base inicial.
48
IN\TS11(;/lCION DE OP I i{ ,\C IONES P/lR ,\ I N(;EN I ER I /lS y ,\D~ II N I STR/lCION DE H IPR ESAS
Teorema: Un Programa Lineal carece de solucin cuando existiendo algn XB, < O,
todo los correspondientes a" son positivos.
49
LUIS ALBERT O RINCON ABR IL
Min(C) = 3X l + 2X2
Xl + X2 S 3
2X l + 3X 2 ~ 12
Xl ,2 ~ O
El lector podr fcilmente verificar que este programa carece de solucin , trazando
para ello las restricciones en el plano cartesiano y observando que no existe ningn
punto que verifique las restricciones y la condicin de no negatividad.
50
INVESTIG ACION DE OPERAC IONES PARA INGEN I ERI AS y ADM IN ISTRAC ION DE EMPRESAS
Max(Z) = 4X 1 + 2X 2
X 1 + X2 ~ 8
2X 1 + X2 ~ 12
X1.2 ~ O
Como este Programa Lineal tiene la forma cannica se construye la forma bsica:
Z - 4X 1 - 2X 2 = O
X 1 + X2 + X3 = 8
2X 1 + X2 + X4 = 12
Xj ~ O para j = 1,2,3,4
Z X1 X2 X3 X4 b Tablero
z-c 1 -4 -2 O O O
A3 O 1 1 1 O 8 Inicial
A4 O 2 1 O 1 12
z-c 1 O O O 2 24
A3 O O 112 1 -% 2 Final 1
A1 O 1 % O Y2 4
z-c 1 O O O 2 24
A2 O O 1 2 -1 4 Final 2
A1 O 1 O -1 1 4
51
L U I S A L BERTO RINCON I\BR IL
Para un Mx(Z) = 24 , los tableros final 1 y final 2 presentan soluciones ptimas que
se pueden escribir como:
4
il
.\~ - O 2
d cl .fIll a l I y
IX'1 IX' 1
.1 = d el .fil/u l 2 .
.1 1 2 .\ .1
x" O .\"
Todas las soluciones ptimas pueden ser expresadas como una combinacin
convexa de estas dos soluciones encontradas.
Max(Z) = 2X 1 + X2
X1 + X2 ~ 4
X 1 - X2 S 2
X1,2 ~ O
52
INVEST IG\C ION DE OPERAC IONES PARA I NGEN I ER I AS y AD~ II N I STR f\C I ON DE EMPRESAS
53
L U I S A L BERTO RI CON AB RIL
Esta nueva solucin puede resultar factible o no factible ; si es el primer caso ser
la nueva solucin ptima . Para el segundo caso , sta ser reemplazada en el
tablero final y se proceder a reestablecer la factibilidad usando el criterio dual.
S4
INVr:ST I( ,\C ION DE OPERM.' IONES P;\R ,\ INlE I ER I,\S y AD~ II N I S TR /\C I ON DE H I PRES ,\S
Solucion.
Variables De Decisin.
55
LU I S ,\L13ERTO RINCON ABRIl.
Algoritmo Simplex
z X, X2 X3 X4 Xs X6 Xl b Tablero
z-c 1 -4 -6 -8 O O O O O
a4 O -1 -1 -1 1 O O O -120 Inicial
as O -1 O O O 1 O O -30
a6 O O -1 1 O O 1 O O
al O 0.6 0.5 OA O O O 1 80
z-c 1 4 2 O -8 O O O 960
a3 O 1 1 1 -1 O O O 120 Segundo
as O -1 O O O 1 O O -30
a6 O -1 -2 O 1 O 1 O -120 Criterio
al O 0.5 0.1 O OA O O 1 32 Dual
z-c 1 3 O O -7 O 1 O 840
a3 O Y2 O 1 -Y2 O % O 60 Tercero
as O -1 O O O 1 O O -30
a2 O 0.05 1 O -% O -Y2 O 60 Criterio
a7 O 0.15 O O OA5 O 0.05 1 26 Dual
z-c 1 O O O -7 3 1 O 750
a3 O O O 1 -% Y2 Y2 O 45 Cuarto
a, O 1 O O O -1 O O 30
a2 O O 1 O -% % -Y2 O 45 Criterio
a7 O O O O 0.45 0.15 0.05 1 21 .5 Primal
z-c 1 O O O O 16/3 16/9 140/9 9760/9
a3 O O O 1 O 2/3 5/9 10/9 620/9 Final
a, O 1 O O O -1 O O 30
a2 O O 1 O O 2/3 -4/9 10/9 620/9
a4 O O O O 1 1/3 1/9 20/9 430/9
S6
INVEST IGAC ION DE OPERAC IONES PARA I NGEN I ER I AS y ADM IN ISTRAC ION DE EMPRESAS
Solucin ptima.
Xl = 30 Ton de concentrado 1.
X2 = 620/9 Ton de concentrado 2.
X3 620/9 Ton de concentrado 3.
X4 = 430/9 Holgura de la restriccin 1
Anlisis de Post-Optimizacin.
C u = (8 4 6 O)
a) Cul es la nueva solucin si el total de la produccin debe ser al menos 150 Ton ,
no dispone sino de 120 Ton de materia prima A y las dems limitaciones no cambian.
57
LU I S ,\ L BERTO RINCON A BR IL
- 150
-30
En este caso el nuevo vector /J' = y calculando X 'BO = S-1 b ' se obtiene
O
120
.1'()
30
X 'lJo= 100 y Z' = CBX'BO = 5120/3. Qu e resulta ser factible , por lo tanto es solucin
X1 = 30 Ton de concentrado 1.
X2 = 340/3 Ton de concentrado 2.
X3 = 340/3 Ton de concentrado 3.
X4 = 260/3 Holgura de la restriccin 1
El nuevo vector /J '= [=~l => X 'BO = S-1 b ' =[~~;: 1 y z' = =
CBX'BO 880/9. Que resulta
40 -~
.'
58
INVr.STI (; ,\C ION DE O I'EI{ \ C IO N ES I',\R J\ I NGEN IER I J\ S y J\ D~ II N I S TR , \ C I ()N DE E~ I PR ES r\S
Z X1 X2 X3 X4 Xs X6 X7 b Tablero
z-c 1 O O O O 16/3 16/9 140/9 880/9
a3 O O O 1 O 2/3 5/9 10/9 -10/3 Nuevo
a1 O 1 O O O -1 O O 30 Tablero
a2 O O 1 O O 2/3 -4/9 10/9 140/3 Final
a4 O O O O 1 1/3 1/9 20/9 -80/3
Para este caso c' 1 =35 - (1 + 0.6*20 + 0.4*30) =10 Y (Z1 - C1)' =- 6
Z X1 X2 X3 X4 Xs X6 X7 b Tablero
z-c 1 O O O O 16/3 16/9 140/9 9760/9
a3 O O O 1 O 2/3 5/9 10/9 620/9 Recuperar
O 1 O O O -1 O O 30 La
a2 O O 1 O O 2/3 -4/9 10/9 620/9 Base
a4 O O O O 1 1/3 1/9 20/9 430/9
z-c 1 O O O O -2/3 16/9 140/9 11 380/9
a3 O O O 1 O 2/3 5/9 10/9 620/9 Criterio
a1 O 1 O O O -1 O O 30 Primal
a2 O O 1 O O 2/3 -4/9 10/9 620/9
a4 O O O O 1 1/3 1/9 20/9 430/9
z-c 1 O O 1 O O 7/3 50/3 4000/3
as O O O 3/2 O 1 5/6 5/3 3 10/3 Final
a1 O 1 O 3/2 O O 5/6 5/3 400/3
a2 O O 1 -1 O O -1 O O
a4 O O O -Y2 1 O -1 /6 5/3 40/3
S9
LU IS ALBERTO RINCON ABRIL
X3 = X6 = X7 = O. Variables no bsicas.
En 1950 aparecen los primeros intentos para dar solucin a programas lineales
mediante el uso de un computador, pero las primeras soluciones acertadas a un
programa lineal en un computador de alta velocidad , solo se obtuvieron en Enero de
1952 con el uso de la mquina SEAC , del National Bureau of Standard . Desde
entonces, el Algoritmo Simplex, ha sido codificado en varios lenguajes de
programacin . El profesional que requiere del uso de la programacin lineal , hoy en
da, en verdad no necesita ms que del diseo del modelo matemtico, pues las
soluciones estn al alcance hasta de los ms pequeos computadores y la eficiencia
de las respuestas de los programas de computador slo dependen de un correcto
diseo del modelo matemtico al problema . La aplicacin de mayor uso actualmente
resulta ser la herramienta SOLVER de EXCEL , la cual se presentar en esta
seccin. Hoy en da, muchos libros sobre Investigacin de Operaciones vienen
acompaados de Software de aplicacin para la solucin de varios problemas . Por
ejemplo el texto de Hillier y Lieberman 3 dispone el OR Courseware con
procedimientos didcticos y aplicaciones para la solucin de varios problemas.
' HILLlER Frederick y LlEBERMAN Gerald, Introduccin a la Investigaci n de Ope raciones. Editoria l
Mc Graw Hi11. 1997. Mxico.
60
INVI STI(; ,\C IO N DI' ()I'I RM ' IONI S P,\R ,\ IN(;I.N II I{L\S y \I )~ IINISTR .\C I()N DE E~IPR r S . \S
1 Este programa puede usarse gratuitamente y el lector podr hace r una copia de su instalador por
Internet en la direccion
61
L U IS A LllE ln O R INCON .\I3R 11.
Los modelos de Programacin Lineal encajan dentro del grupo tres que resue lve la
herramienta Solver, por lo tanto siempre podr ser usada para este propsi to. Se
ilustrar su uso con un ejemplo para el cual ya se haba construdo el modelo
matemtico en la seccin 2.3.4.
Variables de decisin.
62
IN\' I.S1 I(;'\UON D I. O I'I.R ,\ClON I S I'/\ R /\ I N(; EN I ER I,\S y '\ D ~ II N I S T R'\C I ON D E H IP RES r\S
Modelo Matemtico
Xl + X2 ~ 50
2X l + 3X 2 ::; 120
7X l - 8X 2 ~ O
Xl ::; 70
X2 ::; 40
Xl , X2 ~ O
Entre las filas uno y 10 se considera una matriz para los parmetros del modelo
matemtico del Programa Lineal. Por ejemplo las celdas B5: E5 pueden leerse
como 1 Xl + 1X2 ~ 50 , que resulta ser la primera restriccin , mientras que las
celdas B 1O:E 10 pueden leerse como 600X l + 300X 2 , que corresponde con la
funcin objetiva.
63
I IIl S \1 Ilf Rl() I<I N("() N M1RIL
la funcin Objetiva . Las celdas B 16:C 16 se han previsto para que Solver escriba
los valores de Xl, X2 , una vez los calcule.
.-
A B I e I oJ E
---- F
MODELO MATEMATICO
-
5 Aleaci n 1 1 > 50
6 Capacid ad de Trabajo 2 3 < 120
7 Relac i n 7 -8 > O
!----- !
8 ,Dispon ibilidad Acero 1 < 70
9 Di spon ibilidad Chatarra 1 < 40
._- J
10 F.O . Min(Costo) 600 300 !
11
12 --
SOLUCION POR SOLVER
13
14 Acero Chatarra Limitacin
--
~ X1 X2
I
16 Valores obtenidos .1- I
17 Valores mnimos O O
I
I
---
I
18
19 Aleaci n =B5'B$ 16 =C5'C$16 > 50 =SUMA(B19C19)
I 20 -lCapaci dad de Trabajo =B6'B$16 =C6'C$16 < 120 =SUMA(B20 :C20)
121 .Relaci n =B7'B$ 16 =C7'C$ 16 > O =S UMA(B21C21 )
122 Dispon ibilidad Ace ro =B8'B$1 6 =C8'C$16 < 70 =SUMA(B22:C22)
23 Dispon ibilidad Chatarra =B9'B$16 =C9'C$ 16 < 40 =S UMA(B23C23)
24 F.O . Min(Costo) =B10' B$16 =C 10'C$ 16 =S UMA(B24C24 )
25
Preparada esta hoja de clculo se procede a usar la opcin SOLVER del men de
HERRAMIENTAS de EXCEL y se responde el cuadro de dilogo de la siguiente
forma:
64
INVES-I I(, ,\C ION DE OPER /\C IONES P,\Ri\ I NCiEN IER I i\S y i\D~ II N I STR , \CION DE [~IPRES , \S
D E F
Parmetro, de Solver 11
Cerrar
c- t]. xirno
Cam~ando las celdas
Qpoones" ,
Suietas a las si9uientes restricciones:
I IUld .-, ./
I I
3. Cambiando las Celdas. Se selecciona las celdas donde Solver escribir los
valores encontrados para las variables .
5. Resolver. Una vez se responde el cuadro de dilogo, se pul sa este botn para
que EXCEL presente los resultados sobre la hoja de trabajo , tal como lo
muestra la siguiente tabla:
6S
l .l ' I S !\ I. HI-.RTO RI NCON ,\131' 11.
A B e J D E F
MODELO MATEMATICO
2
3 Acero Chatarra I Limitacin .~
4 X1 X2 ~ ..
5 Aleado n 1 1 ? 50 1
6 Capac idad de Trabaj o 2 3 < 120 -
7 Relacio n 7 -8 > O
8 Dispon ibilidad Acero 1 < 70
9 Dispon ibilidad Chatarra 1 < 40 -
10 F.O. M in (Cos to) 600 300
- l.
.~-
11
I 12 I SO LUCIO N POR SOLVER I
-
13
14 Acero - Chatarra Limitacin
15 X1 X2
16 Valore s obtenidos 30 20
17 Valore s mnimos O O
18
19 Al eacio n 30 -
20 > 50 50
20 Capac idad de Trabajo 60 60 < 120 120
21 Relacio n 210 -160 > O 50
- ~
22 Dispon ib il idad Acero 30 O < 70
23 Dispon ibilidad Chatarra O 20 < 40 20
24 F.O. M in (Cos to) 18000 6000
-
24000
1. La fila 16 muestra los valores obtenidos para las variables de decisin; esto es,
30 Ton de Acero y 20 Ton de Chatarra .
66
INVEST I(; ,\CION IlF OPFR ,\C ION lcS !',\RA I N (~E N IERI , \S y , \D~IINISTR;\CI()N DI' r~IPRF S.'\S
1. CONCEPTOS TERICOS.
1.1. Presente una aplicacin generalizada de Programacin Lin eal para algn caso,
por ejemplo: Diseo industrial de raciones , Mezcla industrial de productos, Poltica
de prstamos bancarios , Uso y urbanizacin de la tierra , Asignacin de personal,
Asignacin de recursos , etc.
1.2. Cmo se construye el programa dual a partir de un programa primal y que
relaciones existen entre stos?
1.3. Explique la forma en que puede aplicar el anlisis de post-optimizacin con la
herramienta Solver de Excel.
2.2. Una compaa de alquiler de camiones dispone dos tipos de vehculos, el camin A
que tiene 40 pies 3 de espacio refrigerado y 80 pies 3 de espacio no refrigerado; el
camin B tiene 60 pies 3 de cada tipo de espacio. Una procesadora de alimentos
debe transportar 1800 pies 3 de producto refrigerado y 2400 pies 3 de producto no
refrigerado El camin A lo alqui lan a $US 9 el Km y el camin B a $US 12 el Km .
2.2.2. Escriba el modelo matemtico, considerando el alqui ler de Camin C con 100
pies 3 refrigerados a $US 8 el Km?
67
L U I S A LB ERTO RI NCON A BRIL
2.3. Una industria de Aceite y Torta de Soya tiene capacidad para procesar hasta 60
Ton/da de Soya , las que adquiere a $55000 la Ton. Debe suministrar por lo
menos 16 Ton/da de Aceite. La industria usa dos procesos con los siguientes
rendimientos por Ton de Soya:
Para completar los pedidos , esta industria puede comprar Aceite a granel con
otros productores a $205000 la Ton , que le cuesta envasarla $8000 la Ton. La
industria vende Ton. de Aceite a $210000. y Ton. de Torta de Soya a $60000.
Presente un modelo matemtico que permita planificar la produccin en
condiciones ptimas.
2.4. Una imprenta dispone de 1800 tiras de cartulina de 13 pulg de largo. Debe atender
un pedido que le exige cortes de tal manera que disponga al menos 1000 tiras de
7 pulg , 2000 tiras de 5 pulg. La tabla muestra las cantidades de tiras de 5 y 7 pulg
por tira de cartulina de 13 pulg que puede obtener mediante los cortes posibles :
2.4.1. Cuntas tiras de 13 pulg. debe cortar en las formas A y B para cumplir el
pedido minimizando el desperdicio?
2.4 .3. Ser solucin factible cortar 600 tiras en la forma A y 1100 tiras en la forma
B?
2.5. El Departamento de Servicios de un almacn proporciona servicios de reparacin
para los electrodomsticos vendidos. Durante una semana cinco televisores, 12
grabadoras y 18 hornos microondas fueron devueltos para reparacin . Dos
tcnicos (Juan y Pedro) son contratados temporalmente para ayudar en dicho
68
INVEST IGi\C ION DE O PER AC IONES P\RA INGEN I ER I ;\S y c\D~ 1I N I S TR ;\C I ON DE H IPRESAS
departamento. En una jornada de ocho horas Juan puede reparar dos televisores
o 3 grabadoras o 4 hornos , mientras que Pedro puede reparar un televisor o 2
grabadoras o 3 hornos en el mismo tiempo. El salario diario est definido en
$20000 para Juan y $ 15000 para Pedro . Presente un modelo matemtica para
calcular el nmero de horas contratadas para que los costos sean mnimos.
Se supone que los pagos que no se cubren son irrecuperables y, por lo tanto, no
producen ingresos por concepto de intereses. La competencia con otras financieras
del rea hace que el banco asigne de los fondos totales al menos el 50% para
actividades agrcolas e industriales y los prstamos para vivienda deben ser al
menos el 50% de los asignados a actividades comerciales y compra de vehculos.
Adems , este banco tiene una poltica establecida que especifica que la relacin
global de pagos irrecuperables no puede ser superior a 0.004. Presente un modelo
matemtico que le permita al banco calcular las asignaciones a cada uno de los
tipos de prstamos.
3. SOLUCiN GRFICA.
69
L U IS f\ L BE RTO RINCON ,\BR IL
4X, - 2X 2 S O 6X , + 8X 2 S 120
6X , + 5X 2 S 60 X, + X 2 2: 4
3X, + 4X 2 2: 12 X, S 12
X2 S 8 X 2 S 12
X " X 2 2: O X" X 2 2: O
c) Min(Z) = cX , + cX 2 d) Min(Z) = 6X , + 5X 2
2X , + 3X 2 2: 6 3X , + 2X 2 S 300
X, + X2 s5 2X , + 3X 2 S 300
X, - X2 S 1 X, 2: 50
X" X 2 2: 0 X 2 2: 50
4 . MTODO SIMPLEX.
70
INVrST I(\C ION DE O PER ,\C IONES P,\R ,\ I NCEN IE RI \S y \D~ II N I ST R \C l N DE E~ I P R ES ,\ S
71
LU IS ALBERT O RI NCON AB RIL
72
3. PROGRAMACiN ENTERA.
Para el modelo de Programacin Lineal se optimiza una funcin sobre una regin
convexa, mientras que en la Programacin Entera se optimiza sobre una regin de
factibilidad que generalmente no es convexa . Por lo tanto , la solucin de
problemas enteros ; resulta ms complicada que la Programacin Lineal.
73
I.L' I." .\ I.I1ERTO RI NCON ABR IL
Las variantes del modelo de Programacin Lineal, tienen que ver con las
condiciones de valores enteros que tienen que tomar algunas de las variables de
decisin. Los ca sos son los sigui entes.
Es una variante del Programa Lineal , para el cua l todas las variables de decisin
adems de cumpl ir la condicin de no negatividad deben ser todas en teras. Por
consigu iente el modelo matem tico generalizado es:
"
Oplillli;:o r (Z) =L e,x,
1::.. 1
" <
slIje/o o: LO'l x , ~ h, . pa ra i = 1,2,3 .... .. .. , /1 1
1= 1 -
Los mtodos de solucin desarrollados para este mode lo son los siguientes .
74
INV I.ST IG I\C ION DE OPE RAC IONES I'A I<I\ I N(iENIE I<I. \S y M)~ II N I S T R \C I ON DE H IP RESi\S
En esta variante del Programa Lineal , todas las variables de decisin son positivas
y solamente algunas de ellas deben ser enteras. Por lo tanto el modelo matemtico
generalizado es:
" ,
. (Z) = '"
OJlillli .-or e ,',
r + '"
e J..'J..
r
,=\ , =\
11 11 <
.1/lie IO (/: o" x ,
,=\
+ , =\ p " \' , -~ !J, . po/'{/ i = 1.2,3 .. .... ., /11
x, ~ O po/'{/ .i = 1.2 .3 ...... 11
." ~ O elll e ro . p o /'{/ /.: = 1,2.3 .... , J'
Los mtodos de solucin desarrollados para este modelo son los siguientes .
Esta variante del Programa Lineal , suele utilizarse para modelar problemas con
actividades que deben o no ejecutarse. Por analogia con el sistema de los
nmeros binarios , las variables de decisin toman un nico valor entero entre O y
1. Esto es, si la actividad no se ejecuta la variable correspondiente toma el valor O,
de lo contrario el valor 1. Por consiguiente el modelo matemtico generalizado es:
75
LUIS ALBERTO RI NCON A BRIL
11
Oprill1i~ar(Z) = L e ,x ,
11 <
slljero a: L a" x , : b" para i = 1,2.3 ........ , 111
,; 1 -
X
J
= O , si la acrividad j /l O es reakada ..
x J = 1 , si la acrividad j es reakada ..
Los mtodos de solucin desarrollados para este modelo son los siguientes.
Problema general
Supngase que se tiene una disponibilidad total de dinero K, que puede invertirse
en una o varias de N alternativas posibles ; donde para la alternativa j-sima , se
requ iere I dinero de la disponibilidad total y evaluada su factibilidad se obtiene un
valor presente neto VPN . Se desea , entonces , establecer en cuales alternativas
emplear el dinero total disponible.
76
Modelo.
Encontrar los valores de Xi , para todo j=1 ,2" ... ,n, tal que:
"
sujeto a : "L.,; / ,, x , ;<; K
,_1
x, = O ,si la im'ersin j no es rea lizada ..
.\', = 1 ,si la illl'ersilI j es rea kada ..
Como puede observarse , este modelo encaja dentro del grupo de problemas de
programacin entero cero uno (PECU) , por ello se desarrollar alguna tcnica de
solucin para el (PECU) .
Mtodo de solucin.
77
LU I S 1\L13ERTO RINCON ABR IL
Producido por Kolesar' con base en Nodos. Supone que un Nodo lleva un ndice J
si la alternativa J se incluye y J* si no se incluye. Un Nodo con ndice (J ,K) significa
que se incl uye la alternativa J y despus la alternativa K, mientras que el ndice
(J *,K) significa que la alternativa J no se incluye pero la K s . Cuando se llega a un
Nodo, se analiza cules no han sido bifurcados y se procede a bifurcar aquel que
resulte ms conveniente para la funcin objetiva . Finalmente entre los Nodos que
presentan solucin factible debe seleccionarse el ptimo .
1 36 54 1.5
2 24 18 0.75
3 30 60 2
4 32 32 1
5 26 13 0.5
El grupo fin anciero debe tomar la decisin de aceptar o rechazar cada proyecto .
Cules proyectos se deben incluir y cu les rechazar con el fin de maximizar el
valor presente neto total?
, KOLE SAR, P .. A Branch and Bound Algorilhm lo r tire Knapsck Problem. Managmenl Science.
Volumen 13. 1982.
78
INVEST I(;AC ION DE OPERAC IONES PARA I NGEN I ERI AS y ADM IN ISTR AC ION DE EMPRESAS
Indice
Antiguo Nuevo l VPN Pi
3 1 30 60 2
1 2 36 54 1.5
4 3 32 32 1
2 4 24 18 0.75
5 5 26 13 0.5
Obsrvese que el cociente Pi tambin indica los millones de dlares que se dejarn
de recibir por no invertir un milln de dlares en el proyecto j.
79
LU IS ALBERTO R INCON ABR I L
J Ij VPNj Observaciones
1 30 60
2 36 54
3 32 32
Totales 98 146 Solucin no
Exceso -7 -7=-7x1 Factible
91 139
CUADRO 4. Nodo (1 *)
J Ij VPNj Observaciones
2 36 54
3 32 32
4 24 18
Totales 92 104 Solucin no
Exceso -1 -0.75=-1 xO. 75 Factible
91 103.25
80
INVEST IGACION DE OPE RAC IONES PARA I NGEN I ER I AS y ADM IN ISTRAC ION DE EM PRESAS
Factible Imposible
Con base en lo anterior, entre los nodos no ramificados (1) Y (1 *), se selecciona el
nodo (1) , puesto que 139 > 103.25 Y se procede con el anlisis de los nodos (1 ,2) Y
(1 ,2*).
81
L U IS A L BERTO RINCON A B RI L
J Ij VPNj Observaciones
1 30 60
2 36 54
3 32 32
Totales 98 146 Solucin no
Exceso -7 -7=-7x1 Factible
91 139
J Ij VPNj Observaciones
1 30 60
3 32 32
4 24 18
5 26 13
Totales 112 123 Solucin no
Exceso -21 -10.5=-21xO .5 Factible
91 112.5
En la Figura 7, para los nodos sin ramificacin (1 *), (1 ,2) Y (1,2*) el que tiene mejor
valor para la funcin objetiva es (1 ,2) puesto que 139 > 103.25 Y 139> 112.5, por lo
tanto se ramificar el nodo (1 ,2) . El algoritmo contina con el estudio de los nodos
(1 ,2,3) Y (1 ,2,3*).
J I VPN Observaciones
1 30 60
2 36 54
3 32 32
Totales 98 -1000 Solucin
imposible
82
INVf'STIGAC ION DE OPERAC IONES PARA INGEN IER I AS y ADM IN ISTRAC ION DE E~ I PRESAS
J I VPN Observaciones
1 30 60
2 36 54
4 24 18
5 26 13
Totales 116 145 Solucin no
Exceso -25 -12 .5=-25xO .5 Factible
91 132.5
De los 4 nodos sin ramificacin (mirar Figura 7): (1 *) , (1 ,2*) , (1 ,2,3*) Y (1 ,2,3) , el
nodo (1 ,2,3*) tiene el mejor valor para la funcin objetiva, por lo tanto se ramifica y
se procede con el anlisis de los nodos (1,2,3* ,4) Y (1,2 ,3* ,4*).
J I VPN Observaciones
1 30 60
2 36 54
4 24 18
5 26 13
Totales 116 145 Solucin no
Exceso -25 -12 .5=-25xO .5 Factible
91 132.5
83
LU IS A L BERTO RINCON ABR IL
J J VPN Observaciones
1 30 60
2 36 54
5 26 13
Totales 92 127 Solucin no
Exceso -1 -0 .5=-1 xO .5 Factible
91 126.5
J J VPN Observaciones
1 30 60
2 36 54
4 24 32
5 26 13
Totales 116 -1000 Solucin
imposible
Este nodo presenta unas condiciones similares a las ocurridas para el cuadro 7,
por lo tanto la solucin es imposible . El valor, que en el anterior cuadro se asign a
la funcin objetiva, es debido a la solucin imposible.
J J VPN Observaciones
1 30 60
2 36 54
4 24 18
Totales 90 132 Solucin Factible
84
INVEST IG,\C ION DE ()I'ERAC IONES P,\ RI\ INGEN I ER I,\S y I\DM IN ISTR AC ION D E EMPR ESAS
Invertir:
Hay que hacer notar que el nmero total de posibles soluciones en este problema
es ~(S)
L. . = 2'
c(J k
.= 32 , de las cuales el proceso de bifurcacin y acotacin
PROBLEMA.
Para los 4 proyectos independientes del Cuadro 13, se quiere establecer 'la mejor
combinacin de ellos , asumiendo que los Flujos de fondos netos ocurren despus
85
L U IS ,\ I.I3ERTO RI NCON ,\131< 11.
PROYECTO
A B C D
Inversin inicial 50000 20000 25000 30000
Flujo de fondos (neto anual) 20000 10000 15000 16000
Vida econmica del proyecto (anos) 14 12 10 8
Solucin :
( 1 + i )" - I
Donde el factor: (P I A, i . n ) = - , permite calcular el valor presente neto de
i( 1+ i )"
Los cuatro proyectos son Factibles , por cuanto el VPN de cada uno de ellos no
sobrepasa la inversin propuesta .
Con base en los ndices calculados los proyectos deben ordenarse en la siguiente
forma :
86
INVEST IC; ,\C ION DE OI'E R!\C IONES I',\ I{ ,\ INl;EN IERI ,\S y ,\ D ~ II N I ST R i\C I ON D E EMPR ESAS
Al travs de las tab las siguien tes se usar la tcnica (Al gori tmo) descrita en el
ejemplo anterior.
J Ij VPNj Observaciones
1 25000 37886
2 20000 24392
3 30000 3 1393.6
4 50000 422 10
Totales 125000 13588 1.6 Solucin no
Exceso -25000 -2 11 05=-25000xO.8442 Factible
100000 114776.6
J I VPN Observaciones
2 20000 24392
3 30000 3 1393 .6
4 50000 422 10
Totales 100000 97995.6 Solucin Factible
Analizando la Figura 2, entre los nodos (1) y (1*) , se debe ramificar a (1) y anal izar
(1 ,2) Y (1 ,2*).
87
LU IS I\ Ll lERTO RINCON i\BR IL
J I VPN Observaciones
25000 37886
2 20000 24392
3 30000 3 1393 .6
4 50000 422 10
T otales 125000 13588 1.6 Solucin no
Exceso -25000 -21 105=-25000xO .8442 Factible
100000 11 4776.6
Factible
Imposible
88
INVEST IG /\CION DE OPERAC IONES P,\Ri\ INGEN IER I AS y i\D~ II N I S T RAC I ON DE E~ I P R ESAS
J I VPN Observaciones
1 25000 37886
3 30000 31393.6
4 50000 42210
Totales 105000 111489.6 Solucin no
Exceso -5000 -4221 =-5000xO. 8442 Factible
100000 107268.6
J I VPN Observaciones
1 25000 37886
2 20000 24392
3 30000 31393 .6
4 50000 42210
Totales 125000 135881.6 Solucin no
Exceso -25000 -21105=-25000xO.8442 Factible
100000 114776.6
J VPN Observaciones
1 25000 37886
2 20000 24392
4 50000 42210
Totales 95000 104488 Solucin Factible
Del anlisis de la Figura 8, con base en los valores para la funcin objetiva , es
claro que se debe ramificar el nodo (1 ,2,3) Y proceder a analizar los nodos :
(1 ,2,3,4) Y (1 ,2, 3,4*) .
89
LU IS ,\LBERT O RINCON ,\ BRIL
J VPN Observaciones
1 25000 37886
2 20000 24392
3 30000 31393.6
4 50000 42210
Totales 125000 136881 .6 Solucin imposible
Este nodo es imposible porque exige tener en cuenta las 4 alternativas , obligando
a sobrepasar la disponibilidad .
J VPN, Observaciones
1 25000 37886
2 20000 24392
3 30000 31393 .6
Total es 75000 93671 .6 Solucin Factible
Invertir:
90
IN\ I S'II (;'\C ION 1)1. 0 1' 11< \C IONES P,\ R,\ ING L N IERI \S y ,\D~ II N I S 'I R,\C ION DE H IPRES ,\S
1.1. Use la herramienta Solver de Ex cel para resolver el problema 2.2 de los
camiones con espacio refrigerado y no refrigerado de la seccin 2.9.
Artculo j 1 2 3 4 5
PesoW 5 8 3 2 7
Volumen VI 1 8 6 5 4
Inqreso R 4 7 6 5 4
El pe so y el volumen mximo que se puede cargar estn dados por 112 y 109
unidades,
91
L UIS A LB ERTO RI NCON A J3RIL
1.4. La tabla siguiente muestra que las mquinas 1 y 2 pueden fabricar los artculos A
y B mientras que la mquina 3 nicamente produce el artculo A. La empresa
dispone de una semana para cumplir un pedido de 2000 unidades del artculo A y
1800 unidades del artculo B. Si los precios de venta son 2000 $/ unidad para A y
1500 $/unidad para B.
Costo en $/unidad
Mquina Artculo Artculo Capacidad de
A B produccin semanal
1 1000 800 900 artculo A
900 artculo B
2 600 600 800 artculo A
1200 artculo B
3 700 2000 artculo A
2. Programacin Binaria.
2.1. Use la herramienta Solver de Excel para resolver el problema de los cuatro
proyectos independientes del Cuadro 13 resuelto en este captulo.
2.2. Una compaa debe adquirir al menos 500 Ton de materia prima, tiene las
siguientes ofertas:
Proveedor A B C D E
Cantidad (Ton) 150 200 180 240 300
Costo total (Dlares) 15000 18000 18000 21000 27000
92
2.3. CO IC, Contratistas de obras de Ingeniera Civil , tiene la posibilidad de contratar
o no cada uno de los seis proyectos para los cuales se muestra en la tabla
siguiente, los ingresos derivados y los costos globales, los cuales no se pueden
transferir de un rubro a otro. La empresa har los contratos que le signifiquen el
mayor Ingreso neto total.
93
4. EL PROBLEMA DEL TRANSPORTE .
Tiene que ver con encontrar un plan de costo mnimo para transportar una
mercanca desde varios orgenes hasta varios destinos. Este modelo se puede
extender para resolver numerosas aplicaciones que no se relacionan con el
transporte dentro de los problemas de control de inventarios, flujo de efectivo,
asignacin de recursos.
94
INV rS I IG i\CION DE OPERAC IONES P,\Ri\ INGEN IERI \S y i\D~ II N I ST R I \ C I ON 1)1: U IP RES ,\S
que deben enviarse desde cada origen i-simo hasta cada destino j-simo , si el
costo unitario de transporte entre stos es cj y cada destino demanda b j unidades
mientras que cada origen dispone a unidades .
Orgenes Destinos
X 11 , C 11
Calcular el nmero de unidades que se deben enviar desde cada uno de los
orgenes hasta cada uno de los destinos, atendiendo la demanda de los destinos y
las ofertas de los orgenes para minimizar el costo total de transporte.
95
1 1 ' 1\ \1 ;I.I~ 1() 1< 1r>:( '()'\J ,\1l1< 11.
X ij : Cantidad que ser enviada desde el origen i-simo (i=1 , .... ,m) hasta el destino
j-simo (j=1 , .... ,n).
Expresin matemtica que calcula el costo total de transportar las X ij por cada una
de las rutas i ~j . Se supone que C ij es el costo de transportar una unidad desde el
origen i hasta el destino j,
11 111
M in (C) = IIci Xi
j= l i= l
4.2.4 Restricciones.
X l1 + X 12 + X 13 + ...... + X 1n ::::: a 1
11
Esto es: IX
=l
'1 ::; (/ i para i= 1,2, .... ,m
96
IN\ I S II( ;,\CION 111e OI'FRACION I .S 1' ,\1, /\ I N(~ le N II : RI ,\S y i\1)~ II N I STR\CION DI: E~ IPRE S\S
111
" X /1 ? b1 para J-
Est o es.. L.. '- 1 ,2 ,.... ,n
,~I
11 111
Mill(C) = c X i
i=1 i=1
11
Sujeto a: X ii ::;
) =1
O para i=1 ,2,.... ,m
111
X I} ?b paraj=1,2 ,.... ,n
;= 1
4.2.6 Particularidad.
Aunque para satisfacer totalmente la demanda debe tenerse :La; ~ :Lb j , el algoritmo
de solucin parte de un modelo expresado de tal manera que todas las
restricciones generadas por la oferta y la demanda resulten igualdades. Por lo
tanto:
97
LU IS ,\I.13ERT O RINCON .\13 RI I.
11 111
Min(C) = Ci X i
=I i= 1
1/
X i/ =Oi
Sujeto a: j= 1
111
L X ;i =b j
;= 1
XIJ" -> O
DESTINOS
ORIGEN ES 1 2 3 n Oferta
1 ~ ~ ~ L L ~ a1
X11 X 12 X13 X1n
2 ~ ~ ~ L L ~ a2
X21 X22 X23 X2n
3 ~ ~ ~ L L .~
a3
X 31 X 32 X 33 X3n
L L L L L L
M ~ ~ ~ L L .~
am
Xm1 Xm2 Xm3 Xmn
Dema nd a b1 b2 b3 bn
98
IN\ ' I: ST ll\C ION DI. O PLR ,\C IONr.S P,\ Ri\ INGEN I ICRI ,\S y ,\D~ II N I STR\ Cl ON DE E ~ I PR ES\S
Existen varios mtodos para obtener una prime ra soluci n bsica factible , pero
entre ellos se destacan: Mtodo de la Esquina Noroeste, Mtodo sucesivo del
menor costo un itario y Mtodo de aproximacin de Vogel.
Es un procedimien to heurstico que suele producir una primera solucin mejor que
los dos anteriore s; pues con frecuencia sta resul ta una so lucin ptima o cercana
a la ptim a. Los pasos del procedimien to son los siguien tes:
99
I 1I 1S 1\ 1 B I RTO RINCON AB RI L
(a) Paso 1. Se calcula una penalizacin para cada fila (y columna) restando el
menor elemento de costo de la fila (columna) del elemento de costo menor
siguiente en la misma fila (columna).
(b) Paso 2 . Se identifica la fila o columna con la mayor penalizacin , los empates
se rompen arbitrariamente. Se asigna el mayor va lor posible en la fila o
columna seleccionada con el costo uni tario ms bajo de la misma .
Sucesivamente se procede de esta manera hasta asignar todo el flujo posible.
DESTINOS
ORIGEN ES 1 2 3 4 Ofe rt a
1 ~ L--- ~ ~ 300
Xl l X12 X13 X14
2 ~ ~ lJJL ~ 500
X2l X22 X23 X24
3 L--- ~ LR ~ 100
X31 X32 X33 X34
Demanda 100 300 300 200
100
INVESTIGAC ION DE OPERACIONES PAR I\ I NGEN I ER I AS y ADM IN ISTR AC ION DE EMPRESAS
DESTINOS
ORIGENES 1 2 3 4 Oferta
1 ~ ~ ~ ~ 300
100 200
2 ~ ~ U---- ~ 500
100 300 100
3 ~ ~ ~ ~ 100
100
Demanda 100 300 300 200
lOJ
L U IS ALBERT O RINCON ABR IL
DESTINOS
ORIGEN ES 1 2 3 4 Oferta
1 ~ l---- ~ ~ 300
300
2 ~ ~ Ll----- ~ 500
300 200
3 ~ ~ ~ 100
100 l----
Demanda 100 300 300 200
102
INVES1 IGAC IO N DE OPER AC IONES PA RA ING EN I ER I,\ S y A D ~ I I N I S TR AC I O DE EMPR ES ,\ S
(b) Paso 2. Como el elemento de menor costo est en la misma fila p, entonces en
la columna r, se busca un valor X kr > O con costo Ckr .
(e) Paso 3. Se identifica el costo Ckq, que cierra un ciclo tal como lo muestra la
figura 10, para compensar las unidades cambiadas del flujo pq al flujo pr ,
trasladando del flujo kr al flujo kq .
Ejemplo. Para el caso de los tres centros de produccin (orgenes) y los cuatro
distribuidores (destinos) tratado en la seccin anterior, prtase de la solucin inicial
encontrada por la esquina Noroeste y obtngase la solucin ptima.
103
LU IS c\LBERTO RINCON f\BR I L
DESTINOS
ORIGENES 1 2 3 4 Oferta
1 L~ ~ ~ 300
100 2 OO L------
2 ~ ~ ~ ~ 500
100 300 100
3 L------ ~ ~ ~ 100
100
Demanda 100 300 300 200
(1,2) (1,4)
- (2,2) (2,4)
~c= - 40 + 14 - O + 22 =- 4
104
INVESTIG /\C ION DE OPERAC IO ES PARA I NGEN IER I AS y AD~ II N I STRAClON DE EMPRESAS
Segundo tablero
DESTINOS
ORIGENES 1 2 3 4 Oferta
1
100
l?iL
100 ~ ~
100
~ 300
2 ~ ~ ~ ~ 500
200 300
3 ~ l1.-- LR ~ 100
100
Demanda 100 300 300 200
(1,1) (1,4)
(3,1) (3,4)
~c= - 36 + O - 20 + 22 = - 34
Figura 12. Cambio de flujo de unidades del segundo tablero.
105
L UIS A I. BE RTO RINCON AB RIL
Tercer tablero
DESTINOS
ORIGEN ES 1 2 3 4 Oferta
~
1
100 ~ ~
200
~ 300
2 ~ ~ l.!--- ~ 500
200 300
3
100 ~ ~ LR ~ 100
SOLUCiN PTIMA:
l . Un intermedia rio del mercadeo agropecuari o tie ne soli citu des (demanda) de 4 centros de
acopio por las ca ntidades de un determin ado producto qu e se muestran en la tabla. El
106
INVEST IG ,\C IO N DE OPERAC IONES PA RA INGEN I ERI AS y AD~ II N I ST R AC I ON DE E~ I P R ESAS
Area de distribucin
Refinera 1 2 3 4
1 120 180 200 180
2 200 300 100 150
3 150 250 100
107
LUIS I\Ll3ERTO RINCON ABR IL
108
5. EL PROBLEMA DE ASIGNACiN
Determinar cmo asignar cada uno de los elementos (asignados i =1 ,2 ,3, ........ ,n) a
cada una de las actividades (localidades j =1 ,2,3, ..... ,n), de tal manera que a cada
localidad le corresponda uno y un solo asignado si para cada actividad existe un
coeficiente de efectividad y se debe optimizar la efectividad total.
109
L U IS ALBERTO RINCON ABRIL
110
INVEST IGAC ION DE O PER /\C IONES PARA I NGEN I ER I AS y i\DM IN IST RAC ION DE EM PR ESAS
JI 11
Op t (Z) = Cij X i
j=1 i=1
5.1.4 Restricciones.
1/
Esto es: X ij = J
j= 1
para i=1,2,.... ,n
1/ 1/
Op /(Z) = cij X ij
j=1 i=1
111
LU IS I\ L BERTO RINCON ABRI L
1/
Sujeto a: L X li =]
j=1
para i=1 ,2,.... ,n
11
L Xi =1
;= 1
para j= 1,2, .... ,n
Al comparar este modelo con el problema del transporte , se observa que sus
estructuras son similares. De hecho, el problema de asignacin es slo un caso
especial de los problemas de transporte en donde los orgenes son los
asignados y los destinos son las asignac iones, tareas o localidades , que
cumple :
112
INVESTIGAC ION DE OPE RAC IONES P\ RA I NGEN IERI AS y AD~ II N I S TR AC I ()N DE E~ IPR ESAS
Localidades
Asignados 1 2 3 n
1 ls.L ~ lsL L L ~ 1
X11 X 12 X13 X1n
2 ~ ~ ~ L L ~ 1
X21 Xn X23 X2n
3 ~ L52R ~ L L ~ 1
X31 X32 X33 X 3n
L L L L L L
N ~ ~ Ls& L L ~ 1
Xn1 Xn2 X n3 Xnn
1 1 1 1
113
L UIS ,\ Lll mTO RI NCON ABR IL
Piezas
Torno P1 P2 P3 P4
T1 26 32 24 18
T2 34 20 34 40
T3 20 14 22 12
T4 18 16 24 14
P1 P2 P3 P4
T1 ~ LR ~ U--- 1
1
T2 ~ ~ ~ ~ 1
1
T3 ~ ~ ~ ~ 1
1
T4 U--- l!-- ~ ~ 1
1
1 1 1 1
P1 P2 P3 P4
T1 ~ LR ~ U--- 1
1
T2 ~ ~ ~ ~ 1
1
T3 ~ L!- lR ~ 1
1
T4 L1--- ~ ~ ~ 1
1
1 1 1 1
IJ4
IN\ ' ES'II(;,\C ION DE OPER ,\C IONES P,\R ,\ INGE IER I,\S y AD~ II N I STRAC I O DE E~ I PRES ,\S
Piezas
Torno P1 P4
P2 A
T1 26 32 \,24} 18
T2 ( 34) 20 34 4Q
T3 ~ A 22 (12
T4 18 \. 16) 24 14
Piezas
Torno P1 P2 A P4
T1 26 Jg \,24} 18
T2 34 ( 20) 34 4Q.
T3 20 14 22 (12
T4
--
( 18) 16 24 14
liS
LU IS A LBERTO RINCON ABR IL
Nuevo Producto
Ejecutivo P1 P2 P3 P4
E1 90 60 80 50
E2 90 50 60 50
E3 70 70 50 60
E4 60 70 80 80
Nuevo Producto
Ejecutivo P1 P2 P3 P4
E1 90 60 80 50
E2 90
" 50 60 50
E3 70 70
" 50 60 "
E4 60 70 80 80
"
De conformidad con esta solucin inicial, deben hacerse las siguientes
asignaciones:
11 6
I VrST ll; \C ION DE OPERAC IONES P\Ri\ INGrN IERI \S y \D~ II N I ST R AC I O D E EMPRESAS
Nuevo Producto
Ejecutivo P1 P2 P3 P4
E1 90 60 80 50
E2 90 " 50 60 50
E3 70 70 50
" 60
E4 60 70 "80 80
"
Rendimiento promedio = R = )4 (90 + 60 + 70 + 80) = 75
Nuevo Producto
Ejecutivo P1 P2 P3 P4
E1 90 60 80 50
E2 90 50 60 " 50
E3 70 " 70 50 60
E4 60 70
"80 80
"
117
L U IS ALBE RTO RI NCON I\BRIL
Mquina
Artculo 1 2 3 4
1 15 15 6
2 21 12 6 9
3 27 12 15
4 21 6 18 21
2. Hay que asignar cinco vendedores a cinco zonas de venta. La capacidad de venta de
cada vendedor en cada zona en una escala de O a 100, se muestra en la siguiente
tabla . Si se desea realizar la asignacin de los cinco vendedores sobre la base de la
mayor capacidad promedia, cmo se debe hacer?
Zona de Ventas
Vendedor Z1 Z2 Z3 Z4 Z5
V1 80 50 60 20 70
V2 60 50 50 90 80
V3 50 60 70 70 60
V4 40 70 20 80 40
V5 70 20 70 80 80
J J8
6. MODELOS DE REDES
119
LU IS A LBERTO RINCON AI3 RIL
Ejemplo. Supngase que una persona debe resolver el problema de viajar desde
un origen O hasta un destino final F a lo largo de una ciudad . La figura 13 muestra
las diferentes rutas de autobuses para hacerlo. En cada una de esos caminos
aparece un nmero que indica la longitud del mismo o el costo de escoger dicho
camino o el tiempo empleado en recorrerlo. Si la persona est restringida a viajar
de izquierda a derecha sin devolverse. La pregunta que se debe resolver es: Cul
es la ruta ms corta entre O y F? , en otras circunstancias , Cul es la ruta de
costo o tiempo mnimo entre O y F?
120
INVEST IGAC ION DE OPERAC IONES PA RA INGEN IERI AS y ADM IN IST R,\C ION DE EM PR ESAS
Una red consiste en un conjunto de puntos y lneas, stas unen a los puntos por
parejas. Los puntos se llaman nodos (o vrtices). La red de la figura 13 tiene siete
nodos representados por siete crculos . Las lneas se llaman arcos (o ligaduras ,
aristas o ramas). La red de la figura 13 tiene 13 arcos que corresponden a los 13
caminos de este sistema de transporte de la ciudad. Los arcos se definen con los
nodos terminales ; por ejemplo, AB es el arco entre los nodos A y B en la figura 13.
Los arcos de una red pueden tener un flujo de algn tipo que pasa por ellos , por
ejemplo , el flujo de autobuses sobre los caminos de la ciudad. Un arco dirigido
slo permite el flujo en una direccin. La direccin se indica mediante una cabeza
de flecha . La notacin de un arco dirigido se hace con el nombre de los nodos que
une , colocando primero el nodo de donde viene y despus el nodo a donde va,
esto es , un arco dirigido del nodo A al nodo B debe indicarse como AB A~B . Un
arco de ligadura o no dirigido permite el flujo en ambas direcciones.
Una red que slo tiene arcos dirigidos se llama red dirigida. Si todos sus arcos
son ligados , se trata de una red ligada. Si dos nodos no estn unidos por un arco
a veces resulta conveniente saber si estn conectados por una serie de arcos . Una
121
LU IS I\LBERTO RINCON ABR IL
trayectoria entre dos nodos es una sucesin de arcos distintos que conectan
estos nodos. Por ejemplo , la sucesin de arcos OB , BE Y EF conforman una de las
trayectorias que conectan a los nodos O y F en la figura 13. Pero otra trayectoria
es O ~ e~ E ~ F. Una trayectoria dirigida del nodo 1 al nodo j es una sucesin
de arcos con direccin hacia el nodo j, de manera que el flujo del nodo 1 al nodo j
a travs de esta trayectoria es factible . Una trayectoria ligada del nodo 1 al nodo j
es una sucesin de arcos cuya direccin puede ser hacia o desde el nodo j. Un
ciclo es una trayectoria que comienza y termina en el mismo nodo. Dos nodos
estn conectados si en la red existe al menos una trayectoria entre ellos. Una red
es conexa si cada par de nodos estn conectados; por lo tanto, la red de la figura
13, es conexa y dejar de serlo si se suspenden los arcos A ~ B, A ~ D YA ~ F
La capacidad del arco es la cantidad mxima de flujo que puede circular en ste .
En los nodos fuentes , el flujo que sale de ellos excede el flujo que entra. En los
casos contrarios , esto es , el flujo que llega excede al que sale, se tienen nodos
demandas. En un nodo de transbordo o intermedio, el flujo que entra es igual al
que sale .
Para el anl isis de este modelo se puede suponer una red conexa y no dirigida con
dos nodos principales llamados origen y destino. A cada uno de los arcos no
dirigidos se asocia una distancia. El objetivo del problema es encontrar la ruta ms
corta o trayectoria con la mnima distancia total, que va desde el origen al destino.
122
INVEST IGAC ION DE OPERAC IONES PARA INGEN I ER I AS y ADM IN ISTR AC ION DE EMP RESAS
En cada una de las k-simas iteraciones se debe definir para el k-simo nodo , la
distancia ms corta desde el origen hasta el k-simo nodo. Si d ik define la distancia
entre los nodos i, k; entonces se puede calcular la distancia ms corta desde el
origen hasta el nodo k-simo con la siguiente expresin:
Ejemplo. Encontrar la ruta ms corta desde el origen (nodo O) hasta el final (nodo
F) a travs del sistema de vas que se muestra en la figura 13. En la tabla siguiente
se encuentran los resultados obtenidos al aplicar el algoritmo anterior a este
problema .
123
LU IS ALBERTO RINCON AB RIL
Las dos ltimas columnas de la tabla anterior, resumen la informacin del ltimo
nodo resuelto ; esto es , la distancia de la ruta ms corta desde el origen a este
nodo y la ltima rama en esta ruta ms corta . Adems muestra que la ruta ms
corta para el sistema de vas de la figura 13 es O~A~F y mide 20 unidades.
124
INVESTIGAC ION DE OPERAC IONES PARA I NGEN IERIAS y ADMIN ISTRAC ION DE EMPRESAS
L25
L U ISALBERTO RI CON ABR il
126
INVrST I(, ,\C ION DE OPER ,\CIONrS P,\RA INCEN IER Ir\S y \D~ II N I STR ,\C I ON DI" E~IPRES\S
Figura 14. Posibilidades de construir una red elctrica entre siete municipios.
127
LUIS ALBERTO RINCON ABR I L
En la figura 14-1 , la red elctrica definitiva aparece con lnea continua. Como en
este problema hay n =7 nodos, dispone de n - 1 =6 ligaduras y ningn ciclo para
calificar como un rbol de expansin .
......
......
......
20............ ......
......
/
12 /
/
/
/
20/
/
/
/
/
Figura 14-1. Diseo para construir una red elctrica entre siete municipios.
128
INVEST IGAC ION DE OPERAC IONES PA RA INGEN IER IAS y ADM IN ISTRAC ION DE EM PRESAS
Los problemas de esta clase son aplicaciones de Programacin Lineal con una
caracterstica especial, siempre tienen una solucin ptima con base en nmeros
enteros si los datos de entrada tambin son enteros. Esto permite el diseo de
algoritmos eficientes que pueden ser aplicados a la solucin de una variedad de
problemas combinatorios. Entre estos se disponen, el algoritmo de flujo mximo, el
clculo de flujos de costo mnimo.
129
LU I S \ U 3ERTO RINCON ABR IL
I
I
I
I
, Fuente I
:_____ .____ J Depsito
Estaciones de
Refineras
bombeo
, Terminales
Supngase que cada arco (i, j) de una red dirigida tiene asociado un nmero no
negativo Cj denominado la capacidad del arco, Si esta capacidad representa la
mxima cantidad de algn artculo que pueda enviarse a travs del arco, la
pregunta inmediata es, Cul es la cantidad mxima del artculo que se puede
enviar de un nodo a otro , dentro de la red?
130
INVEST I(; ,\C ION !lE O PEI,AC IONES PA RA INGEN I ERI \S Y , \I)~ II N I STR \CION DE EM PR ESAS
6.5.2 Restricciones.
o S Xii S Gii
El trmino V representa el valor del flujo total. Se llama flujo posible a cualquier
conjunto de valores que satisfacen las restricciones anteriores. Es evidente que
este modelo corresponde a un problema lineal en donde el objetivo es maximizar el
valor de V sujeto a las anteriores restricciones.
Max(V) = X 12 + X 13
Sujeto a las restricciones:
X 12 + X 32 - X 24 =O
X 13 - X 32 - X 34 =O
X 12 S 4 , X 13 S 3 , X 32 S 2 , X 34 S 2 , X 24 S 4
Xii ~ O
J31
LU IS ALBERTO RINCON ABR IL
4 (4,3) 4 ,4)
(2,1)
(3,2) (2,1)
Figura 16. Solucin factible para una Red de flujo mximo propuesta.
La figura 16 ilustra un flujo factible desde el nodo 1 al nodo 4 para una red . El
primer nmero de la pareja asociada con cada uno de los arcos es la capacidad
del arco y el segundo nmero es el flujo del arco.
El modelo matemtico para la figura 16, muestra que este problema es soluble por
el Mtodo Simplex. Sin embargo , se dispone de un algoritmo basado en dos
conceptos intuitivos: red residual y trayectoria aumentada . Una vez se han
asignado flujos a los arcos de la red original , las capacidades restantes o
residuales conforman la red residual que sirve para asignar flujos adicionales.
132
IN\ I SII (;.\(' ION DE O I'LR ;\(' IO N I.S I'.\ R/\ IN(; I 'JlERI AS y \ D ~ II N I S l RA C ION D r E~ IPR ESAS
(40,O)
Cuando se inicia el Algoritmo , todas las trayectorias son de aumento , por cuanto
para cada una de ellas , todos los arcos tienen capacidad residual. Aplicando el
algoritmo para la red residual 1 ~2~6~7 , se obtiene la capacidad residual =
Menor {80 - O, 30 -O , 60 -O} = 30. Flujo que se agrega a esta trayectoria en la
figura 18.
133
L UIS ALBERTO RINCON ABR IL
~ (1 0,0)
. F~.'.~~.~r0 . . . .(~.~:~~ . . . .
'-l..
..... ...~50,0) ~1 0,0) ..../
(40,0)...
. ~20 , O) . .l
..,/
0. . . J.4~,0)
:\
:~/
... ::.. (60,0)
(40,30)
.. ,(50,0)
.................
(40 ,40)
134
INVESTIG /\C ION DE OPERAC IONES PA RA INGEN I ER I,\S y AD~ II N I S TR AC I ON DE EM PR ESAS
(40,30)
(40,40)
Figura 20. Red sin trayectorias de aumento para el ejemplo de f.lujo mximo.
Una solucin final es ptima si para toda trayectoria indiscriminada que se quiera
asignar no puede evitar el uso de cancelacin de flujos asignados con anterioridad.
Puede resultar difcil , cuando las redes son grandes, encontrar una trayectoria de
aumento. El siguiente procedimiento sistemtico simplifica el hecho. Se comienza
135
1 L ' I ~ 1\ L llFR"1() RI NCON ABR il
por analizar todos los nodos que se unen desde el origen con un arco y con
capacidad residual positiva. Enseguida , para cada uno de estos nodos , se
determinan todos los nuevos nodos a los que se llega desde este nodo con un solo
arco con capacidad residual positiva. Esto se repite hasta llegar al nodo final. Se
obtiene como resultado , un rbol con todos los nodos a los que se puede llegar
desde el origen, a lo largo de una trayectoria con capacidad de flujo residual
estrictamente positiva. Este procedimiento de abanico siempre identificar una
trayectoria de aumento , si existe . Aunque el anterior procedimiento es muy directo,
ser til poder reconocer cundo se tiene un patrn ptimo sin tener que buscar de
manera exhaustiva una ruta que no existe . A veces es posible esto con el resultado
de un teorema importante de teora de redes , conocido como el teorema del flujo
mximo - cortadura mnima. Una cortadura se define como cualquier conjunto
de arcos dirigidos que contienen al menos un arco de cada trayectoria dirigida que
va del nodo origen al nodo destino. El valor de la cortadura es la suma de las
capacidades de los arcos de la cortadura.
Teorema del flujo mximo - cortadura mnima. Para cualquier red con un solo
nodo origen y un solo nodo destino, el flujo mximo factible del origen al destino
es igual al valor de la cortadura mnima para todas las cortaduras de la red.
El anlisis para la red residual inicial de la figura 17, presenta el siguiente conjunto
de cortes con la correspondiente capacidad
136
IN\' I S'II (AC ION DI. OPFRAC IONES PARA INGEN I ER I AS y AD~ II N I STRAC I ON DE EMPRESAS
Por lo tanto , 120 es el valor de la cortadura mnima que equivale al flujo mximo
factible presentado en la figura 20,
Es una solucin muy eficiente que aborda un conjunto muy amplio de aplicaciones ,
tomando en cuenta un flujo a travs de una red con capacidades limitadas en sus
arcos, Tal como se tiene para el problema de la ruta ms corta, considera un costo
(o distancia) para el flujo a travs de cada arco. E igual que para los problemas del
transporte y asignacin , puede considerar el flujo desde varios orgenes (nodos
fuente) hasta varios destinos (nodos demanda).
El problema del flujo de costo mnimo se puede resolver de manera tan eficiente
porque se puede formular como un problema de programacin lineal y resolver
mediante una versin simplificada llamada mtodo Smplex de Redes. En la
siguiente seccin se describir el uso del mtodo Simplex.
En una red conexa dirigida con al menos un nodo origen y al menos un nodo
destino, se dispone la siguiente informacin:
b = flujo neto generado en el nodo i. En este caso, b > O en los nodos fuentes, b
< O en los nodos demandas y b = O en los nodos transbordos .
137
L U IS A LBERTO RINCON A BR IL
Variables de decisin.
Funcin Objetiva.
Minimizar el costo total de enviar los recursos disponibles a travs de la red para
cumplir con la demanda.
11 11
Mil/ (Z) = e" X " . Las sumas se toman slo sobre arcos existentes .
i = l j= J
Restricciones.
Para cada nodo , el flujo total que entra menos el flujo total que sale es igual al flujo
neto generado en este nodo.
El flujo a travs del arco i~j, debe ser positivo, sin exceder la capacidad del arco .
flujo de costo mnimo tenga soluciones factibles , debe cumplir que Lb,
"
= O. Esto
i= 1
es , el flujo total generado por los nodos orgenes debe ser igual al flujo total
absorbido por los nodos destinos.
En muchos problem as, las cantidades b i y d ij sern valores enteros ; en este caso ,
en la soluci n las cantidades de flujo Xij tendrn que ser tambin enteros . Sin
138
I ' \'r.STIGAC ION DE OPER ,\C IONES P\R\ INGE IER I\S y \D~ II N I STR /\C I ON DE E~ IPRE S r\S
Variables de decisin.
Funcin Objetiva.
139
I. UIS A l BERTO RI NCON AB RI L
Restricciones.
Restricciones de no negatividad.
50 unidades de 30 unidades
900 Dl/unid demandadas
"O
c:
--o
::1
:o
o
o
N
40 unidades de 60 unidades
produccin demandadas
140
IN\'LS1IC; I\C10N I) \. OPER I\C ION I: S P,\R ,\ I N(;rN I ER I AS y i\D~ II N I ST R i\C I ON DE E~ IPR ESAS
los problemas de flujo de costo mnimo y es esta estru ctura especial la que lleva a
la propiedad de soluciones enteras, De otro lado , cuando se tienen n restricciones
de nodo, nicamente hay n-1 independientes, esto es , una de ellas es redundante ,
Esto se puede comprobar porque al sumar todas estas ecuaciones, se obtienen
ceros en ambos lados , Como existen n - 1 restricciones independientes , estas
ecuaciones proporcionan n- 1 variables bsicas para una solucin bsica factible ,
A B e D E F G H J K
18 Nodo 1 _ SS'S$14 - CS'C$14 =05'0$14 = ES 'E $14 =FS'F$14 =GS'G$14 =HS'H$14 =SUMA(S1S.H1S)
= 50
Nodo 2 - S6'S$14 _C6'C$14 _06 ' 0$14 _F6'F$14 =F6'F$14 =G6 ' G$14 - H6'H$14 - SUMA(S 19 H 19)
19 = 40
20 Nodo 3 =STS$14 =CTC$14 _ OTO$14 - ETE$14 _ FTF$14 _GTG$14 =HTH$14 - SUMA(S20H20)
= O
21 Nodo 4 - SS'S$14 - CS'C$14 = OS'O$14 = ES'E$14 =FS'F$14 =GS ' G$14 =HS'H$14 = SUMA(S21 H21)
= -30
22 Nodo 5 - S9'S$14 - C9'C$14 _ 09 ' 0$14 =E9'E$14 _F9'F$14 - G9'G$14 _ H9'H$14 -S UMA(S22H22)
= -60
23 Arco 1,2 _SlO ' 8$14 - C10'C$14 =010'0$14 =E10'E$14 =F10'F$14 =G10 ' G$14 =H10'H$14 =SUMA(S23 H23)
< 10
24 Arco 3, 5 _S11'S$14 - C11 ' C$14 011'0$14 - E11'E$14 _ F11'F$14 - G11'G$14 _ H11'H$14 - SUMA(S24 H24)
< 80
25
14 J
L U I S I\ L I3E RTO RINCON A IlRI L
Parmetros de Solver
CelQ," objetivo:
Resolver
\Ilor de l." celda ob jetivo :
Cerrar
(-- [:1i:dmo (;- r',1i'o.irno C' y'alores de: lo
Cam!djando las celdas
Qpciones , , .
Suje tas a las siguientes restric cines:
o D D
142
IN" I' STI(, \C ION DI. OPLRAC IONES PAR ,\ IN(,EN IERIAS y \D~ II ISTR \C IO DE E~ I PRF.SAS
A B e D E F G H J K
Figura 24. Hoja EXCEL con la solucin SOLVER para la red de distribucin.
143
LU IS ALBERTO RINCON MlR IL
144
6.7 EJERCICIOS Y PROBLEMAS PROPUESTOS.
Red A
Origen
Red B
Ao Aoj
i 1 2 3
O 16 36 62
1 20 42
2 24
145
L UIS A LB ERTO RINCON ABRIL
3. Una compaa debe suministrar 1000 cajas de cartn por mes a una fbrica. Para los
prximos cuatro meses , el costo de fabricacin de cada caja ser $1000 en el primer
mes, $ 1800 en el segundo mes, $2000 en el tercer mes y $2800 en el cuarto mes. El
costo de mantenimiento y bodega por caja es de 600 $/mes. Si la produccin por mes
se realiza en mltiplos de 1000 Y se desea encontrar el programa de produccin ms
eficiente en trminos de costo , entonces se necesita formular el modelo como una
representacin de Red y resolverlo.
5. Considere para las Redes del problema 1 que los arcos son de ligadura y disee para
cada una el rbol de mnima expansin.
6. Modificar el valor del flujo 0---72 a 16 en la Red A del problema 1 y los valores de los
flujos 0---7 1 a 10, 0---73 a 20 y 6---78 a 16 en la Red B. En ambos casos considerar el
problema de flujo mximo, donde el origen es el nodo fuente y el destino el nodo
demanda . Las capacidades son los valores que se muestran en los arcos. Usando el
algoritmo de la trayectoria de aumento resolver el problema.
J46
IN\TST IG AClON IX OPERACIONES PARA INGEN IERI AS y I\D~'IINISTRACION DE EMPRESAS
cantidad hasta el almacn 2. Pero ambas plantas pueden usar camiones para mandar
hasta 500 unidades de cada planta al centro de distribucin , desde los que se puede
enviar hasta 500 unidades a cada almacn. La tabla siguiente muestra el costo unitario
de transporte por cada ruta , las cantidades que se producen en las plantas por periodo
y las cantidades que se requieren en los almacenes por periodo.
147
7. PROGRAMACiN DE PROYECTOS CON PERT-CPM.
148
INVEST IGAC ION DE OPE RAC IONES PARA INGEN IER I AS y ADM IN ISTR\C ION DE EM PR ESAS
Estas tcnicas fueron desarrolladas por dos grupos diferentes entre 1956 y 1958.
E. 1. du Pont de Nemours & Company desarroll el CPM como una aplicacin a
los proyectos de construccin y posteriormente Mauchly Associates, lo extendi a
nuevas aplicaciones. El PERT , fue producido por un grupo consultor para la Marina
de Estados Unidos, con el fin de programar las actividades de investigacin y
desarrollo del programa de misiles Polaris.
149
I. U IS A I. BERTO RINCON ABR IL
150
Regla 1. Cada actividad quedar representada por un slo arco en la red. Ninguna
actividad puede disponerse ms de una vez en la red . Diferente es el caso en que
una actividad se descompone en segmentos, los cuales pueden estar
representados por arcos separados. La colocacin de una banda transportadora en
un proceso de produccin puede hacerse en secciones.
151
LUI S ,\LB ERTO RIN C O N I\BRIL
I
I
F
Regla 3. Cada que se agrega una actividad a la red , se deben definir las
actividades que deben terminar antes de que esta actividad pueda comenzar, las
actividades que deben seguir a esta actividad y las actividades que deben
E!jecutarse simultneamente con esta actividad .
J52
IN\ r ~ Il l; \C ION DE OPERAC IONES PA R/\ INl;EN I ERI AS y i\D~ II N I S TR i\C I ON DE H IPRESi\S
F1 Y Fi Actividades
ficticias
Figura 27. Diagrama de red para el proyecto del traslado de las oficinas.
15 3
1.1I1S ALBERTO RINCON All RIL
Una ruta crtica define una cade na de actividades crticas que unen los eventos
inicial y final del diagrama de red e identifica todas las actividades crticas del
proyecto. El mtodo para determinar tal ruta se ilustrar con un ejemplo numrico.
Actividad A B C D E F G H I J
Tiempo 3 5 3 4 8 2 4 2 5 3
154
IN\TST IGi\C ION IX OPER ,\C IONES P\J~ \ INGEN I ER I /\S y i\DM IN ISTRf\C ION DE H I PRES r\S
Los clculo s hacia adelante para la figura 27 proporcionan los siguientes valores :
Clculos hacia atrs. Sea TT el tiempo de ocurrencia ms tardo , para todas las
actividades que terminan en el evento i. Si n es el evento de terminacin de todo el
proyecto , entonces , TT n = TP n e iniciar el clculo hacia atrs . En general , para
cada uno de los dems nodos i, el tiempo de ocurrencia ms tardo se calcular
como:
TT, = Mllfn,
, - d I! J
Los clculos hacia atrs para la figura 27 proporcionan los siguientes valores:
J55
LU IS ,\I.IlERTO RINCON A BRIL
Una actividad i~j est en la ruta crtica si satisface las tres condiciones siguientes :
TT = TP
TT j = TP j
TT j - TT = TP j - TP = dj
156
INVEST ICAC ION DE OPERAC IONES PARA IN(,EN I ER I\S Y ADM IN ISTRAC ION DE EMPRESAS
Una vez se haya encontrado la Ruta Crtica , se debe proceder a calcular todas las
holguras de las actividades no crticas. Para determinar estas holgu ras , es
necesario encontrar dos parmetros adicionales, el tiempo de in icio ms tardo
(lTj) y el tiempo de fina lizacin ms prximo (FPj) para cada actividad; los
cuales cumplen las siguientes expresiones matemticas :
ITj = TT j - dj
FPj = TP + dj
Holgura total HTj. Diferencia entre el mximo tiempo disponible para rea lizar la
actividad y su duracin ; esto es :
157
I. U IS i\ LllERTO RINCON ABR IL
Holgura libre HL. Suponiendo que todas las actividades comienzan tan pronto
como sea posible , es el exceso de tiempo disponible sobre su duracin para cada
actividad ; es decir:
HLi = TP - TP - d
Todos los clculos de ruta crtica , incluidas las holguras total y libre para las
actividades no crticas, pueden presentarse como aparecen en la tabla de la
pgina siguiente. En sta , se observa que las actividades crticas tienen las
holguras total y libre iguales a O.
Actividad Ruta d TP TP TT TT IT HT HL
i-7j
A 1 ~2 3 O 8 O 8 5 5 5
B 1 ~3 5 O 5 O 5 O O O
e 3~4 3 5 8 5 8 5 O O
F1 4~2 O 8 8 8 8 8 O O
D 2~5 4 8 12 8 12 8 O O
E 5~8 8 12 20 12 20 12 O o
F 4~6 2 8 10 8 16 14 6 O
F2 6~7 O 10 10 16 16 16 6 O
G 7~8 4 10 20 16 20 16 6 6
H 6~8 2 10 20 16 20 18 8 8
I 3~9 5 5 23 5 23 18 13 13
J 8~9 3 20 23 20 23 20 O O
158
IN\' I S I IG \l'ION DI 01' 1 { ,\C IONES PA R,\ INl; I: N IERI AS y I\I)~ II N I S TR \C I ON DE E~IPRE SAS
actividades simultneas por las limitaciones de personal y equipo . En este caso las
holguras totales para las actividades no crticas resultan muy tiles. Cambiando
una actividad no crtica (hacia atrs o hacia adelante) entre sus lmites TP y TT , se
pueden cumplir los requisitos de recursos. Aun en abundancia de recursos (no hay
recursos limitados) , se acostumbra usar las holguras totales para nivelar los
recursos sobre la duracin del proyecto completo. Esto significa una planeacin ,
uso y control de los recursos ms estable comparada con el caso donde el uso de
la fuerza laboral y de la maquinaria de trabajo cambia fuertemente entre un periodo
y otro.
Actividades crticas
. . .
.. '9'.
~.
Actividades no crticas
'-o
.- - - , - ---.------.----------,.-------'
1\: tF i:2 : ~
.~.;. ... .; ... .; ..':(. . .
~: : tr.=4 : t;'\
.~.~. ... ., ....... .,. .. -". ..~.
o
.. ..
4 8 12 16 20 ~4
Semanas del proyecto
J5 9
LU IS A L BERTO RINCON \BR IL
4-1 2 no consume tiempo , por lo tanto , se muestra como una lnea vertical. Las
actividades crticas se indican con lneas continuas. Los lmites de tiempo para las
actividades no crticas se muestran con lneas punteadas; tales actividades pueden
programarse dentro de esos intervalos , siempre y cuando no se alteren las
relaciones de precedencia.
160
INVEST IGAC ION DE O PERAC IONES PARA INGEN I ER I\S y AD MI N ISTR AC ION DE EMPRESAS
[2111 +
= -J {/ +-
a+ b) ] = - b+ 4111
T,' 6- -
I 1 (
"
161
LU IS ALBERTO RINCON ,\ llR IL
a
Simtrica I
b
/ ~'//I"
/
,-
a m b
Figura 29. Distribucin beta para las tres estimaciones de tiempo de PERT.
Los clculos de la red para la fi gura 27 reali zados en las se cc iones pre cedentes
fueron tomados di rectamente pa ra cada d ij , reemplazndolos con la estim ac iones
Te de la siguie nte tab la:
ACTIVIDAD a b m Te 02
A Seleccionar el s Itl de las Oficinas 1.5- 4.5 3 3 0.250
B Crear el plan organlzaciona l y finanCiero 3 7 5 5 0.444
e Determinar nece sidades de personal 0.5 4.5 3.25 3 0.444
D Disear la Instal acin 2 7 3.75 4 0.694
E Construir el Inte nor de la Instalacin 6 12 9 9 1.000
F Seleccionar el p ersonal que ser transfendo 0.5 3.5 2 2 0.250
G Contratar nuevo s empleados 0 .75 5.25 4.5 4 0 .563
H Trasladarreglst ros, personal y otros 0.25 3.75 2 2 0.340
I Hace r los arregl os fin ancieros con otras sedes 2 12 4 5 2 .778
J Capaci tar el nue vo personal 1 4 3.25 3 0 .250
162
INVrSTI(i\(' ION DE OPER ,\C IONES PA RA I NGEN IER II\S y ADM IN I STR AC ION DE EMPRESAS
La tabla siguiente muestra que para la aplicacin de este enfoque en la ruta crtica
de la figura 27 (actividades 1 ~3~4~2~5~8~9) , el tiempo esperado del
proyecto es 23 semanas con una varianza de 2.832 .
B 1 ~3 5 0.444
e 3~4 3 0.444
F1 4~2 o
D 2~5 4 0.694
E 5~8 8 1.000
J 8~9 3 0.250
Tiempo del proyecto 23 2 .832
J63
LUIS ALBERTO RINCON A BRIL
164
INVESTI(i ,\CION I)E OPI-.I{ ,\C IONES 1',\1< ,\ I NGEN IERI ,\S y , \I)~ II N I STR I \C I ()N DE H IPRES\S
Construir el modelo de red del problema y realizar los clculos de Ruta Critica.
J65
8. MODELOS DE INVENTARIOS
166
INVEST IG,\C ION DE OPERAC ION I:S I',\R ,\ ING EN I FR I,\S y AD~ II N I S T R , \C I ON DE E~ I I' R ESAS
y : Costo de penalizacin por unidad de tiempo o dinero por cada unidad que se
retrasa.
r : Punto de reorden o Nivel del inventario para el que se debe ordenar un nuevo
pedido de tamao Q.
167
I l llS I\ Lll rln O RINCON 1\Il RIL
168
INV LST IC; .\ClON I)r Oi' 1 R,\C IONES PAR ;\ INGEN I ER l f\S y ,\D~ II N I STRAC I ON DE EMP RESAS
Con base en estos criterios , la Figura 30 describe la variacin del nivel del
inventario a lo largo del tiempo . En esta , T representa la longitud del periodo y 0 0
es el valor inicial del inventario. En general , O = AT. En particular, en la figura 30,
00 = AT. El problema ser encontrar el valor de O que produzca los costos
menores anuales para una funcin Ca(O). Esta funcin resulta ser la suma de los
siguientes costos parciales:
/ r AT "
C, = r de (t)dt = Jro IC( Q -At)dt = I C( Q - -
2
). C0 ll1 0 T = Q , ellfOll ces :
I JI) P
A
C = I CT Q
/' '")
Q = I QT Q
T :2 :2
J69
L U IS A LBERTO RINCON AB RIL
3. Costo anual de hacer los pedidos. Costo del pedido por el nmero de
pe d I'dos en el ano, I =AA.
- esto es: el = A -I = A ~
, T (J,!. Q
de le A :2AA :2AA
_ " =- -A - =o entonces Q" = -- = --
dQ :2 Q' ' le . /
Tr = T* - T d Y r =A T r
170
IN\' I ~ 11( ; \C!ON DE OPFR \C!ONES P\RA I NGEN I ERI AS y AD~ II N I S TR /\C I ON DE E~ I PRESAS
Q*
2AA ~40
Tamao econmico del lote: Q" = = 200 Ton
, / 0.02
. d optlma
Longltu d i do: 7" "=
e peno . Q '" = 200
- = S das .
A 40
Tiempo de reorden: Tr = T* - Td =5 - 2 = 3 das
Punto de reorden: r =A Tr = 40 x 3 = 120 Ton
17 1
L U I S ,\ L BE RTO RINCON A IlR II .
Se coloca un nuevo pedido a los tres das de inicia r cada periodo cuando el nivel
de inventarios llega a 120 unidades.
Este caso obedece a una de dos circunstancias. En un primer caso, las demandas
acumuladas insatisfechas pueden esperar hasta ser atendidas. En un segundo
caso, las demandas insatisfechas acumuladas se pierden. En cualquiera de estos
casos hay que considerar un costo de penalizacin adicional por no satisfacer a
tiempo la demanda. Este costo tendr dos componentes, C pen = n + <1>. El primer
elemento representa el costo fijo por las unidades retrasadas y el segundo un
costo proporcional al tiempo de retraso.
Cm= l e I (Q _ S) T = I cA (Q _ S) Q - s = l e (Q - S) 2
T '2 Q 2A 2Q en donde S es la
cantidad retrasada .
172
INV L STI(; ,\CION DE OPERAC IONES P/\RA INCEN ILR I /\S y I\D~ II N I STRAClON DE EM PRES ,\S
3. Costo anual de hacer los pedidos. Costo del pedido por el nmero de
d I -
Pe d I os en e ano , esto es : e, I
= A TI = A IJI = -QA A .
4. Costo de penalizacin. Se defini como Cpen = n + <1>. esto es , el costo fijo por
las unidades retrasadas ms un costo proporcional al tiempo de retraso. Si ..t
define el costo fijo por cada unidad retrasada y y el costo proporcional al tiempo
I T, S I A SS A I }S c
e = "IS + y - = uS - + y =- (ISA - -)
'"'' T :2 T 'Q 2A Q Q :2
173
LU IS A LBERTO RINCON ,\I3R IL
A (Q _ S) C l yS e
e" (Q , S) = Ae + A
Q
+ le
2Q
- + - (USA+ -
Q . 2
)
Aplicando los conceptos del clculo diferencial se pueden encontrar los valores
ptimos para Q y S.
'. le . pA . ! t e - .: p eAe ~I A
S,'= Q"- => S ,'= I _. 2AA- - - ~
le +y le + y ! le +y , le + y le + y
174
INV[ST IGi\ClON UE O I' ER,\ClONES P,\R\ I N(,EN I ER I,\S y i\D MI N IST RI\C ION D E E ~ 1P RES\S
2.2. Si se permiten retrasos en las entregas , con un costo fijo por cada unidad
retrasada de $US 2 y un costo de cada unidad proporcional al tiempo de
retraso de $US 1, determinar cada cunto debe hacerse una corrida y de
qu tamao debe ser.
3.2. Si se admiten retrasos en las entregas , con un costo fijo por cada galn
retrasado de $US 0.3 y un costo de cada galn proporcional al tiempo de
retraso de $US 0.2, determinar cada cunto debe comprar y de qu tamao
debe ser el pedido.
J7S
l. U IS 1\ LB r::RTO RINCO N A BRIL
unidad de tiempo hasta que alcanza el tamao del lote . Los artculos se retiran
a una tasa de A (A< <1 artculos por unidad de tiempo. En este modelo se
Nivel de
Inventario
Tiempo
T1
176
9. MODELOS DE ESPERA O TEORA DE COLAS.
177
L U I S A LB ERTO R INCON A BRIL
efectivamente para recibir atencin este cliente o tiempo que el individuo pasa en
el sistema. Se define una estacin de servicio como la porcin de una instalacin
o estacin que puede suministrar servicio a un cliente a la vez.
Clientes
Fuente de
Entrada !> CHe ntet>,-_C_O_I a_> Estacin de
servicio
servidos
En muchos casos se supone que las llegadas ocurren con una distribucin de
l
Poisson , es decir, P (x = j) = e )'?e . En este caso, el parmetro A., es la intensidad
. JI
o tasa promedio de llegadas al sistema o valor esperado del nmero de llegadas
por unidad de tiempo. Ocasionalmente , las llegadas pueden ser en lotes de
tamao fijo o variable . Un ejemplo lo constituyen las llegadas de aviones a
aeropuertos ; cada avin se considera una unidad que requiere servicio ; mientras
que los pasajeros que llegan dentro del avin componen un lote que requiere la
utilizacin de otros servicios.
178
INVEST IG ,\C10N DE OPER /\C IONES PARA INGEN IER I AS y i\D~ II N I STRAC I ON DE H IPRES AS
La duracin t del servicio, ocurre en muchos casos de acuerdo con una distribucin
exponencial f(t) = pe -pi. El parmetro p representa la tasa promedio de servicio o
valor esperado del nmero de clientes atendidas por unidad de tiempo.
.....................................................................
179
L U IS A L flERTO RINCO ABR IL
Si el sistema de cola se encuentre en el estado estable , esto es , una cola que lleva
operando mucho tiempo y por la cual han pasado o pasarn muchos clientes y se
supone que los lmites usados en las siguientes expresiones existen , entonces:
I
1 E(S, )
1 , EU )
- = LIII1 - - = Llll ~
A I-> ~ j , J.1 J~ OO .i
\V =
I
E(W: )
L ll1 -,-,
, ~,-,--
I _- L = LIl1 _ 0 _
r E (n(r ))dl
---
T-> ~ T
I
T
Sr P (n(l ) = 11 )dl
P(W, "5. / )
P = Llll =-:.(,-
1 ---- P(W ::; 1) = Llll ,~I
"T-> ~ T I ->~ j
180
INVEST ICi .\C ION IX O PER ,\C IONES 1',\1< ,\ INGEN II, RI\S y \I)~ II N I ST R \C I ()N DE E~ I P R ES /\S
e ., (Al )"
algn nmero real A. > O', XI tiene la distribucin P (1 ) = P(X 11 I
= /1 ) = -1 - . Esta
/l .
181
L UIS A Lll ERT O RI NCON ,\ B RIL
todo i, se puede demostrar que Cada r tiene una distribucin exponencial con
parmetro A .
11 1
Esto es, se trata de una distribucin binomial con parmetro uft independiente de
J82
INVFST IUAC ION DE O I'I. R,\C IONES PARA IN( ;EN I FR I!\S y \D~ II N I S T R'\( - I ()N DE F MPR FS\S
183
LUIS ,\ U 3ERTO RINCON ABRIL
P (I+/i )- P(I ) O( /i )
Entonces " /i " =A" J~, 1 (I )+ ,LJ ,,+I ~<+ I(i)-(A,, + ,U ,, ) ~, (i )+ h' tomando el
definen .Lo = O Y A-1 = O, entonces dP/) (t ) = f.1 1 /~( / ) - A,,1~) (I ) .Resolviendo el sistema
dI
dP() (t ) = -AP (1 )
() d~, (I ) = AP ( / )-AP ( / )
( II dI ,,- 1 "
184
IN\TST IGACION DE O PER ,\C IONES PARA I 'GF. I F.R I\S y , \D~ II N I STRAC I ON DE EMPRES\S
AII /~ ) = {I , P
(A, + {I l ) P = A(] I~ ) + .u 2 Pe
La figura 36 muestra los diversos estados a los cuales puede llegar el sistema. Si
se igualan las tasas hacia adentro y hacia afuera de cada estado , se obtienen las
ecuaciones de balance . A esto se le reconoce como el principio de tasa de entrada
igual a tasa de salida.
Estado An-2
I
\.--.J
J.ln J.ln+ 1
J.ln-I
185
LU I S ,\LBERTO RINCON ABR IL
De esta forma simplificada , se obtienen las ecuaciones que rigen el sistema. Este
procedimiento es muy utilizado para desarrollar las relaciones que rigen los
diversos tipos de colas. Este sistema se resuelve en funcin de Po de la siguiente
manera :
Estado
o:
1:
2:
11 - 1 : p1/
=~p 11 - 1
+ _1- ( P I! I P 1/ I
-A 11 - 2 P11 - 2 )
..t " P"
1/: p" = -A"- p" + -1 (..t " P" - A,, _JP',-J)
..t ,,+J ..t ,,+J
186
INvrSTIc;"CION D I: O l' !" R,\C!ONFS PA R" INGEN I ER Ir\S y ADM IN ISTRAC ION DE EMPRESAS
" A ~ ~
Definiendo h" = TI I l . S/' obl i /'II/' L~, = Lb,/~) = l . A partir de esta expresin
,- 1 ~I , 11 _ 0 1/ ..;:. 0
I b"
se pueden calcular Po = , \" P Estas expresiones plantean la
b "
L. "
condicin indispensable para la existencia de las probabilidades de estado estable .
Es necesario que la suma L b n converja.
Dado que se pueden asignar diferentes valores no negativos a las tasas 1.. 0 , Al, 1.. 2 ,
1.. 3, ....... An y Pl , P 2, P 3, pn del proceso de nacimiento y muerte , existe una gran
flexibilidad para modelar un sistema de colas. Los modelos ms usados en teora
de colas estn basados directamente en este proceso y entradas Poisson y
tiempos de servicio exponenciales.
h
"
= rr
" ;l
,_ 1 ,L/
= ( )"
;l
JI
~ C IICIlldo ~
;l
JI
<I
. b;l A A
Entonces se obtiene que ~ , = , -"- = ( 1- )( ~ ) " = ( 1- p)p " COII P =~ . Es decir,
L. b" JI JI JI
la condicin para que existan las probabilidades es que p < 1. La probabilidad de
187
L UIS ,\U3E RTO RI NCON AB RI L
188
IN\TST I(; ,\CION D I- OI'ER ,\ C IONES PARA I Nl;EN II: RI AS y I\D~ II N I S TR I\C I ON DE H I PRESAS
Estado
I\~
u 2u 3u (s-1 )u su su
189
LLlI S I\ L Br:RTO RI NCO ' A BR IL
j
l
sp ( A) , 1
dOllde P = ~ I (A) " + _p
1) L.,
,, _o ll. ,LI
., . 1
S.( .lp-/l)
1. Identifique los clientes y los servidores del sistema de colas en cada una de las
siguientes situaciones:
1.1. Las cajas registradoras de un supermercado.
1.2 . Una estacin de bomberos.
1.3. La caseta de peaje de una carretera.
1.4. Un taller de reparacin de carros.
1.5. Un muelle de carga y descarga.
1.6 . Un grupo de mquinas semiautomticas asignadas a un operador.
4. Considere un sistema M/M/ 1 con p = 1.0. Compare L para los casos en los cuales A es
0.6 , 0.9 Y 0.99, re spectiva mente . Igual para Q Y w. Cal cule la probabilidad de que el
tiempo de espera sea mayor que 4 unidades P [W > 4 l.
190
IN\' I.S1IG ,\C10N J)E 01'1 J{ .. \C ION I.S I',\R \ ING I: N II: RI,\S Y J\ D ~ II N I STJ{ , \C10N DE H IPR ESAS
5. Un flujo de votantes por dos candidatos cumple un proceso de Poisson con tasas de
llegada Al y A2 independientes. Mostrar que el flujo tot al es un proceso de Poisson con
tasa (Al + A2). Determine la probabilidad de que el primer cliente vote por el primer
candidato .
7. Una cabina telefnica recibe clientes Poisson que llegan a un promedio de 12 minutos
entre cada cliente , las llamadas tienen una duracin exponencial de un promedio de 4
minutos. La empresa de telfonos decide que colocara un segundo telfono si los
clientes tienen que esperar en promedio ms de cuatro minutos para que desocupen el
telfono .
7.1. Para que valor de A se sucede este cambio?
7.2. Cul debe ser A, s la compaa de telfonos coloca otro aparato slo si la
probabilidad de que un cliente tenga que esperar exceda de 0.6?
8. Una pequea estacin de gasolina tiene cupo para dos carros solamente. Los clientes
potenciales son Poisson a tasa desconocida , pero que no se detienen si el espacio
est lleno (es decir, se pierden) . Se sabe que el tiempo promedio entre los clientes
actuales (aquellos que se detienen y son servidos) es de 6 minutos. Hay un
despachador con servicio exponencial y con media de 5 minutos .
J9 \
L U I S ,\ U 3ERT O RI NCO ,\ B RIL
9. Un sistema de colas tiene dos servidores, una distribucin de tiempo entre llegadas
Poisson con media de 2 horas y una distribucin de tiempo de servicio Exponencial
con media de 2 horas por servidor. Si a las 12 del da llega el primer cliente.
9.1 . Cul es la probabilidad de que la siguiente llegada ocurra antes de la 1 P.M ., Entre
la 1 y las 2 P.M . Despus de las 2 PM .?
9.2. Cul es la probabilidad de que le nmero de llegadas entre la 1 y las 2 P.M. sea O,
2 ms clientes?
10. El gerente de un supermercado debe decidir a quin contratar de dos cajeras , Mara ,
que trabaja despacio y puede ser empleada por C 1 = 5 $US/hora; o Alicia , que trabaja
ms rpido y cuesta C2 $US/hora , donde C2 > C1. Ambas dan servicio exponencial a
tasas f.! , = 20 clientes/hora y ~l 2 = 30 clientes/ hora , respectivamente . La llegada a la
caja es Poisson con A = 10 clientes/hora. El gerente estima que en promedio, el tiempo
de cada cliente vale 0.02 $US/min y debe ser tomado en cuenta en el modelo.
10.1. Calcular el costo esperado por hora al contratar a Alicia o Mara.
10.2. Cunto estara usted dispuesto a pagarle a Alicia?
10.3. Si no se conoce la tasa de servicios de Alicia , encuentre una cota superior para
la cantidad que se le pagara.
192
10. MODELOS DE DECISiN MARKOVIANOS
193
L U IS 1\ 1J3E RTO RINCON ;\13 1<11 .
194
I N\ ' I. ~T I( ;'\ C I ON D I. O I'LI{ ,\CIONrS [>,\1< ,\ I NGEN I ER Ir\S y r\D~ II N I STR\C I ON DE EMPRESAS
A los resultados EJ , con J=1,2,3., .. , se les denomina estados del sistema . A las
probabilidades condiciona les P{X t + 1 =J I Xt-1 =i} se les llama probabil idades de
transicin . Cuando Xt -1 =i y Xt+ 1 =J , se dice que el sistema realiz una transicin
Ei4 EJ en el paso t. Las Cadenas de Markov homogneas conform an un grupo
especial de probabilidades de transicin que son independientes de t. Se
acostumbra la siguiente notacin PIJ = P{X I =J I XI-1 =i l-1} y nAt ) = P{ XI =J}. Por
,<
I~ 1 P , P , P ,
P" P" P" P"
P= P'I P" Pl1 P"
J95
LU IS A LBERTO RINCON ABR I L
Considerando el siguiente modelo para el cambio del valor de una accin. Al final
del da se registra el precio. Si subi , la probabilidad de que el prximo da suba es
0.66 . Si baj , la probabilidad de que el prximo da suba es slo 0.45 . En este caso
puede representar el estado O el precio de la accin sube y el estado 1 que baja .
La matriz de transicin est dada por
Los estados posibles del clima de una regin son : O da lluvioso, 1 da bueno , 2 da
con nieve. Nunca hay das buenos en secuencia . Despus de un da bueno existe
la misma posibilidad de que el siguiente sea lluvioso o con nieve . El 50% de los
das lluviosos y el 50% de los das con nieve se repiten. Cuando un da es lluvioso
existe la misma posibilidad de que el siguiente sea bueno o con nieve. Cuando un
da es con nieve existe la misma posibilidad de que el siguiente sea bueno o
lluvioso. La matriz es :
25
P,2 1 lo.5 0.25
P 2 = 0.5 0.0.5 1
Pe~ 0.5 0.25 0.25
196
10.3 ECUACIONES DE CHAPMAN KOLMOGOROV.
P,111I ) = 'P.~III)
L.... ,'
/:.> II/
U
111) t:j. I
1,. 11 \" O:-s: /1 1 :-s: 11
J.-O
paso en forma recursiva. Para n = 2, p' ~ :l =I I~, P" , . Estos elementos son las filas
197
l.U I S 1\ l. HERTO RINCON I\ ll l< ll .
P'" = P' =
0.63::>
0.26-1
0 ..\6X
0.36X
O
O.:l6X
O'' fl''O
O
O
0.632
026-1
O.36X
0.368
O
0.36X
()
O
0283 0. 252
(U5 1 0.3 19 0.23:1
0233 01"]
0233
0.097
0.080 01 8-1 0.368 0.368 0.080 0. 18-1 0.368 (U68 0.2-1 9 0.286 0.3 0. 165
Del estado Ek se puede llegar al estado EJ si existe un n>O tal que P';') > O. Una
retorno a J ocurra en el paso n se le llama / ;"), entonces Pi;') = " I ;I) P;;'-I) y la
1-1
198
IN\ 'ES11(; ,\C ION DE OPER I\C IONES PA R .. \ I NGEN I ER II\S y AD~ II N I S TR \C I ON DE H IPR ESt\S
O'
199
LUIS ,\LI3ERTO RI 'eo 'i\I3RIL
n(I) = (1 0{0.5 0.5 ) = (0.5 0.5)=> n('2 )=(0.5 0.5{0.45 0.55) = (0.45 0.55)=(Tr() Tri)
~ OA 0.6 ~ 0.44 0.56
El lector podr comprobar que para rc(O) = (1 O) , los valores sucesivos de rc(n) son :
N O I '2 3 4
7t1) I 0.5 0.45 0.445 0.445
N O I "2 3 4
7t1) I 0.4 0.44 0.445 0.445
En ambos casos se observa que 7t(n) = (0.445 0.555) cuando n crece . Se puede
demostrar que esta cadena es ergdica, solucionando el sistema de ecuaciones:
n = TrP
200
INVEST IGAC ION DE OPERAC IONES PARA INGEN I ERI AS y ADM IN IST RAC ION DE EMPRESAS
7[/0.5 0.5 1
~ 0.4 0.6)
El lector puede analizar una de estas ecuaciones resulta redundante, por lo tanto
se elimina una cualquiera de ella y se obtiene la solucin TCo = 0.445 Y TCl = 0.555 .
La seccin anterior estudi las cadenas de Markov cuyos estados son ergdicos
(recurrentes y no peridicas). Si no se tiene el requerimiento de que los estados
sean no peridicos , entonces el LI/1 p'~") puede no existir. Pero , el siguiente lmite
I I~OO
siempre existe para una cadena de Markov irreducible con estados recurrentes:
L/l/ ( ~
11_00 11
f.. p.~) = 7[, ' en donde las
~ :::I
TCJ satisfacen las ecuaciones de estado estable
201
L U IS I\L13ERTO RINCO A BR IL
perodos est dado por la expresin E( 1 f e,) y usando el resultado del lmite
1/ '~ I
1 " ] '"
~~:! E [ I/~ e, ) = ~Jr , e,
202
IN\ I. S1 1(; ,\c\ON DE O I' I.R AC IONES PARA INGEN IER I AS y AD~ II N I STR I\ C I ON DE H IPRESAS
Cul es la probabilidad de que un cliente llegue a tener una mala deuda dado que
la cuenta pertenece al estado 1 a 30 das de retraso. Igualmente , dado que la
cuenta est en 31 a 60 das de retraso .
f 13 = P 10 f 03 + P 11 f 13 + P 12 f 23 + P 13 f 33
f 23 = P20 f03 + P 21 f 13 + P 22 f 23 + P 23 f33
A partir de la matriz se sustituyen los valores para cada P,J y como f03 = O Y b = 1,
estas ecu aciones se convierten en:
203
LU IS ALBERTO RINCON ABR IL
f 13 = 0.2f 13 + 0.11 23
f 23 = 0.1f 13 + 0.2f 23 + 0.2
204
11"\'1 ST l l \(' ION Dr. OPFR \C!ONES P.\R .\ IN( l: N ILRI.\S y . \D~ II N I STR . \C10 DE H I PRES .. \S
El ltimo elemento de esta matriz de transicin indica que, una vez que la mquina
se vuelve inoperable (entra al estado 3) , permanece inoperable , esto es, el estado
3 es absorbente. Dejar la mquina en este estado seria intole rab le ya que esto
detendra el proceso de producc in, por lo que la mq uina debe reemplazarse. (La
reparacin no es factible en este estado). La nueva mquina comenzara entonces
en el estado O. El proceso de reemplazo toma 1 semana de manera que la
produccin se pierde durante este periodo. El costo de la produccin perdida
(ganancia perdida) es de $US 2000 y el costo de reemplazar la mquina es de
$US 4000 de manera que el costo total en el que se incurre siempre que la
mquina actual entra al estado 3 es de $US 6000. Antes de que la mquina llegue
al estado 3, puede incurrirse en costos por producir artculos defectuosos. Los
costos esperados por semana debido a artculos defectuosos $US O, 1000 Y 3000
respectivamente para los estados O, 1, 2. Estos costos relevantes estn asociados
con la poltica de mantenimiento , reemplazar la mquina cuando es inoperable,
pero no darle mantenimiento en otros casos . Bajo esta poltica , la evolucin del
estado del sistema o sucesin de mquinas , es una cadena de Markov con la
siguiente matriz de transicin:
Estado O 1 2 3
O O 7/8 1/ 16 1/ 16
1 O 34 1/8 1/8
2 O O Y2 Y2
3 1 O O O
205
L U I S ,\1J3I.RTO RI NCON A8 RII.
Para evaluar esta poltica de mantenimiento , deben considerarse tanto los costos
inmediatos en que se incurre en la siguiente semana, como los costos
subsecuentes que resultan cuando el sistema evoluciona de esta forma. Una
medida de desempeo usada para cadenas de Markov es el costo promedio
esperado por unidad de tiempo sobre un periodo largo. El calculo de esta medida ,
exige encontrar las probabilidades de estado estable con el siguiente sistema :
7[0 = 7[.1
7 :\
7[ ( = 7[0 + 7[ 1
8 4
1 l l
7[ , = 7[(, + 7[ 1 + - 7[ ,
- 16 8 2 -
1 1 1
7[ 1 = - 7[0 + - 7[1 + - 7[ ,
. 16 8 '2 -
1= 7[0 +7[ 1 +7[ ~ +7[1
2 7 '2 2
Solu cin: 7[ 0 =- , 7[ 1 = - , 7[ , = - . 7[= -
13 13 - 13 .1 13
As, a la larga , el costo promedio esperado por semana para esta poltica de
mantenimiento es . .,
e= 07[(J + 10007[ 1 + .,0007[ , +
-
6000n 1
.
25000
= --
13
206
INVEST l l;AC ION J)E OI'ER /\C IONES I',\ R /\ INGEN I ER I AS y I \ D ~ II N I ST R ;\C I ON DE EM PRESAS
$2000 por las ganancias perdidas al no producir. Las decisiones posibles despus
de cada inspeccin son las siguientes:
Uno de los modelos para los procesos markovianos de decisin se puede resumir:
207
I lllS .\I.I![R10 RI NCO N .\13RII.
Cada una de estas polticas tiene una matriz de transicin diferente , como se
muestra enseguida:
De los costos totales por semana de la seccin anterior, los valores de C'k son:
208
1;\\ 1 ~ II(; ,\CIO;\ D I. ()P I IUC! O N I.S I'/\ R/\ IN(; I.N II : RI ,\S Y J\1)~ II N 1 S TR '\(: 1 0N DE E~ 'I1'I{I -_ S ,\S
El costo promedio esperado a largo plazo por unidad de ti empo , se calcu la con la
1/
expresin E( e) =I C,lr" siendo k = d(R) para cada i y 1t representa la
1"
distribucin de estado estable para los estados del sistema segn la poltica R que
se est evaluando. Una vez obtenidos 1to, 1t" 1t2 Y 1t3 para cada una de las cuatro
polticas , el clculo de E(C) se presenta en la siguiente tabla:
209
L U IS A LBERTO RI en ,\BI< IL
11 1
1111 11/2 D,"1
~1
O
o
O o
2 10
IN\' I.S11(; ,\C ION D I- OpE I{ ,\C IONES p,\I{ ,\ IN(;r:N I ER I.\S y I\I)~ II N I STRAC I ON DE E~ I PRES-\~
~l
,
/ c O
/
1 '
J
1/
/ -1 X
O O 1
Variables de decisin , Para cada i = O, 1, .... ,m y k = 1, 2,.. " .. " 1, sea )(k la
probabilidad incondicional de estado estable de que el sistema se encuentre en el
estado i y se tome la decisin k,
211
L U I S ,\Lll ': IH O RINCON ,\RR I L
Cada X'k tiene una relacin con la D'k correspondiente , pues de las reglas de
probabilidad condicional , se tiene X ik = ni Diko Siendo ni la probabilidad de estado
estable de que la cadena de Markov se encuentre en el estado i. Se cumple
X x ,
= Ix ,
I
entonces Tr , de manera que D, = -"--
_I Tr ,
Restricciones.
m m I
I lIi I
decir, I
.1. _ 1
X I! = II x , p, (k)
I - (J 1. - 1
para J = 0,1 ,2, ...... ,m .
," I
Mil/(Z) = I I C, x ,
I-() .1. - 1
/11 I
Sujeto a las restricciones : IIx" = 1
1_ 0 /..:;:J
I 111 I
I
J. .;.:; )
X I! - I I X , p, (k) = O
I - () J. - I
212
INVEST IGAC ION DE O PER ,\C IONES PARA I NGEN IER I AS y AD~ " N I STRAC I ON DE E~ I PRESAS
X ,
Una resuelto el modelo, se encuentra a D,I = I
LX ,!
I ~I
Min(Z) = 1000 X11 + 6000 X13 + 3000 X21 + 4000 X22 + 6000 X23 + 6000 X33
21 3
L U IS ,\ I. 13ERTO RI NCO N ,\ 13 RIL
1. Dos mquinas dan premio , la primera con probabilidad a y la segunda con probabilidad
b. Una persona juega, si pierde juega de nuevo en la misma mquina, si gana cambia
de mquina. Encuentre la matriz de transicin y las probabilidades de estado.
3. Una mquina , cuando est operando al comenzar el da tiene una probabilidad de 0.1
de descomponerse en algn momento de ese da. Cuando esto ocurre , la reparacin
se hace al siguiente da y se termina al finalizar ese da .
3.1. Formule la evolucin del estado de la mquina como una cadena de Markov,
identificando los tres estados posibles al final del da y despus construyendo la
matriz de transicin (de un paso) .
3.2. Encontrar el tiempo esperado de primera pasada del estado i al estado j.
3.3. Si la mquina tiene 20 das sin descomponerse desde la ltima reparacin , cul es
el nmero esperado de das que la mquina permanecer en operacin antes de
la siguiente descompostura.
214
IN\ I.S11<i \UON DE 0 1'1 R,\C IONES P,\ R,\ ING I.N IERI ,\S y , \ J) ~ II N I STRAC I ON J) E E~ l r R ES , \ S
de marca como una cadena de Markov, incluyendo tres estados: los estados A y B
representan a los clientes que beben cerveza producida por las mencionadas
cerveceras y el estado C representa a todas las dems marcas. Los datos se toman
cada mes y el analista del CNDOR construye la siguiente matriz de transicin con
datos hi stricos.
A B e
A 0.7 0.2 0.1
B 0.2 0.7 0.1
e 0.2 0.2 0.6
4.1. Cules son los porcentajes de mercado en el estado estable para las dos
cerveceras grandes?
215
L U IS A LB ERT O RI NCON ABR IL
6.1. Cada ao en que el mercado sube (o baja) 100 puntos , el F1 tiene ganancias o
prdidas de $US 200, mientras que el F2 tiene ganancias o prdidas de $US 100.
Si el mercado sube o baja 200 puntos en un ao, las ganancias o prdidas del F1
sern de $US 500 mientras que las del F2 sern de $US 200. Si el mercado no
cambia , ninguno de los fondos tiene ganancias o prdidas. El inversionista quiere
determinar su poltica ptima de inversin con el fin de minimizar en el largo plazo
el costo (prdida menos ganancia) promedio esperado por ao.
6.2. Formule este problema como un problema de decisin de Markov identificando los
estados y las decisiones. Despus encuentre las Cik .
6.3. Identifique todas las polticas determinsticas. Para cada una, encuentre la matriz
de transicin y escriba una expresin para el costo promedio esperado (a la larga)
por periodo en trminos de las probabilidades de estado estable nO, n1, n2, .... "nm.
6.4. Encontrar la poltica ptima por enumeracin exhaustiva.
PO =
(0.9 0.1)
0.6 0.4
RO = (2
1 -3
-1) PI=(0.7 0.3)
0.2 0.8
RO=(4
2
1)
-1
216
APNDICE A.
A.1 MATRIZ.
Los aij de la Matriz A=(aij) son llamados elementos de la matriz y el doble subndice
define la posicin de fila y columna. En el caso anterior diremos que la matriz es de
orden mxn y lo podremos simbolizar como Amn.
A.2.1 Vector columna (Vector): Es una matriz con solamente una columna y cualquier
nmero de filas.
A.2.2 Vector fila (Fila): Es una matriz con solamente una fila y cualquier nmero de
columnas.
217
L U I S i\ U 3ERTO RI NCON j\Il RIL
A.2.4 Matriz cuadrada : Una matriz A se llama cuadrada si m=n , esto es, tiene igual
nmero de filas y columnas. Se dice que es de orden n y se simboliza An.
A.2.5 Matriz triangular: Es una matriz cuadrada que cumple una de las siguientes
condiciones:
- 2 3 1 - 1 O O O
O 1 2 - 1 f3 O O
A= B=
O O -V'2 3 4 2 l2 O
..,
O O O f3 ,) O -13
A.2.6 Matriz diagonal : Es una matriz cuadrada con a'j = O para todo i 7:- j. Equivale a decir
que cualquier elemento ocupando una posicin fuera de la diagonal de la matriz es nulo.
A.2.7 Matriz idntica: Es una matriz diagonal con a" =1 . Equivale a decir que cada
elemento de la diagonal es 1.
1 O O O
O 1 O Oo, O
1= O O O
O
O O O Oo, 1
A.2 .8 Transpuesta de una matriz. Dada. una matriz A de orden mxn , su transpuesta
AT, ser otra matriz de orden nxm , obtenida al intercambiar respectivamente filas por
columnas en la matriz A.
!! ,.
218
IN\TS11(; .\CION J)E ()I'I R,\C IONES I" \R\ ING I,N I ER II\S y I \J)~ II ISTR \C IO DE E~IPRESr\S
T
Una matri z A, se llama simtrica , si cumple A = A; Y se llama oblicuamente simtrica ,
T
cuando cumple A = -A.
A.3IGUALDAD DE MATRICES.
A.4.1 Suma de matrices : La suma de las matrices Amn Y Bmn es otra matriz Cmn , tal que
cada elemento en la posicin fila i-sima , columna j-sima de la matriz resultado , se
obtiene como:
A.4.2 Producto escalar: Operacin producto entre un nmero real a y una matriz A.
La expresin anterior indica que el escalar multiplicar a cada uno de los elementos de
la matriz.
A mp * B pn = C mn
2 19
LUI S ALBERTO RINCON ABR IL
C=AB=
-1
(2 O
1)(~1 - 1 1] (-LxI+bO+Orl - 1.\{- I)+ld+OIO - lxi + b:2+010) = (- 1 2 21)
~ ~ = 2r! +010+ bl 21{- I)+Oxl+bO 2rl+Ox2+bO 3 - 2
Asociativa: (A + B) + C = A + (B + C)
(A *B)*C = A*(B*C)
a(A*B) = (aA)*B = A*(aB)
Conmutativa: A + B = B + A
Distributiva: (a + B)A = aA + BA
a(A + B) = aA + aB
(A + B)*C = A*C + B*C
A*(B + C) = A*B + A*C
A.S VECTORES.
Entenderemos un vector como una matriz con una sola columna , por lo tanto sobre
los vectores aparecen definidas las mismas operaciones con las mismas propiedades
que para las matrices.
220
INVESTIG,\CION DE OI'ER /\CIONES PARA INGEN IER I /\S y AD~ lI N I STR\C I ON DE H IPR ES ,\S
A.5.1 Combinacin lineal: Dados los vectores V l , V2, V3,... .,Vn y los escalares al , a2,
a3, .. ... ,a n ; el vector V obtenido como: V = al V l + a2V2 + a3V3 + ..... + anVn , es una
combinacin lineal de los vectores dados.
22 1
L U I S 1\ I. BE RTO RINCON AB RIL
TEOREMA: Cualquier punto sobre un segmento de lnea puede ser expresado como
una combinacin convexa de los extremos del segmento.
222
INVEST IG ,\CION DC OPEI< \C IONES P/\R ,\ II'GEN I ER I AS y AD~ 1I NISTRAC I ON DE EMPRESAS
A.6 DETERMINANTES.
Asociado con cualquier matriz cuadrada A = (a,j), existe un nmero nico llamado el
determinante de A, que se simboliza de cualquiera de las siguientes formas det(A), I A 1,
I a l
'j
A.5.3 Menor de un elemento : Dada una matriz cuadrada A, para cada elemento a,j, se
define su menor d,j, como el determinante que se puede calcular cuando en la matriz A,
se suspende la fila i-sima y la columna j-sima. Para la siguiente matriz:
del =(-2)(-3)-2(- 1) =8
d" = 1(-3)-2.11=-5
d" = 1(- 1)-(-2) 1 = 1
A.5.5 Cofactor de un elemento : Dada una matriz cuadrada A, para cada elemento a,j,
se define su cofactor f,j , como el menor signado multiplicado por el mismo elemento
f'j = (-1 tja'j d'j
En el ejemplo de los puntos anteriores: f21 = -8*3 = -24, f22 = -5*0 = O Y f23 = -1*1 = -1. De
este ejercicio, el lector podr deducir que si a'j = O, entonces f'j =O.
22 3
LU I S I\ I. BE RTO RI NCON AI3 RIL
A.5.6 Determinante para la matriz de orden n ~ 2. Existe una propiedad para las
matrices cuadradas , la cual no se va a demostrar, la suma de los cofactores de
cualquier fila o columna es siempre el mismo valor. Este aspecto "especfico " fue
definido como el determinante de la matriz. Asi pues, dada una matriz cuadrada A, se
tiene que det(A) = D ,J , para una sola fila i-sima o una sola columna j-sima . En el
ejemplo que se viene presentando se puede calcular det(A) = -24 + O -1 =-25.
A.5.? Propiedades de los determinantes. La demostracin de las siguientes
propiedades se dejan al lector y en ellas se supone que cuando se habla del
determinante de una matriz A, se entiende la estructura IAI .
3. Si 181 es el determinante obtenido al multiplicar por a un solo vector fila o columna del
determinante lA\, entonces: 181 = alAI
224
IN \ I S rJ G ,\ C IO N D E OPER ,\C10 N ES P,\l~" ING EN IER I AS y ,\DM IN I STR AC ION DE E ~ IPRE SAS
A.6.2 Matriz Adjunta . La adjunta de una matriz cuadrada A es otra matriz cuadrada J
del mism o orden , estructurada como la transpuesta de los menores signados de A, esto
es , Si A =(ajj), entonces J =(m jj)T
A.6.3 Matriz Inversa. Una matriz B recibe el nombre de inversa de la matriz cuadrada
A, si A*B = 1. La inversa de A se designa como A '. Puede demostrarse que si A es no
I
singular, esto es IAI 1:- O, entonces A- = I .J .
A
Para cu alquier matriz cuadrada no singular A, A-' es nica y cumple A* A-' =A-'* A =I
A=
{{ el (1 l' (/ 211
X= X'j
X,
b=
b,
(f
",1 (/ 11/2 { I "/II X" b,
225
LU IS ALBERT O R INCN ABR IL
Si A es cuadrada , esto es , m = n y no singular, el vector solucin est dado por X =A- 1b.
Aplicar esta expresin para encontrar X, exige un procedimiento demasiado
congestionado de operaciones, el cual fue totalmente mejorado mediante el mtodo de
eliminacin de Gauss.
1. Construir la estructura ( A 11 1 b ).
2. Realizar las combinaciones lineales adecuadas entre las filas de esta matriz para que
en la posicin donde est A, aparezca la matriz idntica 1.
1
3. Cuando esto se logra la anterior estructura se convierte a ( 1 1 A- 1X ).
Para encontrar la inversa de una matriz A, el proceso ser iniciar con (A 11), realizar las
combinaciones lineales para terminar con (1 1 A-\
2X , +3X , + X ; =2
X1+X , +X ; = O
- X, +X , +2 X ;= 4
226
INVESTIG /\C ION DE OPERAC IONES PARA INGEN IER I AS y ADM IN ISTRAC ION DE EMPRESAS
Con esta informacin se puede construir el tablero inicial ( A 1I 1 b ), el cual queda como:
2 I 3 1 1 O O 2 F1
1 1 1 O 1 O O F2
-1 1 2 O O 1 4 F3
1 3/2 Y2 Y2 O O 1 F1 1=Y2 F1
O [3J Y2 -Y2 1 O -1 F2 1=F2- F1 1
O 5/2 5/2 Y2 O 1 5 F3 1=F3+ F1 1
1 O 2 -1 3 O -2 F1 2=F1 1 -3/2F2 2
O 1 -1 1 -2 O 2 F2 2= -2F2 1
O O I 5 -2 5 1 O F3 2=F3 1 -5/2F2 2
1 O O -1 /5 1 -2/5 -2 F1 3=F1 2-1 /5F33
O 1 O 3/5 -1 1/5 2 F23=F22+F3 3
O O 1 -2/5 1 1/5 O F3 3 =1/5F3 2
b) El "vector unitario" debe generarse con 1 en la posicin del marco (elemento pivote) y
ceros en el resto de la columna.
c) La fila que contiene el elemento pivote ( fila pivote) debe multiplicarse por el inverso
del pivote, para pasar al nuevo tablero.
d) Las dems filas se obtienen realizando entre ella y la fila pivote la correspondiente
combinacin lineal que genere el cero del "vector unitario".
227
I_U I S A L BERTO RINCON A BR IL
T
determinar: a) A + B b) CD e) DC d) BC - 2AD e) C + D
a) b)
5. Dada A= (= S)enCOl1lrOr
J I
B= (x -" ) , para que:
:: l'
T
(a) AB = BA (b) AB = I (e) AB = A (d) AB = A2
22 8
INVEST IG\C ION DE OPERACIONES PARA INGEN IER I\S y \I)~ I I N I S TR AC I ()N DE H 1PRESAS
18 18
15 18
VI = 9 V2 = O
O 8
O O
Expresar mediante una combinacin lineal convexa todas las posibles soluciones
ptimas al programa lineal.
a) 2X 1 + 3X 2 - 5X 3 =-3 b) 3X 1 + 2X 2 - X3 = 4
3X 1 - 2X 2 + 4X 3 = 15 2X 2 + 3X 3 = 8
5X 1 + 3X 2 - 2X 3 = 6 X1 + X2 + X3 = 4
c) 2X 1 + X2 + X3 = 10 d) X1 + X2 + X3 + X4 = 3
X1 + 2X 2 + X3 = 8 2X 1 - X2 - X3 = O
X1 - X2 + 2X 3 = 2 X1 + 2X 2 - X3 + 2X 4 = 2
X3 + X4 = 1
229
BIBLIOGRAFA
AHUJA, R., MAGNANTI T, Y ORLlN, J,. Netwoork flows : Theory, Algorithms and
applications. Ed. Prentice Hall. New Jersey. 1993.
BAZARAA, M., JARVIS J,. Linear programming and Netwoork flows. 3a . Edicin .
Ed , Willey. New York. 1995.
BINGHAM, R. Programas de computacin para formular alimentos. Avicultura
profesional. pp 134-136. 1983.
BRONSON, R. Teora y problemas de investigacin de operaciones. Ed. McGraw
Hill. Mxico 1983. 324 p.
COOPER, Robert B., Introduction to Oueueing Theory. 3 a . Edicin . Elsevier
North Holland. Nueva York. 1988.
COWLES, K y CARLlNG B. , Markov chain Monte Cario convergen ce
diagnostics. Journal Am . Stat. Assoc., 1996. p 91 , 883-904.
DANTZIG, G. B. Linear Programming and Extensions. Princeton University Press.
Princeton. 1963.
EPPEN G. D., GOULD F. G., SCHMIDT C.P. MOORE J. H. Y WEATHERFORD
1. R., Investigacin de Operaciones en la ciencia administrativa. Editorial Prentice
Hall. Ouinta Edicin . 1998. Mxico.
FU, M. C. ,Optimization via Simulation , Annals of Operations Research . 1994. P
199-248.
GASS, S. 1. An IlIustrated guide to Linear programming. Ed . Dover Publications.
1990.
GILKS, W., RICHARDSON S., Markov chain Monte in practice. Chapman Hall.
1996.
HILLlER, Frederick S. y LlEBERMAN, Gerald J., Introduccin a la
Investigacin de Operaciones. Editorial Mc Graw Hill. Cuarta Edicin. 1997.
Mxico.
INFANTE, A. Programacin Lineal. Bogot . Universidad de Amrica, 1979. 352
p.
230
I VESTIGAC ION DE OPERAC IO ES PARA I NGEN I ER I AS y AD~ II N I STRAC I ON DE E~ I PRESAS
231
LUIS ALBERTO RINCN ABRIL
ISBN 958809509 - 3