Hispanopedia Wiki
Articulo de referencia

Solución básica factible

En la teoría de la programación lineal , una solución factible básica ( SFB ) es una solución con un conjunto mínimo de variables no nulas. Geométricamente, cada SFB corresponde...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la programación lineal , una solución factible básica ( SFB ) es una solución con un conjunto mínimo de variables no nulas. Geométricamente, cada SFB corresponde a un vértice del poliedro de soluciones factibles. Si existe una solución óptima, entonces existe una SFB óptima. Por lo tanto, para encontrar una solución óptima, basta con considerar las SFB. Este hecho es utilizado por el algoritmo simplex , que esencialmente va de una SFB a otra hasta encontrar una solución óptima. [ 1 ]

Definiciones

Preliminares: forma ecuacional con filas linealmente independientes

Para las definiciones que siguen, primero presentamos el programa lineal en la llamada forma ecuacional :

maximizardoTincógnita{\textstyle \mathbf {c^{T}} \mathbf {x} }
sujeto aAincógnita=b{\displaystyle A\mathbf {x} =\mathbf {b} }yincógnita≥0{\displaystyle \mathbf {x} \geq 0}

dónde:

  • doT{\displaystyle \mathbf {c^{T}} }yincógnita{\displaystyle \mathbf {x} }son vectores de tamaño n (el número de variables);
  • b{\displaystyle \mathbf {b} }es un vector de tamaño m (el número de restricciones);
  • A{\displaystyle A}es una matriz de m por n ;
  • incógnita≥0{\displaystyle \mathbf {x} \geq 0}significa que todas las variables son no negativas.

Cualquier programa lineal puede convertirse en una forma ecuacional añadiendo variables de holgura .

Como paso preliminar de limpieza, verificamos que:

  • El sistemaAincógnita=b{\displaystyle A\mathbf {x} =\mathbf {b} }tiene al menos una solución (de lo contrario, todo el problema de programación lineal no tiene solución y no hay nada más que hacer);
  • Todas las m filas de la matrizA{\displaystyle A}son linealmente independientes , es decir, su rango es m (de lo contrario, podemos simplemente eliminar filas redundantes sin cambiar el LP).

Solución viable

Una solución factible del LP es cualquier vectorincógnita≥0{\displaystyle \mathbf {x} \geq 0}de tal manera queAincógnita=b{\displaystyle A\mathbf {x} =\mathbf {b} }Suponemos que existe al menos una solución factible. Si m = n , entonces solo hay una solución factible. Normalmente m < n , por lo que el sistemaAincógnita=b{\displaystyle A\mathbf {x} =\mathbf {b} }tiene muchas soluciones; cada una de esas soluciones se denomina solución factible del LP.

Base

Una base del LP es una submatriz no singular de A, con todas las filas de m y solo m < n columnas.

A veces, el término base se usa no para la submatriz en sí, sino para el conjunto de índices de sus columnas. Sea B un subconjunto de m índices de {1,..., n }. Denotemos porAB{\displaystyle A_{B}}la matriz cuadrada m x m formada por las m columnas deA{\displaystyle A}indexado por B. SiAB{\displaystyle A_{B}}es no singular , las columnas indexadas por B son una base del espacio columna deA{\displaystyle A}En este caso, llamamos B una base del LP.

Desde el rango deA{\displaystyle A}es m , tiene al menos una base; ya queA{\displaystyle A}tiene n columnas, tiene como máximo(nortemetro){\displaystyle {\binom {n}{m}}}bases.

Solución básica factible

Dada una base B , decimos que una solución factibleincógnita{\displaystyle \mathbf {x} }es una solución factible básica con base B si todas sus variables no nulas están indexadas por B , es decir, para todoj∉B:  incógnitaj=0{\displaystyle j\not \in B:~~x_{j}=0}.

Propiedades

1. Un BFS está determinado únicamente por las restricciones del LP (la matrizA{\displaystyle A}y el vectorb{\displaystyle \mathbf {b} }); no depende del objetivo de optimización.

2. Por definición, una BFS tiene como máximo m variables distintas de cero y como mínimo n - m variables nulas. Una BFS puede tener menos de m variables distintas de cero; en ese caso, puede tener muchas bases diferentes, todas las cuales contienen los índices de sus variables distintas de cero.

3. Una solución factibleincógnita{\displaystyle \mathbf {x} }es básico si y solo si las columnas de la matrizAK{\displaystyle A_{K}}son linealmente independientes, donde K es el conjunto de índices de los elementos no nulos deincógnita{\displaystyle \mathbf {x} }. [ 1 ] : 45

