Regresar a la Página Principal

SOLUCIÓN GRÁFICA DE PROBLEMAS DE PROGRAMACIÓN LINEAL

Muchos problemas de administración y economía están relacionados con la optimización (maximización o minimización) de una función sujeta a un sistema de igualdades o desigualdades. La función por optimizar es la función objetivo. Las funciones de ganancia y de costo son ejemplos  de funciones objetivo. El sistema de igualdades  o desigualdades a las que está sujeta la función objetivo reflejan las restricciones (por ejemplo, las limitaciones sobre recursos como materiales y mano de obra) impuestas a la solución (o soluciones) del problema. Los problemas de esta naturaleza  se llaman problemas de programación matemática. En particular, aquellas  donde la función objetivo y las restricciones se expresan como ecuaciones o desigualdades lineales se llaman problemas de programación lineal.

Como ejemplo de un problema de programación lineal en que la función objetivo debe maximizarse, considerese el siguiente problema de producción con dos variables

Solución: Como primer paso para la formulación matemática de este problema, se tabula la información dada (Tabla 1). Si llamamos  x a las hectáreas de maíz e y a las hectáreas de trigo. Entonces la ganancia total P, en dólares, está dada por:

P=40x+30y

Que es la función objetivo por maximizar.

La cantidad total de tiempo par hectáreas para sembrar maíz y trigo está dada por 2x+y horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la desigualdad:

2x+y<800  

Solución Gráfica

Los problemas de programación lineal en dos variables tienen interpretaciones geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuya frontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en forma gráfica.

 Si consideremos el problema del granjero López, es decir, de maximizar  P = 40x+ 30y sujeta a 

 El sistema de desigualdades (7)  define la región plana S que aparece en la figura 5. Cada punto de S es un candidato para resolver este problema y se conoce

como solución factible. El conjunto S se conoce como conjunto factible. El objetivo es encontrar – entre todos los puntos del conjunto S- el punto o los puntos que optimicen la función objetivo P. Tal solución factible es una solución óptima y constituyen la solución del problema de programación lineal en cuestión.

       Como ya se ha observado, cada punto P(x,y) en S es un candidato para la solución óptima del problema en cuestión, por ejemplo, es fácil ver que el punto (200, 150) está en S y, por lo tanto, entra en la competencia. El valor de la función objetivo P en el punto (200,150) está dado por P=40(200)+30(150)=12.500 . Ahora si se pudiera calcular el valor de P correspondiente a cada punto de S, entonces el punto (o los puntos) en S que proporcione el valor máximo de P formará el conjunto solución buscado. Por desgracia, en la mayoría de los problemas, la cantidad de candidatos es demasiado grande o, como en este problema, es infinita. Así este método no es adecuado.

       Es mejor cambiar de punto de vista: en vez de buscar el valor de la función objetivo P en un punto factible, se asignará un valor a la función P y se buscarán los puntos factibles que correspondieran a un valor dado de P. Para esto supóngase  que se asigna a P el valor 6000. Entonces la función objetivo se convierte en 40x+ 30y = 6.000,una ecuación lineal en x e y; por lo tanto, tiene como gráfica una línea recta L₁ en el plano.  

       Está claro que a cada punto del segmento de recta dado por la intersección de la línea recta L₁ y el conjunto factible S corresponde el valor dado 6000 de P. Al repetir el proceso, pero ahora asignando a P el valor  de 12.000, se obtiene la ecuación 40x+ 30y =12.000 y la recta L₂  lo cual sugiere que existen puntos factibles que corresponden a un valor mayor de P. Obsérvese que la recta L₂ es paralela a L₁, pues ambas tienen una pendiente igual a –4/3. Esto se comprueba con facilidad escribiendo las ecuaciones en explícita de la recta.

       En general, al asignar diversos valores a la función objetivo, se obtiene una familia de rectas paralelas, cada una con pendiente igual a –4/3. Además, una recta correspondiente a un valor mayor de P está más alejada del origen que una recta con un valor menor de P. El significado es claro. Para obtener las  soluciones óptimas de este problema, se encuentra la recta perteneciente a esta familia que se encuentra más lejos del origen y que interseque al conjunto factible S. La recta requerida es aquella que pasa por el punto P(320,160) (Fig. 6), de modo que la solución de este problema está dado por x=320, y=160 ( es decir que el granjero López deberá sembrar 320 hectáreas de maíz y 160  hectáreas de trigo), lo que produce el valor máximo P=40(320)+30(160)=17.600.

       No es casualidad que la solución óptima de este problema aparezca como vértice del conjunto factible S. De hecho, el resultado es consecuencia del siguiente teorema básico de la programación lineal, que se enuncia sin demostración.

