siendo c₁, c₂, ..., c_n números reales dados. Un problema de programación lineal consiste en la maximización¹ o minimización² de una forma lineal sujeta a una serie de restricciones también expresadas como formas lineales. Tales restricciones pueden ser igualdades o desigualdades.

es un problema de programación lineal

Observación 1 En el programa lineal no hemos considerado restricciones de desigualdad estricta. El motivo de esta exclusión lo explicaremos más adelante.

    En la expresión 10 distinguimos los elementos siguientes:

1. La función objetivo z=c₁ x₁ + c₂ x₂ + ... + c_n x_n es la forma lineal que debe optimizarse y sus coeficientes c₁, c₂, ...,c_n reciben el nombre de coeficientes de beneficio o coeficientes de coste.
2. Las variables x₁, x₂, ..., x_n que se denominan variables de decisión o instrumentales.
3. Las restricciones a_i1₁x₁+a_i1₁x₂+... +a_i1₁x_n ( £ ) ( ³ )(=)b_i, i=1, ..., r.
4. Los coeficientes a_ij, i=1, ..., r, j=1, ..., n, llamados coeficientes tecnológicos.
5. Los términos independientes b_i, i=1, ..., r son los coeficientes de disponibilidades.

    La mayoría de las aplicaciones exigen la no negatividad de las variables de decisión. Esto es, a 10 debemos añadir las restricciones x_i ³ 0, i=1, ..., n. También suele aceptarse que los coeficientes de disponibilidades son no negativos. Esto último es fácil de conseguir. En efecto, si b_i es negativo bastará multiplicar por -1 ambos miembros de la restricción correspondiente

para que el coeficiente b_i sea positivo. Este producto por -1 invierte el sentido de las desigualdades. Así una desigualdad ³ pasa a ser £ y viceversa. La inclusión de todas estas restricciones de no negatividad determina la llamada forma general de un programa lineal (FGPL):

    Afirmamos que todo problema de programación lineal puede expresarse en la forma general. Ilustramos este aserto con un ejemplo.

Ejemplo 3 Sea el programa lineal

    Multiplicamos por -1 ambos miembros de la primera desigualdad y el programa queda

    No todas las variables de decisión son no negativas. Concretamente ni x₂ ni x₃ están determinadas de ese modo. Para conseguir que sólo intervengan variables de decisión no negativas hacemos las asignaciones

donde suponemos que x₄,x₅,x₆ y x₇ son no negativas. ¿Cuál es la justificación de este cambio? Es fácil comprobar que cualquier cantidad sea positiva o negativa puede ponerse como diferencia de dos cantidades positivas. En el caso de que el resultado sea negativo es que el sustraendo es mayor que el minuendo y en el caso en que sea positivo es porque el minuendo es mayor que el sustraendo ³ . Sustituimos ahora los valores 15 y 16 en 14 y obtenemos la FGPL

    Existen muchas otras posibilidades de expresar un programa lineal. Veamos algunas de ellas:

    La expresión 18 es la llamada primera forma canónica (1FC), la expresión 19 es la segunda forma canónica (2FC) y la 20 la forma estándar (FE). Señalemos que es deseable en todas ellas que los coeficientes de disponibilidades sean no negativos pero no se exige a priori. Es posible pasar de una de ellas a cualquiera de las otras mediante alguna de las manipulaciones siguientes:

• Paso de minimización a maximización y viceversa. Teniendo en cuenta que

    Esto es fácilmente justificable pensando en que una restricción del tipo de 27 nos muestra un defecto que puede subsanarse añadiendo una cantidad positiva. Esta cantidad positiva añadida recibe el nombre de variable de holgura y se considera que también está presente en la función objetivo z con coeficiente de coste o beneficio c_n+1₊₁ igual a cero. Para restricciones del tipo

bastará restar una variable positiva x_n+1₊₁ en la forma

    Esta variable se llama excedente y también se supone que tiene asociado un coste cero en la función objetivo.

Ejemplo 4 Vamos a practicar las manipulaciones expuestas con el programa lineal

    En primer lugar vamos a ponerlo en la forma general (FGPL). Para ello utilizamos la manipulación 3 puesto que x₁ y x₂ no se especifican como no negativas. De esta manera quedan

donde x₄,x₅,x₆ y x₇ son no negativas. Ahora sustituimos en 31 y queda en FPGL

    Al ponerlo en FGPL resulta que ya está en la primera forma canónica (1FC). Si queremos ponerlo en la segunda forma canónica (2FC) habrá que transformar la minimización en maximización e invertir el sentido de las desigualdades.

    Es de notar el único coeficiente de disponibilidad del problema es negativo. Por último, pasaremos de 34 a la forma estándar añadiendo una variable de holgura.

    El coeficiente de esta variable de holgura en la función objetivo es cero.

Con el fin de simplificar la notación y ganar en comodidad vamos a expresar los distintos programas lineales en forma matricial. Los elementos que vamos a considerar son los siguientes:

    Señalemos que los vectores c,x,b son de tipo columna y que la matriz A tiene tantas filas como coeficientes de disponibilidades y tantas filas como variables de decisión. La 1FC es entonces

donde la desigualdad A x ³ b representa las desigualdades

y la desigualdad x ³ 0 se entiende como x_i ³ 0,i=1,..., n. La 2FC queda

donde la desigualdades se entienden de manera paralela al caso anterior. Por último, la forma estándar es

    En 41, 43 y 44 no se considera que los correspondientes A, c y b sean los mismos, tan sólo se utilizan las mismas letras por simetría y comodidad. Así un mismo problema puede tener matrices y vectores columna diferentes al formularse en las distintas expresiones anteriores.

Ejemplo 5 Sea el programa lineal

    Vamos a ponerlo en FE. Para ello lo pasamos primero a FGPL. El primer paso es multiplicar la segunda desigualdad por -1 para que todos los coeficientes de disponibilidades sean positivos. A continuación aseguramos la no negatividad de las variables x,y,z mediante 

    Teniendo en cuenta el resultado de multiplicar por -1 y haciendo los cambios 46, 47 y 48 resulta

    El problema 49 ya está en forma general y su expresión matricial es la siguiente (50)

    Para llegar de esta forma general a la estándar nos quedan aún una serie de transformaciones. La primera de ellas es el paso de maximización a minimización

y la segunda y última la introducción de variables excedentes

    La expresión matricial del programa estándar es (53)

    A partir de ahora para las consideraciones de tipo teórico emplearemos el programa lineal en forma estándar. Esto no supone pérdida de generalidad ya que todos las formas expuestas son equivalentes.

Supongamos un programa lineal estándar

    El conjunto formado por los elementos x=(x₁, x₂, ...,x_n)^T que verifican la igualdad A x=b y la desigualdad x ³ 0 se llama conjunto factible del programa lineal 54 y sus elementos reciben el nombre de soluciones factibles. Este conjunto es convexo y cerrado como probamos a continuación.

Teorema 1 [Convexidad del conjunto factible] El conjunto factible de un programa estándar es un conjunto convexo y cerrado .

    Sabemos que la igualdad matricial A x=b condensa las igualdades

    Cada una de estas igualdades puede entenderse como la intersección de dos semiespacios cerrados deRⁿ

    Tales semiespacios son conjuntos convexos. Por otro lado, la desigualdad x ³ 0 también resume las desigualdades

    Esas desigualdades son también semiespacios cerrados enRⁿ. En resumen, el conjunto factible resulta la intersección de una serie de conjuntos convexos cerrados y es, por tanto, convexo y cerrado. En particular al ser intersección de semiespacios cerrados es un politopo.

    El conjunto factible puede ser:

• Vacío y en tal caso el programa no tiene solución (se llama entonces programa no factible).
• Con un sólo elemento y entonces éste es trivialmente la solución.
• Con más de un elemento. En tal caso tiene infinitos. Este aserto es una consecuencia de la convexidad de dicho conjunto. En efecto, si x₁ y x₂ son soluciones factibles, también lo son los puntos del segmento cerrado que las une

    Este conjunto tiene infinitos elementos y, en consecuencia, el conjunto factible es también infinito. Este es el único caso que nos interesa puesto que los demás son triviales. Aquellos elementos del conjunto factible que hagan máxima o mínima la función objetivo (según corresponda) se llaman soluciones factibles óptimas. En el caso de conjuntos factibles infinitos y sin hipótesis adicionales no está garantizada su existencia.

Ejemplo 6 Sea el programa lineal estándar 

    El conjunto factible es infinito. En efecto, el sistema

es compatible indeterminado. El conjunto factible es el conjunto de las soluciones de este sistema que sean no negativas. Es fácil comprobar que tal conjunto es un segmento enR³ y está acotado.

    Supongamos que el conjunto factible es no vacío⁴ y que está acotado. Entonces será un compacto⁵ no trivial y recibe el nombre de poliedro. En este caso el Teorema de Weierstrass nos permite asegurar que el programa tiene solución factible óptima. Sin embargo no nos indica dónde buscarla. La sección siguiente nos da algunas pistas sobre el particular.

    Consideremos el conjunto factible

de un programa lineal estándar. Supongamos que la matriz A tiene de rango m . En tal caso, podemos extraer m columnas de A para formar una submatriz cuadrada D de rango m. Si llamamos x_D al vector genérico formado por las respectivas filas de x (esto es, si la columna j forma parte de la matriz D, entonces se toma la componente x_j del vector x) resulta que el sistema

es compatible y determinado, con solución

    Si ahora igualamos a cero las componentes del vector x que no han intervenido en x_D tenemos una solución del sistema original 58 que llamamos solución básica. Precisamos estas ideas con la siguiente definición.

Definición 1 Dado un sistema A x=b de m ecuaciones lineales y n incógnitas y sea D una submatriz cuadrada de A con rango m. Entonces si todas las n-m componentes de x no asociadas a las columnas de D se igualan a cero, la solución del conjunto resultante de ecuaciones se llama solución básica del sistema original respecto a la base D. Las componentes de x asociadas a las columnas de D se laman variables básicas.

Ejemplo 7 Sea el sistema lineal 

es compatible determinado con solución x=¹/₃, y=- ⁵/₉, z=¹/₉. La solución básica del sistema respecto a la base formada por los vectores columna de D no es más que la expresión del vector

respecto a dicha base. En efecto

    Por otro lado, se puede comprobar que el vector (¹/₃,-⁵/₉, ¹/₉, 0)^T es solución del sistema 61. Las variables x,y,z reciben el nombre de básicas mientras que la variable t se llama no básica.

    En general, no podemos asegurar que un sistema A x=b tenga soluciones básicas. Para ello hay que hacer algunas hipótesis adicionales. Es común suponer que la matriz A es de tipo m ×n con m < n y su rango es máximo (es decir m). Esta hipótesis se llama de rango completo. Con esta hipótesis se puede asegurar que el sistema A x tiene solución y, en particular, una solución básica.

    No todas las soluciones básicas tienen componentes distintas de cero (aunque es deseable por simplicidad). En el caso de que alguna de las variables de una solución básica sea nula se dice que tal solución es degenerada. En las soluciones básicas degeneradas hay una cierta ambigüedad a la hora de determinar las variables básicas y las no básicas puesto que pueden intercambiarse las básicas nulas con las no básicas nulas sin que el valor de la función objetivo cambie.

    Obviamente, una solución básica no tiene por qué ser factible. Es decir, aunque tengamos una solución de 58 no todas las variables son necesariamente no negativas. En el caso de que así sea se dice que la solución factible es además básica. Por supuesto, estas soluciones son las que realmente nos interesan. Las soluciones básicas son determinantes a la hora de resolver los programas lineales. A continuación, enunciamos y probamos un teorema que nos garantiza su existencia

