programación lineal

Cap´
ıtulo 8

´
PROGRAMACION LINEAL
8.1.

Introducci´n
o

La programaci´n lineal es una t´cnica matem´tica relativamente reciente (siglo XX), que consiste
o
e
a
en una serie de m´todos y procedimientos que permiten resolver problemas de optimizaci´n en el
e
o
a
´mbito, sobre todo, de las Ciencias Sociales.
Nos centraremos en este tema en aquellos problemas simples deprogramaci´n lineal, los que tienen
o
s´lamente 2 variables, problemas bidimensionales.
o
Para sistemas de m´s variables, el procedimiento no es tan sencillo y se resuelven por el llamado
a
m´todo Simplex (ideado por G.B.Danzig, matem´tico estadounidense en 1951).
e
a
Recientemente (1984) el matem´tico indio establecido en Estados Unidos, Narenda Karmarkar,
a
ha encontrado un algoritmo, llamadoalgoritmo de Karmarkar, que es m´s r´pido que el m´todo
a a
e
simplex en ciertos casos. Los problemas de este tipo, en el que intervienen gran n´mero de variables,
u
se implementan en ordenadores.

8.2.

Inecuaciones lineales con 2 variables

Una inecuaci´n lineal con 2 variables es una expresi´n de la forma:
o
o
ax + by ≤ c
(donde el s´
ımbolo ≤ puede ser tambi´n ≥ , < o bien >),donde a, b y c son n´meros reales y x e y las
e
u
inc´gnitas.
o
Para resolver estas inecuaciones, se recordar´ de otros cursos, hay que representar gr´ficamente en
a
a
el plano la recta dada por la correspondiente ecuaci´n lineal y marcar una de las dos regiones en que
o
dicha recta divide al plano.
Ejemplo: Si queremos resolver la inecuaci´n: 2x + 3y ≥ −3, representamos en primer lugar larecta
o
2x + 3y = −3:

127

´
CAP´
ITULO 8. PROGRAMACION LINEAL

128

La recta divide al plano en dos regiones, una de las cuales es la soluci´n de la inecuaci´n. Para
o
o
saber qu´ parte es, hay dos procedimientos:
e
1. Se despeja la y de la inecuaci´n, poniendo cuidado en que si en una inecuaci´n multiplicamos o
o
o
dividimos por un n´mero negativo, la desigualdad cambia desentido.
u
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´n de la inecuaci´n ser´ aquella parte en la que la y sea mayor que la recta, es decir, la
o
o
a
parte superior.

Figura 8.1: Soluci´n de la inecuaci´n lineal
o
o

2. Se toma un punto cualquiera que no pertenezca a la recta, porejemplo el (1,2).
Para que dicho punto sea soluci´n, se tendr´ que cumplir la desigualdad, por lo que sustituimos
o
a
en la inecuaci´n inicial el (1,2):
o
2 · 1 + 3 · 2 ≥ −3, es decir, 8 ≥ −3.
Como esta ultima desigualdad es evidentemente cierta, concluimos que el (1,2) es soluci´n y
´
o
por tanto el semiplano que contiene al (1,2) es la soluci´n, es decir el semiplano superior, como
ohab´
ıamos obtenido antes.
Cualquiera de los procedimientos es v´lido si se realiza con correcci´n.
a
o

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´ en resolver gr´ficamente cada inecuaci´n (como en el caso anterior), representar
a
a
o
la soluci´nen un mismo gr´fico y la soluci´n total ser´ la parte com´n a todas las soluciones.
o
a
o
a
u

´
CAP´
ITULO 8. PROGRAMACION 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´n del sistema de inecuaciones lineales
o
El tri´ngulo rayado es la soluci´n del sistema.
a
o
Adem´s, para los problemas de programaci´n lineal es necesario el c´lculo de los v´rtices de la
a
o
a
e
regi´n soluci´n. Es sencillo su c´lculo, pues se reduce a resolver sistemas de ecuaciones lineales son
o
o
a
dos inc´gnitas, que provienen de igualar las ecuaciones de las rectas...