Apuntes de Programación Lineal Parte I PDF

Preview

Summary

apuntes de programación lineal...

Description

Apuntes de Programación Lineal Bidimensional Parte I

Sistemas de Inecuaciones Lineales Bidimensionales SECCIÓN 1

Inecuaciones lineales con 2 incógnitas Los sistemas de inecuaciones lineales son una debilitación natural de los sistemas de ecuaciones lineales. El origen de su tratamiento se remonta probablemente a los trabajos del matemático francés Jean Baptiste Joseph Fourier (fig. 1).

Fig. 1: Jean B. Joseph Fourier (1768-1830). Tienen aplicaciones interesantes en el modelado de aspectos de optimización económicos. Son muy comunes los problemas de optimización de recursos (ingresos o gastos), que están sujetos a condiciones dadas mediante este tipo de sistemas, en donde intervienen un número muy elevado de incógnitas (variables). En este apartado realizaremos un estudio detallado y técnico de estos sistemas, aunque solamente nos restringiremos al caso de sistemas con dos incógnitas. De ellos hablamos en la siguientes subsecciones. Para definirlos, debemos establecer en primer lugar cuáles son sus "pilares", es decir, debemos concretar qué se entiende por inecuación lineal con dos incógnitas, y cuáles (y cuántas) son sus soluciones.

1.1. Definiciones y soluciones Definición 1. Una inecuación lineal con dos incógnitas x e y, es cualquier inecuación de alguno de los siguientes tipos: ax + by  c, ax + by > c, ax + by  c, ax + by < c, (1) para a, b, c ∈ R, siendo a y b no nulos simultaneamente. También se llamará inecuación lineal bidimensional, asumiendo tácitamente que sus incógnitas se representan con las letras x e y. Definición 2. Una solución de alguna de las inecuaciones dadas en (1), es una pareja de valores (x0 , y0 ) que satisfacen conjuntamente la inecuación considerada. Ejemplo 1. La inecuación: 2x + 3y  5 tiene por solución, por ejemplo, al par (x, y) = (1, 1) . En efecto: 2 · 1 + 3 · 1 = 5  5. Otra solución es, por ejemplo, el par (x, y) = (2, 0) , dado que: 2 · 2 + 3 · 0 = 4  5. 1

Llegados a este punto, nos planteamos la siguiente cuestión inherente a la definición. Pregunta: ¿Cuántas soluciones tiene una ecuación lineal con 2 incógnitas? La respuesta a esta pregunta se encuentra en el importante resultado siguiente. Proposición 1. El conjunto de las soluciones de alguna de las inecuaciones lineales con dos incógnitas siguientes: ax + by  c,

ax + by > c,

ax + by  c,

ax + by < c,

es un semiplano determinado por la recta de ecuación ax + by = c . La recta está contenida en el semiplano solución si y solo si se da la igualdad en la inecuación, es decir, si dicha inecuación es de alguno de los tipos siguientes: ax + by  c, ax + by  c. El semiplano solución se llama recinto o región de soluciones de la inecuación. Demostración. En primer lugar estudiaremos el caso en el que la desigualdad no sea estricta. Es decir, cuando la inecuación sea de alguno de los siguientes tipos: ax + by  c,

ax + by  c.

con a y b no simultáneamente nulos. Consideremos ahora la recta de ecuación ax + by = c. Como los dos coeficientes a y b no son simultáneamente nulos, supondremos en primer lugar que a =  0. Pueden darse en tal caso dos posibilidades, que sea b = 0 o bien b =  0. • Si b = 0, entonces la ecuación se escribe como:

ax = c ⇔ x =

c . a

Esta es la ecuación de una recta vertical que pasa por el punto escribirá forzosamente de alguna de las siguientes formas: x

c  a , 0 del eje de abscisas. La inecuación se

c c o bien x  . a a

Las soluciones de x  ac son justamente todos los puntos del plano cuya primera coordenada sea mayor o igual que ac , y ese conjunto de soluciones es precisamente el semiplano que se encuentra a la derecha del valor x = ac , incluido el propio ac . Un razonamiento similar nos lleva a concluir que los puntos que verifican que x  ac determinan el semiplano que queda a la izquierda de la recta de ecuación x = ac, incluidos los puntos de dicha recta.

