algoritmo

ALGORITMO SIMPLEX
En optimización matemática, el término algoritmo símplex habitualmente se refiere a un conjunto de métodos muy usados para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo simplex primal fue desarrollado por el matemáticonorteamericano George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. Un algoritmo simplex es un algoritmo de pivote.
Un método llamado de manera similar, pero no relacionado al anterior, es el método Nelder-Mead (1965) o método de descenso (o ascenso) símplex; un método numérico que busca un mínimo (o máximo) local de una función cualquiera examinando en cada paso losvértices de un simplex.






Pasos del Método Simplex
Este proceso que se repite una y otra vez, siempre inicia en un punto extremo de la región factible que normalmente es el origen, en cada iteración se mueve a otro punto extremo adyacente hasta llegar a la solución óptima.
Los pasos del Método Simplex son los siguientes:
1. Utilizando la forma estándar, determinar una solución básicafactible inicial igualando a las n-m variables igual a cero (el origen).
2. Seleccionar la variable de entrada de las variables no básicas que al incrementar su valor pueda mejorar el valor en la función objetivo. Cuando no exista esta situación, la solución actual es la óptima; si no, ir al siguiente paso.
3. Seleccionar la variable de salida de las variables básicas actuales.
4. Determinar lanueva solución al hacer la variable de entrada básica y la variable de salida no básica, ir al paso 2 (actualizar).
ALGORITMO DE PRIM

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Primen 1957 y redescubierto por Dijkstraen 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP oalgoritmo de Jarnik.

El algoritmo de Prim es un Algoritmo perteneciente a la teoría de grafos para encontrar un Arbol Recubridor Minimo (ARM) en un grafo conexo (si existe un camino entre cualquier par de vértices), no dirigido y cuyas aristas estánetiquetadas. Simplemente es que lo que representa es un subgrafo que contiene todos los nodos de G, conectados con el menor valor posible entreellos.

PASOS PARA REALIZAR EL ALGORITMO:
1. Se Marca un nodo cualquiera, el cual será el nodo de partida.
2. Se selecciona la arista de menor valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.
3. Se repite el paso 2, siempre y cuando la arista elegida enlace un nodo marcado y otro que no lo este.
4. El proceso termina cuando tenemos todos los nodos delgrafo marcados.

Ejemplo: Determinar el Arbol Recubridor Minimo del siguiente grafo Siguiendo el algoritmo de Prim, tenemos:



•Elegimos, por ejemplo, el nodo A como nodo de partida
y lo marcamos.
•Marcamos el nodo B, ya que la arista que une el nodo (A,B) es la arista de menor valor que une un nodo marcado y otro que no lo esta.
•Marcamos el nodo C, ya que la arista que une el nodo (A,C)es la arista de menor valor que une un nodo marcado y otro que no lo esta.
•Marcamos el nodo G, ya que la arista que une el nodo C y el nodo G, es la arista de menor valor que une un nodo marcado y otro que no loesta.
•Marcamos el nodo F, ya que la arista que no el nodo G y el nodo F, esla arista de menor valor que une un nodo marcado y otro que no lo esta.ALGORITMO DE KRUSKAL
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un...