Algoritmo para la ubicación óptima

Algoritmo para la ubicación óptima

El algoritmo que se muestra a continuación nos da una idea del funcionamiento de un algoritmo voraz usado para ayudar a las empresas o multinacionales a ubicar óptimamente sus almacenes principales dependiendo de la ubicación de las ciudades destino y la cantidad de viajes que se deben hacer a cada una de esas ciudades.

Se muestra una implementación del algoritmo con una interfaz gráfica de usuario (GUI) en el lenguaje de programación Java.

Contenido

Descripción

Se trata de una empresa de transportes que debe realizar envíos a distintas ciudades y necesitamos encontrar una solución óptima que nos diga un sitio adecuado donde situar el almacén para evitar en cierta medida recorrer mas kilómetros de los necesarios sabiendo que todos los trayectos se realizan desde el almacén hasta la ciudad en cuestión y viceversa ya que debemos vaciar y llenar el camión. Se trata de encontrar las coordenadas para dicho almacén una vez conocidas las de las ciudades y el número de envíos a cada una de ellas. Las coordenadas se trataran como coordenadas reales, en este caso si las coordenadas fueran Oeste o Sur deben ser introducidas como números negativos. Se toma como referencia la coordenada (0,0) que es el corte del Meridiano de Greenwich con el Ecuador (como un plano cartesiano). Estas son las pruebas que debemos usar en el algoritmo.

Limitaciones

1. La solución algorítmica mostrada en este artículo tiene un enfoque voraz y siempre da una solución óptima, pero su complejidad no depende de la cantidad de ciudades ingresadas, sino de que tan distantes estén dichas ciudades entre sí. A partir de esto concluimos que si se ingresan muchas ciudades cuyas coordenadas están muy próximas, el algoritmo será óptimo, pero si se ingresan pocas ciudades muy alejadas entre sí, el algoritmo será poco óptimo.

2. Las coordenadas de las ciudades siempre deben ser enteras, puesto que el algoritmo se basa en:la capacidad de enumeración de los números enteros.

Solución

1. Se encuentran cuatro pares ordenados, los cuales forman un rectángulo que encierra todas las coordenadas de las ubicaciones de las ciudades. Estas cuatro coordenadas se hallan de la siguiente manera:

            X1= la menor coordenada en x de todas las ubicaciones de las ciudades. 
            Y1= la mayor coordenada en y de todas las ubicaciones de las ciudades.

            X2= X1.
            Y2= la menor coordenada en y de todas las ubicaciones de las ciudades.

            X3= la mayor coordenada en x de todas las ubicaciones de las ciudades.
            Y3= Y1.

            X4= X3.
            Y4= Y2.

2. Se recorre cada coordenada contenida dentro del rectángulo hallando la suma de las distancias desde está a cada ciudad y multiplicándola por la cantidad de envíos respectivos a cada una, y se compara con el mínimo resultado de las pruebas anteriores, de tal forma que al final de hacer el recorrido del rectángulo se va a tener la coordenada cuya suma de las distancias desde ella a todas las ciudades multiplicadas por sus respectivos envíos es la menor.

A continuación se muestra el código con implementación en java:

Implementación del algoritmo

Clase Aplicación

La clase Aplicación contiene el método principal del programa
 public class Aplicacion
 { 
   public static void main (String args[])
   { 
      Ventana ventana;
      Coordinador coordinador;
      Algoritmo algoritmo;
 
      ventana=new Ventana();
      coordinador=new Coordinador();
      algoritmo=new Algoritmo();
 
      ventana.setCoordinador(coordinador);
      coordinador.setVentana(ventana);
      coordinador.setAlgoritmo(algoritmo);
 
      ventana.setVisible(true);
 
   }
 }

Clase Ciudad

