Hogar › Ajustes › ¿Con qué finalidad se utiliza el método de base artificial? Ejemplos de resolución de ZLP mediante el método de base artificial. Un ejemplo de resolución de un problema utilizando el método de base artificial.

¿Con qué finalidad se utiliza el método de base artificial? Ejemplos de resolución de ZLP mediante el método de base artificial. Un ejemplo de resolución de un problema utilizando el método de base artificial.

Resolvamos el ZLP en la forma

En este caso esquema general método simplex sufre algunos cambios. A saber:

1) Deja que la base de algunos. solución de referencia y correspondiente a ello tabla simplex. EN línea superior Esta tabla (encabezados de columnas) contiene variables libres; la columna más a la izquierda contiene variables básicas; la columna de más a la derecha es la columna de términos libres y la fila de más abajo es la fila función objetivo y se llama vector de estimaciones relativas. El resto del contenido de la tabla son columnas de la matriz de restricciones correspondientes a las columnas correspondientes de variables libres. Las coordenadas del vector de estimaciones relativas se encuentran según la regla: el vector de los coeficientes de las variables básicas en la función objetivo se multiplica escalarmente por i aésima columna de la tabla simplex y reste el coeficiente de la función objetivo para la variable libre correspondiente del número encontrado.

2) Si todas las estimaciones relativas (fila inferior de esta tabla) no son negativas, entonces se ha construido una solución de referencia óptima.

3) Si hay una estimación negativa y la columna correspondiente (resolutiva) consta de elementos no positivos, entonces la función objetivo no tiene solución z(incógnita), es decir, máx. z(incógnita) ®+¥.

4) En caso contrario, seleccione el elemento principal (especifica la fila principal) y realice un paso de eliminación de Jordan con él, pasando a una nueva tabla simplex, que se analiza como en el punto 2).

Método base artificial

El método de base artificial se utiliza para resolver problemas de PL en el caso en que el problema no tiene una solución de referencia inicial con una base de vectores unitarios.

Dejemos que el problema de LP se dé en forma canónica, es decir, tiene la forma (2.1.1) y no contiene ninguna base unitaria. Para este problema construimos un problema auxiliar (AP):

Aquí w 1 , w 2 ,…, w m– variables artificiales. Escribamos las restricciones en forma vectorial: A 1 incógnita 1 +A 2 incógnita 2 +…+An x n+Un +1 w 1 +…+Un norte + m w m =B, Dónde , , …, , , , …, , . Así, los vectores , , …, forman una base unitaria en R metro, y todas las variables artificiales correspondientes a estos vectores serán básicas. A continuación, se construye una tabla simplex regular. Si el problema no tiene solución debido a que la función objetivo es ilimitada, entonces el problema original tampoco tiene solución por la misma razón. Sea como resultado de los familiares que utilizan el método simplex. cambios necesarios Obtuvimos la tabla simplex óptima para el VZ. Es obvio que valor máximo la función objetivo VZ es igual a 0, es decir, máx. F=0. si máximo F<0, то исходная задача ЛП не имеет решения в силу несовместности системы ограничений. Предположим, что max F=0. Entonces son posibles las siguientes situaciones:

1) todas las variables artificiales quedaron libres y fueron excluidas de la tabla. En este caso tachamos las columnas correspondientes a las variables artificiales y la última fila. En su lugar, asignamos una nueva línea de estimaciones, pero utilizando la función objetivo original. z(incógnita). Así, obtenemos la tabla simplex inicial para el problema LP original, al que aplicamos el método simplex;

2) en la solución óptima del problema, al menos una variable artificial sigue siendo básica. Entonces:

a) o todos los números en las líneas correspondientes a las variables artificiales básicas restantes son iguales a 0;

b) o hay al menos uno diferente de 0.

En el primer caso hacemos lo mismo que en el punto 1). En el segundo, seleccionamos cualquier elemento distinto de cero como elemento principal y realizamos un paso de eliminación de Jordan. Después de un número finito de pasos llegaremos al punto 1) o al punto 2)a).

Tenga en cuenta que si entre los vectores aj , j=1,2,…,norte, había vectores que podrían incluirse en la base, entonces las variables artificiales se introducen solo en aquellas ecuaciones del sistema de restricciones en las que no hay una variable de base.

Ejemplo. Maximizar función z=incógnita 1 +2incógnita 2 -2incógnita 3 con restricciones

Solución. Transformemos el problema original. programación lineal a canónico (ver (2.1.1). Para hacer esto, introducimos variables adicionales no negativas en las restricciones. Es decir, en la primera desigualdad: la variable incógnita 4 con un signo “+”, el segundo – incógnita 5 con un signo “-” (ver §2.2). El sistema de restricciones tomará la forma:

Escribamos este sistema en forma vectorial: A 1 incógnita 1 +A 2 incógnita 2 +A 3 incógnita 3 +A 4 incógnita 4 +A 5 incógnita 5 =B, Dónde

Es obvio que en este sistema de restricciones no existe una base unitaria. Esto significa que entre los vectores aj No hay tres vectores unitarios necesarios que deban formar una base en R 3. Sin embargo, tenga en cuenta que el vector A 4 es parte de la base. Corresponde a la variable básica incógnita 4. Es necesario encontrar dos vectores unitarios más. Para ello aplicamos el método de la base artificial. Introduzcamos variables artificiales en aquellas ecuaciones de restricción en las que la variable básica no está presente. incógnita 4 y construye el siguiente problema auxiliar (AP):

F=-w 1 -w 2 ®máx.

Dónde w 1 , w 2 – variables artificiales. El sistema de restricciones a la contaminación del aire en forma vectorial tiene la forma: A 1 incógnita 1 +A 2 incógnita 2 +A 3 incógnita 3 +A 4 incógnita 4 +A 5 incógnita 5 +A 6 w 1 +A 7 w 2 =B, donde los vectores aj , j=1,2,3,4,5 se definen de la misma manera que arriba, y y . Así, los vectores A 4 , A 6 , A 7 forman una base en R 3 y corresponden a variables básicas (BP) – incógnita 4 , w 1 , w 2. Todas las demás variables, a saber incógnita 1 , incógnita 2 , incógnita 3 , incógnita 5 son declarados libres (SP). A continuación, aplicamos el método simplex habitual a la entrada de aire. Como antes, ver §5.1, el diseño de referencia inicial se obtiene asignando valores iguales a cero a las variables libres. En este caso, las variables básicas toman valores iguales a los números de la fila correspondiente de la columna de coeficientes libres. EN, eso es incógnita 1 =incógnita 2 =incógnita 3 =incógnita 5 =0¸a incógnita 4 =8, w 1 =4, w 2 = 12. Construimos una tabla simplex correspondiente al plan de referencia inicial:

SP BP.	x1	x2	incógnita 3	incógnita 5	B
x4		-3
w 1				-1
w 2		-2
F	-4		-3		-16

Con esta tabla realizamos las transformaciones necesarias (ver §5.1) del método simplex hasta obtener una tabla simplex óptima u obtener insolvabilidad. En nuestro caso, ya en el segundo paso tendremos la siguiente tabla simplex:

SP BP.	w 1	x2	incógnita 3	w 2	B
x4	-0,5	-3	-0,5	-0,5
x1	0,25		0,75	0,25
incógnita 5	-0,75	-2
F

Esta tabla será óptima para EOI. Al mismo tiempo, todas las variables artificiales se volvieron libres y máximas. F=0. Tachar las columnas correspondientes a las variables ficticias y la última fila, y asignar una nueva fila de estimaciones utilizando la función objetivo original z(incógnita), obtenemos la tabla simplex inicial para el problema LP original:

SP BP.	x2	incógnita 3	B
x4	-3	-0,5
x1		0,75
incógnita 5	-2
z	-2	2,75

Habiendo analizado la última tabla, concluimos que el problema PL original no tiene solución debido a que la función objetivo es ilimitada.

Ejemplo. Minimizar función bajo restricciones

Si introducimos variables adicionales no negativas , , , y pasamos al problema de encontrar el máximo de la función objetivo, el problema original tomará la forma:

La solución básica (plan admisible) tendrá la forma: , a , , w 1 =10, w 2 = 5. Construimos una tabla simplex para el aeródromo correspondiente al plano de referencia inicial:

SP BP.	x1	x2	incógnita 3	incógnita 4	B
w 1			-1
w 2				-1
x5
x6	-1
F	-1	-1			-15

Realizando transformaciones mediante el método de Jordan-Gauss, en el segundo paso tendremos una tabla simplex óptima de VZ (5.2.2). Tachar las columnas correspondientes a las variables ficticias y la última fila, y asignar una nueva fila de puntuaciones utilizando la función objetivo z 1 (incógnita), obtenemos la tabla simplex inicial para el problema (5.2.1).

Método de base artificial (problema M).

Para muchos problemas de programación lineal escritos en forma de problema principal y que tienen planes de referencia, no siempre hay m vectores unitarios entre los vectores P j.

Considere el siguiente problema:

Supongamos que necesitamos encontrar el máximo de una función.

F = do 1 incógnita 1 + do 2 incógnita 2 + ……+ do norte incógnita norte (1)

bajo condiciones

……………………………………… (2)

Dónde b i  0 ( i=l, metro), metro<.>norte y entre los vectores P 1 , P 2 , …, P n no hay m unos unitarios.

Definición. La tarea de determinar el valor máximo de una función.

F=c 1 incógnita 1 + do 2 incógnita 2 + ……+ do norte incógnita norte -METROincógnita norte +1 - ... - Mincógnita norte + metro (3)

bajo condiciones

……………………………………… (4)

donde M es un número positivo suficientemente grande, cuyo valor específico generalmente no se especifica, se denomina problema extendido (tarea M) en relación con el problema (1) - (2).

La tarea extendida tiene un plan de referencia.

X=(0; 0; ...; 0; b1; b 2 ; ...;bm).

determinado por el sistema de vectores unitarios P n +1 ; R n+2 , … R p+t , formando la base del espacio vectorial m-ro, que se llama artificial. Los propios vectores, así como las variables. incógnita norte + yo ( i=l, metro), son llamados artificial. Dado que el problema extendido tiene un plan de referencia, su solución se puede encontrar mediante el método simplex.

Teorema si en plan optimo X*=( incógnita* 1 , incógnita* 2 , ...; incógnita*norte , x* norte +1 ; ...; incógnita*n+m) tarea extendida (3) - (4) valores de variables artificiales incógnita* norte + yo = 0 ( i=1, metro), Eso X*=( incógnita* 1 , incógnita* 2 , ...; incógnita*norte) es el plan óptimo para el problema (1) - (2).

Por lo tanto, si en el plan óptimo encontrado para el problema extendido los valores de las variables artificiales son iguales a cero, entonces se obtiene el plan óptimo para el problema original.

Los valores de la línea de índice ∆ 0 , ∆ 1 , …, ∆ n constan de dos partes, una de las cuales depende de m, pero el otro no. Complete una tabla simplex que contenga una fila más que una tabla simplex normal. En este caso, la (m+2)ésima línea contiene los coeficientes para m, y en el (m+1)ésimo – términos que no contienen METRO. Al pasar de un plan de referencia a otro, se introduce en la base un vector correspondiente al número negativo más grande en el valor absoluto de la (m+2)ésima fila. Un vector artificial excluido de la base no se registra en la siguiente tabla simplex. El recálculo de tablas simplex al pasar de un plan de referencia a otro se realiza de acuerdo con las reglas generales del método simplex.

El proceso iterativo a lo largo de la línea (m+2) continúa hasta:

o no se excluirán de la base todos los vectores artificiales;

o no se excluyen todos los vectores artificiales, pero la (m+2)ésima fila no contiene más elementos negativos en los índices ∆ 1, ..., ∆ n.

En el primer caso, la base corresponde a algún plan de referencia del problema original y la determinación de su plan óptimo continúa a lo largo de la línea (m+1).

En el segundo caso, si el valor de ∆ 0 es negativo, el problema original no tiene solución; si ∆ 0 =0, entonces el plan de referencia encontrado del problema original es degenerado y la base contiene al menos uno de los vectores de base artificiales.

Etapas para encontrar una solución al problema (1) - (2)

método de base artificial:

Redacte un problema extendido (3) - (4).

Encuentre el plan de referencia del problema extendido.

Utilizando los cálculos habituales del método simplex, las variables artificiales se excluyen de la base. Como resultado, se encuentra el plan de referencia del problema original (1) - (2) o se establece su insolubilidad.

Utilizando el plan de referencia encontrado del problema (1) - (2), encuentran el plan óptimo del problema original utilizando el método simplex o establecen su irresolvebilidad.

Ejemplo.

Encuentra el mínimo de una función. F= - 2incógnita 1 + 3incógnita 2 - 6incógnita 3 - incógnita 4

norte con restricciones:

2x 1 +x 2 -2x 3 +x 4 =24

x1 +2x2 +4x3 ≤22

x 1 -x 2 +2x 3 ≥10

incógnita i ≥0, i=1,4

Solución.

Escribamos este problema en forma de problema principal: encuentre el máximo de la función F= 2incógnita 1 - 3incógnita 2 + 6incógnita 3 + incógnita 4

con restricciones:

2x 1 +x 2 -2x 3 +x 4 =24

x1 +2x2 +4x3 +x5 =22

x1 -x2 +2x3 - x6= 10

incógnita i ≥0, i=1, 6

En el sistema de ecuaciones del último problema, considere los vectores de los coeficientes de las incógnitas:

Entre los vectores P 1, R 2 , ... P 6 sólo dos individuales (P 4 y P 5). Por lo tanto, agregamos una variable adicional no negativa x al lado izquierdo de la tercera ecuación del sistema de restricciones del problema. 7 y considere el problema extendido de maximizar la función

F= 2incógnita 1 - 3incógnita 2 + 6incógnita 3 + incógnita 4 -mx7

con restricciones:

2x 1 +x 2 -2x 3 +x 4 =24

x1 +2x2 +4x3 +x5 =22

x 1 -x 2 +2x 3 - x 6 +x 7= 10

El problema extendido tiene un plan de referencia X = (0; 0; 0; 24; 22; 0; 10), definido por un sistema de tres vectores unitarios: P 4 , P 5 , P 7 .

El concepto de problema de programación lineal dual (adjunto).

Reglas para construir un problema dual.

Con cada problema de programación lineal (LPP), que se denomina problema dual (o adjunto) con respecto a problema original, que se llama línea recta.

El problema dual se construye en relación con el problema directo escrito en forma estándar:

F=c 1 x 1 +c 2 x 2 +…+c n x n  máx (3.6)

a 11 x 1 +a 12 x 2 +…+a 1n x n ≤ b 1,

a 21 x 1 +a 22 x 2 +…+a 2n x n ≤ b 2,

………………………………

a k1 x 1 +a k2 x 2 +…+a kn x n ≤ =b k , (3.7)

a k+1.1 x 1 +a k+1.2 x 2 +…+a k+1,n x n =b k+1 ,

………………………………

a m1 x 1 +a m2 x 2 +…+a mn x n =b m ,

x j ≥ 0, , yo≤ norte (3,8)

El problema de encontrar el valor mínimo de una función.

L = b 1 y 1 + b 2 y 2 + … + b m y m (3.9)

bajo condiciones

a 11 y 1 + a 12 y 2 +…+ a m1 y m ≥ c 1

a 21 y 1 + a 22 y 2 +…+ a m2 y m ≥ c 2

………………………………

un 1 yo y 1 + a 2 yo y 2 +…+ a m yo y metro ≥ c yo (3.10)

a yo+1.1 y 1 + a yo+1.2 y 2 +…+ a yo+1,m y m = c l+1

………………………………

a m1 y 1 + a m2 y 2 +…+ a mn y m = c m

y yo ≥ 0, , k ≤ m (3.11)

se llama dual al problema (3.6) – (3.8).

Las reglas para construir un problema dual se dan en la tabla:

Características estructurales de ZLP.	problema de programación lineal
Características estructurales de ZLP.		Dual
1. Función objetivo	Maximización (máx.)	Minimización (min)
2. Número de variables	norte variables	Igual al número de restricciones del problema directo (3.7), y i , es decir metro
3. Número de restricciones	restricciones m	Igual al número de variables del problema directo x j , es decir n
4. Matriz de coeficientes en el sistema de restricciones.
5. Coeficientes de variables en la función objetivo.	c 1 ,c 2, …,c norte	segundo 1, segundo 2, …, segundo metro
6. Lado derecho del sistema de restricciones.	segundo 1, segundo 2, …, segundo metro	c 1 ,c 2, …,c norte
7. Señales en el sistema de restricciones.	a) x j ≥ 0 - condición de no negatividad	La j-ésima restricción tiene el signo “≥”
	b) la condición de no negatividad no se impone a la variable x j	La j-ésima restricción tiene el signo “="
	c) la i-ésima restricción tiene el signo “≤”	variable y yo ≥0
	d) la i-ésima restricción tiene el signo “="	la condición de no negatividad no se impone a la variable y i

Nota

El problema del máximo directo y el problema del mínimo dual son problemas mutuamente duales. Por lo tanto, podemos considerar el problema (3.9) – (3.11) un ZLP directo, y el problema (3.6) – (3.8) su problema dual. En este caso se conservan las reglas para la construcción del PLP dual, sólo con el cambio de que el problema mínimo se considera el inicial.

Si el problema original se resuelve en max (min), y en el sistema de restricciones) i-e ( j-f) la restricción tiene el signo “≤” (“≥”), entonces para construir el problema dual es necesario:

a) o multiplicar ambas partes i th ( j-ésima) desigualdad por (-1) y cambiar el signo a “≤” (“≥”)

b) o traer i-e ( j-e) restricción a la igualdad mediante la introducción de una variable adicional x norte+ i ≥0

El método de la base artificial (o el método “M”) se puede utilizar para resolver el problema PL si su sistema de restricciones, además de desigualdades de significado “≤”, tiene desigualdades de significado “≥” o igualdades estrictas. Consideremos el problema de PL planteado en su forma más general.

Encuentra el extremo de la función.

Algoritmo del método "M".

1. Del sistema de desigualdades pasamos al sistema de ecuaciones, introduciendo variables adicionales no negativas:

2. En las restricciones en las que se incluyeron variables adicionales no negativas con un signo menos o no se incluyeron en absoluto, se introducen las denominadas variables artificiales:

3. La suma de variables artificiales se introduce en forma lineal (1.26) con coeficiente M>0. Para garantizar que las variables artificiales no estén contenidas en el plan óptimo del problema original, se asigna arbitrariamente el coeficiente M gran valor comparado con probabilidades forma lineal(1.26). En este caso, al maximizar la función objetivo (1.26), tomamos (-M), al minimizar (+M).

4. Construimos un problema M – LP extendido:

encontrar el extremo de una forma lineal

en siguientes restricciones:

Encontremos el plan de referencia inicial de la tarea M.

Dado que variables adicionales no negativas y variables artificiales se incluyen en las restricciones con coeficientes unitarios positivos, que constituyen un sistema de vectores linealmente independientes como columnas matriz de identidad, entonces las variables mencionadas serán básicas y todas las demás serán libres, es decir

Entonces el plan de referencia inicial se verá así:

6. Para encontrar el plan óptimo para la tarea M extendida, crean una tabla simplex, que es una fila más grande que la habitual. Esta línea de índice (m+2) contiene los coeficientes correspondientes a M que se incluyen en la función objetivo con el signo opuesto.

Se verifica el criterio de optimización para la (m+2)ésima fila y se determina la variable a incluir en la base. El procedimiento simplex para la línea de índice (m+2) se lleva a cabo hasta que se cumpla el criterio de optimización para esta línea. Luego, el proceso de encontrar el plan óptimo continúa a lo largo de la fila del índice (m+1).

