CONCEPTOS BASICOS DE PROGRAMACION LINEAL

P. Lineal

LA PROGRAMACI ON

L I NEA L

1. INTRODUCCIÓN: la programación lineal como método de optimación
La complejidad de nuestra sociedad en cuanto a organización general y económica exige
disponer de métodos para la planificación y organización de la industria, de los transportes y para la
asignación de trabajos en forma óptima. La programación lineal (iniciada por Dantzig en 1947),que
es una pequeña parte de todo un cuerpo matemático que se ha venido consolidando en el siglo XX
con el nombre de optimización, abarca métodos de resolución de problemas en los que se buscan
los valores máximos o mínimos de funciones del tipo:
f= a 1x 1 + a 2x 2+....+ a nx n (llamada función objetivo ) cuyas variables x 1,x2 ,...,xn están
sujetas a unas condiciones restrictivas que seexpresan por medio de desigualdades.

2
n
Estudiaremos en esta unidad sólo el caso de dos variables y para su resolución métodos grá-

ficos, ya que no se pretende dar una solución general al problema, ni mucho menos agotar todas sus
aplicaciones.
Ejemplo de un problema tipo de programación lineal
Una empresa fabrica dos clases de lápices. De la clase A a 20 ptas. la unidad y de la clase B
a15 ptas. unidad. En la producción diaria se sabe que: el número de la clase B no supera en 1000
unidades a los de A; entre las dos clases no superan a 3000 unidades y los de la clase B no bajan de
1000 unidades. Hallar el costo máximo y mínimo de la producción diaria.
Vamos a traducir el enunciado al lenguaje algebraico:
Sea x el número de unidades fabricadas por día de la clase A
Sea y elnúmero de unidades fabricadas por día de la clase B
el beneficio obtenido al vender x unidades de A e y envases de B será :
20x + 15y, entonces consideramos la función
f(x,y)= 20x + 15y ,
que llamaremos función objetivo, y queremos hallar x, y para que sea máximo o mínimo; x e y están
sujetas a las siguientes condiciones (restricciones) :
y ≤ x + 1000
x + y ≤ 3000,

y ≥ 1000

Además debeser:

CV

41

P. Lineal

x≥0
Por tanto el problema consiste en hallar x, y de forma que el valor
f= 20x + 15y ( función objetivo ) sea máximo con las condiciones:
y ≤ x + 1000
x + y ≤ 3000
y ≥1000
x ≥0
El conjunto de puntos que cumplen estas condiciones se llama conjunto de puntos factibles (
o región factible).
La solución factible que haga óptima la función objetivo se llamasolución óptima.
Planteado el problema veremos a lo largo del tema como resolverlo.
2. Concepto de región factible. Puntos extremos.
Repaso de inecuaciones lineales con dos incógnitas.
*Una inecuación lineal es una desigualdad algebraica del tipo:
ax + by + c ≤ 0 ( ≥; )
Sus soluciones serán los pares de números (x,y) que hagan cierta la desigualdad.
Ejemplo: 2x-5y 0

a.c ≥ b.c

y cx-2y+4 es equivalente a x+y-4>0 , por tanto es lineal.

Representación gráfica del conjunto solución.
Proposición. Dada una inecuación equivalente a:
ax + by + c > 0 ó ax + by + c < 0
el conjunto solución es uno de los semiplanos cuya frontera es la recta:
ax + by + c=0 (la llamaremos recta auxiliar)
La inecuación puede escribirse para b≠ 0
y>
CV

− ax c
− (1)
b
b

y<

− ax c
− (2)b
b
42

P. Lineal

y los puntos de la recta auxiliar verifican:

y=

− ax c
−
b
b

Los puntos del semiplano superior verifican (1) y los del inferior verifican (2) (la demostración es inmediata).
(2)

(1)

Ejemplo 2: Resolver gráficamente la inecuación: 2x-5y 2 x / 5 , la solución es el semiplano superior.
Para señalar que no esta incluida la recta en el conjunto de lassoluciones se ha dibujado ésta
con trazo discontinuo. Si estuviera incluida se dibujaría con trazo continuo.

Sistemas de inecuaciones lineales.
*Un sistema de inecuaciones lineales es un conjunto de dos o más inecuacioness.
Resolver un sistema de inecuaciones es encontrar las soluciones comunes a todas ellas.

También la solución es gráfica
Se utilizará la representación gráfica para dar...