La clase Ciudad nos abstrae las propiedades de ubicación, nombre y cantidad de envios a dicha ciudad
 
 public class Ciudad
 {
 
        // Variables que guardan las coordenadas de la ciudad.
        int x = java.lang.Integer.MAX_VALUE, y = x;
 
        // Variable que guardara el numero de envios que hay que realizar a esta
        // ciudad.
        int numeroEnvios = -1;
 
        // Variable que guarda el nombre de la ciudad.
        String nombre = "";
 
        // Método que se encarga de pedir los datos de la ciudad
 
 
        public Ciudad(String nombre,int x, int y, int numeroEnvios )
        {
                super();
                this.x = x;
                this.y = y;
                this.numeroEnvios = numeroEnvios;
                this.nombre = nombre;
        }
 
        public int getNumeroEnvios()
        {
            return numeroEnvios;
        }
 
        public int getX()
        {
            return x;
        }
 
        public int getY()
        {
            return y;
        }
 
        public String getNombre()
        {
            return nombre;
        }
  }

Clase Algoritmo

La clase Algoritmo trae la implementación del algoritmo para la ubicación óptima
 public class Algoritmo
 {
 
        Ciudad ciudades[];
 
        // Variables que almacenaran las coordenadas limite del problema
 
        int xInicial = java.lang.Integer.MAX_VALUE, yInicial = xInicial;        
        int xFinal = java.lang.Integer.MIN_VALUE, yFinal = xFinal;
 
        // Variables que guardaran las coordenadas solucion encontradas.
 
        int solucionX, solucionY;        
        float distanciaSolucion = java.lang.Float.MAX_VALUE;
 
        public void calcularLimites()
        {
 
                for (int i = 0; i < ciudades.length; i++)
                {
 
                        if (ciudades[i].getX() < xInicial)
                        {
                                xInicial = ciudades[i].getX();
                        }
 
                        if (ciudades[i].getY() < yInicial)
                        {
                                yInicial = ciudades[i].getY();
                        }
 
                        if (ciudades[i].getX() > xFinal)
                        {
                                xFinal = ciudades[i].getX();
                        }
 
                        if (ciudades[i].getY() > yFinal)
                        {
                                yFinal = ciudades[i].getY();
                        }
                }
 
        }
 
        // Método que se encarga de hallar distancias
 
        public float calcularDistancia(int x, int y)
        {
                float distancia = 0;                
                for (int i = 0; i < ciudades.length; i++)
                {
                        distancia += ((Math.sqrt(Math.pow(x - ciudades[i].getX(), 2) + Math.pow(y -                              ciudades[i].getY(), 2))) * ciudades[i].getNumeroEnvios());
                }
 
                return distancia;
 
        }
 
        public Ciudad situarAlmacen(Ciudad[] ciudades)
        {
 
                this.ciudades = ciudades;                
                calcularLimites();                
                for (int i = xInicial; i <= xFinal; i++)                
                {
                        for (int j = yInicial; j <= yFinal; j++)                        
                        {               
                                float distanciaActual = calcularDistancia(i, j);                                
                                if (distanciaSolucion > distanciaActual)              
                                {                                        
                                        distanciaSolucion = distanciaActual;                                       
                                        solucionX = i;                                        
                                        solucionY = j;
                                }
                        }
                }
                return new Ciudad("Solucion", solucionX, solucionY, 0);            
        }
 
        public void inicializar()
        {
                xInicial = java.lang.Integer.MAX_VALUE;
                yInicial = xInicial;
                xFinal = java.lang.Integer.MIN_VALUE;
                yFinal = xFinal;
                distanciaSolucion = java.lang.Float.MAX_VALUE;
        }
 
 }

Clase Coordinador

:La clase Coordinador coordina la [[interfaz]] con los algoritmos
 
 public class Coordinador
 {
       Ventana ventana;
       Algoritmo algoritmo;
 
       public void setAlgoritmo(Algoritmo algoritmo)
       {
           this.algoritmo = algoritmo;
       }
 
       public void setVentana(Ventana ventana)
       {
           this.ventana = ventana;
       }
 
       public void evento_aplicarAlgoritmo()
       {
           Ciudad []ciudades=ventana.obtenerCiudades();
           Ciudad ciudadSolucion;
 
           if(ciudades!=null)
           {
                algoritmo.inicializar();
                ciudadSolucion=algoritmo.situarAlmacen(ciudades);
 
                ventana.getLabelSolucion().setText("Solucion:  X= "+ciudadSolucion.getX()
                +" Y= "+ciudadSolucion.getY());
           }
       } 
 }

Clase ManejoException

