PROGRAMACIN LINEAL

por Patricia Cuadros, Zulma Millan, Laura Oliva

Facultad de Ingeniera - Universidad Nacional de San Juan - Argentina

pcuadros unsj.edu.ar

Introduccin:

Con el avance en rapidez y precisin de las computadoras, programas como el MAPLE V permiten reemplazar el tiempo empleado en los clculos manuales, con el anlisis y profundizacin de conceptos. Convirtindose en una herramienta de gran ayuda para los estudiantes de carreras en ciencias exactas e ingenieras.

Los ejemplos presentados en este trabajo tienen carcter didctico. La metodologa empleada es, luego que el alumno participa de clases terico prcticas realiza en gabinete la practica propuesta, pudiendo comparar los resultados logrados en la misma con los mostrados en la clase y los obtenidos por l.

Objetivo:

La programacion lineal es un conjunto de tecnicas matematicas que permiten solucionar problemas de planificacion economica o social. El objetivo basico es encontrar es encontrar la solucion optima que maximiza o minimiza la funcion objetivo.

Hay varias maneras de enfocar este tema, una instuitivamente mediante la geometra, computacionalmente a travs del mtodo simplex o algebricamente mediante la teora de la dualidad. Se desarrollarn los dos primeros enfoques.

Usando los comandos propios del software, graficar la regin en el plano que determina la solucin de una inecuacin lineal y extender este concepto a la resolucin de problemas de optimizacin de funciones por programacin lineal en regiones planas, mediante un anlisis geomtrico. Y la aplicacin del Mtodo Simplex, usando el paquete brindado por MAPLE V.

Se usaran sentencias que se encuentran incluidas en los paquetes plots y simplex

> restart; with(plots):

Warning, the name changecoords has been redefined

I- Graficacin de inecuaciones y sus regiones factibles

Cuando se encuentra la solucin de una inecuacin de una variable, se representa por intervalos en la recta numrica. En el caso de una desigualdad de dos variables, por lo general la solucin est representada por una regin en el plano coordenado( o semiespacio).

Notar que la grfica de una recta y = m x + b, separa al plano coordenado en tres partes :

1. el semiplano por encima de la recta, que consiste en todos los puntos (x,y) que satisfacen la desigualdad y > m x + b

2. la recta misma, formada por todos los puntos (x,y) que verifican su ecuacin.

3. el semiplano por debajo de la recta, que consiste en todos los puntos(x,y) que satisfacen la desigualdad y< m x + b

Para el caso en que la desigualdad estricta "<" es reemplazada por "<=", la solucin consiste en los puntos que satisfacen la ecuacin de la recta como as tambien los del semiplano por debajo de ella. En este caso se dice que la solucin es el semiplano cerrado.

El comado para graficar la regin y sus rectas de borde es

inequal( inecuaciones, x=xmn..xmx, y=ymn..ymx, optionsnombre )

optionsnombre = (secuencia de opciones del comando plot)

las opciones son:

optionsfeasible: regin que satisface todas las inecuaciones.
optionsexcluded : regin en la cual al menos una de las inecuaciones no es vlida

optionsopen : representacin de las lneas de borde de regiones con desigualdades estrictas ("< o >") En este caso los puntos sobre la recta de borde no son parte de la solucin, indicaremos con lnea punteada este borde.
optionsclosed : representacin de las lneas de borde de regiones cerradas ("<= o >=" , incluyen los bordes).

Ejemplo 1: una inecuacin.

Un consumidor desea gastar como mximo 60 pesos en la compra de las cantidades x e y de dos productos A y B, siendo de dos pesos el costo de cada producto A y de tres pesos para el producto B. Cuales son las posibles combinaciones de cantidades de A y B para satisfacer la condicin?.

> inec:={2*x+5*y <=70 };

> inequal(inec,x=-10..35,y=-4..30,optionsfeasible =(color=plum), optionsexcluded =(color=wheat),optionsopen =(color = blue,linestyle=3),
thickness=1,optionsclosed =(color=coral,thickness=3,linestyle=1));

Ejemplo 2: Sistema de inecuaciones

La solucin de un sistema de inecuaciones consiste en todos los puntos cuyas coordenadas satisfacen de manera simultnea todas las desigualdades y geomtricamente es la regin comn a todas las regiones determinadas por las desigualdades dadas.

> sys:={y>-2*x+3,x>=y,y>1/2};