• Si b = 0, podemos despejar y obtener de esta manera la ecuación explícita de una recta, a saber:

y=

c − ax c a ⇔ y = − x+ b b b

Consideremos un punto cualquiera (x0 , y0 ) de esta recta. Consideremos también la recta de ecuación x = x0 ∈ R. Es una recta vertical que cortará a la recta de ecuación y = −bax + cb precisamente en el punto de coordenadas (x0 , y0 ) . Las coordenadas de este punto verifican, en particular, que y0 = −bax0 + bc . En tal caso, 2

todo punto (x0 , β ) de la recta de ecuación x = x0 , que se encuentre "por encima" de este punto (es decir, en el sentido del semieje positivo del eje de ordenadas), verificará que y > β , y por tanto que β > −bax0 + bc . De igual manera, todo punto (x0 , β ) que se encuentre "por debajo" del punto (x0 , y0 ) , cumplirá que β < y0 , en cuyo caso es β < − ba x0 + bc.

Hemos razonado que si un punto arbitrario del plano (α , β ) se encuentra por encima de la recta de ecuación si se encontrase por debajo y = − ba x + cb , sus coordenadas verificarán la inecuación y > −bax + bc . Por contra,   de la recta de ecuación y = − ba x + bc (representado en el gráfico ahora por α , β  ), entonces debe satisfacer la inecuación y < − ba x + cb . Finalmente, es obvio que si (α , β ) satisface la ecuación de la recta, entonces también verifica cualquiera de las siguientes inecuaciones: ax + by  c,

ax + by  c.

Nuestros razonamientos prueban que el conjunto de las soluciones de alguna de las inecuaciones anteriores es alguno de los semiplanos delimitados por la recta de ecuación ax + by = c. Si en la ecuación ax + by = c, fuese a = 0 y b = 0, la ecuación podría escribirse como: c by = c ⇔ y = . b Hemos obtenido así la ecuación de una recta horizontal (paralela al eje de abscisas), que pasa por el punto de coordenadas (0, cb ). En este caso, el lector debe reparar sin dificultad que las inecuaciones ax + by  c,

ax + by  c.

para a = 0 pueden escribirse de alguna de las formas siguientes: c c y , y . b b Es inmediato concluir que las soluciones de las anteriores inecuaciones son, geométricamente hablando, los semiplanos superior e inferior, respectivamente, que quedan delimitados por la recta aludida. Obviamente, la recta estará en ambos casos contenida en dichos semiplanos. Ejemplo 2. En el ejemplo 1., la recta 2x + 3y = 5 determina dos semiplanos:

No lo demostramos, pero del gráfico se desprende que el semiplano solución de la inecuación 2x + 3y  5 es el semiplano inferior, con la recta incluída.

3

1.2. ¿Cómo se obtiene el semiplano solución de una inecuación lineal con dos incógnitas? El recinto de soluciones de una inecuación de las consideradas siempre se determinará gráficamente. Seguiremos los siguientes pasos, que facilitarán notablemente su obtención. 1. Representaremos geométricamente la recta de ecuación ax + by = c. Para ello, tomaremos dos soluciones particulares de esta ecuación, representaremos los puntos cuyas coordenadas sean estas soluciones, y trazaremos la única recta que los une. 2. El semiplano solución es alguno de los dos en que queda dividido el plano al dibujar la recta anterior. 3. Para determinar dicho semiplano, estudiaremos si (0, 0) es solución de la inecuación. (a) Si (0, 0) es solución, el semiplano que lo contiene es el semiplano solución. (b) Si (0, 0) no es solución, el semiplano que NO lo contiene, será el semiplano solución. (c) Si (0, 0) estuviese en la recta dibujada anteriormente, buscaremos otro punto de la forma (c, 0), o bien (0, c) , y comprobaremos si es solución o no. Si lo es, el semiplano solución será el que lo contiene, en caso contrario, será el otro semiplano solución. 4. Si se da la igualdad en la inecuación, la recta está contenida en el semiplano solución de la inecuación. En caso contrario, no lo estará, y dicha recta se representará con un trazo discontinuo. Ejemplo 3. Representar geométricamente el recinto solución de la inecuación 3x − y  4. Solución. En primer lugar, obtenemos dos soluciones particulares de la ecuación 3x − y = 4. x y

1 −1

2 2

A continuación representamos las soluciones obtenidas, que son (1, −1) y (2, 2), y la recta que las contiene:

Ahora, vemos si (0, 0) es solución de la inecuación. Como: 3 · 0 − 0 = 0  4, razonamos que (0, 0) es solución de la inecuación, y por tanto el semiplano solución es el que lo contiene, y como se da la igualdad en la inecuación, razonamos que la recta 3x − y = 4 está contenida en la región de soluciones 4

de la inecuación:

 Ejemplo 4. Representar gráficamente los semiplanos solución correspondientes a las inecuaciones: (a) x  2

(c) 2x + y < 1

(b) y  3

Solución. (a) La inecuación x  2 puede verse como una inecuación lineal con dos incógnitas, escribiendo: x  2 ⇔ x + 0 · y  2. En este caso, se trata de determinar los puntos del plano cuya abscisa es mayor o igual que 2. El semiplano solución se obtiene a partir de la recta de ecuación x = 2. Gráficamente:

(b) Razonando de manera similar, la inecuación y  3 puede mirarse como una inecuación lineal con dos incógnitas, de la forma: y  3 ⇔ 0 · x + y  3. El semiplano solución será aquél determinado por todos los puntos cuya ordenada sea menor o igual que 3, semiplano que vendrá dado por la recta de ecuación y = 3. Gráficamente:

5

(c) Representamos en primer lugar la recta de ecuación 2x + y = 1. Soluciones particulares de esta ecuación son: x y

0 1

1 −1

Como (0, 0) es claramente solución de la inecuación 2x + y < 1, determinamos que el semiplano solución de la inecuación es, gráficamente, el siguiente:

Un detalle: la recta de ecuación 2x + y = 1 ha sido representada con una línea discontinua. Ello es debido a que la desigualdad establecida en la inecuación es estricta, lo que significa que ningún punto de la recta frontera aporta solución alguna del sistema. Debemos destacar que cada semiplano solución se resaltará habitualmente utilizando algún coloreado de la región, o bien una trama que la destaque. Los coloreados resultan mucho más atractivos que las tramas, de modo que se recomienda su uso al lector.  SECCIÓN 2

Conjuntos convexos en el plano Para dar el salto al estudio de los sistemas de inecuaciones bidimensionales, es necesario conocer algunos aspectos técnicos de ciertas regiones relevantes del plano. Definición 3. Una región del plano se dice que es convexa, si para cualesquiera dos puntos pertenecientes a la región, el segmento que los une también pertenece a dicha región. Consideraremos que el conjunto vacío ∅ es un conjunto convexo en el sentido definido. Por ejemplo, un polígono convexo, determina una región convexa. Sin embargo, un polígono cóncavo no puede determinar, en modo alguno, una región convexa. Mostramos dos ejemplos gráficos que ayudarán a aclarar estas afirmaciones:

Región convexa

Región no convexa

En el primer caso, dos puntos cualesquiera del recinto pueden unirse por un segmento que cae dentro de dicha región. En el segundo caso, existen puntos en los que el segmento que los une se "sale" fuera de la región. Las regiones convexas del plano satisfacen un hecho importante que se enuncia seguidamente. Proposición 2. Sean C1 y C2 dos regiones convexas del plano. Entonces, la intersección C1 ∩ C2 es también una región convexa del plano. 6

La demostración de este hecho es inmediata, y se propone como ejercicio. Como consecuencia, se tiene que: Corolario 1. Sean C1 , C2 ,

···

, Cn regiones convexas del plano. La intersección

n 

Ci es también una región

i=1

convexa del plano.

Fig. 2: La intersección de regiones convexas del plano, es otra región convexa.

