PROGRAMACION LINEAL

INTRODUCCIÓN

Veamos. Si tienes en el bolsillo una cantidad de dinero, la puedes usar para comprar comida, bebidas, pagar por tener diversión, etc. Además del dinero, puedes tener un reloj que pudieras empeñar, y quizás otras piezas de joyería. El problema de programación al que te enfrentas es: “¿Cómo obtengo mayor valor por los productos y servicios que adquiero con el dinero que tengo?”

La Programación Lineal es una técnica de optimización matemática que permite asignar recursos limitados y así encontrar una solución aproximada a problemas de decisión como el planteado anteriormente, y siempre relacionados con la maximización o minimización, utilizando apropiadamente los recursos.

Para poder aplicar la Programación Lineal a un problema, deben existir 4 condiciones:

DEFINICIONES

Función objetivo

Es la función principal de la cual hay que averiguar el valor máximo desde una serie de restricciones o rectas que delimitan la gráfica de dicha función.

Restricciones

Son desigualdades a las cuales se les añaden unas variables llamadas de holgura para convertirlas en rectas y delimitar el área de la función objetivo. Los puntos de cortes entre rectas (sistemas de ecuaciones) serán los que indiquen el máximo de la función objetivo.

Convexidad

Se dice que el área delimitada por las restricciones es un conjunto convexo si está completamente cerrada por los puntos como resultado de resolver la representación gráfica. Siempre se toma el área mínima en los puntos de corte con las rectas.

MÉTODO GRÁFICO

Normalmente, se tratarán funciones de 2 variables. La función objetivo se presenta de la siguiente manera:

Z = Ax1 + Bx2

Para evitar dificultades, se tomarán como muestra 3 restricciones para dicha función, siendo el número mínimo una restricción por cada variable:

a1x1 + b1x2 " c1

a2x1 + b2x2 " c2

a3x1 + b3x2 " c3

x1, x2 " 0

En el método gráfico, las anteriores desigualdades se convierten en igualdades y ya tenemos las rectas que delimitarán la función. Para hallar los puntos de corte con los ejes de coordenadas, se igualan a 0 cada variable, quedando de la siguiente forma:

La última restricción sirve para tomar en cuenta el punto (0,0) como origen del área delimitada por las rectas. Para el eje de coordenada X (variable x1) se tomará el mínimo de los ptos (ci/ai, 0):

Min[ (c1/a1, 0) , (c2/a2, 0) , (c3/a3, 0) ]

Igualmente, para el eje de coordenada Y (variable x2) se tomará el mínimo de los puntos (0, ci/bi):

Min[ (0, c1/b1) , (0, c2/b2) , (0, c3/b3) ]

A continuación, se toman aquellos puntos que sean intersección de las tres rectas y que pertenezcan además a las rectas que contienen los puntos mínimos anteriores. El área total de la función vendrá delimitada por los puntos (ci/ai, 0), (0, ci/bi) y los de la intersección de las rectas. Una vez obtenidos los puntos de intersección, se crean tantos sistemas de ecuaciones como puntos de intersección que cumplan la condición anterior haya. En nuestro caso, para tres rectas se hacen dos sistemas de ecuaciones tomando en cada uno una de las rectas asociadas con uno de los puntos de corte, y la tercera será común a ambos sistemas. Por último, cada punto resultante se resuelve en la función objetivo, sustituyéndolo en las variables x1 y x2, y se toma aquél que dé el máximo valor de Z.

APLICACIONES

1. Un estudiante dedica parte de su tiempo al reparto de propaganda publicitaria. La empresa A le paga 5 ptas. por cada impreso repartido y la empresa B, con folletos más grandes, le paga 7 ptas. por impreso. El estudiante lleva dos bolsas: una para los impresos A, en la que caben 120, y otra para los impresos B, en la que caben 100. Ha calculado que cada día es capaz de repartir 150 impresos como máximo. Lo que se pregunta el estudiante es: ¿Cuántos impresos habrá que repartir de cada clase para que su beneficio diario sea máximo?

Llamemos:

x= n: de impresos diarios tipo A repartidos.

y= n: de impresos diarios tipo B repartidos.

La función objetivo es: f(x, y) = 5x + 7y

Las restricciones:

La zona de soluciones factibles es:

Vértices:

A (0, 100)

B intersección de s,t:

C intersección de r,t:

D (120, 0)

Siendo los valores de la función objetivo:

Debe repartir 50 impresos tipo A y 100 tipo B para una ganancia máxima diaria de 950 ptas..

2. Un comerciante acude a cierto mercado a comprar naranjas con 50000 pesos. Le ofrecen dos tipos de naranjas: las de tipo A a 50 pesos el kg. y las de tipo B a 80 pesos el kg. Sabiendo que sólo dispone en su furgoneta de espacio para transportar 700 kg. de naranjas como máximo y que piensa vender el kg. de naranjas tipo A a 58 pesos y el kg. de tipo B a 90 pesos, contestar justificando las respuestas:

Llamemos:

x= kg. de naranjas tipo A comprados.

y= kg. de naranjas tipo B comprados.

La función objetivo que da el beneficio es:

Y las restricciones:

La zona de soluciones factibles es:

Y los vértices:

A(0, 625)

B intersección de r,s:

C(700, 0)

Y, en ellos la función objetivo toma los valores:

Ha de comprar 200 kg. de naranjas A y 500 de naranjas B para obtener un beneficio máximo de 6600 pesos.

3. A una persona le tocan 10 millones de pesos en una lotería y le aconsejan que las invierta en dos tipos de acciones, A y B. Las de tipo A tienen más riesgo pero producen un beneficio del 10%. Las de tipo B son más seguras, pero producen sólo el 7% anual. Después de varias deliberaciones decide invertir como máximo 6 millones en la compra de acciones A y, por lo menos, 2 millones en la compra de acciones B. Además, decide que lo invertido en A sea, por lo menos, igual a lo invertido en B. ¿Cómo deberá invertir 10 millones para que le beneficio anual sea máximo?

Sea:

x= cantidad invertida en acciones A

y= cantidad invertida en acciones B

La función objetivo es:

Y las restricciones son:

La zona de soluciones factibles es:

Siendo los vértices del recinto:

A intersección de u,t:

B intersección de r,u:

C intersección de r,s:

D intersección de s,t:

La función objetivo toma en ellos los valores:

Siendo la solución óptima invertir 6 millones en acciones tipo A y 4 en acciones tipo B

EJERCICIOS PARA GRAFICAR

Nº1