Programación lineal

Programación lineal

Con el fin de motivar a sus estudiantes, un profesor de Matemática decide proporcionarles dos paquetes de golosinas: uno con 20 chupetes y otro con 10 chocolates. La tarea asignada consiste en empacar dos tipos de combinaciones. En la de tipo A solo pueden ir un chupete y un chocolate, mientras que la de tipo B debe contener 3 chupetes y 1 chocolate. Por cada grupo de golosinas del tipo A, el profesor pagará 3 monedas de diez centavos; y por las del tipo B, 5 monedas de diez centavos. ¿Cuántos grupos de golosinas de cada tipo les conviene formar para conseguir la mayor cantidad de dinero?

INCÓGNITAS DEL PROBLEMALuego de una apropiada lectura, identificamos las variables que intervienen para denotarlas adecuadamente.En este caso nos preguntamos cuántos GRUPOS de golosinas de cada tipo conviene formar. El número de grupos de cada tipo son las incógnitas de la situación. Las llamaremos x e y, respectivamente.

FUNCIÓN OBJETIVO

Es la expresión que debe ser maximizada o minimizada y que da respuesta a la situación problema. En este caso, es la expresión que representa las ganancias por la tarea realizada que se busca maximizar (encontrar el valor máximo).

RESTRICCIONES DEL PROBLEMA

Son situaciones que condicionan el problema y que, en general, se proponen usando expresiones algebraicas. En ese caso es el número de grupos de golosinas de cada tipo, de chupetes y de chocolates.

Representemos los datos en una tabla para poder relacionarlos:

TIPO DE GRUPOS

NÚMERO DE GRUPOS DE GOLOSINAS

NÚMERO DE CHUPETES

NÚMERO DE CHOCOLATES

A

x

x

x

B

y

3y

y

TOTAL

x + 3y

x + y

Como el número de chupetes disponibles para formar los grupos de golosinas del tipo A y B son 20, se tiene que 1

Como el número de chocolates disponibles para formar los grupos de golosinas del tipo A y B son 10, se tiene que 13.

Además, es claro que el número de grupos de golosinas no puede ser negativo:

3

La ganancia total en monedas de diez centavos se representa por la expresión 4, cuyo valor queremos que sea máximo.

En resumen:

Deseamos averiguar para qué valores de x e y la expresión 4se hace lo más grande que sea posible, considerando que x e y están sometidas a las restricciones siguientes:

5

Pasemos a la representación gráfica de las restricciones:

Cada una de las restricciones limita los posibles valores de x e y. Veamos la restricción en el gráfico de cada una de ellas:

1. 6

Se observa que los puntos de la región sombreada satisfacen la restricción, pues cualquier punto de la región tiene coordenadas: abscisa 7 y ordenada 8

2. 9

Se observa que los puntos de la región sombreada satisfacen la segunda restricción, pues cualquier punto de la región tiene coordenadas: abscisa 7 y ordenada 19.

3. 1

Para verificar de manera práctica que la validez de la región sombreada se relaciona con la restricción 1, se toma cualquier punto de dicha región y se reemplazan sus coordenadas en las variables correspondientes de la desigualdad dada. Por ejemplo, si tomamos el punto (0,0), donde x=0 y y=0, y lo reemplazamos en la expresión 1, se tiene que 11es verdadera, puesto que 12.

4. 13

De manera similar se procede con la inecuación 13. Se toma el punto (1,2) perteneciente a la región sombreada, cuyas coordenadas se sustituyen en la expresión dada, y se obtiene 15, ecuación que es verdadera, puesto que   16, lo cual ratifica que los puntos de la región sombreada representan la restricción.

 

Si se juntan las restricciones anteriores en un solo gráfico, se tiene:

La región común a todas las restricciones es denominada “de posible solución” o “ZONA FACTIBLE” (en este caso, la zona factible tiene una cantidad finita de puntos, puesto que x e y representan números de golosinas. Se puede proceder, entonces, a averiguar cuántos puntos de posible solución tiene esta región). Se marcan los vértices del polígono que determina la ZONA FACTIBLE.

Se obtienen las coordenadas de los vértices del polígono de la zona factible (de ser necesario, se hacen los cálculos respectivos).

A = (0,0)

B = (0,20/3)

C = (5,5)

D = (10,0)

Se reemplazan las coordenadas de los vértices en la función objetivo4.

A = (0,0) 18
B = (0,20/3)
C = (5,5)
D = (10,0)

Se observa que el valor máximo se logra al reemplazar las coordenadas del punto C, de coordenadas (5,5), con un valor de 40, que corresponde a 40 monedas de 10 centavos. Esto significa que se deben formar 5 grupos del tipo A y 5 grupos del tipo B.

A continuación se detallan paso a paso las restricciones de la función objetivo 4.