Explicación detallada del método simplex. Un ejemplo de resolución de un problema directo y dual mediante el método simplex. Método simplex, resolución de un problema con una base inicial.

Conferencia 3. Tablas simplex. Algoritmo método simplex.

§ 3 MÉTODO SIMPLEX

3.1. Idea general del método simplex. Interpretación geométrica

El método gráfico es aplicable a una clase muy limitada de problemas. programación lineal: puede resolver eficazmente problemas que contengan no más de dos variables. Se consideraron los teoremas básicos de la programación lineal, de los cuales se deduce que si un problema de programación lineal tiene una solución óptima, entonces corresponde al menos a un punto angular del poliedro de soluciones y coincide con al menos una de las soluciones básicas admisibles del sistema de restricciones. Se indicó una forma de resolver cualquier problema de programación lineal: enumerar un número finito de soluciones básicas factibles al sistema de restricciones y seleccionar entre ellas aquella en la que la función objetivo constituye la solución óptima. Geométricamente, esto corresponde a enumerar todos los puntos de las esquinas del poliedro solución. Una búsqueda tan exhaustiva conducirá en última instancia a una solución óptima (si existe), pero su implementación práctica está asociada con enormes dificultades, ya que para problemas reales el número de soluciones básicas factibles, aunque finitas, puede ser extremadamente grande.

El número de soluciones básicas permitidas a buscar se puede reducir si la búsqueda no se realiza de forma aleatoria, sino teniendo en cuenta los cambios en la función lineal, es decir asegurando que todos siguiente solución era “mejor” (o al menos “no peor”) que la anterior, según los valores de la función lineal (aumentándola al encontrar el máximo, disminuyéndola al encontrar el mínimo
). Esta búsqueda le permite reducir el número de pasos para encontrar el óptimo. Expliquemos esto con un ejemplo gráfico.

Deja que el área soluciones admisibles representado por un polígono ABCDE. Supongamos que su punto de esquina A Corresponde al original aceptable. solución básica. Una búsqueda aleatoria requeriría probar cinco soluciones básicas factibles correspondientes a los cinco puntos de las esquinas del polígono. Sin embargo, del dibujo se desprende claramente que después de la cima A es ventajoso moverse a un vértice vecino EN, y luego al punto óptimo CON. En lugar de cinco, pasamos por sólo tres vértices, mejorando constantemente la función lineal.

La idea de mejorar sucesivamente la solución formó la base de un método universal para resolver problemas de programación lineal: Método simplex o método de mejora secuencial del plan.

El significado geométrico del método simplex consiste en una transición secuencial de un vértice del poliedro restrictivo (llamado inicial) al vecino, en el que la función lineal toma el mejor valor (al menos no el peor) en relación con el objetivo del problema; hasta que se encuentre la solución óptima: el vértice donde se logra el valor óptimo de la función objetivo (si el problema tiene un óptimo final).

El método simplex fue propuesto por primera vez por el científico estadounidense J. Danzig en 1949, pero ya en 1939 las ideas del método fueron desarrolladas por el científico ruso L.V. Kantorovich.

El método simplex, que permite resolver cualquier problema de programación lineal, es universal. Actualmente, se utiliza para cálculos por computadora, pero los ejemplos simples que utilizan el método simplex se pueden resolver manualmente.

Para implementar el método simplex (mejora secuencial de la solución) es necesario dominar tres elementos principales:

un método para determinar cualquier solución básica inicial viable a un problema;

la regla de transición hacia la mejor solución (más precisamente, no peor);

Criterio para comprobar la optimización de la solución encontrada.

Para utilizar el método simplex, el problema de programación lineal debe reducirse a forma canónica, es decir. el sistema de restricciones debe presentarse en forma de ecuaciones.

La literatura describe con suficiente detalle: encontrar el punto inicial plan de referencia(la solución básica factible inicial), utilizando también el método de base artificial, encontrando el plan de referencia óptimo, resolviendo problemas utilizando tablas simplex.

3.2. Algoritmo del método simplex.

Consideremos la solución del ZLP usando el método simplex y presentémosla en relación con el problema de maximización.

1. A partir de las condiciones del problema se elabora su modelo matemático.

2. El modelo compilado se convierte a forma canónica. En este caso se puede identificar una base con un plan de referencia inicial.

3. El modelo canónico del problema se escribe en forma de tabla simplex de modo que todos los términos libres sean no negativos. Si se selecciona el plan de referencia inicial, continúe con el paso 5.

Tabla simplex: un sistema de ecuaciones de restricción y una función objetivo se ingresan en forma de expresiones resueltas con respecto a la base inicial. La línea que contiene los coeficientes. función objetivo
, llamado
– una cadena o una cadena de la función objetivo.

