PROGRAMACION LINEAL

Cap´ıtulo 8

´ LINEAL
PROGRAMACION
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 quetienen
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´
asr´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

´ LINEAL
CAP´ITULO 8. PROGRAMACION

128

Larecta 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 rectadivide 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 quesustituimos
en la inecuaci´
on inicial el (1,2):
2 · 1 + 3 · 2 ≥ −3, es decir, 8 ≥ −3.
Como esta u
´ ltima 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 deinecuaciones 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.

´ LINEAL
CAP´ITULO 8. PROGRAMACION

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 delos 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 −...