Estadísta

Tema 1. Introducci´n y Preliminares
o

Aspectos geom´tricos de los programas matem´ticos
e
a

4. Aspectos geom´tricos de los programas matem´ticos
e
a
Definici´n
o
Dado f : Rn → R, se llama curva de nivel k ∈ R de la funci´n al subconjunto Ck ⊂ Rn
o
definido por:
Ck = {(x1 , x2 , . . . , xn ) ∈ Rn : f (x1 , x2 , . . . , xn ) = k}.

Es decir, que la curva de nivel k de f es elconjunto de puntos del espacio Rn en los
que f toma el valor constante k. El conjunto formado por las distintas curvas de nivel de
o
f obtenidas al variar k se llama mapa de curvas de nivel de la funci´n.
La resoluci´n geom´trica de un programa matem´tico con dos o tres variables consiste
o
e
a
en determinar por medio de una representaci´n gr´fica el o los puntos del conjunto
o
a
factiblesituados sobre la curva de menor y de mayor nivel, que dar´n lugar,
a
respectivamente, al m´
ınimo y al m´ximo globales de la funci´n objetivo.
a
o

Roc´ Raya (Dpto. Estad´
ıo
ıstica)

Programaci´n Matem´tica
o
a

Curso 2011/2012

20 / 30

Tema 1. Introducci´n y Preliminares
o

Aspectos geom´tricos de los programas matem´ticos
e
a

Las fases del proceso de soluci´n gr´ficoson:
o
a
1

Dibujar un sistema de coordenadas cartesianas en que las variables de decisi´n
o
est´n representadas por los ejes.
e

2

Dibujar en el sistema coordenado las restricciones del problema (incluyendo las de
no negatividad). Para ello notar que si una restricci´n es una desigualdad, define
o
una regi´n (indicada con una flecha) limitada por la l´
o
ınea recta (dosdimensiones) o
plano (tres dimensiones) que se obtiene al considerar la restricci´n como una
o
igualdad. Si la restricci´n es una igualdad, se dibuja como una l´
o
ınea recta (dos
dimensiones) o un plano (tres dimensiones). La intersecci´n de todas las regiones
o
o
determina la regi´n factible o espacio de soluciones (que es un conjunto convexo, es
decir, que para cualquier par de puntos delconjunto el segmento de l´
ınea que los
une est´ contenido en ´l). Si esta regi´n es no vac´ ir a la fase siguiente. En otro
a
e
o
ıa,
caso, no existe soluci´n que satisfaga (simult´neamente) todas las restricciones y el
o
a
problema se dice infactible.

3

Determinar los puntos extremos (puntos que no est´n situados en segmentos de
a
l´
ınea que unen otros dos puntos del conjuntoconvexo) del espacio de soluciones.
Evaluar la funci´n objetivo en esos puntos y aqu´l o aqu´llos que maximicen (o
o
e
e
minimicen) el objetivo, corresponden a las soluciones optimas del problema.
´

Roc´ Raya (Dpto. Estad´
ıo
ıstica)

Programaci´n Matem´tica
o
a

Curso 2011/2012

21 / 30

Tema 1. Introducci´n y Preliminares
o

Aspectos geom´tricos de los programas matem´ticose
a

El proceso para resolverlo gr´ficamente si la funci´n objetivo es lineal es el siguiente:
a
o
1

Comprobamos que la funci´n objetivo es lineal. En caso contrario no podemos
o
aplicar el m´todo que vamos a ver.
e

2

Representamos el conjunto de oportunidades.

3

Calculamos el gradiente de la funci´n objetivo y lo representamos gr´ficamente.
o
a

4

Representamos lacurva de nivel f = 0 de la funci´n objetivo. Si la funci´n objetivo
o
o
es lineal ser´ siempre la recta perpendicular al vector gradiente.
a

5

Si la curva de nivel no pasara por el conjunto de oportunidades la movemos
paralelamente a s´ misma hasta que pase por S. As´ obtenemos otra curva de nivel
ı
ı
v´lida para alguna soluci´n factible.
a
o

6

Ahora recordamos que el gradientede la funci´n objetivo indica hacia d´nde
o
o
aumenta la funci´n, mientras que la direcci´n contraria indica hacia d´nde
o
o
o
disminuye. Por lo tanto, si estamos maximizando desplazaremos la curva de nivel
paralelamente a s´ misma en la direcci´n del gradiente. El ultimo punto de S que
ı
o
´
toquemos ser´ la soluci´n optima. Si el problema es de minimizar la unica
a
o ´
´...