Universidad Nacional de Ingeniería
Sede: UNI-Norte
Asignatura:
Investigación de Operaciones I
II Semestre 2008
Conjuntos Convexos
M.C. Ing. Julio Rito Vargas Avilés
Agosto 2008
Conjuntos Convexos
• Concepto de conjunto convexo:
– Es un conjunto que contiene cualquier segmento que une dos
puntos del conjunto.
Ejemplos:
Conjunto A
Conjunto B
Conjunto C
Conjunto D
Conjuntos Convexos
• Los conjuntos convexos son los conjuntos más sencillos
que aparecen de forma natural en la programación
matemática. Un conjunto S es convexo si la línea que
une dos puntos arbitrarios de ese conjunto, pertenece al
conjunto.
• Teorema (teorema de representación de conjuntos
convexos finitos). Si un conjunto convexo está acotado y
cerrado, cualquiera de sus puntos puede escribirse
como una combinación convexa de sus puntos
extremos.
Conjuntos Convexos
Conjuntos Convexos
Poliedro
Definición (poliedro). Un poliedro es la intersección de
un número finito de semiespacios:
Si S está acotado, S es un politopo.
La expresión muestra que el conjunto de todas las
soluciones factibles de un conjunto de desigualdades es
un poliedro.
• El conjunto de restricciones de un PPL define un
poliedro.
Conjuntos Convexos
• Es claro gráficamente que para cualquier par de puntos x, y, el
segmento que los une está totalmente contenido en dicho
conjunto.
• Consideremos un último ejemplo en el plano, sea el conjunto E
conjunto poligonal delimitado por los puntos (
(0,0),(5,0),(0,3),(1,2),(0,0) )
Conjuntos Convexos
• Se puede ver que existen segmentos, como el indicado en la
figura que se sale del conjunto por lo que este conjunto no
sería CONVEXO.
Conjuntos Convexos
•
Así por ejemplo si consideramos el conjunto
•
¿Qué hacemos para dibujar este conjunto?
Usaremos Derive para graficar el conjunto de puntos.
y x
Obsérvese que
es claramente
convexo pues
cualquier par
de puntos que
estén en S3; el
segmento que
los une está
claramente
contenido en
S3.
Conjuntos Convexos
•
•
Qué sucedería si no podemos representar gráficamente el conjunto, como
sucede con conjuntos de dimensión superior a 3?
En esos casos es necesario dar una definición analítica de conjunto
convexo, para lo cual efectuamos la siguiente definición:
CONJUNTO CONVEXO.
Diremos que un subconjunto S  R es convexo si para cualquier
par de puntos
y para cualquier   0 ,1 se cumple
que
está en S, es decir que si llamamos segmento
de extremos
por
• S es convexo si para cualesquiera
,
n
Conjuntos Convexos
• Ejemplo: Estudiar analíticamente si el conjunto
siguiente es convexo. ( x , y )  R 2 ! y  x 
• Para ello consideraremos dos vectores de S3
( x 1 , y 1 ), ( x 2 , y 2 ) Habrá que comprobar si
b ( x 1 , y1 )  (1  b )( x 2 , y 2 )  S 3 para cualquier
valor b  0 ,1
Es decir, tendremos que probar si
( x 2  y 2 )  (1  b ) x 2  (1  b ) y 2
como bx 1  (1  b ) x 2  by 1  (1  b ) y 2
así mismo ( x 1  y 1 )  bx 1  by 1
sumando ambas expresiones la desigualdad, por
tanto S3 es un conjunto convexo.
( x 2  y 2 )  (1  b ) x 2  (1  b ) y 2
Intersección de conjuntos
convexos
Conjunto Convexo
Conjunto Convexo
Ejemplos
• Usaremos el Software matemático Derive
en su versión 6 para ejemplificar gráfica y
analíticamente si un conjunto es convexo.
Descargar

Conjuntos Convexos - MSc. Ing. Julio Rito Vargas Avilés