4. Cada base determina una BFS única: para cada base B de m índices, hay como máximo una BFS. incógnitaB{\displaystyle \mathbf {x_ {B}}}con base B. Esto se debe a queincógnitaB{\displaystyle \mathbf {x_ {B}}}debe satisfacer la restricciónABincógnitaB=b{\displaystyle A_{B}\mathbf {x_{B}} =b}y por definición de base la matrizAB{\displaystyle A_{B}}es no singular, por lo que la restricción tiene una solución única:

incógnitaB=AB−1⋅b{\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}

Lo contrario no es cierto: cada BFS puede provenir de muchas bases diferentes. Si la solución única deincógnitaB=AB−1⋅b{\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}satisface las restricciones de no negatividadincógnitaB≥0{\displaystyle \mathbf {x_{B}} \geq 0}, entonces B se denomina una base factible .

5. Si un programa lineal tiene una solución óptima (es decir, tiene una solución factible y el conjunto de soluciones factibles es acotado), entonces tiene una BFS óptima. Esto es consecuencia del principio del máximo de Bauer : la función objetivo de un programa lineal es convexa; el conjunto de soluciones factibles es convexo (es una intersección de hiperespacios); por lo tanto, la función objetivo alcanza su máximo en un punto extremo del conjunto de soluciones factibles.

Dado que el número de BFS es finito y está acotado por(nortemetro){\displaystyle {\binom {n}{m}}}, se puede encontrar una solución óptima para cualquier LP en tiempo finito simplemente evaluando la función objetivo en todos los(nortemetro){\displaystyle {\binom {n}{m}}}BFS-s. Esta no es la forma más eficiente de resolver un LP; el algoritmo simplex examina los BFS-s de una manera mucho más eficiente.

Ejemplos

Consideremos un programa lineal con las siguientes restricciones:

incógnita1+5incógnita2+3incógnita3+4incógnita4+6incógnita5=14incógnita2+3incógnita3+5incógnita4+6incógnita5=7∀i∈{1,…,5}:incógnitai≥0{\displaystyle {\begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}&=7\\\forall i\in \{1,\ldots ,5\}:x_{i}&\geq 0\end{aligned}}}

La matriz A es:

A=(1534601356)     b=(14  7){\displaystyle A={\begin{pmatrix}1&5&3&4&6\\0&1&3&5&6\end{pmatrix}}~~~~~\mathbf {b} =(14~~7)}

Aquí, m = 2 y hay 10 subconjuntos de 2 índices, sin embargo, no todos ellos son bases: el conjunto {3,5} no es una base ya que las columnas 3 y 5 son linealmente dependientes.

El conjunto B ={2,4} es una base, ya que la matriz AB=(5415){\displaystyle A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}}no es singular.

La única BFS correspondiente a esta base esincógnitaB=(0  2  0  1  0){\displaystyle x_{B}=(0~~2~~0~~1~~0)}.

Interpretación geométrica

El conjunto de todas las soluciones factibles es una intersección de hiperespacios . Por lo tanto, es un poliedro convexo . Si es acotado, entonces es un politopo convexo . Cada BFS corresponde a un vértice de este politopo. [ 1 ] : 53–56

Soluciones básicas factibles para el problema dual

Como se mencionó anteriormente, cada base B define una solución factible básica única.incógnitaB=AB−1⋅b{\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}. De manera similar, cada base define una solución al programa lineal dual :

minimizarbTy{\textstyle \mathbf {b^{T}} \mathbf {y} }
sujeto aATy≥do{\displaystyle A^{T}\mathbf {y} \geq \mathbf {c} }.

La solución esyB=ABT−1⋅do{\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}.

Encontrar una BFS óptima

Existen varios métodos para encontrar una BFS que también sea óptima.

Utilizando el algoritmo simplex

En la práctica, la forma más sencilla de encontrar una BFS óptima es utilizar el algoritmo simplex . Este algoritmo mantiene, en cada punto de su ejecución, una "base actual" B (un subconjunto de m de n variables), una "BFS actual" y un "tableo actual". El tablero es una representación del programa lineal donde las variables básicas se expresan en términos de las no básicas: [ 1 ] : 65incógnitaB=pag+Qincógnitanortez=z0+rTincógnitanorte{\displaystyle {\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}}dóndeincógnitaB{\displaystyle x_{B}}es el vector de m variables básicas,incógnitanorte{\displaystyle x_{N}}es el vector de n variables no básicas, yz{\displaystyle z}es el objetivo de maximización. Dado que las variables no básicas son iguales a 0, la BFS actual espag{\displaystyle p}y el objetivo de maximización actual esz0{\displaystyle z_{0}}.

Si todos los coeficientes enr{\displaystyle r}son negativos, entoncesz0{\displaystyle z_{0}}es una solución óptima, ya que todas las variables (incluidas todas las variables no básicas) deben ser al menos 0, por lo que la segunda línea implicaz≤z0{\displaystyle z\leq z_{0}}.

Si algunos coeficientes enr{\displaystyle r}son positivos, entonces puede ser posible aumentar el objetivo de maximización. Por ejemplo, siincógnita5{\displaystyle x_{5}}es no básico y su coeficiente en r{\displaystyle r}es positivo, entonces aumentarlo por encima de 0 puede hacerz{\displaystyle z}mayor. Si es posible hacerlo sin violar otras restricciones, entonces la variable aumentada se convierte en básica ("entra en la base"), mientras que alguna variable básica se reduce a 0 para mantener las restricciones de igualdad y, por lo tanto, se convierte en no básica ("sale de la base").

Si este proceso se realiza con cuidado, entonces es posible garantizar quez{\displaystyle z}aumenta hasta alcanzar un BFS óptimo.

Convertir cualquier solución óptima en una BFS óptima.

En el peor de los casos, el algoritmo simplex puede requerir un número exponencial de pasos para completarse. Existen algoritmos para resolver un problema de programación lineal en tiempo débilmente polinomial , como el método del elipsoide ; sin embargo, suelen devolver soluciones óptimas que no son básicas.

Sin embargo, dada cualquier solución óptima al LP, es fácil encontrar una solución factible óptima que también sea básica . [ 2 ] : ver también "enlaces externos" a continuación.

Encontrar una base que sea óptima tanto en el plano primal como en el plano dual.

Una base B del LP se denomina dual-óptima si la soluciónyB=ABT−1⋅do{\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c} es una solución óptima al programa lineal dual, es decir, minimizabTy{\textstyle \mathbf {b^{T}} \mathbf {y} }En general, una base óptima primal no es necesariamente óptima dual, y una base óptima dual no es necesariamente óptima primal (de hecho, la solución de una base óptima primal puede incluso ser inviable para la base dual, y viceversa).

Si ambosincógnitaB=AB−1⋅b{\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}es una BFS óptima del LP primal, yyB=ABT−1⋅do{\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}Si es una BFS óptima del LP dual, entonces la base B se llama PD-óptima . Todo LP con una solución óptima tiene una base PD-óptima, y ​​se encuentra mediante el algoritmo Simplex . Sin embargo, su tiempo de ejecución es exponencial en el peor de los casos. Nimrod Megiddo demostró los siguientes teoremas: [ 2 ]

  • Existe un algoritmo de tiempo fuertemente polinomial que recibe como entrada una solución óptima para el problema de programación lineal primal y una solución óptima para el problema de programación lineal dual, y devuelve una base óptima.
  • Si existe un algoritmo de tiempo fuertemente polinomial que introduce una solución óptima solo para el LP primal (o solo para el LP dual) y devuelve una base óptima, entonces existe un algoritmo de tiempo fuertemente polinomial para resolver cualquier programa lineal (este último es un famoso problema abierto ).

Los algoritmos de Megiddo se pueden ejecutar usando un tableau, al igual que el algoritmo simplex. Megiddo, en colaboración con Beling, también propuso un algoritmo rápido que utiliza algoritmos de multiplicación de matrices rápidas . [ 3 ]

  • Cómo pasar de una solución factible óptima a una solución factible básica óptima . Paul Robin, Operations Research Stack Exchange.

Referencias

  1. 1 2 3 4 Gärtner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8.: 44–48
  2. 1 2 Megiddo, Nimrod (1991-02-01). "Sobre la búsqueda de bases óptimas primales y duales" . ORSA Journal on Computing . 3 (1): 63– 65. CiteSeerX 10.1.1.11.427 . doi : 10.1287/ijoc.3.1.63 . ISSN 0899-1499 .  
  3. ↑ Beling, Peter A.; Megiddo, N. (1998). "Uso de la multiplicación rápida de matrices para encontrar soluciones básicas". Theoretical Computer Science . 205 ( 1– 2): 307– 316. doi : 10.1016/S0304-3975(98)00003-6 .
Lecturas relacionadas
6 articulos
Programación linealProgramación linealLa programación lineal ( PL ), también llamada optimización lineal , es un método para lograr el mejor resultado (como el máximo beneficio o el men...Algoritmo simplexAlgoritmo simplexEn optimización matemática , el algoritmo simplex de Dantzig (o método simplex ) es un algoritmo popular para la programación lineal . [1]{\displaystyle \mathbf {s} \geq \mathbf {0} }Slack variableIn an optimization problem, a slack variable is a variable that is added to an inequality constraint to transform it into an equality constraint. A...Independencia linealIndependencia linealEn la teoría de espacios vectoriales , se dice que un conjunto de vectores es.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d...Matriz invertibleEn álgebra lineal , una matriz cuadrada A de n por n se denomina invertible (también no singular , no degenerada o raramente regular ) si existe un...Curva algebraicaLa cúbica de Tschirnhausen es una curva algebraica de grado tres. En matemáticas , una curva plana algebraica afín es el conjunto cero de un polino...