Resolución De PPL

Informe Nº1

“Resolución de PPL”

Resumen Ejecutivo

En el siguiente informe se desarrollan 2 problemas de programación lineal utilizando un software especializado (el cual utiliza el método SIMPLEX para la resolución de PPL’S).

El objetivo principal del trabajo es observar el comportamiento ambos ejemplos de programación lineal.

Descripción del problema

Métodos y software a utilizar

Principales resultados

Principales análisis

Principales conclusiones

Índice

INTRODUCCIÓN

PROBLEMA 1

DESCRIPCIÓN DEL PROBLEMA

PLANTEAMIENTO DEL MODELO

RESULTADOS

ANÁLISIS DE LOS RESULTADOS

PROBLEMA 2

DESCRIPCIÓN DEL PROBLEMA

PLANTEAMIENTO DEL MODELO

RESULTADOS

ANÁLISIS DE LOS RESULTADOS

CONCLUSIONES

ANEXOS

Introducción

Resolver problemas de complejidad exponencial o similar por ejemplo implicaría, en la mayoría de los casos, un tiempo de resolución largo llegando incluso a ser inviable. La aparición de nuevos computadores con capacidad de proceso superior ha logrado reducir los tiempos de respuesta, sin embargo, el mayor avance en esta área fue la utilización de técnicas de optimización consiguiendo resolver problemas antes impensados. El uso de estos algoritmos entrega soluciones bastante cercanas a la real.

Existen diversas formas de optimización pero en este trabajo se profundizará en la utilización de la programación lineal, la cual consiste en una función lineal llamada función objetivo bajo una serie de restricciones, descritas como inecuaciones lineales.

En el siguiente informe se van a desarrollar 2 problemas de programación lineal. El primero de ellos presenta una gran cantidad de variables y restricciones, teniendo que trabajar con un gran número de datos y un segundo problema con una mínima cantidad de datos.

A través de cada una de las preguntas se irá resolviendo ambos problemas para lograr concluir que nivel de dificultad presentan ambos y compararlos con la intuición inicial.

Para encontrar los resultados se utilizó el software OPL/CPLEX, el que funciona usando el método SIMPLEX para la resolución de PPL’S.

Problema 1

Descripción del problema

A partir de un set de nodos, los que representan una ubicación en el globo y las coordenadas de la ubicación de cada integrante, la idea es lograr establecer el camino mínimo tal que se recorra la menor distancia posible pasando por todos los hogares de los integrantes.

Planteamiento del modelo

1.1 Primero fue necesario realizar un pre procesamiento de datos que básicamente consistió en escribir los nodos y sus respectivas latitudes y longitudes en columnas diferentes. Luego con el programa “Google Earth” cada integrante obtuvo las coordenadas de sus casas. Con todos los datos en un archivo Excel (ver Anexo 1) se procedió a calcular la distancia de cada casa a cada nodo, una vez obtenidos estos resultados se eligió el nodo correspondiente a la distancia menor, ya que este corresponde a el nodo más cercano.

Para calcular las distancias se utilizo la fórmula “Haversine”, que consiste en:

Donde:

d es la distancia entre los dos puntos.

R es el radio medio de la tierra que es 6731km. aprox.

El punto 1 tiene coordenadas:

El punto 2 tiene coordenadas:

Y además la función “haversin” corresponde a:

Considerando:

Finalmente reemplazando y despejando, se obtiene que:

.

Los nodos que se obtuvieron son los que aparecen en la tabla 1.

1.2 Así como fue necesario un pre procesamientos de datos para la parte 1.1, para realizar esta parte también se realizo un ordenamiento de los datos del archivo que contenía los arcos, en Excel se calcularon todas las distancias de los arcos (ver Anexo 2).

La estructura del problema de programación lineal, se construyó considerando lo siguiente; como era necesario medir distancias entre el par de casas de cada uno de los integrantes, se consideró este desplazamiento como un flujo, vale decir ir desde el nodo con oferta (casa de inicio) hacia el nodo con demanda (casa destino) y fijando el resto de los nodos como nodos de tránsito. Los nodos se comunican a través de arcos.

En la construcción del OPL se definió lo que se conoce como tuplas las cuales permiten ligar distinta información y manejarla como una sola, en este caso se crearon las “tuplas arcs” que relacionan el nodo inicial, el nodo final, la distancia entre estos nodos, y la capacidad de cada arco asociado a los nodos.

La variable de decisión de este problema corresponde a la cantidad de circulación o flujo que se envía por cada arco. Por ende la función objetivo de este problema consiste en minimizar la distancia para enviar el flujo

...