PROGRAMACION LINEAL L a p r o g r a m a c i ó n l i n e a l d a re s p u e s t a a s i t u a c i o n e s e n l a s q u e s e e x i g e m a x i m i z a r o m i n i m i z a r f u n c i o n es q u e s e e n c u e n t r a n s u j e t a s a d e t e rm i n a d a s l i m i t a c i o n e s , q u e l l a m a re m o s r es t r i c c i o n e s .

Su e mp le o es frec ue nte e n ap lic a c iones d e la indu s tria, la ec onomía , la e s t ra t e g ia m i l i t a r , e t c .

CONSTRUCCIÓN DE MODELOS DE PROGRAMACIÓN LINEAL. Los modelos de programación matemática mantienen una relación indirecta con la computación. El término “Programación” no debe ser confundido con el utilizado en la ciencia de los computadores. En el campo de la programación matemática, “Programación” resulta equivalente a planificación, en el sentido más amplio de este término. No obstante, la magnitud de muchos de los problemas tratados, el elevado número de datos y relaciones, hace impensable su resolución sin el soporte informático. Tal vez la característica común a todos los modelos de programación matemática radica en su finalidad: son modelos de optimización. Cada modelo de programación matemática es concebido con el objetivo de encontrar, para el problema que representa, la solución (o las soluciones), de entre las existentes, que alcance el valor máximo o mínimo de acuerdo a cierto criterio que denominamos objetivo. De forma particular, este capítulo se centrará en la construcción de modelos de programación lineal continuos, enteros, mixtos, y en algún caso modelos que presentan no linealidades, analizando para ellos alguna posible formulación lineal aproximada. Los modelos lineales, como ya se vio en los primeros capítulos del libro, exigen que la función objetivo y las restricciones del problema sean lineales. En algunas situaciones esta consideración resulta excesiva y supone ciertamente una limitación a la hora de modelar. En algunas ocasiones, las expresiones no lineales pueden ser tratadas, obteniéndose un modelo final lineal. A pesar de estas observaciones, resulta más fácil, de forma general, resolver modelos lineales, de aquí su importancia y su amplia utilización. De manera específica, un modelo lineal consta de tres bloques diferenciados. La función Construcción de modelos de Programación Lineal, objetivo, las restricciones y la definición de signo o tipo de las variables. El proceso de modelado consiste en la especificación de estos tres bloques. No existe ninguna metodología específica para modelar problemas, la experiencia resulta fundamental, es en este sentido en el que el proceso de modelar es a veces llamado “arte” de modelar. No obstante, en el presente capítulo se reflejarán las situaciones más comunes que se presentan en el modelado de

problemas lineales. Posteriormente se complementará lo expuesto desarrollando de forma minuciosa algunos casos concretos. En los diferentes modelos expuestos se ha seguido una procedimiento de modelado similar. Así, analizaremos el horizonte temporal para el que se construye el modelo, en el caso de situaciones que presentan variaciones a lo largo del tiempo. Definiremos en cada caso las variables de decisión del problema. Para ello nos basaremos principalmente en los datos disponibles, a veces en los costes unitarios de las variables y en otros casos en los relacionados con la estructura de las restricciones del problema. Conocidas las variables de decisión, formularemos las restricciones del problema, a partir de la descripción formal del mismo, incluyendo las variables auxiliares que resulten necesarias. De forma adicional surgirán restricciones implícitas al modelo como consecuencia de la elección inicial de determinadas variables, de procesos de linealización y de la relación entre variables de decisión y auxiliares. En último lugar, aunque no siempre será así, formularemos el objetivo del problema.

F unción ob jetiv o

E n e s e n c i a l a p ro g ra m a c i ó n l i n e a l c o n s i s t e e n o p t i m i z a r ( m a x i m i z ar o m i n i mi z a r )

una

función

ob jetiv o ,

que

es

una

función

lineal

de

varias variables:

f(x,y) = ax + by.

R es t r i c c i o n e s

La

func ión

ob je tivo

está

s uje ta

a

e x p re s a d a s p o r i n e cu a c i o n es l i n e a l es :

a1x + b1y ≤ c1 a2x + b2y ≤c2 ...

...

...

anx + bny ≤cn

una

serie

de

r es t r i c c i o n es ,

