jueves, 4 de marzo de 2010

Proyecto #2


Optimización




Problema:


"El alcalde de San Nico va a recibir en nuestro municipio al presidente de México en la plaza municipal, para lo que dicha zona debe estar presentable para ese día, digamos que los días restantes para su llegada son 3, entonces el alcalde quiere encontrar la manera mas óptima para dejar esa zona muy bien presentable para tal fecha"


Supongamos que el alcalde cuenta con un presupuesto de $1,166,666.6 para una semana por lo que a los correspondientes 3 días son $500,000 ; el cual es sacado de los impuestos que pagan los ciudadanos; y los aspectos para arreglar en la zona son:

1. Basura
2. Pintura
3.Mantenimiento


El área del terreno a arreglarse es de 1800m cuadrados:





El alcalde cuenta con 3 compañias que se encargan de realizar el trabajo que se requiere y son las siguientes;


Opción 1:

Ellos se tardan 5 días en realizar este trabajo y cobran un 150% mas por cada día menos que se aplace la fecha. La ponderación de lo que cobran por cada aspecto es:

1. Basura → $25 c/m2
2. Pintura → $100 c/m2
3.Mantenimiento → $80 c/m2

f(x)=((25x+100x+80x)•3)+z

si z=25x+100x+80x


Opción 2

Ellos se acomodan al limite de tiempo que el cliente necesita para el trabajo. La ponderación de lo que cobran por cada aspecto es:

1. Basura → $35 c/m2
2. Pintura → $90 c/m2
3. Mantenimiento → $50 c/m2

f(x)=35x+90x+50x


Opción 3

Ellos tradan 2 dias en hacer su trabaj y hacen un descuento del 5% por cada dia de plazo que se le den de mas.

1. Basura → $60 c/m2
2. Pintura → $110c/m2
3. Mantenimiento → $70 c/m2

f(x)=60x+110x+70x - (z(0.05))

si z=60x+110x+70x



¿Cual sera la manera mas óptima para encargar el trabajo?

Como el área =1800m2 entonces los costos de cada una de las empresas son:



Opción 1

1. Basura → $202,500
2. Pintura → $810,000
3.Mantenimiento → $144,000

=$1,156,500 + 300%
Total =$4,626,000


Opción 2

1. Basura → $63,500
2. Pintura → $162,000
3.Mantenimiento → $90,000

Total=$169,200


Opción 3

1. Basura → $108,000
2. Pintura → $198,000
3.Mantenimiento → $126,000

=$432,000 - 5%
Total=$410,400

Complejidad Asintótica

La manera mas óptima seria encontrar una cota inferior a la del presupuesto, pero entre mas alejada se encuentre de esta sera menos el costo, por lo tanto, mas óptimo.






En este caso como se observa en la gráfica la cota óptima a elegir es la opción 2 de color azul, ya que cumple con los requisitos para optimizar el trabajo, se encuentra debajo de la cota de ingreso (verde) y es también la cota mas baja, por lo tanto la menos costosa.


Este problema de decisión pertenece a la clase "P", ya que la elección no es muy complicada y las ecuaciones de cada opción son lineales, es por eso que no es muy difícil su solución.
Aparte estos algoritmos no pertenecen a un problema NP-difícil, por que para empezar como no es un problema NP por lo tanto no puede ser NP-duro.



Esta es una representación del algoritmo:


*Este no es un diagrama de flujo, solo es una representación del algoritmo en diagrama simple.



Referencias :

http://www.google.com.mx/
http://es.wikipedia.org/wiki/NP-hard
http://es.wikipedia.org/wiki/Clases_de_complejidad_P_y_NP
http://es.wikipedia.org/wiki/Cota_superior_asint%C3%B3tica
http://es.wikipedia.org/wiki/Optimizaci%C3%B3n_de_software
http://maps.google.com.mx/?gclid=CKvjnPWen6ACFSpeagodMlwzag
http://es.wikipedia.org/wiki/Problema_de_decisi%C3%B3n



1 comentario:

  1. Muy bien :) Elegiste un problema fácil, pero hiciste un muy buen reporte de ello.

    ResponderEliminar