Formas de un Problema de Programación

Lineal y convexidad

Edgar Ramos Flores

17 de junio de 2021

1. Formas de un problema PL y operaciones de reformulación

A continuacion se presenta la forma estandar y las formas canónicas de un problema de programacion
lineal con m restricciones y n variables.

1. Formas canonicas de un problema de PL

P P
Maximizar:z = j∈J cj x j Minimizar:z = j∈J cj xj
Sujeto a: Sujeto a:
P P
j∈J aij xj ≤ bi , i ∈ I j∈J aij xj ≥ bi , i ∈ I
xj ≥ 0, j ∈ J xj ≥ 0, j ∈ J
donde I = {1, 2, . . . , m} y J = {1, 2, . . . , n} donde I = {1, 2, . . . , m} y J = {1, 2, . . . , n}

2. Forma estandar de un problema de PL

P
Maximizar (Minimizar): z = j∈J cj x j
Sujeto a:
P
j∈J aij xj = bi , i ∈ I
xj ≥ 0, j ∈ J
donde I = {1, 2, . . . , m} y J = {1, 2, . . . , (m + n)}

En términos de matrices, la forma de un problema de PL esta dada por:

1. Formas canonicas de un problema de PL

Maximizar:z = ct x Maximizar:z = ct x
Sujeto a: Sujeto a:
Ax ≤ b Ax ≥ b
x≥0 x≥0

1
 2. Forma estandar de un problema de PL

Maximizar:z = ct x
Sujeto a:
Ax = b
x≥0

Para convertir los problemas en una determinada forma, podremos tener la necesidad de efectuar las
siguientes operaciones de reformulación:

1. Para transformar una inecuacion en una ecuación utilizaremos las llamadas variables de holgura

P
j∈J aij xj + xn+i = bi
X 
aij xj ≤ bi =⇒
j∈J xn+i ≥ 0



P

aij xj − xn+i = bi
j∈J
X
aij xj ≥ bi =⇒
j∈J xn+i ≥ 0


Por ejemplo, si consideramos las restricciones:

20x1 + 40x2 ≤ 800

15x1 + 12x2 ≤ 450
x1 ≤ 30
x2 ≤ 20
x1 , x2 ≥ 0

Considerando variables de holgura, se tiene:

20x1 + 40x2 +x3 ≤ 800

15x1 + 12x2 +x4 ≤ 450
x1 +x5 ≤ 30
x2 +x6 ≤ 20
x1 , x2 , x3 , x4 , x5 , x6 ≥0

2. Una igualdad es equivalente a la conjunción de dos desigualdades


P
j∈J aij xj ≤ bi
X 
aij xj = bi ⇐⇒ P
j∈J aij xj ≥ bi

j∈J 

2. Convexidad y caracterización de poliedros

El conjunto de las soluciones admisibles de un problema de programación lineal es un caso particular
de conjuntos convexos. Ası́, en esta sección son presentados los conceptos sobre la convexidad de conjun-
tos relevantes para la programación lineal, enunciando los principales resultados teóricos y describiendo
algunos ejemplos de conjuntos convexos.

2
Definición 1 (conjunto convexo)
Un conjunto S ⊆ Rn es un conjunto convexo, si para todo x1 , x2 ∈ S, entonces λx1 + (1 − λ)x2 ∈ S
para todo λ ∈ [0, 1]. O sea, un conjunto S ⊆ Rn se dice convexo si el segmento de recta entre dos puntos
cualesquiera en S esta contenido en S.

Nota 1 Por convención, el conjunto vacı́o es un conjunto convexo.

Geometricamente, la definición anterior se puede visualizar en las regiones convexas bidimensionales,

como se muestra en la figura 1

Figura 1: Ilustración de la definición de los conjuntos convexos

Ejemplo 1 Los conjuntos siguientes son conjuntos convexos:

1. W = {(x1 , x2 ) ∈ R2 : x21 + x22 ≤ 4}

2. V = {(x1 , x2 ) ∈ R2 : 0 ≤ x1 ≤ 3, x1 ≥ x2 , x2 ≥ 0}

Las regiones convexas se muestran la figura.

Figura 2: Conjuntos convexos W (izquierda) y V (derecha)

Ejemplo 2 El conjunto S ⊂ R2 de la forma S = {(x1 , x2 ) ∈ R2 : x2 ≤ x21 } no es convexo (ver figura 3),

ya que por ejemplo tomando los puntos (−1, 1), (1, 1) ∈ R2 , tenemos que:
1 1
(−1, 1) + (1, 1) ∈
/S
2 2

3
 Figura 3: Conjunto no convexo

Lema 1 Si S1 , S2 , . . . , Sp ⊆ Rn son conjuntos convexos, entonces S = S1 ∩ S2 ∩ . . . ∩ Sp es convexo.

Demostración

Si S = ∅, entonces S es convexo. Caso contrario, fijemos arbitrariamente x1 , x2 ∈ S, luego:

x1 , x2 ∈ S1 ∩ S2 ∩ . . . ∩ Sp

Esto implica que:

x1 , x2 ∈ S1 ∧ x1 , x2 ∈ S1 ∧ . . . ∧ x1 , x2 ∈ Sp

Como S1 , S2 , . . . , Sp son convexos, para λ ∈ [0, 1] se tiene que:

λx1 + (1 − λ)x2 ∈ S1 ∧ λx1 + (1 − λ)x2 ∈ S1 ∧ . . . ∧ λx1 + (1 − λ)x2 ∈ Sp

Por lo tanto,
λx1 + (1 − λ)x2 ∈ S1 ∩ S2 ∩ . . . ∩ Sp = S

Por la arbitrariedad de escoger x1 , x2 ∈ S, S es un conjunto convexo.

Lema 2 El conjunto de las soluciones admisibles de un sistema de desigualdades lineales de la forma

S = {x ∈ Rn : Ax ≤ b} es un conjunto convexo.

Demostración

Se mostrara a continuación que la región admisible de un problema de programación lineal es siempre un

conjunto convexo. Se considera el conjunto de soluciones admisibles S escrito en la forma:

S = {x ∈ Rn : Ax ≤ b, x ≥ 0}

Sean x1 , x2 ∈ S, tenemos que demostrar que λx1 + (1 − λ)x2 ∈ S para todo λ ∈ [0, 1], en efecto:

x1 ∈ S =⇒ Ax1 ≤ b,

x1 ≥ 0
x2 ∈ S =⇒ Ax2 ≤ b,

x2 ≥ 0

4

λAx1 ≤ λb,

λx1 ≥ 0
(1 − λ)Ax2 ≤ (1 − λ)b, (1 − λ)x2 ≥ 0


Sumando miembro a miembro:

λAx1 + (1 − λ)Ax2 ≤ λb + (1 − λ)b

Aλx1 + A(1 − λ)x2 ≤b
A[λx1 + (1 − λ)x2 ] ≤ b
y
λx1 + (1 − λ)x2 ≥ 0

Luego se tiene que, λx1 + (1 − λ)x2 ∈ S para λ ∈ [0, 1]. Por lo tanto, S es un conjunto convexo.

Definición 2 Un poliedro P es un subconjunto de Rn descrito por un conjunto finito de desigualdades

lineales, P = {x ∈ Rn : Ax ≤ b}.

Note en el ejemplo 1 W es un conjunto convexo, pero no es un poliedro, pues no puede ser descrito por un
numero finito de desigualdades, y V es un poliedro. En R2 , un poliedro es una interseccion de un numero
finito de semiplanos.

Figura 4: Poliedros limitados e ilimitados

Lema 3 Un poliedro en Rn es un conjunto convexo.

Demostración

Un poliedro es un conjunto resultante de un sistema finito de ecuaciones e inecuaciones lineales, esto es,
una interseccion de semiplanos que son conjuntos convexos. Como la intersección de conjuntos convexos
es un conjunto convexo, entonces el poliedro es un conjunto convexo.

Definición 3 Sea S ⊂ Rn . Decimos que un conjunto S es un politopo, cuando S es un poliedro limitado.

Ejemplo 3 Se tiene que:

1. P = {(x1 , x2 ) ∈ R2 : x1 + 2x2 ≤ 20; 5x1 + 3x2 ≤ 15; x1 , x2 ≥ 0}

2. Q = {(x1 , x2 ) ∈ R2 : x1 + 2x2 ≥ 20; 5x1 + 3x2 ≥ 15}

El poliedro P es un politopo, pero el poliedro Q no es un politopo.

5
Los poliedros pueden ser caracterizados a través de un conjunto de desigualdades o a través de un conjunto
de puntos (puntos extremos) y vectores (rayos extremos). A continuación se introducirá algunos conceptos
que nos permiten definir puntos extremos y rayos extremos.

Definición 4 (Combinacion lineal)

Un vector x ∈ Rn es una combinación lineal de los vectores x1 , x2 , . . . , xk ∈ Rn , si existen escalares
Pk
λ ∈ Rk , tales que x = i=1 λi xi .

Adicionalmente, si:
Pk
1. λi ≥ 0 y i=1 λi = 1, entonces x es una combinación lineal convexa de los vectores x1 , x2 , . . . , xk .
Pk
2. i=1 λi = 1, entonces x se dice una combinación afı́n de los vectores x1 , x2 , . . . , xk .

3. λ ≥ 0, entonces x se dice una combinación conica de los vectores.

Definición 5 (Punto extremo)

Un punto x de un conjunto convexo S ⊆ Rn es un punto extremo si no existen dos puntos distintos
x1 , x2 ∈ S tales que, para algun λ, 0 < λ < 1, x = λx1 + (1 − λ)x2 , esto es x no puede ser escrito como
combinacion lineal convexa de dos puntos cualesquiera distintos pertenecientes a S.

Observe que, en la figura, x1 es un punto extremo de S, en tanto x2 y x3 no son puntos extremos.

Figura 5: Punto extremo en un conjunto convexo

Definición 6 (Combinacion convexa de los puntos extremos)

Dado los puntos extremos x1 , x2 , . . . , xk y el politopo S. Para todas las x ∈ S, x puede ser escrito como
combinacion convexa de los puntos extremos x1 , x2 , . . . , xk , esto es:
k
X k
X
x= λi xi , para λi = 1
i=1 i=1

Definición 7 (Rayo) Un rayo (semirecta) es una coleccion de puntos de la forma {x + λr : λ ≥ 0}, en

donde r es un vector distinto de cero. En este caso, x es el vertice del rayo y r es la direccion del rayo.

6
Nota 2 (Direcciones de un conjunto convexo)
Si se tiene un conjunto convexo y un vector r distinto de cero, se dice que r es una dirección del con-
junto, si para cada x dentro del conjunto, el rayo o semirecta {x + λr : λ ≥ 0} también pertenece al
conjunto. Basándose en esta definición se puede concluir que si un conjunto es acotado, entonces no
tiene direcciones.

Nota 3 (Dirección extrema)

La nocion de direccion extrema es similar a la nocion de punto extremo. Una dirección extrema de un
conjunto convexo es una direccion del conjunto que no puede ser representado como combinacion positiva
de dos direcciones del conjunto. Dos direcciones r1 y r2 son llamados distintos o no equivalentes, si
r1 no puede ser representado como multiplo positvo de r2 . Alguna otra direccion dek conjunto, cual no
es multiplo de r1 o r2 puede ser representado por λ1 r1 + λ2 r2 , donde λ1 , λ2 > 0. Algún rayo que esta
contenido en el conjunto convexo cuya direccion es extrema es llamado rayo extremo.

Figura 6: Rayos extremos de un poliedro

3. Ejercicios Propuestos
1. Verifique que los siguientes conjuntos son convexos

a) {(x1 , x2 ) ∈ R2 : x21 + x22 ≥ 4}

b) {(x1 , x2 ) ∈ R2 : x21 + x22 ≤ 1, x1 + x2 ≥ −1}

c) {(x1 , x2 ) ∈ R2 : x21 − x2 = 4}

d ) {(x1 , x2 ) ∈ R2 : x1 = 1, |x2 | ≥ 6}

e) {(x1 , x2 , x3 ) ∈ R3 : x1 + 2x2 ≤ 1, 2x1 + x3 ≤ 2}

f ) {(x1 , x2 , x3 ) ∈ R3 : x2 ≤ 2x21 , x1 + x2 + x3 ≤ 6}

7
2. Verifique cual de los siguientes conjuntos son poliedros y determine todos los puntos extremos del
respectivo poliedro. Determine si el poliedro posee algun rayo extremo.

a) {(x1 , x2 ) ∈ R2 : x1 + x2 ≥ 1, x1 + 2x2 ≥ 4, x1 ≥ 0, x2 ≥ 0}

b) {(x1 , x2 ) ∈ R2 : x1 ≤ 2, x1 + x2 ≥ −1, x1 ≥ 0, x2 ≥ 0}

c) {(x1 , x2 ) ∈ R2 : 2x1 + x2 ≤ 4, x1 + 3x2 ≥ 9, x1 ≥ 0, x2 ≥ 0}

d ) {(x1 , x2 ) ∈ R2 : x1 = 1, |x2 | ≤ 6, x1 ≥ 0, x2 ≥ 0}

e) {(x1 , x2 , x3 ) ∈ R3 : x1 + 2x2 ≤ 1, x1 − x3 ≤ 2, x1 ≥ 0, x2 ≥ 0}

f ) {(x1 , x2 , x3 ) ∈ R3 : x3 = |x2 |, x1 ≤ 4, x1 ≥ 0, x2 ≥ 0}

3. Considere los conjuntos

X = {(x1 , y1 ) : 2x1 + x2 ≤ 10, x1 + 2x2 ≤ 12, x1 ≥ 0, x2 ≥ 0}

Y = {(x1 , y1 ) : 2x1 − x2 ≥ −2, −x1 + 2x2 ≤ 1, x1 ≥ 0, x2 ≥ 0}

Indique puntos extremos y las direcciones extremas de los conjuntos X e Y .

4. Represente gráficamente el conjunto {(x1 , x2 ) ∈ R2 : Ax ≤ b; x1 , x2 ≥ 0}, donde A y b son dados

abajo. En cada caso, identifique si se trata de un politopo, un poliedro vacı́o o no.
   
1 0 4
   
a) A = 0 2 , b = 12
  

2 3 18
   
−3 3 9
   
 1 −1 2
b) A =  , b =  
   
1 1 6
  
1 3 6
   
1 1 3
   
c) A = −1 1 , b = −4
  

1 0 −1