11.4. MÉTODO DOBLE SIMPLE
De los resultados de los apartados anteriores se deduce que para obtener una solución al problema original podemos pasar al dual y, mediante estimaciones de su diseño óptimo, determinar la solución óptima al problema original.
La transición al problema dual no es necesaria, ya que si consideramos el primer cuadro símplex con base unitaria adicional, entonces es fácil ver que las columnas contienen el problema original, y el problema dual está escrito en las filas.
Como se mostró, al resolver el problema directo en cualquier iteración, la diferencia, es decir. magnitud -coeficiente con una variable, es igual a la diferencia entre los lados derecho e izquierdo de la restricción correspondiente del problema dual. Si al resolver un problema directo con una función objetivo maximizable, la iteración no conduce a una solución óptima, entonces para al menos una variable y solo en el óptimo para todas diferencia .
Considerando esta condición teniendo en cuenta la dualidad, podemos escribir
.
Así, si, después . Esto significa que cuando la solución al problema primal no es óptima, la solución al problema dual no es válida. Por otra parte 
a . Esto implica que la solución óptima del problema primal corresponde a una solución admisible del problema dual.
Esto hizo posible desarrollar un nuevo método para resolver problemas de programación lineal, cuando se usa, al principio, se obtiene una solución inaceptable, pero "mejor que óptima" (en el método simplex habitual, primero admisible, pero subóptimo solución). Un nuevo método llamado método símplex dual, asegura el cumplimiento de la condición de optimalidad de la solución y su “aproximación” sistemática al área de soluciones factibles. Cuando la solución obtenida resulta admisible, finaliza el proceso iterativo de cálculos, ya que esta solución también es óptima.
El método simplex dual permite resolver problemas de programación lineal cuyos sistemas de restricciones, con base positiva, contienen términos libres de cualquier signo. Este método permite reducir el número de transformaciones del sistema de restricciones así como el tamaño de la tabla símplex. Considere la aplicación del método símplex dual usando un ejemplo.
Ejemplo. Hallar el mínimo de una función 
bajo restricciones
.
Vayamos a la forma canónica:
bajo restricciones
La tabla símplex inicial tiene la forma
|
Básico Variables |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
Solución |
|
X 3 X 4 X 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Solución básica inicialóptimo, pero no aceptable.
Al igual que el método simplex usual, el método de solución en consideración se basa en el uso de condiciones de admisibilidad y de optimalidad.
condición de admisibilidad. La variable básica negativa más grande en valor absoluto se elige como la variable excluida (si hay alternativas, la elección se hace arbitrariamente). Si todas las variables básicas son no negativas, el proceso de cálculo finaliza, ya que la solución resultante es factible y óptima.
Condición optimización. La variable incluida en la base se selecciona de entre las variables no básicas de la siguiente manera. Las razones de los coeficientes del lado izquierdo se calculan-ecuaciones a los coeficientes correspondientes de la ecuación asociada a la variable excluida. Las relaciones con denominadores positivos o nulos no se tienen en cuenta. En el problema de minimización de la variable de entrada, debe corresponder el menor de los cocientes indicados, y en el problema de maximización, el cociente con el menor valor absoluto (si hay alternativas, la elección se hace arbitrariamente). Si los denominadores de todas las razones son cero o positivos, el problema no tiene soluciones factibles.
Después de elegir las variables a incluir en la base ya excluir, para obtener la siguiente solución, se realiza la operación habitual de transformar las filas de la tabla símplex.
En este ejemplo, la variable excluida es. Los ratios calculados para determinar la nueva variable base se muestran en la siguiente tabla:
|
Variables |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
|
La ecuacion X 4 - ecuación |
–2 –4 |
–1 –3 |
|||
|
Actitud |
La variable a incluir es X 2. La conversión de cadenas posterior da como resultado una nueva tabla símplex:
|
Básico Variables |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
Solución |
|
X 3 X 2 X 5 |
–1 –1 |
|||||
Nueva solución también óptimo, pero todavía inválido. Como nueva variable excluida, elegimos (arbitrariamente) X 3 . Definamos una variable incluida.
|
Variables |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
|
La ecuacion X 4 - ecuación |
|||||
|
actitud |
método símplex - este es un método de transición sucesiva de una solución básica (el vértice del poliedro solución) del sistema de restricciones de un problema de programación lineal a otra solución básica hasta que la función objetivo toma el valor óptimo (máximo o mínimo).
El método simplex es un método universal que puede resolver cualquier problema de programación lineal, mientras que el método gráfico solo es adecuado para un sistema de restricciones de dos variables.
El método simplex fue propuesto por el matemático estadounidense R. Danzig en 1947, desde entonces, por las necesidades de la industria, este método suele resolver problemas de programación lineal con miles de variables y restricciones.
Antes de pasar al algoritmo del método simplex, algunas definiciones.
Cualquier solución no negativa de un sistema de restricciones se llama solución aceptable .
Que haya un sistema metro restricciones de norte Variables ( metro norte).
Solución básica admisible es una solución que contiene metro no negativo importante (básico ) variables y norte - metro no central . (no básico, o libre ) variables. Las variables no básicas en la solución básica son iguales a cero, mientras que las variables principales, por regla general, no son cero, es decir, son números positivos.
Ningún metro variables del sistema metro ecuaciones lineales con norte las variables se llaman principal , si el determinante de los coeficientes en ellos es diferente de cero. luego el resto norte - metro las variables se llaman no central (o libre ).
Algoritmo del método simplex
- Paso 1. Lleva el problema de programación lineal a la forma canónica. Para hacer esto, mueva los términos libres a los lados derechos (si entre estos términos libres son negativos, entonces multiplique la ecuación o desigualdad correspondiente por - 1) e introduzca variables adicionales en cada restricción (con un signo más, si en el desigualdad original el signo es menor o igual que ", y con signo menos si es "mayor o igual que").
- Paso 2. Si en el sistema resultante metro ecuaciones, entonces metro tome las variables como las principales, exprese las variables principales en términos de las no básicas y encuentre la solución básica correspondiente. Si la solución básica encontrada resulta admisible, pasar a la solución básica admisible.
- Paso 3. Exprese la función objetivo en términos de las variables menores de la solución básica factible. Si se encuentra el máximo (mínimo) de la forma lineal y no hay variables no básicas con coeficientes negativos (positivos) en su expresión, entonces se cumple el criterio de optimización y la solución básica resultante es óptima: la solución ha terminado. Si al encontrar el máximo (mínimo) de una forma lineal, su expresión contiene una o más variables no básicas con coeficientes negativos (positivos), pase a una nueva solución básica.
- Paso 4. De las variables no básicas incluidas en la forma lineal con coeficientes negativos (positivos), elija la que corresponda al mayor coeficiente (módulo) y transfiérala a las principales. Vaya al paso 2.
Condiciones importantes
Algunos casos especiales se discuten en artículos separados: cuando función objetivo máxima - infinito, cuando el sistema no tiene solucion, y cuando la solución óptima no es la única .
A continuación, analizaremos un ejemplo típico, cuando el sistema de restricciones es consistente y existe un óptimo finito, y sólo uno. Una variación del método simplex es método de distribución para resolver el problema del transporte .
Método simplex con tablas simplex
Al construir tablas simplex, es mucho más fácil resolver un problema de programación lineal que mediante transformaciones algebraicas, como se muestra en el siguiente párrafo. Las tablas simplex son muy visuales. Hay varios tipos de reglas para trabajar con tablas símplex. Analizaremos la regla, que con mayor frecuencia se denomina columna principal y regla de fila principal.
Sería útil abrir el manual Acciones con fracciones en una nueva ventana: hay bastantes, fracciones en problemas del método simplex, por decirlo suavemente.
Ejemplo.
Introducimos variables no negativas adicionales y reducimos este sistema de desigualdades a un sistema de ecuaciones equivalente
.
Esto se hizo cumpliendo la siguiente regla: si el signo en la restricción original es "menor o igual que", entonces se debe agregar la variable adicional, y si es "mayor o igual que", entonces se debe agregar la variable adicional sustraído
Las variables adicionales introducidas se toman como principales (básicas). Entonces y son variables no básicas (libres).
Expresando las principales variables (básicas) en términos de no básicas (libres), obtenemos
También expresamos la función objetivo en términos de variables no básicas (libres):
A partir de los coeficientes de las variables (incógnitas) construimos la primera tabla símplex.
| tabla 1 | ||||
| Incógnitas básicas | miembros gratis | incógnitas sueltas | Coeficientes auxiliares | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
La última fila de la tabla, que contiene la función objetivo y los coeficientes de las variables libres, se denominará fila de índice.
La solución resultante no es óptima, ya que los coeficientes de las variables libres en la fila del índice son negativos. Es decir, la solución óptima será aquella en la que los coeficientes de las variables libres en la fila del índice sean mayores o iguales a cero.
Para pasar a la siguiente tabla, encuentre el mayor (módulo) de los números y . Este número es 2. Por lo tanto, la columna principal es la columna en la que está escrito
Para determinar la primera fila, encontramos el mínimo de las razones de los miembros libres a los elementos de la primera columna, y si el numerador tiene un número positivo y el denominador es negativo, la razón se considera igual a infinito.
.
Por lo tanto, la línea principal es aquella en la que está escrito
El elemento principal es por lo tanto -2.
Componemos la segunda tabla simplex.
Ingresamos el nuevo elemento básico en la primera línea, e ingresamos la columna en la que se encontraba, ingresamos una nueva variable libre
Complete la primera línea. Para ello, dividimos todos los números de la primera fila de la tabla 1 por el elemento principal y lo escribimos en la columna correspondiente de la primera fila de la tabla 2, excepto el número de la primera columna, donde el recíproco del principal elemento está escrito (es decir, uno dividido por el elemento principal).
Completa la columna de coeficientes auxiliares. Para este número de la columna principal de la tabla 1, además del elemento principal, escribimos con signos opuestos en la columna de coeficientes auxiliares de la tabla 2.
| Tabla 2 | ||||
| Incógnitas básicas | miembros gratis | incógnitas sueltas | Coeficientes auxiliares | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
Quien aún no ha abierto en una nueva ventana el manual Acciones con fracciones, puede hacerlo ahora, porque es el momento.
Para obtener las filas restantes de la tabla 2, los números que ya están en la primera fila de esta tabla se multiplican por el coeficiente auxiliar en la fila que se está llenando, y al resultado le sumamos el número de la tabla 1, que está en la misma fila con la variable correspondiente.
Por ejemplo, para obtener el miembro libre de la segunda fila, multiplicamos el número 1 por 1 y sumamos el número -4 de la tabla 1. Obtenemos -3. Encontramos el coeficiente for en la segunda línea de la misma manera: 
. Como en la tabla anterior no hay ninguna columna con una nueva variable libre, el coeficiente de la segunda fila en la columna de la nueva variable libre será 
(es decir, de la tabla 1 sumamos 0, ya que no hay columna c en la tabla 1).
La línea de índice se rellena de la misma manera:
La solución así obtenida nuevamente no es óptima, ya que los coeficientes de las variables libres en la fila del índice son nuevamente negativos.
Para pasar a la siguiente tabla símplex, busquemos el mayor (módulo) de los números y, es decir, los módulos de los coeficientes en la línea índice. Este número es 2. Por lo tanto, la columna principal es la columna que contiene .
Para buscar la fila principal, encontremos la proporción mínima de miembros libres a los elementos de la fila principal. Obtenemos:
.
Por lo tanto, la línea principal es aquella en la que está escrito, y el elemento principal es -3/2.
Compilando la tercera tabla simplex
Escribimos la nueva variable básica en la primera línea. En la columna en la que estaba, ingresamos una nueva variable libre.
Primera linea:
Coeficientes auxiliares:
| Tabla 3 | ||||
| Incógnitas básicas | miembros gratis | incógnitas sueltas | Coeficientes auxiliares | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
La solución resultante nuevamente no es óptima, ya que los coeficientes de las incógnitas libres en la fila del índice son nuevamente negativos.
Para ir a la cuarta tabla símplex, busquemos el mayor de los números y . Este es un número.
Por lo tanto, la columna principal es la que tiene .
Módulo mínimo de relaciones de miembros libres a elementos de la columna principal:
.
Por lo tanto, la línea principal es aquella en la que está escrito, y el elemento principal es 1/3.
En la cuarta tabla símplex, escribimos la nueva variable básica en la primera línea. En la columna donde estaba, escribimos una nueva variable libre.
Primera linea:
Coeficientes auxiliares:
| Tabla 4 | ||||
| Incógnitas básicas | miembros gratis | incógnitas sueltas | Coeficientes auxiliares | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
Cálculo de las filas restantes usando el ejemplo de la segunda fila:
La solución resultante tampoco es óptima, pero ya es mejor que las anteriores, ya que uno de los coeficientes para variables libres en la fila del índice es no negativo.
Para mejorar el plan, pasemos al siguiente cuadro símplex.
Encuentra el mayor de los números 4 y . Este número es 4. Por lo tanto, la columna principal es .
Para encontrar la fila principal, encuentre
.
Por lo tanto, la línea principal es la que contiene . Pero ya estaban juntos entre las variables libres. Por lo tanto, para transferir la siguiente variable de libre a básica, seleccionamos otra columna principal, en la que está escrito.
Para encontrar la fila principal, encuentre
.
Por lo tanto, la línea clave es aquella en la que está escrito, y el elemento principal es 1.
En la quinta tabla símplex, la nueva variable básica se escribe en la primera línea. En la columna donde estaba, escribimos una nueva variable libre.
Primera linea:
Coeficientes auxiliares:
| Tabla 5 | ||||
| Incógnitas básicas | miembros gratis | incógnitas sueltas | Coeficientes auxiliares | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
Intentemos averiguar de inmediato si la solución no es óptima. Por lo tanto, para las filas restantes, calculamos solo los términos libres (para averiguar los valores de las variables básicas cuando las variables libres son iguales a cero) y los coeficientes para las variables libres en la fila de índice.
Miembros gratuitos:
En la segunda línea;
En la tercera línea;
En la cuarta línea.
Línea de índice:
Observamos la tabla simplex 5. Vemos que se ha obtenido la solución óptima, ya que los coeficientes para las incógnitas libres en la fila del índice no son negativos.
Método simplex con transformaciones algebraicas
Resolvamos por transformaciones algebraicas el mismo ejemplo del párrafo anterior. Cabe señalar que al resolver este tipo de método simplex, es mejor no escribir la función objetivo en la forma , ya que es fácil confundirse en los signos. Pero en este caso, el punto del algoritmo que determina el criterio de optimalidad se modificará de la siguiente manera.
Si se encuentra el máximo (mínimo) de la forma lineal y no hay variables no básicas con coeficientes positivos (negativos) en su expresión, entonces se cumple el criterio de optimización y la solución básica resultante es óptima: la solución ha terminado. Si al encontrar el máximo (mínimo) de una forma lineal, su expresión contiene una o más variables no básicas con coeficientes positivos (negativos), pase a una nueva solución básica.
Ejemplo. Encuentra el máximo de una función bajo restricciones
Paso I. Introducimos variables no negativas adicionales y reducimos este sistema de desigualdades a un sistema de ecuaciones equivalente
.
Las variables adicionales introducidas se toman como principales, ya que en este caso se encuentra fácilmente la solución básica del sistema. Entonces y son variables menores.
Expresando las principales variables en términos de las no básicas, obtenemos
En consecuencia, esta división de variables en básicas y no básicas corresponde a la solución básica 
, que no es válido (dos variables son negativas) y, por lo tanto, no es óptimo. Pasemos de esta solución básica a una mejorada.
Para decidir qué variable debe convertirse de no principal a principal, considere cualquiera de las dos ecuaciones disponibles del último sistema con términos libres negativos, por ejemplo, la segunda. Muestra que y se puede traducir a las variables principales, ya que en esta ecuación tienen coeficientes positivos (por lo tanto, cuando aumentan, y esto sucederá si traducimos alguna de ellas a las variables principales, la variable aumentará).
Tratemos de traducir a la variable principal. Para establecer qué variable se debe trasladar de la principal a la no básica, encontramos el valor absoluto de la relación más pequeña de los miembros libres del sistema a los coeficientes en . Tenemos . Se obtiene de la tercera ecuación, que muestra que la variable debe ser convertida a no básicas, la cual es positiva en la solución básica original. En consecuencia, la solución básica resultante, al igual que la original, contiene dos componentes negativos, es decir, no habrá mejora en la transición a dicha solución básica.
Método símplex− este es un método de enumeración ordenada de planes de referencia (el orden está asegurado por un cambio monótono en el valor de la función objetivo durante la transición al siguiente plan). En este caso, es necesario observar el principio: cada paso siguiente debe mejorar o, en casos extremos, no empeorar el valor de la función objetivo.
Para resolver la LLP método símplex se reduce a forma canónica, es decir, de las restricciones - desigualdades es necesario hacer restricciones - igualdades. Para ello, cada restricción se complementa con una adicional no negativa variable del balance con el signo “+” si el signo de desigualdad es “£”, y con el signo “–” si el signo de desigualdad es “³”.
En la función objetivo, estas variables adicionales entran con coeficientes cero, es decir la entrada de la función de destino no cambiará. Cada variable que no está sujeta a la condición de no negatividad se puede representar como la diferencia de dos variables no negativas: .
Si las restricciones de la tarea reflejan la presencia y el consumo de recursos, entonces el valor numérico de la variable adicional en el plan de tareas, escrito en forma canónica, es igual a la cantidad del recurso no utilizado.
Para resolver el problema por el método símplex, utilizaremos tablas simplex abreviadas de un sistema de ecuaciones lineales y el método de eliminación de Jordan modificado.
1. Elaboramos el primer plan básico
La tarea sigue siendo la misma. Traigamos la forma estándar del sistema de desigualdades (1) a la forma canónica del sistema de ecuaciones introduciendo variables de equilibrio adicionales X 3 , X 4 , X 5 ,X 6 .
En el sentido económico, los valores de variables adicionales X 3 , X 4 , X 5 determinar el saldo de materias primas después de la venta de productos.
La matriz del sistema de ecuaciones resultante tiene la forma:
Se puede ver que en la matriz A la base menor de 4º orden es el determinante, compuesto de coeficientes unitarios para variables adicionales X 3 , X 4 , X 5 ,X 6, ya que es distinto de cero e igual a 1. Esto significa que los vectores de columna para estas variables son linealmente independientes, es decir forma base, y las variables correspondientes X 3 , X 4 , X 5 ,X 6 son básico(básico). Variables X 1 , X 2 se llamará libre(menor).
Si las variables libres X 1 y X 2 para establecer diferentes valores, luego, resolviendo el sistema con respecto a las variables básicas, obtenemos un conjunto infinito de soluciones particulares. Si solo se establecen valores cero para variables libres, entonces a partir de un conjunto infinito de soluciones particulares, soluciones basicas- planos básicos.
Para saber si las variables pueden ser básicas, es necesario calcular el determinante formado por los coeficientes de estas variables. Si este determinante no es igual a cero, entonces estas variables pueden ser básicas.
El número de soluciones básicas y el número correspondiente de grupos de variables básicas no puede ser mayor que , donde norte es el número total de variables, r es el número de variables básicas, r≤ metro≤ norte.
Para nuestra tarea r = 4; norte= 6. Entonces , es decir Son posibles 15 grupos de 4 variables básicas (o 15 soluciones básicas).
Resolvamos el sistema de ecuaciones con respecto a las variables básicas X 3 , X 4 , X 5 ,X 6:
Suponiendo que las variables libres X 1 = 0, X 2 = 0, obtenemos los valores de las variables básicas: X 3 = 312; X 4 = 15; X 5 = 24;X 6 = -10, es decir la solución básica será = (0; 0; 312; 15; 24; -10).
Esta solución básica es inaceptable, porque X 6 = –10 ≤ 0, y por la condición de restricción X 6 ≥ 0. Por lo tanto, en lugar de la variable X 6 como base, debe tomar otra variable de entre las libres X 1 o X 2 .
Llevaremos a cabo la solución adicional utilizando tablas simplex abreviadas, completando las filas de la primera tabla con los coeficientes del sistema de la siguiente manera (Tabla 1):
tabla 1
F- la cadena se llama índice. Se llena con coeficientes de función objetivo tomados con signos opuestos, ya que la ecuación de la función se puede representar como F = 0 – (– 4X 1 – 3X 2).
En la columna de miembros libres b yo hay un elemento negativo b 4 = -10, es decir la solución del sistema no es válida. Para obtener una solución válida (plan base), el elemento b 4 debe hacerse no negativo.
Elegir X 6 - una línea con un miembro libre negativo. Esta línea contiene elementos negativos. Elija cualquiera de ellos, por ejemplo, "-1" en X 1 -columna, y X 1 - columna aceptar como columna de permiso(determinará que la variable X 1 pasará de libre a básico).
Compartimos miembros gratis b yo sobre los elementos pertinentes un es columna de resolución, obtenemos relaciones evaluativasΘ i==(24, 15, 12, 10). De estos, elegimos el positivo más pequeño (minΘ i=10), que corresponderá a línea de permiso. La cadena de permiso define una variable xj, que en el siguiente paso sobresale de la base y se libera. Es por eso X 6 -line es una línea permisiva, y el elemento "-1" es elemento habilitador. Lo rodeamos. Variables X 1 y X Se intercambian 6.
Razones estimadas Θ i en cada línea están determinados por las reglas:
1) Θ i= si b yo y un es tener diferentes signos;
2) Θ i= ∞ si b yo= 0 y un es < 0;
3) Θ i= ∞ si un es = 0;
4) Θ i= 0 si b yo= 0 y un es > 0;
5) Θ i= si b yo y un es tienen los mismos signos.
Damos el paso de la eliminación jordana modificada (MJJI) con un elemento permisivo y compilamos una nueva tabla (Tabla 2) de acuerdo con la siguiente regla:
1) en lugar del elemento de resolución (RE), se establece un valor, su inverso, es decir ;
2) los elementos de la línea permisiva se dividen en RE;
3) los elementos de la columna de resolución se dividen en RE y el signo cambia;
4) los elementos restantes se encuentran de acuerdo con la regla del rectángulo:
De la Mesa. 2 muestra que los miembros libres en b yo-columna son no negativos, por lo tanto, se obtiene la solución inicial admisible - plano de primera base= (10; 0; 182; 5; 4; 0). En este caso, el valor de la función F() = 40. Geométricamente, esto corresponde a la parte superior F(10; 0) polígono solución (Fig. 1).
Tabla 2
2. Verificamos la optimización del plan. El plan base no es óptimo, porque en F-line tiene un coeficiente negativo "-4". Mejoramos el plan.
3. Encontrar una nueva línea de base
Seleccionamos el elemento que permite de acuerdo con la regla:
Elegimos el coeficiente negativo más pequeño de F-línea "-4", que determina la columna de habilitación - X 6; variable X 6 se traducen en básico;
Hallamos las razones Θ i, entre ellos elegimos el positivo más pequeño, que corresponde a la cadena permisiva:
min Θ i = min(14, 5, 2, ∞) = 2, por lo tanto X 5 - línea - permisivo, variable X 5 lo traducimos a libre (variables X 5 y X 6 están intercambiados).
En la intersección de la fila y la columna permisivas se encuentra el elemento permisivo "2";
Realizamos el paso SHMZhI, construimos la tabla. 3 de acuerdo con la regla anterior y obtenga un nuevo plan de referencia = (12; 0; 156; 3; 0; 2).
Tabla 3
4. Comprobación de la optimización del nuevo plan básico
El plan base tampoco es óptimo, ya que en F-line tiene un coeficiente negativo "-1". Valor de función F() = 48, que geométricamente corresponde a la parte superior mi(12; 0) polígono solución (Fig. 1). Mejoramos el plan.
5. Encontrar una nueva línea de base
X 2 columnas es permisivo, ya que en F-línea el coeficiente negativo más pequeño "-1" está en X 2 columnas (Δ 2 = -1). Encontrar el Θ más pequeño i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, por lo tanto X Cuarta línea - permisivo. Elemento permisivo "1/2". Intercambio de variables X 2 y X cuatro Realizamos el paso SHMZhI, construimos la tabla. 4, obtenemos un nuevo plan de referencia = (9; 6; 51; 0; 0; 5).
6. Comprobación del plan básico para la optimización
A F-línea, todos los coeficientes son no negativos, por lo tanto, el plan de referencia es óptimo. Corresponde geométricamente a un punto D(9;6) (ver Fig. 1). El plan óptimo da el valor máximo de la función objetivo c.u.
Principal la idea de un método simplex para resolver el LLP consiste en la mejora constante de las soluciones de soporte de LLP.
Hay varias formas de escribir el método símplex.
- La forma básica del método simplex;
- Método simplex en forma de tabla simplex;
- método símplex modificado;
- Método simplex en forma de columnas;
- Método simplex en forma de fila.
Definamos el valor máximo de la función objetivo F(X) = 3x 1 +5x 2 +4x 3 bajo las siguientes condiciones de restricción.
0,1x1 +0,2x2 +0,4x3 ≤1100
0,05x 1 +0,02x 2 +0,02x 3 ≤120
3x1 +x2 +2x3 ≤8000
Para construir el primer plan de referencia, reducimos el sistema de desigualdades a un sistema de ecuaciones introduciendo variables adicionales (transición a la forma canónica).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Notación básica del método simplex
| La solución se lleva a cabo expresando las variables básicas a través de no básicas: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0.1x 1 -0.2x 2 -0.4x 3 x 5 = 120-0.05x 1 -0.02x 2 -0.02x 3 x 6 = 8000-3x 1 -x 2 -2x 3 |
Método simplex en forma de tabla simplex
La solución se lleva a cabo en forma de tabla símplex. El formulario está diseñado para computar en una computadora. Cuando se usa una base artificial, se usa un número especial M (generalmente 10000).| Plan | Base | A | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| línea de índice | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| línea de índice | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| línea de índice | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
método símplex modificado
| Matriz de coeficientes A = a ij matriz b. |
Método simplex en forma de columnas
| Pasamos a la forma columnar del método símplex. Expresamos cada variable en términos de variables no básicas. x0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x4 = 1100+0.1(-x 1)+0.2(-x 2)+0.4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0.05(-x 1)+0.02(-x 2)+0.02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Este sistema corresponde a la tabla T 0 .
|
Método simplex en forma de cadena
Como base inicial admisible podemos tomar B 0 =<4, 5, 6>. Corresponderá a la siguiente tabla.
|
La matriz Q, compuesta por los coeficientes del sistema, se llama mesa símplex correspondiente a la base B. Un cuadro símplex se llama admisible, o directamente admisible, si q i0 ≥ 0. Los elementos q i0 de la última fila de la tabla símplex Q se denominan estimaciones relativas.
Formas de solución por el método de base artificial.
Por el uso de variables artificiales introducidas en la función objetivo, se impone la denominada penalización de M, un número positivo muy grande, que normalmente no se especifica.La base resultante se llama artificial y el método de solución se llama método de base artificial.
Además, las variables artificiales no están relacionadas con el contenido de la tarea, pero te permiten construir un punto de partida, y el proceso de optimización obliga a estas variables a tomar valores cero y garantizar la admisibilidad de la solución óptima.
Formas de solución por el método de base artificial:
- método M (tabla simplex);
- método simplex de dos etapas o dos fases (notación básica, método simplex modificado, método simplex en forma de columna, método simplex en forma de línea).
Si existen restricciones con el signo ≥ en la condición del problema, entonces se pueden reducir a la forma ∑a ji b j multiplicando ambas partes de la desigualdad por -1. Introducimos m variables adicionales x n+j ≥0(j =1,m ) y transformamos las restricciones a la forma de igualdades
(2)
Supongamos que todas las variables iniciales del problema x 1 , x 2 ,..., x n no son básicas. Entonces las variables adicionales serán básicas, y una solución particular al sistema de restricciones tiene la forma
X 1 = X 2 = ... = X norte = 0, X norte + j = segundo j , j = 1, metro . (3)
Dado que en este caso el valor de la función objetivo F 0 = 0 , podemos representar F(x) de la siguiente manera:
F(x)=∑c yo x yo + F 0 =0 (4)
La tabla simplex inicial (tabla simplex 1) se compila con base en las ecuaciones (2) y (4). Si las variables adicionales x n+j están precedidas por el signo “+”, como en (2), entonces todos los coeficientes antes de las variables x i y el término libre b j se ingresan en la tabla simplex sin cambios. Los coeficientes de la función objetivo durante su maximización se ingresan en la línea inferior de la tabla simplex con signos opuestos. Los miembros libres en la tabla símplex determinan la solución del problema.
El algoritmo para resolver el problema es el siguiente:
1er paso Los elementos de la columna de miembros libres se buscan. Si todos son positivos, entonces se ha encontrado una solución básica aceptable y se debe pasar al paso 5 del algoritmo, que corresponde a encontrar la solución óptima. Si hay términos libres negativos en la tabla símplex inicial, entonces la solución no es válida y debe ir al paso 2.
2do paso Para encontrar una solución factible, se lleva a cabo, mientras que es necesario decidir cuál de las variables no básicas incluir en la base y qué variable retirar de la base.
Tabla 1.
| variables base | Miembros gratis en restricciones | Variables no básicas | |||||
| x1 | x2 | ... | xl | ... | x norte|||
| xn+1 | segundo 1 | un 11 | un 12 | ... | un 1l | ... | un 1n |
| xn+2 | segundo 2 | un 21 | un 22 | ... | un 2l | ... | un 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | un r1 | un r2 | ... | un rl | ... | un rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | un m1 | un m2 | ... | un ml | ... | amén |
| F(x)máx | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Para hacer esto, elija cualquiera de los elementos negativos de la columna de miembros libres (que sea b 2 principal o permitido). Si no hay elementos negativos en la fila con un miembro libre negativo, entonces el sistema de restricciones es inconsistente y el problema no tiene solución.
Al mismo tiempo, se excluye de la BP la variable que es la primera en cambiar de signo con un incremento en el NP x l seleccionado. Este será x n+r , cuyo índice r se determina a partir de la condición
aquellos. la variable que corresponde a la razón más pequeña del término libre al elemento de la columna principal seleccionada. Esta relación se llama relación símplex. Sólo se deben considerar las relaciones símplex positivas.
La cadena correspondiente a la variable x n+r se llama conducir o permitir. El elemento de la tabla símplex a rl , que está en la intersección de la fila principal y la columna principal, se denomina elemento principal o de resolución. Encontrar el elemento principal finaliza el trabajo con cada siguiente cuadro símplex.
3er paso Se calcula una nueva tabla simplex, cuyos elementos se recalculan a partir de los elementos de la tabla simplex del paso anterior y se marcan con un primo, es decir b" j , a" ji , c" i , F" 0 . Los elementos se recalculan según las siguientes fórmulas:
Primero, la fila y la columna que encabezaban la tabla simplex anterior se completarán en la nueva tabla simplex. La expresión (5) significa que el elemento a "rl en lugar del elemento principal es igual al recíproco del elemento de la tabla simplex anterior. Los elementos de la fila a ri se dividen por el elemento principal, y los elementos del columna a jl también se dividen por el elemento principal, pero se toman con el signo opuesto Los elementos b" r y c" l se calculan de acuerdo con el mismo principio.
El resto de las fórmulas se pueden escribir fácilmente usando .
El rectángulo se construye de acuerdo con la antigua tabla simplex de tal manera que una de sus diagonales está formada por los elementos recalculados (a ji) y principales (a rl) (Fig. 1). La segunda diagonal está determinada de forma única. Para encontrar un nuevo elemento a "ji, el producto de los elementos de la diagonal opuesta dividido por el elemento principal se resta del elemento a ji (esto se indica con el signo" - "en la celda). De manera similar, los elementos b" j, (j≠r) yc" i se recalculan, (i≠l).
4to paso. El análisis de una nueva tabla simplex comienza desde el primer paso del algoritmo. La acción continúa hasta que se encuentra una solución básica factible, es decir, todos los elementos de la columna de miembros libres deben ser positivos.
5to paso Creemos que se ha encontrado una solución básica aceptable. Nos fijamos en los coeficientes de la línea de la función objetivo F(x) . Un signo de la optimización de una tabla simplex es la no negatividad de los coeficientes para variables no básicas en la fila F.
Arroz. 1. Regla del rectángulo
Si entre los coeficientes de la fila F hay negativos (con la excepción del término libre), entonces debe ir a otra solución básica. Al maximizar la función meta, la base incluye la de las variables no básicas (por ejemplo, x l), cuya columna corresponde al valor absoluto máximo del coeficiente negativo c l en la fila inferior de la tabla simplex. Esto le permite seleccionar la variable cuyo aumento conduce a una mejora en la función objetivo. La columna correspondiente a la variable x l se llama columna principal. A su vez, se excluye de la base aquella variable x n+r, cuyo índice r viene determinado por la relación mínima símplex:
El renglón correspondiente a x n+r se denomina renglón inicial, y el elemento de la tabla símplex a rl , que se encuentra en la intersección del renglón inicial y la columna inicial, se denomina elemento protagónico.
6to paso. de acuerdo con las reglas establecidas en el 3er paso. El procedimiento continúa hasta que se encuentra una solución óptima o se concluye que no existe.
Si en el proceso de optimización de la solución en la columna principal todos los elementos son no positivos, entonces no se puede seleccionar la fila principal. En este caso, la función en el dominio de las soluciones admisibles del problema no está acotada desde arriba y F max ->&∞.
Si en el siguiente paso de la búsqueda de un extremo una de las variables básicas se vuelve igual a cero, entonces la solución básica correspondiente se llama degenerada. En este caso, se produce el llamado bucle, que se caracteriza por el hecho de que la misma combinación de BP comienza a repetirse con cierta frecuencia (el valor de la función F se conserva en este caso) y es imposible cambiar a una nueva solución básica aceptable. El bucle es uno de los principales inconvenientes del método símplex, pero es relativamente raro. En la práctica, en tales casos, generalmente se niega a ingresar en la base la variable cuya columna corresponde al valor absoluto máximo del coeficiente negativo en la función objetivo, y se elige aleatoriamente una nueva solución básica.
Ejemplo 1. Resolver un problema
máx(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Método simplex y dar una interpretación geométrica del proceso de solución.
La interpretación gráfica de la solución del problema se muestra en la fig. 2. El valor máximo de la función objetivo se alcanza en la parte superior del ODZP con coordenadas . Resolvamos el problema usando tablas simplex. Multiplicamos la segunda restricción por (-1) e introducimos variables adicionales para llevar las desigualdades a la forma de igualdades, entonces
Las variables iniciales x 1 y x 2 se toman como no básicas, y las adicionales x 3 , x 4 y x 5 se consideran básicas y compilamos una tabla simplex (tabla simplex 2). La solución correspondiente a la tabla simplex. 2, no es válido; el elemento principal se perfila y selecciona de acuerdo con el paso 2 del algoritmo anterior. La siguiente pestaña símplex. 3 define una solución básica admisible; 2 El elemento principal se delinea y selecciona de acuerdo con el quinto paso del algoritmo para resolver el problema. Pestaña. 4 corresponde a la solución óptima del problema, por lo tanto: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x4 = 8; Fmáx = 20.
Arroz. 2. Solución gráfica del problema
