Método simplex con ejemplos de bases artificiales. Ejemplos de resolución de ZLP mediante el método de base artificial. Significados de la palabra simplex. ¿Qué es simple?
| x1 | - | 2 | x2 | + | S 1 | = | 2 | ||||||||||
| 2 | x1 | +3 | x2 | - | S 2 | = | 4 | ||||||||||
| - | 2 | x1 | + | x2 | + | S 3 | = | 2 |
| x1 | - | 2 | x2 | + | S 1 | = | 2 | |||||||||||||
| 2 | x1 | +3 | x2 | - | S 2 | + | Por tanto, se ha determinado el elemento que será la base. A continuación contamos. | = | 4 | |||||||||||
| - | 2 | x1 | + | x2 | + | S 3 | = | 2 |
| R 1 x 1 = 0 x 2 = 0 S 2 = 0 |
S 1 = 2 S 3 = 2 R 1 = 4 |
| x1 | x2 | S 1 | S 2 | S 3 | Por tanto, se ha determinado el elemento que será la base. A continuación contamos. | Paso #1 | Θ |
| 1 | -2 | 1 | 0 | 0 | 0 | 2 | |
| 2 | 3 | 0 | -1 | 0 | 1 | 4 | 4: 3 ≈ 1,33 |
| -2 | 1 | 0 | 0 | 1 | 0 | 2 | 2: 1 = 2 |
| -2 | -3 | 0 | 1 | 0 | 0 | Calle. miembro | |
| 1 | -2 | 1 | 0 | 0 | 0 | 2 | |
| 2/3 | 1 | 0 | -1/3 | 0 | 1/3 | 4/3 | |
| -2 | 1 | 0 | 0 | 1 | 0 | 2 | |
| -2 | -3 | 0 | 1 | 0 | 0 | Calle. miembro | |
| 7/3 | 0 | 1 | -2/3 | 0 | 2/3 | 14/3 | |
| 2/3 | 1 | 0 | -1/3 | 0 | 1/3 | 4/3 | |
| -8/3 | 0 | 0 | 1/3 | 1 | -1/3 | 2/3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 4 |
| 7/3 | x1 | + | S 1 | - | 2/3 | S 2 | = | 14/3 | |||||||||
| 2/3 | x1 | + | x2 | - | 1/3 | S 2 | = | 4/3 | |||||||||
| - | 8/3 | x1 | + | 1/3 | S 2 | + | S 3 | = | 2/3 |
| x1 | x2 | S 1 | S 2 | S 3 | Paso #1 | Θ |
| 7/3 | 0 | 1 | -2/3 | 0 | 14/3 | 14/3: 7/3 = 2 |
| 2/3 | 1 | 0 | -1/3 | 0 | 4/3 | 4/3: 2/3 = 2 |
| -8/3 | 0 | 0 | 1/3 | 1 | 2/3 | |
| -7/3 | 0 | 0 | 5/3 | 0 | 4. Encontrar el valor más pequeño de la función F. | |
| 1 | 0 | 3/7 | -2/7 | 0 | 2 | |
| 2/3 | 1 | 0 | -1/3 | 0 | 4/3 | |
| -8/3 | 0 | 0 | 1/3 | 1 | 2/3 | |
| -7/3 | 0 | 0 | 5/3 | 0 | 4. Encontrar el valor más pequeño de la función F. | |
| 1 | 0 | 3/7 | -2/7 | 0 | 2 | |
| 0 | 1 | -2/7 | -1/7 | 0 | 0 | |
| 0 | 0 | 8/7 | -3/7 | 1 | 6 | |
| 0 | 0 | 1 | 1 | 0 | F - 20/3 |
| F - 2 S 1 = 0 S 2 = 0 |
x 1 = 2 x 2 = 0 S 3 = 6 |
No hay coeficientes negativos entre los coeficientes de la fila seleccionada. En consecuencia, se ha encontrado el valor más pequeño de la función F. Método 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.
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
busquemos el original plan de referencia M – tareas.
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 plan optimo M – tareas. 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 
Eso 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 que estamos considerando, podemos 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. |
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Advertencia
¿Borrar todas las celdas?
Cerrar Borrar
Instrucciones de entrada de datos. Los números se ingresan como números enteros (ejemplos: 487, 5, -7623, etc.), decimales (ej. 67, 102,54, etc.) o fracciones. La fracción debe ingresarse en la forma a/b, donde a y b (b>0) son números enteros o numeros decimales. Ejemplos 45/5, 6,6/76,4, -7/6,7, etc.
método simplex
Ejemplos de resolución de ZLP mediante el método simplex
Ejemplo 1: Resuelva el siguiente problema programación lineal:
 |