7. Analizar el plan óptimo M - tarea. Si a este respecto todas las variables artificiales son iguales a cero, es decir entonces el plan X(x 1, x 2,…, x n) es el plan óptimo del problema original. Si en el plan óptimo del problema M al menos una variable artificial no es igual a cero, es decir entonces el problema original no tiene solución.

Si en el proceso de resolución de un problema M establecemos su irresoluble, entonces el problema original también es irresoluble.

Solución de caso de prueba.

Encuentra el mínimo de una función.

sujeto a las siguientes restricciones:

1. Del sistema de desigualdades pasamos a un sistema de ecuaciones, introduciendo variables adicionales no negativas x 4 y x 5 en la primera y segunda restricciones. Reescribimos la tercera ecuación sin cambios:

2. En las ecuaciones 2 y 3 introducimos variables artificiales y 1 e y 2:

3. En la forma lineal L(X) introducimos la suma y 1 +y 2 con el factor M. Como el problema es mínimo, tomamos el factor M con el signo “+”.

4. Construya M - problema. Encuentra el mínimo de una forma lineal.

sujeto a las siguientes restricciones:

5. Resolvemos este problema mediante el método simplex. Dado que x 4 , y 1 , y 2 son variables básicas, las expresamos en términos de variables libres y las sustituimos en la función L(X):

