Upload
carmenmoyon55
View
5
Download
0
Embed Size (px)
Citation preview
UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINISTRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORIA
CATEDRA
INVESTIGACION OPERATIVA
PORTAFOLIO ESTUDIANTIL
NOMBRE:
CARMEN ELENA MOYÓN GUADALUPE
6to SEMESTRE “A”
DOCENTE:
MSC. MARLON VILLA
UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINISTRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORIA
CATEDRA
INVESTIGACION OPERATIVA
PORTAFOLIO ESTUDIANTIL
NOMBRE:
CARMEN ELENA MOYÓN GUADALUPE
6to SEMESTRE “A”
DOCENTE:
MSC. MARLON VILLA
UNIDAD I
EL MÉTODO DE TRANSPORTE
Es un método de programación lineal que nos permite asignar artículos de un
conjunto de orígenes a un conjunto de destinos de tal manera que se optimice la
función objetivo.
Esta técnica se utiliza especialmente en organizaciones que producen el mismo
producto en numerosas plantas y que envía sus productos a diferentes destinos
(Centros de distribución, almacenes). También se aplica en distribución, análisis de
localización de plantas y programación de la producción.
Se han desarrollado diferentes enfoques para resolver este problema de
distribución, tales como: El método de la esquina noroeste, el método modificado
de la esquina noroeste (celda mínima), método del trampolín (Cruce de arroyo,
steppingstone), método de la distribución modificada (MODI), método de
aproximación de Vogel y el método simplex.
Para que un problema pueda ser solucionado por el método de transporte, este
debe reunir tres condiciones:
1) La función objetivo y las restricciones deben de ser lineales.
2) Los artículos deben de ser uniformes e intercambiables, los coeficientes de todas
las variables en la ecuación deben de ser 0 o 1.
3) La suma de las capacidades de las fuentes debe ser igual a la suma de los
requerimientos de los destinos, si alguna desigualdad existe una variable de
holgura deberá ser añadida.
El objetivo del modelo de programación es minimizar el costo.
MÉTODO DEL COSTO MÍNIMO
El método del costo mínimo o de los mínimos costoses un algoritmo desarrollado
con el objetivo de resolver problemas de transporte, arrojando mejores resultados
que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que
presentan menores costos. El diagrama de flujo de este algoritmo es mucho más
sencillo que los anteriores se trata de asignar la mayor cantidad de unidades
posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa
de toda la matriz hasta finalizar el método
ALGORITMO DE RESOLUCIÓN
1.- De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este
se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades posible,
cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda.
En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna
afectada, restándole la cantidad asignada a la celda.
2.- Elimine la fila, cuya oferta o demanda sea (0) si dado el caso ambas son cero
arbitrariamente se elija cual eliminar y la restando se deja con demanda u oferta
cero (0) según sea el caso.
3.- Una vez en este paso existen dos posibilidades
1) Que quede un solo renglón o columna, si este es el caso se ha llegado al
final el método.
2) Es que quede más de un renglón o columna, si este es el caso inicie de
nuevo el "Paso 1".
La matriz debe estar en equilibrio, y si no lo están se puede aumentar filas o
columnas Ejemplo:
Método del costo mínimo
Z = 12.500
MÉTODO DE LA APROXIMACIÓN DE VOGUEL
1) Determinar para cada fila y columna una medida de penalización, restando
los dos costos menores en fila y columnas.
2) Con la mayor Penalización
3) De la fila o columna de mayor penalización escoja la celda con el menor
costo y asigne la mayor cantidad posible.
4) Si queda sin tachar una fila o columna termina se detiene
5) si queda sin tachar la fila o columna con oferta y demanda positiva aplique
el método delo costo mínimo u termine.
6) si todas las filas y columnas que no se tacharon tiene oferta (0) o demanda
(0) determine las variables básicas (0) cero determinando el método del
costo mínimo.
7) Si no se presenta ningún de los casos anteriores vuelva al paso 1 hasta que
la oferta y la demanda se haya agotado.
EJEMPLOS:
MÉTODO DE DISTRICUCION MODIFICADA (MODI)
El Métod
o MODI nos ofrece la oportunidad de calcular costos marginales basados en los
valores de las variables de decisión del modelo, pero aunado a esto también nos
indica la celda no básica en la cual se deben realizar los ajustes para obtener una
mejor solución.
ALGORITMO
1. Usar la solución factible calculada por cualquier método (MEN, VAM O MCM ) y
las siguientes (a) y (b) para determinar el costo marginal de enviaar la materia
prime para cada una de las rutas.
2. Si existe por lo menos un c.m. negativo, tomar la celda con mayor valor
negativo. Crear un circuito con todos los vértices en celdas de variables básicas. Es
decir, encontrar la trayectoria de la variable “no básica” que entrará a la solución.
3. Ajustar el valor de Xij en las celdas del circuito, comenzando por sumar la
variable θ a la celda seleccionada en el Paso 2, en el sentido de las manecillas del
reloj, y alternando una resta y suma de θ en cada celda de la trayectoria hasta
regresar a la celda primera, resolver una desigualdad (≥0) para θ y ajustar la
solución. En todo caso volver al Paso 1.
EJEMPLOS:
Z= 16.700
METODO DE ASIGANACIÓN
Tiene similitud con el de Vogel, debo buscar tachar los tres ceros utilizando el
menor número de líneas
Z= 4+3+1+9 Z= 17
MÉTODO DEL CRUCE DEL ARROYO (TRAMPOLIN)
El método del cruce del arroyo también llamado algoritmo de Stepping –Stone o
método del paso a paso es un método que nos ayuda a calcular cuál sería la
variación del costo mínimo, además a buscar la solución óptima de un problema de
transporte solucionado por algunos de los métodos (Vogel, Costo mínimo, Esquina
Noroeste entre otros).
Este método parte de una solución factible, la cual es tomada de cualquiera de las
soluciones que arrojan los métodos de asignación.
El Cruce del Arroyo evalúa la solución inicial y mediante iteraciones (procesos
aritméticos) busca mejorarla hasta llegar a la solución óptima. Si la solución de
partida es la más desfavorable en términos económicos, el procedimiento se hará
más dispendioso pues implica más iteraciones hasta aproximarse a la solución
óptima. Por tal motivo entre más acertado sea la solución de la que partiremos,
resultara más confiable la solución óptima que resultara de nuestro procedimiento.
CARACTERÍSTICAS
1. Se debe comenzar a resolver por las celdas vacías.
2. El número de casillas debe ser igual a m+n-1
3. Se deben trazar las líneas solo horizontal y verticalmente.
4. Se puede trazar líneas por celdas llenas o vacías sin utilizarlas.
5. El Circuito debe comenzar en una celda vacía y al recorrer las celdas ocupadas
debe terminar en la misma celda vacía en la que comenzó.
6. Cuando alguno de los índices de mejoramiento arroja un resultado negativo, se
toma el número menor de las celdas con signo negativo (-) y este valor se le suma a
las celdas con signo positivo (+) y se resta a las celdas cuyo signo sea negativo(-).
Estas serán las nuevas asignaciones.
7. Cuando los índices de mejoramiento arrojan como resultado cero (0) o un numero
positivo se puede concluir el ejercicio, es decir, se ha llegado a la solución óptima.
IMPORTANCIA
El Método del Cruce del Arroyo nos permite encontrar la solución óptima a partir del
resultado factible que arrojan las operaciones con los métodos de transporte.
Las casillas no asignadas sean positivas (+) o cero (0), que es la forma como
sabremos que el ejercicio ha llegado a su resultado óptimo.
EJEMPLOS:
RAMIFICACIÓN Y ACOTAMIENTO)
El método de Branch and Bound (o Ramificación y Acotamiento) es un
algoritmo diseñado para la resolución de modelos de programación entera. Sin
embargo es muy frecuente que la naturaleza del problema nos indique que las
variables son enteras o binarias. Su operatoria consiste en resolver éste como si
fuese un modelo de programación lineal y luego generar cotas en caso que al
menos una variable de decisión adopte un valor fraccionario. El algoritmo genera
Programación cuadrática
La programación cuadrática (PC) es el nombre que recibe un procedimiento que
minimiza una función cuadrática de n variables sujeta a m restricciones lineales de
igualdad o desigualdad. De nuevo los problemas de programación cuadrática tienen
restricciones lineales, pero ahora la función objetivo f(x) debe ser cuadrática.
Entonces, la única diferencia entre éstos y un problema de programación lineal es
que algunos términos de la función objetivo incluyen el cuadrado de una variable o
el producto de dos variables. La importancia de la programación cuadrática es
debida a que un gran número de problemas aparecen de forma natural como
cuadráticos (optimización por mínimos cuadrados, con restricciones lineales), pero
además es importante porque aparece como un subproblema frecuentemente para
resolver problemas no lineales más complicados.
UNIDAD II
MODELOS DE REDES
• El problema del transporte y el problema de asignación, forman parte de un tipo
más general de modelos, conocidos como modelos de red.
• Los modelos de red son aplicaciones muy importantes para la logística y la
distribución en la administración, además de tener múltiples aplicaciones en
ingeniería y computación.
• Un modelo de red es un modelo de transbordo con capacidades, el cual puede
adoptar diversas formas, como el modelo de la ruta más corta y el modelo del
flujo máximo y mínimo, el problema de árbol de alcance mínimo, método de
camino crítico, entre otras aplicaciones de la planeación financiera y de
producción.
CARACTERISTICAS
• La principal característica de un modelo de transbordo con capacidades es que
es una red donde las ofertas están en los puntos de origen específicos, las
demandas en los puntos de destino específicos y las alternativas de embarque
se ofrecen por medio de los nodos intermedios, de manera que siguen rutas con
capacidades definidas desde los orígenes hasta los destinos.
Terminología de redes
A continuación se presenta un diagrama de red y sus principales componentes.
Las flechas se conocen como arco o rama de la red. Generalmente el arco
(flecha) de un punto A a B se designa (A, B)
Los puntos/elementos del modelo se conocen como nodos de la red.
En el nodo de la red comúnmente encontrarás un número con un signo positivo o
negativo, el cual denota la oferta (+) y la demanda o requerimientos (-) del nodo.
Una ruta es una secuencia de arcos distintos que conectan a dos nodos. En la red podemos observar las diferentes rutas que puede tomar el flujo por
medio de los arcos o ramas dela red.
Consideraciones importantes:
• Las flechas/líneas de una sola dirección son arcos directos.
• Las líneas con flujo para ambas direcciones son arcos indirectos.
• Una red que tiene solamente arcos directos es una red directa.
• Una red que tiene arcos en ambas direcciones es una red indirecta.
PROBLEMA. El gerente de distribución de una empresa distribuye tractores en
cinco provincias. El gerente tiene 10 aparatos en la provincia, estos tractores deben
ser enviados a las provincias 3 y 4 que demandan 3 y 7 tractores respectivamente.
Elabore el diagrama de red, establezca las capacidades y los costos agregados,
formule el problema, construya la matriz de incidencia (nodo – arco) y establezca la
tabla de transporte.
DIAGRAMA DE RED
CAPACIDADES Y COSTOS AGREGADOS
FORMULACIÓN DEL PROBLEMA
Min
Z= C12X12+ C23X23+ C24X24+ C25X25+ C34X34+ C43X43+ C53X53+ C54X54
Sujeto a:
+X12 =10
- X12 + X23 + X24 + X25 =0
- X23 + X34 – X43 – X53 =-3
- X24 - X34 + X43 - X54 =-7
- X25 + X53 + X54 =0
CONDICION DE NO NEGATIVIDAD
0 ≤ Xij ≤ Uij,
Xij= Flujo del nodo i hasta el nodo j
EL PROBLEMA DE LA RUTA MAS CORTA
GRAFO. Es una serie de nodos unidos por arcos, ramas o aristas
Red. Es un grafo con algún tipo de flujo en sus ramales. Ejemplo: Eléctrica, transporte.
Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente caso [1, 4, 7].
Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, si los arcos tienen la misma dirección se conoce como circuitos, en el siguiente ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].
Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido determinado, es decir que posee un nodo fuente y un nodo destino.
Gráfica orientada o dirigida: Una gráfica orientada es aquella en la cual todos sus ramales se encuentran orientados.
Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.
Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la red, de igual manera no permite la existencia de ciclos.
Bosque. Es una gráfica sin ciclos, se considera también como un conjunto de árboles.
Arborescencia. Es un árbol dirigido con un nodo llamado raíz
EL PROBLEMA DE LA RUTA MAS CORTA
Se refiere a una red, en la que el arco tiene asociado un n° C y J que se interpreta
como la distancia ( costo, tiempo) que hay entre los nodos y el objetivo consiste en
encontrar las rutas más cortas( Económicas, Rápidas) entre un nodo específico y
todos los demás nodos de la recta.
PASOS
1. considere todos los nodos que están conectados con el origen, el
componente de distancia de la etiqueta que se pone a cada nodo es al
distancia desde el origen, el componente predecesor es el origen, están
etiquetas se llaman temporales.
2. de entre todos los nodos con etiquetas temporales escoja un cuyo
componente y distancia sea mínima y etiqueta permanentemente todos los
empates en cualquier punto del algoritmo se rompe arbitrariamente tan
pronto como todos los nodos han sido etiquetados en forma permanente
vaya al paso 4.
3. todo nodo que no tenga etiqueta permanente no tiene etiqueta o su etiqueta
es temporal, considérese todas las etiquetas de los vecinos del nodo, para
cada uno de los nodos calcule las suma de la distancia más los componentes
de la distancia de la etiqueta, si el nodo no está etiquetado, asigne una
etiqueta temporal que consta en esta distancia y la del predecesor si el nodo
en cuestión ya tiene una etiqueta temporal cambie si solo la distancia recién
calculada es menor < que la distancia de la etiqueta actual regrese al paso
2.
4. Las etiquetas permanentes indican la distancia más corta desde el origen a
cada nodo de la recta, también el nodo predecesor en la ruta más corta
hacia cada nodo.
EJEMPLO:
Una persona hace el reparto de cerveza a 7 lugares diferentes de la ciudad de
Riobamba, después de haber obtenido la información necesaria, se establece el
siguiente esquema.
A cada nodo se asocia, la distancia que hay en los nodos
Se empieza minimizar la totalidad de los costos asegurando que cualquiera que
sea sea a través de la ruta más corta
EL PROBLEMA DEL ÁRBOL EXPANDIDO MÍNIMO
La tarea consiste en construir un árbol que conecte todos los nodos de la red con un
costo total mínimo
El algoritmo que nos permite resolver este tipo de problemas es el ALGORITMO
GLOTÓN y se puede hacer de dos formas: el método gráfico y el método Tabular.
MÉTODO GRÁFICO.
1. Empiece en cualquier nodo. Seleccione el arco más barato que parta de ese
nodo. Este es su primer enlace. Forma un segmento de conexión entre dos
nodos. Los nodos restantes se llaman NODOS DESCONECTADOS.
2. Considere todos los arcos que parten del segmento de conexión a los nodos
desconectados. Seleccione el más barato como enlace. Si hay empates rompa
de manera arbitraria. Esto agrega un nuevo nodo al segmento de conexión.
Repita este paso hasta que todos los nodos estén conectados lo cual requiere n
-1 pasos.
MÉTODO TABULAR.
1. Comience con cualquier nodo, se designa este nodo como conectado y se coloca
un V al lado del renglón correspondiente a este nodo. Se tacha el índice de la
columna que corresponde a él.
2. Considerando todos los renglones que tienen V, busque el valor mínimo en las
columnas cuyo índice aún no haya sido tachado y se encierra ese valor en un
círculo. Se rompe arbitrariamente los empates. La columna que contenga a ese
elemento encerrado en un círculo designa al nuevo nodo conectado. Se tacha el
índice de esta columna y se coloca una marca en el renglón correspondiente a
este nodo. Se repite este paso hasta que todos los nodos sean conectados.
3. Una vez que todos los nodos hayan sido conectados, se identifica el árbol
expandido mínimo mediante los elementos circundados.
EL PROBLEMA DEL FLUJO MÁXIMO.
En este problema hay un solo nodo FUENTE ( origen, entrada) y un solo nodo
DESTINO ( sumidero, salida), El problema consiste en determinar el máximo flujo
que se puede enviar desde el nodo fuente al nodo destino, teniendo en cuenta las
capacidades kij sobre el flujo de cada arco (i,j) y que el flujo se debe conservar. Se
utiliza para saber cuál es la cantidad máxima de vehículos, peatones, líquidos o
llamadas telefónicas que pueden entrar y salir del sistema, para reducir los
embotellamientos entre ciertos puntos de partida y destino en una red.
El único requerimiento en ellos es que para cada nodo (que no sea la fuente o el
destino) la relación de equilibrio debe cumplirse:
Flujo que sale = flujo que entra
La cantidad de flujo a lo largo de dicho recorrido es FACTIBLE si:
1. No se excede la capacidad de ningún arco del camino.
2. A excepción de los nodos de entrada y salida se debe cumplir la condición de
conservación:
Flujo que sale = flujo que entra
ALGORITMO PARA RESOLVER ESTE PROBLEMA.
1. Encontrar un camino que vaya del origen al destino y que tenga capacidad mayor
a cero en el sentido deseado.
2. Encontrar la rama de menor capacidad (Pf) del camino seleccionado en el paso
anterior y programar el envío de dicha capacidad (Pf).
3. Para el camino elegido en el paso 1 reducir la cantidad Pf en las ramas
involucradas y aumentar dicha cantidad en el sentido contrario.
4. Repetir el procedimiento desde el paso 1.
5. Si la capacidad final es menor que la capacidad inicial, calcule la diferencia y esta
es la cantidad de flujo a través del arco.
CORTE. Partición del conjunto de nodos en dos clases ajenas, digamos C1 y Cn
donde la fuente está en C1 y el destino en Cn.
CAPACIDAD DE CORTE. Considérense todos los arcos que conectan directamente
un nodo de C1 a un nodo Cn. La suma de las capacidades de esos arcos, en la
dirección C1 – Cn se llama capacidad de corte.
TEOREMA DE FLUJO MÁXIMO Y CORTE MÍNIMO. El flujo máximo de cualquier
red es igual a la capacidad del corte mínimo.