4. Encuentre el plan de referencia inicial realizando transformaciones simplex con elementos resolutivos positivos correspondientes a las relaciones simplex mínimas, y sin tener en cuenta los signos de los elementos.
-pauta. Si durante las transformaciones se encuentra una fila 0 cuyos elementos, excepto el término libre, son ceros, entonces el sistema de ecuaciones de restricción del problema es inconsistente. Si encontramos una fila 0 en la que, aparte del término libre, no hay otros elementos positivos, entonces el sistema de ecuaciones restrictivas no tiene soluciones no negativas.

Llamaremos a la reducción del sistema (2.55), (2.56) a una nueva base. transformación simplex . Si consideramos una transformación simplex como una operación algebraica formal, entonces podemos observar que como resultado de esta operación, los roles se redistribuyen entre dos variables incluidas en un determinado sistema. funciones lineales: una variable pasa de dependiente a independiente, y la otra, por el contrario, pasa de independiente a dependiente. Esta operación se conoce en álgebra como Paso de eliminación de Jordania.

5. Se examina la optimización del plan de soporte inicial encontrado:

a) si en
– no hay elementos negativos en la fila (sin contar el término libre), entonces el plan es óptimo. Si no hay ceros, entonces sólo hay un plan óptimo; si hay al menos un cero, entonces hay un número infinito de planes óptimos;

b) si c
– hay al menos un elemento negativo en la fila, que corresponde a una columna de elementos no positivos, entonces
;

c) si en
– la fila tiene al menos un elemento negativo y su columna tiene al menos un elemento positivo, entonces puede pasar a un nuevo plan de referencia que se acerque más al óptimo. Para hacer esto, la columna especificada debe designarse como columna de resolución, utilizando la relación simplex mínima, encontrar la fila de resolución y realizar una transformación simplex. El plan de referencia resultante se examina nuevamente para determinar su optimización. El proceso descrito se repite hasta obtener un plan óptimo o hasta establecer la insolubilidad del problema.

La columna de coeficientes de una variable incluida en la base se llama resolución. Por lo tanto, seleccionar una variable ingresada en la base (o seleccionar una columna de resolución) por el elemento negativo
-strings, proporcionamos función creciente
.

Es un poco más difícil determinar la variable que se excluirá de la base. A tal efecto, las relaciones de los miembros libres con elementos positivos columna de resolución (tales relaciones se llaman simplex) y encuentre la más pequeña entre ellas, lo que determina la fila (resolución) que contiene la variable excluida. La elección de una variable excluida de la base (o la elección de una línea de resolución) según la relación simplex mínima garantiza, como ya se ha establecido, la positividad de los componentes de la base en el nuevo plan de referencia.

En el punto 3 del algoritmo, se supone que todos los elementos de la columna de miembros libres no son negativos. Este requisito no es necesario, pero si se cumple, todas las transformaciones simples posteriores se realizan solo con elementos de resolución positivos, lo cual es conveniente para los cálculos. Si hay números negativos en la columna de términos libres, entonces el elemento de resolución se elige de la siguiente manera:

1) mira la línea correspondiente a algún término libre negativo, por ejemplo – una fila, y seleccione cualquier elemento negativo en ella, y la columna correspondiente se toma como resolutiva (asumimos que las restricciones del problema son consistentes);

2) componer las relaciones de los elementos de la columna de términos libres con los elementos correspondientes de la columna resolutiva que tienen los mismos signos (relaciones simples);

3) elija la más pequeña de las relaciones simplex. Esto determinará la cadena de habilitación. Sea, por ejemplo, r-línea;

4) en la intersección de la columna y la fila de resolución, se encuentra un elemento de resolución. Si el elemento es permisivo –cadenas, luego de la transformación simplex el término libre de esta cadena se volverá positivo. De lo contrario, en el siguiente paso volvemos a -línea. Si el problema se puede resolver, después de un cierto número de pasos no quedarán elementos negativos en la columna de términos libres.

Si una determinada situación real de producción se expresa en forma de PLP, entonces las variables adicionales que deben introducirse en el modelo en el proceso de conversión a la forma canónica siempre tienen un cierto significado económico.

método simplex es un proceso iterativo de solución dirigida de un sistema de ecuaciones paso a paso, que comienza con solución de referencia y en busca mejor opción se mueve a lo largo de los puntos de las esquinas del área de solución factible, mejorando el valor de la función objetivo hasta que la función objetivo alcanza el valor óptimo.

