Programación Lineal

Julio Yarasca

CEPREUNI

13 de diciembre de 2015

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 1 / 21

Introducción

Figura: George Dantzing

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 2 / 21

Conjunto Convexo

Conjunto Convexo
Un conjunto C ⊂ R2 es convexo si para cada par de puntos del conjunto, el
segmento que los une esta incluido en el conjunto.

1 C es convexo si dados dos puntos cualesquiera x y x en C , entonces λx + (1 − λ)x ∈ C

1 2 1 2
para todo λ ∈ [0, 1].
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 3 / 21
Conjunto Convexo

Conjunto Convexo
Un conjunto C ⊂ R2 es convexo si para cada par de puntos del conjunto, el
segmento que los une esta incluido en el conjunto.

C x2
S

x2

x1
x1

Conjunto convexo Conjunto no convexo

1 C es convexo si dados dos puntos cualesquiera x y x en C , entonces λx + (1 − λ)x ∈ C

1 2 1 2
para todo λ ∈ [0, 1].
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 3 / 21
Propiedades de los conjuntos convexos

1 Si S, T son conjuntos convexos, entonces S ∩ T es un conjunto convexo.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 4 / 21

Propiedades de los conjuntos convexos

1 Si S, T son conjuntos convexos, entonces S ∩ T es un conjunto convexo.

2 Si S1 , S2 , · · · , Sn son conjuntos convexos, entonces
n
\
Si := S1 ∩ S2 ∩ · · · ∩ Sn
i=1

es un conjunto convexo.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 4 / 21

Unión?
Veamos que la unión de dos conjuntos convexos no necesariamente es un conjunto
convexo, sean los conjuntos A y B

A B

claramente convexos pero tenemos que la unión A ∪ B , no es un conjunto convexo.

A∪B

x1 x2

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 5 / 21

Ejemplos

Ejemplo: Semiplano
El siguiente conjunto es un conjunto convexo

S = (x, y ) ∈ R2 / ax + by ≤ c


Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 6 / 21

Ejemplos

Ejemplo: Semiplano
El siguiente conjunto es un conjunto convexo

S = (x, y ) ∈ R2 / ax + by ≤ c


ax + by ≤ c

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 6 / 21

Ejemplo: Poliedro
Sea U el conjunto solución del sistema de inecuaciones
≤ 100

 x +y
 + 4y ≤ 160

x


x + 2y ≤ 110
x ≥ 0



≥ 0

y


es un conjunto convexo.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 7 / 21

Problema de Programación lineal

Un problema de programación lineal PPL (en dos variables) consiste en maximizar

o minimizar (es decir, optimizar ) una función f (llamada función objetivo ) de la
forma
z = f (x, y ) = ax + by
sujeta a las restricciones (s.a )


 a1 x + b1 y ≤ c1
 a2 x + b2 y ≤ c2

(1) ..


 .
an x + bn y ≤ cn


y
x ≥0

(2)
y ≥0
llamadas restricciones de vínculo y de no negatividad, respectivamente, al
conjunto solución de (1) y (2) se le conoce como región admisible.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 8 / 21

Ejemplo
Sea el PPL
máx f (x, y ) = 4x + y
s.a
x +y ≤ 6
−x + 2y ≤ 8
x ≥ 0
y ≥ 0
Graque la región admisible.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 9 / 21

Ejemplo
Sea el PPL
máx f (x, y ) = 4x + y
s.a
x +y ≤ 6
−x + 2y ≤ 8
x ≥ 0
y ≥ 0
Graque la región admisible.

4 14


3, 3

(0, 6)

región admisible

(6, 0)
(0, 0)

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 9 / 21

Puntos del conjunto admisible

Una solución factible o admisible de un PPL, es todo par ordenado (x, y )

que pertence a la región admisible.
Una solución óptima de un PPL, es una solución factible que optimiza la
función objetivo.
Si (x0 , y0 ) es una solución óptima de un PPL, f (x0 , y0 ) es llamado valor
óptimo.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 10 / 21

Teorema

Teorema Fundamental de la Programación Lineal

Si un PPL tiene valor óptimo, tal valor es alcanzado por lo menos en un vértice de
la región admisible; y si este valor óptimo se alcanza en dos vértices A, B tal valor
se logra en todo el segmento de extremos A y B .

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 11 / 21

Teorema

Teorema Fundamental de la Programación Lineal

Si un PPL tiene valor óptimo, tal valor es alcanzado por lo menos en un vértice de
la región admisible; y si este valor óptimo se alcanza en dos vértices A, B tal valor
se logra en todo el segmento de extremos A y B .

Este teorema nos brinda una herramienta para poder resolver los problemas de
programación lineal.
Método Analítico
Consiste basicamente de dos pasos
1 Gracar la región admisible y encontrar los vertices.
2 Evaluar la función objetivo en cada vertice y encontrar cual maximiza o
minimiza la función.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 11 / 21

Ejemplo
Sea el PPL
máx f (x, y ) = 4x + y
s.a
x + y ≤ 100
x + 4y ≤ 160
x + 2y ≤ 110
x ≥ 0, y ≥ 0

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 12 / 21

