Cómo solucionar problemas de programación lineal Usando Simplex

Con el fin de averiguar la mayor cantidad de dinero que usted podría hacer con sujeción a ciertas restricciones , puede utilizar el método simplex. Originalmente descubierto por un ingeniero de la Fuerza Aérea , George B. Dantzig , en 1947 , el método simplex es un método de programación lineal que maximiza ( o minimiza ) una función sujeta a restricciones en forma de igualdades lineales. Geométricamente, las desigualdades forman una región poligonal . El método simplex trata todos los vértices de esta región hasta que encuentra el que hace la función de asumir el mayor valor . Instrucciones Matemáticas 1

Determine si el problema es un problema de maximización estándar. En este tipo de problemas , las siguientes condiciones deben cumplirse : la función debe maximizarse , las constantes en las desigualdades deben ser todos no negativos , las variables deben todos ser no negativo y las desigualdades deben todos ser menor o igual a . Por ejemplo, el siguiente es un problema de maximización estándar :

Maximizar F = 5x + 6y sujeta a las limitaciones

4x + 2y <= 10

3x + y <; = 5

x + 2y <= 8 personas

donde x e y son ambos no negativo
2

Convertir cada desigualdad en una igualdad añadiendo . una variable de holgura entre la desigualdad. Por ejemplo, después de la adición de variables de holgura , las desigualdades se convierten en:

4x + 2y + u = 10

3x + y + v = 5

x + 2y + w = 8
3

Asegurar todas las ecuaciones , incluyendo la función , tienen las variables en el lado izquierdo y las constantes de la derecha. Por ejemplo , en el ejemplo de todas las ecuaciones ya tienen la forma correcta , excepto para la función . Vuelva a escribir la función como se indica :

-5x - 6y + F = 0
4

Convertir el sistema de ecuaciones en una matriz denominada tabla inicial simplex. Cada fila de la matriz corresponde a los coeficientes de las ecuaciones . Ponga los números de la función en la fila inferior . Por ejemplo, la tabla símplex inicial del ejemplo es :

xyuvw F

4 2 1 0 0 0 10

3 1 0 1 0 0 5

1 2 0 0 1 0 8 personas

-5 -6 0 0 0 -1 0
5

encuentra el indicador más negativo de la tabla inicial simplex. Los "indicadores " son los números en la parte inferior (a excepción de la parte más inferior número). En el ejemplo , el indicador más negativo es -6 en la segunda columna. Esta columna se denomina columna pivote .
6

Encontrar la proporción más pequeña de la columna pivote . Relaciones Formulario tomando más a la derecha el número de cada fila y dividiéndolo por el número correspondiente en la columna pivote . Haga esto para cada fila , excepto la fila indicador. Por ejemplo , las proporciones en el ejemplo son :

10/2 = 5

5/1 = 5

8/2 = 4

La proporción más pequeña de la columna pivote es 4 , que corresponde a la tercera fila .
7

usar operaciones de fila de la matriz para cambiar todos los otros números en la columna pivote a 0 . Por ejemplo , restar la primera fila por la fila pivote para formar un 0 en la primera fila. Reste el doble de la segunda fila de la fila pivote para formar un 0 en la segunda fila. El resultado se muestra a continuación :

xyuvw F

3 0 1 0 -1 0 2 Foto

5 0 0 2 -1 0 2 Foto

1 2 0 0 1 0 8 personas

-8 0 0 0 -3 -1 -24
8

Compruebe si todos los indicadores son no negativos . Si es así, entonces ya está. De lo contrario , vaya al Paso 5 .
9

Lea la solución de la matriz final. Por ejemplo , si la matriz final es

xyuvw F

1 0 0 3 0 4 4

0 3 0 4 4 0 6 0 0

2 4 3 0 ​​4

0 0 0 3 3 1 5

buscan las columnas con un solo número que no sea cero . Esta columna le da el valor de esa variable en la solución. Para encontrar el valor , se divide el número más a la derecha por el número que no sea cero . En esta matriz final , la solución es :

x = 4/1 o 4

y = 6/3 o 2

u = 4/2 o 2

y el valor máximo de la función f es 5 .