Objeto del servicio. El servicio está destinado a soluciones en línea Problemas de programación lineal (LPP) utilizando el método simplex en siguientes formularios entradas:

• en forma de tabla simplex (método de transformación de Jordan); forma básica archivos;
• método simplex modificado; en forma de columna; en forma de línea.

Instrucciones. Seleccione el número de variables y el número de filas (número de restricciones). La solución resultante se almacena en archivo de palabra y Excel.

Número de variables 2 3 4 5 6 7 8 9 10
Número de filas (número de restricciones) 1 2 3 4 5 6 7 8 9 10

En este caso, no tenga en cuenta restricciones como x i ≥ 0. Si no hay restricciones en la tarea para algún x i, entonces el ZLP debe convertirse al KZLP o utilizar este servicio. La solución determina automáticamente el uso. método M(método simple con base artificial) y método simplex de dos etapas.

Lo siguiente también se utiliza con esta calculadora:
Método gráfico para resolver ZLP.
Solución del problema del transporte.
Resolver un juego de matrices
Usando el servicio en modo en línea puedes determinar el precio de un juego de matrices (límites superior e inferior), consulta la disponibilidad punto de silla, encuentre una solución a una estrategia mixta utilizando los siguientes métodos: minimax, método simplex, método gráfico (geométrico), método de Brown.
Extremo de una función de dos variables.
Problemas de programación dinámica
Distribuir 5 lotes homogéneos de bienes entre tres mercados para obtener ingreso máximo de su venta. Los ingresos por ventas en cada mercado G(X) dependen del número de lotes vendidos del producto X y se presentan en la tabla.

Volumen de producto X (en lotes)	Ingreso G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Algoritmo del método simplex incluye los siguientes pasos:

1. Elaboración del primer plan básico. Transición a la forma canónica del problema de programación lineal mediante la introducción de variables de equilibrio adicionales no negativas.
2. Comprobar la optimización del plan. Si hay al menos un coeficiente de línea de índice menor que cero, entonces el plan no es óptimo y debe mejorarse.
3. Determinar la columna y fila principal. De los coeficientes negativos de la línea del índice, se selecciona el mayor en valor absoluto. Luego, los elementos de la columna de miembros libres de la tabla simplex se dividen en elementos del mismo signo de la columna principal.
4. Construyendo un nuevo plan de referencia. La transición a un nuevo plan se lleva a cabo recalculando la tabla simplex utilizando el método de Jordan-Gauss.

Si es necesario encontrar el extremo de la función objetivo, entonces estamos hablando de acerca de la búsqueda valor mínimo(F(x) → min , ver ejemplo de resolución de una función de minimización) y valor máximo((F(x) → max , ver ejemplo de resolución de una maximización de función)

Una solución extrema se logra en el límite de la región de soluciones factibles en uno de los vértices de los puntos de las esquinas del polígono, o en el segmento entre dos puntos de las esquinas adyacentes.

Teorema fundamental de la programación lineal. si el objetivo función ZLP alcanza un valor extremo en algún punto de la región de soluciones factibles, luego toma este valor en el punto de la esquina. Si la función objetivo ZLP alcanza un valor extremo en más de un punto de esquina, entonces toma el mismo valor en cualquiera de las combinaciones lineales convexas de estos puntos.

La esencia del método simplex.. El movimiento al punto óptimo se realiza moviéndose desde un punto de esquina al vecino, lo que acerca y más rápido a X opt. Tal esquema para enumerar puntos, llamado método simplex, sugerido por R. Danzig.
Los puntos de esquina se caracterizan por m variables básicas, por lo que la transición de un punto de esquina a uno adyacente se puede lograr cambiando solo una variable básica en la base a una variable de una no base.
Implementación del método simplex vigente varias características y planteamientos de problemas, LP tiene varias modificaciones.

La construcción de tablas simplex continúa hasta obtener la solución óptima. ¿Cómo se puede utilizar una tabla simplex para determinar que la solución a un problema de programación lineal es óptima?
Si la última línea (valores de la función objetivo) no contiene elementos negativos, por tanto, encontrará el plan óptimo.

Observación 1. Si una de las variables básicas es igual a cero, entonces el punto extremo correspondiente a dicha solución básica es degenerado. La degeneración ocurre cuando hay ambigüedad en la elección de la línea guía. Es posible que no notes la degeneración del problema en absoluto si eliges otra línea como guía. En caso de ambigüedad, se debe seleccionar la fila con el índice más bajo para evitar bucles.

Observación 2. Sea en algún punto extremo todas las diferencias simplex no negativas D k ³ 0 (k = 1..n+m), es decir se obtiene una solución óptima y existe A k - un vector no básico para el cual D k ​​= 0. Entonces el máximo se logra al menos en dos puntos, es decir existe un óptimo alternativo. Si introducimos esta variable x k en la base, el valor de la función objetivo no cambiará.

Observación 3. Solución problema dual está en la última tabla simplex. Los últimos m componentes del vector de diferencias simplex (en las columnas de variables de equilibrio) son la solución óptima al problema dual. Los valores de las funciones objetivo de los problemas directo y dual en puntos óptimos coinciden.

Observación 4. Al resolver el problema de minimización, se introduce en la base el vector con la mayor diferencia simplex positiva. A continuación se aplica el mismo algoritmo que para el problema de maximización.

Si se especifica la condición “Es necesario que las materias primas tipo III se consuman por completo”, entonces la condición correspondiente es una igualdad.

Paso 0. Etapa preparatoria.

Reducimos el problema de LP a forma especial (15).

Paso 1. Compilando tabla simplex, correspondiente a la forma especial:

Tenga en cuenta que esta tabla corresponde a una solución básica admisible
problemas (15). El valor de la función objetivo en esta solución.

Paso 2. Comprobación de optimización

Si entre los elementos de la fila del índice hay tablas simplex
entonces no hay un solo elemento positivo
, se encuentra la solución óptima al problema de LP :. El algoritmo termina.

Paso 3. Control de indecidibilidad

si entre
hay un elemento positivo
, y en la columna correspondiente
no hay un solo elemento positivo
, entonces la función objetivo l es ilimitado desde abajo en el conjunto admisible. En este caso no existe una solución óptima. El algoritmo termina.

Paso 4. Seleccionar una columna principal q

entre los elementos
elige el elemento positivo máximo
.Declaramos que esta columna es la columna principal (permisiva).

Paso 5. Selección de línea principal pag

Entre los elementos positivos de la columna
encontrar el elemento
, para lo cual se cumple la igualdad

.

Cadena pag Declaramos que es líder (lo permite). Elemento
Lo declaramos líder (permitiendo).

Paso 6. Conversión de tabla simplex

Creamos una nueva tabla simplex en la que:

a) en lugar de la variable básica anotar , en lugar de una variable no básica anotar ;

