Algoritmos utilizados en la investigación de operaciones

1. Método gráfico (George Bernard Dantzig Ourisson 1947) Definición: Conjunto convexo de R2 Un subconjunto de S de R2 es convexo si todo punto del segmento de la recta que una dos puntos cualesquiera de S es un punto de S. Pasos: 1.- Dibujar el conjunto de desigualdades. 2.- Dibujar la función económica. 3.-Desplazar la función económica paralelamente a la dirección de optimizan sin abandonar el conjunto de restricción 4.- Leer las coordenadas del punto antes de que la recta que representa la función económica abandone la región restringida.

2. Método del Simplex (George Bernard Dantzig Ourisson 1947) Definición: Es un método iterativo que permite ir mejorando la solución en cada paso. Pasos: 1.- Moderación mediante programación linea. 2.- Convertir las inecuaciones en ecuaciones. 3.- Definir la solución básica inicial. 4.- Realizar las iteraciones necesarias.

3. Método de la Ruta mas Corta Definición:Modalidad de problemas de redes, en la cual se debe determinar el plan de rutas que genere la trayectoria con la mínima distancia total, que una un nodo fuente con un nodo destino, sin importar el número de nodos que existan entre estos. Pasos: 1.- La restricción del nodo de origen dice que debe dejar el nodo 1 para ir al 2 o 3. 2.- La restricción del nodo intermedio dice que si siempre que se dirija a un nodo usted deberá dejar ese nodo. 3.- El nodo de destino es similar al nodo de origen dado que se puede alcanzar este nodo solo desde los nodos vecinos.

4. Método de Dijkstra Definición: Es un modelo que se clasifica dentro de los algoritmos de búsqueda. Pasos: 1.- Inicializar todas las distancias en D con un valor infinito relativo, ya que son desconocidas al principio, exceptuando la de x, que se debe colocar en 0, debido a que la distancia de x a x sería 0. 2.- Sea a = x (Se toma a como nodo actual.) 3.- Se recorren todos los nodos adyacentes de a, excepto los nodos marcados. Se les llamará nodos no marcados vi. 4.- Para el nodo actual, se calcula la distancia tentativa desde dicho nodo hasta sus vecinos con la siguiente fórmula: dt(vi) = Da + d(a,vi). Es decir, la distancia tentativa del nodo ‘vi’ es la distancia que actualmente tiene el nodo en el vector D más la distancia desde dicho nodo ‘a’ (el actual) hasta el nodo vi. Si la distancia tentativa es menor que la distancia almacenada en el vector, entonces se actualiza el vector con esta distancia tentativa. Es decir, si dt(vi) < Dvi → Dvi = dt(vi) 5.- Se marca como completo el nodo a. 6.- Se toma como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y se regresa al paso 3, mientras existan nodos no marcados.

5. Metodo Pert: Definición: El método PERT (Project Evaluation and Review Techniques), es un algoritmo basado en la teoría de redes diseñado para facilitar la planificación de proyectos. Pasos: Paso 1: Actividades del proyecto Paso 2: Calcular el tiempo estimado (Duración promedio) y la varianza Paso 3: Diagrama de red Paso 4: Calcular la red Paso 5: Cálculo de la varianza, desviación estándar y probabilidades Paso 6: Establecer el cronograma

6. Método de la ruta critica (Dupont y Remington Rand 1957) Definición: Es un algoritmo basado en la teoría de redes diseñado para facilitar la planificación de proyectos. Pasos: Paso 1: Actividades del proyecto Paso 2: Diagrama de la red Paso 3: Calcular la red Paso 4: Establecer el cronograma

7. Método Punto de Esquina Teorema: Una función lineal definida sobre un conjunto convexo acotado alcanza sus valores máximo y mínimo en los puntos extremos (o vértices). Pasos: 1.- Determinar todos los puntos esquina del conjunto de restricción 2.- Determinar los puntos de esquina que satisfacen todas las desigualdades. 3.- Evaluar el valor de la función económica en cada esquina y determinar los puntos en donde se alcanza el máximo.

8. Método de aproximación de Vogel (William R. Vogel) Definición: Método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos. Pasos: Paso 1 Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas. Paso 2 Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el «Paso 1» se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal). Paso 3 De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0). Paso 4: De ciclo y excepciones

9. Método de la Teoría de redes Definición: Modelación de redes permite la resolución de múltiples problemas de programación matemática mediante la implementación de algoritmos especiales creados para tal fin. Pasos: 1.-Se definen los conjuntos iniciales 2.- Se debe definir de manera arbitraria el primer nodo permanente del conjunto 3.- Ahora se debe seleccionar el nodo del conjunto.

10. Algoritmo de Frank Wolfe ((Marguerite Frank y Philip Wolfe 1956 ) Definición Aplica a problemas de optimización matemática con una función objetivo no lineal convexa y cuyo dominio de soluciones factibles esta compuesto exclusivamente por restricciones lineales, es decir, es un conjunto convexo (en consecuencia el problema es convexo)