Vista previa del material en texto
Breve descripción del MRP II: Flujograma 7
/ NARASIMHAN, Simm y otros. Planeaclón de la producción y control de inventarios. Póg. 352
122
Características del MRP II
• Realiza la planeaeión con base en el plan agregado.
• Incluye la programación de toda la empresa, para varios períodos de tiempo.
• Toma en forma integrada toda la información.
• Lo que efectúa lo hace en tiempo real.
• Puede predecir lo que sucederá si se hicieran cambios.
• Va de arriba hacia abajo.
• Participa en la planeaeión estratégica.
• Convierte unidades físicas en unidades monetarias.
• Proporciona la opción de planificar, programar, gestionar y controlar los recursos.
Un vez definidos cada uno de los sistemas MRP estamos en condiciones de acometer el problema
de la confusión terminológica existente, básicamente entre MRP de Bucle Cerrado y MRP II. El MRP
II incluye al MRP de Bucle Cerrado, pero no son lo mismo. Sin embrago, son numerosos los autores
que utilizan la denominación MRP II para referirse a lo que en realidad es el MRP de Bucle Cerrado o
viceversa, con lo que se da un alto grado de confusión entre los dos términos. En otros casos se
emplean incluso nombres como MRP I, MRP II y MRP III (Schroeder, 1992, página 497).
Las curvas de intercambio pueden utilizarse para determinar acciones concretas del manejo de
inventario que permitan identificar claramente los costos que implica el tener mercancía almacenada
o la escasez de ella.
A su vez muestra de manera gráfica el comportamiento de los costos anuales y la inversión
promedio del inventario.
Para la construcción de la curva se requiere establecer la cantidad de orden económico (COE).
CURVAS DE INTERCAMBIO
A : Consumo anual
S : Costo de pedido
/ : Costo de tendencia del inventario
123
La cantidad económica de pedido se determina para cada artículo, con un rango de valores de
tendencia de inventario, para cada uno de ellos se determina la inversión promedio para todos los
artículos acompañado del costo total de ordenamiento en un período general de un año.
Hay medidas para que la empresa disminuya los costos anuales de almacenamiento; el valor
promedio del inventario en unidades monetarias (UM) y el costo anual de orden (CO).
Esta fórmula se deduce observando que el nivel promedio de inventario de un artículo es la mitad
de la cantidad de pedido.
La ecuación CO se deriva del hecho de que se hacen X cantidad de pedidos para un año, de
determinado artículo.
En muchas ocasiones es común no conocer el valor de almacenamiento de cada producto durante
un año, situación que afectaría el valor promedio de inventario y costo anual.
La curva de estos dos puntos asociada al valor de almacenamiento de cada artículo por año es
que la que se identifica como curva de intercambio para cualquier punto que observamos:
UM(CO)
De igual manera todo punto en la curva de intercambio cumple con:
UM 1 ——— = h
UM CO h
O sea.
124
PRODUCTO COSTO DE ORDEN PRODUCTO DEMANDA
COSTO DE
COMPRA
Drive 3.5 150= 500 30.000=
Teclado 110= 550 20.000=
Ejemplo:
UM(CO) =-* (y/K * D * c + *D,*c
UM(CO) =—(¿150 * 500 * 30.000 + yflTo * 550 * 20.000 J
UM(CO) = -(47.434 + 34785 )2
UM(CO) = 3.379.982. 000
125
EL PROBLEMA DE LOS PUENTES DE KÖNIGSBERG
Königsberg, la segunda capital de Prusia, está dividida por el río Pregel en cuatro
zonas, incluyendo la isla de Kneiphof, tal como lo muestra la gráfica. Hay ocho puentes
que conectan las diferentes partes de la ciudad y hay un acertijo acerca de ellos que
intrigó grandemente a los ciudadanos de Königsberg hace unos doscientos años.
Dar un paseo por los puentes ha sido siempre un entretenimiento para recreación
de los jóvenes. Según los viejos relatos, de una manera o de otra se presentó la
pregunta de cuánto llevaría recorrer los puentes. Esto condujo a la sorprendente
afirmación de que un recorrido completo de todos los puentes sin pasar más de una
vez por ninguno de los puentes era imposible.
Es un hecho histórico que un comité de jóvenes visitó a Leonard Euler, el
matemático, en 1735, para pedirle que resolviera el conflictivo tema. Un año más
tarde, Euler presentó un voluminoso informe a la Academia de Ciencias de San
Petersburgo. Allí afirmaba haber demostrado la imposibilidad de resolver el
problema. Esta conclusión aparece en el informe de la Academia, 1741, vol. 8, y
ha sido publicada en Inglés y Francés por renombrados matemáticos, ya que se
ocupa del principio aplicándolo a cualquier número de puentes.
El profesor W. Rouse Ball, de Trinity College, discute la antigüedad y
los méritos del problema en su gran obra Mathematical Recreations,
pero se equivoca al adjudicar su origen a Euler en 1736 y hace la
notable afirmación de que había y aún hay, según Baedecker,
solamente siete puentes. Los registros más antiguos se
refieren a ocho y el mapa presenta un acertado esquema
de Baedecker, quien se refiere especialmente a los
F ocho puentes.
La cuestión de regresar al punto de partida no
forma parte en absoluto del problema. Sólo se
trata de demostrar si es posible partir de
cierto sitio de la ciudad y llegar a otro sitio
pasando una sola vez por todos los
puentes. Se le pide al lector que diga
de cuántas maneras es posible hacerlo
y cuál es la ruta más corta.
CAPÍTULO IV
M O D E L O S (TEORÍA) DE REDES
Quizás el resultado más valioso de toda educación es la capacidad para obligarse uno
mismo a hacer lo que tiene que hacer y cuando debe hacerse, le guste o no.
Esta es la primera lección a aprender.
T. Huxley
• Gráfica: Serie de puntos llamados nodos (nudos) unidos por ramales.
• Red: Es una gráfica con algún tipo de flujo en sus ramales. Ejemplo: Eléctrica, transporte.
• Cadena: Serie de elementos que van de un nodo a otro. Ejemplo: 1 - 2, 2 - 5, 5 - 7.
• Ruta: Serie de elementos que conforman una cadena. Ejemplo: Para el anterior 1 - 2 - 5 - 7 .
• Ciclo: Es la cadena que une un nodo consigo mismo. Ejemplo: 3 - 5, 5 - 2 ,2 - 4 ,4 - 7, 7 - 6, 6 - 3.
• Gráfica conectada: Aquella en la cual al menos todos los nodos están conectados. Ejemplo:
El de la gráfica.
• Ramal orientado: Es aquel que tiene un sentido determinado, o sea, que tiene un nodo origen
y un nodo destino. Ejemplo:
127
Gráfica orientada: Aquella en la cual todos sus ramales están orientados. Ejemplo:
Arbol: Gráfica sin ciclos. Ejemplo:
«ÍÍ.» ¡s % fe i
La capacidad de flujo de un ramal es el límite superior de la rata de flujo en dicho ramal en un
sentido determinado.
• Nodo fuente: Aquel en el cual todos sus ramales están orientados hacia afuera. Ejemplo: O
• Nodo receptor: Aquel en el cual todos sus ramales están orientados hacia él. Ejemplo: ©
128
ALGUNOS PROBLEMAS A RESOLVER
1. Problema del flujo máximo.
2. Problema de la ruta más corta.
3. Problema del árbol de mínimo recorrido.
4. Problema del PERT / CPM / LPU / ROY / RAMPS.
Problema del flujo máximo
Nos permite conocer (calcular) la máxima cantidad de cualquier artículo o información que
podemos transportar desde un origen hasta un destino.
Pasos a seguir:
Primer paso: Elegir una ruta arbitraria.
Segundo paso: En dicha ruta escoger aquel ramal de menor flujo en ese sentido y transportar por
esa ruta la cantidad escogida.
Hacer esto repetitivamente hasta que no sea posible encontrar una ruta con capacidad de flujo.
Ejemplo:
129
El origen puede despachar 28 unidades y el destino puede recibir 22 unidades, pero por las
restricciones, el destino solo puede recibir 19 unidades en la ruta AB - BC - CD - DF - FG.
Problema de la ruta más corta
Por medio de la aplicación del algoritmo de este problema podemos conocer la menor distancia
entre un nodo origen y un nodo destino.
Pasos a seguir:
• Primer paso: Elaborar un cuadro con todos los nodos y los ramales que salen de él.
• Segundo paso: Partiendo del origen, debemos encontrar el nodo más cercano a él.
• Tercer paso: Anular todos los ramales que entren al nodomás cercano elegido.
• Cuarto paso: Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio
del (los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino. Ejemplo:
131
A B<13) C(16) D<»> E(19)
A D = 11 BF = 5 CE = 3 DC = 5 EC = 3
A B = 13 BC = 7 CF = 4 DF = 10 EH = 6
AC = 17 BE = 9 CD = 5 D G = 11 EF = 6
CB = 7 DE = 14 EB = 9
ED = 14
yi
F (A G<22> H <24) I (27) J(30)
FC = 4 GF = 7 HE = 6 IJ = 7
FB = 5 G D = 11 HF = 6 IF = 9
FE = 6 G I = 13 HJ = 7 I G = 13
FH = 6
FG = 7
FI = 9
FD = 10
F J = 12
13
0 ' 0 J ? 0
Es decir, la ruta más corta corresponde a la ruta ABFJ, la cual suma 30 unidades.
Problema del árbol de mínimo recorrido
En este problema se trata de encontrar un árbol, cuya suma total de distancias sea mínima.
Pasos a seguir:
• Primer paso: Escoger un nodo arbitrariamente y elegir el ramal que esté más cercano a él.
132
• Segundo paso: Elegir el nodo más cercano a cualquiera de los nodos ya existentes en el árbol.
• Tercer paso: Anular todos los ramales que me puedan crear ciclos al entrar dicho nodo y volver
al segundo paso hasta encontrar el árbol.
A B C D E
AD = 1 1 BF = 5 CE = 3 DC = 5 EC = 3
AB = 13 BC = 7 CF = 4 DF = 10 EH = 6
AC = 1 7 BE = 9 CD = 5 D G = 1 1 EF = 6
BA = 13 CB = 7 DA = 1 1 EB = 9
CA = 1 7 DE = 1 4 ED = 14
H
FC = 4 GF = 7 HE = 6 IJ = 7 JH = 7
FB = 5 G D = 11 HF = 6 IF = 9 JI = 7
FE = 6 G I = 13 HJ = 7 I G = 13 JF = 12
FH = 6
FG = 7
FI = 9
FD = 10
F J = 12
1
H
6 - ' \ 7
© • • • • • • • © • • • • • • Ó © " ' . 0
. ' 7
133
De acuerdo a la anterior gráfica el árbol de mínimo recorrido se encuentra constituido por AD -
DC - CE - EH - HJ - JI - CF - FG - BF, lo cual nos da un total de 55 unidades.
Problema del PERT / CPM / LPU / ROY / RAMPS
Para solucionar los problemas planteados en el Gráfico de Gantt se presentan los sistemas de
trayectoria crítica, es decir, PERT, CPM, LPU, ROY y RAMPS.
A mediados de 1957, la E.l. Du Pont de Nemours de los Estados Unidos estaba interesada en
ampliar cerca de 300 fábricas, lo cual implicaba un gran número de actividades; pensemos que cada
ampliación tuviera 100 actividades, esto implicaba 30000 actividades, las cuales no podían ser planeadas
en Gráfica de Gantt. Morgan Walker de Du Pont y James E. Kelley de la Remington Rand pensaron
que la única posibilidad era utilizar la computadora e idearon un sistema que denominaron CPM
Critical Path Method (Método del Camino Crítico).
A fines de 1957 la Oficina de Proyectos Especiales de la Armada de los Estados Unidos, fue
encargada de administrar el gran proyecto Polaris. Se trataba de fabricar, probar y dejar en posición de
combate un cohete balístico llamado Polaris. Dicha Oficina contrató la asesoría de las firmas Lockheed
Aircraft y Booz, Alien y Hamilton para que propusiera métodos apropiados al control del proyecto
con tan especiales características de incertidumbre. Este grupo desarrolló los procedimientos que dieron
origen al PERT Program Evaluation and Review Technique (Técnicas de Evaluación y Revisión de
Programas).
Existe un sistema llamado LPU Lines Points Union (Líneas y Puntos de Unión) desarrollado en
1961 por John W. Fondahl profesor de la Universidad de Stanford. Este trabajo inicialmente se denominó
Sistema de Actividades en los Nodos; luego la IBM desarrolló en base a él un programa llamado
Diagrama de Precedencias. La diferencia fundamental con el CPM / PERT es que este modelo (LPU)
está orientado hacia el proceso manual y no hacia el computador.
En Europa un grupo constituido por ingenieros de los Chantiers de lAtlantique, la SEMA, la
Compagnie des Machines BULL y el Matemático Francés B.Roy estudió el problema del equilibrado
de las curvas de carga de las diferentes especialidades que intervienen en las operaciones de armamentos
de buques; estos trabajos dieron origen al ROY o Método de los Potenciales. La principal ventaja del
ROY sobre el PERT es que no exige tareas ficticias.
En un afán por sincronizar el mecanismo de la acción empresarial, respondiendo a ese deseo
de mayor orden, mayor productividad y mayor gestión que imponen las nuevas formas de la
economía actual y que viene sintetizado en la llamada gestión integrada, ha surgido el método
RAMPS que se preocupa en coordinar los medios disponibles y las tareas de varios proyectos que
se llevan a cabo a la vez.
Los modelos más extendidos en cuanto a su aplicación en nuestro medio y sus principales
diferencias son:
134
PERT CPM
1. Probabilístico.
2. Se basa en eventos.
3. Orientado a quien controla.
4. Se puede utilizar en proyectos
1. Determinístico.
2. Se basa en actividades.
3. Orientado a quien ejecuta.
4. Se puede utilizar para todo tipo
de investigación. de proyecto.
En este momento es importante advertir las ventajas de los sistemas de trayectoria crítica (PERT /
CPM / LPU / ROY / RAMPS) sobre el sistema tradicional de barras (Gráfica de Gantt):
1. Se puede conocer exactamente la secuencia de las actividades.
2. Podemos analizar el efecto de cualquier atraso o adelanto de una actividad en relación al
proyecto.
3. Se pueden estudiar rápidamente diferentes alternativas.
4. Podemos analizar todas las variables (tiempo, costos, recursos).
5. Se pueden conocer cuáles son las actividades que sufriendo retrasos no modifican el proyecto.
6. La efectividad del sistema es directamente proporcional al número de actividades; cuantas
más actividades existan más detalles y más conocimientos del proyecto tenemos.
7. Podemos visualizar todos los problemas y situaciones en el papel, antes que ellos ocurran en la
realidad.
Este problema resuelve situaciones atinentes a proyectos. Un proyecto está constituido por las
tareas o actividades (hechos que consumen tiempo) y / o recursos ( hechos que consumen dinero).
Los recursos son los elementos necesarios de un proyecto para ejecutar una actividad; estos recursos
pueden ser:
• Mano de Obra.
• Materiales:
- Permanentes; no fungibles ( quedan físicamente en lo que hemos hecho).
- Fungibles; dinero, energía utilizada, etc.
• Espacio.
• Maquinaria.
Problema PERT - CPM
135
En todo proyecto el recurso más importante es el dinero.
Entre las actividades existen unas relaciones que nos permiten ordenarlas y representarlas mediante
un grafo valuado G = (X , Y ) de dos formas:
1. X : Conjunto de actividades.
Y: Relaciones entre las actividades.
2. X : Conjunto de actividades.
X : Conjunto de elementos X tales que X es el final de una actividad y el comienzo de toda
actividad inmediatamente posterior.
La diferencia entre dos métodos es que para PERT la duración de las actividades es aleatoria, de
la que conocemos su ley de distribución (Distribución ¡5 ); se consideran tres clases de tiempos:
T0= Tiempo optimista ( duración prevista sin ningún tipo de retraso).
Tn— Tiempo normal ( duración prevista desde un punto de vista real ).
Tp= Tiempo pesimista (duración prevista si va mal la actividad la actividad en su desarrollo).
De acuerdo a la distribución (3 calculamos el tiempo medio de duración , que estará en el
intervalo \Tq , Tp J como:
= r p + 4 * r „ + r 0
6
Luego la varianza y la desviación estándar corresponden a:
La desviación estándar nos dice el grado de confiabilidad de la estimación hecha con T^ . Luego
calculamos la ruta crítica.
T p ~
6
136
El método CPM considera que conoce exactamente lo que dura cada actividad.
Las convenciones por medio de grafos corresponden a:
ÍT P TL\ K
\ /
U •
TPi : : Es el
TL- Es el
U: Es el
K- Es la
i- Es la
Calculárnoslos T P¡ de la siguiente manera: T P}. = [r P (i-1)+ K] inicializando T Pj
del nodo inicial en cero; si un nodo tiene varios predecesores se escoge el valor mayor entre los T P¡
calculados. Cuando se llega al nodo final se habrá obtenido el tiempo más próximo de la finalización
del proyecto.
El cálculo de T P¡ es así : T L¡ = [ r z ( /+ l ) - K] igualando T L¡ = T P¡ para inicializar
T L¡ en el último grado de grafo. Si un nodo tiene varios sucesores, se escoge el valor de T L [i + 1)
más pequeño; cuando se llegue al nodo inicial se obtendrá el tiempo más tarde de comenzar el proyecto.
Un suceso se dice que es crítico cuando T L¡ — T Pi = 0 ; la ruta o camino crítico está
constituida por el conjunto de actividades críticas. Holgura total de una actividad es el tiempo que se
puede prolongar dicha actividad sin afectar el tiempo final del proyecto. Holgura libre es el tiempo
que se puede prolongar la actividad sin afectar el suceso. Cuando una actividad tiene una duración
nula se llama hito.
Ejemplo: Se tiene un proyecto de sistematización de un Departamento de Programación:
137
ACTIVIDAD DURACION
( Semanas)
SUCESOR
INMEDIATO
1. Definir el trabajo a realizar 3 2
2. Aprobar el proyecto 2 3,4
3. Estudio de Hardware 3 5
4. Análisis general 5 10,11
5. Decisión compra de Hardware 0 8
6. Entrega Hardware 1. 7 9
7. Entrega Hardware 2. 10 15
8. Preparar sala de computo. 17 6,7
9. Pruebas instalación Hardware 1 14
10. Análisis de detalle 1. 4 12,16
11. Análisis de detalle 2. 6 13,17
12. Programar 1. 8 14
13. Programar 2. 10 15
14. Probar 1. 2 15
15. Probar 2. 2 18
16. Documentar 1. 4 18
17. Documentar 2. 4 18
18 Prueba de recepción. 2 19
19. Cobrar. 0
La representación del proyecto anterior por medio de un grafo es:
138
139
En cualquiera de los dos grafos podemos observar que la duración del proyecto es de 39 semanas
determinadas a partir de las dos (2) rutas críticas siguientes:
/ = 1 , 2 , 3 , 5 , 8 , 7 , 15, 18, 19.
ii= 1 , 2 , 3 , 5 , 8 , 6 , 9 , 1 4 , 1 5 , 1 8 , 1 9 .
TIEMPO (SEMANAS)
ACTIVIDAD OPTIMISTA MAS PROBABLE PRESIMISTA
1,2 2 3 8
2,3 1 2 4
3,4 2 3 5
3,5 3 5 7
5,10 2 4 5
5,11 4 6 9
10,9 5 8 10
10,13 3 4 6
11,12 8 10 13
11,13 2 4 6
4,6 0 0 0
6,7 12 17 19
7,8 4 7 10
7,12 7 10 12
8,9 0 1 3
9,12 1 2 4
12,13 1 2 5
13,14 1 2 3
14,15 1 2 4
141
Las varianzas y la desviación estándar total de la ruta crítica corresponden a :
5 - 2
<y12 = — — ; cr12 = 1
4-1
°~2J = ~ ~ > &2J = 0,5
o
5-2
°~34 = cr34 = 0,5
o
19-12
(T67 = 7 ' °"67 = ¡'16
10-4
a78 = 7 / °~78 = 1
O
3-0
& 89 = T ! CF89 = 0 ' 5
4 - 1
cr 9,2 = — - — / a 9 I 2 = 0,5
5 - 1
1213 = 7 <7,213 = 0'6
3 - 1
13,4 = 7 ' G 13,4 = 0,3
4 - 1
<* 14,5 = —— >' 1415 = 0'5
crT = ^ c r ¡ 2 + c r ¿ + a ¿ + a ¿ + o¿ 8 + + a ¡ ¡ 2 + (f¡213 + o j 3 1 4 + 1415
142
crT = j5,0456 SEMANAS 2
(7 T = ± 2,24 SEMANAS
<j T ~ ± 2 S E M A N A S
Es decir, el proyecto lo podemos realizar en un intervalo cerrado: [37 , 41] con una holgura
aproximada de 2 semanas por defecto y por exceso.
El proyecto se puede hacer en 39 semanas con una desviación a izquierda y derecha de 2 semanas,
o sea, el trabajo deberá ser realizado entre 37 y 41 semanas respectivamente.
143
EL ACARREADOR DE LADRILLOS
Un acarreador está organizando ladrillos en un segundo piso, al cual accede a través
de una escalera de nueve peldaños; un joven que pasa acaba de proponerle el
siguiente problema, poco usual al acarreador de ladrillos: empiece desde el suelo,
después suba y baje alternativamente la escalera, un peldaño por vez, hasta llegar
al último. Debe usted subir y bajar de tal modo de llegar otra vez al suelo solo un
vez, pisar solo dos veces el último peldaño de arriba y pisar todos los otros igual
número de veces.
El problema es cumplir con todas las condiciones en el menor número posible de
pasos.
CAPÍTULO V
PROGRAMAC IÓN N O LINEAL
El conocimiento es poder.
• , r: '
F. Bacon
Existen muchos problemas que no pueden ser expresados en términos de funciones lineales, sino
por medio de funciones no lineales.
Las soluciones a estos problemas son más dispersas que las de programación lineal, ya que no
existe un método de solución general como por ejemplo el algoritmo Simplex; por lo tanto existen
soluciones para algunos tipos muy especiales de problemas de programación no lineal.
El problema general de programación no lineal es:
optz=f{x„x ,x3 ,xn)
Con las siguientes restricciones:
g\Xx,X ,x„ ,xj<z>,.
g (xltx ,x3, ,xn)<b2
g3(xx,x ,x3, ,xn)<b}
gH(XítX,X3, ,Xn) <bm
X j > 0 J = 1,2,3, ,n
La OPT puede corresponder a un problema de maximización o de minimización.
Algunos de los principales métodos de solución son los siguientes:
• La solución gráfica, cuando son máximo tres (3) variables.
• Las restricciones son ecuaciones en lugar de desigualdades" m < n "; lo anterior constituye un
caso de optimización clásica y se puede aplicar para su solución ios multiplicadores de
Lagrange.
145
• "f[XvX2,X3, es no lineal, pero las " g ( X l , X 2 , X 3 , >Xn)' son
lineales; para las anteriores condiciones hay dos (2) casos especiales:
1. Programación cuadrática:
i = n j =n
Z = f { x x , x 2 , x „ , x „ ) = X c , x , + X X d i i X i X ¡
j = 1 1 = i 7 = 1 /
Términos lineales Términos no lineales
cuadráti eos
2. Programación convexa separable:
Z = f{Xl,X2,X3, txa) = fl(xl)+f2(x2)+f3(x3)+ fn(xJ
Donde f"(X¡)' es una función de una sola variable.
• La Búsqueda Gradiental para Programación Convexa, si la funsión lineal es cóncava y las
restricciones son convexas.
• Restricciones no lineales, pero separables :
g, {Xx , x 2 x 3 , ,xn)=gn(xl)+gi2(x2)+ + gin(xn)
Para garantizar una solución óptima estos problemas deben contener restricciones muy estrictas
en las " g¡j {X -) " y en la función objetivo.
• La Programación Geométrica:
Los métodos más generales de solución aplicables en programación no lineal son los
multiplicadores de Lagrange y Karush - Kuhn - Tucker.
El m é t o d o de los mu l t i p l i c ado re s de Lag range cons i s te en ap l ica r la f u n c i ó n
_ _ \
F x,Á, m = / ( x ) - / l [ g , . ( x ) + ju , luego calcular las primeras derivadas parciales, igualarlas acero
y encontrar el óptimo del problema; para verificar el máximo o mínimo de la función se encuentran las
segundas derivadas parciales.
146
Las condiciones necesarias de Karush - Kuhn - Tucker también son suficientes si la función
objetivo y el espacio solución satisfacen ciertos requerimientos con respecto a la convexidad y a la
concavidad.
Una solución óptima de un problema de programación no lineal, corresponde a la solución óptima
definitiva si existen n números negativos A¡, i = 1,2,3, ,n tales que satisfacen las condiciones
siguientes:
g e_^r} = 3_Ar} 0 m
t r ' d X j d X j J J
2. 2 4 5 / X - O
t í d X j d X j
3. g. ( x * ) - b, = 0 57 A¡ >0 i = 1,2,3, ,n
4. 0 SI A, = 0
A¡ > 0 indica que la i- ésima restricción es equivalente a XR¡ - 0, donde XRi es la
i - ésima variable de holgura.
A¡ = 0 explica que la i - ésima restricción no es limitante a XR¡ > 0.
5. X > 0 j= 1,2,3, ,m
6. A¡ > 0 i=1,2,3, ,n
Para definir estas condiciones, definimos el problema de Programación no lineal generalizado
como:
OPT Z =f (x)
Sujeto a :
(x) < 0 i = 1 , 2 , 3 , , r
g, (x)> 0 i = r +1, ,p
g¡{x) = 0 i=p +1, ,n
147
El multiplicador de Lagrange es:
F [ x , x , p ] = f { x ) - ' f j 4 t , ] 2 A,.
V 7 i = 1 I = r +1 i= p+1
Sentido de optimización
Condiciones requeridas
Sentido de optimización
Función objetivo Espacio solución
Maximización Cóncava Conjunto convexo
Minimización Convexa Conjunto convexo
Sentido de la
Optimización
Condiciones requeridas
S i M
^ Convexa > 0 (l <i<r )
Maximización Cóncava
-<
Cóncava
Lineal
V
f
Convexa
< 0
Sin restricción
< 0
( r + l < / < p)
(p + l<i<n)
(l <i<r)
Minimización Convexa -< Concava
Lineal
> 0
Sin restricción
(r + \<i<p)
(p + \<i<n)
148
Solución Gráfica
Nos permite visualizar el óptimo, pero tiene la desventaja de servir únicamente para representar
pocas variables, hasta tres (3). Ejemplo:
MinZ = (X, - i f + (X2 -1)2
Sujeto a:
1. X] -X2<0
2. X,+X2<£
X,,X2 >0
En estagráfica podemos observar la región sombreada, la cual es cerrada, acotada, convexa, así
como también algunas curvas de nivel.
Este problema posee solución global en la región factible; todo mínimo local es global y al
verificarse las condiciones de convexidad, todo punto candidato a mínimo lo es.
149
Buscamos los puntos candidatos a mínimo Construyendo la función de Lagrange:
F(X,X) = (X, - 2 ) 2 + (X2 - 1 ) 2 + A,(-X,2 +X2)+A2(2-Xl-X2)
Las derivadas parciales igualadas a cero son:
dF
dXl
dF
dX,
= 2(X, - 2)-2Á¡Xl -Á2=0
= 2(X2-1)+Á¡-Á2 =0
8F
5 F
dA
= - X 2 +X2=0
2 - X, - X2 = 0
d-F
dX,2
82F
dX?
= 2 - 2 / 1 ,
a 2 F
= 0
a 2 F
s I T
Resolviendo el sistema de cuatro ecuaciones son cuatro incógnitas (primeras derivadas parciales)
obtenemos:
X= 1, X] = 1; X¡ = 0; X2 = 2; f T = 1,
Es decir, al verificar las condiciones del problema X*x = 1 yX2 = 1 es un mínimo global estricto.
150
Con sus restricciones:
\..X1K2<2
Xx,X2 >0
2.MAX Z = JYl+-JX¡
§ » I
Y BIBliO I 7
y
X,
Construimos la función de Lagrange:
/ _
F X , Á — + -J X2 + Aj (2 — ^Yj — X 2 )
v /
5/7
8X, 2^X,
82F 1
8X' 4X¡
8F 1
dX2 2jx~
d2F
d x ' 4X!
8F
- = 2 - X , - X i =0
8A, 7 2
82F
8Á2,
= 0
151
Resolviendo el anterior sistema de ecuaciones (primeras derivadas de parciales) llegamos a:
X\ = 0; X\ = 1, X¡ = 0 ;Z* = 2 , Valores que corresponden al máximo propuesto inicialmente.
3. MIN W = -2Xx - 6X2 + X? - 2X, X 2 + 2X\ Sujeto a :
1. X, + X2 < 2
2. - X , + 2X2 < 2
X, , x2 > o
x2
' 1 l ) f 2 - 2 n f2^
A = ; h= b = C=
v - 1 2 , 4 A
Formamos los multiplicadores de Lagrange por las restricciones
AX <by X >0 Por p y por u y el vector de las var iables libres por Y; sea :
M =
O -A
A' H
; g =
rb> í 7 ^ ii
vVJ
; Z =
152
Aplicando las condiciones de Korush - Kuhn - TUCKER el problema se reduce a encontrar la
solución del sistema S-MZ =q,S' Z =0 y (S,z)> 0
Calculamos las primeras derivadas:
dF
d X ,
= -2 + 2X,-2X2-A1+A2 = 0
dF
dX,
= -6-2X2 +4X2 -Á1-2Á2 = 0
dF
dÁ,
=2-X¡ ~X2 = 0
6F
d^
= 2+X,-2X2 = 0
Calculamos las segundas derivadas
d2F
d X,2
d2 F
d x2
= 2
MIN
d %
d %
Resolviendo las ecuaciones 1, 2, 3, 4 llegamos a :
x; = x: =^-;¡V'=- —
• 5 2 5 5
153
PROGRAMACIÓN CUADRATICA
Consideremos un problema de programación no lineal cuya función objetivo es la suma de términos
de la fo rma X X \ 2 X*" ; el grado del t é rmino
Xf X*2 X*" es ti{ +h2+ + . Un problema de programación no lineal,
cuyas restricciones son lineales y cuya función objetivo es la suma de términos de la forma
X¡'' X22 X''" (en la cual cada término tiene un grado de 2, 1 o 0) es un problema de
programación cuadrática.
Vamos a ilustrar de manera general el método de Wolfe para resolver problemas de programación
cuadrática.
Se define un problema de programación cuadrática como:
MIN W =CT X + XT Q X
Con sus restricciones:
A X <b
X > 0
Donde X e E" (Vector en E" con componentes continuas), C es un vector de precios con n
componentes, Q es una matriz de n x n, simétrica y positiva definida, es decir , X' Q X > 0 ,
para toda X e E" , excepto X = 0 , b es el vector de recursos con m componentes, A es una
matriz de m * n coeficientes tecnológicos y 0 es un vector con n ceros.
El problema de optimización anterior tiene restricciones lineales, si Q es una matriz nula se
convierte en un problema de programación lineal. Como Q es positiva definida , implica que W es
una función estrictamente convexa y por lo tanto el mínimo si existe es global; si Q es negativa
definida, W es estrictamente cóncava y si el máximo existe es global.
A continuación se escribe el problema en notación algebraica, se le aplican los multiplicadores
de Lagrange, se verifican las condiciones necesarias y suficientes de Karush - Kuhn- Tucker que
deben existir en un óptimo global.
El método de Wolfe sigue con la reescritura del problema original como un problema de
programación lineal con holguras complementarias; éste último problema es equivalente al problema
154
original. El problema de programación lineal a resolver será de 2 {m + n) + n variables, m + n
restricciones lineales y m + n restricciones de holgura complementaria.
Ejemplo
Resolver el siguiente problema de programación cuadrática por el método de Wolfe:
MAX Z = 10X, +25 X2 - 1 0 X,2 - X 2 -4 X, X2
Con sus restricciones :
1. X, + 2X2 < 10
2. X, + X2<9
X, X2 > 0
Aplicando los multiplicadores de Lagrange tenemos:
F X , À, ju = 10 X, + 25 X 2 - 10 X2 - X22 - 4X, X2 - Á, (X, + 2 X2- 1 0 ) -
(X, + X2 - 9) ~ / / , {-Xx)-m2 ( - X2)
Las primeras derivadas parciales son:
5 F
= 10-20 X - 4 X2 - À, - À2+ u. = 0 ÔX 2 , 2 ^ ,
ô F
j ^ = 25-2X2-4X,2A,-A2+M2=0
El problema de programación lineal equivalente al original de acuerdo al método Wolfe es:
MIN W = F¡ + V2
Sujeto a:
155
1. 2 0 X , + 4X2 + + - / / , +V{ = 1 0
2. 4 X 1 + 2 X 2 + 2 ^ + 4 - M i + v i = 2 5
3. X, + 2 X2 + YX = 1 0
4. X, + X 2 + Y2 = 9
Con las siguientes restricciones de holgura complementaria:
X, M, = 0
X2M2=0 ¿ Z « * ?
X, Y =0
Z, Y =0
Utilizando el método Simplex se tiene que la solución básica inicial es:
W=-35; Vl = 10; V2 = 25; Yx =10 ; Y2 = 9
En la primera iteración entra X, ( / / ,=0) a la base y sale Vx de la base; el punto extremo después
de iterar es:
1 19 17
W = -23; X, =-;V2= 23;Y.=— = -1 2 2 ' 2 2
En la segunda iteración entra y sale X, ( es de aclarar que aunque el Simplex
escoge Á¡ y para entrar a la base antes que lo haga X2, Á¡ y A^ no son aceptables, ya que
Y¡ y Y2 son positivos). El punto extremo luego de recalcular es:
^ = - 2 0 ; X 2 = | ; F 2 = 2 0 ; Y,=5;Y2 = j
En la tercera iteración no pueden entrar a la base A1 o A2 porque Yx y Y2 son positivas; el
Simplex toma como siguiente candidato a /i, y de salida Yx ; el punto extremo después de iterar es:
156
W=—15; X2 =5; V2=15; #=1QY2=4
En la última iteración (F¡ = O y V2 = 0 ) debe entrar Xx , pero no puede porque ¡ux es
positivo; el siguiente elemento a entrar a la base es A¡ el cual reemplaza a K, . Luego de recalcular
( pivotear) el punto extremo es:
W = 0; X2=5; AX=~; Yx = 4
La solución anterior corresponde al óptimo:
X, = 0 ; X\ = 5 ; Z* = 100
Algunos métodos para resolver problemas de Programación Cuadrádita son: Beale, Hildreth -
DEsopo , Zheil - Van de Panne, Barankin - Dorgman y Graves - Whinston, entre otros.
PROGRAMACION SEPARABLE
Una función f (Xx, X2, Xn) es separable si se puede expresar como la suma de n
funciones de una sola variable, fx ( X , ) , f2 (X2), fn (Xn) , es decir,
/ , x„) = y¡ ( x , ) + f2 (x2)+ + /„ (xn)
Un caso especial de programación separable ocurre cuando las funciones g¡ (X¡) son convexas,
resultando así un espacio convexo de solución; además la función f¡ (X¡) es convexa en caso de
minimización y cóncava en caso de maximización.
No existe un algoritmo único para solucionar problemas de programación convexa; en general
los algoritmos conocidos se pueden clasificar así:
1. Algoritmos de gradiente, en estos casos se modifica de alguna manera el procedimiento de
búsqueda del gradiente para evitar que la trayectoria de búsqueda penetre la frontera de restricción.
157
2. Algoritmos secuenciales no restringidos, incluye los métodos de función de penalización y de
función barrera; estos algoritmos convierten el problema de optimización restringida original en
una sucesión de problemas de optimización no restringida, cuyas soluciones óptimas convergen
a la solución óptima del problema original.
3. Algoritmos de Aproximación Secuencial, incluye métodos de aproximación lineal y
aproximación cuadrática; estos algoritmos sustituyen la función objetivo no lineal por una
sucesión de aproximaciones lineales o cuadráticas. Para problemas de optimización linealmente
restringidos, estas aproximaciones permiten la aplicación repetida de los algoritmos de
programaciónlineal o cuadrática.
A continuación resolvemos un problema de programación separable aplicando el método de la
base restringida.
MAXZ = Xx +X¡
Con sus restricciones:
3 X, + 2X\ < 9
Xx,X2>0
El método de aproximación nos sugiere que las variables separables son:
fx {Xx)=Xx- f2 (X2)=X42; g\ (Xl)=3Xl; gf (X2) = 2X22
Las funciones fx \Xx) y g¡ (Xl) se dejan como están (son lineales); f2 (X2 ) y gf (X2)
tienen puntos de ruptura ( K 2 = 4), como X2 < 3, entonces:
K a k ) s2M)
1 0 0 0
2 1 i 2
3 2 16 8
4 3 81 18
158
Luego:
A T' f2 + T¡ f2 (a2) + T¡ f2 + T¡ f2 (a])
f2 (x2)* o (t2i)+ i (:r;)+i6 (ti)+81 ( r / )
f2{X2)*T22 + 16T¡ + 81T?
g] (x})*2 T2 + 8 T¡ + 18 T42
Entonces el problema original por aproximación se convierte en:
MAX Z = X,+T2 + 16 r23 + 8 1 7;4
Sujeto a:
1. 3 X, + 2T2 +87/ + 18T24 < 9
2. T¡ + T2 + T¡ + T2 = 1
T2 >0, A" = 1,2,3,4
X, > 0
El tablero simplex inicial corresponde a:
> 1 1 16 81 0 0
CB VB T2 2 T
3
2 T
4 2
_ 1
r 2
0 S, 9 3 2 8 18 1 0
0 Ti 2 1 0 1 1 1 1 i
z 0 - 1 - 1 -16 - 8 1 0 0
t
Donde S{ es una variable de holgura (relleno).
La solución óptima por el Simplex a este problema equivalente es:
159
Luego el óptimo en términos de Xx y X2 es:
X] — 0 ; X 2 ~ 2 T2 4" 3 T2 \ X 2 { -JO,
f 1 \
+ 3 — ; X\ «2,1; Z* = —
1 , 1 0 / 2 2
PROGRAMACION GEOMETRICA
La Programación Geométrica soluciona un caso especial de problemas de Programación No
lineal. Este método resuelve al considerar un problema dual asociando los siguientes dos tipos de
Programación No lineal:
1. Problema geométrico no restringido:
i=n j=m
MIN W = Y e 71 Y.aij ¿—i 1 ,-_ 1 J
Donde C, > 0 , Yj > 0 , a¡j es real, para toda i = 1, ,n; 7=1,
2. Problema geométrico restringido:
«=» j=m 0
M I N W 0 = Y C ? 71 Y*«
Con sus restricciones :
'=" j-m k
gk(x)=lLc? « S - 1 ' k = l ^
160
Donde Cf > 0 ; YJ>0,afcJ es real, para toda i=1, y'=l, , m ; K = 0,1,2, ,/?;
se supone para ambos casos n,m y p son finitas, los exponentes a ¡j, a°¡j y a f j no tienen
restricciones de signo, las funciones W y W0 toman la forma de un polinomio, excepto que los
exponentes a , a'' ¡ y af pueden ser negativos; por esta razón y porque todas las C¡ y Cf son
mayores que cero (C¡ > 0 y Cf > 0 ) , W y W0 se denominan posinomiales. La Programación
Geométrica fue diseñada por Duffin, Peterson y Zener.
La lógica de la Programación Geométrica se basa en la desigualdad de Cauchy (desigualdad de
media aritmética - geométrica):
^ Media aritmética ponderada^ ^
yde YX,Y2, Ym j
Es decir,
>
Media geométrica ponderada
de Y Y Y uc i 2 , , i M
1 - Y , + - Y 2 + i y m > (Y^ [Y2)m (7j¿ m m m
¿ Ct Wi > V (Wj' , Donde Wt > 0 y ¿C. = 1
¿=i 1 - 1 /=i
El método de solución consiste en calcular las primeras derivadas parciales de W y fV0 ; de
la función objetivo se obtiene la ecuación:
^ Wt = 1: condición de normalidad.
i = i
De las primeras derivadas parciales iguales a cero se escribe la relación:
i-m
y ai . W¡ = 0: condición de ortogonalidad.
í = i
Donde a¡ j son los coeficientes positivos, m es el número de variables y el número de términos.
161
Generalmente, el número de términos precisa el número de factores de peso y el número de variables
independientes señala el número de ecuaciones.
Cuando n = m + 1 , se dice que el problema tiene cero grados de dificultad.
Cuando n — (m + l) > 0 , es un problema que no se puede resolver mediante Programación
Geométrica. Finalmente se resuelven los sistemas de ecuaciones simultáneas planteadas y se obtiene
la solución del problema. Ejemplo:
1. Encontrar la cantidad económica de pedido de un producto, es decir, se debe decidir que
cantidad del artículo conviene almacenar periódicamente; los costos totales asociados al producto y
su almacenamiento se pueden expresar como: CT = CCI + CHP + VC
2 Q Q '
Donde:
CT : Costo Total.
CCI : Costo Cargado al Inventario.
CHP: Costo de hacer de pedidos.
VC: Valor de Compra.
Q : Cantidad Económica de Pedido.
h : Costo de Almacenamiento Por Unidad Anual.
a : Costo de Hacer un Pedido.
d : Consumo Promedio al año.
k,P: Constantes.
La función objetivo tiene la siguiente formula general:
MIN CT = C, Q + C2 Q~x
162
//, + //2 = O 1.
L u e g 0 / y , - n 2 = 0 2.
De tal modo que al resolver el anterior sistema de ecuaciones simultáneas llegamos a que = ¡-i2
y la variable Q* debe ser tal que haga que los dos términos de la función objetivo sean iguales:
C,Q=C2 Q '
1
dCT C^ d2 CT _ 2C2
' <?02 ~ 0 3 > (mínimo).
Aporte de los métodos de solución para problemas de Programación No lineal ya mencionados
algunos de los conocidos son:
• Técnicas de búsqueda unidimensional: Minimax, Búsqueda simultánea: dos experimentos,
búsqueda simultánea: n experimentos, resolución, distinguibilidad, escalamiento, búsqueda
secuencial, método de Bolzano, búsqueda por bloques, búsqueda en bloques pares, búsqueda
dicotòmica, búsqueda de Fibonacci, búsqueda con resolución desconocida, búsqueda de sección
áurea, búsqueda de Fibonacci inverso y búsqueda mediante bloques impares, entre otros.
• Técnicas de búsqueda multidimensional: algunos modelos son: Eliminación multivariable,
métodos geométricos, métodos lógicos, búsqueda aleatoria, procedimientos de aproximación
estocásticos, búsqueda en forma de malla, método de búsqueda patrón: Hooke - Jeeves, método
de interpolación cuadrática de Powell, método del ascenso acelerado, método de Newton -
Raphson, método de Davidon - Fletcher - Powell, método de Broyden - Fletcher, método de
Fletcher - Reeves, método de Smith.
163
Otros métodos: método de Levenberg - Marquardt, Cuasi - Newton, gradiente conjugado,
subgradiente, Zoutendijk, programación sucesiva lineal (PSL), programación sucesiva cuadrática (PSC),
Rosen, Zangwill y técnica de minimización secuencial no restringida (SUMT), entre otros.
ALGUNOS PROGRAMAS DE COMPUTADORA
NOMBRE AUTOR
1. MÉTODOS DE BÚSQUEDA
OPTIM Boas
Búsqueda Secuencial Cooper
COMPLEX Davies
Rosenbrock Davies
Técnica de suma multigradiente Himmelblau
CANDIDE Himmelblau
Búsqueda Simple Miller
PROBE Sullivan
2. MÉTODOS DE GRADIENTE CON RECORRIDOS CORTOS
POP / 360 Colville
Pivote gradiental Greenstadt
POP II / 7094 Grigsby
Paquete de optimización Carburo Hutton
Búsqueda del gradiente generalizado Kephart
Método de programación aproximado Miller
Ascenso deflectado Miller
3. MÉTODOS DE GRADIENTE CON RECORRIDOS LARGOS
Gradiente generalizado reducido Abadie
GRGII Abadie
Direcciones factibles Anthony
Davidon con CRST Davies
Programación convexa Gauthier
Gradiente conjugado Goldfarb
Gradiente Reducido Huard
Proyección de gradiente corregido Kalfon
Gradiente proyectado Miller
Proyección de la variable métrica Murtagh
Gradiente revisado reducido Ribiere
Direcciones factibles modificadas Zzchach
164
4. METODOS QUE USAN HESSIANAS
Gauss - Newton - Carroll
SUMT
SOLVER
Bard
MCcormick
Wilson
5. OTROS
Programación separable
Método de centros
QSB
•WINQSB
LINDO / LINGO
AIMMS
CPLEX
FORT MP
GAMS
LP/MIP SOLVERS
LPS-867
MPL
SDPIMS
VISUAL MATH PROGRAMMING
XPRESS-MP
Harvey
Huard
Chang / Sullivan
Chang / Sullivan
Schagre
Paragon Decision Technology - Holanda
Compass Modeling Solutions - USA
Numerical Algorithms Group - USA
Gams Development Corporation - USA
Frontline Systems - USA
Applied Automated Engineering Corporation - USA
Modeling System - USA
Aspen Technology - USA
Sundown Software Systems - USA
Dash Associates Ltd - Inglaterra
Es importante aclarar que existen estudios comparativos de algoritmos en los cuales se analiza el
número de iteraciones en la obtención de un óptimo local y su respectivo tiempo de computadora;
estos estudios corresponden a Colville, Holzman y Stocker. Algunos métodos como los de tolerancia
flexible ( Paviani - Himmelblau) han resultado ser bastante eficientes en la práctica; los resultados de
los estudios de los algoritmos concluyeron que losmétodos que mejor se pueden aplicar en la práctica
por orden de importancia son:
1. Método generalizado de reducción de gradiente (Abadie / Carpentier)
2. Método de tolerancia flexible (Paviani - Himmelblau)
3. Técnica de minimización secuencial no restringida - SUMT - (Fiacco / Mccormick).
4. Método de aproximación Lineal de Smith (Smith).
5. Método generalizado de búsqueda de gradiente de Cross y Kephart (Cross / Kephart).
165
PASEO DE FIN DE A Ñ O
Cuando todos partieron al gran paseo de fin de año, cada coche llevaba exactamente
el mismo número de personas. A mitad de camino, se rompieron diez coches, de
modo que cada uno de los coches debió llevar una persona más.
Cuando volvían a casa descubrieron que se habían descompuesto quince coches
más, de manera que durante el viaje de regreso había en cada coche tres personas
más que al partir por la mañana. ¿ Cuántas personas asisteron al gran paseo anual ?
CAPITULO VI
S IMULACIÓN
Un experto es una persona que cada vez sabe más cosas sobre menos cosas.
N. Butler
INTRODUCCIÓN
De hecho, la simulación es una de las herramientas del análisis cuantitativo más ampliamente
usada. Varios estudios de las corporaciones americanas revelaron de 25% a 30% simulaciones de uso
en planificación corporativa. La simulación parece puede ser la solución a los problemas de dirección.
Todavía nosotros pensamos que en nuestro medio (Colombia) su uso es apenas incipiente. Empecemos
nuestra discusión de simulación con una definición simple.
Simular es intentar reproducir los rasgos, apariencia, y características de un sistema real. En este
capítulo, se pretende mostrar un recorrido general por la simulación. Nosotros no construiremos ningún
modelo de Física, como podría usarse un avión dentro de un túnel de viento para pruebas de simulación.
Pero así como se prueban aviones, ejemplares físicos y modificados bajo las condiciones experimentales,
para que nuestros modelos matemáticos se experimentan con estimar los efectos de varias acciones.
La idea detrás de la simulación es imitar una situación del mundo real matemáticamente, entonces
para estudiar sus propiedades y operando características, finalmente se pretenden dibujar las
conclusiones y decisiones y cursos de acción basados en los resultados de la simulación. De esta
manera, el sistema real está influenciado por las ventajas y desventajas de lo que puede ser una decisión
de la política en el modelo del sistema.
Simulación, desde el punto de vista empresarial debe seguir los siguientes pasos:
1. Definir claramente el problema.
2. Introducir las variables asociadas con el problema.
3. Elaborar la estructura numérica y traducir a un modelo.
4. Preparar posibles cursos de acción por probar.
5. Correr el experimento.
6. Considerar los resultados (decidiendo modificar posiblemente la planeación o entrada de datos);
7. Decidir el curso de acción a tomar.
167
Los pasos están ilustrados en la Figura 1.
EL PROCESO DE SIMULACION: El proceso de simulación deberá responder al siguiente
diagrama de flujo:
FIGURA .1 EL PROCESO DE SIMULACIÓN
168
Los conceptos más utilizados en simulación son:
• Un sistema es un conjunto de entidades que interactúan para la realización de un fin lógico.
• El estado de un sistema es el conjunto de variables necesarias para describir la condición del
sistema en un momento determinado.
• En un sistema, un objeto de interés se llama entidad y cualquier propiedad de una entidad se
denomina atributo y los momentos en los que ocurren los cambios en el sistema identifican
los eventos del modelo (por ejemplo llegada y salida de los clientes).
TIPOS DE SIMULACIÓN
• Un sistema discreto es aquel en el cual las variables de estado cambian solo en puntos discretos
o contables en el tiempo. Un ejemplo típico de simulación discreta ocurre en las colas donde
estamos interesados en la estimación de medidas como el tiempo de espera promedio o la longitud
de la línea de espera. Tales medidas solo cambian cuando un cliente entra o sale del sistema; en
todos los demás momentos, no ocurre nada en el sistema desde el punto de vista de la inferencia
estadística.
• Un sistema continuo es aquel en el cual las variables de estado cambian en forma continua a
través del tiempo. Un ejemplo típico de simulación continua es el estudio de la dinámica de la
población mundial; los modelos de simulación continua normalmente se representan en términos
de ecuaciones diferenciales en diferencias que describen las interacciones entre los diferentes
elementos del sistema.
• Un modelo estático de simulación es una representación de un sistema en determinado punto
en el tiempo.
• Una simulación dinámica es una representación de como evoluciona un sistema a través del
tiempo.
Podríamos intentar dar algunas acepciones acerca del modelado en simulación:
• Desarrollo de un modelo matemático-lógico de un sistema y la manipulación experimental de
él en una computadora.
• Implica la observación del comportamiento dinámico del modelo en el tiempo.
• Dependiendo de la naturaleza de los datos de entrada, los resultados pueden ser determinísticos
o estocásticos.
• Un medio para ganar experiencia artificial mediante el uso de un modelo que da apariencia o
efecto de realidad.
169
• Un medio para evaluar alternativas de acción y determinar cual hecho probablemente será el
más efectivo en la situación real.
• Se usa para problemas que son demasiado complejos para ser resueltos mediante técnicas
analíticas y/o matemáticas.
Técnicas Numéricas Técnicas Analíticas
Procesos
Determinísticos
VENTAJAS Y DESVENTAJAS DE LA SIMULACION
La simulación es una herramienta universalmente aceptada por diversas razones.
Ventajas:
1. Es un proceso relativamente eficiente y flexible.
2. Puede ser usada para analizar y sintetizar una compleja y extensa situación real, pero no
puede ser empleada para solucionar un modelo de análisis cuantitativo convencional.
3. En algunos casos la simulación es el único método disponible.
4. Los modelos de simulación se estructuran y nos resuelve en general problemas trascendentes.
5. Los directivos requieren conocer como se avanza y que opciones son atractivas; el directivo
con la ayuda del computador puede obtener varias opciones de decisión.
6. La simulación no interfiere en sistemas del mundo real.
7. La simulación permite estudiar los efectos interactivos de los componentes individuales o
variables para determinar las más importantes.
8. La simulación permite la inclusión en complicaciones del mundo real.
Montecarlo Simulación Análisis Estocástico
Métodos econométricos
Programación
matemática Optimización clásica
Sistemas Dinámicos
170
Desventajas:
1. Un buen modelo de simulación puede resultar bastante costoso; a menudo el proceso es largo
y complicado para desarrollar un modelo.
2. La simulación no genera soluciones óptimas a problemas de análisis cuantitativos, en técnicas
como cantidad económica de pedido, programación lineal o PERT / CPM / LPU. Por ensayo
y error se producen diferentes resultados en repetidas corridas en el computador.
3. Los directivos generan todas las condiciones y restricciones para analizar las soluciones. El
modelo de simulación no produce respuestas por si mismo.
4. Cada modelo de simulación es único. Las soluciones e inferencias no son usualmente
transferibles a otros problemas.
GENERACIÓN DE ALEATORIOS
Generación de números pseudoaleatorios:
Existen varios métodos para la generación de números pseudoaleatorios entre cero (0) y uno (1);
la importancia del método a emplear estriba en el hecho que los números generados deben cumplir
ciertas condiciones para poder validarlos:
• Uniformemente distribuidos: Los números aleatorios son los valores de las variables estadísticas
que pertenecen a la distribución uniforme; tienen las siguientes características:
Si r , (i=l, 2, 3, ) son números aleatorios, entonces su funciónf satisface la relación para
todos los valores:
Í0 para 1 > T > 0
f(T,) = ' [l para 0 < r,< 1
Es decir, la función / ( T ( ) en un punto T, expresa la posibilidad de que algunos números
aleatorios se encuentren en el intervalo [0, T, ). Los números pseudoaleatorios, son teóricamente
variables continuas con densidad f y una distribución acumulada F.
0 r ; < o
< r , o < r , < i
1 r i > l
171
r¡
f ( r t ) = \f(Ti)dx
0
r,
F( r , . ) = J l dx
0
•Estadísticamente independientes: Las variables L son independientes si su función G se puede
representar como :
G ( r , , r 2 , r3 , . . . , r „ ) = F, ( r , ) • F2 ( r 2 ) • F3 ( r 3 ) F„( r j
y si todos los números aleatorios tienen la misma distribución, entonces la relación toma la forma:
G(T,, r 2 , r 3 , , r „ ) = F ( r , ) • F ( r 2 ) • F ( r 3 ) F ( r j
i
•Su media debe ser estadísticamente igual a ~ :
o ^
1
• Su varianza debe ser estadísticamente igual a — : 6 12
o - \ x ) = j ( r ; -~f(\)dri = —
o 2 1 2
• Su período o ciclo de vida debe ser largo: Existen varios procedimientos de generación de
números pseudoaleatorios; para la simulación por computador son importantes los números
pseudoaleatorios cuyos generadores se basan en los procedimientos algebraicos. Este es el procedimiento
iterativo donde los números pseudoaleatorios se obtienen del número anterior o de varios anteriores
(proceso de recursion).
172
MÉTODOS PARA LA GENERACIÓN DE NUMEROS PSEUDOALEATORIOS
Uno de los métodos más utilizados para generar números pseudoaleatorios empieza con un valor
inicial ng, llamado semilla y a continuación por recursion los valores sucesivos n., i > 1, haciendo:
n. = an. (mod m)
Los métodos más empleados para la generación de los números pseudoaleatorios son los siguientes:
1. Contrastes empíricos
La aproximación a los generadores de números aleatorios exige contrastar ciertas propiedades
estadísticas de sus salidas. Algunos de los contrastes son genéricos y pueden utilizarse en la evaluación
de generadores de variables aleatorias. Mencionemos que muchos de estos contrastes se encuentran
implementados en los paquetes estadísticos comerciales más importantes. Además, algunos generadores
disponen de una teoría analítica que conduce a contrastes teóricos específicos.
Contraste J 2
El contraste X 2 es de bondad de ajuste. Es poco potente, por lo que permite justificar el rechazo
de una hipótesis, pero proporciona escaso soporte a su aceptación. El estadístico del contraste es:
i=i
2
cuya distribución asintotica es una Zk-r-i, donde r son los parámetros estimados y la aproximación se
acepta si min e¡ >5.
Contraste de Kolmogorov - Smirnov
Consideramos el caso en que F0 es continua. La función de distribución empírica de una muestra
X,, X,, ..., X se define corno 1' 2' n
#{X,<X}
FJx)= ,
173
Bajo la hipótesis nula Hn : Fx (x) = F0(x), esperamos que Fn se aproxime a Fg. Definimos el
estadístico bilateral de Kolmogorov-Smirnov
Dn = sup ¡ F „ ( x ) - F 0 ( x ) j
xcr
La distribución exacta de Dn está tabulada para valores seleccionados de n > 40 y del nivel de
significación a . Para muestras grandes, se utiliza la distribución asintótica de Dn.
Contraste de rachas
Dada la sucesión de observaciones X,, X , , . . . , X , construimos la sucesión de símbolos binarios i ¿ n
definida mediante 1 si Xi < X.+1, 0 si X. > Xj+1. Definimos racha creciente (decreciente) de longitud 1
a un grupo seguido de 1 números 1 o 0. Intuitivamente, rechazamos la aleatoriedad con un número
muy pequeño o muy grande de rachas. De ahí se obtiene inmediatamente el contraste.
Contraste de rachas por encima y por debajo de la mediana
Otro procedimiento para definir rachas es el recuento de observaciones que se sitúan a un mismo
lado de la mediana. La distribución asintótica del número de rachas, bajo la hipótesis de aleatoriedad, es
N[\ + (n/2),(n/2)]
De donde se sigue, inmediatamente, un contraste.
Contraste de permutaciones
Separamos las observaciones en k-uplas
ik+2' "• ' U(i+l)k)'
La k-upla general se escribe
(U i k + j ) í = i
Las o rdenamos crecientemente y consideramos la ordenación correspondiente de los
subíndices j . Bajo la hipótesis de la probabilidad de que dos números sean iguales es nula, hay k!
ordenaciones posibles. Bajo la hopótesis de independencia, todas las permutaciones son equiprobables,
174
.2
con probabilidad 1 / k! . Entonces es inmediato aplicar un contraste X con k! clases, distribución
2
asintótica XK\-1 , frecuencias esperadas r / k!, donde r es el número de k-uplas y frecuencias observadas
el número de veces que aparece cada ordenación.
Contraste de huecos
Fijamos dos valores a y (3 con 0 < a < J3< 1. La sucesión presenta un hueco de longitud m si
U. , Uj+m e [«, /?] pero Uj+], ... , Uj+m l e[a,(3]. Bajo la hipótesis de aleatoriedad de la serie, la
long i tud m de los huecos sigue una d is t r ibución geométr ica de pa rámet ro P
P ( hueco longitud m ) = p( 1 - p)m X
La hipótesis de aleatoriedad implica independencia de las longitudes de los huecos y podemos
2
aplicar un contraste X basado en las comparaciones de los números observados y esperados de
huecos de longitud m.
Repetición de contrastes
Para aumentar su potencia, los contrastes anteriores pueden repetirse N veces. La distribución
empírica de los valores del estadístico pueden compararse con su distribución teórica mediante, por
ejemplo, el contraste de Kolmogorov-Smirnov.
2. Generadores congruenciales lineales
Los principales son:
Métodos de los medios de cuadrados: Cada nuevo número de la secuencia es producido tomando
los dígitos medios m de un número obtenido mediante la elevación al cuadrado de un dígito. Ejemplo:
X0 = 3458 ;(X0)2 = 11957764
X, =9577; (X,)2 = 91718929
X2 = 7189; (X2)2 = 51681721
X3 = 6817; (X3)2 = 46471489
175
Método aditivo de congruencias: Inicializa con Avalores dados, con k un entero positivo y la
sucesión se da mediante:
n.+¡ an. +n.k ( mod m )
Método multiplicativo de congruencias: Calcula una sucesión de enteros no negativos, cada
uno de los cuales siempre es menor que m:
n.+¡ = an. ( mod m )
Método mixto de congruencias: Son números que se obtienen mediante la siguiente relación de
congruencia (con a mayor que 0):
n.+¡ an. +n k (mod m )
Generadores de registro de desplazamiento
Los generadores congruenciales pueden generalizarse a recursiones lineales de orden mayor.
Para k > 1, m primo, se define
= ( «Pn-l + - + akXnJm°d m
u = x / m n n
y el generador se denomina recursivo múltiple. El estudio de este generador se asocia al del polinomio
característico
P (z) = zk - a tzk l - . . . - ak
sobre el álgebra finita F con m elementos.
Generadores de Fibonacci retardados
Cuando n0 = 0 y n; = 1 en el método aditivo congruencial se obtiene por medio de generalización
el caso especial denominado secuencia de Fibonacci. Parte de la semilla inicial ( x p x2 , . . . , xr ) y usa la
recursión
donde r y s son retardos enteros que satisfacen r > s y o es una operación binaria que suele ser r +, -,
XÓXOR. Típicamente, los elementos iniciales son enteros y la operación binaria es la suma módulo 2".
176
La caracterización del periodo máximo de los generadores de Fibonacci retardados está bien estudiada
y se basan, de nuevo en el análisis de sucesiones lineales recursivas de enteros de la forma
x. = ( a, x , + a, x. , + ... + a x. ) mod m
i v 1 i-l 1 1-2 r i-r '
Generadores no lineales
Dada la estructura reticular de los generadores lineales, algunos autores sugieren utilizar
generadores no lineales. Se distinguen dos formas de introducir no linealidad en un generador:
a. Usar un generador con función de transición lineal, produciendo la salida mediante una
transformación no lineal del estado.
b. Usar un generador con función de transición no lineal.
Una propiedad común en estos generadores es que no producen una estructura reticular como la
de los lineales.Su estructura es altamente no lineal: típicamente, un hiperplano t-dimensional tendrá
a lo sumo t t-uplas solapantes de números.
Sea rn > 5 un primo arbitrario y Fm = {0. 1, ..., m - 1} el álgebra finita de orden m. Para un
entero z, se define z e Fm,z = z"'~2(modm) , que es la inversa de z para la multiplicación en Fm, si
z = 0 (mod rn). Dados a, b e F , a ^ 0, la sucesión congruencial inversa explícita se define
mediante
yn= an + b , n > 0
El generador congruencial de inversión explícita se obtiene mediante normalización
u = y / m n J n
Obviamente, las sucesiones { u n } y { y n } son periódicas con periodo máximo m.
Combinación de generadores
Para incrementar el período e intentar evitar las regularidades que muestran los generadores
lineales congruenciales se ha sugerido combinar diferentes generadores para obtener uno híbrido que
tal vez sea de mayor calidad que los generadores originales. Tales combinaciones pueden considerarse
heurísticas, algunas de las cuales han resultado bastante pobres.
177
Aunque el fundamento de estos procedimientos es esencialmente empírico, también se han
desarrollado algunos aspectos teóricos. En primer lugar, se ha observado que el período de un generador
híbrido es, en general, bastante más largo que el de sus componentes siendo, además, posible su
determinación. En segundo lugar, hay resultados teóricos que sugieren que algunas formas de
combinación de generadores que mejoran su comportamiento estadístico.
Generadores paralelos de números aleatorios
La forma más simple y obvia de generar números aleatorios con procesamiento en paralelo es
utilizar un solo generador fuente. La situación más sencilla se da cuando se considera un punto único
de comienzo para ese generador, que proporcionará números a todos los procesadores que los necesiten.
Hay dos inconvenientes importantes. Primero, a menos que haya una sincronización en la generación
de los números aleatorios no será posible garantizar que todos los procesos particulares reciban siempre
la misma secuencia exacta de números. La sincronización conlleva dificultades de implementación,
pero es necesaria para garantizar que los resultados sean reproducibles. En segundo lugar, para sistemas
paralelos basados en "paso de mensaje" puede haber un aumento considerable de gasto en la transmisión
de los números generados a los procesos que los necesitan.
Una forma sencilla de crear generadores separados para conjuntos de procesos consiste en
utilizar puntos de comienzo predeterminados, es decir, utilizar un único generador común con un
conjunto de semillas preseleccionadas para cada proceso. La ventaja de este procedimiento es que
todos los procesos usan el mismo código, aunque las sucesiones generadas y utilizadas por cada uno
serán distintas. Un inconveniente es que las sucesiones serán diferentes, pero sólo porque hay un
cambio de registro de unas a otras.
Generadores comerciales
Describimos aquí brevemente algunos generadores comerciales. Recomendamos la lectura del
articulo de Park y Miller (1988) como advertencia sobre la mala calidad de algunos generadores
comerciales.
IMSL implementa generadores multiplicativos de módulo m — 231 - 1 y multiplicadores
a = 16807,397204094,950706376. El lenguaje de simulación SIMSCRIPT II.5 implementa el mismo
tipo de generador con multiplicador a = 630360016, proporcionando semillas suficientemente separadas
para producir sucesiones independientes. El entorno estadístico S-PLUS implementa el algoritmo Super-
Duper de Marsaglia, basado en un generador multiplicativo y un generador de Taust-Worthe.
Lenguajes y /o paquetes de simulación
En esta parte haremos una descripción sucinta de algunos paquetes y/o lenguajes de simulación
de los más empleados en el medio.
178
Lenguajes
El desarrollo de los lenguajes de simulación comenzó a finales de los años cincuenta; inicialmente
los lenguajes que se usaron en fueron los de propósito general, los cuales tenían las siguientes ventajas:
• La situación a analizar se puede modelar en forma más o menos sencilla para el programador
por el conocimiento del lenguaje.
• El proceso se puede describir con tanta precisión como le sea posible en el lenguaje conocido.
• Se pueden realizar todas las depuraciones posibles.
Cualquier lenguaje de programación puede ser empleado para trabajar en simulación, pero los
lenguajes especialmente diseñados presentan las siguientes propiedades:
• Acaban la tarea de programación.
• Generan una guía conceptual.
• Colaboran en la definición de entidades en el sistema.
• Manejan la flexibilidad en los cambios.
• Ayudan a analizar y a determinar la relación y el número de entidades en el sistema.
Emshoff y Sisson consideran que la Simulación Discreta requiere de ciertas funciones comunes
que diferencian un lenguaje de simulación de uno de propósito general, entre las cuales se encuentran
las siguientes:
• Generar números aleatorios.
• Generar variables aleatorias.
• Variar el tiempo hasta la ocurrencia del siguiente evento
• Registrar datos para salida.
• Realizar análisis estadístico sobre datos registrados.
• Construir salidas en formatos determinados.
• Detectar inconsistencias y errores.
Los lenguajes precursores en Simulación fueron los de propósito general, entre ellos por mencionar
solo algunos tenemos: FORTRAN, ALGOL, COBOL, RPG, BASIC, PASCAL, MODULA, PL/1, etc.
Los principales lenguajes utilizados en simulación son:
Simulación de cambio continuo y de cambio discreto en computadoras híbridas H01; simulación
de incremento continuo con orientación a ecuaciones directas con énfasis en ecuaciones diferenciales
DSL/90, MIMIC, BHSL, DIHYSYS y S/360 CSMP; simulación de incremento continuo con
simuladores orientados a bloques con énfasis en ecuaciones diferenciales MIDAS, PACTOLUS,
SCADS, MADBLOC, COBLOC y 1130 CSMP; simulación de incremento continuo con simuladores
179
orientados a bloques con énfasis en ecuaciones de diferencias DYNAMO, DYSMAP 2; simulación de
incremento discreto con orientación a actividades CSL, CLP, GSP, GERT, FORSIM, ESP,
MONTECODE y MILITRAN; simulación de incremento discreto con orientación a eventos
SIMSCRIPT, GASP, SIMCOM, SIMULATE y SIMPAC; simulación de incremento discreto con
orientación a procesos SIMULA, OPS, SLAM y SOL; simulación de incremento discreto con orientación
a flujo de transacciones GPSS y BOSS.
Paquetes
Los paquetes son una versión depurada de los diferentes lenguajes de propósito general y presentan
algunas ventajas sobre los lenguajes de programación generales:
• Reducción de la tarea de programación.
• Definición exacta del sistema.
• Flexibilización mayor para cambios.
• Diferenciación mejor de las entidades que conforman el sistema.
• Relación estrecha entre las entidades del sistema.
Los paquetes de mayor utilización en simulación son:
EXCEL, STELLA, SIMAN, RISK, STORM, LINDO, CRYSTAL BALL, QSB, MOR/DS, OR/
MS, BEER GAME, GREENPACE, SIMULACION, TAYLOR II, CAPRE, SIMNETII, PROMODEL,
ITHINK, URBAN DYNAMICS y POWERSIM. En Simulación Gerencial podemos citar: FISH BANK,
FINANACAT, BUGA-BUGA y MARKOPS, TREE PLAN entre otros.
Un ejemplo de simulación discreta
Filas de espera
Se presentan situaciones en las cuales los requisitos de mano de obra no solamente están afectados
por el tiempo necesario para terminar una actividad sino también por el patrón de demanda de los
servicios de hombre. Para ilustrar esto, consideremos el caso de un encargado del puesto de herramientas.
Los operarios de máquina llegarán al puesto para obtener los accesorios de máquina que necesitan. En
el caso más sencillo, el tiempo necesario para atender a un operario y los momentos en los cuales
llegan los operarios serán constantes. Bajo estas circunstancias, la determinación de los requisitos de
mano de obra para el puesto de herramientas no presenta ninguna dificultad. Por ejemplo, si el tiempo
de atención es de 10 minutos por el operario de máquinay llega un operario de máquina cada 10
minutos, es evidente que debe asignarse un encargado al puesto. Si se hace esto, los acontecimientos
que se presentan durante un período típico de una hora pueden describirse como sigue:
180
Tiempo de
llegada de
operario
Tiempo en que
comienza el
servicio
Tiempo en que
termina el
servicio
Tiempo ocioso
del encargado
(minutos)
Tiempo de
espera del
operario
(minutos)
Operarios que
esperan para
que se les
atienda
1:00 1:00 1:10 0 0 0
1:10 1:10 1:20 0 0 0
1:20 1:20 1:30 0 0 0
1:30 1:30 1:40 0 0 0
1:40 1:40 1:50 0 0 0
1:50 1:50 2:00 0 0 0 '
Como puede verse, ni el encargado ni los operarios pierden tiempo y no se forma línea de espera
o cola o fila. En consecuencia, no habría necesidad de asignar sino un encargado al puesto de
herramientas. Sin embargo, la situación real es generalmente más compleja. Por ejemplo, es más probable
que solamente el tiempo de servicio promedio sea de 10 minutos y que un operario llegue cada 10
minutos en promedio. Como esto lo sugiere, un solo tiempo de servicio y un solo intervalo entre los
eventos de llegada puede ser más o menos de 10 minutos. En un caso como este, pueden presentarse
demoras de servicio y formarse una fila de espera. Para demostrar esto, consideremos otro período de
tiempo hipotético durante el cual los tiempos promedio de servicio y de llegada son de 10 minutos,
pero los valores individuales varían. Específicamente, supondremos que los tiempos de llegada y
servicio son los indicados en las dos primeras columnas de la tabla que sigue. Dados estos datos y
suponiendo que estará presente un encargado, podemos construir el patrón de acontecimientos que se
describe en el resto de la tabla.
Tiempo de
llegada de
operario
Tiempo de
servicio
necesario
(minutos)
Tiempo en
que
comienza el
servicio
Tiempo en
que
termina el
servicio
Tiempo
ocioso del
encargado
(minutos)
Tiempo de
espera del
operario
(minutos)
Operarios que
esperan para
ser atendidos
1:00 12 1 00 1 12 0 0 0
1:08 8 1 12 1 20 0 4 1
1:18 10 1 20 1 30 0 2 1
1:30 6 1 30 1 36 0 0 0
1:45 14 1 45 1 59 9 0 0
1:50 10 1 59 2 09 0 9 1
181