En nuestro ejemplo los únicos vértice del conjunto factible S son los puntos coordenados:  (0,0); (400,0); (320,160); (0,480), llamados también puntos esquinas (Fig. 6). 

El teorema 1 dice que la búsqueda de las soluciones a un problema de programación  lineal se puede restringir al examen del conjunto de vértices del conjunto factible S relacionado con el problema. Como un conjunto factible S tiene un número finito de vértices, el teorema sugiere que las soluciones a un problema de programación lineal se puedan hallar inspeccionando los valores de la función objetivo P en los vértices.

Aunque el teorema 1 arroja un poco de  luz acerca de la naturaleza de la solución de un problema de programación lineal, no  indica cuándo tiene solución.  El siguiente teorema establece ciertas condiciones que garantizan la existencia de la solución de un problema de programación lineal.

El método utilizado para resolver el problema del granjero López recibe el nombre de método de las esquinas. Este método sigue un procedimiento muy sencillo para resolver los problemas de programación lineal basado en el teorema1.

Aplicaremos los conceptos antes emitidos al siguiente problema de nutrición, basado en los requerimientos, en el cual hay que minimizar la función objetivo.

 

Un nutricionista asesora a un individuo que sufre una deficiencia de hierro y vitamina B, y le indica que debe ingerir al menos 2400 mg de vitamina B-1 (tiamina) y 1500 mg de vitamina B-2 (riboflavina) durante cierto período de tiempo. Existen dos píldoras de vitaminas disponibles, la marca A y la marca B. Cada píldora de la marca A contiene 40 mg de hierro, 10 mg de vitamina B-1, 5 mg de vitamina B-2 y cuesta 6 centavos. Cada píldora de la marca B contiene 10 mg de hierro, 15 mg de vitamina B-1 y de vitamina B-2, y cuesta 8 centavos (tabla 2).  ¿Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus requerimientos de hierro y vitamina al menor costo?

Solución: Sea x el número de píldoras de la marca A e y el número de píldoras de la marca B por comprar. El costo C, medido en centavos, está dado por

C = 6x+ 8y

que representa la función objetivo por minimizar.

       La cantidad de hierro contenida en x píldoras de la marca A e y el número de píldoras de la marca B  está dada por 40x+10y  mg, y esto debe ser mayor o igual a 2400 mg. Esto se traduce en la desigualdad.

40x+10y>2400 

Consideraciones similares con los requisitos mínimos de vitaminas B-1 y B-2 conducen a las desigualdades: 

respectivamente. Así el problema en este caso consiste en minimizar C=6x+8y sujeta a 

Los valores de la función objetivo C en estos vértices en la tabla que sigue

La tabla muestra que el mínimo de la función objetivo C=6x+8y ocurre en el vértice B(30,120) y tiene un valor de 1140. Así el paciente debe adquirir 30 píldoras de la marca A y 120 de la marca B, con un costo mínimo de $11,40. 

El método de las esquinas es de particular utilidad para resolver problemas de programación lineal en dos variables con un número pequeño de restricciones, como han demostrado los ejemplos anteriores, sin embargo su efectividad decrece con rapidez cuando el número de variables o de restricciones aumenta. Por ejemplo, se puede mostrar que un ejemplo de programación lineal en tres variables y cinco restricciones puede tener hasta diez esquinas factibles. La determinación de las esquinas factibles requiere resolver 10 sistemas 3x3 de ecuaciones lineales y luego comprobar que cada uno es un punto factible, sustituyendo cada una de estas soluciones en el sistema de restricciones. Cuando el número de variables y de restricciones aumenta a cinco y diez, respectivamente (que aún es un sistema pequeño desde el punto de vista de las aplicaciones en economía), la cantidad de vértice por hallar y comprobar como esquinas factibles aumenta hasta 252, y cada uno de estos vértices se encuentra resolviendo el sistema lineal ...¡de 5x5! Por esta razón, el método de las esquinas se utiliza con poca frecuencia para resolver problemas de programación lineal, su valor reside en que permite tener una mejor idea acerca de la naturaleza de las soluciones a los problemas de programación lineal a través de su uso en la solución de problemas de dos variables.

Regresar a la Página Principal