b) el elemento principal se reemplaza por el valor inverso
;

c) todos los elementos de la columna principal (excepto
) multiplicar por
;

d) todos los elementos de la línea de enfilación (excepto
) multiplicar por ;

e) los elementos restantes de la tabla simplex se transforman según el siguiente esquema de “rectángulo”.

Del elemento se resta el producto de tres factores:

el primero es el elemento correspondiente de la columna principal;

el segundo es el elemento correspondiente de la línea principal;

el tercero es el recíproco del elemento principal
.

El elemento transformado y los tres factores que le corresponden son precisamente los vértices del “rectángulo”.

Paso 7 La transición a la siguiente iteración se realiza volviendo al paso 2.

2.3. Algoritmo del método simplex para el problema máximo.

El algoritmo del método simplex para el problema máximo difiere del algoritmo para el problema mínimo solo en los signos de la línea índice de los coeficientes en la función objetivo.
, a saber:

En el paso 2:
:

en el paso 3
. La función objetivo no está acotada desde arriba en el conjunto admisible.

en el paso 4:
.

2.4. Un ejemplo de resolución de un problema utilizando el método simplex.

Resuelva el problema escrito en la forma (15).

Creemos una tabla simplex:

Dado que los coeficientes de la recta de la función objetivo no son negativos, la solución base inicial no es óptima. El valor de la función objetivo para esta base. L=0.

Seleccione la columna principal: esta es la columna correspondiente a la variable .

Seleccione la línea principal. Para ello encontramos
. Por tanto, la línea principal corresponde a la variable .

Transformamos la tabla simplex introduciendo una variable. en la base y generando la variable desde la base. Obtenemos la tabla:

Se completa una iteración del método. Pasemos a una nueva iteración. La tabla resultante no es óptima. La solución básica correspondiente a la tabla tiene la forma. El valor de la función objetivo sobre esta base. L = -2.

La columna principal aquí es la columna correspondiente a la variable. . Línea principal: la línea correspondiente a la variable. . Realizadas las transformaciones obtenemos una tabla simplex:

Otra iteración completada. Pasemos a una nueva iteración.

La línea de la función objetivo no contiene valores positivos, lo que significa que la solución básica correspondiente es óptima y el algoritmo termina.

Es necesario resolver un problema de programación lineal.

Función objetivo:

2x 1 +5x 2 +3x 3 +8x 4 →mín.

Condiciones limitantes:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

