Embed Size (px)
Citation preview
analisis de riEsgo
UNIVERDIDAD DE ORIENTE
NÚCLEO DE MONAGAS
ESCUELA DE INGENIERIA Y CIENCIAS APLICADAS
DEPARTAMENTO DE INGENIERIA DE SISTEMAS
ANALISIS DE DECISIONES SECCIÓN (UNO)
JULIO DEL 2017.
BACHILLERES: SOUQUETT NATALYA 25576958.
PALACIOS ANDRES 21350350.
PROFESOR: ESTABA CESAR.
l análisis de riesgo es el uso sistemático de la información disponible
para determinar la frecuencia con la que determinados eventos se
pueden producir y la magnitud de sus consecuencias; Los riesgos
normalmente se definen como eventos negativos.
EEl análisis de riesgo se puede realizar cualitativa y cuantitativamente. El análisis
de riesgo cualitativo generalmente incluye la evaluación instintiva o “por
corazonada” de una situación, y se caracteriza por afirmaciones como “Eso parece
muy arriesgado” o “Probablemente obtendremos buenos resultados”. El análisis de
riesgo cuantitativo trata de asignar valores numéricos a los riesgos, utilizando
datos empíricos o cuantificando evaluaciones cualitativas. Vamos a concentrarnos
en el análisis de riesgo cuantitativo.
En el estudio del análisis de riesgos se tiene la toma de decisiones bajo
certidumbre (todos los datos se conocen con certeza), sólo es posible cuando
dispones de toda la información necesaria, conoces todos los datos y variables,
ANÁLISIS DE RIESGO
sabes qué soluciones puedes tomar y comprendes las repercusiones de las
diferentes alternativas entre las que puedes elegir.
Con estas condiciones, la probabilidad de tomar una decisión acertada aumenta
de manera considerable.
Toma de decisiones bajo incertidumbre: El proceso de toma de decisiones es
complejo, sin embargo, éste se complica aún más en condiciones de
incertidumbre, cuando los datos obtenidos son mínimos, o sus fuentes no son
fiables, desconoces las posibles soluciones y repercusiones y la experiencia no te
puede ayudar.
MÉTODOS DE INCERTIDUMBRE:
I. LLUVIA DE IDEAS: este es uno de los métodos más antiguos para recoger
información acerca de un problema en particular. Al comienzo fue
ampliamente utilizada por las fuerzas armadas y desde entonces se ha
usado en toda la industria. La lluvia de ideas es especialmente efectiva para
generar ideas nuevas.
El procedimiento consiste en que se reúne un grupo de personas
interesadas en solucionar un problema en particular. Está técnica se realiza mejor
en un salón de clase, donde el problema puede escribirse en el tablero para que
todos lo vean. El líder explica el problema y las reglas del ejercicio.
II. LLUVIA DE IDEAS: este es uno de los métodos más antiguos para recoger
información acerca de un problema en particular. Al comienzo fue
ampliamente utilizada por las fuerzas armadas y desde entonces se ha
usado en toda la industria. La lluvia de ideas es especialmente efectiva para
generar ideas nuevas.
El procedimiento consiste en que se reúne un grupo de personas
interesadas en solucionar un problema en particular. Está técnica se realiza mejor
en un salón de clase, donde el problema puede escribirse en el tablero para que
todos lo vean. El líder explica el problema y las reglas del ejercicio.
III. ÁRBOLES DE FALLOS: La técnica del árbol de fallos nació en 1962 con
su primera aplicación a la verificación de la fiabilidad de diseño del cohete
Minuteman. Posteriormente ha sido aplicada sobre todo inicialmente en el
campo nuclear y posteriormente en el campo químico, en estudios como el
de Rijmond. Los árboles de fallos constituyen una técnica ampliamente
utilizada en los análisis de riesgos debido a que proporcionan resultados
tanto cualitativos como cuantitativos. En este apartado se describe
únicamente la técnica en su aplicación cualitativa.
Esta técnica consiste en un proceso deductivo basado en las leyes del
Algebra de Boole, que permite determinar la expresión de sucesos complejos
estudiados en función de los fallos básicos de los elementos que intervienen en él.
De esta manera, se puede apreciar de forma cualitativa, qué sucesos son menos
probables porque requieren la ocurrencia simultánea de numerosas causas.
IV. MÉTODO DE MONTE CARLO ÁRBOL DE SUCESOS: El árbol de sucesos
o análisis de secuencias de sucesos es un método inductivo que describe la
evolución de un suceso iniciador sobre la base de la respuesta de distintos
sistemas tecnológicos o condiciones externas.
Partiendo del suceso iniciador y considerando los factores condicionantes
involucrados, el árbol describe las secuencias accidentales que conducen a
distintos eventos.
V. ANÁLISIS DE SENSIBILIDAD: El Análisis de Sensibilidad en
Programación Lineal permite analizar el impacto en los resultados del
modelo (solución óptima y valor óptimo) en aquellos casos donde uno o
varios parámetros sufren modificaciones en relación a sus valores
originales, sin la necesidad de resolver nuevamente el problema (sin
reoptimizar). En dicho contexto en el siguiente artículo presentamos un
ejemplo de dicho análisis para un problema de optimización lineal que
considera 2 variables de decisión.
VI. ANÁLISIS DEL VALOR MONETARIO ESPERADO: Es el promedio o
resultado monetario esperado de una decisión, este es determinado de la
multiplicación de los resultados esperados por sus probabilidades
respectivas, los resultados entonces son sumados hasta llegar al EMV. es
una técnica de análisis que hace el cálculo para determinar el promedio de
todos los resultados posibles cuando el futuro exige una serie de
situaciones particulares que pueden o no en última instancia suceder. estos
escenarios pueden ser interpretados como posibles de forma individual.
Una utilización común de esta técnica se lleva a cabo dentro de una técnica
como la realización de árboles de decisión. el análisis del valor monetario
esperado lo que también puede hacer referencia a nagrama, puede
realizarse en cualquier ciclo de vida del proyecto.
VII. ÁRBOLES DE DECISIÓN: Técnica que permite analizar decisiones
secuenciales basada en el uso de resultados y probabilidades asociadas.
Los árboles de decisión se pueden usar para generar sistemas expertos,
búsquedas binarias y árboles de juegos, los cuales serán explicados
posteriormente.
VIII. MODELADO Y SIMULACIÓN: En general un modelo puede ser entendido
como una representación, bien sea abstracta, análoga, fenomenológica o
idealizada, de un objeto que puede ser real o ficticio. En este caso y por su
naturaleza, el programa de maestría propuesto se ocupará de modelos
fenomenológicos y/o modelos de procesos que requieren el uso formal de
herramientas matemáticas y/o computacionales para representar algún
sistema y su comportamiento.
Mediante el modelado se busca mejorar el conocimiento y la comprensión
de un fenómeno o proceso y ello involucra el estudio de la interacción entre las
partes de un sistema y el sistema como un todo. Desde esta perspectiva es
apropiado afirmar que las teorías están integradas por dos grandes elementos
conceptuales no del todo separables:
a) Un formalismo, es decir, un aparato matemático con unas reglas operativas
para calcular y
b) una interpretación, es decir, una ontología que cuenta, en correspondencia
con el formalismo, cuál es la imagen de los fenómenos, de los procesos y
del mundo que la teoría pretende describir o explicar.
El modelado permite, al nivel de la teoría, acercar el formalismo científico
a su interpretación con el fin de lograr una mejor comprensión, explicación y
descripción de los sistemas estudiados. Sin embargo, uno de los desafíos más
grandes de la ciencia en general, tal como lo refiere el documento Science2020,
es el de integrar las teorías, sus modelos y la experimentación.
IX. MÉTODO PERT: Básicamente es un método para analizar las tareas
involucradas en completar un proyecto dado, especialmente el tiempo para
completar cada tarea, e identificar el tiempo mínimo necesario para
completar el proyecto total.
MÉTODOS DE CERTIDUMBRE:
I. PROGRAMACIÓN LINEAL:
Corresponde a un algoritmo a través del cual se resuelven situaciones
reales en las que se pretende identificar y resolver dificultades para aumentar la
productividad respecto a los recursos (principalmente los limitados y costosos),
aumentando así los beneficios. El objetivo primordial de la Programación Lineal es
optimizar, es decir, maximizar o minimizar funciones lineales en varias variables
reales con restricciones lineales (sistemas de inecuaciones lineales), optimizando
una función objetivo también lineal.
Los resultados y el proceso de optimización se convierten en un respaldo
cuantitativo de las decisiones frente a las situaciones planteadas.
El primer paso para la resolución de un problema de programación lineal
consiste en la identificación de los elementos básicos de un modelo matemático,
estos son:
Función Objetivo.
Variables.
Restricciones
El siguiente paso consiste en la determinación de los mismos, para lo cual
proponemos seguir la siguiente metodología:
La función objetivo tiene una estrecha relación con la pregunta general
que se desea responder. Sí en un modelo resultasen distintas preguntas, la
función objetivo se relacionaría con la pregunta del nivel superior, es decir, la
pregunta fundamental. Así por ejemplo, si en una situación se desean minimizar
los costos, es muy probable que la pregunta de mayor nivel sea la que se
relacione con aumentar la utilidad en lugar de un interrogante que busque hallar la
manera de disminuir los costos.
Similar a la relación que existe entre objetivos específicos y objetivo
general se comportan las variables de decisión respecto a la función objetivo,
puesto que estas se identifican partiendo de una serie de preguntas derivadas de
la pregunta fundamental. Las variables de decisión son en teoría factores
controlables del sistema que se está modelando, y como tal, estas pueden tomar
diversos valores posibles, de los cuales se precisa conocer su valor óptimo, que
contribuya con la consecución del objetivo de la función general del problema.
Cuando hablamos de las restricciones en un problema de programación
lineal, nos referimos a todo aquello que limita la libertad de los valores que pueden
tomar las variables de decisión.
La mejor manera de hallarlas consiste en pensar en un caso hipotético en
el que decidiéramos darle un valor infinito a nuestras variables de decisión, por
ejemplo, ¿qué pasaría si en un problema que precisa maximizar sus utilidades en
un sistema de producción de calzado decidiéramos producir una cantidad infinita
de zapatos? Seguramente ahora nos surgirían múltiples interrogantes, como por
ejemplo:
¿Con cuánta materia prima cuento para producirlos?
¿Con cuánta mano de obra cuento para fabricarlos?
¿Pueden las instalaciones de mi empresa albergar tal cantidad de
producto?
¿Podría mi fuerza de mercadeo vender todos los zapatos?
¿Puedo financiar tal empresa?.
La fábrica de Hilados y Tejidos "SALAZAR" requiere fabricar dos tejidos de
calidad diferente T y T’; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108 Kg
de hilo c. Para obtener un metro de T diariamente se necesitan 125 gr de a, 150 gr
de b y 72 gr de c; para producir un metro de T’ por día se necesitan 200 gr de a,
100 gr de b y 27 gr de c.
El T se vende a $4000 el metro y el T’ se vende a $5000 el metro. Si se
debe obtener el máximo beneficio, ¿cuántos metros de T y T’ se deben fabricar?
El problema se recomienda leer en más de una ocasión para
facilitar el reconocimiento de las variables, además es muy recomendable la
elaboración de tablas o matrices que faciliten una mayor comprensión del mismo.
PASO 1: "FORMULAR EL PROBLEMA"
Para realizar este paso partimos de la pregunta central del problema.
¿Cuántos metros de T y T’ se deben fabricar?
Y la formulación es:
“Determinar la cantidad de metros diarios de tejido tipo T y T’ a fabricar teniendo
en cuenta el óptimo beneficio respecto a la utilidad”.
PASO 2: DETERMINAR LAS VARIABLES DE DECISIÓN
Basándonos en la formulación del problema nuestras variables de decisión
son:
XT: Cantidad de metros diarios de tejido tipo T a fabricar
XT’: Cantidad de metros diarios de tejido tipo T’ a fabricar
PASO 3: DETERMINAR LAS RESTRICCIONES DEL PROBLEMA
En este paso determinamos las funciones que limitan el problema, estas
están dadas por capacidad, disponibilidad, proporción, no negatividad entre otras.
De disponibilidad de materia prima:
0,125XT + 0,200XT’ <= 500 Hilo “a”
0,150XT + 0,100XT’ <= 300 Hilo “b”
0,072XT + 0,027XT’ <= 108 Hilo “c”
De no negatividad
XT,XT’ >= 0
PASO 4: DETERMINAR LA FUNCIÓN OBJETIVO
En este paso es de vital importancia establecer el contexto operativo del
problema para de esta forma determinar si es de Maximización o Minimización. En
este caso abordamos el contexto de beneficio por ende lo ideal es Maximizar.
Función Objetivo
ZMAX = 4000XT + 5000XT’
PASO 5: RESOLVER EL MODELO UTILIZANDO SOFTWARE O MÉTODOS MANUALES
A menudo los problemas de programación lineal están constituidos por
innumerables variables, lo cual dificulta su resolución manual, es por esto que se
recurre a software especializado, como es el caso de WinQSB, TORA, Lingo o
para modelos menos complejos se hace útil la herramienta Solver de Excel.
II. MÉTODO DE SOLUCIÓN GRÁFICA:
Solo aplica a problemas con dos variables de decisión; sin embargo,
ilustra adecuadamente los conceptos que nos permitirán entender la naturaleza
del problema PL y de allí entender los métodos de solución algebraicos.
III. MÉTODO SIMPLEX:
Es un método analítico de solución de problemas de programación lineal
capaz de resolver modelos más complejos que los resueltos mediante el método
gráfico sin restricción en el número de variables.
El Método Simplex es un método iterativo que permite ir mejorando la
solución en cada paso. La razón matemática de esta mejora radica en que el
método consiste en caminar del vértice de un poliedro a un vértice vecino de
manera que aumente o disminuya (según el contexto de la función objetivo, sea
maximizar o minimizar), dado que el número de vértices que presenta un poliedro
solución es finito siempre se hallará solución.
Este famosísimo método fue creado en el año de 1947 por el
estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich,
con el ánimo de crear un algoritmo capaz de solucionar problemas de m
restricciones y n variables.
La empresa el SAMÁN Ltda. Dedicada a la fabricación de muebles, ha
ampliado su producción en dos líneas más. Por lo tanto actualmente fabrica
mesas, sillas, camas y bibliotecas. Cada mesa requiere de 2 piezas rectangulares
de 8 pines, y 2 piezas cuadradas de 4 pines. Cada silla requiere de 1 pieza
rectangular de 8 pines y 2 piezas cuadradas de 4 pines, cada cama requiere de 1
pieza rectangular de 8 pines, 1 cuadrada de 4 pines y 2 bases trapezoidales de 2
pines y finalmente cada biblioteca requiere de 2 piezas rectangulares de 8 pines, 2
bases trapezoidales de 2 pines y 4 piezas rectangulares de 2 pines. Cada mesa
cuesta producirla $10000 y se vende en $ 30000, cada silla cuesta producirla $
8000 y se vende en $ 28000, cada cama cuesta producirla $ 20000 y se vende en
$ 40000, cada biblioteca cuesta producirla $ 40000 y se vende en $ 60000. El
objetivo de la fábrica es maximizar las utilidades.
PASO 1: MODELACIÓN MEDIANTE PROGRAMACIÓN LINEAL
Las variables:
X1 = Cantidad de mesas a producir (unidades)
X2 = Cantidad de sillas a producir (unidades)
X3 = Cantidad de camas a producir (unidades)
X4 = Cantidad de bibliotecas a producir (unidades)
Las restricciones:
2X1 + 1X2 + 1X3 + 2X4 <= 24
2X1 + 2X2 + 1X3 <= 20
2X3 + 2X4 <= 20
4X4 <= 16
La función Objetivo:
ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4
PASO 2: CONVERTIR LAS INECUACIONES EN ECUACIONES
En este paso el objetivo es asignar a cada recurso una variable de Holgura, dado que todas las restricciones son "<=".
2X1 + 1X2 + 1X3 + 2X4 + 1S1 + 0S2 + 0S3 + 0S4 = 24
2X1 + 2X2 + 1X3 + 0X4 + 0S1 + 1S2 + 0S3 + 0S4 = 20
0X1 + 0X2 + 2X3 + 2X4 + 0S1 + 0S2 + 1S3 + 0S4 = 20
0X1 + 0X2 + 0X3 + 4X4 + 0S1 + 0S2 + 0S3 + 1S4 = 16
De esta manera podemos apreciar una matriz identidad (n = 4), formado por las variables de holgura las cuales solo tienen coeficiente 1 en su respectivo recurso, por el ejemplo la variable de holgura "S1" solo tiene coeficiente 1 en la restricción correspondiente a el recurso 1.
La función objetivo no sufre variaciones:
ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4
PASO 3: DEFINIR LA SOLUCIÓN BÁSICA INICIAL
El Método Simplex parte de una solución básica inicial para realizar todas sus iteraciones, esta solución básica inicial se forma con las variables de coeficiente diferente de cero (0) en la matriz identidad.
1S1 = 24
1S2 = 20
1S3 = 20
1S4 = 16
PASO 4: DEFINIR LA TABLA SIMPLEX INICIAL
Solución: (segundo término)= En esta fila se consigna el segundo término de la solución, es decir las variables, lo más adecuado es que estas se consignen de manera ordenada, tal cual como se escribieron en la definición de restricciones.
Cj = La fila "Cj" hace referencia al coeficiente que tiene cada una de las variables de la fila "solución" en la función objetivo.
Variable Solución = En esta columna se consigna la solución básica inicial, y a partir de esta en cada iteración se van incluyendo las variables que formarán parte de la solución final.
Cb = En esta fila se consigna el valor que tiene la variable que se encuentra a su derecha "Variable solución" en la función objetivo.
Zj = En esta fila se consigna la contribución total, es decir la suma de los productos entre término y Cb.
Cj - Zj = En esta fila se realiza la diferencia entre la fila Cj y la fila Zj, su significado es un "Shadow price", es decir, la utilidad que se deja de recibir por cada unidad de la variable correspondiente que no forme parte de la solución.
Solución inicial:
PASO 5: RREALIZAR LAS ITERACIONES NECESARIAS
Este es el paso definitivo en la resolución por medio del Método Simplex, consiste en realizar intentos mientras el modelo va de un vértice del poliedro objetivo a otro.
El procedimiento a seguir es el siguiente:
1. Evaluar que variable entrará y cual saldrá de la solución óptima:
Maximizar MinimizarVariable que entra La más positiva de los Cj - Zj La más negativa de los Cj - Zj
Variable que sale
Siendo b los valores bajo la celda solución y a el valor
correspondiente a la intersección entre b y la variable que entra. La
menos positiva de los b/a.
Siendo b los valores bajo la celda solución y a el valor correspondiente a la
intersección entre b y la variable que entra. La más positiva de los
IV. MÉTODO DE TÉCNICA M O VARIABLE ARTIFICIAL:
Una variable artificial es un truco matemático para convertir inecuaciones
">=" en ecuaciones, o cuando aparecen igualdades en el problema original, la
característica principal de estas variables es que no deben formar parte de la
solución, dado que no representan recursos. El objetivo fundamental de estas
variables es la formación de la matriz identidad.
Estas variables se representa por la letra "A", siempre se suman a las
restricciones, su coeficiente es M (por esto se le denomina Método de la M
grande, donde M significa un número demasiado grande muy poco atractivo para
la función objetivo), y el signo en la función objetivo va en contra del sentido de la
misma, es decir, en problemas de Maximización su signo es menos (-) y en
problemas de Minimización su signo es (+), repetimos con el objetivo de que su
valor en la solución sea cero (0).
Los pasos básicos del método M son los siguientes:
1) Exprese el problema en forma estándar transformando las inecuaciones en
ecuaciones introduciendo variables de holgura.
2) Agregue variables no negativas al lado izquierdo de cada una de las
ecuaciones correspondientes a las restricciones de tipo (>=) o (=). Estas
variables se denominan variables artificiales y su adición hace que las
restricciones correspondientes.
Esta dificultad se elimina asegurando que las variables sean 0 en la
solución final. Esto se logra asignando una penalización muy grande por unidad a
estas variables en la función objetivo. Tal penalización se designará como –M para
problemas de maximización y +M para problemas de minimización.
3) Utiliza las variables artificiales en la solución básica inicial; sin embargo la
función objetivo de la tabla inicial se prepara adecuadamente para
expresarse en términos de las variables no básicas únicamente. Esto
significa que los coeficientes de las variables artificiales en la función
objetivo deben ser 0 un resultado que puede lograrse sumando múltiplos
adecuados de las ecuaciones de restricción al renglón objetivo.
4) Proceda con los pasos regulares del método simplex.
EJEMPLO:
Minimizar
Sujeto a:
Minimizar
Sujeto a:
Minimizar
Sujeto a:
Minimizar
Sujeto a:
V.B. Z X1 X2 X3 S1 S2 R1 Solución
Z 1 -3 -2 -4 0 0 -M 0
R1 0 2 2 3 -1 0 1 15
S2 0 2 3 1 0 1 0 12
V.B. Z X1 X2 X3 S1 S2 R1 Solución
Z 1 -3+2M -2+2M -4+3M -M 0 0 15M
R1 0 2 2 3 -1 0 1 15
S2 0 2 3 1 0 1 0 12
Criterio para seleccionar la variable entrante:
Maximización: El valor mayor negativo del renglón Z.
Minimización: El valor mayor positivo del renglón Z.
V.B. Z X1 X2 X3 S1 S2 R1 Solución
Z 1 -1/3 2/3 0 -4/3 0 4/3-M 20
X3 0 2/3 2/3 1 -1/3 0 1/3 5
S2 0 4/3 7/3 0 1/3 1 -1/3 7
V.B. Z X1 X2 X3 S1 S2 R1 Solución
Z 1 -5/7 0 0 -10/7 -2/7 10/7-M 18
X3 0 2/7 0 1 -3/7 -2/7 3/7 3
X2 0 4/7 1 0 1/7 3/7 -1/7 3
V. MÉTODO DE DOS FASES:
Es una variante del Algoritmo simplex, que es usado como alternativa al
Método de la Gran M, donde se evita el uso de la constante M para las variables
artificiales.
Fase Uno: Minimizar la suma de las variables artificiales del modelo. Si el
valor de la Z óptima es cero, se puede proseguir a la Fase Dos, de lo
contrario el problema no tiene solución.
Fase Dos: Con base en la tabla reclinable de la fase uno, se elimina de las
restricciones las variables artificiales, y se reemplaza la función objetivo, por
la función objetivo original y se resuelve a partir de la resultante, con el
método Simplex tradicional.
PROBLEMA # 1
Minimizar
Sujeto a:
Minimizar
Sujeto a:
FASE I
Minimizar
Sujeto a:
Minimizar
Sujeto a:
V.B. Z X1 X2 S1 S2 R1 R2 Solución
Z 1 0 0 0 0 -1 -1 0
R1 0 2 3 -1 0 1 0 36
R2 0 3 6 0 -1 0 1 60
V.B. Z X1 X2 S1 S2 R1 R2 Solución
Z 1 5 9 -1 -1 0 0 96
R1 0 2 3 -1 0 1 0 36
R2 0 3 6 0 -1 0 1 60
V.B. Z X1 X2 S1 S2 R1 R2 Solución
Z 1 1/2 0 -1 1 /2 0 3/2 6
R1 0 1/2 0 -1 1 /2 1 -1/2 6
X2 0 1/2 1 0 -1/6 0 1/6 10
V.B. Z X1 X2 S1 S2 R1 R2 Solución
Z 1 0 0 0 0 -1 -1 0
X1 0 1 0 -2 1 2 -1 12
X2 0 0 1 1 -2/3 -1 2/3 4
FASE II.
Minimizar
V. Básica Z X1 X2 S1 S2 Solución
Z 1 -2000 -500 0 0 0
X1 0 1 0 -2 1 12
X2 0 0 1 1 -2/3 4
V. Básica Z X1 X2 S1 S2 Solución
Z 1 0 0 -3500 5000/3 26000
X1 0 1 0 -2 1 12
X2 0 0 1 1 -2/3 4
V. Básica Z X1 X2 S1 S2 Solución
Z 1 -5000/3 0 -500/3 0 6000
S2 0 1 0 -2 1 12
X2 0 2/3 1 -1/3 0 12
VI. MÉTODO Y DUAL SIMPLEX:
Primero se debe expresar el modelo en formato estándar, agregando las
variables de holgura y de exceso que se requieran.
Enseguida, en las ecuaciones que tengan variables de exceso (resultantes
de restricciones de tipo >), se debe multiplicar por (-1) en ambos lados, para hacer
positivo el coeficiente de la variable de exceso, y formar así un vector unitario que
nos permita tomar esta variable de exceso como una variable básica inicial. sin
necesidad de agregar una variable artificial en esa restricción.
Al hacer lo anterior se logra que debajo de las variables básicas aparezca
una matriz identidad, que es la que el simplex siempre toma como base inicial.
Obtendremos que los términos del lado derecho de las ecuaciones multiplicadas
por (-1) quedan con signo negativo, lo cual hace que la solución inicial sea
infactible.
Es importante destacar que este proceso es muy útil ya que en muchos
modelos evita la inclusión de variables artificiales en el momento de transformar
un modelo a formato estándar.
El algoritmo para resolver un modelo de maximización es el siguiente:
Paso 1: Hallar una solución básica inicial infactible e inmejorable.
Escribir el tablero inicial tomando a las variables de holgura y de exceso
como variables básicas iniciales
Paso 2: Prueba de factibilidad
Si todas las variables básicas son no negatívas, la actual solución es la
óptima.
Si hay al menos una variable básica negativa, seleccionar como variable
de salida, (llamémosla (XB)s ), a aquella con el valor mas negativo. Los empates
se pueden romper arbitrariamente.
Paso 3: Prueba de inmejorabilidad
Sí en el renglón de la variable básica de salida (XB)s todos los
coeficientes de reemplazo con las variables no básicas son no negativos, la
solución del modelo es óptima ¡limitada. Se termina el proceso.
Si en el renglón de la variable básica de salida (XB)s, hay al menos un
coeficiente de intercambio negativo , se efectúan los cocientes entre el efecto neto
de cada variable no básicas y su correspondiente coeficiente de intercambio
negativo. Es decir, siendo (XB)s la variable de salida se calculan todos los
cocientes.
Se toma como variable de entrada (Llamémosla Xe) a aquella que
corresponda al mínimo de los cocientes del anterior conjunto.
Si la variable de entrada es Xe el elemento pivote será el elemento (Se)s
El empate se puede romper arbitrariamente.
Aplicar la operación de pivoteo para generar la nueva tabla, en la cual
aparezca Xe como variable básica en lugar de la variable de salida (XB)s
Repetir el algoritmo a partir del paso 2.
Sea el siguiente modelo:
Maximi
zar
Z
=
-
2
X
1
-
2X
2
-
3X
3
Sujeto a :
2
X
1
+4
X2
+2
X3 >
1
0
3
X
1
-
3X
2
+9
X3 =
1
2
con X1, X2, X3 > 0
Expresemos el modelo en formato estándar
Maximi
zar
Z
=
-
2
X
1
-
2X
2
-
3X
3
Sujeto a :
2
X
1
+4
X2
+2
X3
-
I
E
1 =
1
0
3
X
1
-
3X
2
+9
X3
-
I
E
2 =
1
2
Multipliquemos por (-1) en ambos lados de las ecuaciones, para formar los
vectores unitarios, requeridos para contar con una base inicial unitaria.
Maximi
zar
Z
=
-
2
-
2X
-
3
X
1 2
X
3
Sujeto a :
-
2
X
1
-
4X
2
-
2
X
3
+I
E1 =
-
1
0
-
3
X
1
+3
X2
-
9
X
3
+I
E2 =
-
1
2
Paso 1.
Tomando las variables básicas iniciales hacemos lo siguiente:
Paso 2
Sale E2 = (XB)2 o sea s = 2
Paso 3
Calculando los cocientes para todo (Sj)2 < 0 obtenemos:
Es decir que X3 es la variable de entrada( entonces e = 3) y el elemento pivote es
el (Se)s = (S3)2 = -9
Efectuando el pivoteo obtenemos la tabla siguiente:
Tabla 1 (maximizar)
Repitiendo el algoritmo desde el paso 1, obtenemos:
Sale E1 = (XB)1 y entra X2 por lo cual obtenemos la siguiente tabla
Tabla 2
Como se observa, ahora estamos en el óptimo.
En definitiva:
X2* = 11/7
X3* = 13/7
Z* = – 61/7
VII. Método de transporte
El problema general del transporte se refiere a la distribución de
mercancía desde cualquier conjunto de centro de suministro, denominados
orígenes (fuentes), hasta cualquier conjunto de centros de recepción, llamados
destinos, de tal forma que se minimicen los costos totales de distribución. Cada
origen tiene que distribuir ciertas unidades a los destinos y cada destino tiene
cierta demanda de unidades que deben recibir de los orígenes.
Como se puede observar cualquier modelo de transporte se compone de
unidades de un bien a distribuir, m orígenes, n destinos, recursos en el origen,
demandas en los destinos y costos de distribución por unidad. Adicionalmente, se
tienen varios supuestos:
Supuesto de requerimientos: cada origen tiene un suministro fijo de
unidades que se deben distribuir por completo entre los destinos.
Supuesto de costo: el costo de distribuir unidades de un origen a un destino
cualquiera es directamente proporcional al número de unidades
distribuidas.
Propiedad de soluciones factibles: un problema de transporte tiene
soluciones factible si y sólo si la sumatoria de recursos en lo m orígenes es
igual a la sumatoria de demandas en los destinos.
Propiedad de soluciones enteras: En los casos en los que tanto los
recursos como las demandas toman un valor entero, todas las variables
básicas (asignaciones), de cualquiera de las soluciones básicas factibles
(inclusive la solución optima), asumen también valores enteros.
Debido a la particularidad del modelo de transporte la forma tabular
Símplex adquiere una estructura que facilita el proceso de asignación a las
variables básicas, tal se muestra a continuación:
En los renglones se ubican los orígenes indicando en la columna de la
derecha los recursos (oferta disponible). En las columnas se ubican los distintos
destinos indicando en el último renglón los totales demandados. En el pequeño
recuadro ubicado en la margen superior derecha se indica el costo de distribuir
una unidad desde el origen hasta ese destino y en la parte inferior de cada
recuadro se registran las asignaciones Xi para cada variable. En los casos donde
la sumatoria de los recursos y las demanda no sean las mismas, se agrega un
origen o destino ficticio con la cantidad que permita cumplir la propiedad de
soluciones factibles.
Después de planteado el modelo de transporte, el siguiente paso es
obtener una solución básica factible, la cual se puede obtener a partir de
cualquiera de los 3 criterios siguientes:
Regla de la esquina noroeste.
Método de la ruta preferente.
Método de aproximación de Vogel
Antes de explicar el procedimiento para cada uno de estos criterios de
asignación para encontrar la solución inicial BF, se debe conocer el número de
variables básicas, el cual se determina con la expresión: m + n - 1. En el modelo
anterior 3 + 2 - 1 = 4 variables básicas.
Regla de la esquina noroeste: la primera elección X11, es decir, se inicia
la asignación por la esquina noroeste de tabla. Luego se desplaza a la columna de
la derecha si todavía quedan recursos en ese origen. De lo contrario se mueve al
reglo debajo hasta realizar todas las asignaciones.
Método de la ruta preferente: se fundamenta en la asignación a partir del
costo mínimo de distribuir una unidad. Primero se identifica este costo se realiza la
asignación de recursos máxima posible y luego se identifica el siguiente costo
menor realizando el mismo procedimiento hasta realizar todas las asignaciones.
Método de asignación de Vogel: para cada reglón y columna, se calcula
su diferencia, que se define como la diferencia aritmética entre el costo unitario
más pequeño y el costo menor que le sigue en ese renglón o columna. En el
renglón o columna con la mayor diferencia, se le asigna al menor costo unitario.
Los empates se pueden romper de manera arbitraria.
De estos 3 modelos para encontrar la solución inicial BF, el método de
Vogel ha sido el más utilizado. Considerando que este criterio toma en cuenta los
costos de distribución de forma más eficaz, ya que la diferencia representa el
mínimo costo adicional que se incurre por no hacer una asignación en la celda que
tiene el menor costo ya sea columna o renglón.
Posterior a esta asignación inicial se requiere un procedimiento que
permita las siguientes iteraciones y se obtenga la solución óptima.
Prueba de optimalidad: un solución BF es óptima si y sólo si Cij - Uij -Vij
>= 0 para todo (i,j) tal que Xij es no básica. Primeramente para todo variable
básica de la solución actual se tiene que Cij - Uij -Vij = 0, por lo que se deduce Cij
= Uij -Vij para todo (i,j) tal que Xij es básica. Para los fines de facilitar los diferentes
de las diferente ecuaciones resultantes se asume el valor de U1 como cero.
En cada iteración se determina una variable básica entrante, una variable
básica saliente y luego la nueva solución básica factible. Paso 1: la variable de
entrada se determina a partir de la relación Cij - Uij -Vij, donde la variable Xij con
el resultado más negativo es la que contribuye en una mejor medida a disminuir el
costo total, se debe tener en cuenta que esta disminución va en proporción a la
asignación resultante. Paso 2: la variable básica saliente es aquella variable
básica que disminuya su valor a cero, es decir, es aquella variable de menor
asignación y que participa en la reacción en cadena que se establece para
compensar los cambios de asignar valor a la variable entrante que permitan
satisfacer las restricciones de recursos y demandas. En este punto, se definen dos
tipos variables para receptoras y donadoras, de acuerdo a la variación de signo
que se produzca en el polígono que permite la transferencia desde la variable de
salida a la variable entrante. Paso 3: se encuentra la nueva solución BF, sumando
el valor de la variable básica saliente a las asignaciones de las celdas receptoras y
se resta a las asignaciones de las celdas donadoras.
Para los fines de ejemplo, se selecciona el problema 8.2-8 ubicado en la
página 325 del libro de texto. La Cost-Less Corp., surte sus cuatro (4) tiendas
desde sus cuatro (4) plantas y desea minimizar los costos de distribución. A
continuación se muestra la tabla con las informaciones de los costos de
distribución:
VIII. MÉTODO DE TRASBORDO:
Es una variación del modelo original de transporte que se ajusta a la
posibilidad común de transportar unidades mediante nodos fuentes, destinos y
transitorios, mientras el modelo tradicional solo permite envíos directos desde
nodos fuentes hacia nodos destinos.
Existe la posibilidad de resolver un modelo de transbordo mediante las
técnicas tradicionales de resolución de modelos de transporte y este
procedimiento se basa en la preparación del tabulado inicial haciendo uso de
artificios conocidos con el nombre de amortiguadores, los cuales deben ser
iguales a la sumatoria de las ofertas de los nodos de oferta pura y de coeficiente
cero (0) en materia de costos.
Sin embargo la resolución de un problema de transbordo haciendo uso de
los algoritmos de resolución de modelos de transporte es una idea anacrónica,
teniendo en cuenta la posibilidad de acceso a herramientas de cómputo capaces
de resolver problemas complejos una vez modelados mediante las técnicas de
programación lineal.
La importancia de los modelos de transbordo aumenta con las nuevas
tendencias globales de gestión de cadenas de abastecimiento, en las cuales se
deben de optimizar los flujos logísticos de productos teniendo en cuenta la
importancia de minimizar los costos, asegurar disponibilidad de unidades y
reconociendo la importancia de los centros de distribución en la búsqueda del
equilibrio entre las proyecciones y la realidad de la demanda.
Para poder resolver un problema de transbordo mediante programación
lineal basta con conocer una nueva familia de restricciones, las llamadas
restricciones de balanceo. En un problema de transbordo existen 3 clases de
nodos, los nodos de oferta pura, los de demanda pura y los nodos transitorios que
posibilitan el transbordo y que deben de balancearse para hacer que el sistema
sea viable, es decir, que todas las unidades que ingresen a un nodo sean iguales
a las que salgan del mismo (unidades que salen + unidades que conserve el
nodo).
La figura muestra una serie de nodos y sus respectivas rutas mediante las
cuales se supone distribuir las unidades de un producto, el número que lleva cada
arco (flecha) representa el costo unitario asociado a esa ruta (arco), y las
cantidades que se ubican en los nodos iniciales representan la oferta de cada
planta, así como las cantidades de los nodos finales representa la demanda de
cada distribuidor.
LAS VARIABLES DE DECISIÓN
En este caso como en la mayoría las variables de decisión deben
representar la cantidad de unidades enviadas por medio de cada ruta. Es muy
aconsejable denotar cada nodo con un número para simplificar la definición
nominal de las variables.
Una vez renombrado cada nodo definiremos las variables:
XA,C = Cantidad de unidades enviadas desde P1 hacia T1
XA,D = Cantidad de unidades enviadas desde P1 hacia T2
XB,C = Cantidad de unidades enviadas desde P2 hacia T1
XB,D = Cantidad de unidades enviadas desde P2 hacia T2
XC,D = Cantidad de unidades enviadas desde T1 hacia T2
XC,E = Cantidad de unidades enviadas desde T1 hacia D1
XC,F = Cantidad de unidades enviadas desde T1 hacia D2
XD,F = Cantidad de unidades enviadas desde T2 hacia D2
XD,G = Cantidad de unidades enviadas desde T2 hacia D3
XE,F = Cantidad de unidades enviadas desde D1 hacia D2
XF,G = Cantidad de unidades enviadas desde D2 hacia D3
RESTRICCIONES
Existen en este modelo 3 tipos de restricciones y están estrechamente
relacionadas con los tipos de nodos existentes, para un nodo oferta pura existe la
restricción de oferta; para un nodo demanda pura existe la restricción de
demanda, y para un nodo transitorio y/o transitorio de demanda existe la
restricción de balance. Recordemos que los nodos transitorios son aquellos que
tienen rutas (arcos o flechas) de entrad y salida, y si además este presenta un
requerimiento de unidades se denomina transitorio de demanda.
Restricciones de Oferta:
XA,C + XA,D = 1000
XB,C + XB,D = 1200
Restricciones de demanda:
XD,G + XF,G = 500
Restricciones de balanceo para nodos únicamente transitorios:
Con estas restricciones aseguramos que todas las unidades que lleguen
sean iguales a las unidades que salgan.
XA,C + XB,C - XC,D - XC,E - XC,F = 0
XA,D + XB,D + XC,D - XD,F - XD,G = 0
Restricciones de balanceo para nodos transitorios con requerimientos:
Con estas restricciones aseguramos que todas las unidades que lleguen
sean iguales a la sumatoria de las unidades que salen más los requerimientos del
nodo (demanda).
XC,E - XE,F = 800
XC,F + XD,F + XE,F - XF,G = 900
FUNCIÓN OBJETIVO
En este caso la definición de la función objetivo se limita a la consignación
de cada ruta con su respectivo costo bajo el criterio "minimizar".
ZMIN = 3XA,C + 4XA,D + 2XB,C + 5XB,D + 7XC,D + 8XC,E + 6XC,F + 4XD,F +
9XD,G + 5XE,F + 3XF,G
IX. MÉTODO DE RUTA MÍNIMA:
El método de la ruta más corta es un método de programación lineal, que
permite buscar la solución a un problema de optimización que resulte de una
combinatoria y de diferentes aplicaciones, el objetivo de este método está en
encontrar rutas cortas o de menor costo, según sea el caso, que va desde un nodo
especifico hasta cada uno de los demás nodos de la red. En este sentido un nodo
es una representación gráfica en forma de circulo, este nodo es muy importante ya
que denota los orígenes y destinos del problema que se realice, asimismo una red
representa un conjunto de puntos y líneas que conectan pares de puntos, estos
puntos son los que llamaremos nodos y las líneas serían las aristas.
Este método es muy importante ya que por medio de este modelo se
pueden resolver de manera rápida, ya que pueden formularse como modelos de
redes obteniendo soluciones enteras sin necesidad de restricciones (aunque en
algunos casos pudieran tenerlas), asimismo se puede decir que no importa que
tan grande sea el problema se puede resolver por pequeños algoritmos. Por otra
parte según la página www.ptolomeo.unam.mx en sus conceptos básicos, capitulo
1 señala la importancia de este método:
El problema de la Ruta más Corta es fundamental en muchas áreas, como son:
investigación de operaciones, ciencia de la computación e ingeniería. Algunas de
las razones son:
i. La amplia variedad de aplicaciones prácticas como es el envío de algún
material entre dos puntos específicos de la forma más eficiente, económica
o rápida.
ii. Existen métodos de solución eficientes, los cuales al ser aplicados a una
red con características específicas (a cíclica y con costos no negativos),
proveen una solución exacta a un tiempo y costo razonables.
iii. Se puede utilizar como inicio en el estudio de modelos complejos de redes,
esto es, cuando no se conoce la estructura de la red se pueden aplicar
algoritmos para conocer algunas características de la red (presencia de
ciclos negativos).
iv. Se utiliza frecuentemente como sub-problemas (subrutinas) en la solución
de problemas combinatorios y redes, así en el caso de problemas para los
cuales no existe un algoritmo de solución exacto (p. e. problemas NP-
completos), la aplicación de algoritmos de ruta más corta, resultan
auxiliares para encontrar una buena solución.
En cuanto a sus aplicaciones este modelo tiene muchas aplicaciones en la
vida práctica, dentro de las que podemos mencionar:
Transporte.
Horarios de operadores telefónicos.
Planeación de tráfico urbano.
Trasbordo.
En las redes eléctricas.
Diseño de rutas de vehículos.
Telecomunicaciones.
Planeación de inventarios.
Planeación de producción, entre otros.
“Considere la siguiente red dirigida (para una red indirecta, haga que los arcos
estén dirigidos en ambas direcciones, luego aplique la misma formulación. Note
que en este caso usted tiene Xij y Xji variables. El objetivo es encontrar el camino
más corto desde el nodo 1 al nodo 7. La red sería:
Figura 2.Ejercicio Ejemplo
Para encontrar la función objetivo para los costos se plantea:
MinZ(x) = 15X12+10X13+8X32 +4X35+6X24+17X27+4X45+5X47+2X56+6X67
Para hacer las ecuaciones hay que tomar en cuenta:
Entra al nodo es +
Sale del nodo es -
S.A.:
Nodo 1: X12+X13 = 1
Nodo 2: X12+X32-X24-X27 = 0
Nodo 3: X13-X32-X35 = 0
Nodo 4: X24-X47-X45 = 0
Nodo 5: X35+X45 – X56 = 0
Nodo 6: X56-X67 = 0
Nodo 7: X27+X47+X67 = 1
X. MÉTODO DE FLUJO MÁXIMO:
Existe un flujo que viaja desde un único lugar de origen hacia un único
lugar de destino a través de arcos que conectan nodos intermediarios. Los arcos
tienen una capacidad máxima de flujo y se trata de enviar desde la fuente al
destina la mayor cantidad posible de flujo.
Hay problemas donde lo importante es la cantidad de flujo que pasa a
través de la red como por ejemplo: en las líneas de oleoductos, redes eléctricas o
de transmisión de datos. Por esta razón en dichos problemas se determina el flujo
máximo que pasa a través de una red.
Definiciones básicas
Flujo: Circulación de unidades homogéneas de un lugar a otro.
Capacidad de flujo: es la capacidad de unidades que pueden entrar por el nodo
fuente y salir por el nodo destino.
Origen o fuente de flujo: nodo por el cual el flujo ingresa.
Destino o Sumidero de flujo: nodo por el cual el flujo sale.
Capacidades residuales: capacidades restantes unas vez que el flujo pasa el
arco.
Ford Fulkerson
Para la resolución de problemas de flujo máximo se requiere el uso del
método Ford Fulkerson. Este método propone buscar caminos en los que se
pueda aumentar el flujo hasta que se alcance el flujo máximo, la idea es encontrar
una ruta de penetración con un flujo positivo neto que una los nodos de origen y
destino.
El flujo es siempre positivo y con unidades enteras.
El flujo a través de un arco es menor o igual que la capacidad.
El flujo que entra en un nodo es igual al que sale de él.
Resolución de problema
Para resolver un problema de flujo máximo se debe seguir los siguientes pasos:
Se identifica el nodo origen y destino.
Se parte desde el nodo de origen y se escoge el arco que posea mayor flujo
Se identifica los nodos de transbordo.
Repetir como si el nodo intermediario fuera el nodo origen.
Se calcula "k" y las capacidades nuevas.
Dado el resultado se cambian las capacidades y se repite el mismo procedimiento
desde el inicio.
Hallar el flujo máximo del siguiente problema:
Método Ford Fulkerson
El nodo de origen como se puede observar es el numero 1 de color
amarillo, y el nodo de destino es el numero 5 de color azul.
Se escoge desde el nodo de origen aquel flujo que sea el mayor, en este
caso es 30, y va dirigido al nodo numero 3.
Se identifica el nodo de transbordo como [30,1], 30 es la capacidad, y 1 es
el nodo del cual proviene la capacidad y luego repetimos todo el proceso, como si
el nodo intermediario fuese el nodo de origen. Se tiene como flujo mayor 20 del
nodo numero 3 al nodo número 5, con el nodo de transbordo como [20,5].
Ahora que hemos llegado al nodo de destino, procedemos a calcular "k" y
las capacidades nuevas.
K=min(∞,30,20)
K=20
C13,31 =(30-20, 0+20)
C13,31 =(10, 20)
C35,53 =(20-20, 0+20)
C35,53 =(0, 20).
Luego de haber calculado las nuevas capacidades, es necesario reemplazarlas.
Se realiza el proceso otra vez, haciendo la ruta con los mayores flujos.
K=min(∞,20,40,10,20)
K=10
C12,21 =(20-10, 0+10)
C12,21 =(10, 10)
C23,32 =(40-10, 0+10)
C23,32 =(30, 10)
C34,43 =(10-10, 5+10)
C34,43 =(0, 15).
C45,54 =(20-10, 0+10)
C45,54 =(10, 10).
Volvemos a hacer el proceso y escogemos el camino 1,2. Como
se puede observar si se tomara rumbo del nodo 2 al nodo
3 terminaría trancado, obligándose a volver al nodo origen, por lo que se toma el
camino 2,5.
K=min(∞,10,20)
K=10
C12,21 =(10-10, 10+10)
C12,21 =(0, 20)
C25,52 =(20-10, 0+10)
C25,52 =(10, 10)
Se actualizan las capacidades y procedemos a resolver de nuevo. Esta vez
agarraremos el camino de 1,3.
K=min(∞,10,10,10)
K=10
C13,31 =(10-10, 20+10)
C13,31 =(0, 30)
C32,23 =(10-10, 30+10)
C32,23 =(0, 40)
C25,52 =(10-10, 10+10)
C25,52 =(0, 20)
Y por último escogemos el camino 1,4.
K=min(∞,10,10)
K=10
C14,41 =(10-10, 0+10)
C14,41 =(0, 10)
C45,54 =(10-10, 10+10)
C45,54 =(0, 40)
Reemplazando las nuevas capacidades, nos queda de la siguiente forma, las
capacidades del nodo de origen quedan como 0, por lo cual seguimos a sumar a
todas las K y ahi conseguimos el flujo máximo.
Flujo Máximo = Σ K.
Flujo Máximo = 20+10+10+10+10.
Flujo Máximo = 60.
El flujo máximo que puede pasar del nodo origen 1 hasta el nodo destino es de 60.