Lado derecho restricciones del sistema de ecuaciones tiene la forma:
Anotemos el plan de referencia actual:
 |
Este plan de referencia no es óptimo porque hay elementos negativos en la última fila. El elemento negativo más grande en el módulo es (-3), por lo tanto, el vector está incluido en la base. incógnita 
en 
. mín.(40:6, 28:2)=20/3 corresponde a la línea 1. El vector surge de la base incógnita 3. Hagamos una eliminación gaussiana para la columna. incógnita 2, dado que el elemento principal corresponde a la fila 1. Restablezcamos todos los elementos de esta columna excepto el elemento principal. Para hacer esto, suma las líneas 2, 3, 4 con la línea 1, multiplicada por -1/3, 1/6, 1/2, respectivamente. A continuación, dividimos la línea con el elemento principal por el elemento principal.
Este plan de referencia no es óptimo, ya que la última fila tiene un elemento negativo (-3), por lo tanto la base incluye el vector incógnita 1. Determinamos qué vector sale de la base. Para ello calculamos 
en 
. min(44/3:11/3, 62/3:5/3)=4 corresponde a la línea 2. El vector surge de la base incógnita 4. Hagamos una eliminación gaussiana para la columna. incógnita 1, dado que el elemento principal corresponde a la fila 2. Restablezcamos todos los elementos de esta columna excepto el elemento principal. Para hacer esto, sume las líneas 1, 3, 4 con la línea 2 multiplicada por 1/11, -5/11, 9/11, respectivamente. A continuación, dividimos la línea con el elemento principal por el elemento principal.
La tabla simplex aceptará siguiente vista:
El plan de referencia actual es óptimo, ya que en las líneas 4 bajo las variables 
no hay elementos negativos.
La solución se puede escribir así: 
.
Significado función objetivo en este punto: F(incógnita)=
.
Ejemplo 2. Encuentra el máximo de una función.
Solución.
Vectores básicos incógnita 4 , incógnita 3 por lo tanto todos los elementos en columnas incógnita 4 , incógnita 3, abajo línea horizontal debe ser cero.
Restablecer todos los elementos de la columna a cero incógnita 4, excepto el elemento principal. Para hacer esto, sume la fila 3 con la fila 1 multiplicada por 4. Restablezca todos los elementos de la columna a cero incógnita 3, excepto el elemento principal. Para hacer esto, suma la línea 3 con la línea 2 multiplicada por 1.
La tabla simplex tomará la forma:
Este plan de referencia no es óptimo, ya que la última fila tiene un elemento negativo (-11), por lo tanto la base incluye el vector incógnita 2. Determinamos qué vector sale de la base. Para ello calculamos 
en 
. Por tanto, la función objetivo es ilimitada desde arriba. Aquellos. El problema de programación lineal no tiene solución.
Ejemplos de resolución de ZLP utilizando el método de base artificial.
Ejemplo 1. Encuentra el máximo de una función.
Solución Como el número de vectores base debe ser 3, le sumamos una variable artificial, y a la función objetivo le sumamos esta variable multiplicada por −M, donde M es un número muy grande:
 |
