ingenieria

Apuntes de A. Cabañó
Matemáticas aplicadas a cc.ss.

PROGRAMACIÓN LINEAL
CONTENIDOS:
•
•
•

Desigualdades e inecuaciones. Sistemas lineales de inecuaciones. Recintos
convexos.
Problemas de programación lineal. Terminología básica.
Resolución analítica. Resolución gráfica.

La programación lineal surgió especialmente para dar respuesta a cuestiones de carácter
logístico y militar,aunque es en la industria y en la economía donde, posteriormente, ha
encontrado sus aplicaciones más importantes.
Así, por ejemplo, la programación lineal permite resolver problemas de mezclas, nutrición de
animales, distribución de factorías, almacenaje, planes de producción, escalonamiento de la
fabricación, problemas de circulación, planes de optimización de semáforos, etc.
Recintosconvexos.
Una ecuación lineal de la forma ax+by+c=0 representa una recta en el plano.
Una inecuación lineal de la forma
ax+by+c≤0 o bien ax+by+c≥0
representa el conjunto de puntos de cada uno de los dos semiplanos en los que la recta
ax+by+c=0 divide al plano.

ax+by+c≤0

ax+by+c≥0

Ejemplo
a) Dibuja el recinto formado por los puntos que cumplen las siguientes condiciones:
y ≤ 3

y − x≥ 1
y − 3 x ≤ 0


b) Indica si los puntos (0, 0), (2, 1) y (1, 2) forman parte de las soluciones del sistema
anterior.
y = 3

a) Representa mos las rectas y − x = 1 → y = x + 1
y − 3 x = 0 → y = 3 x


1

Programación lineal

Apuntes de A. Cabañó
Matemáticas aplicadas a cc.ss.

Tomamos un punto cualquiera; por ejemplo el (1, 0), para comprobar cuáles son los
puntos quecumplen las desigualdades propuestas.
El recinto buscado es:

b) A la vista de la gráfica anterior, tenemos que (0, 0) y (2, 1) no son soluciones del
sistema, pero (1, 2) sí lo es.
Problemas de programación lineal. Terminología básica.
Un problema de programación lineal para dos variables consiste en optimizar (maximizar o
minimizar) una función lineal de la forma
z=ax+by
que llamamosfunción objetivo, sujeta a un sistema de desigualdades lineales:

a1 x + b1 y ≤ d1
a x + b y ≤ d
 2
2
2

.............

..............

que llamamos restricciones.
Cada desigualdad lineal anterior determina un semiplano. El conjunto de los puntos que
cumplen todas las desigualdades determina un recinto, acotado o no. A los puntos del recinto,
por cumplir todas las restricciones, seles denominan soluciones factibles.
Solución óptima es una solución factible que haga máxima o mínima la función objetivo. El
valor que toma la función objetivo z en la solución óptima, es decir, en el punto que la maximiza
o minimiza, recibe el nombre de valor del programa lineal.
Se demuestra que si existe una única solución óptima, ésta se encuentra en un vértice del
recinto. Por tanto,calcularemos las coordenadas de los vértices del recinto y evaluaremos la
función objetivo en cada uno de ellos. En el vértice que la función objetivo tome el mayor valor,
ese será el máximo o la solución óptima. Análogamente para el mínimo.
En algunos casos es posible que existan infinitas soluciones y todas ellas se encontrarán en un
lado del recinto que será paralelo al vector que marca ladirección de la función objetivo.
También es posible que no exista solución óptima, pues si el recinto no está acotado
superiormente la función objetivo crecerá indefinidamente, no encontrando nunca el máximo.
Del mismo modo, si el recinto no está acotado inferiormente la función objetivo decrecerá
indefinidamente, no encontrando nunca el mínimo.
Para obtener el máximo o el mínimo por métodosgráficos basta desplazar una recta paralela a
la determinada por la función objetivo; en el vértice del recinto que tenga la recta mayor
ordenada en el origen, estará el máximo. Análogamente para el mínimo.
Por lo tanto para hallar gráficamente, la solución de un problema de programación lineal de dos
variables es conveniente seguir este proceso:

2

Programación lineal

Apuntes de...