6. Construimos una tabla simplex que tiene dos filas de índice: en la primera, como de costumbre, se escriben los coeficientes Cj tomados con el signo opuesto, y en la segunda, los coeficientes correspondientes al factor M (también con el signo opuesto, excepto el plazo gratuito).

Comprobamos el signo de optimización utilizando la línea índice (m+2). Dado que la tarea es mínima, el criterio no se cumple, ya que la columna x 2 contiene elemento positivo 4. Marque esta columna clave con una flecha. Y, como de costumbre, seleccione la línea clave. Al seleccionar una cadena clave, obtuvimos dos idénticas. valores más bajosθ. Para evitar bucles, aplicamos la regla de Kreko. Dividimos las filas x 1 e y 1 en los elementos correspondientes de la columna clave 2 y 4. Los resultados de la división se leen de izquierda a derecha, y la fila donde se encuentra primero el número más pequeño se selecciona como clave. es decir.

marca la linea y 1 flecha y encontramos el elemento general 4. Luego realizamos el procedimiento simplex habitual y obtenemos la segunda tabla (Tabla 1.2.), en la que analizamos nuevamente la (m+2)ésima fila del índice y seleccionamos la columna x 3 como la clave.

Como resultado de construir la tercera tabla (Tabla 1.2.), obtenemos el plan óptimo para el problema extendido. ya que el criterio de optimización se cumple para ambas líneas del índice.

Debido a que todas las variables artificiales se derivan de la base, el plan óptimo para el problema original es el plan Y

Para el problema considerado, es posible construir una segunda solución óptima. con el mismo valor L min =24 (tabla 1.2.). Por tanto, el problema tiene muchos planes óptimos. Dónde

Tabla 1.2.

No. de mesas	Variables básicas	Miembros gratuitos	X1	x2	X3	x4	X5	å	q
	x4				-4
Y 1		-1		-2		-1
Y2								-
L(X)		-1	-2	-2			-5	mín.
		4			-1		-
	x4		7/2		-3		1/2		-
x2		-1/4		-1/4		-1/4		-
Y2
L(X)		-3/2		-3		-1/2		mín.
			2
	X3		1/2					15/2
x2						-1/4	27/4	-
x4						1/2	49/2	18/5
L(X)						-1/2	47/2	mín.

	X3	21/5			-1/10		-1/20	101/20
x2						-1/4	27/4
x4	18/5			1/5		-1/10	49/10
L(X)						-1/2	47/2	mín.

Una condición necesaria para utilizar el método simplex es la presencia de un plan de referencia, es decir, un nivel aceptable. solución básica sistema canónico de ecuaciones. Para ello se deben cumplir las siguientes condiciones:

el sistema debe tener una estructura canónica (escalonada);
sólo hay restricciones de igualdad;
los lados derechos de las restricciones son positivos;
las variables del problema son positivas.