La matriz de coeficientes del sistema de ecuaciones tiene la forma:
Los vectores base, por lo tanto, todos los elementos en las columnas debajo de la línea horizontal deben ser cero.
Restablezcamos todos los elementos de la columna excepto el elemento principal. Para hacer esto, sume la línea 5 con la línea 3 multiplicada por -1.
La tabla simplex tomará la forma:
Este plan de referencia no es óptimo porque hay elementos negativos en la última fila. El elemento negativo absoluto más grande es (-5), por lo tanto el vector se incluye en la base. Determinamos qué vector sale de la base. Para ello calculamos 
en 
corresponde a la fila 3. Un vector emerge de la base. Hagamos una excepción gaussiana para la columna, dado que el elemento principal corresponde a la fila 3. Restablezcamos todos los elementos de esta columna, excepto el elemento principal. Para hacer esto, sume las líneas línea 5 con la línea 3 multiplicada por 1. Luego, divida la línea con el elemento principal por el elemento principal.
La tabla simplex tomará la siguiente forma:
Este plan de referencia no es óptimo porque hay elementos negativos en la última fila. El elemento negativo absoluto más grande es (-3), por lo tanto el vector se incluye en la base. Determinamos qué vector sale de la base. Para ello calculamos 
en 
corresponde a la fila 1. El vector surge de la base incógnita 2. Hagamos una eliminación gaussiana para la columna. incógnita 1, dado que el elemento principal corresponde a la fila 1. Restablezcamos todos los elementos de esta columna excepto el elemento principal. Para hacer esto, suma las líneas 2, 3, 4 con la línea 1, multiplicada por 3/2, -1/10, 3/2, respectivamente. A continuación, dividimos la línea con el elemento principal por el elemento principal.
La tabla simplex tomará la siguiente forma:
Este plan de referencia no es óptimo porque hay elementos negativos en la última fila. El elemento negativo más grande en módulo (-13/2), por lo tanto la base incluye el vector incógnita 3. Determinamos qué vector sale de la base. Para ello calculamos 
en 
corresponde a la línea 3. El vector surge de la base incógnita 5. Hagamos una eliminación gaussiana para la columna. incógnita 3, dado que el elemento principal corresponde a la fila 3. Restablezcamos todos los elementos de esta columna excepto el elemento principal. Para hacer esto, suma las líneas de la línea 1, 2, 4 con la línea 3, multiplicadas por 5/3, 25/9, 65/9, respectivamente. A continuación, dividimos la línea con el elemento principal por el elemento principal.
La tabla simplex tomará la siguiente forma:
El plan de referencia actual es óptimo, ya que no hay elementos negativos bajo las variables de las líneas 4-5.
La solución al problema original se puede escribir de la siguiente manera:
Ejemplo 2. Encuentre el plan óptimo para un problema de programación lineal:
La matriz de coeficientes del sistema de ecuaciones tiene la forma:
Vectores básicos incógnita 4 , incógnita 5 , incógnita 6 por lo tanto todos los elementos en columnas incógnita 4 , incógnita 5 , incógnita 6, debajo de la línea horizontal debe ser cero.
Restablecer todos los elementos de la columna a cero incógnita 4, excepto el elemento principal. Para hacer esto, sume la línea 4 con la línea 1 multiplicada por -1. Restablecer todos los elementos de la columna a cero incógnita 5, excepto el elemento principal. Para hacer esto, sume la línea 5 con la línea 2 multiplicada por -1. Restablecer todos los elementos de la columna a cero incógnita 6, excepto el elemento principal. Para hacer esto, sume la línea 5 con la línea 3 multiplicada por -1.
La tabla simplex tomará la forma:
En la línea 5 los elementos correspondientes a las variables incógnita 1 , incógnita 2 , incógnita 3 , incógnita 4 , incógnita 5 , incógnita 6 no son negativos y el número ubicado en la intersección de una fila y columna determinadas incógnita 0 es negativo. Entonces el problema original no tiene plan de referencia. Por tanto es indecidible.
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 de manera óptima 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 METRO, 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 METRO, 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 mayor en valor absoluto número negativo(m+2)ésimas líneas. 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 reglas generales 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, en lado izquierdo de la tercera ecuación del sistema de restricciones del problema, agregamos una variable adicional no negativa x 7 y considere el problema extendido de maximizar la función
F= 2incógnita 1 - 3incógnita 2 + 6incógnita 3 + incógnita 4 - Мх7
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 de construcción problema dual.
Con cada problema de programación lineal (LPP), que se denomina problema dual (o adjunto) respecto del problema original, que se denomina directo.
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 |
|
|
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 |
m restricciones |
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 construir un PLP dual, solo con por ese cambio, 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-mi ( j-e) restricción a la igualdad mediante la introducción de una variable adicional x norte+ i ≥0
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 más a la derecha es la columna de términos ficticios y la fila más inferior es la fila de la función objetivo y se denomina vector de puntuaciones 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 de 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 lugar de ello, asignamos una nueva línea de estimaciones, pero utilizando la función objetivo original. z(incógnita). Así, hemos obtenido 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 podían entrar 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 de programación lineal original en uno 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) se verá así: , 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).
