Programacion lineal

Cap´ıtulo 8

PROGRAMACI´ON LINEAL

8.1. Introducci´on

La programaci´on lineal es una t´ecnica matem´atica relativamente reciente (siglo XX), que consiste

en una serie de m´etodos y procedimientos que permiten resolver problemas de optimizaci´on en el

´ambito, sobre todo, de las Ciencias Sociales.

Nos centraremos en este tema en aquellos problemas simples de programaci´on lineal, los que tienen

s´olamente 2 variables, problemas bidimensionales.

Para sistemas de m´as variables, el procedimiento no es tan sencillo y se resuelven por el llamado

m´etodo Simplex (ideado por G.B.Danzig, matem´atico estadounidense en 1951).

Recientemente (1984) el matem´atico indio establecido en Estados Unidos, Narenda Karmarkar,

ha encontrado un algoritmo, llamado algoritmo de Karmarkar, que es m´as r´apido que el m´etodo

simplex en ciertos casos. Los problemas de este tipo, en el que intervienen gran n´umero de variables,

se implementan en ordenadores.

8.2. Inecuaciones lineales con 2 variables

Una inecuaci´on lineal con 2 variables es una expresi´on de la forma:

ax + by ≤ c

(donde el s´ımbolo ≤ puede ser tambi´en ≥ , < o bien >), donde a, b y c son n´umeros reales y x e y las

inc´ognitas.

Para resolver estas inecuaciones, se recordar´a de otros cursos, hay que representar gr´aficamente en

el plano la recta dada por la correspondiente ecuaci´on lineal y marcar una de las dos regiones en que

dicha recta divide al plano.

Ejemplo: Si queremos resolver la inecuaci´on: 2x + 3y ≥ −3, representamos en primer lugar la recta

2x +3y = −3:

127

CAP´ ITULO 8. PROGRAMACI´ ON LINEAL 128

La recta divide al plano en dos regiones, una de las cuales es la soluci´on de la inecuaci´on. Para

saber qu´e parte es, hay dos procedimientos:

1. Se despeja la y de la inecuaci´on, poniendo cuidado en que si en una inecuaci´on multiplicamos o

dividimos por un n´umero negativo, la desigualdad cambia de sentido.

En este caso tend´ıamos que:

y ≥

−3 − 2x

3

Observando el dibujo vemos que la recta divide al eje de ordenadas (y) en dos partes.

La soluci´on de la inecuaci´on ser´a aquella parte en la que la y sea mayor que la recta, es decir, la

parte superior.

Figura 8.1: Soluci´on de la inecuaci´on lineal

2. Se toma un punto cualquiera que no pertenezca a la recta, por ejemplo el (1,2).

Para que dicho punto sea soluci´on, se tendr´a que cumplir la desigualdad, por lo que sustituimos

en la inecuaci´on inicial el (1,2):

2 · 1 +3 · 2 ≥ −3, es decir, 8 ≥ −3.

Como esta ´ultima desigualdad es evidentemente cierta, concluimos que el (1,2) es soluci´on y

por tanto el semiplano que contiene al (1,2) es la soluci´on, es decir el semiplano superior, como

hab´ıamos obtenido antes.

Cualquiera de los procedimientos es v´alido si se realiza con correcci´on.

8.3. Sistemas de inecuaciones lineales con dos variables

Un sistema de inecuaciones lineales, por tanto, es un conjunto de inecuaciones del tipo anterior, y

resolverlo consistir´a en resolver gr´aficamente cada inecuaci´on (como en el caso anterior), representar

la soluci´on en un mismo gr´afico y la soluci´on total ser´a la parte com´un a todas las soluciones.

CAP´ ITULO 8. PROGRAMACI´ ON LINEAL 129

Ejemplo: Resolver el sistema de inecuaciones siguiente:





2x +3y ≥ −3

2x − y − 9 ≤ 0

2x − 5y − 5 ≥ 0

Si representamos las rectas: 





2x+ 3y = −3 (recta r)

2x − y − 9 = 0 (recta s)

2x − 5y − 5 = 0 (recta t)

Figura 8.2: Soluci´on del sistema de inecuaciones lineales

El tri´angulo rayado es la soluci´on del sistema.

Adem´as, para los problemas de programaci´on lineal es necesario el c´alculo de los v´ertices de la

regi´on soluci´on. Es sencillo su c´alculo, pues se reduce a resolver sistemas de ecuaciones lineales son

dos inc´ognitas, que provienen de igualar las ecuaciones de las rectas correspondientes.

Por ejemplo, en este caso, si queremos el punto intersecci´on de las rectas r y t tendremos que

resolver el sistema formado por:



2x +3y = −3

2x − y − 9 = 0

=⇒



−2x − 3y = 3

2x − y − 9 = 0

Sumando −4y = 12 =⇒ y = −3.

Y sustituyendo que da 2x +3(−3) = −3, es decir 2x − 9 = −3, y entonces x = 3.

Luego r y t se cortan en el punto (3,-3).

Ejercicios:

1. Calcular los otros dos v´ertices.

2. Resolver los sistemas de inecuaciones lineales siguientes encontrando los v´ertices de las regiones

que sean soluci´on:

a)



3x +6y ≥ 420

4x +2y ≥ 290

b)



3x + 5y ≤ 150

3x + 3y ≤ 120

c)





x +2y ≤ 12

2x + y ≥ 4

x − 2y ≤ 6

x − y ≥ 0

CAP´ ITULO 8. PROGRAMACI´ ON LINEAL 130

Nota: Rectas horizontales y verticales.

En ocasiones, en estos sistemas, aparecen inecuaciones del tipo x ≥ k o bien y ≥ k, donde falta

alguna de las dos inc´ognitas.

Estas inecuaciones en realidad corresponden a rectas horizontales y verticales, y su representaci´on

es bien sencilla.

Por ejemplo, la inecuaci´on x ≤ −2 no es m´as que el conjunto de puntos a la izquierda de la recta

vertical que pasa por el punto x = −2, gr´aficamente:

Lo mismo ocurre con y ≤ 1, que ser´a en este caso la parte inferior a la recta horizontal y = 1, es

decir:

En el caso particular de que sea x ≥ 0 o y ≥ 0, las rectas coincidir´an con los ejes de coordenadas.

Ejercicios: Resolver los sistemas de inecuaciones lineales siguientes, encontrando los v´ertices de las

regiones que sean soluci´on:

a)





5x +15y ≤ 150

6x + 8y ≤ 120

x ≥ 0

y ≥ 0

b)





x + 3y ≥ 50

9x − 8y ≥ 0

3x +4y ≥ 60

x ≥ 0

y ≥ 0

c)





2x + y ≤ 10

x + 3y ≤ 12

0 ≤ x ≤ 8

0 ≤ y ≤ 2

Nota: Las dobles desigualdades como 0 ≤ x ≤ 8 se pueden desdobler en otras dos, x ≥

...