10. Programación lineal

NOTA: Debido a la complejidad de este tema, sólo se tratarán unas nociones básicas para poder maximizar una función en base a una serie de restricciones.

FUNCION OBJETIVO

Una función objetivo viene expresada de la forma:

z = a · x + b · y

donde para ser representada gráficamente se utilizan una serie de restricciones:

a1 · x + b1 · y <= c1

a2 · x + b2 · y <= c2

...

an · x + bn · y <= cn

x, y >= 0

Una vez representada gráficamente, se dice que forma un conjunto convexo si la superficie delimitada por las rectas (restricciones) dan lugar a puntos de corte con los ejes X (PX , 0) e Y (0, PY) y los puntos PMAX (PX' , PY') para que esté completamente delimitada:

ai · x + bi · y = ci   ||   y = 0   ||   (PX , 0)

aj · x + bj · y = cj   ||   x = 0   ||   (0, PY)

ai · x + bi · y = ci   ||   aj · x + bj · y = cj   ||   (PX' , PY')

x = 0   ||   y = 0   ||   (0, 0)

Las dos primeras ecuaciones se resuelven de forma inmediata al igualar a cero las incógnitas x e y. La última viene impuesta por la última restricción donde los valores tienen que ser positivos. Sin embargo, para la tercera dependerá del número de ecuaciones, que se combinarán entre ellas (sistema de ecuaciones) hasta obtener un punto que sea el valor máximo para dicha función. Una vez hallados todos los puntos, se sustituyen en la función objetivo y se calcula el valor que maximiza la función:

z(PX , 0) = PX · x + 0 · y = ZX

z(0, PY) = 0 · x + PY · y = ZY

z(PX' , PY') = PX' · x + PY' · y = ZMAX

z(0, 0) = 0 · x + 0 · y = 0

Los valores que maximizan la función serán:

PMAX = ( x = PX' , y = PY' , z = ZMAX )

Ejemplo

Maximizar la función z = 3x + 2y con las siguientes restricciones:

4x + y <= 16

5x + 6y <= 30

x, y >= 0

Se representan gráficamente las rectas y se hallan los puntos que delimitan:

4x + y = 16

y = 0

(PX , 0) = (4, 0)

5x + 6y = 30

x = 0

(0, PY) = (0, 5)

4x + y = 16

5x + 6y = 30

(PX' , PY') = (66/19 , 40/19)

x = 0

y = 0

(0, 0) = (0, 0)

Se sustituyen los puntos en la función objetivo:

z(4, 0) = 3 · 4 + 2 · 0 = 12

z(0, 5) = 3 · 0 + 2 · 5 = 10

z(66 / 19, 40 / 19) = 3 · 66 / 19 + 2 · 40 / 19 = 278 / 19

z(0, 0) = 3 · 0 + 2 · 0 = 0

El valor que maximiza la función es zMAX = 278 / 19, por lo tanto el punto máximo es:

x = 66 / 19

y = 40 / 19

z = 278 / 19

PMAX = ( 66 / 19 , 40 / 19 , 278 / 19 )