Solución básica factible

Concepto de programación lineal

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

Definiciones

Preliminares: forma ecuacional con filas linealmente independientes

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

maximizar ${\textstyle \mathbf {c^{T}} \mathbf {x} }$

sujeto a y ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle \mathbf {x} \geq 0}$

dónde:

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

Cualquier programa lineal se puede convertir en una forma ecuacional agregando variables de holgura .

Como paso preliminar de limpieza, verificamos que:

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

Solución factible

Una solución factible del PL es cualquier vector tal que . Suponemos que hay al menos una solución factible. Si m = n , entonces solo hay una solución factible. Normalmente m < n , por lo que el sistema tiene muchas soluciones; cada una de estas soluciones se denomina solución factible del PL. ${\displaystyle \mathbf {x} \geq 0}$ ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle A\mathbf {x} =\mathbf {b} }$

Base

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

A veces, el término base no se utiliza 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 por la matriz cuadrada m por m formada por las m columnas de indexadas por B. Si es no singular , las columnas indexadas por B son una base del espacio columna de . En este caso, llamamos a B una base del PL. ${\displaystyle A_{B}}$ ${\displaystyle A}$ ${\displaystyle A_{B}}$ ${\displaystyle A}$

Como el rango de es m , tiene al menos una base; como tiene n columnas, tiene como máximo bases. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle {\binom {n}{m}}}$

Solución básica factible

Dada una base B , decimos que una solución factible es una solución factible básica con base B si todas sus variables distintas de cero están indexadas por B , es decir, para todos los . ${\displaystyle \mathbf {x} }$ ${\displaystyle j\not \in B:~~x_{j}=0}$

Propiedades

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

2. Por definición, una BFS tiene como máximo m variables distintas de cero y al menos n - m variables cero. 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 factible es básica si y sólo si las columnas de la matriz son linealmente independientes, donde K es el conjunto de índices de los elementos distintos de cero de . ^{[1] : 45} ${\displaystyle \mathbf {x} }$ ${\displaystyle A_{K}}$ ${\displaystyle \mathbf {x} }$

4. Cada base determina una única BFS: para cada base B de m índices, hay como máximo una BFS con base B . Esto se debe a que debe satisfacer la restricción , y por definición de base la matriz no es singular, por lo que la restricción tiene una solución única: ${\displaystyle \mathbf {x_{B}} }$ ${\displaystyle \mathbf {x_{B}} }$ ${\displaystyle A_{B}\mathbf {x_{B}} =b}$ ${\displaystyle A_{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 única solución de satisface las restricciones de no negatividad , entonces B se denomina base factible . ${\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}$ ${\displaystyle \mathbf {x_{B}} \geq 0}$

5. Si un programa lineal tiene una solución óptima (es decir, tiene una solución factible y el conjunto de soluciones factibles está acotado), entonces tiene una BFS óptima. Esto es una consecuencia del principio del máximo de Bauer : el objetivo de un programa lineal es convexo; el conjunto de soluciones factibles es convexo (es una intersección de hiperespacios); por lo tanto, el 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á limitado por , se puede encontrar una solución óptima para cualquier PL en un tiempo finito simplemente evaluando la función objetivo en todos los BFS. Esta no es la forma más eficiente de resolver un PL; el algoritmo símplex examina los BFS de una manera mucho más eficiente. ${\displaystyle {\binom {n}{m}}}$ ${\displaystyle {\binom {n}{m}}}$

Ejemplos

Consideremos un programa lineal con las siguientes restricciones:

${\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:

${\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 no es singular. ${\displaystyle A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}}$

El BFS único correspondiente a esta base es . ${\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 está 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 única solución básica factible . De manera similar, cada base define una solución para el programa lineal dual : ${\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}$

minimizar ${\textstyle \mathbf {b^{T}} \mathbf {y} }$

sujeto a . ${\displaystyle A^{T}\mathbf {y} \geq \mathbf {c} }$

La solución es . ${\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}$

Encontrar un BFS óptimo

Existen varios métodos para encontrar un BFS que también sea óptimo.

Utilizando el algoritmo simplex

En la práctica, la forma más fácil de encontrar una BFS óptima es utilizar el algoritmo simplex . Mantiene, en cada punto de su ejecución, una "base actual" B (un subconjunto de m de n variables), una "BFS actual" y una "tabla actual". La tabla es una representación del programa lineal donde las variables básicas se expresan en términos de las no básicas: ^{[1] : 65} donde es el vector de m variables básicas, es el vector de n variables no básicas y es el objetivo de maximización. Como las variables no básicas son iguales a 0, la BFS actual es y el objetivo de maximización actual es . $${\displaystyle {\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}}$$ ${\displaystyle x_{B}}$ ${\displaystyle x_{N}}$ ${\displaystyle z}$ ${\displaystyle p}$ ${\displaystyle z_{0}}$

Si todos los coeficientes en son negativos, entonces 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 implica . ${\displaystyle r}$ ${\displaystyle z_{0}}$ ${\displaystyle z\leq z_{0}}$

Si algunos coeficientes de son positivos, entonces puede ser posible aumentar el objetivo de maximización. Por ejemplo, si no es básico y su coeficiente en es positivo, entonces aumentarlo por encima de 0 puede hacer que sea más grande. Si es posible hacerlo sin violar otras restricciones, entonces la variable aumentada se vuelve 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 vuelve no básica ("sale de la base"). ${\displaystyle r}$ ${\displaystyle x_{5}}$ ${\displaystyle r}$ ${\displaystyle z}$

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

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

En el peor de los casos, el algoritmo símplex puede requerir una cantidad exponencial de pasos para completarse. Existen algoritmos para resolver un PL en tiempo débilmente polinomial , como el método del elipsoide ; sin embargo, generalmente devuelven soluciones óptimas que no son básicas.

Sin embargo, dada cualquier solución óptima para la PL, 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 a la vez óptima primaria y óptima dual

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

Si ambos son una BFS óptima del LP primario y 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] ${\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}$ ${\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}$

• Existe un algoritmo de tiempo fuertemente polinomial que ingresa una solución óptima para el LP primal y una solución óptima para el LP dual, y devuelve una base óptima.
• Si existe un algoritmo de tiempo fuertemente polinomial que ingresa 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 utilizando una tabla, al igual que el algoritmo simplex.

Enlaces externos

• 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. 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. Megiddo, Nimrod (1991-02-01). "Sobre la búsqueda de bases óptimas primarias 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.