Método simplex paso a paso – Programación lineal

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].

método simplex

Al final del texto se le puede asignar una implementación de lenguaje de programación en Python está disponible en Github.

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.

Vuelva al paso 4 para iniciar otra iteración.

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.

programacion 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

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *