programación lineal

Clase: Intro a Programación lineal

Temas
•  Repaso de álgebra lineal
•  Intro a Programación Lineal
•  Geometría Poliédrica

Intro a la Programación Lineal
•  En notación matricial:

Ø  Formato estándar:
min Z = c1 x1 + c2 x2 + ... + cn xn
s.a.

min Z = cT x

a11 x1 + a12 x2 + ... + a1n xn ≤ b1

s.a.

a21 x1 + a22 x2 + ... + a2 n xn ≤ b2

am1 x1 + am 2 x2 + ... +amn xn ≤ bm
x j ≥ 0, ∀j
n

min Z =

∑c

j

xj

j =1
n

s.a.

∑a

ij

x j ≤ bi

j =1

x j ≥ 0,

i = 1,..., m

j = 1,..., n

≡

A x ≤b
x≥0

⎡ x1 ⎤
min Z = [c1 ... cn ]⎢  ⎥
⎢ ⎥
⎢ xn ⎥
⎣ ⎦
⎡ a11 ... a1n ⎤ ⎡ x1 ⎤ ⎡ b1 ⎤
⎢    ⎥ ⎢  ⎥ ≤ ⎢  ⎥
s.a.
⎢
⎥ ⎢ ⎥ ⎢ ⎥
⎢am1 … amn ⎥ ⎢ xn ⎥ ⎢bm ⎥
⎣
⎦ ⎣ ⎦ ⎣ ⎦
⎡ x1 ⎤ ⎡0⎤⎢  ⎥ ≥ ⎢  ⎥
⎢ ⎥ ⎢ ⎥
⎢ xn ⎥ ⎢0⎥
⎣ ⎦ ⎣ ⎦

Terminología
Solución no factible
(infactible)

( x1 , x2 ) = (4,6)
Solución factible

( x1 , x2 ) = (1,1)

• 
• 
• 
• 
• 
• 
• 

Región factible
Solución óptima
Múltiples óptimos
Solución no óptima
Valor óptimo más favorable de Z
Problema no acotado
Problema infactible

Solución factible
= ( x1 , x2 ) o vértice opunto
extremo

Casos Patológicos
1. Problema Infactible
Ejemplo:

x2

x1 + x2 ≤ 1
x1 + x2 ≥ 3
x1 + x2 ≤ 5

x1
x2

x1 + 2 x2 ≥ 6

Ejemplo:

x2 ≤ 3
4 x1 + 2 x2 ≥ 11
x1

≤1

− 3x1 + 2 x2 ≥ 0

x1

Casos Patológicos
2. Región factible no acotada pero Valor óptimo acotado

Región Factible

Solución óptima

Z

Casos Patológicos
3. Problema no acotado

RegiónFactible

Z

Casos Patológicos
4. Múltiples Soluciones
Soluciones óptimas

A
Región
factible

B

x1
Soluciones: combinación convexa de los puntos A y B

{ A + (1

)B :

2 [0, 1]}

Algebra Lineal
Ø vectores, matrices, suma y producto de vectores y
matrices.
Ø Combinación Lineal: b es combinación lineal de los
vectores {a1,…,am} si existen λ1,…,λm tales que:
m
X
b=ai
i
i=1

§  Combinación convexa: si adicionalmente

m
X

i

=1

i=1

Ø Sub-espacio vectorial generado por {a1,…,an} :
m
X
⌦ 1
↵
a , . . . am = {b 2 Rn : b =
ai , 8 i 2 R}
i
i=1

es decir, los vectores que se escriben como combinación
lineal de a1,…,am

Independencia Lineal y Bases
Ø Un conjunto de vectores {a1,…,am} se dice linealmente
independiente si
m
Xi=1

ia

i

= 0 =)

i

= 0 8i = 1 . . . m

es decir, que ningún vector del conjunto se puede escribir como
combinación de los otros vectores del conjunto.

Ø Una base de un espacio vectorial V es un conjunto
{v1,…,vm}tal que
§  Todo vector en V se puede escribir como combinaciones
lineales de {v1,…,vm}.
§  El conjunto {v1,…,vm} es linealmente independiente.

Sistemas deEcuaciones
Ax = b ,
Ø Dos visiones:

m
X
i=1

Ax = b

a·,i xi = b

§  Cada fila es un hiperplano. Las soluciones del sistema son la
elementos en la intersección de los hiperplanos.
§  b tiene que escribirse como combinación lineal de las columnas
de A, y x son los ponderadores que lo permiten.

Ø Si A es de rango completo (filas/columnas son l.i.),
entonces A es invertible y elsistema tiene solución única.
§  ¿Y si no es de rango completo?

Sistemas de Ecuaciones

Ax = b

Ø Caso más filas que columnas:
§  O las restricciones hacen al problema infactible, o hay
restricciones redundantes.

Ø Caso más columnas que filas (l.i.):
§  Infinitas soluciones (¡todo un espacio vectorial!)
§  ¿qué solución es mejor? ¡Depende de mi “objetivo”!

Ø En general,asumimos que el conjunto de restricciones
(filas) es linealmente independiente.
§  Si hay una restricción redundante, eliminarla.

min f (x)

Programación Lineal
Ø Forma estándar

s.a.

Ø Forma normal

min cx

min cx

Ax = b

x2⌦

Ax  b

x

0

x

0

Observación: Un problema en forma normal se puede
convertir en uno en forma estándar

Transformación forma...