La clase ManejoException crea una Exception con la información dada en mensaje
 public class ManejoException extends Exception
 {
        String men;
        public ManejoException(String mensaje)
        {
                men=mensaje;
        }
 
        public String getMessage()
        {
                return men;
        }
 }

Clase Tabla

La clase Tabla crea una tabla abstracta reescribiendo algunos métodos para la conveniencia de la GUI.
 import javax.swing.table.AbstractTableModel;
 
 public class Tabla extends AbstractTableModel
 {
        int col = 1, fil = 1, i = 0;
        Object[][] datos;
        String[] nombres;
 
        public boolean isCellEditable(int fil, int col)
        {
                return col != 0;
        }
 
        public Object getValueAt(int fil, int col)
        {
                return datos[fil][col];
        }
 
        public int getColumnCount()
        {
                return nombres.length;
        }
 
        public int getRowCount()
        {
                return datos.length;
        }
 
        public String getColumnName(int col)
        {
                return nombres[col];
        }
 
        public void setValueAt(Object dato, int fil, int col)
        {
                datos[fil][col] = dato;
        }
 
        public void cambiarCantidadFilas(int fil)
        {
                this.fil = fil;
                datos = new String[fil][col];
        }
 
        public void cambiarCantidadColumnas(int col)
        {
                this.col = col;
                datos = new String[fil][col];
                nombres = new String[col];
        }
 
        public void añadirNombre(String nombre)
        {
                nombres[i] = nombre;
                i++;
        }
 
        public void inicializar()
        {
                fil = 0;
                datos = new String[fil][col];
        }
 }

Clase Ventana