Teorema 2 [Teorema fundamental de la Programación Lineal] Dado un programa lineal de forma estándar que verifica la hipótesis del rango completo se tiene que:

1. si hay una solución factible también hay una solución factible básica;
2. si hay una solución factible óptima, también hay una solución factible básica óptima.

    De esta manera, tenemos que la solución dada por 71 es factible y tiene como máximo p-1 variables positivas (es decir, coeficientes positivos). Repitiendo este proceso podemos eliminar variables positivas hasta conseguir una solución factible que tenga los a_i correspondientes linealmente independientes. En este punto aplicamos el caso 1.
    Demostremos el segundo apartado. Sea x=(x₁, x₂, ..., x_n) una solución factible óptima. Suponemos como antes que hay que las p primeras variables son positivas. Entonces, queda

    Si los vectores a_i son linealmente independientes, la demostración es análoga al caso 1 anterior. Si son linealmente dependientes también se sigue un desarrollo paralelo al caso 2 anterior pero con la salvedad de que hay que probar que para cada e la solución 71 es óptima. Tal solución puede expresarse en forma matricial

por lo que su valor en la función objetivo es

    Si suponemos que c^T y ¹ 0, entonces tomando un valor de e suficientemente pequeño conseguiremos una solución factible (esta argumentación es consecuencia de los razonamientos del caso 2 anterior). Aplicando 75 resultaría que esta solución factible tendría un valor más pequeño que la óptima x, lo cual es absurdo. Así pues ha de ser c^T y=0. En conclusión, x -ey también es una solución óptima para cualquier valor de e, por lo que aplicando los mismos pasos que en el caso 2 anterior concluimos que es posible encontrar una solución factible básica óptima. Esto termina nuestra demostración.

    El teorema fundamental de la programación lineal nos informa de la especial relación existente entre las soluciones y los puntos extremos. En su demostración sólo hemos empleado razonamientos algebraicos y hemos obviado el aspecto geométrico del problema. Sin embargo, este aspecto geométrico es muy importante y facilita la comprensión y resolución de multitud de problemas. Para entender los resultados que vamos a exponer se deben recordar algunos conceptos de la Teoría de conjuntos convexos. Sean x₁,x₂, ..., x_n vectores deRⁿ y l₁, l₂, ..., l_n números reales, el vector

es una combinación lineal de los vectores x₁,x₂,..., x_n.

• Si å_i=1ⁿ l_i=1 entonces es una combinación afín de esos mismos vectores.
• Si l_i ³ 0, i=1, ..., n es una combinación cónica.
• Si es una combinación afín ( å_i=1ⁿ l_i=1 ) y cónica (l_i ³ 0, i=1, ..., n ) se dice que es una combinación lineal convexa.

    Un punto x de un convexo K es un extremo si no puede expresarse como combinación lineal convexa de otros puntos de K diferentes a él. Un convexo puede no tener puntos extremos, tener un número finito o tener un número infinito.

Teorema 3 Sea un programa lineal estándar que verifica la hipótesis del rango completo. Sea K el politopo determinado por el conjunto factible. Un vector x es punto extremo de K si y sólo si es una solución factible básica.

    Supongamos que x=(x₁, x₂, ..., x_m, 0, ..., 0) es una solución factible básica. Entonces, por definición

siendo los vectores a₁, a₂, ...,a_m linealmente independientes. Si suponemos que x es combinación convexa de otros dos puntos y, z de K diferentes ambos del mismo x resultará que

con 0 < a < 1. En particular, como y y z pertenecen a K cumplirán A y=b con y ³ 0 y A z=b también con z ³ 0. Por ello, de 78 y de la positividad de sus componentes se sigue que las n-m últimas componentes de los vectores y y z son nulas y se dan las igualdades

    Pero como los vectores a₁, a₂, ...,a_m son linealmente independientes, habrá de ser y=z y sustituyendo en 78 se tiene x=y=z. Esto prueba que la solución factible básica es un extremo del politopo. Recíprocamente, supongamos que x es un punto extremo del politopo K. Aceptemos también que las primeras k componentes de tal vector son no nulas

    Si comprobamos que los vectores a₁, a₂,..., a_k son linealmente independientes, entonces el punto extremo será una solución factible básica. Haremos esta prueba por reducción al absurdo. En efecto, si los vectores a₁, a₂, ..., a_k son linealmente dependientes, hallaremos escalares no todos nulos y₁, y₂,..., y_k tales que

    Para el vector y=(y₁, y₂, ..., y_k, 0,0, ..., 0) se comprueba que, tomando un e adecuado, los vectores x+ ey y x - ey pertenecen al politopo K. Así es, ya que podemos conseguir que todas las componentes de ambos vectores sean positivas y además A (x±ey)=Ax±eA y=b ±0=b. Por otro lado, podemos escribir

    La igualdad 84 implica que x es combinación lineal convexa de dos puntos distintos de K por lo que no se trata de un extremo. Esto es absurdo y nos lleva a concluir que nuestra hipótesis de no independencia de los vectores a₁, a₂, ..., a_m es falsa. En consecuencia tales vectores son linealmente independientes y el punto extremo es una solución factible básica (que puede ser degenerada si k < m). Esto termina nuestra demostración.

    Es posible deducir una serie de consecuencias inmediatas del teorema 3 y del teorema fundamental.

Corolario 1 Si un programa lineal que verifica la hipótesis del rango completo tiene conjunto factible no vacío entonces tiene al menos un punto extremo.

    De acuerdo con el teorema fundamental si un programa lineal tiene alguna solución factible entonces tiene también al menos una solución factible básica. Como tales soluciones son puntos extremos se concluye que también tiene al menos un punto extremo.

Corolario 2 Si un programa lineal que verifica la hipótesis del rango completo tiene una solución óptima finita, entonces existe una solución óptima finita que es un punto extremo del conjunto factible.

    De nuevo utilizando el teorema fundamental se deduce que todo programa lineal que verifica la hipótesis del rango completo y que tiene una solución factible óptima también tiene una solución factible básica óptima. Tal solución factible básica óptima es un punto extremo.

Corolario 3 El conjunto factible de un programa lineal que cumple la hipótesis del rango completo, tiene un número finito de puntos extremos.

    En virtud del teorema 3 sabemos que las soluciones básicas son puntos extremos y viceversa. Evidentemente, sólo es posible seleccionar para cada matriz A_m ×n _×n de rango máximo m un número finito de vectores básicos (en particular \binomnm). Tales vectores básicos son los puntos extremos.

    Los resultados demostrados en los párrafos anteriores hacen referencia a conjuntos convexos y cerrados pero no necesariamente acotados. En efecto, ya vimos que los conjuntos factibles de los programas en forma estándar eran conjuntos convexos y cerrados. En el caso de que además tales conjuntos estén acotados es posible obtener todos sus puntos utilizando sólo los puntos extremos. El siguiente teorema, que enunciamos sin demostración, nos permite efectuar esta afirmación.

Teorema 4 Si K es un conjunto no vacío convexo y compacto enRⁿ, entonces todo punto de K es combinación lineal convexa de sus puntos extremos.

Notas al pie:

¹ Es decir, búsqueda del máximo.

² Búsqueda del mínimo.

³ Más adelante daremos un argumento distinto que justifica también este paso.

⁴ Se dice entonces que el programa es consistente.

⁵ Ya que es cerrado y acotado.