Llevemos el sistema de restricciones a la forma canónica; para ello es necesario pasar de las desigualdades a las igualdades, con la adición de variables adicionales.

Dado que nuestro problema es un problema de minimización, necesitamos transformarlo en un problema de búsqueda de máximo. Para ello cambiamos los signos de los coeficientes de la función objetivo por los opuestos. Escribimos los elementos de la primera desigualdad sin cambios, agregando una variable adicional x 5 y cambiando el signo “≤” a “=". Dado que la segunda y tercera desigualdades tienen signos "≥", es necesario cambiar los signos de sus coeficientes por los opuestos e introducir en ellos variables adicionales x 6 y x 7, respectivamente. Como resultado, obtenemos un problema equivalente:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Procedemos a la formación de la tabla simplex inicial. Los coeficientes de la función objetivo con signo opuesto se ingresan en la fila F de la tabla.

					Miembro gratuito
F
X5
X6
X7

En la tabla que hemos compilado hay elementos negativos en la columna de términos libres, entre ellos encontramos el máximo en módulo: este es el elemento: -6, establece la fila principal - X6. En esta línea también encontramos el elemento máximo negativo en módulo: -10 se ubica en la columna X3, que será la columna principal. La variable de la fila principal se excluye de la base y la variable correspondiente a la columna principal se incluye en la base. Recalculemos la tabla simplex:

	X1	X2	X6	X4	Miembro gratuito
F	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

En la tabla que hemos compilado hay elementos negativos en la columna de términos libres, entre ellos encontramos el máximo en módulo: este es el elemento: -0,4, establece la fila principal - X7. En esta línea también encontramos el elemento máximo negativo en módulo: -8.3 se ubica en la columna X2, que será la columna principal. La variable de la fila principal se excluye de la base y la variable correspondiente a la columna principal se incluye en la base. Recalculemos la tabla simplex:

	X1	X7	X6	X4	Miembro gratuito
F	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

Como no hay elementos negativos en la columna de términos libres, se ha encontrado una solución admisible. La fila F contiene elementos negativos, lo que significa que la solución resultante no es óptima. Definamos la columna principal. Para hacer esto, encontraremos en la fila F el elemento negativo con el módulo máximo: esto es -1,988. La fila principal será aquella para la cual la relación entre el término libre y el elemento correspondiente de la columna principal sea mínima. La fila principal es X2 y el elemento principal es: 0,313.

	X2	X7	X6	X4	Miembro gratuito
F	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

Como no hay elementos negativos en la cadena F, se ha encontrado la solución óptima. Porque tarea original estaba buscando un mínimo, entonces la solución óptima será el término libre de la cadena F, tomado con el signo opuesto. F=1,924
con valores de variables iguales: x 3 =0.539, x 1 =0.153. Las variables x 2 y x 4 no están incluidas en la base, por lo que x 2 =0 x 4 =0.

Si necesita resolver un problema de programación lineal usando tablas simplex, entonces nuestro servicio en línea te daré gran ayuda. El método simplex implica la enumeración secuencial de todos los vértices de la región. valores aceptables para encontrar el vértice donde la función toma un valor extremo. En la primera etapa, se encuentra alguna solución, que se mejora en cada paso posterior. Esta solución se llama básica. A continuación se muestra la secuencia de acciones al resolver un problema de programación lineal utilizando el método simplex:

Primer paso.

En la tabla compilada, en primer lugar, debe mirar la columna con miembros gratuitos. Si contiene elementos negativos, entonces es necesario pasar al segundo paso, si no, al quinto. Segundo paso. En el segundo paso, es necesario decidir qué variable excluir de la base y cuál incluir para volver a calcular la tabla simplex. Para hacer esto, miramos la columna con términos libres y encontramos un elemento negativo en ella. La línea con un elemento negativo se llamará principal. En él encontramos el elemento máximo negativo en módulo, la columna correspondiente es la esclava. Si entre los miembros gratuitos hay

valores negativos

, pero no está en la fila correspondiente, entonces dicha tabla no tendrá soluciones. La variable de la fila principal ubicada en la columna de términos libres se excluye de la base y la variable correspondiente a la columna principal se incluye en la base.	Tabla 1.	variables básicas
		Miembros gratuitos bajo restricciones	Variables no básicas	...	x1	...	x2
xl	xn	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	arn	xn+m	b m	...	un m1	...	un m2
un ml	un minuto	F(x)máx	F 0	...	F(x)máx	...	-c 1

-c 2

-c norte

Tercer paso. En el tercer paso, recalculamos toda la tabla simplex usando fórmulas especiales que se pueden ver usando. Cuarto paso.