Video de aplicación del modelo de Asignación.

 Aplicación del Modelo de Asignación a un problema

Edsger Dijkstra

Dijkstra estudió física teórica en la Universidad de Leiden. Trabajó como investigador para Burroughs Corporation a principios de los años 1970. En la Universidad de Texas en Austin, Estados Unidos, ocupó el Schlumberger Centennial Chair in Computer Sciences. Se retiró en 2000.
Entre sus contribuciones a la informática está la solución del problema del camino más corto, también conocido como el algoritmo de Dijkstra, la notación polaca inversa y el relacionado algoritmo shunting yard, THE multiprogramming system, el algoritmo del banquero y la construcción del semáforo para coordinar múltiples procesadores y programas. Otro concepto debido a Dijkstra, en el campo de la computación distribuida, es el de la auto-estabilización, una vía alternativa para garantizar la confiabilidad del sistema. El algoritmo de Dijkstra es usado en la ruta más corta primero (SPF) que es usado en el protocolo de enrutamiento Open Shortest Path First (OSPF). También se le debe la autoría de la expresión "Crisis del software", aparecida en su libro The Humble Programmer y usada ampliamente en la famosa reunión de la OTAN de 1968 sobre desarrollo del software. Recibió el Premio Turing en 1972.
Era conocido por su baja opinión de la sentencia GOTO en programación, que culminó en 1968 con el artículo Go To Statement Considered Harmful, visto como un paso importante hacia el rechazo de la expresión GOTO y de su eficaz reemplazo por estructuras de control tales como el bucle while. El famoso título del artículo no era obra de Dijkstra, sino de Niklaus Wirth, entonces redactor de Comunicaciones del ACM. Dijkstra era un aficionado bien conocido de ALGOL, y trabajó en el equipo que desarrolló el primer compilador para este lenguaje. En ese mismo año creó el primer sistema operativo con estructura jerárquica, de niveles o capas. Fue denominado THE (Technische Hogeschool, Eindhoven) que se utilizó con fines didácticos.
Desde los años 1970, el principal interés de Dijkstra fue la verificación formal. La opinión que prevalecía entonces era que uno debe primero escribir un programa y seguidamente proporcionar una prueba matemática de su corrección. Dijkstra objetó que las pruebas que resultan son largas e incómodas, y que la prueba no da ninguna comprensión de cómo se desarrolló el programa. Un método alternativo es la derivación de programas, «desarrollar prueba y programa conjuntamente». Uno comienza con una especificación matemática del programa que se supone va a hacer y aplica transformaciones matemáticas a la especificación hasta que se transforma en un programa que pueda ser ejecutado. El programa que resulta entonces es sabido correcto por la construcción. Muchos de los últimos trabajos de Dijkstra tratan sobre las maneras de hacer fluida la argumentación matemática.


referencias.http://es.wikipedia.org/wiki/Edsger_Dijkstra

Algoritmo de Prim

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

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. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

Referencias:http://es.wikipedia.org/wiki/Algoritmo_de_Prim

Guión del video.

https://docs.google.com/document/pub?id=1Ud77FopXVlP2FqsjReW_hgXMozwGEl7sJX9z6OmnTjg

Aqui le dejamos el link de nuestro guión. Esperamos comentarios.

Participación 10

min z= X13+4X14+3X23+2X24+X34+6X35+3X43+5X45+8X46+X56
s.a                                                         X13+X14= 100
                                                              X23+X24= 200
                                                              X34+X35=X13+X23+X43
                                                              X43+X45+X46=X14+X24+X34
                                                              X35+X45=150+X56
                                                              X46+X56= 150
                                                              Xij>=0
                                                              Xij E Z

	3	4	5	6
1	1	4	M	M	100
2	3	2	M	M	200
3	0	1	6	M	0+300
4	3	0	5	8	0+300
5	M	M	0	1	0+300
	0+300	0+300	150	150

Participación 7.

Dos plantas abastecen a tres clientes con suministros médicos. Las ganancias unitarias, junto con los suministros y demandas se dan en la siguiente tabla:

	1	2	3	Oferta
1	$55	$65	$80	35
2	$10	$15	$25	50
Demanda	10	10	10

1. ¿Cómo cambian los criterios de los métodos que generan la solución inicial?
Esquina noroeste
No cambia el metodo

Costos mínimos.
Se toma el de mayor costo y con ese se inicia el metodo

Vogel.se sacan las penalizaciones con la resta de los costas mayores tanto renglones como columnas se toma el de mayor numero en penalizacion y se escoge la casilla con mayor costo; ingresas la oferta o demanda menor y se tacha el renglon o columna sin valor en oferta o demanda;se actulizan las penalizaciones y se repiten lo ya mencionado 

2. ¿Qué criterio se utilizaría para determinar la variable de entrada?

teta min{xij}

3. ¿Cómo es el criterio de la variable de salida?

Se sacan los multiplicadores y la variable no  basica con menor costo sale.
Termina el metodo cuando todos son mayores o iguales que 0

4.Encontrar la solución óptima.

X11=10  X12=10  X13=10   Z=2000

Participación 8

1. Hay tres refinerías con capacidad diarias de 6, 5 y 8 millones de galones, respectivamente, que abastecen a tres áreas de distribución cuyas demandas diarias son 4, 8 y 7 millones de galones, respectivamente. La gasolina se transporta por una rede de oleoductos a las tres áreas de distribución. El costo de transporte es de 10 centavos por 1000 galones por milla de oleoducto. En la siguiente tabla se ven las distancias entre refinerías y las áreas de distribución. La refinería 1 no está conectada con el área de distribución 3.

Refinería \ Área de Distribución	1	2	3
1	120	180	--
2	300	100	80
3	200	250	120

m = millones.

Plantear red:

Modelo de programación lineal:
Xij = Número de galones de la refinería i al área j.

Min z = 1.2x11 + 1.8x12 + 3x21 + x22 + .8x23 + 2x31 + 2.5x32 + 1.2x33
x11 + x12                                                      = 6 m
                 x21 + x22 + x23                           = 5 m
                                           x31 + x32 + x33 = 8 m
x11         + x21                + x31                     = 4 m
          x12         + x22                + x32           = 8 m
                                    x23                  + x33 = 7 m

Solución inicial aplicando Vogel:

	1	2	3
1	1.2	1.8	M	6 m
	4 m	2 m
2	3	1	0.8	5 m
		5 m
3	2	2.5	1.2	8 m
		1 m	7 m
	4 m	8 m	7 m

Solución final:

		V1= 1.2	V2= 1.8	V3= 0.5
		1	2	3
X11=4 millones	U1= 0         1	1.2	1.8	M	6 m
X12 = 2 millones		4 m	2 m	0.5-M
X22= 5 millones	U2 = -0.8    2	3	1	0.8	5 m
X32= 1 millón		-2.6	5 m	-1.1
X33= 7 millones	U3= 0.7      3	2	2.5	1.2	8 m
		-0.1	1 m	7 m
		4 m	8 m	7 m

Interpretación de resultados:

1) La refinería 1 enviará 4 millones de galones a la área 1.
2) La refinería 1 enviará 2 millones de galones a la área 2.
3) La refinería 2 enviará 5 millones de galones a la área 2.
4) La refinería 3 enviará 1 millón de galones a la área 2.
5) La refinería 3 enviará 7 millones de galones a el área 3.