Sin estas condiciones, es imposible obtener un plan de referencia. Sin embargo, en problemas reales Las condiciones anteriores no siempre se cumplen.

Existe un método especial llamado base artificial, que permite obtener un plan de referencia inicial en cualquier problema de programación lineal.

Reduzcamos el problema de programación lineal a su forma estándar:

Que todo /? > 0, pero algunas o todas las variables base son negativas, INCÓGNITA; 0. Por tanto, no existe un plan de referencia.

Complementemos las ecuaciones de restricción con variables artificiales (asumimos que todas xj j - 1, norte).

vamos a presentar t variables (por número de ecuaciones): x lM los que estan en nuevo sistema será básico y negativo. INCÓGNITA-

Como resultado, obtenemos el siguiente problema equivalente.

Aqui estan las variables xn+i No tiene nada que ver con el problema de programación lineal original. Sirven únicamente para obtener un plan de referencia y se denominan variables artificiales. y el nuevo

la función objetivo /(.t) se forma para completar el problema.

En un diseño de referencia óptimo, las variables artificiales deberían ser cero. De lo contrario, se violarán las condiciones del problema original.

En el plan de referencia inicial las variables artificiales son básicas, es decir, no son iguales a cero, y en el plan óptimo las variables artificiales deben ser iguales a cero. Esto significa que las variables artificiales deberían quedar libres de manera óptima. Esta traducción es la idea principal del método: la traducción de variables artificiales de variables básicas a variables libres. Veamos el mecanismo de dicha traducción usando un ejemplo.

Reescribamos el ZLP en forma estándar. Para ello, introducimos variables adicionales. x ), x A, x 5 , x 6 y escribe el problema en forma canónica.

Variables libres x, incógnita 2 = 0, en cuyo caso las variables básicas tomarán los valores x 3 = -5, x 4 = -5, x 5 = 7, x 6 = 9. Dado que algunas de las variables básicas son negativas, no existe un plan de referencia. Para obtener el plan de referencia inicial, introducimos las variables x 7, x 8 en las dos primeras ecuaciones de restricción y formulamos un problema auxiliar:

De este modo, base inicial es

Mesa simplex con base artificial.





	incógnita4

Anotemos las secuencias. planos de referencia.

Para los primeros tres pasos incrementales un a se calculan sólo a partir de variables artificiales que se incluyen en la función objetivo artificial /(x) =x 7 + x 8 con coeficiente c, = 1.

En el tercer paso, se excluyen las variables artificiales, ya que todas un a son positivos.

Entonces, el método simplex con la introducción de variables artificiales incluye dos etapas.

Formación y solución de un problema auxiliar de LP con introducción de variables artificiales. Las variables artificiales en el diseño de referencia inicial son básicas. Una función objetivo artificial incluye sólo variables artificiales. Al recibir planes de referencia adyacentes, transferimos variables artificiales de las básicas a las gratuitas. Como resultado, se obtuvo el plan de referencia óptimo para el problema auxiliar /(x) = 0.

El plan de referencia óptimo para el problema de PL auxiliar es el plan de referencia inicial para el problema de PL principal. El problema se resuelve para la función objetivo original /(x) utilizando el método simplex habitual.

Notas

1. La introducción de variables artificiales se requiere en dos casos:
- varias variables básicas x son negativas en forma canónica;
- si es difícil reducirlo a una forma canónica, simplemente agregue una variable artificial a cualquier ecuación de restricción.
2. Ocurriendo en la práctica control automático Los problemas de programación lineal contienen de 500 a 1500 restricciones y más de 1000 variables. Está claro que problemas de esta dimensión sólo pueden resolverse con la ayuda de una computadora y un equipo especial. software. La complejidad del algoritmo radica en el hecho de que:
- APP requiere forma canónica;
- PPP para problemas de este tamaño requiere el uso de computadoras grandes (y computación paralela), ya que el método simplex almacena la tabla completa.
3. La eficiencia computacional del método simplex puede evaluarse mediante los siguientes indicadores:
- número de pasos (planes de soporte adyacentes);
- Costos de tiempo de máquina.