ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Programación en enteros wiki: info, historia y vídeos

videos internet

salud  Programación en enteros 


Un programa lineal en enteros en forma preceptiva se expresa como:

maximizarcTxsujeto aAx=b,x=0,yx?Z,,

y un PLE en forma estándar se expresa como

maximizarcTxsujeto aAx+s=b,s=0,yx?Z,

donde c,b son vectores y A es una matriz de valores enteros. Note que afín a los programas lineales, los PLEs que no están en forma estándar pueden ser transformados a forma estándar suprimiendo las desigualdades y también introduciendo variables artificiales (s) y sustituyendo las variables que no están limitadas en signo con la diferencia de 2 variables limitadas en signo

IP polytope with LP relaxation

La imagen a la derecha muestra el próximo inconveniente.

maxy-x+y=13x+2y=122x+3y=12x,y=0x,y?Z

Los puntos enteros viables se muestran en colorado, y las líneas rojas intermitentes acotan la zona convexa, la que es el poliedro más pequeño que contiene todos esos puntos. Las líneas de azul, así como el eje de coordenadas definen el poliedro de la relajación del PL, el que está dado por las desigualdades sin la limitación de entera. La meta de la optimización es desplazar la línea de puntos negros tan arriba como se pueda al tiempo que esta prosiga tocando el poliedro. Las soluciones inmejorables del inconveniente entero son los puntos (uno con dos) y (dos,2) los que dan un valor de la función objetivo de dos. El perfecto único de la relajación es (dieciocho con veintiocho) con un valor de la función objetivo de dos.8. Note que si la solución de la relajación es redondeada al entero más próximo, esta no es viable para el PLE.


La programación lineal en enteros mixta (PLEM) implica inconvenientes en los que ciertas variables, xi, están limitadas a ser enteras, al tiempo que otras variables pueden no ser enteras.


La programación lineal cero-uno implica inconvenientes en los que las variables son limitadas a los valores 0 o 1. Note que cualquier variable entera delimitada puede ser expresada como un combinación de variables binarias. Por servirnos de un ejemplo, dada una variable entera, 0=x=U, esta puede ser expresada utilizando ?log2?U?+1 variables binarias:

x=x1+2x2+4x3+…+2?log2?U?x?log2?U?+1.

Existen 2 razones primordiales para emplear variables enteras cuando se modelan inconvenientes como programas lineales:



  1. Las variables enteras representan cantidades que solo pueden ser enteras. Por poner un ejemplo, no es posible edificar tres.7 automóviles.
  2. Las variables enteras representan resoluciones, con lo que deberían tomar solo los valores 0 o 1.

Estas consideraciones ocurren habitualmente en la práctica y por ende la programación lineal en enteros puede ser utilizada en muchas áreas de aplicación, ciertas cuales son concisamente descritas ahora.


Plan de producción


La PLEM tiene muchas aplicaciones en la producción industrial, incluyendo modelado trabajo-tienda. El plan de producción en la agricultura implica determinar el desempeño de la producción para múltiples cultivos que pueden compartir recursos (y también.g., tierra, tarea, fondo para fertilizador de semillas, etcétera). Un propósito posible es aumentar al máximo la producción total, sin sobrepasar los recursos libres. En ciertos casos, esto puede ser expresado en concepto de un programa lineal, mas las variables han de ser limitadas a los enteros.


Planificación


Estos inconvenientes implican planificación de automóviles y servicios en redes de transportación. Por poner un ejemplo, un inconveniente puede implicar asignar buses o bien metros a sendas individuales a fin de que un horario sea cumplido, y asimismo pertrecharlos con chóferes. Acá las variables de resolución binarias señalan dónde un autobús o bien metro es asignado a una senda y dónde un chofer es asignado a un tren o bien metro particularmente.


Redes de telecomunicaciones


El objetivo de estos inconvenientes es diseñar una red de líneas para instalar con lo que un conjunto predefinido de requerimientos de comunicación es conocido y el costo total de la red es minimal. Esto requiere optimar la topología de la red así como la configuración de capacidades de las distintas líneas. Habitualmente, las capacidades están limitadas a cantidades enteras. Generalmente existen, en dependencia de la tecnología utilizada, limitaciones auxiliares que pueden ser modeladas como desigualdades lineales con variables enteras o bien binarias.


Redes celulares


La labor de planear a menudo en redes de teléfonos GSM implica repartir frecuencias libres mediante las antenas a fin de que los usuarios puedan ser servidos y la interferencia sea minimizada entre las antenas. Este inconveniente puede ser elaborado como un programa lineal en enteros en el que las variables binarias señalan donde una frecuencia es asignada a una antena.