2.1. Inecuaciones bidimensionales y convexidad El conjunto de las soluciones de una ecuación bidimensional de alguno de los siguientes tipos: ax + by  c ax + by > c ax + by  c ax + by < c es un semiplano, como ya tuvimos ocasión de estudiar en §1.1. Resaltemos que un semiplano (con o sin la recta que lo delimita, según si la inecuación es estricta o no) es claramente un conjunto convexo del plano. Esto es lo que afirma el siguiente resultado. Proposición 3. El semiplano solución de una inecuación lineal con dos incógnitas, es un conjunto convexo del plano. Demostración. Para probar la afirmación anterior, supondremos, sin pérdida de generalidad, que la inecuación puede escribirse de la forma: ax + by  c, para ciertos a, b, c reales (a y b no simultáneamente nulos). Si a y b son nulos, entonces el conjunto solución o es ∅, o es todo el plano, que son conjuntos convexos en cualquier caso. De igual forma, si la desigualdad fuese estricta, se razona de manera análoga a como lo haremos en lo sucesivo. En primer lugar, recordemos un hecho esencial, relativo a la ecuación de la recta que pasa por dos puntos. La ecuación vectorial de la recta, que pasa por los puntos P y Q del plano, puede escribirse como: X

= P+λ

·

−→ PQ, λ ∈ R,

(3)

donde X es un punto de la recta. Utilizando coordenadas cartesianas, la ecuación (3) se podría escribir, suponiendo que P = (x1 , y1 ) y Q = (x2 , y2 ) , como: ( x , y) = (x1 , y1 ) + λ · ( x2 − x1 , y2 − y1 )

es decir, (x, y) = (x1 + λ (x2 − x1 ) , y1 + λ (y2 − y1 )) = (1 − λ ) · (x1 , y1 ) + λ · (x2 , y2 ) .

Es inmediato comprobar que si λ ∈ [0, 1] , las coordenadas de X = (x, y) se corresponden con las de algún punto del segmento que une los puntos P y Q. Es decir, todo punto del segmento que une los puntos P y Q tiene por coordenadas: (x, y) = (1 − λ ) · (x1 , y1 ) + λ · (x2 , y2 ) , λ ∈ [0, 1] . 7

Fig. 3: Ecuación vectorial de la recta. Sólo si λ ∈ [0, 1] se obtienen puntos del segmento que une P y Q. De hecho, si λ = 0 se obtiene el punto P, y el punto Q se obtendrá para λ = 1. Supongamos que P = (x1 , y1 ) y Q = (x2 , y2 ) son soluciones de la inecuación ax + by  c. Esto significa, en particular, que: ax1 + by1  c ý ax2 + by2  c. Veamos que un punto genérico (x0 , y0 ) del segmento que une los puntos P y Q, también satisface la inecuación de partida, y en consecuencia, todo el segmento que une dichos puntos también se encontrará en el semiplano solución de la inecuación. En efecto, por lo razonado anteriormente, deberá existir algún λ 0 ∈ [0, 1] tal que: ( x0 , y0 ) = (1 − λ 0 ) · ( x1 , y1 ) + λ 0 · ( x2 , y2 ) .

Operando, e igualando componente a componente, x0

=

( 1 − λ 0 ) · x1 + λ 0 · x2 ,

y0

=

( 1 − λ 0 ) · y1 + λ 0 · y2 .

En tal caso, ax0 + by0

=

a [(1 − λ 0 ) · x1 + λ 0 · x2 ] + b [(1 − λ 0 ) · y1 + λ 0 · y2 ]

=

(1 − λ 0 ) · (ax1 + by1 ) + λ 0 · (ax2 + by2 )



(1 − λ 0 ) · c + λ 0 · c

=

c

lo que prueba que ax0 + by0  c, y por tanto que (x0 , y0 ) también es solución de la inecuación ax + by  c. Este hecho demuestra que todo el segmento que une los puntos P y Q está determinado por soluciones de dicha inecuación, y por tanto, adicionalmente, hemos probado que el semiplano solución es convexo. SECCIÓN 3

Sistemas de inecuaciones bidimensionales Siguiendo una inercia natural, similar a la utilizada con los sistemas de ecuaciones, procederemos en este apartado a definir los sistemas de inecuaciones bidimensionales, y sus correspondientes soluciones. Detallaremos también cómo es el conjunto de todas las soluciones de un tal sistema. Definición 4. Un sistema de inecuaciones lineales (bidimensional) con dos incógnitas x e y, es cualquier conjunto de n inecuaciones lineales con dos incógnitas, n  1. Podemos suponer que es de la forma: ⎧ ⎪ ⎪ a1 x + b1 y  c 1 ⎪ ⎨ a2 x + b2 y  c 2 (4) .. ⎪ ⎪ . ⎪ ⎩ an x + bn y  c n 8