> inequal(sys,x=-5..12,y=-4..18,optionsfeasible=(color = plum), optionsexcluded=(color=wheat),optionsopen=(color=blue),thickness=2,linestyle = 3, optionsclosed=(color=coral,thickness=2,linestyle=1));

Ejemplo 3:

> sys3:={ x + y <= 16, x > -3, x < 10, y > -2, y <= 14 };

> inequal(sys3,x=-5..12,y=-4..18,optionsfeasible=(color = plum), optionsexcluded=(color=wheat),optionsopen=(color=blue,thickness = 1, linestyle=3),optionsclosed=(color=coral,thickness=2) );

>

II. Programacin lineal

Un tpico problema de optimizacin por programacin lineal consta de dos partes:
las restricciones : un sistema de inecuaciones ( ) que define la regin de validez y una funcin a optimizar (maximizar o minimizar) dentro de la regin de validez.Hay una restriccin fundamental en la programacin lineal: se pide que x e y sean no negativas. Estas condiciones son un par de desigualdades lineales ms, e , ya que representan cantidades de objetos o sustancias. Un sistema de m inecuaciones como describe la interseccin de m semiespacios (semiplanos), y si se pide que cada componente de x sea no negativa, esto aade n semiespacios ms. Las restricciones deben ser inecuaciones lineales, su numero depende del problema en cuestion, mientras ms restricciones impongamos ms pequea ser la regin factible. Puede suceder que una regin factible sea acotada, no acotada o an vacia.

En programacin lineal no estamos interesados en el conjunto de todos los puntos factibles sino, el objetivo del problema es encontrar un punto (x,y), que est en el conjunto factible y que sea la solucin ptima, donde el valor de la funcin objetivo es mximo o mnimo. La funcin objetivo P(x,y) proporciona una familia de rectas paralelas, hay que encontrar la primera recta que intersecta a la regin factible, que es la que maximiza o minimiza a P(x,y). El primer contacto de una recta debe suceder a lo largo de la frontera de la regin factible, por lo que el punto (x,y) que d el valor ptimo es una esquina de la regin factible.

Por ejemplo un fabricante puede querer maximizar una funcin de utilidad sujeta a las restricciones de produccin impuestas por las limitaciones sobre el uso de la maquinaria y la mano de obra.

La solucin del problema se puede dividir en cuatro partes:
1. Definir el sistema de inecuaciones ( las restricciones) a partir de los datos del problema

2. Graficar la regin de validez o factible. Este es el paso fundamental donde se imponen simultneamente todas las restricciones dadas por las inecuaciones. Geomtricamente se combinan para dar la regin factible.
3. Definir la funcin objetivo P(x,y)
4. Encontrar la solucin, (x,y), el valor ptimo (mximo o mnimo) de P(x,y), que satisface el sistema de inecuaciones ( las restriccones impuestas)

Ejemplo 4: Solucin del problema desde un enfoque geomtrico

Una compaa produce dos tipos de artculos, manuales y elctricos. Cada uno requiere para su fabricacin del uso de tres mquinas A,B, y C. cada artculo manual requiere del uso de la mquina A durante 2 horas, de la mquina B por una hora y de lamquina C otra hora. Un artculo elctrico requiere una hora de A, dos horas de B y una hora de C. Adems el nmero de horas disponibles por mes para el uso de las mquinas A,B y C es de 180, 160, y 100 repectivamente. La utilidad por cada artculo manual es de $4 y por cada artculo elctrico es de $6. Si la compaa vende todos los artculos que puede producir, Cuntos artculos de cada tipo debe producir con el fin de maximizar la utilidad mensual?

1. Definir el sistema de inecuaciones . sean x e y el nmero de artculos manuales y elctricos respectivamente.

El nmero de artculos producidos es no negativo: ,

Para la mquina A :

Para la mquina B: y para la C:

La utilidad es : funcin objetivo

> sys4:={x>=0,y>=0,2*x+ y<=180,x+2*y<=160,x+y<=100};

2. grfica de la regin de validez ( donde se cumplen todas las restricciones impuestas por la fabricacin)

> inequal(sys4,x=-0..200,y=0..180,optionsfeasible=(color =plum), optionsexcluded=(color=wheat),optionsclosed=(color=coral),thickness=2);

3. Definir la funcin objetivo

> P :=(x,y)-> 4*x + 6*y;

> y:=x->-2/3*x+P/6;

Si suponemos que la utilidad es P = 600:

> y1:=subs(P=600,%);

Suponiendo la utilidad P=300

> y2:=subs(P=300,%%);