La clase Ventana crea una GUI con un JTable para ingresar las ciudades con sus respectivos datos.
  import java.awt.Dimension;
 import java.awt.Toolkit;
 import java.awt.event.ActionEvent;
 import java.awt.event.ActionListener;
 import java.util.Vector;
 
 import javax.swing.JButton;
 import javax.swing.JFrame;
 import javax.swing.JLabel;
 import javax.swing.JOptionPane;
 import javax.swing.JScrollPane;
 import javax.swing.JTable;
 import javax.swing.JTextField;
 
 public class Ventana extends JFrame implements ActionListener
 {
        JTable tabla;
        Tabla abTabla;
        JScrollPane barra;
        JTextField campoCantidad;
        JLabel labelCantidad,labelSolucion;
        JButton botonCantidad, botonHallarSolucion;
 
        Vector<String> nombres;
        Coordinador coordinador;
        int cantidad;
 
        public Ventana()
        {
                setLayout(null);
 
                labelCantidad = new JLabel("Cantidad De Ciudades");
                campoCantidad = new JTextField();
                botonCantidad = new JButton("Ingresar");
 
                abTabla = new Tabla();
 
                labelSolucion=new JLabel("Solucion: ");
                botonHallarSolucion = new JButton("Hallar Solucion");
 
                abTabla.cambiarCantidadColumnas(5);
 
                abTabla.añadirNombre("#");
                abTabla.añadirNombre("Nombre");
                abTabla.añadirNombre("CooX");
                abTabla.añadirNombre("CooY");
                abTabla.añadirNombre("Envios");
 
                tabla = new JTable(abTabla);
                tabla.setEnabled(true);
 
                cambiarTamañoTabla(10);
 
                tabla.getColumn("#").setMinWidth(20);
                tabla.getColumn("#").setPreferredWidth(20);
                tabla.getColumn("#").setPreferredWidth(20);
 
                barra = new JScrollPane();
                barra.setViewportView(tabla);
                tabla.getTableHeader().setReorderingAllowed(false);
 
                labelCantidad.setBounds(20, 40, 140, 20);
                campoCantidad.setBounds(160, 40, 50, 20);
                botonCantidad.setBounds(220, 40, 100, 20);
 
                barra.setBounds(20, 100, 300, 230);
 
                labelSolucion.setBounds(20,340,500,20);
                botonHallarSolucion.setBounds(110, 370, 120, 20);
 
                add(labelCantidad);
                add(campoCantidad);
                add(botonCantidad);
                add(barra);
                add(labelSolucion);
                add(botonHallarSolucion);
 
                setTitle("Ubicacion optima de un almacen");
                setSize(350, 450);
 
                botonCantidad.addActionListener(this);
                botonHallarSolucion.addActionListener(this);
 
                Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
                setLocation((screenSize.width - 350) / 2, (screenSize.height - 500) / 2);
                setDefaultCloseOperation(EXIT_ON_CLOSE);
        }
 
        public void actionPerformed(ActionEvent evento)
        {
                if (evento.getSource() == botonCantidad)
                {
                        try
                        {
                                int cantidad = Integer.parseInt(campoCantidad.getText());
 
                                if (campoCantidad.getText().contains(".") || 
                                campoCantidad.getText().contains("-"))
                                        throw new ManejoException("La cantidad de ciudades tiene que
                                        ser un numero\nno negativo ni decimal");
 
                                cambiarTamañoTabla(cantidad);
                                barra.repaint();
                        }
                        catch (NumberFormatException e)
                        {
                                JOptionPane.showMessageDialog(null, "La cantidad de ciudades tiene 
                                que ser un numero\nno negativo ni decimal");
                        }
                        catch (ManejoException e)
                        {
                               JOptionPane.showMessageDialog(null, e.getMessage());
                        }
                }
                else
                {
                         coordinador.evento_aplicarAlgoritmo();
                }
        }
 
        private void cambiarTamañoTabla(int cantidad)
        {
                this.cantidad = cantidad;
 
                abTabla.cambiarCantidadFilas(cantidad);
 
                for (int i = 0; i <cantidad; i++)
                     abTabla.setValueAt("" + (i + 1), i, 0);
 
                tabla.setVisible(false);
                tabla.setVisible(true);
        }
 
        public Ciudad[] obtenerCiudades()
        {
                int x, y, envios,i=0;
                Ciudad[] ciudades = new Ciudad[cantidad];
 
                nombres=new Vector(0,1);
 
                try
                {
                        for (i = 0; i < cantidad; i++)
                        {
                                if (((String) tabla.getValueAt(i, 1))==null)
                                        throw new ManejoException("Tiene que ingresar el nombre de la
                                        ciudad");
 
                                x = Integer.parseInt((String) tabla.getValueAt(i, 2));
                                y = Integer.parseInt((String) tabla.getValueAt(i, 3));
                                envios = Integer.parseInt((String) tabla.getValueAt(i, 4));
 
                                if (nombres.contains((String) tabla.getValueAt(i, 1)))
                                        throw new ManejoException("hay nombres de ciudades 
                                        repetidos");
                                if (((String) tabla.getValueAt(i, 2)).contains("."))
                                        throw new ManejoException("Tiene que ingresar un numero no 
                                        decimal\nError fila: "+i+" col: "+2);
                                if (((String) tabla.getValueAt(i, 3)).contains("."))
                                        throw new ManejoException("Tiene que ingresar un numero no 
                                        decimal\nError fila: "+i+" col: "+3);
                                if (((String) tabla.getValueAt(i, 4)).contains(".") || ((String) 
                                tabla.getValueAt(i, 4)).contains("-"))
                                        throw new ManejoException("Tiene que ingresar un numero no 
                                        negativo ni decimal\nError fila: "+i+" col: "+4);
 
                                nombres.add((String) tabla.getValueAt(i, 1));
                                ciudades[i] = new Ciudad((String) tabla.getValueAt(i, 1), x, y, 
                                envios);
                        }
                        return ciudades;
                }
                catch (NumberFormatException e)
                {
                        JOptionPane.showMessageDialog(null, "Tiene que ingresar un numero\nError
                        fila: "+i);
                }
                catch (ManejoException e)
                {
                       JOptionPane.showMessageDialog(null, e.getMessage());
                }
                return null;
        }
 
        public JTable getTabla()
        {
                return tabla;
        }
 
        public int getCantidad()
        {
                return cantidad;
        }
 
        public void setCoordinador(Coordinador coordinador)
        {
                this.coordinador = coordinador;
        }
 
        public JScrollPane getBarra()
        {
                return barra;
        }
 
        public JLabel getLabelSolucion()
        {
                return labelSolucion;
        }
 }

Complejidad Temporal

La complejidad de este algoritmo viene dada por dos factores, el primero es la cantidad de ciudades que son ingresadas y el segundo la amplitud del rectángulo que contiene todas las ubicaciones de las ciudades. Se podría observar que para cada punto contenido en el rectángulo se le halla la suma de las distancias a las ciudades multiplicadas por el respectivo número de envíos, y para hacer esta suma hay que recorrer todas las ciudades, por tanto la posible complejidad del algoritmo viene dada por:

               X1= la menor coordenada en x de todas las ubicaciones de las ciudades. 
               Y1= la menor coordenada en y de todas las ubicaciones de las ciudades.
               X2= la mayor coordenada en x de todas las ubicaciones de las ciudades.
               Y2= la mayor coordenada en y de todas las ubicaciones de las ciudades. 
               N= la cantidad de ciudades.

                                 T (N)= ( X2 – X1 ) * ( Y2 – Y1 ) * N

Pruebas

A continuación se muestran algunas pruebas que se le pueden hacer al algoritmo:

Forma de Ejecución

Forma 1:

Si tiene instalado java con un IDE como Eclipse o JCreator puede copiar las clases aquí vistas en un archivo con extensión '.java' y crear un proyecto y ejecutarlo desde allí.
Para Eclipse, abra el entorno, entre a File, New, Proyect, le da un nombre y especifica un Package dentro del proyecto, a continuación entre a Windows, Show View, Package Explorer, para abrir una ventana donde aparece el proyecto, a dentro de este debe estar el Package especificado por usted, si no se encuentra, da click derecho sobre el proyecto y le dice New, Package, le da un nombre.
A continuación con el click derecho sobre el Package creado le dice importar, elige la dirección donde se encuentran las clases y le da aceptar.

Luego busca la clase Aplicación dentro del Package, le da click derecho y run, java aplication.

Forma 2:

Para poder compilar y ejecutar el programa debe tener instalado en su computador el JDK de Java 1.5 o mejores actualizaciones y además debe tener el path de Windows configurado con el jdk. Para configurar el path es necesario ir a Panel de Control-> Sistema->Variables de Entorno->Path->Modificar. A continuación agregue la ruta del jdk
      Por ejemplo si el path anterior era:
      %SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem; C:\Archivos de programa\Intel\DMIX
      el path modificado deberá quedar:
      %SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem; C:\Archivos de programa\Intel\DMIX; C:\Archivos de programa\Java\jdk1.6.0\bin

Más sobre configuración del path

Antes de comenzar tiene que copiar cada una de las clases en un bloc de notas separado y guardarlo con el mismo nombre de la clase y con extensión.java. Por ejemplo: al copiar la clase Algoritmo en un bloc de notas la guarda como AlgoritmoKurskal.java.
Para compilar abra la consola, o para Windows XP la herramienta símbolo del sistema, estando allí diríjase al directorio donde tiene todas las clases guardadas (Todas las clases deben estar en el mismo directorio para que el programa corra correctamente) y enseguida copie el siguiente comando javac Aplicación.java, esto le dice a java que compile el main del programa que se encuentra en Aplicación.java. Si hace esto correctamente deben haberse creado en el directorio de las clases varios archivos .class, uno para cada clase y con el mismo nombre de la clase.
Para ejecutar tiene que haber compilado primero. Nuevamente abra la consola, o símbolo del sistema, y diríjase al directorio donde se encuentran todas las clases y digite el siguiente comando java Aplicación, esto le dice a java que ejecute el main del programa. Si lo hace correctamente el programa debe estar corriendo.

Conclusiones

1.El algoritmo tiene un enfoque voraz.

2.El algoritmo siempre da la solución óptima.

3.La complejidad no solo depende de la cantidad de ciudades ingresadas, también se debe tener en cuenta que tan distantes están las ciudades entre sí.

Véase también

1.Algoritmo Voraz

2.Algoritmo de kruskal

3.Algoritmo de Prim


Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Algoritmo voraz — Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución …   Wikipedia Español

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

  • Edificio Habitacional Inteligente Sustentable E.H.I.S. — Edificio Habitacional Inteligente Sustentable E.H.I.S. Saltar a navegación, búsqueda Introducción: El Edificio Habitacional Inteligente Sustentable (en adelante, E.H.I.S) es aquél cuya regularización, supervisión y control del conjunto de las… …   Wikipedia Español

  • Pila (informática) — Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”