La forma fácil de solucionar un PLE es sencillamente suprimir la limitación x que es entera, solucionar el pertinente PL (llamado relajación PL del PLE), y entonces redondear la solución del PL relajado. Mas, esta solución no solo puede no ser perfecta, sino aun puede no ser viable, es decir que puede violar alguna limitación.


Usando unimodularidad total


Mientras que por lo general la solución del inconveniente relajado no se garantizará que sea perfecta, si el PLE tiene la manera maxcTx tal que Ax=b donde A,b, y c son todos enteros y A es plenamente unimodular, entonces toda solución viable básica es entera. Consecuentemente, la solución retornada por el algoritmo simplex se asegura que es entera. Para probar que cada solución viable básica es entera, sea x una solución viable básica cualquiera. Pues x es viable, sabemos que Ax=b. Sea x0=ndefined los elementos pertinentes a las columnas básicas para la solución básica x. Por definición de una base, hay una submatriz cuadrada B de A con columnas linealmente independientes semejantes que Bx0=b.


Puesto que las columnas de B son linealmente independientes y B es cuadrada, B es no singular, y por tanto, B es unimodular y de esta manera det(B)=±1. Asimismo, debido a que B es no singular, es inversible y por ende x0=B-1b. Por definición, B-1=Badjdet(B)=±Badj. Note que Badj indica la conjugada de B y es entera pues B es entera. En consecuencia,

?B-1=±Badj es entera.?x0=B-1b es entero.?Cada solución viable básica es entera.

De esta forma, si la matriz A de un PLE es plenamente unimodular, en lugar de utilizar un algoritmo de PLE, el procedimiento simplex puede ser utilizado para solucionar la relajación de PL y la solución va a ser entera


Algoritmos exactos


Cuando la matriz A no es absolutamente unimodular, existen una pluralidad de algoritmos que pueden ser utilizados para solucionar los programas lineales en enteros precisamente. Una clase de estos algoritmos son los métodos de planos tajantes los que marchan resolviendo la relajación de PL y entonces agregar limitaciones lineales que lleve la solución a ser entera sin excluir algún punto entero viable.


Otra clase de algoritmos son las variaciones de los métodos de ramificación y acotación Por poner un ejemplo, el procedimiento ramificación y corte que combina los métodos de ramificación y acotación y planos tajantes. Los algoritmos de ramificación y acotación tienen un elevado número de ventajas sobre algoritmos que solo utilizan planos tajantes. Una ventaja es que los algoritmos pueden ser de manera temprana terminados y siempre que por lo menos una solución entera ha sido encontrada, una viable, si bien no necesariamente perfecta, esta puede ser retornada. Además de esto, las soluciones de los PL relajados pueden ser utilizadas para proveer un estimado del caso peor de qué lejos de la optimalidad está la solución retornada. Por último, los métodos de ramificación y acotación pueden ser utilizados para regresar múltiples soluciones perfectas.


Lenstra en mil novecientos ochenta y tres probó, que cuando el número de variables es fijo, los inconvenientes de programación en enteros pueden ser resueltos en un tiempo polinomial.


Métodos heurísticos


Puesto que la programación lineal en enteros es NP-completo, muchas instancias de inconvenientes son desagradables, con lo que métodos heurísticos han de ser utilizados en su sitio. Por servirnos de un ejemplo, busca tabú puede ser utilizada para buscar soluciones de PLEs. Para emplear busca tabú para solucionar PLEs, los movimientos pueden ser definidos como acrecentar o bien decrementar una variable entera de una solución viable, al paso que todas las otras variables enteras se sostienen incesantes. Las variables irrestrictas pueden entonces ser resueltas. Memoria de término corto puede consistir de soluciones anteriormente intentadas al paso que memoria de término medio puede consistir de valores para las variables enteras que han resultado en valores altos de la función objetivo (asumiendo que el PLE es un inconveniente de maximización). Por último, memoria de término largo puede guiar la busca cara los valores enteros que no han sido anteriormente intentados.


Otros métodos heurísticos que pueden ser utilizados para solucionar PLEs incluye


Existen asimismo una pluralidad de otras heurísticas de inconvenientes concretos, como heurísitica k-opt para el TSP. Note que una desventaja de los métodos heurísticos es que si fallan en localizar una solución, no puede ser determinado donde es por el hecho de que no hay solución viable, o bien donde el algoritmo sencillamente no pudo hallar una solución. Además de esto, es generalmente imposible cuantificar qué cerca de la solución perfecta está una solución retornada por estos métodos.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Programación en enteros wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas