www.matematicas.net

¡Pulsa Aquí!

LO DIJO...

Lee Smolin  
 
En el fondo, los científicos somos gente con suerte: podemos jugar a lo que queramos durante toda la vida.
 
www.matematicas.net - Nuestros Temas ~ El modelo de programación lineal
.: Nuestros Temas :.
El modelo de programación lineal

Contenido

1  Primeras consideraciones
2  Expresión matricial
3  Conjunto factible
4  Soluciones básicas. Teorema fundamental de la programación lineal
5  Soluciones básicas y puntos extremos

1  Primeras consideraciones

    Una forma lineal de Rn en R es una aplicación

f:Rn ' (x1,x2, ¼, xn) ®z(x1,x2, ..., xn) ÎR
(1)

donde

z(x1,x2, ..., xn)=c1 x1 + c2 x2 + ... + cn xn
(2)

siendo c1, c2, ..., cn números reales dados. Un problema de programación lineal consiste en la maximización1 o minimización2 de una forma lineal sujeta a una serie de restricciones también expresadas como formas lineales. Tales restricciones pueden ser igualdades o desigualdades.

Ejemplo 1 Sea la forma lineal f:R2® R definida por

z(x,y)=2 x-y
(3)

y sean las restricciones lineales

x-y
£
(4)
2x+y
³
(5)

    El problema de buscar el mínimo de z sujeto a las restricciones 4 y 5 es un problema de programación lineal. En particular, se debe formular de la siguiente manera

Minimizar z
2 x-y
sujeto a x-y
£
(6)
2x+y
³

Ejemplo 2 Sean la forma lineal z=3x1-2x2+x3 y las restricciones

x1-2 x2
(7)
x3
£
(8)

    El problema

Maximizar z
3x1-2x2+x3
sujeto a x1-2x2
(9)
x3
£

es un problema de programación lineal

    Podemos convenir en que un programa lineal es un problema del tipo

Minimizar (Maximizar) z=c1x1+c2 x2+... +cn xn

 

sujeto a 
a11x1+a12x2+... +a1nxnxn £
b1
a21x1+a22x2+... +a2nxnxn £
b2
ap11x1+ap22x2+... +apnxn £
bp
ap+1,1+1,1x1+ap+1,2+1,2x2+... +ap+1,nxnxn ³
bp+1+1
ap+2,1+2,1x1+ap+2,2+2,2x2+... +ap+2,nxnxn ³
bp+2+2
(10)
aq11x1+aq22x2+... +aqnxn ³
bq
aq+1,1+1,1x1+aq+1,2+1,2x2+... +aq+1,nxnxn
bq+1+1
ar11x1+ar22x2+... +arnxn
br

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=c1 x1 + c2 x2 + ... + cn xn es la forma lineal que debe optimizarse y sus coeficientes c1, c2, ...,cn reciben el nombre de coeficientes de beneficio o coeficientes de coste.
  2. Las variables x1, x2, ..., xn que se denominan variables de decisión o instrumentales.
  3. Las restricciones ai11x1+ai11x2+... +ai11xn ( £ ) ( ³ )(=)bi, i=1, ..., r.
  4. Los coeficientes aij, i=1, ..., r, j=1, ..., n, llamados coeficientes tecnológicos.
  5. Los términos independientes bi, 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 xi ³ 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 bi es negativo bastará multiplicar por -1 ambos miembros de la restricción correspondiente

ai11x1+ai11x2+... +ai11xn ( £ ) ( ³ ) (=)bi
(11)

para que el coeficiente bi 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):

Minimizar (Maximizar) z=c1x1+c2 x2+... +cn xn
sujeto a 
a11x1+a12x2+... +a1nxnxn £
b1
a21x1+a22x2+... +a2nxnxn £
b2
ap11x1+ap22x2+... +apnxn £
bp
ap+1,1+1,1x1+ap+1,2+1,2x2+... +ap+1,nxnxn ³
bp+1+1
ap+2,1+2,1x1+ap+2,2+2,2x2+... +ap+2,nxnxn ³
bp+2+2
(12)
aq11x1+aq22x2+... +aqnxn ³
bq
aq+1,1+1,1x1+aq+1,2+1,2x2+... +aq+1,nxnxn
bq+1+1
ar11x1+ar22x2+... +arnxn
br
x1 ³ 0, x2 ³ 0, ..., xn ³
b1 ³ 0, b2 ³ 0, ..., bm ³

    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

Maximizar z
2 x1 + x2 -x3
sujeto a x1-x2+ 2x3
£
-1 
x2-x3
2
(13)
x1
³

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

Maximizar 
z
2 x1 + x2 -x3
sujeto a -x1+x2- 2x3
³
x2-x3
2
(14)
x1
³

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

x2
x4-x5
(15)
x3
x6-x7
(16)

donde suponemos que x4,x5,x6 y x7 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 3 . Sustituimos ahora los valores 15 y 16 en 14 y obtenemos la FGPL

Maximizar z=2 x1 + x4-x5-x6+x7
sujeto a -x1+x4-x5-2x6+2x7
³
x2-x6+x7
2
(17)
x1 ³ 0, x4 ³ 0,x5 ³ 0,x6 ³ 0, x7 ³

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

Minimizar z=c1x1+c2 x2+... +cn xn

 

sujeto a 
a11x1+a12x2+... +a1nxnxn
³
b1
a21x1+a22x2+... +a2nxnxn
³
b2
(18)
am11x1+am22x2+... +amnxn
³
bm
x1 ³ 0, x2 ³ 0, ..., xn ³

Maximizar z=c1x1+c2 x2+... +cn xn
sujeto a 
a11x1+a12x2+... +a1nxnxn £
b1
a21x1+a22x2+... +a2nxnxn £
b2
(19)
am11x1+am22x2+... +amnxn £
bm
x1 ³ 0, x2 ³ 0, ..., xn ³

Minimizar z=c1x1+c2 x2+... +cn xn

 

sujeto a 
a11x1+a12x2+... +a1nxnxn
b1
a21x1+a22x2+... +a2nxnxn
b2
(20)
am11x1+am22x2+... +amnxn
bm
x1 ³ 0, x2 ³ 0, ..., xn ³

    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
min f(x)=- max (-f(x))
(21)
podemos pasar cualquier programa de maximización a uno de minimización. Del mismo modo
max f(x)=- min (-f(x))
(22)
implica que todo problema de minimización puede pasarse a uno de maximización.
  • Paso de igualdad a desigualdad. Una igualdad
ai11x1+ai22x2+... +ainxn=bi
(23)
equivale a dos desigualdades no estrictas
ai11x1+ai22x2+... +ainxn
£
bi
(24)
ai11x1+ai22x2+... +ainxn
³
bi
(25)
  • No negatividad de las variables. Si alguna de las variables de decisión es no negativa, se sustituye por una diferencia de dos variables no negativas (ver el ejemplo 3). En efecto, sea xi la variable en cuestión. Sean x+i=max {0,x} y x-i=max {0,-x}. Entonces se tiene que x+i ³ 0 y x-i ³ 0 con
xi=x+i - x-i
(26)
Si xi tuviera un valor negativo entonces x+i=0 y x-i=-x por lo que xi=0-(-x)=x. En el caso contrario también se comprueba la misma igualdad.
  • Cambio de inecuación a ecuación. Este paso es uno de los más importantes. Supongamos que
ai11x1+ai22x2+... +ainxn £ bi
(27)
es una restricción del programa lineal. Añadiendo una variable no negativa xn+1+1 a 27 se tiene
ai11x1+ai22x2+... +ainxn+xn+1+1=bi
(28)

    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 cn+1+1 igual a cero. Para restricciones del tipo

ai11x1+ai22x2+... +ainxn ³ bi
(29)

bastará restar una variable positiva xn+1+1 en la forma

ai11x1+ai22x2+... +ainxn-xn+1+1=bi
(30)

    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

Minimizar z
2 x1 + x2 -3 x3
sujeto a 
x1+x2
³
(31)
x3
³

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

x1=x4-x5
(32)
x2=x6-x7
(33)

donde x4,x5,x6 y x7 son no negativas. Ahora sustituimos en 31 y queda en FPGL

Minimizar z=2 x4 - 2 x5 + x6 - x7 -3x3

 

sujeto a 
x4-x5+x6-x7 ³ 1

 

(34)
x3 ³ 0, x4 ³ 0, x5 ³ 0, x6 ³ 0, x7 ³ 0

    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.

- Maximizar -z=-2 x4 + 2 x5 - x6 + x7 +3x3

 

sujeto a 
-x4+x5-x6+x7 £ -1

 

(35)
x3 ³ 0, x4 ³ 0, x5 ³ 0, x6 ³ 0, x7 ³ 0

    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.

Minimizar z=2 x4 - 2 x5 + x6 - x7 -3x3 +0x8

 

sujeto a 
x4-x5+x6-x7+x8=1

 

(36)
x3 ³ 0, x4 ³ 0, x5 ³ 0, x6 ³ 0, x7 ³ 0

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

2  Expresión matricial

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:

c æ
ç
ç
ç
ç
ç
è
c1
c2
:
cn
ö
÷
÷
÷
÷
÷
ø
(37)

x æ
ç
ç
ç
ç
ç
è
x1
x2
:
xn
ö
÷
÷
÷
÷
÷
ø
(38)

b æ
ç
ç
ç
ç
ç
è
b1
b2
:
bm
ö
÷
÷
÷
÷
÷
ø
(39)

A æ
ç
ç
ç
ç
ç
è
a11
a12
... 
a1,n-1
a1,n
a21
a22
... 
a2,n-1
a2,n
:

 

... 

 

:
am11
am22
... 
am,n-1,n-1
am,n,n
ö
÷
÷
÷
÷
÷
ø
(40)

    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

Minimizar z
cT x
sujeto a 
Ax ³ b
(41)
x ³ 0

donde la desigualdad A x ³ b representa las desigualdades

n
å
j=1
aijxj ³ bi        i=1, ..., m
(42)

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

Maximizar z
cT x
sujeto a 
Ax £ b
(43)
x ³ 0

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

Minimizar z
cT x
sujeto a 
Ax=b
(44)
x ³ 0

    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

Maximizar z=2 x - 3y +z
sujeto a x -y +z ³
(45)
x+y £ -1 

    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 

x
x1-x2
(46)
y
x3-x4
(47)
z
x5-x6
(48)

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

Maximizar z=2 x1- 2 x2 - 3 x3+3 x4 +x5-x6
sujeto a x1-x2 -x3+x4 +x5-x6 ³
(49)
-x1+x2-x3+x4 ³
x1 ³ 0, x2 ³ 0, x3 ³ 0, x4 ³ 0, x5 ³ 0, x6 ³ 0

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

Maximizar z æ
è
2
-2
-3
3
1
-1
ö
ø
æ
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
è
x1
x2
x3
x4
x5
x6
ö
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
ø
sujeto a 
æ
ç
è
1
-1
-1
1
1
-1
-1
1
-1
1
0
0
ö
÷
ø
æ
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
è
x1
x2
x3
x4
x5
x6
ö
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
ø
³ æ
ç
è
0
1
ö
÷
ø
x1 ³ 0, x2 ³ 0, x3 ³ 0, x4 ³ 0, x5 ³ 0,x6 ³ 0

    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

- Minimizar -z=-2 x1+ 2 x2 + 3 x3-3 x4-x5+x6
sujeto a x1-x2 -x3+x4 +x5-x6 ³
(51)
-x1+x2-x3+x4 ³
x1 ³ 0, x2 ³ 0, x3 ³ 0, x4 ³ 0, x5 ³ 0, x6 ³ 0

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

- Minimizar -z=-2 x1+ 2 x2 + 3 x3-3x4-x5+x6+0x7+0x8
sujeto a 
x1-x2 -x3+x4 +x5-x6-x7=0 
(52)
-x1+x2-x3+x4-x8=1 
x1 ³ 0, x2 ³ 0, x3 ³ 0, x4 ³ 0, x5 ³ 0,x6 ³ 0,x7 ³ 0, x8 ³

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

- Minimizar -z æ
è
-2
2
3
-3
-1
1
0
0
ö
ø
æ
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
è
x1
x2
x3
x4
x5
x6
x7
x8
ö
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
ø
sujeto a 
æ
ç
è
1
-1
-1
1
1
-1
-1
0
-1
1
-1
1
0
0
0
-1
ö
÷
ø
æ
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
ç
è
x1
x2
x3
x4
x5
x6
x7
x8
ö
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
÷
ø
æ
ç
è
0
1
ö
÷
ø
x1 ³ 0, x2 ³ 0, x3 ³ 0, x4 ³ 0,x5 ³ 0,x6 ³ 0,x7 ³ 0, x8 ³

    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.

3  Conjunto factible

Supongamos un programa lineal estándar

Minimizar z
cT x
sujeto a 
Ax=b
(54)
x ³ 0


    El conjunto formado por los elementos x=(x1, x2, ...,xn)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

n
å
j=1
aijxj=bi        i=1, ... m

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

n
å
j=1
aijxj ³ bi        i=1, ... m
n
å
j=1
aijxj £ bi        i=1, ... m

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

xi ³ 0        i=1, ..., n

    Esas desigualdades son también semiespacios cerrados enRn. 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 x1 y x2 son soluciones factibles, también lo son los puntos del segmento cerrado que las une
[x1, x2]={ x ÎRn/x=lx1 + (1-l) x2,l Î [0,1] }
(55)

    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 

Maximizar z=2 x -y+z
sujeto a 
x + y -z=0 
(56)
2x + 3 y=2 
x,y,z ³

    El conjunto factible es infinito. En efecto, el sistema

x + y -z=0 
2x + 3 y=2
ü
ý
þ
(57)

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 enR3 y está acotado.

    Supongamos que el conjunto factible es no vacío4 y que está acotado. Entonces será un compacto5 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.

4  Soluciones básicas. Teorema fundamental de la programación lineal

    Consideremos el conjunto factible

A x=b
(58)

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 xD 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 xj del vector x) resulta que el sistema

DxD=b
(59)

es compatible y determinado, con solución

xD=D-1 b
(60)

    Si ahora igualamos a cero las componentes del vector x que no han intervenido en xD 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 

x-y+z+t=1 
2x+y-z-t=0 
x-3y+t=2
ü
ï
ï
ý
ï
ï
þ
(61)

    Su expresión matricial es

æ
ç
ç
ç
ç
è
1
-1
1
2
1
-1
-1 
1
-3
0
1
ö
÷
÷
÷
÷
ø
æ
ç
ç
ç
ç
ç
è
x
y
z
t
ö
÷
÷
÷
÷
÷
ø
æ
ç
ç
ç
ç
è
2
ö
÷
÷
÷
÷
ø
(62)

    Seleccionamos la submatriz de rango 3

D æ
ç
ç
ç
ç
è
1
-1
1
2
1
-1 
1
-3
0
ö
÷
÷
÷
÷
ø
(63)

    La matriz D está formada por las tres primeras columnas por lo que tiene asociadas las variables x,y,z. Así pues el sistema

æ
ç
ç
ç
ç
è
1
-1
2
1
-1 
1
-3
0
ö
÷
÷
÷
÷
ø
æ
ç
ç
ç
ç
è
x
y
z
ö
÷
÷
÷
÷
ø
æ
ç
ç
ç
ç
è
2
ö
÷
÷
÷
÷
ø
(64)

es compatible determinado con solución x=1/3, y=- 5/9, z=1/9. 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

b æ
ç
ç
ç
ç
è
2
ö
÷
÷
÷
÷
ø
(65)

respecto a dicha base. En efecto

1

3

(1 2 1)+  -5

9

(-1 1 3)+  1

9

(1 -1 0)=(1 0 2)
(66)

    Por otro lado, se puede comprobar que el vector (1/3,-5/9, 1/9, 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.

Consideremos el programa estándar

Minimizar z
cT x
sujeto a 
Ax=b
(67)
x ³

    Probemos el apartado 1. Para ello bastará comprobar que si el conjunto factible es no vacío entonces podemos expresar b como combinación lineal no negativa de m vectores columna de A linealmente independientes (no olvidemos que por hipótesis el rango de A es m). Supongamos que la matriz A tiene por columnas los vectores a1, a2,..., an. La existencia de una solución factible (x1, x2, ..., xn)T implica la igualdad

x1 a1 + x2 a2 + ... + xn an=b
(68)

con xi ³ 0, i=1, ..., n. Podemos suponer que p de tales n variables son no nulas (si todas las variables fueran nulas la solución factible es nula y b=0, por lo que también resulta factible básica pero degenerada, puesto que b=0 puede expresarse entonces trivialmente como combinación lineal no negativa de m vectores columna independientes de la matriz A). Por comodidad suponemos que tales variables no nulas son las p primeras (esto no afecta a la demostración). Así pues la igualdad 68 queda

x1 a1 + x2 a2 + ... +xp ap + 0 ap+1 + ... +0 an=b
(69)

    Llegados a este punto podemos analizar dos casos:
Caso 1: Los vectores a1, a2,..., ap son linealmente independientes. Entonces como m es el rango de la matriz A y tales vectores son algunas de sus columnas, se sigue que p £ m. Si p=m la solución es básica y si p < m basta tomar m-p columnas de A de manera que el conjunto resultante de m columnas sea linealmente independiente (esto es posible debido a que el rango de A es m). Asignando el valor cero a las variables asociadas a estas nuevas columnas se consigue una solución factible básica degenerada.
Caso 2: Los vectores a1, a2,...,ap son linealmente dependientes. Entonces existen escalares yi, i=1,2, ..., n no todos nulos tales que

y1 a1 + y2 a2 + ... + yp ap+ 0 ap+1+ ... +0 an=0
(70)

    Podemos suponer que al menos uno de los escalares yi, i=1,..., p de 70 es positivo (si todos fueran negativos, podríamos multiplicar por (-1) ambos miembros de 70 y obtendríamos una relación lineal donde todos los escalares son positivos ). Multiplicamos 70 por un número positivo arbitrario e y el resultado se le resta a 69, quedando(x_1- y_1) _1 + (x_2- y_2) _2 + ... + (x_p- y_p) _p+
(0- 0) _p+1+ ...+ (0- 0)_n=Observemos que esta ecuación es válida para todo e ya que al multiplicar ambos miembros de 70 por un mismo número (en este caso e) se mantiene la igualdad y al restar dos igualdades miembro a miembro obtenemos otra igualdad. Además es también una solución de A x=b. Sin embargo, no podemos asegurar que todos los coeficientes de esta solución sean no negativos. Para e=0 obtenemos la solución factible inicial y a medida que aumentamos e el valor de los coeficientes xi - eyi aumenta si yi < 0, disminuye si yi > 0 y permanece igual si yi=0. Como sabemos que una de las yi es mayor que cero, está claro que uno de estos coeficientes decrece a medida que e aumenta. Aumentemos e hasta que uno o más coeficientes no triviales se hagan nulos. Esto se consigue tomando

e min ì
í
î
xi

yi

, yi > ü
ý
þ
(71)

    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 ai correspondientes linealmente independientes. En este punto aplicamos el caso 1.
    Demostremos el segundo apartado. Sea x=(x1, x2, ..., xn) una solución factible óptima. Suponemos como antes que hay que las p primeras variables son positivas. Entonces, queda

x1 a1 + x2 a2 + ... +xp ap +=b
(72)

    Si los vectores ai 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

x -ey
(73)

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

cT (x -e y)=cTx- ecT y
(74)

    Si suponemos que cT 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 cT 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.

5  Soluciones básicas y puntos extremos

    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 x1,x2, ..., xn vectores deRn y l1, l2, ..., ln números reales, el vector

x n
å
i=1
li xi
(75)

es una combinación lineal de los vectores x1,x2,..., xn.

  • Si åi=1n li=1 entonces es una combinación afín de esos mismos vectores.
  • Si li ³ 0, i=1, ..., n es una combinación cónica.
  • Si es una combinación afín ( åi=1n li=1 ) y cónica (li ³ 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=(x1, x2, ..., xm, 0, ..., 0) es una solución factible básica. Entonces, por definición

x1 a1 + x2 a2 + ... + xm am=b
(76)

siendo los vectores a1, a2, ...,am 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

x=ay + (1- a) z
(77)

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

y1 a1 + y2 a2 + ... + ym am=b
(78)
z1 a1 + z2 a2 + ... + zm am=b
(79)

    Pero como los vectores a1, a2, ...,am 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

x=(x1, x2, ..., xk, 0, 0, ..., 0)
(80)

con xi > 0, i=1, 2, ..., k y también

x1 a1 + x2 a2+ ... + xk ak=b
(81)

    Si comprobamos que los vectores a1, a2,..., ak 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 a1, a2, ..., ak son linealmente dependientes, hallaremos escalares no todos nulos y1, y2,..., yk tales que

A y=y1 a1 + y2 a2+ ... + yk ak=0
(82)

    Para el vector y=(y1, y2, ..., yk, 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

x 1

2

(x+ ey)+  1

2

(x- ey)
(83)

    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 a1, a2, ..., am 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 Am ×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 enRn, entonces todo punto de K es combinación lineal convexa de sus puntos extremos.

Notas al pie:

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

2 Búsqueda del mínimo.

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

4 Se dice entonces que el programa es consistente.

5 Ya que es cerrado y acotado.

Area On-Line
  Todo tipo de material, para disfrutar de él completamente On-Line, sin necesidad de descargar archivos ni tener que andar descomprimiendo estos. No te olvides de pasar por el Diccionario, y las secciones Origami y Geointeractiva. Son de lo más interesante.

¿ Nuestros Temas?

En esta sección de la página, se publican distintos artículos matemáticos, ya sean teóricos o prácticos, y todos aquellos escritos que puedan ser de interés para nuestros visitantes.

Se intentan crear versiones on-line de todo el material, pero esto no siempre es posible. Unas veces debido al formato fuente del documento original, y otras al elevado tamaño del archivo final HTM/PHP que haría realmente lenta y tediosa la carga de la página on-line.

Para visualizar correctamente alguno de los artículos disponibles en PHP/HTM, es necesario disponer de los tipos de letra True Type llamados Symbol.ttf y MTExtra.ttf. Descárgalos si no los tienes. Si aun así tienes problemas para visualizar el texto, pásate por nuestra sección de ayuda.

Martes, 2 / 09 / 2014
   BUSCADOR
 

   TU CORREO
Usuario
Contraseña

   MATRACAS
Lista de correo gratuita
.: Chismes de Adán y Eva :.
Adios a Elisenda Fo...
WolframAlpha: El mo...
WIRIS para Mac...
Third CEU Summersch...
¡Más y más actualiz...
Cerca de 500 MB de ...
Ha llegado el momen...
WIRIS, matemáticas ...
El Universo Matemát...
Segundas Jornadas d...
Los Elementos de Eu...
VI Semana de la Cie...
Tras varios meses d...
¡Chiflados por los ...
Otro verano más, to...

 

Todos los derechos reservados. El Paraíso de las Matemáticas 2010Información Legal Política de PrivacidadAyudaEmail