> r:=inequal(sys4,x=0..200,y=0..180,optionsfeasible=(color =plum), optionsexcluded=(color=wheat),optionsclosed=(color=coral),thickness=2):

> f1:=plot(y1(x),x=0..200,color=blue):

> f2:=plot(y2(x),x=0..200,color=blue):

> t1:=textplot([110,65,`funcin objetivo (P=600)`]):

> t2:=textplot([100,-55,`funcin objetivo (P=300)`]):

> display(r,f1,f2,t1,t2);

4. Encontrar la solucin

La funcin objetivo donde P adopta el valor 600 da todas las posibles combinaciones de x e y con que se obtiene la misma utilidad. $600; en forma anloga la funcin con valor de P =300. La recta de valor P=600 no tien ningn punto en comn con la regin factible, mientras que la de P=300, tiene infinitos puntos en comn. Por lo que tenemos que buscar una recta de esta familia que solo tenga un punto en comn y ese sea el mximo. El intento de solucionar el problema probando soluciones es importante, pues conduce a entender la naturaleza del problema, permite encontrar soluciones aproximadas y descartar resultados absurdos y siempre es importante ayudarse con representaciones graficas.

Observando la grfica se deduce que la solucion es aquella recta que tiene en comn con la regin vlida, un punto vrtice de la regin. Por lo cual hay que encontrar las coordenadas de los vrtices de la regin vlida, formados por la interseccin de las rectas de borde y se calculan resolviendo cada uno de los posibles sistemas de dos escuaciones que se obtienen.

.

Punto A : pertenece a las rectas:

> solve({x=0,x+2*y=160},{x, y});

> P1=subs({x=0,y=80},P(x,y));

Punto B: pertenece a las rectas

> solve({x+2*y=160, x+y=100},{x,y});

> P2=subs({x=40,y=60},P(x,y));

Punto C : pertenece a las rectas

> solve({2*x+y=180, x+y=100},{x,y});

> P2=subs({x=80,y=20},P(x,y));

Por los resultados obtenidos la mxima utilidad est dada por P2 = $520, por lo cual la combinaciun adecuada es producir 40 articulos manuales y 60 artculos elctricos, respetando las restricciones impuestas.

Ejemplo 5: regin factible no acotada

Un agricultor compra fertilizantes que contienen tres nutrientes, A, B y C. las necesidades mnimas son: 160 unidades de A, 200 de B y 80 de C. En el mercado existen dos marcas populares de fertilizantes. F.G., con un costo de $4 por bolsa con 3 unidades de A, 5 de B y 1 unidad de C. E.G., con un costo de $3 por bolsa con 2 unidades de cada nutriente. si el agricultor desea minimizar el costo mientras se mantenga el requerimiento de nutrientes, Cuntas bolsas de cada marca debe comprar?.

Sea x el nmero de bolsas de F.G. e y el nmero de bolsas de E.G.

> sys5:={x>=0,y>=0,3*x+2*y>=160,5*x+2*y>=200,x+2*y>=80};

> inequal(sys5,x=-0..100,y=0..150,optionsfeasible=(color =plum), optionsexcluded=(color=wheat),optionsclosed=(color=coral),thickness=2);

Se observa que la regin factible no es acotada.

> C:=(x,y)-> 4*x + 3*y;

> y:=(x)->C/3-4/3*x;

> y1:=subs(C=200,%);

> r:=inequal(sys5,x=0..100,y=0..120,optionsfeasible=(color =plum), optionsexcluded=(color=wheat),optionsclosed=(color=coral),thickness=2):

> f1:=plot(y1(x),x=0..100,color=blue):

> t1:=textplot([40,-40,`funcin objetivo (C=200)`]):

> display(r,f1,t1);

> solve({3*x+2*y=160,x+2*y=80},{x,y});

> C1:=subs({y = 20, x = 40},C(x,y));

> solve({3*x+2*y=160,5*x+2*y=200},{x,y});

> C1:=subs({y = 50, x = 20},C(x,y));

El costo mnimo se obtiene al comprar 40 bolsas de F.G. y 20 bolsas de E.G.

III - MTODO SIMPLEX

El mtodo geomtrico no es posible usarlo cuando el nmero de variables supera a tres. Los problemas reales de programacion lineal dependen de muchas variables, a veces, de cientos. Ello genera regiones factibles con un gran numero de vertices. El metodo Simplex, fue desarrollado por Dantzig a partir de 1947, permite encontrar la solucion optima. Para su aplicacion requiere el uso de un software cientifico.

