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

...