Ejemplo
Sea el PPL
máx f (x, y ) = 4x + y
s.a
x + y ≤ 100
x + 4y ≤ 160
x + 2y ≤ 110
x ≥ 0, y ≥ 0

La región admisible es

vértices (x, y) f(x,y)=4x+y

(0; 0) 0
(0, 40) (0; 40) 40
(60; 25) 265
(60, 25) (90; 10) 360
(100; 0) 400
Region Admisible
(90, 10)

(0, 0) (100, 0)

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 12 / 21

Ejemplo
Sea el PPL
máx f (x, y ) = 4x + y
s.a
x + y ≤ 100
x + 4y ≤ 160
x + 2y ≤ 110
x ≥ 0, y ≥ 0

La región admisible es

vértices (x, y) f(x,y)=4x+y

(0; 0) 0
(0, 40) (0; 40) 40
(60; 25) 265
(60, 25) (90; 10) 360
(100; 0) 400
Region Admisible
(90, 10)

(0, 0) (100, 0)

Por lo tanto el máximo se obtiene en el punto (100, 0)

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 12 / 21

Región acotada

Región admisible acotada

Una región admisible es acotada si alrededor del origen existe una cirfunferencia
que lo contenga.

Sea el PPL

máx f (x, y ) = 4x + y 
4 14

,
s.a 3 3

x +y ≤ 6 (0, 6)
−x + 2y ≤ 8
x ≥ 0
y ≥ 0
Región admisible acotada
(6, 0)
(0, 0)

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 13 / 21

Sea el PPL
máx f (x, y ) = 4x + y
s.a
4y − x ≤ 32
−x + 2y ≤ 12
x ≥ 0
y ≥ 0

(8,10)

(0,6) Región admisible no acotada

(0,0)

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 14 / 21

Teorema

Teorema de representación
En un PPL si la región admisible es no vacía entonces el conjunto de sus vértices
es un conjunto no vacío y nito.

Como cololario tenemos

1 En un PPL si la región admisible es acotada y no vacía, entonces el problema
tiene solución.
Propiedad
Sobre cualquier región admisible tenemos

máximo ax + by = −mínimo − (ax + by )

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 15 / 21

Método geométrico

Sea el problema máx F (x, y ) = ax + by sobre cualquier región admisible.

1 Gracamos la región admisible.
2 Gracamos la rectas ax + by = k y las movemos en la direción (a, b) tanto
como sea posible .
En caso de un problema de minimización las rectas las movemos tanto como sea
posible en la direción (−a, −b), es decir en la direción opuesta.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 16 / 21

Ejemplo
Sea el problema
máx f (x, y ) = x + 2y
s.a
x − 2y ≥ −10
x + 4y ≤ 10
x ≥0
y ≥0

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 17 / 21

Ejemplo
Sea el problema
máx f (x, y ) = x + 2y
s.a
x − 2y ≥ −10
x + 4y ≤ 10
x ≥0
y ≥0
Entonces la región admisible es:

(2, 6)
(0, 5)

región admisible
(5, 0)
(0, 0)
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 17 / 21
Gracamos las rectas x + 2y = z y la movemos hasta en la direción2 (1, 2) tanto
como sea posible.

(2, 6) (1, 2)

(0, 5)

(5, 0)
(0, 0)

Por lo tanto la solución es el punto (2, 6)

2 En el caso de un problema de minimización es en la dirección opuesta.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 18 / 21
Otra forma

1 Gracamos la región admisible.

2 Gracamos la rectas con dirección (−b, a) que pasan por los puntos
extremos3 .
3 Se observa en qué vértice la función objetivo se hace máxima (o mínima) solo
teniendo en cuenta cuál de las rectas corta en un punto mayor (o menor) al
eje y.

3 Es decir, sea (x0 , y0 ) una punto extremo, gracamos la recta ax + by = ax0 + byo
Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 19 / 21
Ejemplo
En el problema anterior
máx f (x, y ) = x + 2y
s.a
x − 2y ≥ −10
x + 4y ≤ 10
x ≥0
y ≥0

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 20 / 21

Ejemplo
En el problema anterior
máx f (x, y ) = x + 2y
s.a
x − 2y ≥ −10
x + 4y ≤ 10
x ≥0
y ≥0

(0, 7)
(2, 6)

(0, 5) Por lo tanto

la solución es (2, 6)

(0, 2,5)
(−2, 1)

(5, 0)
(0, 0)

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 20 / 21

Bibliografía
1 Programación y ujos de redes, Mokhtar Bazaraa.
2 Que es la programación lineal, Barsov.
3 Técnicas de Cálculo para Sistemas de Ecuaciones, Programación Lineal y
Programación Entera, Jose Luis de la Fuente O'Connor.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 21 / 21

Bibliografía
1 Programación y ujos de redes, Mokhtar Bazaraa.
2 Que es la programación lineal, Barsov.
3 Técnicas de Cálculo para Sistemas de Ecuaciones, Programación Lineal y
Programación Entera, Jose Luis de la Fuente O'Connor.

Gracias por su tiempo.

Julio Yarasca (CEPREUNI) Programación Lineal 13 de diciembre de 2015 21 / 21