El mtodo simplex empieza con una solucin factible y prueba si es o no ptima, si no lo es, se procede a obtener una solucin mejor. Es eficiente y completamente mecnico, con uso de matrices y sus operacione bsicas. Aplica la siguiente propiedad: Si P no toma su valor maximo en el vertice A, entonces hay una arista que parte de A a lo largo de la cual P aumenta. Por lo tanto, para hallar el valor maximo de la funcion objetivo P nos desplazamos a traves de las aristas de la region factible, hasta alcanzar el vertice mas alto, aquel en que P sea maxima. Es por lo tanto un metodo iterativo, que se detiene cuando P alcanza el maximo, o sea cuando no haya ninguna arista que parte del vertice en la que P aumente su valor.

Se trata de una programacion lineal con n incognitas y m restricciones. Las n incognitas se constituyen en un vector columna no negativo x, este vector debe satisfacer m restricciones, ademas de , escribiendolas como . La matriz A es de m por n y cada una de sus filas proporcina una inecuacion.

En este caso se hace uso directamente del paquete de comandos que provee MAPLE V.

Ejemplo: Maximizar

sujeta a : , , , ,

> with(simplex):# paquete que contiene el mtodo

Warning, the name display has been redefined

Warning, the protected names maximize and minimize have been redefined and unprotected

> sys9:={x-2*y <= 2 , x+y <= 5 , w+t <= 4 , w-2*t <= 7, 0 <= x, 0 <= y, 0 <= w, 0 <= t}; # restricciones

> z:=(x,y,w,t)->60*x+0*y+90*w+0*t; # funcin objetivo

> display(sys9);# muestra el sistema en forma de matriz

> feasible(sys9);# determina si tiene solucin o no el sistema planteado

> sol:=maximize(z(x,y,w,t),sys9,NONNEGATIVE);

> Zmax=subs(sol,z(x,y,w,t)); # valor mximo de z

>

Ejercicios

1) Un fabricantede juguetes esta preparando un programa de produccin para dos nuevos artculos "M y F", la informacin de sus tiempos de produccin se proporciona en la tabla siguiente:

juguete Mquina A Mquina B terminado

M 2 hs 1 hs 1 hs

F 1 hs 1 hs 3 hs

Las horas disponibles para la mquina A por semana son 70, para la mquina B: 40 horas y para terminado 90 horas. si las utilidades de cada juguete M y cada F son $4 y $6 respectivamente. Cuntas unidades de cada juguete se debe producir por semana con el fin de maximizar la utilidad? Cul sera la utilidad mxima?

2) Un bioqumico va ha comprar dos soluciones que contienen tres compuestos qumicos A,B,C. Los requisitos mnimos semanales del laboratorio son 80 unidades de A, 120 unidades de B y 240 unidades de C. Existen dos marcas usuales de estas soluciones en el mercado. La marca I cuesta $4 el paquete y contiene 2 unidades de A, 6 de B y 4 de C; la marca II cuesta $5 y contiene 2 unidades de A, 2 de B y 12 de C. Cuantos paquetes de cada marca debe comprar el bioquimico cada semana para minimizar los costos y satisfacer los requerimientos del laboratorio?

3) Las autoridades sanitarias de una determinada region planifican la puesta en marcha de centros de asistencia medica primaria. En la region hay dos zonas bien diferenciadas, El Valle y La Montana, y que necesitan distinta dotacion. Cada centro asistencial de El Valle requiere 3 medicos, 3 asistentes y una inversion de 30 millones de pesos. En La Montana, cada centro necesita 2 medicos y 4 asistentes, mas una inversion de 10 millones. Para llevar a cabo tal proyecto se cuenta con un total de 30 medicos, 48 asistentes y 240 millones. Cual es el numero maximo de centros asistenciales que pueden ponerse en funcionamiento?

4) Utilice el mtodo simplex para resolver los siguientes problemas.

Referencias

1. Ernest F. HAEUSSLER, JR. y Richard S. PAUL. Matemticas para Administracin, Economa, Ciencias Sociales y de la Vida. Octava Edicin. Editorial Printice Hall.

2. Gilbert STRANG. Algebra Lineal y sus aplicaciones. Editorial Addison-Wesley Iberoamericana.

3. Jose M. Martinez-Mediano, Rafael Cuadra Lopez. Matematicas aplicadas a las Ciencias Sociales 2. Editorial Mc.Graw Hill