C a d a d e s i g u a l d a d d e l s i s t e m a d e r e s t r i c c i o n e s d e t e rm i n a u n s e m ip l a n o .

Solución factib le

E l c o n j u n t o i n t e r s e c c i ó n , d e t o d o s l o s s e m ip l a n o s f o r m a d o s p o r l a s r e s t r ic c i o n e s , d e t e r m i n a u n r e c i n t o , a c o t a d o o n o , q u e re c ib e e l n o m b r e d e r e g i ó n d e v a l i d ez o z o n a d e s o l u ci o n e s f a c t i b l es .

Solución óp tima

El

c onjunto

s o l u ci o n es s o l u ci ó n

de

los

v é r t ic e s

f a c t i b l es

óp tima

se

del

b á s i c as llama

re c into

y

el

solución

se

vértice

de nomina d onde

má x i m a

(o

se

c onjunto

de

p re s e n t a

mínima

la

s eg ún

el

caso).

Valor d el pr og r ama lineal

E l v a l o r q u e t o m a l a f u n c i ó n o b j e t i v o e n e l v ér t i c e d e s o l u c i ó n ó p t i m a s e l l a m a v a l o r d el p r o g r am a l i n ea l

E je r cicio s

d e p r o g r a m a ció n line a l ( a p lica cio ne s)

C o n e l c o m i e n z o d e l c u r s o s e va a l a n z a r u n a s o f e rt a s d e m a t e r i a l e s c o l a r . U nos

a lma ce ne s

q u ie r e n

ofrecer

600

cua de rnos ,

500

c a rp e t a s

y

400

b o l í g r a f o s p a r a l a o f e r t a , e m p a q u e t á n d o l o d e d o s f o rm a s d i s t i n t a s ; e n e l p rime r

b loq ue

p ond rá

2

c u a d e rn o s ,

1

c a rp e t a

y

2

b o l í g ra f o s ;

en

el

s e g u n d o , p o n d rá n 3 c u a d e r n o s , 1 c a r p e t a y 1 b o l í g ra f o . L o s p re c i o s d e

c a d a p a q u e t e s e r á n 6 . 5 y 7 €, re s p e c t iv a m e n t e . ¿ C u á n t o s p a q u e t e s le c o n v i e n e p o n e r d e c a d a t i p o p a ra o b t e n e r e l m á x i m o b e n e f i c i o ?

1 Elec c ión d e las incóg nitas. x = P1

y = P2

2 F unción ob jetivo f(x, y) = 6.5x + 7y

3 R es t r i c c i o n es

P1 P2

Disponibles

C u a d e r no s

2

3

600

Carpetas

1

1

500

B o l í g r a f os

2

1

400

2x + 3y ≤ 600

x + y ≤ 500

2x + y ≤ 400

x ≥ 0

y ≥ 0

4 H a l l a r e l c o n j u n t o d e s o l u c i o n es f a c t i b l e s

5 C a l c u l a r l a s c o o rd e n a d a s d e l o s v é r t i c e s d e l r e c i n t o d e l a s s o l u c i o n e s f a c t ib l e s .

6 C a l c u l a r e l v al o r d e l a f u n ci ó n o b j e t i v o

f ( x , y ) = 6 . 5 · 2 0 0 + 7 · 0 = 13 0 0 €

f ( x , y ) = 6 . 5 · 0 + 7 · 2 0 0 = 1 40 0 €

f ( x , y ) = 6 . 5 · 1 5 0 + 7 · 1 00 = 1 6 7 5 €

Má ximo

La s oluc ión óp tima s on 150 P 1 y 100 P2 con la q ue se ob tie ne n 1675 €

EJERCICIOS 1. Explique cuáles son los parámetros para la construcción de modelos de programación lineal 2. Que es la función objetivo y explique cuál es la finalidad e importancia en el cálculo de máximos y mínimos en una función. 3. Consulte un ejercicio donde se ponga en práctica las definiciones anteriores, hallando el mínimo o máximo de la función en dicho problema. 4. Explique que es región de soluciones optimas 5. Explica cual es la finalidad del estudio de los métodos de programación lineal en el programa de formación que actualmente usted desempeña en la Universidad. 6. Realice un paralelo entre los conceptos aprendidos de algebra Lineal y los que empieza a relacionar en programación lineal.