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.

Un problema de programación lineal

Un problema de programación lineal consta de una funci´n objetivo lineal por maximizar o minimizar, sujeta a ciertas restricciones en la forma de igualdades o desigualdades lineales.

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

El granjero Lopez tiene 480 hectáreas en la que se puede sembrar ya sea trigo o maíz. El calcula que tiene 800 horas de trabajo disponible durante la estación crucial del verano. Dados márgenes de utilidad y los requerimientos laborales mostrados a la derecha, ¿Cuántas hectáreas de cada uno debe plantar para maximizar su utilidad?¿Cuál es ésta  utilidad máxima?

Maiz:Utilidad: $40 por hrs.Trabajo: 2hsTrigo:Utilidad:  $30 por hrs.Trabajo: 1hs

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.

  Maíz TrigoElementos disponibles

Horas 2 1  

Hectáreas 1 1 800

Utilidad por unidad $40 $30 480

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  

En forma análoga, la cantidad de hectáreas disponibles está dada por x+y, y ésta no puede exceder las hectáreas disponibles para el trabajo, lo que conduce a la desigualdad. Por último, si no queremos tener pérdidas, x y y no pueden  ser negativa, de modo que 

x>0y>0  

En resumen, el problema en cuestión consiste en maximizar la función objetivo  P=40x+30y sujeta a las desigualdades

2x+y<800x+y<480

x>0y>0 

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 

2x+y<800x+y<480

                                                        x>0, y>0                                                    (7)

 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 L1 en el plano.  

       Está claro que a cada punto del segmento de recta dado por la intersección de la línea recta L1 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 L2  lo cual sugiere que existen puntos factibles que corresponden a un valor mayor de P. Obsérvese que la recta L2 es paralela a L1, 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.

Teorema 1 Si en problema de programación lineal tiene una solución, entonces ésta debe aparecer en un vértice, o esquina, del conjunto factible S asociado con el problema. Además, si la función objetivodos vértices adyacente de S, entonces se optimiza en todos los puntos del segmento de recta que une estos vértices, en cuyo caso existe una infinidad de soluciones al problema

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). 

Un ejemplo en el que tendríamos infinitas soluciones, es:

VERTICE P=40x+40y

(0,0) 0

(0,480) 19.200

(320,160) 19.200

(400,0) 16.000

Supóngase que la utilidad por hectáreas es de $40 para ambos, maíz y trigo. La tabla para este caso muestra la misma utilidad total en los vértices(0,480) y (320,160). Esto significa que la línea de utilidad en movimiento abandona la región sombreada por el lado determinado por esos vértices (adyacentes) , así todo punto en ese lado da una utilidad máxima. Todavía es válido, sin embargo, que la utilidad máxima ocurre en un vértice.

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 Srelacionado 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.

Teorema 2:Existencia de una solución 

Supóngase un problema de programación lineal con un conjunto factible S y una función objetivo P = ax + by.1.   Si S está acotado, entonces P tiene u valor máximo y n valor mínimo en S.2.  Si S no está acotado y tanto a como b son no negativos, entonces P tiene un valor mínimo en S, si las restricciones que definen a S incluyen las desigualdades x ³ 0 e y ³ 0.3.    Si S es el conjunto vacío, entonces el problema de programación lineal no tiene solución; es decir, P no tiene un valor máximo ni uno mínimo 

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.

Método de lasesquinas 

1.      Se grafica el conjunto factible.2.      Se encuentran las coordenadas de todas las esquinas (vértices) del conjunto factible.3.   Se evalúa la función objetivo en cada esquina. 4.   Se halla el vértice que proporcione el máximo (mínimo) de la función objetivo. Si sólo existe un vértice con esta propiedad, entonces constituye una solución única del problema. Si la función objetivo se maximiza (minimiza) en dos esquinas adyacentes de S, entonces existe una infinidad de soluciones óptimas dadas por los puntos del segmento de recta determinado por estos dos vértices. 

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?

  Marca A Marca BRequerimientos

mínimos

Hierro 40 mg 10 mg 2400 mg

Vitamina B-1 10 mg 15 mg 2100 mg

Vitamina B-2 5 mg 15 mg 1500 mg

Costo por píldora (US$)

0,06 0,08  

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: 

10x+15y>21005x+15y>1500 

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

40x+10y>240010x+15y>21005x+15y>1500

x>0, y>0   El conjunto factible S definido por el sistema de restricciones aparece en la figura. Los vértices del conjunto factible S son A(0,240); B(30,120); C(120; 60) y D(300,0).

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

Vertice C=6x + 8y

A (0,240) 1920

B(30,120) 1140

C(120,60) 1200

D(300,0) 1800

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.