Metodo simplex de programacion lineal

Metodo simplex de programacion lineal

Pasos del método simplex

Esta macro encuentra la solución óptima de un programa lineal, utilizando la forma revisada del Simplex. La programación lineal (LP) trata de una función objetivo con sólo términos lineales, y asume que sólo existen restricciones lineales.

La función objetivo puede ser maximizar o minimizar una función matemática, como la representación de un beneficio o un coste. La optimización suele estar restringida, lo que significa que la solución óptima debe encontrarse dentro de ciertos límites definidos normalmente por la cantidad de recursos disponibles o el presupuesto de un proyecto.

El ejemplo que sigue está tomado de Hillier y Lieberman y representa la fabricación de dos productos (x1, x2) para la empresa Wyndor Glass Co. Las tres restricciones representan la capacidad de cada una de sus tres plantas de utilizar recursos para la fabricación del producto 1 (x1) y del producto 2 (x2).

Por defecto, la macro resolverá un problema de maximización. Si quiere minimizar la función objetivo, ponga un punto y coma después del comando principal y en la segunda línea utilice el comando MIN y un punto («.»), indicando el final del comando.

Problemas de maximización del método simplex de programación lineal con soluciones

En esta sección, resolveremos los problemas de minimización de programación lineal estándar utilizando el método simplex. Una vez más, recordamos al lector que en los problemas de minimización estándar todas las restricciones son de la forma \(ax + by ≥ c\).

Leer Más  Perito en informatica forense

El procedimiento para resolver estos problemas fue desarrollado por el Dr. John Von Neuman. Consiste en resolver un problema asociado llamado problema dual. A todo problema de minimización le corresponde un problema dual. La solución del problema dual se utiliza para encontrar la solución del problema original. El problema dual es un problema de maximización, que hemos aprendido a resolver en la última sección. Primero resolvemos el problema dual por el método simplex.

Obsérvese que esta tabla se parece a una tabla simplex inicial sin las variables de holgura. A continuación, escribimos una matriz cuyas columnas son las filas de esta matriz, y las filas son las columnas. Tal matriz se llama transposición de la matriz original. Obtenemos:

El lector puede reconocer que el Ejemplo \(\PageIndex{2}\) anterior es el mismo que el Ejemplo 3.1.1, en la sección 3.1. También es el mismo problema que el Ejemplo 4.1.1 en la sección 4.1, donde lo resolvimos por el método simplex.

Ejemplo del método simplex

ResumenEl objetivo es dar alguna explicación teórica de la eficiencia del método simplex de George Dantzig. Fijando el número de restricciones y utilizando el algoritmo paramétrico autodual de Dantzig, mostramos que el número de pivotes necesarios para resolver un problema de programación lineal crece en proporción al número de variables en promedio.

Mathematical Programming 27, 241-262 (1983). https://doi.org/10.1007/BF02591902Download citationShare this articleAnyone you share the following link with will be able to read this content:Get shareable linkSorry, a shareable link is not currently available for this article.Copy to clipboard

El método simplex de resolución de problemas de programación lineal utiliza

El nombre del algoritmo se deriva del concepto de simplex y fue sugerido por T. S. Motzkin[2] En realidad, el método no utiliza simples, pero una interpretación del mismo es que opera sobre conos simpliciales, y éstos se convierten en simples propios con una restricción adicional[3][4][5][6] Los conos simpliciales en cuestión son las esquinas (es decir, las vecindades de los vértices) de un objeto geométrico llamado politopo. La forma de este politopo está definida por las restricciones aplicadas a la función objetivo.

Leer Más  Graficos 2d en java netbeans

George Dantzig trabajó en métodos de planificación para las Fuerzas Aéreas del Ejército de Estados Unidos durante la Segunda Guerra Mundial utilizando una calculadora de escritorio. En 1946, su colega le retó a mecanizar el proceso de planificación para evitar que aceptara otro trabajo. Dantzig formuló el problema como desigualdades lineales inspiradas en el trabajo de Wassily Leontief, sin embargo, en ese momento no incluyó un objetivo como parte de su formulación. Sin un objetivo, un gran número de soluciones pueden ser factibles y, por lo tanto, para encontrar la «mejor» solución factible, hay que utilizar «reglas básicas» especificadas por los militares que describen cómo se pueden alcanzar los objetivos, en lugar de especificar un objetivo en sí. La idea central de Dantzig fue darse cuenta de que la mayoría de esas reglas básicas pueden traducirse en una función objetivo lineal que hay que maximizar[7]. El desarrollo del método simplex fue evolutivo y se produjo a lo largo de un año[8].

Entradas relacionadas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad