METODO SIMPLEX
Para comprender el funcionamiento de este tema basta con recordar el método gráfico, el cual se iban buscando esquinas del grafico hasta llegar la solución óptima. El método simplex se basa en ir buscando esquina por esquina a fin de encontrar el punto esquina optimo, pero al contrario del método grafico este se logra mediante un proceso algebraico, no obstante es necesario convertir cada restricción de desigualdades a igualdades con el objetivo de manipular estas ecuaciones de forma sistemática.
Conversión de desigualdades a igualdades:
Sean las desigualdades:
Para la primera desigualdad, representa un valor más pequeño o igual que 8, por lo tanto si quisiéramos convertir esta desigualdad en igualdad deberíamos sumar un valor de holgura (denotada usualmente como ) que represente el número necesario para llegar a 8, de esta manera si tomara un valor de 3 y un valor de 2 el valor de holgura será 3. La primera restricción se transforma como sigue:
Para la segunda restricción, representa un valor más grande o igual a 5 por lo tanto se debe buscar un valor de holgura que le reste a la desigualdad y llegue al valor de 5, por ejemplo si vale 4 y tiene un valor de 6 el número de holgura será 3 de manera que cuando restemos el valor de holgura llegue al valor de 5. La segunda ecuación queda como sigue:
Siguiendo con nuestro tema, tomaremos un ejemplo en particular e iremos describiendo paso a paso la solución del problema.
Supondremos el siguiente caso:Maximizar:
Sujeto a:
Como se vio anteriormente las restricciones tomaran el valor de:
Y la función objetivo tomara la forma:
Si reordenamos en una tabla las restricciones y la función objetivo tomaría la siguiente forma:
Se denominara las posibles variables de entrada a todos los valores de la fila z como sigue:
Cuando se trata de maximizar se debe seleccionar el valor más negativo, en este caso será -2 y posteriormente se debe seleccionar la respectiva columna (columna pivote):
Para la última tabla se le ha agregado una columna (razón, denotada a menudo como ) este indica la razón entre el número de la columna “resultado” y el posterior numero de la columna pivote (Obviando la columna z), en forma más grafica el procedimiento para hallar la razón se hace del siguiente modo:
El segundo paso es hallar la fila pivote, y este se hace seleccionando el valor más pequeño positivo en la columna “razón” (variable de salida), en este caso será el 5, y posteriormente seleccionando toda la fila:
Normalmente se dividiría toda la fila pivote por el número sombreado en rojo, pero esta vez no es necesario, puesto que tiene valor 1, y por ende cada división resultaría el mismo número.
El tercer paso se basara en transformar toda la columna pivote en cero, a excepción del numero tocado por la fila pivote. Para este procedimiento se usa el método gauss, el cual se detallara a continuación:
Para transformar la columna R1 en forma adecuada se usa la siguiente ecuación:
Esto indica que cada cuadro de la columna deberá ser restado por el respectivo valor de , así cuando se transforme el número de la columna pivote este tome el valor de cero:
Igualmente el valor de Z será transformado con la ecuación:
Para una mayor comprensión hacia el lector se detallara los procesos para la ecuación anterior:
En general la columna nueva será el valor de la columna antigua menos el número pivote de la columna multiplicado por el número de la fila pivote.
La grafica final queda como sigue:
Para este sistema ya no es posible encontrar una solución más óptima, esto es porque los valores de y en la fila z son cero, por lo tanto el valor de z será 10, x1 será 0 (esto es porque la columna x no puede ser transformada en valores de cero) y x2 será igual a 5.
Transformar las desigualdades
Es posible a veces manipular las desigualdades de tal manera que se transformen en desigualdades “<=” por ejemplo se tienen la ecuación:
Es posible transformar esta desigualdad multiplicando cada miembro por -1:
Posteriormente es posible transformar un problema de minimización a maximización multiplicando cada variable por -1, por ejemplo se tiene la función objetivo:
Es posible transformar esta función objetivo de la siguiente forma:
Es muy usual hacer este tipo de procedimientos cuando se tiene mucha más experiencia haciéndolo de la forma maximizar con restricciones de desigualdad <=.
Método de la gran M
Supongamos el siguiente problema:Minimizar:
S.A:
Si reordenamos las restricciones de la forma común, tomaría la forma:
Para el reglón 1, si se multiplicara por -1 la variable de holgura podría tomar valores negativos, y violaría la restricción . Es por eso que para este tipo de problema se le asigna una variable artificial (a), de tal manera que su valor sea lo suficientemente alto para no convertir s1 en un número negativo.
De una forma similar pasara con el reglón 3, si se multiplicara esta por -1 tanto x como y podrían tomar valores negativo, y por consiguiente se le debe agregar una variable artificial
Las restricciones quedaran como sigue:
Desafortunadamente no hay garantía para que las últimas restricciones tengan los mismos resultados que se piden en el enunciado. Puede existir la posibilidad de que se consiga algún valor a en el resultado final. Para solucionar este problema se hace lo siguiente:
La M agregado representan valores extremadamente grandes por lo tanto si se trata de minimización los valores serán iguales a cero, y el resultado final serán iguales a los que se piden en el problema primero
Reordenando la función objetivo quedará como sigue:
En tabla la función objetivo y las restricciones tomara la siguiente forma:
Antes de seguir nuestro estudio miraremos un último problema:
Si la columna z tiene un resultado final de 0 las variables z, x, y tomarían valores de cero también, por consiguiente en el reglón R1 por ejemplo los valores de a1+a2 seria 4, por ende toda la tabla seria inconsistente. Para solucionar este problema se transforma cada una de las M en cero utilizando el método gauss, la formula a utilizar será:
La tabla modificada será:
En este punto ya es posible proceder con el método gauss ordinario, pero tratándose de minimización se buscara el valor más positivo en la columna Z, el cual resulta 3M-2
De igual manera se selecciona la variable de salida como el valor más pequeño de la razón de la fila “total” con la fila “x” (en este caso seria 1), posteriormente la columna pivote será las casillas consecutivas a este. La tabla 6 muestra la columna y fila pivote sombreadas en azul.
El ejercicio continúa normalmente como se mostró en el primer ejemplo, recordando que:- Ha de tener en cuenta que este es un ejercicio de minimización por ende la variable de entrada será el de valor más positivo, pero a su vez solo se deben tener en cuenta las variables del problema y no las holguras o los valores artificiales.
- Se llega al óptimo cuando los valores de zx y zy son cero o mayores a este.
Como ayuda al lector se ha especificado que se debe hacer con los diferentes criterios de decisión en la siguiente tabla:
El método simplex es un algoritmo creado por George Dantzig que permite la solución de muchos problemas de programación lineal.
Muy popular, es bien aceptado en las zonas donde las diferentes necesidades y limitaciones influencia en un valor que necesita ser aumentado o disminuido al máximo.
El algoritmo puede ser implementado de varias maneras diferentes, pero el principio es básicamente el mismo. A continuación se muestra el enfoque utilizado por [Papadmitriou].
Al final del texto se le puede asignar una implementación de lenguaje de programación en Python está disponible en Github.
El uso más común de la Simplex es maximizar el resultado, es decir, encontrar el valor más grande posible para un total. Los problemas típicos de resolver con Simplex están buscando cantidades óptimas de productos para ser vendidos, con restricciones en el almacenamiento y la producción de los mismos.
La idea es para aislar una función como el objetivo. Las cantidades que desee optimizar están representados por las variables aquí llamados , y la función objetivo se presenta como siendo los coeficientes de las variables. Estos muestran la proporcionalidad entre ellos.
Por lo general son números racionales obtenidos en el problema que desea resolver.
Las restricciones se presentan como las desigualdades. Peculiaridades indican el hecho de que una empresa sólo es capaz de almacenar un determinado peso o volumen de los productos, por ejemplo.
Entre las posibilidades de los valores de las variables que satisfagan las limitaciones, el algoritmo debe encontrar a los que dan la función objetivo el total más alto posible.
A continuación, se incrementa gradualmente a la variable que tiene la interferencia más positivo en los resultados de la función objetivo, es decir, el que tiene el coeficiente más alto. Esto se llama “la variable activa” y tiene una gran importancia inicial, ya que es el más “rentable” ellos, es decir, que nos lleva más cerca de optimización.
A medida que este valor aumenta, el algoritmo comprueba todas las restricciones, hasta que uno de ellos no se cumple. Esta restricción se llama la “restricción activa”. En este momento, se sabe la variable activa máxima.
El procedimiento se desplaza a la siguiente variable que nos trae buena solución, siempre teniendo en cuenta la cantidad máxima que el primero podría lograr. Cada uno de estos cambios, el Simplex convierte todos los coeficientes (incluyendo la función objetivo) de acuerdo con los límites que se encuentran en las sucesivas restricciones activas.
El procedimiento se repite hasta que el incremento de las variables se presente como una disminución en total alcanzado. Esto se identifica con el signo negativo delante de los coeficientes de la función objetivo. Al final, los valores buscados son conocidos por medio de un sistema de ecuaciones, los derivados de la problema original.
Para ello, el algoritmo puede ser perfectamente adaptado con el fin de resolver un problema en el que desea encontrar un pequeño resultado. Sin embargo, lo que se hace a menudo es simplemente invertir todas las relaciones, multiplicando los coeficientes por -1 y haciendo que el problema original es visto como un simple maximización.
La versión modificada tiene una línea formada por los coeficientes simétricos de la línea relativa a la limitación violado dividido por el coeficiente de la variable violada. Esta línea se corresponderá, en orden, a la variable que violó la restricción.
Este producto hace que las matrices siempre tiene una lista de coeficientes ya modificados de acuerdo con las restricciones y los mejores valores posibles para las variables hasta la fecha. El proceso se repite hasta que encuentre el resultado óptimo, es decir, cuando ya no es posible mejorar el total sin violar las restricciones.
Sin embargo, utilizando el enfoque de procesamiento lineal en cada iteración de la totalidad del sistema se enciende de manera que el vértice anterior es el nuevo origen de la complejidad por iteración se convierte.
Por supuesto, la pregunta es ¿cuántas iteraciones son necesarias para alcanzar los criterios de parada. Un límite superior para este número es, el extremo que conduce a la complejidad exponencial en a.
Afortunadamente, tanto Papadimitriou como informó de que, en la práctica, pocos problemas tomando esta complejidad y, por lo tanto, el algoritmo Simplex es muy utilizado.
Programación lineal es un campo importante de la optimización por varias razones. Muchos de los problemas prácticos en la investigación de operaciones se pueden expresar como problemas de programación lineal.
Ciertos casos especiales de programación lineal, tales como problemas de flujo de red y problemas de flujo multiservicio se consideran lo suficientemente importante que si una gran cantidad de investigación se ha generado en los algoritmos especializados para sus soluciones. Varios algoritmos para otros tipos de trabajo resolver problemas de optimización problemas de PL como sub-problemas.
Históricamente, las ideas de programación lineal han inspirado a muchos de los conceptos centrales de la teoría de optimización, tales como la dualidad, la descomposición , y la importancia de la convexidad y sus generalizaciones.
El agricultor haya una cantidad limitada de fertilizantes F permitido y insecticida P permitida para ser utilizados, cada uno que se requiera en diferentes cantidades por unidad de superficie para el trigo ( F 1 , P 1 ) y cebada ( F 2 , P 2 ).
Sea S 1 precio de venta de trigo, y S 2 de la cebada. Si llamamos a la superficie sembrada con trigo y cebada x 1 y x 2 , respectivamente, a continuación, el número óptimo de km 2 de siembra con trigo vs. La cebada se puede expresar como un problema de programación lineal:
maximizar (Maximizar el beneficio – esta es la “función objetivo”)
sujeto a (Límite de la superficie total)
(Límite de fertilizantes)
(Límite de insecticida)
(No se puede sembrar un área negativa)
Para ser función objetivo lineal también implica que una solución óptima sólo puede ocurrir en un punto del conjunto de puntos factibles frontera.
Hay dos situaciones en las que una solución óptima no se puede encontrar. En primer lugar, si las restricciones se contradicen entre sí (por ejemplo, x ≥ 2 y x ≤ 1), entonces la región factible está vacía y no puede haber ninguna solución óptima, ya que no puede haber solución. En este caso, la PL se dice no factible .
Alternativamente, el poliedro puede ser ilimitada en la dirección de la función objetivo (por ejemplo, maximizar x 1 + 3 x 2 sujetos a x 1 ≥ 0, x 2 ≥ 0, x 1 + x 2 ≥ 10), en este caso no existe una solución óptima desde arbitrariamente grandes soluciones de la función objetivo puede ser construido, y el problema se dice a ilimitado .
Aparte de estas dos condiciones patológicas (que a menudo se eliminan por las limitaciones de recursos inherentes en el problema que se modela como arriba), el óptimo se alcanza siempre un vértice poliedro.
Sin embargo, la óptima no siempre es único: es posible tener un conjunto de soluciones óptimas que cubren un borde o cara del poliedro, o incluso todo el poliedro (Esta última situación puede ocurrir si la función objetivo es uniformemente igual a una constante).
Aunque este algoritmo es muy eficiente en la práctica, y está garantizado para encontrar un óptimo global si ciertas condiciones para evitar los ciclos se toman, es débil en el peor de los casos: Usted puede construir un problema de programación lineal práctico para los que el método simplex realiza un número exponencial de pasos en relación con el tamaño de la emisión.
De hecho, desde hace algún tiempo no se sabía si los problemas de programación lineal fueron NP-completo o ha tenido solución en tiempo polinómico.
El primer algoritmo de programación lineal en el tiempo polinomio en el peor caso fue propuesto por Leonid Khachiyan en 1979 . Se basaba en optimización no lineal de Naum Shor, que es una generalización del método de elipsoide Arkadi Nemirovski, uno de los ganadores del Premio de Teoría John von Neumann en 2003 , y D. Yudin.
Sin embargo, el rendimiento práctico es decepcionante algoritmo Khachiyan: en general, el método simplex es más eficiente. Su importancia es que fomenta la investigación de métodos de punto interior.A diferencia de algoritmo simplex, que sólo avanza a lo largo puntos en el límite de la región factible, los métodos de punto interior pueden moverse por el interior de la región factible.
En 1984 , Narendra Karmarkar propuso su método proyectivo, que se convirtió en el primer algoritmo para un buen desempeño en la teoría y en la práctica: el peor de los casos es la complejidad polinómica y los problemas prácticos de la experiencia muestra que es razonablemente eficiente en comparación con el algoritmo simplex.
Dado que el método Karmarkar, se han propuesto y analizado muchos otros métodos de punto interior. Un método popular es el método predictor-corrector de Mehrotra, cuya actuación tiene un buen rendimiento en la práctica, aunque se sabe poco acerca de ello en teoría.
La última opinión entre los estudiosos es que la eficiencia de las buenas implementaciones de los métodos basados en simplex y los puntos interiores son similares a la aplicación rutinaria de la programación lineal.
La solución de programación lineal se están utilizando diversos problemas de optimización generalizados en la industria, tales como la optimización del flujo de transporte, que puede transformarse en problemas de programación lineal sin demasiadas dificultades.
Si las variables son binarias, es decir, teniendo sólo los valores 0 (cero) o 1, tienen un caso especial de PI, que también puede ser clasificado como NP-duro.
Cuando sólo algunas de las variables son números enteros y otra continua, tenemos la “Programación Entera Mixta” (PIM).
Sin embargo, hay algunas clases de problemas que se pueden resolver perfectamente en tiempo polinómico, tienen su propia estructura de la matriz llama matrices totalmente unimodulares.
Si la estructura del problema permiten también es posible aplicar un algoritmo de generación de columnas
Muy popular, es bien aceptado en las zonas donde las diferentes necesidades y limitaciones influencia en un valor que necesita ser aumentado o disminuido al máximo.
Al final del texto se le puede asignar una implementación de lenguaje de programación en Python está disponible en Github.
Contenido
Visión general
El método Simplex permite encontrar los valores óptimos en situaciones donde deben respetarse muchos aspectos. Ante un problema, las desigualdades se establecen limitaciones que representan a las variables. A partir de ahí, se prueba posibilidades con el fin de optimizar el resultado tan pronto como sea posible.El uso más común de la Simplex es maximizar el resultado, es decir, encontrar el valor más grande posible para un total. Los problemas típicos de resolver con Simplex están buscando cantidades óptimas de productos para ser vendidos, con restricciones en el almacenamiento y la producción de los mismos.
La idea es para aislar una función como el objetivo. Las cantidades que desee optimizar están representados por las variables aquí llamados , y la función objetivo se presenta como siendo los coeficientes de las variables. Estos muestran la proporcionalidad entre ellos.
Por lo general son números racionales obtenidos en el problema que desea resolver.
Las restricciones se presentan como las desigualdades. Peculiaridades indican el hecho de que una empresa sólo es capaz de almacenar un determinado peso o volumen de los productos, por ejemplo.
Entre las posibilidades de los valores de las variables que satisfagan las limitaciones, el algoritmo debe encontrar a los que dan la función objetivo el total más alto posible.
Operación
Relacionado con la programación lineal, se trabaja con funciones de 1º grado, la idea del algoritmo es bastante simple. Inicialmente, se asigna el valor cero a variables, sería muy lejos de la solución.A continuación, se incrementa gradualmente a la variable que tiene la interferencia más positivo en los resultados de la función objetivo, es decir, el que tiene el coeficiente más alto. Esto se llama “la variable activa” y tiene una gran importancia inicial, ya que es el más “rentable” ellos, es decir, que nos lleva más cerca de optimización.
A medida que este valor aumenta, el algoritmo comprueba todas las restricciones, hasta que uno de ellos no se cumple. Esta restricción se llama la “restricción activa”. En este momento, se sabe la variable activa máxima.
El procedimiento se desplaza a la siguiente variable que nos trae buena solución, siempre teniendo en cuenta la cantidad máxima que el primero podría lograr. Cada uno de estos cambios, el Simplex convierte todos los coeficientes (incluyendo la función objetivo) de acuerdo con los límites que se encuentran en las sucesivas restricciones activas.
El procedimiento se repite hasta que el incremento de las variables se presente como una disminución en total alcanzado. Esto se identifica con el signo negativo delante de los coeficientes de la función objetivo. Al final, los valores buscados son conocidos por medio de un sistema de ecuaciones, los derivados de la problema original.
Minimización
Aunque los ejemplos son casi siempre maximizando el Simplex también comprende los casos en que desea encontrar el valor más pequeño posible. Los costos y gastos son algunos de los resultados buscados comúnmente en estas situaciones.Para ello, el algoritmo puede ser perfectamente adaptado con el fin de resolver un problema en el que desea encontrar un pequeño resultado. Sin embargo, lo que se hace a menudo es simplemente invertir todas las relaciones, multiplicando los coeficientes por -1 y haciendo que el problema original es visto como un simple maximización.
Cuadro
Ya implementada en varios idiomas diferentes, el Simplex también se puede aplicar de forma manual. El método, conocido como Tableau, es poner toda la información organizada de forma correcta en un marco, haciendo exactamente lo que el software lo haría. En muchos lugares, el Simplex se enseña en este camino, por lo que la gente tiene un buen campo de la técnica de optimización.Matrices
El algoritmo de procesamiento puede ser realizado por un producto de matriz. Una vez que los coeficientes están correctamente dispuestos en filas y columnas, es suficiente que este se multiplica por una versión modificada de la “identidad Matrix”, de tamaño igual al número de variables.La versión modificada tiene una línea formada por los coeficientes simétricos de la línea relativa a la limitación violado dividido por el coeficiente de la variable violada. Esta línea se corresponderá, en orden, a la variable que violó la restricción.
Este producto hace que las matrices siempre tiene una lista de coeficientes ya modificados de acuerdo con las restricciones y los mejores valores posibles para las variables hasta la fecha. El proceso se repite hasta que encuentre el resultado óptimo, es decir, cuando ya no es posible mejorar el total sin violar las restricciones.
En el espacio de dimensión N
Si se considera a la óptica geométrica, el Simplex trabajando en la construcción de un politopo con un número de dimensiones igual al número de variables del problema. La solución óptima será siempre un conjunto de coordenadas de los vértices del politopo. Cada incrementar una variable, es como el Simplex percorresse uno de los bordes, siempre en busca de la punta perfecta.Complejidad
Formalmente, se cree que la complejidad del algoritmo Simplex ser exponencial. Muestra que en una aplicación ingenua, cada iteración en busca de la mejor solución es, en principio, la complejidad en términos de variables y restricciones.Sin embargo, utilizando el enfoque de procesamiento lineal en cada iteración de la totalidad del sistema se enciende de manera que el vértice anterior es el nuevo origen de la complejidad por iteración se convierte.
Por supuesto, la pregunta es ¿cuántas iteraciones son necesarias para alcanzar los criterios de parada. Un límite superior para este número es, el extremo que conduce a la complejidad exponencial en a.
Afortunadamente, tanto Papadimitriou como informó de que, en la práctica, pocos problemas tomando esta complejidad y, por lo tanto, el algoritmo Simplex es muy utilizado.
Con un algoritmo de Tableau
Estos procedimientos son válidos para problemas de maximización:- Introduzca las variables de holgura, uno para cada desigualdad;
- Establecer un marco para los cálculos mediante la colocación de los coeficientes de todas las variables con sus signos y, en la última línea, incluyen los coeficientes de la función objetivo transformado;
- Establecer una solución básica inicial, por lo general mediante la asignación de valor cero a las variables originales y la búsqueda de valores positivos para las variables de holgura;
- Como siguiente variable para entrar en la base, elegir no variable básica que proporciona, en la última línea, la mayor contribución al aumento de la función objetivo (es decir, tiene el valor más negativo). Si todas las variables que están fuera de la base tienen cero o positivos coeficientes en esta línea, la solución actual es óptima. Si cualquiera de estas variables tienen coeficiente cero, esto significa que se puede insertar en la base sin incrementar el valor de la función objetivo. Esto significa que tenemos una gran solución con el mismo valor de la función objetivo.
- Para elegir la variable que debe salir de la base, debe realizar lo siguiente:
- Dividir los elementos de la última columna de los elementos positivos correspondientes de la columna de la variable que va a entrar en la base. Si no hay elemento positivo en esta columna, el proceso debe detenerse, ya que la solución sería ilimitado.
- La proporción menor indica la ecuación cuya variable básica respectiva que ser anulada, por lo que es variable no básica.
- El uso de las operaciones válidas con filas de la matriz, la transformación de la mesa de cálculos con el fin de encontrar una nueva solución alcalina. La columna de la nueva variable básica debe convertirse en una identidad vectorial, donde se anularon los elementos 1 aparece en la línea correspondiente a la variable.
Programación lineal
En las matemáticas , un problema de programación lineal (LP) son problemas de optimización en el que la función objetivo y las restricciones son lineales.Programación lineal es un campo importante de la optimización por varias razones. Muchos de los problemas prácticos en la investigación de operaciones se pueden expresar como problemas de programación lineal.
Ciertos casos especiales de programación lineal, tales como problemas de flujo de red y problemas de flujo multiservicio se consideran lo suficientemente importante que si una gran cantidad de investigación se ha generado en los algoritmos especializados para sus soluciones. Varios algoritmos para otros tipos de trabajo resolver problemas de optimización problemas de PL como sub-problemas.
Históricamente, las ideas de programación lineal han inspirado a muchos de los conceptos centrales de la teoría de optimización, tales como la dualidad, la descomposición , y la importancia de la convexidad y sus generalizaciones.
Ejemplo
Aquí está un ejemplo de un problema de programación lineal. Supongamos que un agricultor tiene un pedazo de tierra que decir, el km 2 , para ser sembrada con trigo o cebada, o una combinación de ambos.El agricultor haya una cantidad limitada de fertilizantes F permitido y insecticida P permitida para ser utilizados, cada uno que se requiera en diferentes cantidades por unidad de superficie para el trigo ( F 1 , P 1 ) y cebada ( F 2 , P 2 ).
Sea S 1 precio de venta de trigo, y S 2 de la cebada. Si llamamos a la superficie sembrada con trigo y cebada x 1 y x 2 , respectivamente, a continuación, el número óptimo de km 2 de siembra con trigo vs. La cebada se puede expresar como un problema de programación lineal:
maximizar (Maximizar el beneficio – esta es la “función objetivo”)
sujeto a (Límite de la superficie total)
(Límite de fertilizantes)
(Límite de insecticida)
(No se puede sembrar un área negativa)
Teoría
Geométricamente, las restricciones lineales definen un poliedro convexo , que se llama el conjunto de puntos factibles . Dado que la función objetivo también es lineal, es un fantástico lugar automáticamente un óptimo global.Para ser función objetivo lineal también implica que una solución óptima sólo puede ocurrir en un punto del conjunto de puntos factibles frontera.
Hay dos situaciones en las que una solución óptima no se puede encontrar. En primer lugar, si las restricciones se contradicen entre sí (por ejemplo, x ≥ 2 y x ≤ 1), entonces la región factible está vacía y no puede haber ninguna solución óptima, ya que no puede haber solución. En este caso, la PL se dice no factible .
Alternativamente, el poliedro puede ser ilimitada en la dirección de la función objetivo (por ejemplo, maximizar x 1 + 3 x 2 sujetos a x 1 ≥ 0, x 2 ≥ 0, x 1 + x 2 ≥ 10), en este caso no existe una solución óptima desde arbitrariamente grandes soluciones de la función objetivo puede ser construido, y el problema se dice a ilimitado .
Aparte de estas dos condiciones patológicas (que a menudo se eliminan por las limitaciones de recursos inherentes en el problema que se modela como arriba), el óptimo se alcanza siempre un vértice poliedro.
Sin embargo, la óptima no siempre es único: es posible tener un conjunto de soluciones óptimas que cubren un borde o cara del poliedro, o incluso todo el poliedro (Esta última situación puede ocurrir si la función objetivo es uniformemente igual a una constante).
Algoritmos
El algoritmo simplex resuelve problemas de PL por la construcción de una solución admisible en vértice poliedro, y entonces corre a través de los vértices del poliedro que tienen valores sucesivamente más altos de la función objetivo para encontrar el máximo.Aunque este algoritmo es muy eficiente en la práctica, y está garantizado para encontrar un óptimo global si ciertas condiciones para evitar los ciclos se toman, es débil en el peor de los casos: Usted puede construir un problema de programación lineal práctico para los que el método simplex realiza un número exponencial de pasos en relación con el tamaño de la emisión.
De hecho, desde hace algún tiempo no se sabía si los problemas de programación lineal fueron NP-completo o ha tenido solución en tiempo polinómico.
El primer algoritmo de programación lineal en el tiempo polinomio en el peor caso fue propuesto por Leonid Khachiyan en 1979 . Se basaba en optimización no lineal de Naum Shor, que es una generalización del método de elipsoide Arkadi Nemirovski, uno de los ganadores del Premio de Teoría John von Neumann en 2003 , y D. Yudin.
Sin embargo, el rendimiento práctico es decepcionante algoritmo Khachiyan: en general, el método simplex es más eficiente. Su importancia es que fomenta la investigación de métodos de punto interior.A diferencia de algoritmo simplex, que sólo avanza a lo largo puntos en el límite de la región factible, los métodos de punto interior pueden moverse por el interior de la región factible.
En 1984 , Narendra Karmarkar propuso su método proyectivo, que se convirtió en el primer algoritmo para un buen desempeño en la teoría y en la práctica: el peor de los casos es la complejidad polinómica y los problemas prácticos de la experiencia muestra que es razonablemente eficiente en comparación con el algoritmo simplex.
Dado que el método Karmarkar, se han propuesto y analizado muchos otros métodos de punto interior. Un método popular es el método predictor-corrector de Mehrotra, cuya actuación tiene un buen rendimiento en la práctica, aunque se sabe poco acerca de ello en teoría.
La última opinión entre los estudiosos es que la eficiencia de las buenas implementaciones de los métodos basados en simplex y los puntos interiores son similares a la aplicación rutinaria de la programación lineal.
La solución de programación lineal se están utilizando diversos problemas de optimización generalizados en la industria, tales como la optimización del flujo de transporte, que puede transformarse en problemas de programación lineal sin demasiadas dificultades.
Variables enteras
Si ninguna de las variables de problemas pertenecen al conjunto de los números enteros, tenemos una programación lineal subclase llamada Programación Entera (IP) o la programación lineal entera. A diferencia de la PL que se puede encontrar la solución óptima en un tiempo razonable, muchos problemas de programación entera se consideran NP-duro.Si las variables son binarias, es decir, teniendo sólo los valores 0 (cero) o 1, tienen un caso especial de PI, que también puede ser clasificado como NP-duro.
Cuando sólo algunas de las variables son números enteros y otra continua, tenemos la “Programación Entera Mixta” (PIM).
Sin embargo, hay algunas clases de problemas que se pueden resolver perfectamente en tiempo polinómico, tienen su propia estructura de la matriz llama matrices totalmente unimodulares.
Si la estructura del problema permiten también es posible aplicar un algoritmo de generación de columnas
No hay comentarios.:
Publicar un comentario