Embed Size (px)
Citation preview
INSTITUTO TECNOLÓGICO SUPERIOR
de Acayucan
Asignatura: Investigación de Operaciones
Clave de la asignatura: SCB - 0419
Carrera: Ingeniería en Sistemas Computacionales
A N T O L O G I A
Presenta:
ING. JOSÉ ALBERTO LIMÓN CORTAZA
ACAYUCAN, VER. JUNIO 2008
INVESTIGACIÓN DE OPERACIONES
Ing. José Antonio Limón Cortaza
III
INDICE
OBJETIVO GENERAL VI
JUSTIFICACION VII
UNIDAD I PROGRAMACIÓN LINEAL…………………………………………………... 7
1.1. Definición de desarrollo y tipos de modelos de investigación de
operaciones…………………………………...……………………………
8
1.2. Formulación de modelos……………………….………………………… 17
1.3. Método grafico…………………………………………………………….. 22
1.4. Formas estándar y canónicas……………………………………………. 27
1.5. Métodos simples…………………………………………………………... 30
1.6. Técnicas con variables artificiales………………………………………. 34
1.7. Método de la M………………………………………………………..
1.7.1. Método de las dos fases……………………………………………..
UNIDAD II ANÁLISIS DE REDES………………………………………………………… 40
2.1. Problema de transporte…………………………………………………... 41
2.1.1 Método de la esquina noroeste……………………………………. 45
2.1.2 Procedimiento de optimización…………………………………….
2.2. Problema del camino más corto………………………………………… 55
2.3. Problema del árbol expandido mínimo………………………………… 60
2.4. Problema de flujo máximo……………………………………………... 63
2.5 Ruta critica (PERT-CPM)…………………………………………………. 68
UNIDAD III PROGRAMACIÓN NO LINEAL……………………………………………… 82
3.1. Planteamientos de problemas de programación no lineal…………… 83
IV
3.2. Optimización clásica……………………………………………………… 83
3.2.1 Puntos de inflexión………………………………………………………. 84
3.2.3 Máximos y mínimos……………………………………………………... 84
3.3. Problemas no restringidos……………………………………………… 89
3.3.1 Multiplicadores de LAGRANGE (λ lambda)…………………………... 89
3.3.2 Interpretación económica………………………………………………. 89
UNIDAD IV TEORÍA DE INVENTARIOS………………………………………………….. 96
4.1. Sistemas de administración y control…………………………………… 97
4.2. Modelos determinístico……………………….………………………….. 102
4.2.1 Lote económico sin déficit……………………………………………… 103
4.2.2 Lote económico con déficit……………………………………………... 109
4.3 Lote económico con producción…………………………………………. 109
4.3 Modelo probabilístico……………………………………………………… 112
UNIDAD V LÍNEAS DE ESPERA…………………………………………………………. 115
5.1. Definiciones, característica y suposiciones……………………………. 116
5.2 Terminología y notación…………………………………………………... 119
5.3 Proceso de nacimiento o muerte………………………………………… 120
5.4 Modelos Poisson…………………………………………………………... 121
5.4.1 Un servidor……………………………………………………………….. 123
5.4.2 Múltiples servidores……………………………………………………... 123
5.5 Análisis de costo…………………………………………………………… 123
BIBLIOGRAFIA 129
OBJETIVO GENERAL
V
El estudiante aplicará las técnicas y modelos de investigación de
operaciones en la solución de problemas, utilizando o desarrollando
herramientas de software para tomar decisiones.
JUSTIFICACION
VI
La presente antología fue elaborada viendo la falta de apoyo didáctico que
existe en la institución y tendrá como finalidad complementar los
conocimientos del alumno a fin de elevar su nivel académico.
Será un gran apoyo para el maestro ya que con ella reforzará lo dicho en
clases, este documento es un apoyo didáctico y su información fue extraída
de diferentes autores tomando en cuenta los temas que se verán a lo largo
del curso.
UNIDAD 1
PROGRAMACION LINEAL
Objetivo: El estudiante comprenderá los modelos
y metodología que utiliza la
programación lineal y aplicara el
método simplex a problemas
propuestos.
UNIDAD I / PROGRAMACION LINEAL
- 8 -
1.1 Definición, desarrollo, tipos de modelos de I.O.
La Investigación de Operaciones es una ciencia gerencial, enfocada hacia
la toma de decisiones, basada en el método científico para resolver
problemas, es un enfoque sistemático que usa herramientas analíticas para
resolver problemas.
Tomar decisiones es la tarea esencial de toda persona o grupo que tiene
bajo su responsabilidad el funcionamiento de una organización entera o parte
de ella.
Su propósito de ayudar a tomar acción, científicamente. Se usa el enfoque
científico, el análisis cuantitativo. Por su casi ilimitada amplitud de
aplicaciones, se usa en negocios, industrias, gobierno y defensa. Una
empresa eficiente actualmente depende de las computadoras y de los
métodos cuantitativos para manejar su innumerables problemas, que pueden
ser problemas de rutina o muy complejos.
Historia:
Desde la primera guerra mundial se le dio la tarea a Thomas Edison la tarea
de averiguar las maniobras de los barcos mercantes fueran más eficaces
para disminuir las pérdidas de embarques causada por los submarinos
enemigos. El empleo un tablero táctico. Rutas más corta.
A finales de 1910 A. K. Erlang, Ing. Danés, estudio el comportamiento de las
fluctuaciones de la demanda de instalaciones telefónicas, en relación con los
equipos automáticos. Inicios del modelo de la línea de espera.
1930 Horace C. Levinson aplico modelos matemáticos refinados para
grandes cantidades de datos sobre todo modelos óptimos de los embarques:
1937 Se pidió a los científicos ingleses, que ayudaran a los militares a
descubrir la mejor manera de utilizar el radar para localizar aviones
enemigos.
1940 se reunió a otro grupo de científicos encabezados por él ingles Blackett
para estudiar los problemas de puntería contra los aviones enemigos.
UNIDAD I / PROGRAMACION LINEAL
- 9 -
Estudiando el uso del equipo de control de cañones en campo. El grupo
estaba integrado por dos fisiólogos, 2 físico – matemáticos, 1 físico general,
2 matemáticos, 1 astrofísico, un oficial del ejército. Después el grupo creció y
se dividió un grupo para la marina, fuerza aérea y otro para el ejército, que
llevaron a cabo estudios desde el inicio de la guerra 1941. A este tipo de
actividades se le conoció como “investigación operacional”.
1942 Se pusieron en funcionamiento los departamentos de investigación de
operaciones en el departamento de guerra y marina en los estados unidos
para problemas con el radar y la creación de convoyes para aminorar las
pérdidas causadas por los submarinos.
Cuando termino la guerra Gran Bretaña enfrentaba problemas de
administración creados por la nacionalización de la industria y por la
reconstrucción de instalaciones industriales con un nuevo enfoque. Por ello
los grupos de investigación de operaciones empezaron a ocuparse de los
problemas gubernamentales e industriales.
En cambio en estados unidos, al terminar la guerra siguieron las
investigaciones militares aumentaron manteniendo los grupos de
investigación de operaciones. Para 1950 comenzaron a entrar la
automatización y el uso de computadoras trayendo problemas de sistemas.
Los grupos de I.O. aprovecharon la oportunidad y se creó la programación
lineal. Teniendo aplicación en muchas industrias. Empezaron a aparecer
técnicas como el PERT, control de inventarios, y simulación.
La I.O. Se aplica en sistemas. Se usa para tomar decisiones dentro de
sistemas, y usa modelos como su esencia. Para tomar decisiones se modela
el sistema
En la toma de decisiones el análisis puede tomar dos formas: cualitativo y
cuantitativo.
El análisis cualitativo se basa principalmente en el juicio y experiencia de la
gerencia, incluye sentimientos intuitivos sobre el problema tratado y es más
un arte que una ciencia.
UNIDAD I / PROGRAMACION LINEAL
- 10 -
El análisis cuantitativo se concentra en hechos cuantitativos o datos
asociados con los problemas y desarrolla expresiones matemáticas que
describen las relaciones existentes en ellos. Seguidamente, utilizando
métodos cuantitativos, obtiene resultados con los que se hacen
recomendaciones basadas en los aspectos cuantitativos del problema.
El papel del análisis cuantitativo en la toma de decisiones puede variar
dependiendo de la importancia de los factores cualitativos. En algunas
situaciones, cuando el problema, el modelo y los insumos permanecen
iguales, el análisis cuantitativo puede hacer automática la decisión con los
resultados obtenidos al usar métodos cuantitativos. En otros casos, el
análisis cuantitativo es sólo una ayuda para tomar la decisión y sus
resultados deben ser combinados con información cualitativa.
Un sistema es un conjunto de elementos que interactúan entre sí.
Un modelo es una representación simplificada de un sistema de la vida real,
de una situación o de una realidad. Un modelo captura características
selectas de un sistema, proceso o realidad, y luego las combina en una
representación abstracta del original.
Los modelos pueden ser objeto de diversa clasificación.
Tres formas de modelo son: Icónico, Analógico y Simbólicos.
Los icónicos son representaciones a escala (réplicas físicas) de objetos
reales. Adecuados para descripción de acontecimientos en un momento
determinado. Por ejemplo la fotografía de una fabrica. Maqueta, etc.
Los analógicos o esquemáticos son modelos físicos en cuanto a la forma
pero no son semejantes físicamente al objeto que está siendo modelado
(mapas de carreteras). Muestran las características del acontecimiento que
se estudia. Curvas de demanda, diagramas de flujo. Representan relaciones
cuantitativas entre propiedades de los objetos de varias clases.
Los modelos simbólicos (llamados también matemáticos) representan
sistemas del mundo real; cuantifican sus variables y las combinan en
expresiones y fórmulas matemáticas. Son idealizaciones de problemas de la
UNIDAD I / PROGRAMACION LINEAL
- 11 -
vida real basados en supuestos claves, estimados y/ó estimaciones
estadísticas. Son representaciones que toman la forma de cifras, símbolos y
matemáticas.
Los modelos matemáticos son los que, tradicionalmente, han sido más
comúnmente identificados con la Investigación de Operaciones.
Los modelos matemáticos, contienen:
Función objetivo.- Como su nombre lo dice es el objetivo que se quiere
alcanzar, es el sentido de buscar una solución optima. Esto se logra
maximizando o minimizando.
Variables de decisión.- Son las variables que se pueden modificar, que
están bajo nuestro control e influyen en el desempeño del sistema.
Parámetros.- Son coeficientes fijos, estos no se pueden variar pero tienen
influencia en el sistema. Normalmente son los insumos.
Restricciones.- Son las limitantes que harán que las variables de decisión
solo puedan tomar ciertos valores.
Clasificación de los modelos matemáticos:
1) Cualitativos: La mayor parte de los problemas de negocios comienza con
problemas cualitativos, o propiedades que tienen los componentes.
Algunas veces es mejor emplear el análisis lógico, sistemas de clasificación,
métodos de ordenamiento, teoría de conjuntos, análisis dimensional. Ya que
el problema resulta muy complicado pasarlo a un modo cuantitativo.
Cuantitativos: La I.O. sistematiza los modelos cualitativos y los
desarrolla llegando a un punto en que puedan cuantificarse, y se convierte en
un modelo matemático, que contiene símbolos, contantes y variables.
2) Estándar: Modelos que se pueden aplicar para todos los negocios
solamente alimentando con los números apropiados de un problema.
Hechos a la medida: Cuando para resolver e problema se han
aplicado varias técnicas de diversas disciplinas.
UNIDAD I / PROGRAMACION LINEAL
- 12 -
3) Modelo Determinístico: Cuando para cualquier variable de decisión se
conoce el valor exacto de la función objetivo y de las restricciones.
Modelo Estocástico: Cuando para cualquier variable de decisión no
se conoce el valor exacto de la función objetivo y de las restricciones.
4) Modelo Descriptivo: Se construye para describir matemáticamente una
condición del mundo real.
Modelo optimización: Se construye con el fin de encontrar una
solución óptima de un conjunto de alternativas.
5) Modelos estáticos: Cuando el valor que se busca para las variables, es
aplicables a un solo periodo. Es decir las limitantes no sufren cambios con el
paso del tiempo aunque sea por el corto plazo.
Modelos dinámicos: Cuando el valor de las variables deben de ser
sucesiones para aplicarse en periodos múltiples. Este modelo está sujeto al
factor tiempo que desempeña un papel esencial en la secuencia de
decisiones.
6) Simulación: Utilizan la computadora para reproducir el funcionamiento de un
problema o sistema a gran escala. Comprende cálculos secuenciales, los
datos iníciales pueden introducirse o generarse por medio de números
aleatorios.
No simulación: son modelos de problemas donde no es posible
utilizar una simulación.
7) Modelos lineales: Cuando la función objetivo y las restricciones en términos
matemáticos son lineales.
Modelos no lineales: Cuando la función objetivo o las restricciones
en términos matemáticos son no lineales.
UNIDAD I / PROGRAMACION LINEAL
- 13 -
8) Modelos enteros: Si el valor de una o más variables de decisión deben de
ser entera.
Modelos no enteros: Si las variables de decisión son libres de asumir
valores fraccionarios.
CONSTRUCCIÓN DE UN MODELO
La Investigación de Operaciones hace uso extensivo del análisis cuantitativo,
este análisis es racional y lógico. Consiste en:
a) Definir claramente un problema, que previamente se ha determinado que
existe,
b) Desarrollar un modelo,
c) Recolectar los datos de insumo,
d) Solucionar el Modelo,
e) Validar resultados, Interpretarlos y
f) Implementarlos en la ejecución de una decisión.
A) Definir el problema es el paso inicial, es primordial y muchas veces el
paso más difícil. Debe reflejar una representación segura del interés total de
sistema. La esencia del problema se debe establecer explícitamente y no de
manera ambigua. La definición del problema es un paso crítico y
determinante en el éxito o fracaso de cualquier enfoque cuantitativo para
tomar decisiones. Si el problema no se ha escrito, no se ha definido.
Muchas veces se concluye que el problema debe ser redefinido después de
haber realizado varios pasos para tomar una decisión.
Al definir el problema se deben identificar alternativas, criterios para evaluar
esas alternativas, y seleccionarlas.
La optimización es un criterio utilizado y es sinónimo de maximización o
minimización. La evaluación de las alternativas se hace con modelos
B) El desarrollo de los modelos. Formular y construir el modelo son
procesos integrados. La formulación es el aspecto lógico conceptual y la
UNIDAD I / PROGRAMACION LINEAL
- 14 -
construcción es la expresión de las relaciones lógicas en el lenguaje
simbólico de la Matemática.
La Investigación de Operaciones provee un sinnúmero de modelos para
distintos sistemas.
El desarrollo de los modelos, y en general el análisis cuantitativo, involucra a
grupos interdisciplinarios.
El modelo debe tener solución, ser realista, fácil de entender y de modificar.
Además debe permitir que los datos de insumo requeridos puedan ser
obtenidos
Ventajas de utilizar modelos
Las principales razones para usar modelos, en lugar de trabajar directamente
sobre la realidad, son las siguientes:
a) Ahorro de dinero, tiempo u otro bien de valor;
b) Evitar riesgos de daños al sistema cuando se está solucionando el
problema;
c) Para entender mejor el ambiente real cuando éste es muy complicado.
C) La recolección de los datos, se refiere a obtener la información
cuantitativa que es necesaria para obtener una solución.
Las fuentes de datos incluyen:
a) Reportes de la organización y documentos;
b) Muestreos estadísticos;
c) Entrevistas con personas empleados o relacionadas con la organización
cuyo juicio y experiencia son invalorables y a menudo proporcionan
información excelente.
Además pueden incluirse otras medidas directas. A menudo los datos son
incorrectos o inapropiados porque son recolectados bajo suposiciones que
no son apropiadas. A veces no están disponibles y deben ser recogidos por
el analista.
UNIDAD I / PROGRAMACION LINEAL
- 15 -
Dependiendo de datos buenos, se obtendrán buenos resultados; de lo
contrario, se obtendrá lo que no se quiere, como resultado de la utilización de
un mal insumo.
D) La solución de modelos matemáticos, bien documentada en la
bibliografía de Investigación de Operaciones, incluye un algoritmo o serie de
cálculos específicos que deben realizarse. Cada modelo usa un particular
algoritmo. Muchos de ellos contienen pasos repetitivos y por eso se les llama
iterativos, esto permite su fácil implementación en la computadora.
En análisis cuantitativo la solución óptima es la mejor solución matemática.
E) Los modelos deben ser probados para su validez interna o externa. En
sentido interno, las representaciones matemáticas deben tener sentido unas
con respecto a las otras. En sentido externo, los resultados obtenidos del
modelo deben tener sentido cuando se comparan con la realidad de la
situación que es estudiada.
Datos pasados pueden ser usados frecuentemente para probar la validez de
un modelo
Matemático.
La interpretación de resultados implica examinarlos a la luz de los
objetivos propuestos. Se debe determinar las implicaciones de su aplicación.
Además, como el modelo es una aproximación de la realidad, debe ser
analizada la sensibilidad de la solución a cambios que ocurran en sus
insumos. Para ello se cuenta con el Análisis de Sensibilidad o Análisis de
Post- optimización.
E) Toma de decisión e implementación consiste en trasladar los resultados
obtenidos en detalladas instrucciones de operaciones para la organización.
Los procesos de control son necesarios.
Muchos grupos de análisis cuantitativo han fracasado en sus esfuerzos
porque han fallado en implementar, apropiadamente, una buena solución
viable.
UNIDAD I / PROGRAMACION LINEAL
- 16 -
La solución óptima de un modelo matemático, no es siempre la política que
debe ser implementada por la empresa.
La decisión final la debe tomar el ser humano, que tiene conocimientos que
no se pueden cuantificar exactamente, y que puede ajustar los resultados del
análisis para llegar a una decisión conveniente.
El análisis cuantitativo no reemplaza el sentido común, es un complemento.
Los modelos cuantitativos auxilian a los encargados de tomar decisiones,
pero es ir muy lejos decir que lo sustituye. El rol de la experiencia, intuición y
juicio del ser humano no puede ser disminuido.
Un punto clave es que la Investigación de Operaciones usa una metodología
que está objetiva y claramente articulada. Está construida alrededor de la
filosofía de que tal enfoque es superior al que está basado solamente en la
subjetividad y opinión de expertos. Por lo tanto conduce a mejores y más
consistentes decisiones. Sin embargo no excluye el juicio y razonamiento no
cuantificable del ser humano. No es pues un proceso absoluto de toma de
decisiones, sino una ayuda para tomar buenas decisiones.
METODOLOGIA DE INVESTIGACION DE OPERACIONES
DEFINICION
DEL
PROBLEMA
DESARROLLO
DE UN MODELO
MAT. Y
RECOLECCION
DE DATOS
RESOLUCION
DEL MODELO
MATEMATICO
SOLUCION
MODELO
MODIFICADO
ES
VALIDA
LA
SOLUCI
ON
UNIDAD I / PROGRAMACION LINEAL
- 17 -
1.2 Formulación de modelos de I.O.
Todo programa lineal consta de cuatro partes:
Función objetivo.- Como su nombre lo dice es el objetivo que se quiere
alcanzar, es el sentido de buscar una solución optima. Esto se logra
maximizando o minimizando.
Conjunto de Variables de decisión.- Son las variables que se pueden
modificar, que están bajo nuestro control e influyen en el desempeño del
sistema.
Parámetros.- Son coeficientes fijos, estos no se pueden variar pero tienen
influencia en el sistema. Normalmente son los insumos.
Conjunto Restricciones.- Son las limitantes que harán que las variables de
decisión solo puedan tomar ciertos valores.
Al formular un determinado problema de decisión en forma matemática, debe
practicar la comprensión del problema (es decir, formular un Modelo Mental)
leyendo detenidamente una y otra vez el enunciado del problema. Mientras
trata de comprender el problema, formúlese las siguientes preguntas
generales:
1.- ¿Cuáles son las variables de decisión? Es decir, ¿cuáles con las entradas
controlables? Defina las variables de decisión con precisión utilizando
nombres descriptivos. Recuerde que las entradas controlables también se
conocen como actividades controlables, variables de decisión y actividades
de decisión.
2.- Cuáles son los parámetros? Vale decir ¿cuáles son las entradas no
controlables? Por lo general, son los valores numéricos constantes dados.
Defina los parámetros con precisión utilizando nombres descriptivos.
3.- ¿Cuál es el objetivo? ¿Cuál es la función objetivo? Es decir, ¿qué quiere
el dueño del problema? ¿De qué manera se relaciona el objetivo con las
variables de decisión del dueño del problema? ¿Es un problema de
maximización o minimización? El objetivo debe representar la meta del que
toma la decisión.
UNIDAD I / PROGRAMACION LINEAL
- 18 -
4.- ¿Cuáles son las restricciones? Es decir, ¿qué requerimientos se deben
cumplir? ¿Debería utilizar un tipo de restricción de desigualdad o igualdad?
¿Cuáles son las conexiones entre las variables? Escríbalas con palabras
antes de volcarlas en forma matemática.
La Programación Lineal (PL) es un modelo que tiene un número m de
recursos que están limitados para repartirse en un número n de actividades.
Ahora describiremos el modelo canónico de la PL, y usaremos las siguientes
literales que representaran lo que se indica:
x Sabemos que es el conjunto de valores que puede asumir cada
actividad
b Es la cantidad total disponible de un recurso
a Es el coeficiente asociado a x que indica la cantidad de un cierto
recurso que se aplicara para llevar a cabo dicha actividad
j Como el subíndice a cada una de las actividades que pueden llevarse
a cabo, es decir j = 1, 2, 3 , ….n
i Como el subíndice a cada uno de los recursos limitados i= 1, 2, 3
…….m
Recurso
Consumo de recursos por unidad de
actividad Cantidad de
recursos
disponibles. Actividad
1 2 n
1 A11 a12 ………… a1n b1
2 A21 a22 ………… a2n b2
: _: : : : :
M am1 am2 ………… amn bn
Contribución
a Z por c1 c2 ……… cn
UNIDAD I / PROGRAMACION LINEAL
- 19 -
unidad de
actividad
Ejemplos de modelos matemáticos:
Decisión de fabricación
1) Una compañía que fabrica dos productos, mesas y sillas, fabricar una mesa
requiere de 30 pies cúbicos de tabla, 2 horas de mano de obra para su
armado y 4 hrs de mano de obra para su acabado. El fabricar una silla
requiere de 20 pies cúbicos de tabla, 2 horas de mano de obra de armado, y
6 horas para su acabado.
Esta compañía solo puede conseguir en una semana la cantidad de 120 pies
cúbicos de tablas, 9 horas de mano de para armado y 24 horas de mano de
obra para el acabado.
La mesa le deja una utilidad a la empresa de 10 pesos y la silla deja una
utilidad de 8 pesos.
La compañía desea saber si fabrica, puras sillas, puras mesas o una mezcla
de sillas y mesas, para que se obtenga la mayor utilidad para le empresa.
S.A.
2) El departamento de rayos X de un hospital tiene dos maquinas, A y B, que
pueden utilizarse para revelar radiografías. La capacidad máxima de
procesamiento diaria de estas maquinas es A = 80, B = 100 radiografías. El
departamento debe de planear procesar al menos 150 radiografías por día.
Los costos de operación por cada radiografía son $4 para la máquina A y 3
UNIDAD I / PROGRAMACION LINEAL
- 20 -
para la maquina B. ¿Cuántas radiografías por día debe procesar cada
máquina para minimizar costos?
S.A.
3) En un hospital el departamento de nutrición prepara el menú para la cena, una
para cada día del mes. Una comida consiste en espagueti, pavo, papas, espinacas y
pastel de manzana. Según los requerimientos la comida debe proporcionar 63 000
miligramos (mg) de proteínas, 10 mg de hierro, 15 de niacina, 1 mg de tiamina, y 50
mg de vitamina C. cada 100 gramos de esta comida proporciona la cantidad de
nutrientes y grasas indicadas en esta tabla:
Proteínas Hierro Niacina Tiamina Vitamina
C
Grasa
Espagueti 5 000 1.1 1.4 0.18 0.0 5 000
Pavo 29 000 1.8 5.4 0.06 0.0 5 000
Papas 5 300 0.5 0.9 0.06 10.0 7 900
Espinacas 3 000 2.2 0.5 0.07 28.0 300
Pastel 4 000 1.2 0.6 0.15 3.0 14 300
Para evitar demasiada cantidad de un tipo de comida, no debe incluirse en
ella más de 300 gramos de espagueti, 300 gr de pavo, 200 gr de papas, 100
gr de espinacas y 100 gr de pastel de manzana.
Determinar la composición de una comida que satisface los requerimientos
nutricionales y proporciona la mínima cantidad de grasas.
4) Una ensambladora de computadoras, fabrica 3 tipos diferentes de
modelos. El modelo económico que requieren de 1 hrs. de armado, 2
UNIDAD I / PROGRAMACION LINEAL
- 21 -
unidades USB y 3 centímetros cuadrados de plástico especial. El modelos
medio que se arman en 2 hrs. 3 unidades USB y 2.5 centímetros cuadrados
de plástico especial. El modelo de lujo necesitan 3 hrs. de armado, 1 unidad
USB y 4 centímetros cuadrados de plástico especial.
Las ganancias que deja una computadora económica son de 700.00 pesos,
una mediana, 3500.00 y una de lujo 7000.00. Se venderán todas las
unidades producidas, pero de acuerdo a la planificación están disponibles
100 hrs. de trabajo de armado, 200 Unidades USB y 600 centímetros
cuadrados de plástico especial.
¿Cuál será la producción que deja la mayor ganancia?
X1= Cantidad de computadoras económicas
X2= Cantidad de computadoras medianas
X3= Cantidad de computadoras de lujo
Max Z = 700 X1 + 3500 X2 + 7000 X3 o bien Max Z = C1x1 + C2x2 +
C3x3
x1 + 2x2 + 3x3 ≤ 100 o bien a11x1 + a12x2 + a13x3 ≤ b1
2x1 + 3x2 + x3 ≤ 200 a21x1 + a22x2 + a23x3 ≤ b2
3x1 + 2.5x2 + 4x3 ≤ 600 a31x1 + a32x2 + a33x3 ≤ b3
x1, x2, x3≥ 0
5) Una productora-vendedora produce 2 tipos diferentes de queso. El tipo 1 se
vende en 27 el kilogramo, fabricar un kilo requiere 10 pesos de materia prima y 14
pesos de mano de obra y transporte. El queso tipo 2 se vende en 21 pesos, pero el
costo la materia prima por kilo es de 9 pesos y 10 pesos de mano de obra y
transporte.
UNIDAD I / PROGRAMACION LINEAL
- 22 -
La fabricación de un kilo de queso tipo 1 requiere; 2 horas de secado, y 1
hora reposo en un lugar especial. La fabricación de un kilo de queso tipo 2; 1
horas de secado, y 1 hora reposo en un lugar especial.
La demanda de queso tipo 2 es ilimitada pero la del tipo 1 es de cuando
mucho 40 kilos a la semana. El tiempo total disponible para el secado es de
100 hrs y de 80 hrs de reposo. ¿Cómo se puede maximizar las utilidades?
1.3. Método grafico de investigación de operaciones.
Para solucionar un problema de PL por el método gráfico se debe seguir los
siguientes pasos:
1) En una sola gráfica se deben dibujar todas las inecuaciones del conjunto
de restricciones para encontrar la región factible. Por cada inecuación habrá
una línea recta en la gráfica
Tomar cada una de las inecuaciones y realizar lo siguiente:
a) Convertirla momentáneamente en una igualdad.
b) Despejar una de las variables.
c) Encontrar 2 puntos, asignándole 2 valores diferentes a la variable
independiente.
d) Dibujar la recta que debe pasar por los 2 puntos encontrados.
e) Encontrar cual región es la que hace verdadera a esa inecuación.
2) Trazar la recta de la función objetivo (recta de isoutilidades).
3) Desplazar de forma paralela esa recta de isoutilidades. Si el problema es
de maximización en dirección en que se incrementa Z. si es minimización
entonces en dirección en que se decrementa Z.
UNIDAD I / PROGRAMACION LINEAL
- 23 -
Al resolver un problema de programación lineal se puede tener uno de los
siguientes 4 casos:
Caso 1) El PL tiene una solución única. Es decir los valores de las
variables solo pueden tomar una solo valor para cumplir con la función
objetivo.
Caso 2) El PL tiene soluciones optimas múltiples, es decir una
cantidad de soluciones infinita para hacer verdaderos para cumplir la
función objetivo. Al desplazar la recta de isoutilidades queda en sobre
un segmento de alguna recta formada por una de las ecuaciones de
restricción.
Caso 3) El PL no es factibles, es decir no hay una solución que
satisfaga todas las inecuaciones.
Caso 4) El PL no es acotado. Es decir el valor que puede tomar Z la
región factible no tiene límites.
Región factible de un PL.- Es un conjunto de todos los puntos que
satisfagan las limitaciones y restricciones de signo de la PL.
Solución optima para un problema de maximización.- Es un punto con el
valor de función objetivo más grande en la región factible.
Solución optima para un problema de minimización.- Es un punto con el
valor de función objetivo más pequeño en la región factible.
1) Una compañía que fabrica dos productos, mesas y sillas, fabricar una
mesa requiere de 30 pies cúbicos de tabla, 2 horas de mano de obra
para su armado y 4 hrs de mano de obra para su acabado. El fabricar
una silla requiere de 20 pies cúbicos de de tabla, 2 horas de mano de
obra de armado, y 6 horas para su acabado.
UNIDAD I / PROGRAMACION LINEAL
- 24 -
Esta compañía solo puede conseguir en una semana la cantidad de 120 pies
cúbicos de tablas, 9 horas de mano de para armado y 24 horas de mano de
obra para el acabado.
La mesa le deja una utilidad a la empresa de 10 pesos y la silla deja una
utilidad de 8 pesos.
La compañía desea saber si fabrica, puras sillas, puras mesas o una mezcla
de sillas y mesas, para que se obtenga la mayor utilidad para le empresa.
UNIDAD I / PROGRAMACION LINEAL
- 25 -
2) Una productora-vendedora produce 2 tipos diferentes de queso. El tipo 1
se vende en 27 el kilogramo, fabricar un kilo requiere 10 pesos de
materia prima y 14 pesos de mano de obra y transporte. El queso tipo 2
se vende en 21 pesos, pero el costo la materia prima por kilo es de 9
pesos y 10 pesos de mano de obra y transporte.
La fabricación de un kilo de queso tipo 1 requiere; 2 horas de secado, y 1
hora reposo en un lugar especial. La fabricación de un kilo de queso tipo 2; 1
horas de secado, y 1 hora reposo en un lugar especial.
La demanda de queso tipo 2 es ilimitada pero la del tipo 1 es de cuando
mucho 40 kilos a la semana. El tiempo total disponible para el secado es de
100 hrs y de 80 hrs de reposo. ¿Cómo se puede maximizar las utilidades?
UNIDAD I / PROGRAMACION LINEAL
- 26 -
3) El departamento de rayos X de un hospital tiene dos maquinas, A y B, que
pueden utilizarse para revelar radiografías. La capacidad máxima de
procesamiento diaria de estas maquinas es A = 80, B = 100 radiografías. El
departamento debe de planear procesar al menos 150 radiografías por día.
Los costos de operación por cada radiografía son $4 para la máquina A y 3
para la maquina B. ¿Cuántas radiografías por día debe procesar cada
máquina para minimizar costos?
UNIDAD I / PROGRAMACION LINEAL
- 27 -
OBJ. 1.4 FORMAS ESTÁNDAR Y CANONICA
La forma canónica de la programación lineal es:
Max Z= c1x1 + c2x2 ………..+ cnxn
Sujeto a las restricciones:
a11x1 + a12x2 …….. + a1nxn ≤ b1
a21x1 + a22x2 ………..+ a2nxn ≤ b2
am1x1 + am2x2 ………..+ amnxn ≤ bm
x1 ≥ 0, x≥ 0………. xn≥ 0
Se puede observar que en la forma canónica:
1) La función objetivo se maximiza
2) Las restricciones de los recursos son representados por
desigualdades menor o igual a los recursos limitados (≤)
3) La variables todas deben ser mayores que cero
UNIDAD I / PROGRAMACION LINEAL
- 28 -
Esto todavía lo podemos resumir más si hacemos una matriz A con los
coeficientes de los aij:
a11 a21 …… a1n
a21 a22 …… a2n
a11 a21 …… a1n
.
A= .
am1 am1 …… amn.
También formamos un vector con los coeficientes cj:
= [c1, c2, c3 …cn]
Formamos un vector con los coeficientes xj:
Formamos un vector con los coeficientes bi:
Por lo tanto la forma canónica reducida es
y
Para poder resolver de forma algebraica el modelo de programación lineal
debe tener las siguientes propiedades:
UNIDAD I / PROGRAMACION LINEAL
- 29 -
a) Todas restricciones deben ser ecuaciones (igualdades) y el segundo
miembro no debe de ser negativo.
b) Todas las variables no deben ser negativas
c) La función objetivo puede ser de maximización o de minimización.
a) Para que todas las restricciones se conviertan a ecuaciones
(igualdades):
1) Las restricciones de tipo ≤ se le suma una variable de holgura al
primer miembro de la ecuación.
Ejemplo:
X1 + 2x2 ≤ 6 se convierte en: X1 + 2x2 + Xh = 6
2) Las restricciones de tipo ≥ se le resta una variable de exceso al primer
miembro de la ecuación.
Ejemplo:
X1 + 2x2 ≥ 6 se convierte en: X1 + 2x2 - Xe = 6
3) El segundo miembro de una ecuación puede hacerse no negativo
multiplicando ambos lados por -1
X1 + 2x2 - 5x3= -6 se convierte en: -X1 - 2x2 + 5x3 = 6
4) En una desigualdad, el signo se invierte al multiplicar por -1
X1 - 2x2 ≥ -6 se convierte en: -X1 + 2x2 ≤ 6
b) Todas las variables no deben ser negativas
En caso de existir una variable irrestricta (no restringida) xi puede expresarse
en término de dos variables no negativas
xi = xi´ + xi´´
La sustitución debe efectuarse en todas las ecuaciones incluyendo la función
objetivo.
C) como sabemos el problema de PL puede ser maximización o
minimización, pero algunas veces es conveniente convertir de una forma a
otra:
UNIDAD I / PROGRAMACION LINEAL
- 30 -
La maximización de una función objetivo equivale a la minimización del
negativo de la misma función y viceversa
Maximizar z = 5x1+2x2+3x3 es igual a minimizar –z = -5x1 – 2x2 – 3x3
Además la función objetivo de debe igualar a cero:
z = 5x1+2x2+3x3 se convierte a z- 5x1-2x2-3x3=0
Aprovechando estas propiedades podemos pasar cualquier problema de PL
de la forma canónica a la forma estándar que es la que se trabaja de forma
algebraica y que tiene la forma general de:
Z - c1x1-c2x2…………cnxn
Sujeto a:
a11x1 + a12x1 ………….. +a1nxn+ xh1 = b1
a21x1 + a22x1 …………..+a2nxn+ xh2 = b2
am1x1 + am2x1 …………..+a1mxn+ xhm = bm
En donde:
x1 ≥ 0, x2≥ 0………. xn≥ 0 xh1 ≥ 0, xh2≥ 0………. Xhm≥ 0
1.5 método Simplex
El método simplex es un algoritmo, o sea un proceso que se repite un
procedimiento sistemáticamente hasta obtener el resultado deseado.
Además de las iteraciones, los algoritmos incluyen un procedimiento para
iniciar y un criterio para determinar cómo detenerse.
Los pasos para aplicar el método simplex son:
1) El modelo matemático debe estar en la forma estándar. Después de
introducir las variables de holgura, a las variables originales se le
nombra variables no básicas y a las variables de holgura se le llama
variables básicas. De aquí podemos tomar la primera solución, que se
conoce como solución básica factible inicial. Las variables no básicas
toman el valor de cero y en el resto de las ecuaciones se lee como si
no existieran, por lo tanto las variables básicas tomaran el valor de la b
UNIDAD I / PROGRAMACION LINEAL
- 31 -
correspondiente. Para mayor comodidad a la hora de realizar las
operaciones matemáticas, la información de la forma estándar se
puede acomodar en una tabla:
Ejemplo:
MAX Z = 3x1 + 5x2
Sujeto a:
x1 ≤ 4 x1, x2, son las variables no básicas
(originales)
+ 2x2 ≤ 12 x3, x4 , x5 son las variables básicas
(holgura)
3x1 + 2x2 ≤ 18
x1 ,x2 ≥ 0
MAX Z - 3x1 - 5x2 = 0
Sujeto a:
x1 + x3 = 4 x1, x2, son las variables no básicas
(originales)
+2x2 +x4 =12 x3, x4 , x5 son las variables básicas
(holgura)
3x1+2x2 +x5 =18
Básica Ecuación Z X1 X2 X3 X4 X5 Solución
Z 0 1 -3 -5 0 0 0 0
X3 1 0 1 0 1 0 0 4
X4 2 0 0 2 0 1 0 12
X5 3 0 3 2 0 0 1 18
Para este ejemplo la solución básica factible inicial es (0, 0 , 4 , 12 , 19 )
Es decir x1= 0, x2= 0, x3= 4, x4= 12, x5=18
2) Paso iterativos. Cada vez que se itera el método simplex se mueve de
una solución factible básica actual, a una solución factible adyacente
mejor.
UNIDAD I / PROGRAMACION LINEAL
- 32 -
El método consiste en convertir una variable no básica (llamada variable
básica entrante) en una variable básica, y al mismo tiempo convertir una
variable básica (llamada variable básica saliente) en una variable no básica y
se identifica la nueva solución factible.
Para seleccionar la variable básica entrante. Si existen variable no básicas
con coeficientes negativos en la columna 0 (función objetivo), se selecciona
la de mayor valor negativo. A la columna donde se encuentra se le nombra
columna pivote.
Para seleccionar a la variable básica que sale, se toman todos los valores de
la columna solución y se dividen por su correspondiente coeficiente de la
columna pivote, se identifica el cociente de menor valor y a ese reglón se le
llama renglón pivote. Al número que se encuentra en la intersección de la
columna pivote y el renglón pivote se le llama número pivote.
Para determinar la nueva solución factible, se construye una nueva tabla
simplex, por medio de la eliminación de Gauss.
A. El renglón pivote se divide entre el numero pivote, por lo tanto ahora el
numero pivote se convierte en la nueva variable básica con coeficiente
1
Renglón pivote nuevo (RPN) = renglón pivote anterior / numero pivote
B. Siguiendo con la eliminación de Gauss se obtienen los demás
renglones de la tabla. Los valores de la nueva variable básica debe
hacerse 0 en todos los demás renglones incluso en la ecuación 0. Si
algún renglón ya tiene coeficiente cero en la columna de la nueva
variable básica, ese renglón se pasa sin cambio alguno a la nueva
tabla.
Nueva ecuación = Ecuación anterior – (coeficiente de la columna
pivote) x (RPN)
En el ejemplo anterior después de realizar lo pasos se tiene la nueva tabla
que es:
UNIDAD I / PROGRAMACION LINEAL
- 33 -
Básica Ecuación Z X1 X2 X3 X4 X5 Solución
Z 0 1 -3 0 0 5/2 0 30
X3 1 0 1 0 1 0 0 4
X2 2 0 0 1 0 1/2 0 6
X5 3 0 3 0 0 -1 1 6
Las nuevas soluciones son (0, 6, 4, 0 , 6)
3) Prueba de optimalidad: si todas las variables no básicas tienen
coeficiente positivo o nulo en el renglón 0 se ha obtenido la solución
optima, en caso contrario se tiene que volver a iterar hasta que esta
condición se cumpla.
Como se observa en el ejemplo aun no se cumple con esta prueba, por lo
que de nuevo se itera y se obtiene la nueva tabla:
Básica Ecuación Z X1 X2 X3 X4 X5 Solución
Z 0 1 0 0 0 3/2 1 36
X3 1 0 0 0 1 1/3 -1/3 2
X2 2 0 0 1 0 1/2 0 6
X1 3 0 1 0 0 -1/3 1/3 2
La nueva solución es (2, 6, 2, 0, 0)
Como se cumple la prueba esta es la solución óptima por lo que se detiene el
proceso, con esos valores para las variables.
X1= 2, X2=6, X3= 2, X4=0, X5= 0
Max z = 3x1+5x2
=3(2)+5(6)
=6 + 30
= 36
UNIDAD I / PROGRAMACION LINEAL
- 34 -
1.6 Método de la M
El algoritmo Simplex requiere de una solución factible básica (sfb) inicial.
Hasta ahora en los problemas que sean resueltos se determino una sfb
inicial usando las variables de holgura como si fueran variables básicas. Pero
si un PL tiene una restricción ≥, no sería tan evidente una sfb inicial.
Descripción del método de la gran M.
Paso1.- Modifique las restricciones de tal manera que el lado derecho de
cada una sea no negativo. Para lograrlo, cada restricción con un segundo
miembro se multiplica por -1. Recuerde que si se multiplica una desigualdad
por un número negativo se invierte la dirección de la desigualdad.
Paso 1ª.- Identifique cada restricción que es ahora (después del paso 1) una
restricción = ó ≥.
Paso 2.- Convierta cada restricción de desigualdad en la forma estándar.
Esto quiere decir que si la restricción i es una restricción ≤ se suma una
variable de holgura y si la restricción i es una restricción ≥ se resta una
variable de excedente.
Paso 3.- Si después de haber terminado el paso 1 la restricción i es una
restricción ≥ ó =, sume una variable artificial, también sume la restricción de
signo que debes ser mayor o igual a cero.
Paso 4.- Sea M un numero positivo muy si el PL es un problema de
Minimización sume por cada variable artificial Mai a la función objetivo. Si el
PL es un problemas de Maximización sume por cada variable artificial -Mai a
la función objetivo.
Paso 5.- Como cada variable artificial está en la base de inicio, todas las
variables artificiales se tienen que eliminar del renglón 0. Antes de empezar
el simplex. De esta manera se asegura que se empieza con una forma
canónica. Al elegir una variable entrante, recuerde que M es un número
positivo muy grande. Por ejemplo 4M-2 es más positivo que 3M+900, y -6M-
5 que -5M-40. Ahora se resuelve el problema transformado por el simplex, si
todas las variables artificiales son iguales a 0 en la solución óptima, entonces
UNIDAD I / PROGRAMACION LINEAL
- 35 -
se ha encontrado la solución óptima del problema original. Si alguna de las
variables artificiales es positiva en la solución óptima, entonces el problema
original es no factible.
Mediante el siguiente ejemplo se ilustra la forma de trabajar estos problemas.
S.A.
S.A.
1).- Como el lado derecho no tiene lado negativo no se multiplica por -1.
2).- Sumar una variable de holgura a la ecuación 2 y restarle una variable de
exceso a la Ecuación 2.
MIN. Z = 2X1 + 3X2
S.A.
10
20
4
34
1
2
1
21
421
321
XX
XXX
XXX
0,,, 4321 XXXX
Paso 3.- Sumar una variable artificial a la ecuación 2 y la ecuación 3.
MIN. Z = 2X1 + 3X2
S.A.
UNIDAD I / PROGRAMACION LINEAL
- 36 -
10
20
4
34
1
2
1
6
5
21
421
321
X
X
XX
XXX
XXX
0,,,,, 654321 XXXXXX
Paso 4.- Como es un problema de Minimización se suma MX5 + MX6 a la
función objetivo.
Teniendo en cuenta que M es un valor muy grande.
MIN. Z = 2X1 + 3X2 + MX5 + MX6
S.A.
10
20
4
34
1
2
1
6
5
21
421
321
X
X
XX
XXX
XXX
0,,,,, 654321 XXXXXX
Paso 5.- Al observar la función objetivo hay que igualar la a cero.
Quedando:
MIN. Z - 2X1 - 3X2 - MX5 - MX6 = 0
Aquí debemos eliminar las variables artificiales - MX5 - MX6
Para ello observamos que - MX5 proviene de la ecuación 2, por ello a la
ecuación 2 la multiplicamos por M y las sumamos a la función objetivo.
Pero también que - MX6 proviene de la ecuación 3, por ello a la ecuación 3
la multiplicamos por M y las sumamos a la función objetivo, quedando lo
siguiente:
UNIDAD I / PROGRAMACION LINEAL
- 37 -
Por lo tanto el problema lineal a resolver es:
S.A.
Pasando esto a la tabla simplex queda:
Básica Ecuación X1 X2 X3 X4 X5 X6 Solución
Z 0 2M - 2 4M - 3 0 - M 0 0 30 M
X3 1 2
1
4
1 1 0 0 0 4
X5 2 1 3 0 -1 1 0 20
X6 3 1 1 0 0 0 1 10
La solución inicial factible es: x1 = x2 = x4 = 0, x3 = 4, x5 = 20, x6 = 10.
Como se observa el problema es de minimización, por lo tanto debe de
buscarse que no haya valores positivos en la ecuación Z. Se observa que
esta (2M-2) y (4M-3), como (4M-3) es mayor entonces esa será la columna
pivote que es de x2.
UNIDAD I / PROGRAMACION LINEAL
- 38 -
Al dividirse la solución entre la columna pivote se tiene que el menor es 20/3
por lo tanto el renglón dos es pivote y el número pivote el 3, por lo tanto el
reglón dos se divide entre 3: quedando:
Básica Ecuación X1 X2 X3 X4 X5 X6 Solución
Z 0 2M - 2 4M - 3 0 - M 0 0 30 M
X3 1 2
1
4
1 1 0 0 0 4
X5 2 1/3 1 0 -1/3 1/3 0 20/3
X6 3 1 1 0 0 0 1 10
Ahora hay que volver ceros todos los valores de columna de x2. Empezando
por la función objetivo tenemos que al reglón 2 lo multiplicamos por (- 4M +
3) y lo sumamos a la función objetivo.
203
1001
3
41
3
1001
3
2
203
8001
3
41
3
40341
3
4300003422
MMMM
MMMMM
MMMM
Se eliminan los valores del reglón 1 y 3 quedando la tabla:
Básica Ecuación X1 X2 X3 X4 X5 X6 Solución
Z 0 2/3M -
1 0 0
1/3 M
+ 1
- 4/3 M
+ 1 0
10/3 M +
20
X3 1 5/12 0 1 1/12 -1/12 0 7/3
X2 2 1/3 1 0 -1/3 1/3 0 20/3
X6 3 2/3 0 0 1/3 -1/3 1 10/3
Las soluciones de esta tabla son: x1, x4, x5 = 0, x2 = 20/3, x3 = 7/3, x6 = 10/3
Pero como se observa existe todavía positivos en el reglón cero, por lo tanto
sale x1 ya que 2/3M - 1 es mayor que 1/3M + 1.
Dividiendo la solución entre los valores de la columna x1 tenemos que el
menor es 10/3 entre 2/3. Por lo tanto el numero pivote es 2/3.
Multiplicando el tercer reglón por 3/2 la tabla queda:
UNIDAD I / PROGRAMACION LINEAL
- 39 -
Básica Ecuación X1 X2 X3 X4 X5 X6 Solución
Z 0 2/3M -
1 0 0
1/3 M
+ 1
- 4/3 M
+ 1 0
10/3 M +
20
X3 1 5/12 0 1 1/12 -1/12 0 7/3
X2 2 1/3 1 0 -1/3 1/3 0 20/3
X6 3 1 0 0 ½ -1/2 3/2 5
Ahora hay que volver ceros todos los valores de columna de x1. Empezando
por la función objetivo tenemos que al reglón 3 lo multiplicamos por (- 2/3M +
1) y lo sumamos a la función objetivo.
2523/42
1
2
1000
53
1023/4
2
1
3
1
2
1
3
10013/2
203
1001
3
41
3
1001
3
2
MM
MMMMM
MMMM
Se eliminan los valores del reglón 1 y 2 quedando la tabla:
Como se observa no hay valores positivos en la función objetivo por lo tanto
se ha encontrado la solución óptima que es:
X1 = 5; X2 = 5; X3 = 1/4; X4 = X5 = X6 =0
SI AL RESOLVER UN PROBLEMA DONDE TENGAN VALORES LA
VARIABLES ARTIFICIALES, SE DICE QUE ESE PROBLEMA NO TIENE
SOLUCIÓN ÓPTIMA.
Básica Ecuación X1 X2 X3 X4 X5 X6 Solución
Z 0 0 0 0 -1/2
- M +
1/2
- 4/3
M + 2 25
X3 1 0 0 1 - 1/8 1/8 - 5/8 1/4
X2 2 0 1 0 - 1/2 1/2 - 1/2 5
X1 3 1 0 0 1/2 - 1/2 2 5
UNIDAD 2
ANÁLISIS DE REDES
Objetivo: Comprenderá y aplicará los diferentes
modelos matemáticos planteados como
problemas de redes y sus métodos de
solución.
UNIDAD II / ANÁLISIS DE REDES
- 41 -
2.1 Problema De Transporte
Modelo Del Transporte
Este modelo tiene que ver con la determinación de un plan de costo mínimo
para transportar una mercancía desde varias fuentes (orígenes, centros de
abastecimientos, puntos de suministro, que ejemplo pueden ser fábricas) a
varios destinos (centros de recepción, puntos de demanda, que pueden ser
bodegas, almacenes, etc.). El modelo de transporte también es un programa
lineal que se puede resolver por el método simplex, sin embargo hay un
procedimiento de solución, conocido como técnica de transporte, que es más
eficiente.
Este método se puede aplicar a otros problemas como el modelo de
asignación o el de trasbordo.
Como se menciona, el modelo de transporte busca determinar un plan de
transporte de una mercancía de varias fuentes a varios destinos. Los datos
que debe de contener el modelo son:
1) Un conjunto de m puntos de suministros, a partir de los cuales se envía un
bien. El punto de suministro i abastece una cantidad a lo sumo Si unidades.
2) Un conjunto n de puntos de demanda a los que se envía el bien. El punto
de demanda j debe recibir por lo menos dj unidades del bien enviado.
3) Cada unidad producida en el punto de suministro i y enviada al punto de
demanda j incurren un costo variable cij.
Aquí utilizaremos
xij = como el número de unidades enviadas del punto de suministro i al
punto de demanda j.
Así podemos definir que el la formula general para el método del transporte
es:
nj
j
ijij
mi
i
xc11
min
s.a.
UNIDAD II / ANÁLISIS DE REDES
- 42 -
nj
j
iij Sx1
)........3,2,1( mi
mi
i
iij dx1
)........3,2,1( nj
Como solo hay una mercancía, un destino puede recibir su demanda de una
o más fuentes.
En el conjunto de ecuaciones anteriores se puede notar que:
El objetivo es determinar la cantidad que se enviará de cada fuente a cada
destino tal que minimice el costo del transporte total.
El primer conjunto de restricciones indica que la suma de los envíos desde
una fuente, no puede ser mayor que su oferta.
La segunda restricción indica que la suma de los envíos a un destino debe
satisfacer su demanda.
Como solo hay una mercancía, un destino puede recibir su demanda de una
o más fuentes.
Si en el problema:
nj
j
j
mi
i
i dS11
Se dice que el problema es equilibrado.
Como Equilibrar Un Problema De Transporte
a) Si el suministro total excede a la demanda total, se equilibra, creando un
punto de demanda ficticio, el cual tendrá como valor de demanda, la cantidad
de suministro en exceso. El costo de los envíos, como no son reales, serán
cero; aunque se les puede asignar un costo de almacenaje.
b) Si el problema de transporte tiene un suministro total menor que la
demanda total, entonces se crea un punto de suministro ficticio, la cantidad
que produciría será igual a la cantidad faltante. El costo también será cero o
bien un costo de penalización por no cubrir la demanda.
Si algún punto de demanda, no puede, o no se quiere que envié a un punto
de demanda, se le asignara una penalización muy alta al costo del envió (M).
UNIDAD II / ANÁLISIS DE REDES
- 43 -
Tabla Simplex De Transporte.
Como se menciono anteriormente el problema de transporte es solo un tipo
especial de problemas de programación lineal, por lo tanto se puede resolver
aplicando el método simplex, como se hizo en la unidad anterior. Pero
debido que se tiene una estructura muy especial, se pueden ahorrar muchos
pasos, que casi eliminan a la tabla simplex y a sus actualizaciones. Para ello
se registra la información del problema en una tabla simplex del transporte
que tiene el siguiente formato general:
Recursos ui
c11 c12 c1n
c21 c22 c2n
cm1 cm2 cmn
vj
Informacion adicional que se agrega a cada celda:
cij cij
xij
dn
Si xij es una variable
basica
Si xij es una variable
no basica
cij - u i -v j
Demanda d1 d2 ……
……
……
……
m …… Sm
O
r
i
g
e
n
1 …… S1
2 …… S2
……
……
……
Destino
1 2 …… n
Solución Al Problema De Transporte
Los pasos para solucionar un problema de transporte son:
Paso 1.- Si el problema está desequilibrado, equilíbrelo.
Paso 2.- Encontrar una solución factible inicial, en este caso utilizando el
método de la esquina noroeste. Se utiliza la tabla de simplex de transporte
para resolver el problema.
Paso 3.- Haga que u1 = 0 y ui + vj = cij para todas las variables básicas con la
finalidad de encontrar [u1,u2…..um; v1, v2……vn] para la sfb (solución factible
inicial)
UNIDAD II / ANÁLISIS DE REDES
- 44 -
Paso 4.- Si ui + vj - cij≤0 para las variables no básicas, entonces las sfb actual
es óptima. Si éste no es el caso, entonces se introduce en la base la variable
con el valor positivo más grande de ui + vj –cij. Para hacer esto, encuentre el
bucle. Luego contando sólo las celdas de bucle, marque las celdas pares.
También marque las impares. Ahora encuentre la celda impar cuya variable
tome el valor más pequeño, θ. Los valores de las variables que no están el
bucle permanecen sin cambio. El pivote ahora está completo. Si θ=0,
entonces la variable entrante será igual a cero, y una variable impar que
tiene el valor actual de 0 saldrá de la base. En este caso resultará una sfb
degenerada. Si más de una celda impar del bucle es igual a θ, se podría
elegir de manera arbitraría que una de estas celdas impares salga de la
base; de nuevo, se obtiene un sfb degenerada. Este pivoteo produce una
nueva sfb.
Paso 5.- Usando la nueva sfb, vuelva a los pasos 3 y 4.
Si el problema es de maximización se siguen los mismos pasos, pero se
sustituye el paso 4 de la siguiente manera.
Paso 4’.- Si ui + vj – cij ≥ 0 para las variables no básicas, la sfb es óptima, de
otro modo introduzca una variable con le valor negativo más grande de ui + vj
– cij en la base por medio del procedimiento de pivoteo.
Para Encontrar Una Solución Factible Inicial. (Paso 2)
Para empezar a resolver el problema de transporte una vez colocado en la
tabla de transporte, se tiene que encontrar una solución factible inicial.
Existen 3 métodos conocidos, que son:
a) método de esquina noroeste
b) método de costo mínimo
c) método de Vogel.
UNIDAD II / ANÁLISIS DE REDES
- 45 -
Método De Esquina Noroeste.
Se comienza colocando en la esquina superior izquierda (noroeste) de la
tabla de transporte, el valor de x11, que será el valor más grande posible de
acuerdo al recurso disponible y la demanda.
Si el valor de x11 es igual al valor del suministro (x11= s1 ) ya no se le asignara
otra variable básica a el renglón 1 y el valor de la siguiente variable, se
colocara en el siguiente renglón pero misma columna y el valor tratara de
agotar a la demanda de la columna 1 (d1).
Si el valor de x11 es igual al valor de la demanda (x11= d1 ) ya no se le
asignara otra variable básica a la columna 1 y el valor de la siguiente
variable, se colocara en la siguiente columna pero misma renglón y el valor
tratara de agotar a le suministro del renglón 1 (s1).
Si x11= s1= d1 se puede anular ya sea la columna o el renglón eligiendo
arbitrariamente. Si se elimina el renglón 1 se pasa al renglón 2 y se coloca
con valor cero, y se continua con un valor en la siguiente columna. Si se
elimina la columna 1, se pasa a la siguiente columna y se le coloca el valor
de cero, y se continúa con un valor en el renglón siguiente.
EJEMPLO No 1.
Un empresario se dedica al ensamble y venta de computadoras, el puede
ensamblar en tres lugares diferentes y enviar estas computadoras a sus 4
puntos de ventas que tiene.
Para la próxima semana tiene llevar 5 computadoras al punto de venta No. 1,
15 al punto de venta No. 2, 15 al punto de venta No. 3, y 10 al punto de
venta No. 4.En donde ensambla tiene las siguientes computadoras, en el
lugar 1 tiene 15, en el lugar 2 tiene 25, y en el lugar 3 tiene 5.
El costo que tiene el transporte de cada computadora saliendo de las
diferentes ensambladoras para llegar a los diferentes destinos son:
UNIDAD II / ANÁLISIS DE REDES
- 46 -
DESTINO
ENS. 1 2 3 4
1 10 0 20 11
2 12 7 9 20
3 0 14 16 18
SOLUCION:
Utilizando la tabla simplex de transporte y colocándole los datos del
problema tenemos:
Recursos ui
10 0 20 11
12 7 9 20
0 14 16 18
vj
Destino
1 2 3 4
O
r
i
g
e
n
1 15
2 25
3 5
10Demanda 5 15 15
Paso 1. Se verifica y se obtiene que el suministro es igual a la demanda por
lo tanto el problema está equilibrado.
Paso 2. Se obtiene una solución factible inicial por el método de la esquina
noroeste. Quedando la tabla de la siguiente manera.
Recursos ui
10 0 20 11
5 10
12 7 9 20
5 15 5
0 14 16 18
5
vj
10Demanda 5 15 15
O
r
i
g
e
n
1 15
2 25
3 5
Destino
1 2 3 4
El costo total de esta solución básica es:
UNIDAD II / ANÁLISIS DE REDES
- 47 -
5(10)+10(0)+5(7)+15(9)+5(20)+5(18) = 410
Paso 3. Encontrando lo valores de las u y v tenemos que u1=0 y además de
las variables básicas tenemos:
x11 u1 + v1 = 10
x12 u1 + v2 = 0
x22 u2 + v2 = 7
x23 u2 + v3 = 9
x24 u2 + v4 = 20
x34 u3 + v4 = 18
Como sabemos que u1=0, entonces v1=10, v2=0,
u2=7, v3=2, v4=13 y u3=5
Paso 4. Evaluando ahora las variables no básicas tenemos:
x13 u1 + v3 – c13= 0 + 2 – 20 = -
18
x14 u1 + v4 – c14= 0 + 13
– 11 = 2
x21 u2 + v1 – c21= 7 + 10
– 12 = 5
x31 u3 + v1 – c31= 5 + 10
– 0 = 15
x32 u3 + v2 – c32= 5 + 0 –
14 = -9
x33 u3 + v3 – c33= 5 + 2 –
16 = -9
Como podemos observar la condición
de optimalidad nos dice el resultados
de las celdas no básicas tienen que
ser menor o igual a cero. Como se
observa esto no se cumple, por lo
tanto tenemos que iterar tomando la
variable no básica que entra, la que
tenga el mayor numero positivo en
este caso x31.
Ahora tenemos que ir a la tabla y encontrar la posición de x31 y construir el
bucle (ciclo cerrado) para encontrar que variable básica es la que sale.
UNIDAD II / ANÁLISIS DE REDES
- 48 -
Recursos ui
10 0 20 11
5 10
12 7 9 20
5 15 5
0 14 16 18
x31 5
vj
10Demanda 5 15 15
O
r
i
g
e
n
1 15
2 25
3 5
Destino
1 2 3 4
Como podemos observar un bucle se construye, empezando y terminando
en la variable básica que va a entrar, además las esquinas del bucle son solo
algunas de la variables básicas y son las que se tomaran en cuenta, las otras
no (en este caso la variable x23 es básica pero no se toma en cuenta es
decir, su valor mantiene igual). También conviene saber que para cualquier
conjunto de variables básicas, habrá siempre un solo bucle. Ahora en este
problemas las celdas impares son x11, x22, x34 y las celdas pares serian x12, x
24, y x31. Aquí no importa en que sentido se maneje el bucle. De las celdas
impares, se toma la que tenga el valor mas pequeño y esa será la que salga,
en este caso como las tres tienen el mismo valor puede salir cualquiera de
las tres, aquí se elige arbitrariamente. Digamos que sacamos a x34, ahora el
valor que tiene esta variable (5) la colocamos en la variable que entra x31 y
se calcula la nueva tabla:
Recursos ui
10 0 20 11
0 15 -18 2
12 7 9 20
5 0 15 10
0 14 16 18
5 -24 -24 -15
vj 10
0
7
-10
0 2 13
10Demanda 5 15 15
O
r
i
g
e
n
1 15
2 25
3 5
Destino
1 2 3 4
Como se puede observar, a las celdas impares se le resta el valor que entra
y a las pares se le suma. Como en este caso tenemos variables básicas igual
UNIDAD II / ANÁLISIS DE REDES
- 49 -
a 0, se dice que la solución es degenerada, pero no importa, se consideran
con ese valor y se sigue trabajando igual.
Se regresa al paso 3 y después otra vez se aplica el paso 4, si no se cumple
con la condición se vuelve a iterar hasta cumplir con la condición de
optimalidad.
Las siguientes tablas son:
Recursos ui
10 0 20 11
-5 5 -18 10
12 7 9 20
0 10 15 -2
0 14 16 18
5 -19 -19 -12
vj
Demanda 5 15 15
O
r
i
g
e
n
1 15
2 25
3 5
Destino
1 2 3 4
0
7
-5
5 0 2 11
10
La solución óptima se resume como enviar 5 computadoras de la
ensambladora 1 al punto de venta 2, y 10 al punto 4. Enviar 10
computadoras de la ensambladora 2, al punto de venta 2 y 15 al punto de
venta 3, y por ultimo enviar 5 computadoras de la ensambladora 3 al punto
de venta 1. Todo esto sale con un costo de transporte igual a:
5(0) + 10(11) + 10(7) + 15(9) + 5(0) = 315.
EJEMPLO No. 2
Recursos ui
10 0 20 11
-5 15 -18 2
12 7 9 20
0 0 15 10
0 14 16 18
5 -19 -19 -10
vj
0
7
-5
5 0 2 13
10Demanda 5 15 15
O
r
i
g
e
n
1 15
2 25
3 5
Destino
1 2 3 4
UNIDAD II / ANÁLISIS DE REDES
- 50 -
El gerente de una mueblería, requiere enviar los colchones que tiene en sus
tres bodegas, a las 5 sucursales que tiene. De acuerdo con el inventario
sabe que en bodega de Minatitlán cuenta con 20 colchones, en la de San
Andrés con 30 y la de Acayucan 30. Leyendo los informes sabe que en la
sucursal de de Hueyapan requieren 25 colchones, en la de San Pedro
Soteapan requieren 25, en Cosoleacaque 20, en Catemaco 10 y en la de
Coatzacoalcos 20. El costo de envío por cada colchón de las diferentes
bodegas a los destinos se resume en la siguiente tabla. Solo que la bodega
de San Andrés no puede entregar en San Pedro Soteapan.
H.
d
e
O.
San
Pedr
o
Cosoleacaqu
e
Catemac
o
Coatzacoalco
s
Minatitlá
n
8 6 3 7 5
San
Andrés
5 - 8 4 7
Acayuca
n
6 3 9 6 8
Encontrar el costo más bajo para transportarlos colchones.
Armando la tabla inicial tenemos:
Recursos ui
8 6 3 7 5
5 _ 8 4 7
6 3 9 6 8
vj
2010
Destino
H. DE O S. P. COSO. COATZA.CATE.
O
r
i
g
e
n
M
I
N
20
A
N
D
30
A
C
A
30
Demanda 25 25 20
UNIDAD II / ANÁLISIS DE REDES
- 51 -
Paso 1.- Al analizar el problema vemos que esta desequilibrado ya que la
demanda es de 100 colchones y los recursos solo hay 80, por lo tanto el
primer paso es equilibrar el problema, creando una fuente ficticia que surta
20 colchones que faltan, esta fuente ficticia tendrá costos igual a 0. Por otra
parte como no se puede surtir de la bodega de san Andrés a la mueblería de
San Pedro, se le coloca un costo muy alto M (penalizar con un valor muy alto
M). Por lo tanto la tabla inicial queda:
Recursos ui
8 6 3 7 5
5 M 8 4 7
6 3 9 6 8
0 0 0 0 0
vj
2010
Destino
H. DE O S. P. COSO. COATZA.CATE.
O
r
i
g
e
n
M
I
N
20
A
N
D
30
F
I
C
20
A
C
A
30
Demanda 25 25 20
Paso 2.- Aplicando el método de la esquina noroeste, la tabla queda:
Recursos ui
8 6 3 7 5
20
5 M 8 4 7
5 25
6 3 9 6 8
0 20 10
0 0 0 0 0
0 20
vj
2010
Destino
H. DE O S. P. COSO. COATZA.CATE.
O
r
i
g
e
n
M
I
N
20
A
N
D
30
F
I
C
20
A
C
A
30
Demanda 25 25 20
Paso 3.- Aplicando la prueba de optimalidad.
UNIDAD II / ANÁLISIS DE REDES
- 52 -
Recursos ui
8 6 3 7 5
20 M-3 M+6 M-1 M+1
5 M 8 4 7
5 25 M-2 M-1 M-4
6 3 9 6 8
-M+2 0 20 10 -2
0 0 0 0 0
-M-2 -3 3 0 20
vj
M
M-3
-6
-M+8 3 9 6
2010
6
Destino
H. DE O S. P. COSO. COATZA.CATE.
F
I
C
20
A
C
A
30 0
Demanda 25 25 20
O
r
i
g
e
n
M
I
N
20
A
N
D
30
Como se observa no se cumple con la prueba de optimalidad por lo tanto se
empieza iterar hasta cumplir con ella, por lo tanto tenemos las siguientes
tablas:
Recursos ui
8 6 3 7 5
0 M-3 20 M-1 M+1
5 M 8 4 7
25 5 -8 M-1 M-4
6 3 9 6 8
-M+2 20 -M-6 10 -8
0 0 0 0 0
-M+2 -3 -M-3 0 20
vj
-M+3
Demanda 25 25 20
O
r
i
g
e
n
M
I
N
20
A
N
D
30
F
I
C
20
A
C
A
30
Destino
H. DE O S. P. COSO. COATZA.CATE.
3
0
-M-3
5 M 0 M+3
2010
M+3
Recursos ui
8 6 3 7 5
M-1 -4 20 -2 0
5 M 8 4 7
25 5 M-7 M-1 M-4
6 3 9 6 8
-M+2 20 -5 10 -2
0 0 0 0 0
-M+2 -3 -2 0 20
vj
0
M-2
-5
-M+7 2 3 5
2010
5
Destino
H. DE O S. P. COSO. COATZA.CATE.
F
I
C
20
A
C
A
30 1
Demanda 25 25 20
O
r
i
g
e
n
M
I
N
20
A
N
D
30
UNIDAD II / ANÁLISIS DE REDES
- 53 -
Recursos ui
8 6 3 7 5
-2 -4 20 -2 0
5 M 8 4 7
25 -M+1 -6 5 -3
6 3 9 6 8
1 25 -5 5 -2
0 0 0 0 0
1 -3 -2 0 20
vj
0
-1
-5
6 2 3 5
2010
5
Destino
H. DE O S. P. COSO. COATZA.CATE.
F
I
C
20
A
C
A
30 1
Demanda 25 25 20
O
r
i
g
e
n
M
I
N
20
A
N
D
30
Recursos ui
8 6 3 7 5
-2 -3 20 -2 0
5 M 8 4 7
20 -M+2 -6 10 -3
6 3 9 6 8
5 25 -6 -1 -3
0 0 0 0 0
1 -2 -2 0 20
vj
0
-1
-5
6 3 3 5
2010
5
Destino
H. DE O S. P. COSO. COATZA.CATE.
F
I
C
20
A
C
A
30 0
Demanda 25 25 20
O
r
i
g
e
n
M
I
N
20
A
N
D
30
El mínimo costo que se obtiene es de:
(20)(3) + (20) (5) + (10) (4) + (5) (6) + (25) (3) = 305
Redes
Los problemas de redes surgen en un gran variedad de situaciones, por
ejemplo una red de transporte, redes eléctricas, de comunicación, etc. En la
vida diaria son muy comunes. Estas redes las podemos representar para
tener un panorama general y poder visualizar las relaciones existentes entre
Recursos ui
8 6 3 7 5
-3 -4 20 -3 0
5 M 8 4 7
20 -M+2 -5 10 -2
6 3 9 6 8
5 25 -5 -1 -2
0 0 0 0 0
0 -3 -2 -1 20
vj
0
0
-5
5 2 3 5
2010
4
Destino
H. DE O S. P. COSO. COATZA.CATE.
F
I
C
20
A
C
A
30 1
Demanda 25 25 20
O
r
i
g
e
n
M
I
N
20
A
N
D
30
UNIDAD II / ANÁLISIS DE REDES
- 54 -
los componentes de los sistemas de los sistemas que se usan en casi todas
áreas científicas, sociales y económicas.
La representación de una red se puede utilizar para la plantación de un
proyecto, administración de recursos, localización de instalaciones, áreas de
producción, de distribución, etc.
Terminología Básica Utilizadas En La Redes
Una red o grafica consiste en una serie de puntos y un conjunto de líneas
que unen a ciertos pares de puntos. Los puntos se llaman nodos (o vértices)
y las líneas arcos (aristas o ramas). Los nodos se pueden identificar
colocándole una letra mayúscula o bien por medio de números. Los arcos se
pueden nombrar de acuerdo de acuerdo a su nodo de origen y su nodo
Terminal. Por ejemplo en la siguiente red se tiene:
Los arcos de una red pueden tener flujo de algún tipo, por ejemplo personas,
agua, gas, aviones, etc. Por lo tanto estos arcos van a tener una dirección y
estará representado por la cabeza de flecha del arco. También el nombre del
arco indicara la dirección del flujo, por ejemplo el arco del la red anterior (2,5)
indica que sale del nodo 2 y va con dirección de flujo al nodo 5. Pero si este
mismo arco se representa (5,2) es incorrecto.
Si a través del arco se permite al flujo ir en una solo dirección, se dice que es
un arco dirigido, (algo similar a una calle de un solo sentido), pero si se
permite el flujo en ambos sentidos el arco será no dirigido. Si la red está
5 nodos y 6 arcos. Se tienen los nodos 1,2,3,4,5 Y a los arcos (1,2), (1,3), (2,5), ¿2,4), (3,4), y (5,4).
1
2
3 4
5
UNIDAD II / ANÁLISIS DE REDES
- 55 -
compuesta por puros arcos dirigidos se la llamara red dirigida, si la red está
compuesta por puros arcos no dirigidos se llamara red no dirigida.
Trayectoria entre 2 nodos es cuando 2 nodos están conectados por medio de
una sucesión de arcos distintos.
En el ejemplo anterior una trayectoria del nodo 1 al nodo 4 seria (1 2) (2 4).
Cuando la red tiene algunos o todos los arcos no dirigidos se pueden
distinguir entre trayectorias dirigidas y trayectorias no dirigidas. Una
trayectoria dirigida será una sucesión de arcos que van del nodo inicial al
final llevando siempre la dirección del nodo inicial al final. Una trayectoria no
dirigida del nodo inicia la al nodo final es la trayectoria que cuya dirección del
arco puede ser hacia o desde el nodo final.
Ejemplo de trayectoria dirigida seria del nodo 1 al nodo 4: (1 3) (3 2) (2 4) Ejemplo de trayectoria no dirigida seria del nodo 3 al nodo 5: (3 2) (2 4) (5 4)
Ciclo o bucle.- Es una trayectoria que comienza y termina en el mismo nodo.
2.2 Problema del camino más corto.
Este problema se presenta cuando necesitamos encontrar en un red la
distancia más corta entre un nodo fuente y llegar a un nodo destino. Esto
podría ocuparse en una red de transporte, para determinar la ruta mas corta
entre dos ciudades, o la ruta más corta para colocar algún cable de
comunicación o de energía eléctrica, etc.
Para resolver estos problemas podemos utilizar el siguiente algoritmo:
Digamos que:
dij = distancia de la red entre nodos adyacentes i y j.
uj = distancia más corta a un nodo i al nodo j
u1 = 0
1
2
3 4
5
UNIDAD II / ANÁLISIS DE REDES
- 56 -
uJ= min. (Distancia más corta a un nodo i inmediatamente
anterior mas la distancia entre el nodo actual j y su predecesor
i)
uJ= min. { uj + dij }
Ejemplo:
En un parque declarado reserva natural, se permite paseos y campamentos
pero no se permite el paso de vehículos, ya que el parque cuenta con jeep
ecológicos que transportan a la gente a las diferentes estaciones. La
siguiente red es una representación de los caminos dentro del parque y las
diferentes estaciones. El nodo 1 representa la entrada del parque, el nodo 7
representa el mirador principal del parque que ofrece una maravillosa vista,
los demás nodos son estaciones de servicios como cafeterías, baños, etc.
Un visitante llego al parque pero desea llegar lo más rápido posible al
mirador, ¿Cuál será la ruta más corta que pueda tomar el conductor del jeep?
Los números de los arcos indican la distancia en kilómetros entre los nodos.
Podemos hacer los cálculos siguientes: En el nodo 1 u1 = 0 Por ser el origen En el nodo 2: u2 = u1 + d12= 0 + 2 = 2 En el nodo 4: U4 = u1 + d14= 0 + 4 = 4 En el nodo 3: U3 = u1 + d13= 0 + 5 = 5
En el nodo 5: U5 = u2 + d25= 2 + 7 = 9 U5 = u3 + d35= 4 + 4 = 8 U5 = u6 + d65= 7 + 1 = 8 En el nodo 7: U7 = u5 + d57= 8 + 5 = 13
U7 = u6 + d67= 7 + 7 = 14 Por lo tanto la ruta mas corta es : (1 2)(2 3)(3 5)(5 7) y otra alternativa es (1 2)(2 3)(3 6)(6 5)(5 7)
1
2
5
7
3
4 6
UNIDAD II / ANÁLISIS DE REDES
- 57 -
U3 = u2 + d23= 2 + 2 = 4 U3 = u4 + d43= 4 + 1 = 5 En el nodo 6: U6 = u3 + d36= 4 + 3 = 7 U6 = u4 + d46= 4 + 4 = 8
Problema 2.- Un vendedor de refacciones tiene que entregar un pedido
dentro de la ciudad, al revisar los planos encuentra la posibles rutas que
puede tomar, el se encuentra en nodo 1 y el lugar donde entregara se
encuentra en el nodo 6.
¿Cuál es el camino más corto que podrá tomar?
Este tipo de problemas se puede resolver por medio de la tabla de transporte
haciendo algunas modificaciones:
Todos los valores de los suministros y demanda serán igual a 1. Por lo tanto
los valores de xij = 1 y 0.
El nodo fuente no se coloca en las columnas de la tabla.
Haciendo los cálculos: u1 = 0 u2 = u1+ d12= 0 + 4 = 4 u3 = u1+ d13= 0 + 3 = 3 u4 = u2+ d24= 4 + 3 = 7
u5 = u2+ d25= 4 + 2 = 6 u5 = u3+ d35= 3 + 3 = 6 u6 = u4+ d46= 7 + 2 = 9 u6 = u5+ d56= 6 + 2 = 8
Por lo tanto las opciones son: (1 2)(2 5)(5 6) o bien (1 3)(3 5)(5 6)
1
2
5 3
4
6
3
3
3
2
2
2 4
UNIDAD II / ANÁLISIS DE REDES
- 58 -
El nodo destino no se coloca en los renglones de la tabla.
En el cuadro de los costos ira la distancia entre los nodos.
Cuando se este enlazando el mismo nodo la distancia será 0.
Cuando no este enlazado un nodo con otro, se le da un valor de M.
Resolver la tabla hasta cumplir con la prueba de optimalidad.
Recursos ui
4 3 M M M
1 M+1 M+4 2M+4 2M+6
0 M 3 2 M
0 1 2M-3 3M-2 2M+2
M 0 M 3 M
-2M 0 1 2M-3 M+2
M M 0 M 2
-3M -2M 0 1 M
M M M 0 2
-4M -3M -2M 0 1
vj
1 -M
2M
Demanda 1 1 1
O
r
i
g
e
n
1
1
2
1
5
1
4
1
3
Destino
2 3 4 65
4
0
-3M
0 M 2M 3M+2
11
3M
Recursos ui
4 3 M M M
0 M 3 2 M
M 0 M 3 M
M M 0 M 2
M M M 0 2
vj
11
Destino
2 3 4 65
3
1
4
1
Demanda 1 1 1
O
r
i
g
e
n
1
1
2
1
5
1
UNIDAD II / ANÁLISIS DE REDES
- 59 -
Recursos ui
4 3 M M M
1 M+1 6 -2 -M
0 M 3 2 M
0 0 M-1 1 -M+4
M 0 M 3 M
0 1 -M+2 -M-1 -2M+4
M M 0 M 2
-2 M-2 1 0 M
M M M 0 2
-M-2 -2 0 0 1
vj
1 -M
M-2
Demanda 1 1 1
O
r
i
g
e
n
1
1
2
1
5
1
4
1
3
Destino
2 3 4 65
4
0
-2
0 M M+2 4
11
2
Recursos ui
4 3 M M M
1 0 -2M+6 -M+6 -M+4
0 M 3 2 M
0 -M-1 -M-1 1 -M
M 0 M 3 M
-M+1 1 -2M+3 0 -M+1
M M 0 M 2
-2 -3 1 0 M-4
M M M 0 2
-M-2 -M-3 -2M 0 1
vj
6
2
0
-2 -3 -M -2
11
0
Destino
2 3 4 65
2
1
5
1
4
1
3
1 3
M
Demanda 1 1 1
O
r
i
g
e
n
1
1
Recursos ui
4 3 M M M
1 0
0 M 3 2 M
0 -1 1
M 0 M 3 M
1 0
M M 0 M 2
1 0
M M M 0 2
0 1
vj
-3
-6
Demanda 1 1 1
O
r
i
g
e
n
1
1
2
1
5
1
4
1
3
1
Destino
2 3 4 65
0
-4
-6
4 3 6 8
11
6 Por lo tanto la ruta más corta es: 1-2-5-6
UNIDAD II / ANÁLISIS DE REDES
- 60 -
2.3.- Problema Del Árbol Expandido Mínimo.
Este problema tiene que ver con la determinación de los arcos que pueden
unir a todos los nodos de una red, para formar un árbol.
Un árbol de expansión (o de extensión) para una de red de n nodos, es un
grupo de n-1 arcos que conectan todos los nodos de la red y no contiene
ciclos (bucles).
Por ejemplo:
1
2
5 3
4
6
7
c)
1
2
5 3
4
6
7
b)
1
2
5 3
4
6
7
a)
UNIDAD II / ANÁLISIS DE REDES
- 61 -
En el inciso a) no se forma un árbol de expansión ya que no están
conectados todos los nodos, en un dado caso se podrían tomar como un
conjunto de dos árboles.
En el inciso b) no se forma un árbol ya que hay ciclos o bucles.
En el Inciso c) y d) si se forman árboles de expansión.
Como se observa se pueden construir diferentes formas de los árboles de
extensión, con un grupo de nodos, pero en el problema del árbol expandido
mínimo que nos interesa es determinar el conjunto de arcos de una red que
conecte todos lo nodos que minimice la suma de la longitud del total de los
arcos.
Algoritmo Para Determinar El Problema Del Árbol Expandido Mínimo.
1) Se selecciona de manera arbitraria cualquier nodo y se une con un arco al
nodo más cercano. Estos dos nodos forman ahora un conjunto conectado y
los otros nodos constituyen el conjunto de nodos no conectados
(desconectados).
2) Se identifica el nodo no conectado más cercano a un nodo conectado y se
conectan estos dos nodos (se agrega un arco). Este paso se repite hasta
conectar todo los arcos.
3) En caso de surgir empates, esto se rompe de manera arbitraria y el
algoritmo todavía lleva a una solución optima, estos empates significan que
pudieran existir (pero no necesariamente). Soluciones optimas múltiples.
Todas estas soluciones se pueden verificar si se buscan las demás formas
de romper el empate hasta el final.
1
2
5 3
4
6
7
d)
UNIDAD II / ANÁLISIS DE REDES
- 62 -
Por ejemplo:
La administración del parque de reserva natural, desea poner teléfonos en
todos las estaciones del parque, para calcular la longitud del cable necesitan
saber cuál es la ruta más corta que puede unir a todas las estaciones, ¿Cuál
es esa ruta y que distancia tendrá?
Esta es la red original del parque El primer paso es elegir cualesquiera de los nodos, en este caso empezaremos en el nodo 4. Este nodo 4 lo unimos con el nodo más cercano en este caso con el nodo 3, por lo tanto la nueva red queda:
Ahora ya tenemos conectados lo nodos 4 y 3 hay que buscar un nodo de los desconectado que este más cercano a estos nodos y resulta ser el nodo 2. Teniendo esto se conecta. Y resulta lo siguiente:
Siguiendo, ahora se conecta el nodo numero 1
El siguiente nodo en conectarse es el No. 6
1
2
5
7
3
4 6
7
2
7
5
4 1
4
3
4
1
5
2
1
2
5
7
3
4 6
7
2
7
5
4 1
4
3
4
1
5
2
1
2
5
7
3
4 6
7
2
7
5
4 1
4
3
4
1
5
2
UNIDAD II / ANÁLISIS DE REDES
- 63 -
Posteriormente el nodo 5.
Y por último el nodo 7. Quedando finalmente el árbol expandido mínimo:
El cual tiene una distancia de: 2+2+1+3+1+5 = 14 kilómetros.
2.4 Problema De Flujo Máximo.
Este problema se presenta cuando queremos enlazar un nodo fuente y un
nodo destino a través de una red de arcos, que pueden ser arcos dirigidos o
no dirigidos. Cada arco tiene una capacidad máxima de flujo permitida. El
objetivo es obtener la máxima cantidad de flujo entre la fuente y el destino.
1
2
5
7
3
4 6
7
2
7
5
4 1
4
3
4
1
5
2
1
2
5
7
3
4 6
7
2
7
5
4 1
4
3
4
1
5
2
1
2
5
7
3
4 6
7
2
7
5
4 1
4
3
4
1
5
2
1
2
5
7
3
4 6
7
2
7
5
4 1
4
3
4
1
5
2
UNIDAD II / ANÁLISIS DE REDES
- 64 -
Hay diferente caso por ejemplo, el de un número de refinerías que está
conectada a una red de distribución por medio de oleoductos. Estos
oleoductos conectan a las refinerías con unidades de bombeo que impulsan
el petróleo hasta terminales de distribución, el objetivo es maximizar el flujo
entre las refinerías y las terminales de distribución dentro de los límites de la
capacidad de las refinerías y los oleoductos. Esto mismo se puede llevar a
cabo con sistemas de agua, de trasporte aéreos etc.
Para resolver este problema se presenta el siguiente algoritmo que se
conoce como de etiquetas:
1) Se identifica una trayectoria dirigida del nodo origen al nodo destino en la
red, esta trayectoria deberá tener capacidad disponible. Si esta trayectoria no
existe entonces ya sea ha encontrado el flujo optimo.
2) Identificar cual es nodo fuente y etiquetarlo poniéndole un que tiene un
flujo ilimitado y no tendrá un nodo que lo precede ya que es el origen. Una
etiqueta para los nodos va a tener dos elementos, [ f , n ], donde f representa
el flujo que se puede asegurar que proviene del nodo n, así que para el nodo
fuente la etiqueta será [∞ , - ], para todos lo demás nodos se ira colocando [ f
, n]. Se identifican los nodos de la trayectoria encontrada el paso 1.
3) Identificar cual es la mínima capacidad que se puede transportar por esa
primer trayectoria encontrada. Se actualiza la capacidad de la red
colocándole etiquetas a los arcos que forman la trayectoria encontrada, en
los cuales se aumentara ese flujo mínimo que se identifico. Las etiquetas que
se le colocan a los arcos deben contener dos elementos, ( fo , fm), donde fo
es el flujo ocupado y fm el flujo máximo que puede pasar por ese arco. Por
lógica cuando fo es igual a fm, ya el arco no tiene capacidad de transportar
más flujo.
4) Regresar al paso 1.
Si en la red existen arcos que permiten el flujo en dos sentidos (no dirigidos)
estos se pueden representar como dos arcos dirigidos con sentidos
opuestos.
UNIDAD II / ANÁLISIS DE REDES
- 65 -
Ejemplo: El mismo parque de reserva natural se pretende cambiar los jeep
por tranvías, solo que para cuidar ciertas áreas solo se permitirá cierto
número de viajes diarios por algunos caminos. Ahora los números de la red
siguiente son los viajes máximos que se pueden permitir de cada estación a
cada estación del parque, pero el hay dos arcos que son no dirigidos los
arcos (2 3) y (5 6). Encuentre cual es el flujo máximo diario de trenes que
puede salir de la entrada y llegar hasta el mirador.
Primero como en lo nodos (2 3) y (5 6) son no dirigidos, se reemplazan por 2 arcos dirigidos en sentidos opuestos. SOLUCION:
Como podemos observar, podemos tener un trayectoria (1 2) (2 5) (5 7) que llega desde la fuente hasta el destino, como es la primera vez que pasamos, sus capacidades están sin ocupar, entonces a los nodos los etiquetamos quedando de la siguiente manera. Leyendo estas etiquetas nos damos cuenta que el flujo mínimo es el que llega al nodo 5 proveniente del nodo 2, el cual tiene una capacidad máxima de 3, esta capacidad se le sumara a los arcos por donde pasa esta trayectoria y se le pondrá su etiqueta a los arcos. Quedando:
1
2
5
7
3
4 6
6
1
3
7
4 2
4
5
4
1
9
5
[ ∞-]
_
[5 1]
[3 2]
[9 5]
1
1
1
2
5
7
3
4 6
6
1
3
7
4 2
4
5
4
1
9
5
UNIDAD II / ANÁLISIS DE REDES
- 66 -
Ya se encontró la primera, primera trayectoria y ya está etiquetada ahora hay que encontrar otra trayectoria que vaya del origen hasta el destino, podría ser por ejemplo: (3 5) (2 3) (3 5) (5 7), tomado esta trayectoria como base, colocamos las etiquetas en los nodos:
Como se observa las etiquetas de los nodos solo contienen el flujo disponible aun en los arcos de la trayectoria, se busca el flujo mínimo y encontramos que es 1, ahora actualizando la red quedara:
De nuevo se vuelve a buscar otra trayectoria en este caso puede ser (1 3) (3 5) (5 7) y volvemos a colocar las etiquetas de los nodos:
Ahora se observa que el menor flujo es de 3, por lo tanto actualizando la red queda:
La siguiente ruta podría ser (1 3) (3 6) (6 5) (5 7) colocando de nuevo las etiquetas en los nodos, tenemos:
[∞ -]
_
1
2
5
7
3
4 6
6 4 2 5
4
1 1
1 (4,5)
(3,3)
(7,9)
(1,1)
(4,4) (3,7)
1
2
5
7
3
4 6
6
7
4 2 5
4
1
[∞ -]
_ 1
1 (4,5)
(3,3)
(4,9)
(1,1)
(1,4) [7,1] [3,3]
[5,5]
1
2
5
7
3
4 6
6
7
4 2 5
4
1
[∞ -]
_ 1
1 (4,5)
(3,3)
(4,9)
(1,1)
(1,4)
1
2
5
7
3
4 6
6
1
7
4 2
4
5
4
1
[∞ -]
_ 1
1 (3,5)
(3,3)
(3,9)
[2,1]
[1,2] [4,3]
[6,5]
1
2
5
7
3
4 6
6
1
7
4 2
4
5
4
1
[∞ -]
_ 1
1 (3,5)
(3,3)
(3,9)
UNIDAD II / ANÁLISIS DE REDES
- 67 -
De nuevo se observa que el menor es 1, por lo tanto al hacer la actualización de la red queda:
Buscando una nueva ruta podría ser (1 3) (3 6) (6 7) se etiqueta de nuevo los nodos y se tiene lo siguiente:
Ahora el menor flujo que podría pasar es 3 por lo tanto la nueva red queda:
Buscando una nueva trayectoria podría ser (1 4) (4 6) (6 7) y etiquetando los nodos quedaría:
Ahora se observa que el flujo máximo permitido es de 3 por lo tanto la red queda: [∞ -]
_
1
2
5
7
3
4 6
4 2
4
1
1 (4,5)
(3,3)
(8,9)
(1,1)
(4,4) (7,7)
(4,5) (1,1)
(3,6)
[4,1] [4,4]
[3,6]
[∞ -]
_
1
2
5
7
3
4 6
4 2
4
1
1 (4,5)
(3,3)
(8,9)
(1,1)
(4,4) (7,7)
(4,5) (1,1)
(3,6)
[3,1]
[∞ -]
_
1
2
5
7
3
4 6
6 4 2
4
1
1 (4,5)
(3,3)
(8,9)
(1,1)
(4,4) (4,7)
(1,5) (1,1)
[4,3]
[6,6]
[∞ -]
_
1
2
5
7
3
4 6
6 4 2
4
1
1 (4,5)
(3,3)
(8,9)
(1,1)
(4,4) (4,7)
(1,5) (1,1)
[∞ -]
_
1
2
5
7
3
4 6
6 4 2 5
4
1 1
1 (4,5)
(3,3)
(7,9)
(1,1)
(4,4) (3,7)
[4,1]
[5,3]
[1,6]
[2,5]
UNIDAD II / ANÁLISIS DE REDES
- 68 -
Si tratamos de armar alguna otra trayectoria vemos que ya no es posible por lo tanto podemos decir que el flujo máximo que llega desde el nodo entrada hasta el nodo del mirador es de 14 viajes diarios.
Teorema del flujo máximo-corte mínimo
Como podemos observar pudimos haber tomado cualquier trayectoria pero al
final tenemos que comprobar si ya no hay mas trayectorias disponibles, una
forma de hacer esta comprobación es aplicando un corte mínimo en la red.
Un corte mínimo en la red es definir a un conjunto de arcos de tal manera
cuando tengan un flujo de cero, el flujo del nodo origen al nodo destino será
cero. La capacidad de un corte mínimo será suma de las capacidades de los
arcos.
Por ejemplo en la red anterior:
Conjunto de arcos que se cortan: Capacidad de corte:
(1 2 ) (1 3 ) ( 1 4 ) 5 + 7 + 4 = 16 ( 5 7 ) ( 6 7 ) 9 + 6 = 15 ( 2 5 ) ( 3 5 ) ( 3 6 ) ( 4 6 ) 3 + 4 + 5 + 4 = 16 ( 2 5 ) ( 3 5 ) ( 6 5 ) ( 6 7 ) 3 + 4 + 1 + 6 = 14
Son algunos de los cortes que podemos hacer, aquí nos damos cuenta que
el flujo mínimo de corte es igual a 14, por lo tanto ese es el flujo máximo que
pude pasar del nodo origen al nodo destino, por lo tanto la trayectorias
encontradas en la resolución del problemas son las optimas.
2.5 RUTA CRÍTICA (CPM-PERT)
Los modelos de red se pueden utilizar como una ayuda en la programación
de proyectos complejos de gran tamaño que consiste en muchas actividades.
Un proyecto define a una combinación de actividades interrelacionadas que
deben ejecutarse en un cierto orden antes de que el trabajo completo pueda
[∞ -]
_
1
2
5
7
3
4 6
2 1
1 (4,5)
(3,3)
(8,9)
(1,1)
(4,4) (7,7)
(4,5) (1,1)
(6,6) (3,4)
(3,4)
UNIDAD II / ANÁLISIS DE REDES
- 69 -
terminarse. Las actividades están interrelacionadas en una secuencia lógica,
ya que algunas de ellas no pueden comenzar hasta que otras hayan
terminado.
Una actividad en un proyecto, es un trabajo que requiere tiempo y recursos
para su terminación.
Para una buena administración de proyectos a gran escala, requiere de 3
fases básicas: plantación, programación y control.
Planeación.- Se inicia descomponiendo el proyecto en actividades distintas,
se tiene que estimar un tiempo para las actividades y se construye un
diagrama de red donde los arcos representan una actividad. Este diagrama
da la representación gráfica de las interdependencias entre las actividades
del proyecto; esto permite estudiar los diferentes trabajos a detalle e incluso
sugerir mejoras antes de ejecutar el proyecto, además será la base para el
desarrollo de la programación del mismo.
Programación.- Se construye un diagrama de tiempo que muestre los
tiempos de inicio y termino de cada actividad así como la relación con las
otras actividades. Además en el programa se debe señalar las actividades
criticas (en función del tiempo) para terminar el proyecto a tiempo. Para las
actividades no críticas, el programa debe de mostrar los tiempos de holgura
que pueden utilizarse cuando se demora esas actividades o cuando usar
eficientemente los recursos limitados.
Control.- Es la fase final de la administración. Utiliza el diagrama de red y el
diagrama de tiempo para hacer reportes periódicos del proyecto. La red debe
actualizarse, analizarse y en caso de ser necesario determinar un nuevo
programa para la porción restante del proyecto.
Existen en la actualidad dos técnicas comúnmente empleadas para estos
casos: CPM, PERT.
CPM (Método de la ruta crítica) que se aplica cuando:
a) La duración de cada actividad se conoce con certeza. Esto a veces,
basándose en la experiencia.
UNIDAD II / ANÁLISIS DE REDES
- 70 -
b) Cuando el tiempo se puede ajustar con facilidad.
c) Cuando es importante planear una combinación apropiada entre el tiempo
y el costo del proyecto.
Ejemplos de estos tipos de proyectos son los de construcción y
mantenimiento.
PERT (Técnica de evaluación y revisión de proyectos) que se aplica cuando:
a) Se utiliza para estimar la probabilidad de que el proyecto se complete en
fechas específicas. Debido a que hay mucha incertidumbre.
b) Y cuando es importante controlar de una manera efectiva la programación
del proyecto.
Ejemplos de estos tipos de proyectos son los de investigación y desarrollo.
Para aplicar CPM y PERT, se necesita una lista de actividades que
conformen el producto. Además se considera que el proyecto esta completo,
cuando se hayan terminado todas las actividades.
Para construir una red de de actividades interrelacionadas, las actividades se
representaran por los arcos de la red, y la punta de la flecha indicara el
avance del proyecto. Los nodos se utilizan para representar a los eventos, un
evento representa un punto en el tiempo y significa la terminación de algunas
actividades y el comienzo de otras. Las actividades un cierto evento no
pueden comenzar hasta que hasta que las actividades que concluyen en el
mismo evento hayan terminado. La longitud del arco no necesita ser
proporcional a la duración de la actividad ni tiene que dibujarse en línea
recta.
Reglas para la construcción de un diagrama de proyecto o red de
proyecto
1) El nodo No. 1 representa el comienzo del proyecto. El arco llevar desde el
nodo 1 para representar cada actividad que no tiene predecesores.
2) Se debe incluir en la red un nodo que represente la terminación del
proyecto, el nodo terminación que tendrá el número más grande de todos los
nodos.
UNIDAD II / ANÁLISIS DE REDES
- 71 -
3) Se deben numerar los nodos de la red de modo que el nodo que
representa la terminación de una actividad, tenga siempre, un número más
grande que el nodo que representa el comienzo de esta actividad.
4) Cada actividad está representada por un y sólo un arco en la red. Es decir
ninguna actividad puede representarse pede representarse dos veces en la
red. Aunque si se puede descomponer una actividad en segmentos, y cada
segmento estará representada por un arco. Por ejemplo en el tendido de una
tubería.
5) Dos nodos (eventos) no pueden estar conectados por mas de un arco,
esto puede surgir cuando dos actividades se tiene que ejecutar
simultáneamente.
6) Para asegurar correcta relación de procedencia correcta en el diagrama,
antes de agregar una actividad a la red se pueden contestar las siguientes
preguntas.
a) ¿Qué actividades deben terminarse inmediatamente antes de que esta
actividad pueda comenzar?
b) ¿Qué actividades deben de seguir a esta actividad?
c) ¿Qué actividades deben efectuarse con esta actividad?
Para no violar las reglas 4 y 5, se pueden utilizar una actividad ficticia,
representado por un arco ficticio (punteado), que no consume tiempo ni
recursos.
Ejemplo de una red de proyecto.
Red de proyecto para construir una casa.
La siguiente es una lista de actividades que hay que realizar para la
construcción de una casa.
UNIDAD II / ANÁLISIS DE REDES
- 72 -
ACTIVIDAD DESCRIPCION PREDECESORES INMEDIATOS
DURACION (DIAS)
A Excavación -------------- 2
B Cimientos A 4
C Obra negra B 10
D Colado de techo C 6
E Plomería exterior C 4
F Instalación eléctrica C 7
G Plomería interior E 5
H Recubrimiento externo D 7
I Recubrimiento interno F, G 8
J Pintura exterior E, H 9
K Colocación de piso I 4
L Pintura interior I 5
M Acabado exterior J 2
N Acabado interior K, L 6
A partir de esta lista elaboramos la red del proyecto, quedando de la siguiente manera:
1
2
5
3
4
7
9
11 12
6
8
10
13
Inicio
Terminación
A
B
C
D
E
F
G
H
I
J
K L
M
N
UNIDAD II / ANÁLISIS DE REDES
- 73 -
La aplicación del CPM-PERT es para crear un programa especificando la
fecha de inicio y termino de cada actividad. Debido a las interacciones de las
diferentes actividades, la determinación de estos tiempos requiere de
cálculos y como resultado final se tendrán actividades criticas y actividades
no criticas.
Actividad critica.- Es una actividad que si se demora en su comienzo causara
una demora en la terminación del proyecto completo, se dice que estas
actividades tiene un tiempo libre (holgura) igual a cero.
Actividad no critica.- Es aquella en que el tiempo entre su comienzo mas
próximo y de su terminación más tardío (como lo permita el proyecto) es mas
grande que su duración real, entonces se dice que se tiene holgura.
Determinación De La Ruta Crítica Por Medio De CPM
La ruta crítica es una cadena de actividades críticas, las cuales conectan al
evento inicial y final del diagrama del proyecto. Los paso para calcular esta
ruta son:
1) Se calculan los tiempo más próximos de cada evento (tiempo de inicio
más próximo TIPi) es el tiempo estimado en que ocurrirá el evento si las
actividades que lo preceden comienzan lo más pronto posible.
Esto se empieza a calcular desde el nodo inicio y se va moviendo hacia el
nodo de terminación.
TIPi=i
MAX [ TIPi + Dij ] Dij = Duración de la actividad ij
2) Se calcula el tiempo más lejano para un evento, es el último momento
estimado en que pueda ocurrir sin retrasar la terminación de un proyecto más
UNIDAD II / ANÁLISIS DE REDES
- 74 -
allá de su tiempo más próximo. (Tiempo de terminación más tardío TTT)
TTTi=j
MIN [ TTTj - Dij ]
Para realizar estos cálculos se comienza desde el nodo Terminal y mueve
hacia el inicio.
3) Se calculan las holguras totales (HT) para cada una de las actividades,
que es la diferencia entre el máximo tiempo disponible para realizar la
actividad y su duración. En otras palabras es el tiempo que se puede retrasar
la actividad sin retrasar la terminación del proyecto.
HTIJ= TTTj - TIPi - Dij
Todas las actividades que tengan una holgura total igual a cero son
actividades críticas.
4) Se calculan las holguras libres para cada actividad (HL), que es el exceso
de tiempo disponible sobre la duración de la actividad. Es el tiempo que se
puede retrasar una actividad, sin retrasar el comienzo de otra actividad
posterior.
HLij = TIPj – TIPi - Dij
Ejemplo 1.- Con el ejemplo de la construcción de la casa, calcularemos la
ruta crítica para este proyecto. Primero colocamos los días en la red del
proyecto de acuerdo a las actividades.
UNIDAD II / ANÁLISIS DE REDES
- 75 -
Primero calculamos los tiempos más próximos para los eventos.
Los cálculos se pueden hacer directamente en la red o bien formando una
tabla como la siguiente:
1
2
5
3
4
7
9
11 12
6
8
10
13
Inicio
Terminación
2
4
10
6
4
7
5
7
8
9
4 5
2
6
UNIDAD II / ANÁLISIS DE REDES
- 76 -
TIPi=i
MAX [ TIPi + Dij ]
Evento Evento
inmediato anterior
Tiempo más próximo
+ Tiempo de la
actividad =
Tiempo máximo más
próximo
1 - - + - = - 0
2 1 0 + 2 = 2 2
3 2 2 + 4 = 6 6
4 3 6 + 10 = 16 16
5 4 16 + 4 = 20 20
6 4 16 + 6 = 22 22
7 4 16 + 7 = 23
25 5 20 + 5 = 25
8 5 20 + 0 = 20
29 6 22 + 7 = 29
9 7 25 + 8 = 33 33
10 8 29 + 9 = 38 38
11 9 33 + 4 = 37 37
12 9 33 + 5 = 38
38 11 37 + 0 = 37
13 10 38 + 2 = 40
44 12 38 + 6 = 44
Ahora haciendo los cálculos más lejanos para los eventos tenemos:
TTTi=j
MIN [ TTTj - Dij ]
Evento Evento
inmediato anterior
Tiempo más lejano
- Tiempo de la
actividad =
Tiempo mínimo mas lejano
13 - - - - = 0 44
12 13 44 - 6 = 38 38
11 12 38 - 0 = 38 38
10 13 44 - 2 = 42 42
9 12 38 - 5 = 33
33 11 38 - 4 = 34
8 10 42 - 9 = 33 33
7 9 33 - 8 = 25 25
6 8 33 - 7 = 26 26
5 8 33 - 0 = 33
20 7 25 - 5 = 20
4
7 25 - 7 = 18
16 6 26 - 6 = 20
5 20 - 4 = 16
3 4 16 - 10 = 6 6
2 3 6 - 4 = 2 2
1 2 2 - 2 = 0 0
Calculando las holguras totales y holguras libres de las actividades tenemos:
UNIDAD II / ANÁLISIS DE REDES
- 77 -
Actividad Holgura total
HTIJ= TTTj - TIPi - Dij Holgura libre
HLij = TIPj – TIPi - Dij
1 – 2 2 - 0 - 2 = 0 2 - 0 - 2 = 0 Actividad critica
2 – 3 6 - 2 - 4 = 0 6 - 2 - 4 = 0 Actividad critica
3 – 4 16 - 6 -10 = 0 16 - 6 - 10 = 0 Actividad critica
4 – 5 20 - 16 - 4 = 0 20 - 16 - 4 = 0 Actividad critica
4 – 6 26 - 16 - 6 = 4 22 - 16 - 6 = 0
4 – 7 25 - 16 - 7 = 2 25 - 16 - 7 = 2
5 – 7 25 - 20 - 5 = 0 25 - 20 - 5 = 0 Actividad critica
5 – 8 33 - 20 - 0 = 13 29 - 20 - 0 = 9
6 – 8 33 - 22 - 7 = 4 29 - 22 - 7 = 0
7 – 9 33 - 25 - 8 = 0 33 - 25 - 8 = 0 Actividad critica
8 – 10 42 - 29 - 9 = 4 38 - 29 - 9 = 0
9 – 11 38 - 33 - 4 = 1 37 - 33 - 4 = 0
9 – 12 38 - 33 - 5 = 0 38 - 33 - 5 = 0 Actividad critica
10 – 13 44 - 38 - 2 = 4 44 - 38 - 2 = 4
11 – 12 38 - 37 - 0 = 1 38 - 37 - 0 = 1
12 – 13 44 - 38 - 6 = 0 44 - 38 - 6 = 0 Actividad critica
Si deseamos armar la programación lineal de este problema tendríamos:
Min. z = X13 - X1
S.A.
X2 ≥ X1 + 2
X3 ≥ X2 + 4
X4 ≥ X3 + 10
X5 ≥ X4 + 4
X6 ≥ X4 + 6
X7 ≥ X5 + 5
X7 ≥ X4 + 7
X8 ≥ X6 + 7
X8 ≥ X5
X9 ≥ X7 + 8
X10 ≥ X8 + 9
X11 ≥ X9 + 4
X12 ≥ X9 + 5
X12 ≥ X11
UNIDAD II / ANÁLISIS DE REDES
- 78 -
X13 ≥ X10 + 2
X13 ≥ X12 + 6
X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13 ≥ 0
Determinación De La Ruta Crítica Por Medio De PERT
Como se menciono anteriormente CPM supone que la duración de cada
actividad se conoce con certeza. Pero para muchos proyectos esto no es
aplicable, entonces se ocupa el PERT, para corregir estas deficiencias.
Ahora el PERT requiere que se estimen las tres cantidades siguientes para
cada actividad:
a = Tiempo optimista, el cual se necesita si la ejecución va
extremadamente bien.
b = Tiempo pesimista, el que se requerirá si todo va muy mal.
c = Tiempo más probable, el cual se necesitara si la ejecución
es normal.
A partir de esto se construye la ruta crítica mediante el siguiente proceso:
1) Calcular la media para la duración del tiempo de cada actividad (D) y su
varianza (V) (distribución beta):
6
4mbaD
22
36
)(
6
ababV
2) Con los valores de D se construye la ruta crítica como si fuera en CPM.
Nada más que ahora la suma de la duración de las actividades de la ruta
crítica será el valor de la duración esperada de las actividades, y se sumara
todas las varianzas de las actividades de la ruta crítica para que sea a
varianza de la duración de actividades.
E = Duración esperada de las actividades de la ruta critica.
Var.= Varianza de la duración de la actividades de la ruta critica.
CP = desviación estándar de la ruta critica = (Var.)1/2
Con estos datos se pueden calcular las probabilidades de terminar en ciertos
días, tomando estos datos y utilizando las tablas de distribución normal.
UNIDAD II / ANÁLISIS DE REDES
- 79 -
EJEMPLO 2.- Una constructora naviera, necesita fabricar un nuevo tipo de
embarcación pequeña, se tiene contemplado construir la armazón y el motor
propulsor por separado, y al final ensamblar los dos componentes para
terminar la fabricación, en resumen las actividades que se harán son:
Actividad Descripción Act. Precedente Duración
a b m
A Capacitar trabajadores - 2 10 6
B Comprar materiales - 5 13 9
C Construir armazón A, B 3 13 8
D Armado del motor propulsor A, B 1 13 7
E Pruebas al motor D 8 12 10
F Ensamble del motor en la armazón.
C, E 9 15 12
Calcular la ruta critica por medio del PERT.
Calculando el tiempo para cada actividad y su varianza tenemos:
Actividad D Var.
A 66
)6(4102D 78.1
36
)210(2
V
B 96
)9(4135D 78.1
36
)513(2
V
C 86
)8(4133D 78.2
36
)313(2
V
D 76
)7(4131D 0.4
36
)113(2
V
E 106
)10(4128D 44.0
36
)812(2
V
F 126
)12(4159D 0.1
36
)915(2
V
Haciendo la red del proyecto, queda:
UNIDAD II / ANÁLISIS DE REDES
- 80 -
Calculando tiempo más próximo:
Evento Evento
inmediato anterior
Tiempo más próximo
+ Tiempo de la
actividad =
Tiempo máximo más
próximo
1 - - + - = - 0
2 1 0 + 9 = 9 9
3 1 0 + 6 = 6
9 2 9 + 0 = 9
4 2 9 + 3 = 12
16 3 9 + 7 = 16
5 3 9 + 8 = 17
26 4 16 + 10 = 26
6 5 26 + 12 = 38 38
Calculando el tiempo más lejano:
Evento Evento
inmediato anterior
Tiempo más lejano
- Tiempo de la
actividad =
Tiempo mínimo mas lejano
6 - - - - = 38
5 6 38 - 12 = 26 26
4 5 26 - 10 = 16 16
3 4 16 - 7 = 9
9 5 26 - 8 = 17
2 3 9 - 0 = 9
9 4 16 - 3 = 13
1 2 9 - 9 = 0
0 3 9 - 6 = 3
Calculando las holguras totales:
Actividad Holgura total
HTIJ= TTTj - TIPi - Dij D V
1 – 2 9 - 0 - 9 = 0 Act. Critica 9 1.78
1 – 3 9 - 0 - 6 = 3
2 – 3 9 - 9 - 0 = 0 Act. Critica 0 0
2 – 4 16 - 9 - 3 = 4
3 – 4 16 - 9 - 7 = 0 Act. Critica 7 4.0
1
3
4 2
5 6 8
3
9
7 10
12
6
UNIDAD II / ANÁLISIS DE REDES
- 81 -
3 – 5 26 - 9 - 8 = 9
4 – 5 26 - 16 - 10 = 0 Act. Critica 10 0.44
5 – 6 38 - 26 - 12 = 0 Act. Critica 12 1.00
E = 38
Var. = 7.22
Como se observa la duración media en que se realizara el proyecto es de 38
días.
Con una variación de 7.22
Con una desviación estándar = (7.22)1/2 = 2.69
A partir de aquí podemos calcular las probabilidades de realizar el trabajo en
un determinado tiempo, por ejemplo, calcular la probabilidad de que el
proyecto se complete máximo en 35 días.
P(x≤35) = 13.0)12.1(69.2
3835zpzp
UNIDAD 3
PROGRAMACIÓN NO LINEAL
Objetivo: Identificará y resolverá modelos con
comportamiento no lineal utilizando
problemas propuestos.
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 83 -
3.1 Planteamiento de problemas de Programación no lineal.
La programación Lineal es un tema importante en investigación de
operaciones, donde todas sus funciones (las de objetivo y restricción) son
lineales. Esto se cumple en muchos casos pero a veces es necesario
manejar problemas de programación no lineal.
De manera general la programación no lineal Consiste en encontrar
x = (x1, x2, x3,…..,xn) para:
Maximizar f(x)
Sujeta a: gi(x)≤bi ,,, para i = 1,2,….,m
y
x≥0
Donde f(x) y g(x) son funciones dadas de n variables de decisión.
Existen tipos diferentes de problemas de programación no lineal, lo cual
depende de las características de las funciones f(x) y g(x). Se emplean varios
algoritmos para los diferentes tipos de problemas. Para ciertos tipos donde
las funciones tienen formas simples, los problemas pueden resolverse de
manera relativamente eficiente. En algunos tipos incluso la solución de
pequeños problemas representa un gran reto.
Los problemas de programación no lineal se presentan en muchos formas
distintas, al contrario del método simplex para programación lineal no se
dispones de un algoritmo que resuelva todos estos tipos especiales de
problemas. Se han desarrollado algoritmos para algunas clases de
problemas de programación no lineal.
3.2 Optimización clásica.
Optimización clásica
Si la restricción no existe, o es una restricción de igualdad, con menor o igual
número de variables que la función objetivo entonces, el cálculo diferencial,
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 84 -
da la respuesta, ya que solo se trata de buscar los valores extremos de una
función.
3.2.1 Puntos de inflexión.
Un punto de la gráfica de una función en donde hay un cambio en la
concavidad de la gráfica se llama punto de inflexión
3.2.2 Máximos y mínimos
Una función puede contener varios máximos y mínimos, identificados por los
puntos extremos de la función. En la figura se puede observar esto, los
puntos x1, x3 y x6 son máximos, de la figura notamos que f(x6) es el mayor
que f(x1) y f(x3), a este punto se le conoce como máximo global de la función
y a los restantes como máximos locales. Lo mismo se puede ver para los
mínimos, en los que también existe un mínimo global f(x2) y un mínimo local
f(x4). Como es de lógico, solo puede existir un solo global y posiblemente
varios locales.
Representación de máximos y mínimos en una función con una sola variable
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 85 -
La derivada puede utilizarse para determinar los puntos donde la tangente es
horizontal (derivada = 0).
Extremos Relativos
Definición:
La función f se dice que tiene un valor máximo relativo en “c”, si existe un
intervalo abierto que contenga a “c” sobre el cual está definida la función f tal
que f (c) ≥ f (x) para toda x en este intervalo.
La función f se dice que tiene un valor mínimo relativo en “c”, si existe un
intervalo abierto que contenga a “c” sobre el cual f está definido tal que f (c) ≤
f (x) para toda x en este intervalo.
¿Dónde Localizar los Posibles Valores Extremos?
Teorema: Si f (x) existe para todos los valores de x en el intervalo abierto
(a,b) y si f tiene un extremo relativo en “c”, donde a c b , entonces f '(c)
existe y f ' (c) = 0.
Si f es una función diferenciable, los únicos lugares posibles para puntos
extremos es donde f ' (x) = 0.
Sin embargo, f ' (x) puede ser cero y no obstante en ese valor f no tiene un
valor extremo (Punto de Silla).
Más aún f puede tener un extremo relativo en un número y f’ puede no existir
allí.
En resumen:
Si una función está definida en un número “c” es una condición necesaria,
pero no suficiente, para que f tenga un extremo relativo en “c” que f ' (c) = 0 ó
que f '(c) no exista.
Si c es un número en el dominio de la función f y si f ' (c) = 0 ó f ' (c) no
existe, entonces “c” se llama número crítico de f.
Extremos Absolutos
Frecuentemente estamos en una función definida en un intervalo dado, y
deseamos encontrar el valor mayor o menor de la función en el intervalo.
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 86 -
Estos intervalos pueden ser cerrados, abiertos o cerrados a un extremo y
abierto en otro.
El valor máximo absoluto es el mayor valor dentro del intervalo, y el valor
mínimo absoluto es el mínimo valor de la función dentro del intervalo.
Extremos Absolutos en un Intervalo
Definición: La función f se dice que tiene un valor máximo absoluto en un
intervalo, si existe algún número “c” en el intervalo tal que f (c) f (x) para toda
x en el intervalo. En tal caso f (c) es el valor máximo absoluto de f en el
intervalo.
Definición: La función f se dice que tiene un valor mínimo absoluto en un
intervalo si existe algún número “c” en el intervalo tal que f (c) f (x) para toda
x en el intervalo. En tal caso f (c) es el valor mínimo absoluto de f en el
intervalo.
Valor extremo absoluto es un mínimo o máximo absoluto de la función en el
intervalo.
También se puede hablar de extremo absoluto de una función cuando no se
especifica ningún intervalo.
Definición: Se dice que f (c) es el extremo máximo absoluto de la función f si
c está en el dominio de f (c) f (x) para toda x en el dominio de la función.
Definición: f (c) se dice que es un mínimo global de la función f si c al
dominio de f y si f (c) f (x) x Dominio de f.
Teorema del Valor Extremo
Si una función f es continua en el intervalo cerrado [a,b], entonces f tiene un
valor máximo absoluto y un valor mínimo absoluto en [a,b].
Un extremo absoluto de una función en un intervalo cerrado debe ser un
extremo relativo o ser un valor de la función en un extremo del intervalo.
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 87 -
Procedimientos para determinación de extremos absolutos en intervalo
cerrado:
1. Identificar valores de la función en los números críticos de f en [a,b]
2. Encontrar f (a) y f (b)
3. El mayor de estos es el máximo absoluto y el menor es el mínimo absoluto
Teorema de Rolle
Sea una función f continua en un intervalo cerrado [a,b], diferenciable en el
intervalo (a,b) abierto y sean f (a) = 0 y f (b) = 0 , existe al menos un número
“c” entre a y b donde f ' (c) = 0.
Teorema del Valor Medio Sea f una función continua tal que:
es continua en el intervalo cerrado [a,b]
es diferenciable en el intervalo abierto (a,b) entonces existe un número “c” en
el intervalo abierto (a,b) tal que:
Criterio de la Primera derivada para Extremos Relativos
Si una función continua en el intervalo abierto (a,b) que contiene un número
“c” y f es diferenciable, excepto, posiblemente en “c” ( f (c) puede no existir).
Si c es un extremo entonces:
f'( x1 0 f x donde x1 C
f' ( x2 0 f x donde C2 x2 en este caso c es un máximo relativo
Procedimiento para Determinar Extremos Relativos
1. Encontrar números críticos ( f ' (x) = 0 ó f ' (x) no
2. Aplicar criterio de la primera derivada
Criterio de la Segunda Derivada
Sea “c” un número crítico de una función en la cual f ' (c) = 0 y f existe para
todos los valores de x en algún intervalo abierto que contenga a “c”.
Entonces si f ' ' (c) existe y:
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 88 -
Si f ' ' c 0, f, f tiene un valor máximo relativo en “c”.
Si f ' ' c 0, f, f tiene un valor mínimo relativo en “c”.
Nótese que si f ' ' (c) = 0 nada puede concluirse.
Teorema: Sea f una función continua en el intervalo I que contiene al número
c. Si f (c) es un extremo relativo de f en I y es el único, entonces f (c) es un
extremo absoluto de f en I. Además,
Si f c es un máximo relativo es un máximo absoluto
Si f c es un mínimo relativo es un mínimo absoluto.
Gradiente
Derivadas Parciales: Son derivadas direccionales pero especiales, las
direcciones son las de los ejes coordenados.
Y
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 89 -
Extensión de los Criterios de Existencia de Máximo y Mínimos
- Los puntos críticos son aquellos donde Ñf = 0 o no existe.
- Alguna medida de “positividad” del Hessiano nos dirá si es un máximo o un
mínimo
3.3 Problemas no restringidos.
3.3.1 Multiplicadores de LAGRANGE (λ lambda).
Los problemas de optimización no restringida no tienen restricciones, por lo
que la función objetivo es sencillamente:
Maximiza f(x)
Sobre todos los valores de x = (x1, x2, …, xn), la condición necesaria para que
una solución especifica x = x* sea optima cuando f(X) es una función
diferenciable es: En x=x*, para j=1,2…….n
Cuando f(x) es cóncava, esta condición también es suficiente, por lo que la
obtención de x* se reduce a resolver el sistema de n ecuaciones que se
obtuvo al establecer las n derivadas parciales igual a cero. Cuando se trata
de funciones no lineales f(x), las ecuaciones no son lineales, y es poco
probable que se pueda tener una solución analítica simultanea.
a) Optimización no restringida de una variable:
Estos problemas x (n=1) donde la función diferenciable debe ser
maximizarse es cóncava.
La condición necesaria y suficiente para que la solución particular x=x* sea
optima (un global máximo) es
En x = x*
Si en la ecuación se puede despejar x* de forma directa el problema llega a
su fin, pero si f(x) no es una variable sencilla y su derivada no es una función
lineal o cuadrática tal vez sea imposible resolver la ecuación analítica.
De ser así existen métodos numéricos para un procedimiento de búsqueda
para resolver el problema.
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 90 -
Método de la bisección (pasos)
Paso inicial:
Seleccione una tolerancia del error para x* (ε), encuentre la cota inferior
actual para x*, (x) y la cota actual superior para x* ( ) por inspección y
seleccione una solución de prueba inicial:
Iteración:
1.- Evalúe
2.- Si
3.- Si
4.- Seleccione una nueva
Regla de detención
Detenerse si , de modo que la nueva x´ deba de estar dentro de ε
para x*. En caso contrario debe hacerse otra iteración
b) Optimización no restringida de varias variables:
Si se considera el problema de maximizar una función cóncava f(x) de
variables múltiples, x = (x1, x2, x3….,xn) en la que no se tienen restricciones
sobre los valores factibles. Suponga de nuevo que la condición necesaria y
suficiente para la optimalidad, dada por el sistema de ecuaciones que se
obtiene al establecer sus respectivas derivadas parciales iguales a cero, no
se puede resolver de forma analítica, por lo que debe emplearse un
procedimiento de búsqueda numérico.
Método de Newton
El encontrar la solución a un sistema de ecuaciones no lineal es mucho más
difícil que el de un sistema lineal. El método de Newton es un procedimiento
iterativo y permite la linealización de un sistema de ecuaciones no lineal,
para posteriormente darle solución por cualquier método numérico de
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 91 -
ecuaciones lineales simultáneas, este forma parte de los métodos conocidos
como métodos de gradiente.
Un sistema de n ecuaciones con n incógnitas (x1, x2, ... xn), se conoce como
no lineal, si una o más de estas no es lineal.
De manera general, la solución de un sistema de n ecuaciones no lineales
aplicando el método de Newton se plantea como sigue:
La suma de todas las ecuaciones no lineales que representan el sistema en
estudio
La iteración de Newton se podrá obtener para el conjunto de ecuaciones a
partir de la ecuación anterior, usando la serie de Taylor en una aproximación
de primer orden
Estas ecuaciones representan un conjunto de 2n ecuaciones lineales
acopladas para el vector de incógnitas X en el paso de tiempo k+1, en la
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 92 -
iteración i+1. Los términos en derivadas darán lugar a la formación de la
matriz Jacobiana:
La solución del conjunto de ecuaciones lineales encontradas en cada
iteración (matriz Jacobiana) será resuelta por cualquier método lineal de
matrices hasta que los residuales sean menores a una tolerancia designada,
muy próxima a cero.
Método de derivadas restringidas (Jacobiano).
Se puede considerar como una generalización del método simplex para
programación lineal.
Considere el problema
Las funciones f(X) y gi(X), donde i = 1,2,…,m, se suponen diferenciables y
doblemente continuas. El utilizar derivadas restringidas es encontrar una
expresión de forma cerrada para las primeras derivadas parciales de f(X) en
todos los puntos que satisfacen las restricciones g(X) = 0. Estos puntos
estacionarios entonces se sabe que son donde dichas derivadas parciales se
anulan.
Por el teorema de Taylor, para los puntos X + DX en el entorno factible de X,
se deduce que
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 93 -
Con esto se tienen m ecuaciones con n incógnitas, cuando m < n tenemos, si
definimos a X ahora como:
X = (Y, Z)
De donde:
Jmxn se conoce como la matriz jacobiana y Cmxn-m = es la matriz de
control. Utilizando las definiciones anteriores, se puede escribir el conjunto
original de ecuaciones como:
Como J se supone que no es singular, existirá su inversa J-1. Por lo tanto
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 94 -
Aplicando a esta ecuación la derivada restringida con respecto a al vector
independiente Z, se tiene
Método Lagrangiano.
Está muy relacionado con el método jacobiano y se puede desarrollar a partir
de aquel. Anteriormente se demostró que:
Considerando que en el punto extremo (y para cualquier punto estacionario)
X0 = (Y0, Z0), el gradiente restringido c f debe anularse, entonces de
UNIDAD III / PROGRAMACIÓN NO LINEAL
- 95 -
Esta relación permite estudiar el efecto de variaciones pequeñas de g sobre
el valor óptimo de f evaluando la tasa de cambio de f con respecto a g. Estas
tasas usualmente se conocen como coeficientes de sensibilidad.
Si tomamos
Esta ecuación satisface las condiciones necesarias para los puntos
estacionarios ya que la expresión para f/ g se calcula con c f = 0. Otra
representación más conveniente de la ecuación es tomando sus derivadas
parciales con respecto a todas las xj. Lo anterior da
Las ecuaciones resultantes junto con las de restricciones g = 0 proporcionan
los valores factibles de X y que satisfacen las condiciones necesarias para
puntos estacionarios. Este procedimiento define al método de Lagrange para
identificar los puntos estacionarios de problemas de optimización con
restricciones de igualdad.
UNIDAD 4
TEORÍA DE INVENTARIO
Objetivo: Utilizara los diferentes sistemas de de
control de inventarios, en la formulación
de modelos para resolver problemas.
UNIDAD IV / TEORÍA DE INVIERNO
- 97 -
4.1. SISTEMAS DE ADMINISTRACION Y CONTROL.
Mantener un inventario de productos o artículos para su venta o uso futuro es
una práctica común en el mundo de los negocios. Se aplica tanto en las
ventas al mayoreo como al menudeo y por los fabricantes.
Casi todas las empresas deben almacenar bienes para asegurar un trabajo
uniforme y eficiente.
El problema de tener un inventario, debe responder básicamente a 2
preguntas:
1) ¿Cuándo hacer un pedido?
2) ¿Qué cantidad se debe pedir?
Existen dos formas de satisfacer la demanda requerida de productos,
teniendo un sobre almacenamiento o teniendo un subalmacenamiento.
Con el sobre almacenamiento, de requiere invertir un mayor capital, aunque
tendremos menos ocurrencias frecuentes de escasez, y de colocación de
pedidos. Con el subalmacenamiento, el capital invertido es menor pero
aumenta la frecuencia de pedidos así como el tiempo que estén sin
mercancía. Los dos extremos son costosos, por lo tanto debemos tomar
decisiones basadas en la minimización de costos que produzcan un balance
entre el costo de sobre almacenamiento y subalmacenamiento.
SISTEMA DE INVENTARIO ABC.
En un negocio a veces al manejar un inventario implica a un número
apreciable de artículos o productos con diferentes precios, desde los
económicos hasta el más costoso. Como el inventario representa en realidad
un capital ocioso (inactivo) es necesario mantener el control sobre los
artículos que aumenten considerablemente el costo del inventario. Por
experiencia se sabe que sola una pequeña parte impacta considerablemente
en el costo del inventario, sobre estos artículos se debe tener un control
estricto.
UNIDAD IV / TEORÍA DE INVIERNO
- 98 -
Se puede seleccionar estos artículos, con un procedimiento simple, el
sistema ABC se realiza graficando el porcentaje de artículos de inventario
total contra el porcentaje del valor monetario total en un periodo
(generalmente un año).
La idea es determinar el porcentaje de artículos que contribuyen al 80% del
valor monetario acumulado. Esto se clasifica como el grupo A y normalmente
es alrededor del 20% del total de artículos, los clase B comprenden a los
valores monetarios porcentuales entre el 80% y 95% y son alrededor del
25% y los restantes son clase C.
Las clase A son pocos artículos pero costosos y deben tener un control
estricto de inventario, los clase B son los siguen en el orden y el control debe
ser moderado, la clase C son muchos artículos influyen poco en el costo del
inventario deben tener un control bajo.
Convenientemente se dividen para su estudio a los sistemas de inventarios
en 2 categorías:
1) Demanda y tiempo de entrega determinista.
2) Demanda y/o tiempo de entrega probabilística.
Los sistemas de inventarios son tan variados e implican tantas
consideraciones que sería imposible desarrollar modelos para todas las
situaciones posibles.
Clasificación de los sistemas de inventarios:
A) Orden repetitiva, demanda independiente.
B) Una sola orden, demanda independiente.
C) Orden repetitiva, demanda dependiente.
A veces se clasifican, por la relación con la secuencia de producción.
A) Abastecimiento.
B) Materiales
C) En proceso
D) Bienes terminados
UNIDAD IV / TEORÍA DE INVIERNO
- 99 -
Los modelos para representar a un sistema de inventarios se pueden dividir
en dos grandes categorías:
A) Modelos de cantidad fija de
reorden.
B) Modelos de periodos fijos de reorden.
Los inventarios produce beneficios mixtos, ya que consume recursos en
adquirir bienes y mantenerlos que pueden ocuparse en otras áreas, por
ejemplo, publicidad o investigación. Pero por le otro lado se mejora el
Llega una Demanda
Inventario Que se
Tiene
¿Lo que Se tiene
≥ Demanda?
Llenar una Orden
Calcular el estado
Fin
Faltantes/venta De pérdida
Actualizar Registros:
Recibir almacén
Si
No
Llega tiempo
de revisión
Calcular Cantidad a
ordenar
Mandar orden
de reabastecimi
ento
Llega una Demanda
Inventario Que se
Tiene
¿Lo que se tiene
≥ demanda?
Llenar una
Orden
Recalcular el estado
Estado
≤ Punto de Reorden
Fin
Faltantes/venta de perdida
Actualizar registros:
Recibir almacén
Mandar orden De
Reabastecimiento
Si
No
Si
No
UNIDAD IV / TEORÍA DE INVIERNO
- 100 -
servicio al cliente al tener un producto siempre que lo demande. Por lo tanto
se debe de buscar un equilibrio de esos costos.
Los cuatro costos más comunes asociados a un inventario son:
Costo de compra (de fabricación, precio unitario).- Este costo incluye el costo
de un articulo, mas los impuestos y los gastos de transporte. Si la compañía
produce el producto entonces se debe incluir todos los gastos de fabricación.
Costo de ordenar (costo fijo, costo directo).- Este se genera debido a la
elaboración de pedidos y de facturación, como son la mano de obra, la
papelería, el teléfono, etc. Si el producto se genera en la misma compañía
entonces se toman los costos de preparación de maquinaria
Costos de conservación, (almacenamiento).- Este costo incluye los costos
generados por el almacenar físicamente los artículos, por ejemplo: la
refrigeración, aseguramiento, impuesto al almacenaje, el costo de mantener
inmóvil el capital cuando se pudo invertir en otra actividad.
Costo de escasez (agotamiento o faltantes) esto reproduce cuando un cliente
demanda un producto y la demanda no se satisface a tiempo, si los clientes
aceptan la entrega en una fecha posterior se denomina pedidos pendientes.
Pero si el clientes no acepta se tiene una venta perdida. Este costo es el mas
difícil de medir ya que implica, que los clientes vayan a otra partes a surtir su
demanda, perdida del nombre comercial, que la compañía pierda
competitividad, etc.
Al partir de lo anterior, podemos decir que en el costo de un inventario
generalizado lo obtenemos de la siguiente manera.
Costo de inventario = costo de compra + costo de ordenar + costo de
conservación + costo de escasez.
UNIDAD IV / TEORÍA DE INVIERNO
- 101 -
Como se observa el nivel óptimo de inventario corresponde al costo total
mínimo de los cuatro componentes
Existen varios modelos de inventarios y esto es debido al tipo de demanda
del artículo lo cual hace que el modelo matemático sea más complejo. El tipo
de demanda puede ser:
Demanda determinista estática, se produce cuando la tasa de consumo
permanece constante todo el tiempo.
Demanda determinista dinámica, se produce cuando la demanda reconoce
con certeza, pero varía de un periodo a otro.
Demanda probabilística estacionaria, es cuando la demanda es descrita
por una densidad de probabilidad que se mantiene constante.
Costo total Costo de almacenamiento Costo de
ordenar
Costo de
escasez
Costo compra
Nivel de inventario
Costo mínimo
Nivel optimo
Costo por año
UNIDAD IV / TEORÍA DE INVIERNO
- 102 -
Demanda probabilística no estacionaria, la densidad de probabilidad varía
con el tiempo.
ESTATICA MÁS SIMPLE DETERMINISTA DEMANDA DINAMICO NIVEL DE DIFICULTAD DE MODELADO MATEMATICO
ESTATICA PROBABILISTICA
DINAMICA MÁS COMPLEJA
Otros factores que complican al modelo matemático son:
Las demoras de entrega.
Abastecimiento múltiple
Número de artículos
Etc.
4.2. MODELOS DETERMINISTICOS
En la realidad estos modelos es difícil encontrarlos directamente, pero una
situación real se puede ajustar a ellos.
El modelo más comúnmente aplicado para resolver este tipo de modelos es
el del lote económico de pedido
El modelo clásico de lote económico de pedido fue elaborado por F. W.
Harris de Westinghouse en 1915 y para que sean validos se deben cumplir
las siguientes suposiciones:
1) La demanda es determinista y ocurre a una tasa constante (β).
UNIDAD IV / TEORÍA DE INVIERNO
- 103 -
2) El hacer un pedido de cualquier tamaño (q) genera un costo de ordenar
(K)
3) El conservar una unidad de artículo en el inventario en una unidad de
tiempo genera un costo (h)
4.2.1. LOTE ECONÓMICO SIN DÉFICIT.
El primer modelo que estudiaremos será el lote económico sin déficit, es
decir aparte de las tres consideraciones se le agrega una más:
4) No se permite que exista escasez, es decir el inventario no debe ser
negativo.
A) Lote económico sin déficit con tiempo de entrega cero.
En este modelo, como la entrega es inmediata nos conviene hacer un pedido
cuando el nivel de inventario sea igual a cero, para no generar costos de
conservación en el inventario. Pero cuidando que no haya escasez.
Si graficamos este modelo tendríamos lo siguiente:
Ciclo: es el intervalo de tiempo que comienza con la llegada de un pedido y
termina un instante antes de que se reciba el siguiente pedido.
Como en este modelo no se permite la escasez, entonces el costo total por
ciclo será:
Nivel de inventario
q
0
q - βt
q
2q
t = q/t
Inv. Prom.
= q/2
Tiempo
UNIDAD IV / TEORÍA DE INVIERNO
- 104 -
Costo por ciclo = costo de ordenar + costo de compra + costo de
conservación.
El costo de ordenar es = K (sin importar el tamaño)
El costo de compra es = pq (precio unitario por la cantidad)
El costo de conservación se calcula de la siguiente manera:
El nivel promedio del inventario es (q + 0)/2 = q/2 artículos por unidad de
tiempo. El costo por unidad de tiempo sera h(q/2). Como el tiempo de un
ciclo es q/β, el costo total de almacenamiento por ciclo será h(q/2) q/β= hq2/
2β.
Sustituyendo el costo de un ciclo quedara:
Costo por ciclo = K + pq + hq2/ 2β.
Para obtener el costo por unidad de tiempo tenemos:
Costo por unidad de tiempo =CPUT=/
2
2
q
hqpqK
=2
hqp
q
K
Supongamos que Q representa el valor de q que minimiza el costo por
unidad de tiempo, la tendríamos que encontrar haciendo 0CPUTdq
d
Quedando: 02
CPUTdq
d2
h
q
K
Despejando obtenemos la cantidad óptima q:
Q =h
K2
El tiempo de cada pedido será:
T =Q
h
K2
Ejemplo 1:
Un negocio vende 500 discos DVD al mes, cada vez que genera un pedido
genera un costo de 5 pesos, cada disco le cuesta 10.00 pesos, el costo de
mantener un disco en el inventario durante un mes es de 0.08 pesos/disco.
UNIDAD IV / TEORÍA DE INVIERNO
- 105 -
Suponga que la demanda es constante y no se permite escasez y el tiempo
de entrega es cero.
¿Cuál será el tamaño del lote que minimice costos? ¿Cuántos pedidos hará
en un mes?
K= 5.00 pesos
p =10.00 pesos
h=0.08 pesos por disco
por mes
β= 500 discos/mes
25008.0
)5)(500(22
h
KQ
T = 5.0500
250T
Como observamos el lote de pedido tendría que ser de 250 discos y los
pedidos se harían cada ½ mes. Cada 15 días.
Ejemplo 2:
Una compañía que ensambla computadoras, fabrica sus propias bocinas,
ensambla computadoras con una producción continua de 8 000 al mes, sus
bocinas reproducen en lotes y cada lote genera un costo de preparación de
maquinaria de 12 000 pesos, el costo de mantener una bocina en el
almacén durante un mes es de 0.30 pesos, el costo de producción de una
bocina es de 50.00 pesos. ¿Cuál será el tamaño del lote que minimice
costos? ¿En qué tiempo se hará la producción del lote de bocinas?
K= 12 000.00 pesos
p =50.00 pesos
h= 0.30 pesos por
bocina por mes
β= 8 000
bocinas/mes
bocinash
KQ 298,25
30.0
)12000)(8000(22
T = mesesT 16.38000
25298
UNIDAD IV / TEORÍA DE INVIERNO
- 106 -
B) Lote económico sin déficit con tiempo de entrega distinto de cero.
Este lote tiene las mismas condiciones del primero solo que ahora la entrega
demora un tiempo L, es decir es mayor que cero. Esto deja sin cambios los
costos de conservación y de ordenar sin cambios. Pero ahora para evitar que
haya escasez, y reducir el costo de conservación, cada pedido se debe hacer
a un nivel de inventario que asegure que cuando llega cada pedido, nivel de
inventario sea igual cero. Este nivel se conoce como punto de reposición. Se
pueden presentar dos casos al calcularlo:
1) La demanda durante el plazo de entrega (LD) no excede la Q. (LD ≤ Q).
En este caso el punto de reposición ocurre cuando el nivel de inventario es
igual a LD. Entonces el pedido llegara cuando el nivel de inventario sea igual
a cero.
En el ejemplo 1 suponga que el tiempo de entrega es de 5 días. Tendríamos
que L= 5/30
Entonces el punto de reposición es (5/30) (500) = 83.333
Significa que cuando el inventario llegue a 83.333 discos se debe hacer un
nuevo pedido.
2) La demanda durante el plazo de entrega excede a la Q. (LD > Q). En este
caso el punto de reabastecimiento no es igual a LD. Supongamos en el
ejemplo que el tiempo de entrega es de 40 días, entonces LD= (40/30)*500=
666.66 discos. Como se ve llegar a este nivel es imposible ya que el valor de
Q es de 250.
En este caso se debe dividir LD entre el valor de Q y el residuo será el valor
buscado.
En este caso dividimos LD/Q = 666.666/250= 2.666 le restamos el entero en
este caso 2 y nos queda de resto 0.6666 esto lo multiplicamos por Q y
tenemos (0.6666)(250)= 166.6666
Así que haremos un nuevo pedido cuando el nivel de inventario alcance
166.66 discos.
UNIDAD IV / TEORÍA DE INVIERNO
- 107 -
C) Lote económicos de un solo artículo con diferente precio tiempo de
entrega cero.
A menudo sucede que el precio de compra por unidad depende de la
cantidad a comprar. Esto se conoce como descuentos según la cantidad. En
este modelo si habrá que tomar en cuenta el precio del producto para tener
el número optimo de artículos que se debe de pedir.
Aquí encontraremos literales nueva, las cuales son:
P1 = Precio más alto
P2 = Precio más bajo
qr = Cantidad superior que garantiza la rebaja del precio.
Q* = Cantidad optima sin tomar en cuenta los precios.
CPUTQ * = Costo por unidad de tiempo con cantidad Q y precio
unitario más alto.
CPUTQ1 = Costo por unidad de tiempo con cantidad Q1. Esta
cantidad Q1 será calculada haciendo una igualación
De las ecuaciones CPUTQ = CPUTQ1 y utilizando el precio
unitario más bajo.
Pasos para calcular la cantidad óptima.
1) Determinar
Q* h
KQ
2*
Si qr < Q* entonces la
cantidad optima será
igual a Q* (Q=Q*) y
termina el proceso, si no
es así se realiza el paso
2
2) Calcular
Q1
Q1 se calcula a partir de la
igualación
CPUTQ = CPUTQ1
Si Q*< qr < Q1 entonces
el valor optimo es qr
Q = qr
UNIDAD IV / TEORÍA DE INVIERNO
- 108 -
22
*
*
1
1
21
hQ
Q
KP
hQ
Q
KP
Si qr ≥ Q1 entonces el
valor optimo es Q*
Q = Q*
Ejemplo 3) Un vendedor maneja un producto que tiene una demanda diaria
de 5 piezas, el costo por ordenar que se genera es de 10 pesos y el costo
diario por mantener una pieza en el almacén es de 1.00 peso. Si adquiere
menos de 15 productos, el costo por unidad es de 2 pesos, pero si adquiere
15 o más productos, el precio es de 1.00 peso. Cuál es el tamaño de lote que
más le conviene comprar.
Datos:
P1 = 2.00
P2 = 1.00
qr = 15 piezas
h=1.00 peso pieza/día
β= 5 piezas/día
K=10 pesos
Paso 1)
Calculando Q* 101
)5)(10(22*
h
KQ
Comparando Q* y qr resulta que: qr > Q* 15 > 10
Como se observa que qr es mayor que Q* se realiza el paso No. 2
Paso 2) Calculando Q1, esto se calculan igualando las ecuaciones:
22
*
*
1
1
21
hQ
Q
KP
hQ
Q
KP
2
)1()5)(10()5)(1(
2
)10)(1(
10
)5)(10()5(2 1
1
Q
Q
2
505
2
10
10
5010 1
1
Q
Q
UNIDAD IV / TEORÍA DE INVIERNO
- 109 -
0152
50 1
1
Q
Q
010030 1
2
1QQ
Como resultado tenemos que Q1 = 26.18 o bien Q1= 3.82 en este caso se
toma el mayor valor 26.16
Comparando Q* = 10
Qr = 15
Q1= 26.18
Como observamos se cumple la condición Q*< qr < Q1 entonces el valor
optimo es qr, en este caso es 15.
Es decir el tamaño óptimo de los pedidos es de 15 piezas cada 3 días.
4.2.1. LOTE ECONÓMICO CON DÉFICIT.
Muchas veces la demanda no se satisface a tiempo y se produce escasez,
algunas veces esto puede ser redituable, pues alarga la longitud del ciclo y
produce ahorro en los costos de ordenar (o preparación) y de conservación.
Esto provoca que el costo del inventario de incluya un costo de escasez (pf)
La grafica de este modelo queda de la siguiente manera:
Nivel de inventario
q
0
s- βt
q/β
Tiempo
s
q-s
s/β
UNIDAD IV / TEORÍA DE INVIERNO
- 110 -
El costo del inventario por unidad de tiempo quedara de la siguiente manera:
Costo de ordenar + costo de compra + costo de conservación + costo de
escasez.
Costo de compra = pq
Costo de ordenar = K
Costo de conservación = (hs/2) (s/β) = hs2/ 2β
El costo por escasez se calcula de la siguiente manera:
La escasez ocurre en un tiempo: (q-s)/ β
La cantidad promedio de artículos faltantes es: [0 + (q/s)] /2 = (q-s)/2
El costo por el número promedio de faltantes será: pf(q-s)/2
Y el costo escasez multiplicado por el tiempo quedaría: (q-s)/ β * pf(q-s)/2 =
2
)( 2sqpf
Sustituyendo estos valores en la ecuación del modelo queda el costo del
ciclo como:
2
)(
2
2 2sqpfhspqK
El costo por unidad de tiempo es:
q
sqpf
q
hsp
q
K
q
sqpfhspqK
CPUT2
)(
2
2
)(
2
22
2
Como se observa en esta ecuación tenemos dos variables que no
conocemos q y s, por lo tanto tenemos que derivar parcialmente esta
ecuación respecto a estas dos variables e igualar a cero para encontrar el
valor óptimo de q y s, quedando:
0)(
q
sqpf
s
h
s
CPUT
02
)()(
2 2
2
2
2
2 q
sqpf
q
sqpf
q
hs
q
K
q
CPUT
UNIDAD IV / TEORÍA DE INVIERNO
- 111 -
Estas ecuaciones se resuelven simultáneamente obteniéndose los valores de
S y Q (valores óptimos de q y s) los cuales quedan de la siguiente manera:
Cantidad optima:
pf
hpf
h
KQ
2
Cantidad antes de producirse la escasez:
hpf
pf
h
KS
2
El tiempo o periodo que se deben hacer lo pedidos:
Qt
Faltante máximo = Q - S
Ejemplo 4: Un negocio vende 500 discos DVD al mes, cada vez que genera
un pedido genera un costo de 5 pesos, cada disco le cuesta 10.00 pesos, el
costo de mantener un disco en el inventario durante un mes es de 0.08
pesos/disco, el costo de la escasez por disco en un mes es de 0.40 pesos.
Suponga que la demanda es constante y se permite escasez y el tiempo de
entrega es cero.
¿Cuál será el tamaño del lote que minimice costos? ¿Cuántos pedidos hará
en un mes? ¿Cuál será la escasez máxima?
K=5.00
P=10.00
h=0.08
pesos/disco/
mes
β=500
discos/mes
pf=0.40
86.27340.0
08.040.0
08.0
)5)(500(22
pf
hpf
h
KQ
piezas
547.0500
86.273Qt
3.20808.040.0
040
08.0
)5)(500(22
hpf
pf
h
KS
piezas
UNIDAD IV / TEORÍA DE INVIERNO
- 112 -
pesos/disco/
mes
Escasez máxima=Q - S=273.86 - 208.3 =
65.5
Estos resultados indican que los pedidos se harán por 274
piezas, cada 16 días y que la escasez máxima permitida
será de 66 piezas.
Ejemplo 5: resuelva el problema 2 con un costo de pérdida de 1.1 por
pieza/mes
4.4 Modelo probabilístico
En estos modelos de inventarios, a diferencia de los anteriores, tienen una
demanda incierta o probabilística. En vez de conocer exactamente la
demanda de un producto, ahora se conoce la distribución de probabilidad
para la demanda. Como no se conoce con exactitud la demanda del
producto, siempre hay el riesgo de de que haya faltantes, este riesgo puede
disminuirse con un inventario grande pero no puede eliminarse. Como es
difícil encontrar un punto de reordenamiento exacto para no tener escasez,
se maneja los conceptos de inventario de seguridad y nivel de servicio.
El inventario de seguridad, es un número que incrementa al punto de reorden
para proteger contra los posibles faltantes durante el periodo de entrega.
Esta cantidad de inventario de seguridad esta basada en una decisión
administrativa sobre el nivel de servicio. El nivel de servicio es la probabilidad
de tener un artículo en el almacén cuando se solicite. Los niveles de servicio
más comunes varían de 80% al 99%, es decir la posibilidad de quedarse sin
artículos es de 20% a 1%.
Aquí se presentaron dos ejemplos de modelos de inventarios probabilísticos:
a) Modelo de cantidad fija de reorden cuando no se conoce el costo de
escasez.
UNIDAD IV / TEORÍA DE INVIERNO
- 113 -
b) Modelo de cantidad fija de reorden cuando se conoce el costo de escasez.
Modelo de cantidad fija de reorden cuando no se conoce el costo de
escasez.
El procedimiento para resolver este modelo es el siguiente:
1) Encontrar la cantidad que debe ordenarse por medio de la formula:
h
DKQ
2
Q = Tamaño del lote económico
D = Demanda promedio en cierto tiempo
K = Costo por ordenar
h = costo de conservación.
2) Determínese el inventario de seguridad con base a la distribución de la
demanda del tiempo de entrega y la sección intuitiva del nivel de servicio,
con la formula:
ZB B = Tamaño del inventario de seguridad
Z = valor de acuerdo al nivel de servicio (obtenerla de la tabla
de distribuciones de probabilidad).
σ= desviación estándar de para la demanda del tiempo de
entrega.
3) Iguálese el punto de reorden a la demanda promedio del tiempo más el
inventario de seguridad.
R=DL+B
R = punto de reorden
L = promedio del tiempo de entrega
Ejemplo:
Una refaccionaría vende cajitas de tornillos, la demanda tiende a un
promedio de 5 cajas por día, y tiene un distribución normal. El tiempo de
entrega varía en promedio 3 días. La desviación estándar para la demanda
del tiempo de entrega es de 3.90. El costos de ordenar es de 1.50 y el costo
de conservación es de 1.0 por año. El dueño de la refaccionaría quiere que
el valor del nivel de servicio sea de 98%.
Datos: Observamos que D esta en día, mientras que el costo de
UNIDAD IV / TEORÍA DE INVIERNO
- 114 -
D = 5/dia
K = 1.50
h =1.0 por
año
σ=3.9
L=3
conservación esta en año, asi que hay convertir. Suponiendo
que trabaja 6 días durante la 50 semanas del año.
D=(5)(6)(50)= 1500 unidades año
1)Calculando el valor de Q=
670.1
)5.1)(1500(22
h
DKQ
2)Calculando el inventario de seguridad:
Como se desea un nivel de servicio de 98% el valor de Z
correspondiente de la tabla de distribución normal es igual a
2.06
034.8)9.3)(06.2(ZB
3) calculando el punto de reorden:
R=(5)(3)+8=23 unidades
En resumen los pedidos se harán de 67 cajitas de tornillos,
cuando queden en el inventario 23 piezas.
UNIDAD 5
LINEAS DE ESPERA
Objetivo: Comprenderá la importancia del
desarrollo de modelos de líneas de
espera identificando sistemas con
distribución Poisson, y analizará sus
costos
UNIDAD V / LINEAS DE ESPERA
- 116 -
5.1 Definiciones Líneas de Espera características y suposiciones
PROCESO BÁSICO DE LAS LÍNEAS DE ESPERA.
Una situación de línea de espera, se genera de la siguiente manera:
El cliente llega a una instalación se forma en un línea de espera. El servidor
elige a un cliente de la línea de espera, para comenzar el servicio. Al término
del servicio se repite el proceso de elegir un nuevo cliente.
Cliente.- Unidades que entran al sistema para recibir un servicio. Pueden ser
personas, cartas, carros, incendios, ensambles intermedios en una fábrica,
etc.
Servidor.- Unidades encargadas de prestar un servicio. Pueden ser las cajas
en un banco, en un supermercado, unidades de emergencias, un médico,
una maquina, etc.
Disciplina de servicio.- Regla establecida para proporcionar un servicio a
un cliente en la línea de espera.
PROCESO DE ENTRADA. (PROCESO DE LLEGADA)
Este proceso se refiera a la forma en que surgen y llegan los clientes a la
instalación.
Una característica muy importante es el tiempo entre llegadas (tiempo de
llegadas) que es tiempo que transcurre entre dos llegadas consecutivas.
Este tiempo entre llegadas puede ser de dos clases:
Determinístico: Cuando los clientes llegan a un intervalo de tiempo
conocido de forma constante.
Cola
Mecanismo de servicio
Disciplina de la cola
Sistema de cola
Llegadas
UNIDAD V / LINEAS DE ESPERA
- 117 -
Probabilístico: Cuando se considera al tiempo de llegada como una variable
aleatoria cuya distribución probabilística se considera conocida.
Normalmente se considera que los clientes llegan de forma individual, es
decir en un momento dado solo hay una llegada, pero se puede presentar
también que la llegadas sean en grupo (en masa).
El proceso de entrada podría depender de la cantidad o tamaño de clientes
presentes en un determinado tiempo. Si la fuente de fuente de clientes es
pequeña, se le nombra fuente como fuente de entrada finita, pero si la
fuente de clientes es grande o no se puede determinar su tamaño se conoce
como fuente de entrada infinita. (Fuente limitada o ilimitada).
Rechazo: Se produce un rechazo cuando, un cliente llega a una instalación y
se niega a entrar debido al tamaño de la línea de espera.
Abandono: se produce cuando un cliente estando en la línea de espera se
sale, debido a que la espera es muy larga.
PROCESO DE SALIDA. (PROCESO DE SERVICIO)
Este proceso de refiere a la forma en que son atendidos los clientes por lo
servidores.
Dentro de este proceso tenemos el tiempo de servicio, que es el tiempo
que le toma a un servidor atender a un cliente. Este tiempo pude ser de dos
tipos:
Determinístico: Cuando el tiempo de servicio se conoce con exactitud.
Probabilístico: Cuando se considera al tiempo de servicio como una
variable aleatoria cuya distribución probabilística se considera conocida.
En una instalación puede haber más de un servidor, y debido a esto surgen 2
tipos de líneas de espera:
Líneas de espera en paralelo (canales de servicio en paralelo).- Cuando
en una instalación hay más de un servidor y todos ofrecen el mismo servicio.
UNIDAD V / LINEAS DE ESPERA
- 118 -
Líneas de espera en serie (estaciones).- Cuando en una instalación hay
más de un servidor en la cuales el cliente tiene que pasar a cada una para
completar su servicio.
Líneas de espera en red.- En estas instalaciones hay una combinación de
líneas de espera en serie y otras en paralelo.
DISCIPLINA EN UNA LINEA DE ESPERA.
Como se menciono, la disciplina en una línea de espera es el orden que se
atiende a los clientes las cuales pueden ser:
Disciplina FCFS (First come, first served) (FIFO). En el cual el cliente que
llega primero se atiende primero, es decir según el orden de llegada.
Disciplina LCFS (Last come, first served) (LIFO). En el cual el último cliente
que llega se atiende primero.
Disciplina SIRO (service in random order) Servicio en orden aleatorio.
Prioridad en el servicio.- aquí se clasifican los clientes en categorías y cada
categoría recibe un nivel de prioridad.
UNIDAD V / LINEAS DE ESPERA
- 119 -
TIPOS DE LÍNEAS DE ESPERA.
5.2 Terminología Notación Líneas de Espera
NOTACION KENDALL-LEE.
Esta notación sirve para etiquetar o nombrar a los diferentes modelos de
líneas de espera que se pueden tener.
La notación consta de 6 números de la forma siguiente:
a/b/c/d/e/f
Donde los símbolos representan lo siguiente:
a = La distribución de tiempo entre llegadas.
b = La distribución de tiempo de servicio.
c = El numero de servidores en paralelo.
d = Tipo de disciplina en el servicio (FCFS, LCFS, SIRO, PRIORIDAD)
e = Numero máximo admitido en el sistema (línea de espera + en servicio).
Cola Servidor Llegada
Salida
Una cola, un servidor
Cola Llegada
Una cola, múltiples servidores
Servidor
Servidor
Servidor Salida
Salida
Salida
Colas
Colas
Colas Servidor Salida
Servidor Salida
Servidor Salida
Varias colas, múltiples servidores
Llegada
Cola Servidor Llegada
Cola Servidor Salida
Una cola, servidores secuenciales
UNIDAD V / LINEAS DE ESPERA
- 120 -
f = Tamaño de la población de donde se extrae los clientes.
Para reemplazar a los símbolos a y b se usan las siguientes iniciales:
M = Cuando el tiempo de llegada o servicio tiene una distribución
exponencial entrada o salida de Poisson (o Markoviana).
D= Cuando el tiempo de llegada o servicio es determinista
Ek = Cuando el tiempo de llegada o servicio tiene una distribución de Erlangs
con parámetro K.
G = Cuando el tiempo de llegada o servicio tiene una distribución general
(cualquier distribución arbitraria).
Como observamos los elementos básicos para crear un modelo de línea de
espera, dependerá de los siguientes factores:
Distribución de llegadas. (Individuales o en grupo).
Distribución de servicio. (Individuales o en grupo).
Diseño de la instalación (estaciones en serie, paralelo, o en red)
Disciplina de servicio
Tamaño de la línea (finita o infinita)
Fuente de los clientes (finita o infinita)
5.3 Proceso Nacimiento Muerte Líneas de Espera
PROCESO DE NACIMIENTO Y MUERTE.
La mayoría de los modelos de colas suponen que las entradas y salidas al
sistema de colas, ocurren de acuerdo al proceso de nacimiento y muerte.
En este caso un nacimiento se refiere a la entrada de un nuevo cliente y una
muerte a la salida de un cliente servido.
Este proceso nos sirve para calcular el número de clientes probables que
habrá en un sistema en un tiempo determinado t. N(t) número de clientes que
hay en el momento t.
Este proceso de nacimiento y muerte describe en términos probabilísticos
como cambia N (t) al aumentar t.
Este proceso hace las siguientes suposiciones:
UNIDAD V / LINEAS DE ESPERA
- 121 -
1) Dado N (t)=n, la distribución de probabilidad para la próxima llegada es
exponencial. Con un parámetro λn (n= 1, 2, 3,….)
2) Dado N (t)=n, la distribución de probabilidad para la próxima muerte es
exponencial. Con un parámetro μn (n= 1, 2, 3,….)
3) Solo un nacimiento o una muerte puede ocurrir a la vez.
En la aplicación de problemas λn representa la tasa media de llegadas y μn
tasa media de salidas.
5.4 Modelos Poisson
Existen una gran variedad de modelos para los sistemas de colas, las dos
características más importantes serán:
a) Los tiempos de llegada.
b) Los tiempos de servicio.
En los sistemas de colas reales no es posible determinar con exactitud estos
dos tiempos, es decir no son determinísticos, los más comunes son los
modelos probabilísticos, donde se dan un promedio de estos tiempos, por lo
tanto tenemos que usar una distribución de probabilidad que se ajuste lo más
cercano a la realidad.
Para calcular la probabilidad de cuál será el tiempo entre llegadas se
utiliza la distribución exponencial, esta distribución tiene una función
de densidad de probabilidad: (densidad de probabilidad continua)
0
0
0)(
tPara
tParaetfT
t
Donde: T es el tiempo entre los eventos (tiempo de llegadas o tiempo de
servicio)
α es la tasa media que ocurra una llegada o servicio.
Si se grafica esta distribución de probabilidad nos da lo siguiente:
UNIDAD V / LINEAS DE ESPERA
- 122 -
La media de esta función esta dado por: 1
La varianza de esta función es: 2
1
Aquí se puede observar las siguientes propiedades de esta distribución:
1) La probabilidad de que ocurra un evento siempre es positiva pero menor
que 1
2) fT(t) es una función decreciente respecto a t, es decir es más probable que
el valor de T este cercano a la media.
3) La distribución de probabilidad del tiempo para que ocurra un evento, no
depende del tiempo en que ocurrió el evento anterior, es decir es
independiente.
Para calcular la probabilidad de cuál será el número de llegadas en un
tiempo determinado, se utiliza la distribución de Poisson (densidad de
probabilidad discreta)
Donde X(t) representa el numero de ocurrencias de un evento en un
determinado tiempo t. Siempre que t >0, en donde el tiempo cero es el
instante donde comienza la cuenta. La probabilidad seria:
UNIDAD V / LINEAS DE ESPERA
- 123 -
!
)()(
n
etntXP
tn
Para n = 1, 2, 3, 4 ……..
Como se observa también la distribución de Poisson tiene un parámetro αt
donde α representa la tasa o numero esperado de eventos por unidad de
tiempo.
Y cuando n = 0 se tiene:
tetXP 0)(
Que es igual a la probabilidad obtenida por la distribución exponencial para
que ocurra un evento después del tiempo t.
La media de la distribución de Poisson es:
ttXE )(
DISTRIBUCION ERLANG.
Si los tiempos entre llegadas no son exponenciales entonces se modelan de
acuerdo a la distribución Erlang (gamma). En esta distribución continua, que
tiene la siguiente función:
)0()!1(
)()(
1
tk
eRtRtf
Rtk
5.4.1 Modelos Poisson un Servidor
5.4.2 Modelos Poisson Múltiples Servidores
Cálculos en los modelos de colas
Pn = probabilidad que en el estado estable haya n clientes en el sistema
Ls = número de clientes que espera halla en el sistema
Lq = número de clientes que espera halla en la línea de espera.
Ws = Tiempo de espera en el sistema (línea mas servicio)
UNIDAD V / LINEAS DE ESPERA
- 124 -
Wq = Tiempo de espera en la línea de espera.
(M/M/S) S=1 Y S>1
(M/M/S) VARIACION DE COLA FINITA S=1 Y S>1(COLA FINITA)
(M/M/S) VARIACION DE FUENTE DE ENTRADA FINITA S=1 Y S>1
REPARACION DE MAQUINAS
(M/M/1)(GD/∞/∞), (M/M/C)(GD/∞/∞)
(M/M/1)(GD/N/∞), (M/M/C)(GD/N/∞) VARIACION DE COLA FINITA (COLA
FINITA)
(M/M/R)(GD/K/K) MODELO DE SERV A MAQ. ORIGEN FINITO
(M/M/∞)(GD/∞/∞) MODELO DE AUTOSERVICIO.
FORMULARIO DE ACUERDO AL MODELO:
En estos modelos utilizaremos las siguientes literales:
λ = Tasa de llegadas por unidad de tiempo.
μ = Tasa de servicio por unidad de tiempo.
ρ = Intensidad de tráfico del sistema.
0 = Probabilidad que sistema este ocioso.
j = Probabilidad que haya j clientes en el sistema
L = Cantidad de personas en el sistema.
Lq = Cantidad de personas en la cola.
Ls = Cantidad de personas en servicio.
W = Tiempo promedio que un cliente pasa en el Sistema.
Wq = Tiempo promedio que un cliente pasa en la cola.
Ws = Tiempo promedio que un cliente pasa en el servidor.
M/M/1/GD/∞/∞
En este modelo las llegadas son de forma exponencial, el tiempo de servicio
también es exponencial, solo hay un servidor, el número de clientes que se
pueden formar en la cola es infinito, y el tamaño de la población también es
infinito.
UNIDAD V / LINEAS DE ESPERA
- 125 -
Si ρ > 1 no existe estado estable.
10
)1(j
1L
)(1
22
LLq
01Ls
1
)1(
LW
)(
LqWq
LsWs
M/M/S/GD/∞/∞
En este modelo las llegadas son de forma exponencial, el tiempo de servicio
también es exponencial, existen S números de servidores que dan los
mismos servicios, el número de clientes que se pueden formar en una sola
cola es infinito, y el tamaño de la población también es infinito.
S
)1(!
)(
!
)(
1)1(
0
0
S
S
i
S SSi
i
i
!
)( 0
j
S j
j
UNIDAD V / LINEAS DE ESPERA
- 126 -
Sj .......3,2,1
)1(!
)()( 0
S
SSjP
S
Probabilidad de que todos los
servidores estén ocupados
1
)( SjPLq
S
SjPLqWq
)(
LqL
1)(
S
SjPLW
M/M/1/GD/C/∞
En este modelo las llegadas son de forma exponencial, el tiempo de servicio
también es exponencial, solo hay un servidor, el número de clientes que se
pueden formar en la cola es C, es decir, después de cierto tamaño en la cola
ya no se aceptan clientes, y el tamaño de la población es infinito.
101
1C
0j
j
1C
Cj
SI =1
UNIDAD V / LINEAS DE ESPERA
- 127 -
)1)(1(
)1(11
1
C
CC CCL
2
CL SI =1
LsLLq
01Ls )1( C
LW
)1( C
LqWq
)( SjP PARA UN SISTEMA DE COLAS M/M/S/GD/∞/∞
ρ
S=2 S=3 S=4 S=5 S=6 S=7
.10 .02 .00 .00 .00 .00 .00
.20 .07 .02 .00 .00 .00 .00
.30 .14 .07 .04 .02 .01 .00
.40 .23 .14 .09 .06 .04 .03
.50 .33 .24 .17 .13 .10 .08
.55 .39 .29 .23 .18 .14 .11
.60 .45 .35 .29 .24 .20 .17
.65 .51 .42 .35 .30 .26 .21
.70 .57 .51 .43 .38 .34 .30
.75 .64 .57 .51 .46 .42 .39
UNIDAD V / LINEAS DE ESPERA
- 128 -
.80 .71 .65 .60 .55 .52 .49
.85 .78 .73 .69 .65 .62 .60
.90 .85 .83 .79 .76 .74 .72
.95 .92 .91 .89 .88 .87 .85
BIBLIOGRAFIA
1. Ackoff R. y L. Sasieni . Fundamentos de Investigación. de Operaciones.
México: Limusa. 1977
2. Bazaraa M., y J. Jarvis (). Programación lineal y flujo de redes. México:
Limusa. 1980.
3. Bronson R Investigación de Operaciones. México: McGraw-Hill. 1984.
4. Bueno de A. G. Introducción a la Programación lineal y al Análisis de
Sensibilidad. México: Trillas. 1990
5. Daellenbach H., Georgej., y D. Mc.Nickle. Introducción a Técnicas de
Investigación de Operaciones. México: CECSA.
6. Eppen, Gould y Shmidt.
Investigación de Operaciones Aplicadas a la Administración.
7. Gallagher C. y H. Watson Métodos y modelos cuantitativos para la
toma de decisiones. México: Mc. Graw-Hill. 1982.
8. Hillier F. y G. Lieberman.. Introducción a la Investigación de
Operaciones, ( 5a. ed). México; McGraw-Hill.. 1991
9. Moskowitz H. y G. Wright. Investigación de Operaciones. México:
Prentice Hall. 1982.
10. Prawda, J. Métodos y Modelos de Investigación de Operaciones, Vol.. I,
Vol. .
II. México: Limusa. 1981. 11. Shamblin, J. y Stevens . Investigación de
operaciones México: McGraw-
Hill. 1975
12. Taha H. Investigación de Operaciones, (4a. ed. ). México: Alfa-Omega
1991.