donde ai , bi , ci ∈ R, para cada i = 1, 2, ..., n. Cada relación  puede ser estricta o no. Obsérvese que cada relación  puede escribirse también como , intercambiando los miembros de cada inecuación. Por solución del sistema (4) se entenderá cualquier pareja de números reales (x0 , y0 ) , que satisface todas las inecuaciones del sistema. Llamaremos recinto o región de soluciones del sistema, al conjunto de todas las soluciones de dicho sistema.

Ejemplo 5. El par (x, y) = (1, 2) es claramente solución del sistema: ⎧ ⎨ x1 y3 ⎩ xy

De igual forma, el par (x, y) = (1.3, 2.7) es también solución del mencionado sistema. Teniendo en cuenta la Proposición 2. y su correspondiente corolario posterior, podemos asegurar que el conjunto o recinto solución de un sistema bidimensional (4) es un conjunto convexo.

Proposición 4. El recinto solución del sistema (4) es una región convexa del plano. Demostración. La prueba es inmediata pues, como sabemos por el Corolario 1., la intersección de un conjunto finito de regiones convexas del plano, es también convexa. De hecho, el recinto de soluciones, salvo que sea ∅, es una región poligonal que puede ser limitada o no, en un sentido que definiremos más adelante. En este orden de ideas, es pertinente introducir alguna notación relativa al recinto de soluciones del sistema (4). Definición 5. Sea R el recinto de soluciones del sistema (4). Entonces R es una región poligonal, y por tanto llamaremos vértices a los vértices del polígono obtenido, y llamaremos aristas a los segmentos, o semirrectas, que lo delimitan. Por ejemplo, los vértices y las aristas de una región convexa que podría haberse obtenido como solución del sistema (4), se detallan en la figura 4.

Fig. 4: Relación de vértices y aristas de un ejemplo de recinto de soluciones de un cierto sistema (4).

3.1. Representación del recinto de soluciones Habitualmente, el sistema (4) tiene infinitas soluciones, y al conjunto de todas ellas lo hemos llamado región o recinto de soluciones del sistema. Debemos dejar claro que, en lo sucesivo, tendrá especial interés para nosotros representar geométricamente dicho recinto. Como veremos, esta cuestión conlleva un procedimiento gráfico que al utilizar elementos del plano, es bastante asequible de implementar. Antes de determinar las pautas para efectuar la representación de un sistema de inecuaciones lineales, vamos a mostrar algunos ejemplos de recintos de soluciones de algunos sistemas particulares. 9

Ejemplo 6. Representar gráficamente los sistemas bidimensionales siguientes: ⎧ ⎧ ⎨ 2x + y  1 ⎨ x1 y3 , x+y  3 ⎩ ⎩ x − 2y > 1 xy

Solución. Mostramos, obviando los detalles, las representaciones de los sistemas anteriores:

⎧ ⎨ 2x + y  1 x+y  3 ⎩ x − 2y > 1

⎧ ⎨ x1 y3 ⎩ xy

El primer sistema tiene por región de soluciones un recinto acotado, entendiendo con esto, a falta de una definición más rigurosa que será detallada posteriormente, que la región no se extiende indefinidamente, cuestión que sí le sucede a la región solución del segundo sistema (es una región no acotada). La primera región es un triángulo, cuyas aristas pertenecen a ella. En el segundo ejemplo, la región tiene dos aristas infinitas que pertenecen a la región, y por contra tiene una arista (representada en línea discontinua), que no pertenece al recinto de soluciones del sistema.  En relación con lo comentado en el ejemplo anterior, establecemos la idea de acotación del recinto solución del sistema. Definición 6. Sea R el recinto solución del sistema lineal bidimensional (4). Diremos que R es acotado, si puede inscribirse totalmente dentro de alguna circunferencia de radio r > 0.

Fig. 5: Una región R acotada, puede inscribirse totalmente dentro de alguna circunferencia en el plano.

3.1.1. Pautas Para representar geométricamente el recinto de soluciones del sistema (4), se recomienda realizar los pasos siguientes: 10

1. Representaremos cada semiplano solución de todas y cada una de las inecuaciones del sistema.

(a) Cada semiplano solución será indicado con ...