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: 2hs  por hrs. Trigo: Utilidad:  $30 por hrs. Trabajo: 1hs  por hrs.

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

1

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>0 y>0  

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

2x+y<800 x+y<480

x>0 y>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<800 x+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

2

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

3

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 objetivo P se optimiza en dos 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 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.

Teorema 2: Existencia de

Supóngase un problema de programación lineal con un conjunto factible S y una función objetivo P = ax + by.

4

una solución  

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 las esquinas  

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

5

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>2100 5x+15y>1500 

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

40x+10y>2400 10x+15y>2100 5x+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).

6

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,

7

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.

 Aspectos Generales de la Programación Lineal En los siglos XVII y XVIII, grandes matemáticos como Newton, Leibnitz, Bernouilli y, sobre todo, Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones.

Posteriormente el matemático fránces Jean Baptiste-Joseph Fourier (1768-1830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva.

Si exceptuamos al matemático Gaspar Monge (1746-1818), quien en 1776 se interesó por problemas de este género, debemos remontarnos al año 1939 para encontrar nuevos estudios relacionados con los métodos de la actual programación lineal. En este año, el matemático ruso Leonodas Vitalyevich Kantarovitch publica una extensa monografía titulada Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada, hoy en día, programación lineal .

En 1941-1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y Kantarovitch, razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantarovitch.

Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio optimal.

En estos años posteriores a la Segunda Guerra Mundial, en Estados Unidos se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal.

Paralelamente a los hechos descritos se desarrollan las técnicas de computación y los ordenadores, instrumentos que harían posible la resolución y simplificación de los problemas que se estaban gestando.

En 1947, G.B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo que dio en denominarse SCOOP (Scientific Computation of Optimum Programs).

Una de las primeras aplicaciones de los estudios del grupo SCOOP fue el puente aéreo de Berlín. Se continuó con infinidad de aplicaciones de tipo preferentemente militar.

Hacia 1950 se constituyen, fundamentalmente en Estados Unidos, distintos grupos de estudio para ir desarrollando las diferentes ramificaciones de la programación lineal. Cabe citar, entre otros, Rand Corporation, con Dantzig, Orchard-Hays, Ford, Fulkerson y Gale, el departamento de Matemáticas de la Universidad de Princenton, con Tucker y Kuhn, así como la Escuela Graduada de Administración Industrial, dependiente del Carnegie Institute of Technology , con Charnes y Cooper.

8

Respecto al método del simplex, que estudiaremos después, señalaremos que su estudio comenzó en el año 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de varios modelos de ordenador de la firma IBM.

Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro Janos von Neuman (1903-1957), quie en 1928 publicó su famoso trabajo Teoría de Juegos. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, discípulo de David Hilbert en Gotinga y, desde 1930, catedrático de la Universidad de Princenton de Estados Unidos, hace que otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina.

En 1858 se aplicaron los métodos de la programación lineal a un problema concreto: el cálculo del plan óptimo de transporte de arena de construcción a las obras de edificación de la ciudad de Moscú. En este problema había 10 puntos de partida y 230 de llegada. El plan óptimo de transporte, calculado con el ordenador Strena en 10 días del mes de junio, rebajó un 11% los gastos respecto a los costes previstos.

Se ha estimado, de una manera general, que si un país subdesarrollado utilizase los métodos de la programación lineal, su producto interior bruto (PIB) aumentaría entre un 10 y un 15% en tan sólo un año.

La programación lineal hace historia: El puente aéreo de Berlín

En 1946 comienza el largo período de la guerra fría entre la antigua Unión Soviética (URSS) y las potencias aliadas (principalmente , Inglaterra y Estados Unidos). Uno de los episodios más llamativos de esa guerra fría se produjo a mediados de 1948, cuando la URSS bloqueó las comunicaciones terrestres desde las zonas alemanas en poder de los aliados con la ciudad de Berlín, iniciando el bloqueo de Berlín. A los aliados se les plantearon dos posiblidades: o romper el bloqueo terrestre por la fuerza, o llegar a Berlín por el aire. Se adoptó la decisión de programar una demostración técnica del poder aéreo norteamericano; a tal efecto, se organizó un gigantesco puente aéreo para abastecer la ciudad: en diciembre de 1948 se estaban transportando 4500 toneladas diarias; en marzo de 1949, se llegó a las 8000 toneladas, tanto como se transportaba por carretera y ferrocarril antes del corte de las comunicaciones. En la planificación de los suministros se utilizó la programación lineal. (El 12 de mayo de 1949, los soviéticos levantaron el bloqueo)

 ¿Qué es la programación lineal ? 

En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc.. se presentan situaciones en las que se exige maximizar o minimizar algunas fucniones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.

Para hacernos una idea más clara de estos supuestos, veamos dos ejemplos:

Ejemplo 1: Problema de máximos.En una granja se preparan dos clases de fertilizantes, P y Q, mezclando dos productos A y B. Un saco de P contiene 8 kg de A y 2 de B, y un saco de Q contiene 10 kg de A y 5 de B. Cada saco de P se vende a 300 Bs. y cada saco de Q a 800 Bs. Si en la granja hay almacenados 80 kg de A y 25 de B, ¿cuántos sacos de cada tipo de pienso deben preparar para obtener los máximos ingresos?

9

Ejemplo 2: Problema de mínimos.Una campaña para promocionar una marca de productos lácteos se basa en el reparto gratuito de yogures con sabor a limón o a fresa. Se decide repartir al menos 30000 yogures.Cada yogur de limón necesita para su elaboración 0.5 gramos de un producto de fermentación y cada yogur de fresa necesita 0.2 gramos de este mismo producto. Se dispone de 9 kilogramos de este producto para fermentación.El costo de producción de un yogur de limón es de 30 Bs. y 20 Bs. uno de fresa.

En los dos ejemplos descritos está claro que tanto la cantidad que deseamos maximizar como la cantidad que deseamos minimizar podemos expresarlas en forma de ecuaciones lineales. Por otra parte, las restricciones que imponen las condiciones de ambos problemas se pueden expresar en forma de inecuaciones lineales.

Tratemos de plantear en términos matemáticos los dos ejemplos anteriores:

1) Si designamos por x al número de sacos de fertilizante de clase P y por y el número de sacos de fertilizante de clase Q que se han de vender, la función : Z = 300x + 800y representará la cantidad de bolívares obtenidas por la venta de los sacos, y por tanto es la que debemos maximizar.Podemos hacer un pequeño cuadro que nos ayude a obtener las restricciones:

  Nº kg de A kg de B

P x 8x 2x

Q y 10y 5y

    80 25

Por otra parte, las variables x e y, lógicamente, han de ser no negativas, por tanto : x 0, y 0Conjunto de restricciones:

8x + 10y 80

2x + 5y 25

x 0, y 0

2) Si representamos por x el número de yogures de limón e y al número de yogures de fresa, se tiene que la función de costos es Z = 30x + 20y.Por otra parte, las condiciones del problema imponen las siguientes restricciones:

De número : x + y 80

10

De fermentación: 0.5x + 0.2y 9000

Las variables x e y han de ser, lógicamente, no negativas; es decir: x 0, y 0

Conjunto de restricciones:

x + y 80

0.5x + 0.2y 9000

x 0, y 0

En definitiva:

Se llama programación lineal al conjunto de técnicas matemáticas que pretenden resolver la situación siguiente:Optimizar (maximizar o minimizar) una función objetivo, función lineal de varias variables, sujeta a:una serie de restricciones, expresadas por inecuaciones lineales.

Un problema de programación lineal en dos variables, tiene la siguiente formulación estándar:

puediendo cambiarse maximizar por minimizar, y el sentido de las desigualdades.

En un problema de programación lineal intervienen:

La función f(x,y) = ax + by + c llamada función objetivo y que es necesario optimizar. En esa expresión x e y son las variables de decisión, mientras que a, b y c son constantes.

11

Las restricciones que deben ser inecuaciones lineales. Su número depende del problema en cuestión. El carácter de desigualdad viene impuesto por las

limitaciones, disponibilidades o necesidades, que son: inferiores a ... ( menores: < o ); como mínimo de ... (mayores: > o ) . Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en cualquiera de los dos sentidos.

Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo denomina conjunto (o región ) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución. En el apartado siguiente veremos como se determina la región factible.

La solución óptima del problema será un par de valores (x0, y0) del conjunto factible que haga que f(x,y) tome el valor máximo o mínimo.

En ocasiones utilizaremos las siglas PPL para indicar problema de programación lineal.

 Determinación de la región factible    La solución de un problema de programación lineal, en el supuesto de que exista, debe estar en la región determinada por las distintas desigualdades. Esta recibe el nombre de región factible, y puede estar o no acotada.

Región factible acotada Región factible no acotada

La región factible incluye o no los lados y los vértices, según que las desigualdades sean en sentido amplio ( o ) o en sentido estricto (< o >).

Si la región factible está acotada, su representación gráfica es un polígono convexo con un número de lados menor o igual que el número de restricciones.

El procedimiento para determinar la región factible es el siguiente:

1) Se resuelve cada inecuación por separado, es decir, se encuentra el semiplano de soluciones de cada una de las inecuaciones.

Se dibuja la recta asociada a la inecuación. Esta recta divide al plano en dos regiones o semiplanos Para averiguar cuál es la región válida, el procedimiento práctico consiste en elegir un punto, por ejemplo, el (0,0) si la recta no pasa por el origen, y

comprobar si las coordenadas satisfacen o no la inecuación. Si lo hacen, la región en la que está ese punto es aquella cuyos puntos verifican la inecuación; en caso contrario, la región válida es la otra.

2) La región factible está formada por la intersección o región común de las soluciones de todas las inecuaciones.

12

Como sucede con los sistemas de ecuaciones lineales, los sistemas de inecuaciones lineales pueden presentar varias opciones respecto a sus soluciones: puede no existir solución, en el caso de que exista el conjunto solución puede ser acotado o no.

Veámoslo con un ejemplo:

Dibuja la región factible asociada a las restricciones:

x + y 4

y 4

y x

Las rectas asociadas son : r : x + y = 4 ; s : y = 4 , t: y = x

Elegimos el punto O(0,0), que se encuentra en el semiplano situado por debajo

de la recta. Introduciendo las coordenadas (0,0) en la inecuación x + y 4, vemos que no la satisface: 0 + 0 = 0 < 4 . Por tanto, el conjunto de soluciones de la inecuación es el semiplano situado por encima de la recta r : x + y = 4 .

Procedemos como en el paso anterior. Las coordenadas (0,0) satisfacen la

inecuación y 4 ( 0 4) . Por tanto, el conjunto de soluciones de la inecuación es el semiplano que incluye al punto O.

13

La recta t asociada a la restricción pasa por el origen, lo cual significa que si probásemos con el punto O(0,0) no llegaríamos a ninguna conclusión.

Elegimos el punto (1,0) y vemos que no satisface la inecuación y x ( y = 0 < 1 = x ). Por tanto, el conjunto solución de esta inecuación es el semiplano determinado por la recta t que no incluye al punto (1,0).

La región factible está formada por los puntos que cumplen las tres restricciones, es decir, se encuentran en los tres semiplanos anteriores.

 Método gráfico o Método de las rectas de nivel

Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor.

Si la función objetivo es f(x,y) = ax + by + c, la ecuación de las rectas de nivel es de la forma:

ax + by + c = 0 ax + by = k

Variando k (o p) se obtienen distintos niveles para esas rectas y, en consecuencia, distintos valores para f(x,y).

En un problema todas las rectas de nivel son paralelas, pues los coeficientes a y b de la recta ax + by = k son los que determinan su pendiente. Por tanto, si k1 es distinto de k2 , las rectas ax + by = k1 y ax + by = k2 son paralelas. Luego, trazada una cualquiera de esas rectas, las demás de obtienen por desplazamientos paralelos a ella.

Si lo que se pretende es resolver un problema de programación lineal, los únicos puntos que interesan son los de la región factible, y las únicas rectas de nivel que importan son aquellas que están en contacto con dicha región. Como el nivel aumenta (o disminuye) desplazando las rectas, el máximo (o el mínimo) de f(x,y) se alcanzará en el último (o en el primer) punto de contacto de esas rectas con la región factible.

Veamos ahora como se aplica todo esto a la resolución de un problema de programación lineal :

14

Maximizar Z = f(x,y) = x + y

sujeto a: 0 x 4

  0 y 4

  y x /2

1) Representamos la región factible:

La recta s : x = 4 pasa por el punto (4,0) y es paralela al eje Y. Las soluciones de 0 x 4 son los puntos entre el eje Y y la recta x = 4

La recta r : y = 4 pasa por el punto (0,4) y es paralela al eje X. Las soluciones de 0 y 4 son los puntos entre el eje X y la recta y = 4

La recta t : y = x/2 pasa por los puntos (0,0) y (2,1) . Las soluciones de y x /2 son los puntos de su izquierda.

Resolviendo los sistemas correspondientes calculamos los vértices de la región factible:

{ y = x/2 , x = 0 } nos da el vértice O(0,0) { x = 4, y = x/2 } nos da el vértice A(4,2){ x = 4 , y = 4} nos da el vértice B(4,4) { y = 4 , x = 0 } nos da el vértice C(0,4)

2) Representamos las rectas de nivel :

En nuestro caso son rectas de la forma x + y = k . Inicialmente representamos Z = x + y = 0 . Trasladándola hacia la derecha, obtenemos las rectas : x + y = 2, x + y = 4, x + y = 8 , es decir aumenta el nivel.

3) Obtenemos la solución óptima:

Se obtiene en el punto de la región factible que hace máximo k. En nuestro caso esto ocurre en el punto B; es el último punto de contacto de esas rectas con la región factible , para el que k = 8.

Si hay dos vértices, P y Q, que se encuentran en la misma recta de nivel ,de ecuación ax + by = k .Es evidente que todos los puntos del segmento PQ son de esa recta; por tanto, en todos ellos f(x,y) vale k. Así pues, la solución óptima es cualquier punto de esa recta; en particular los vértices P y Q.

 Método analítico 

15

o Método de los vértices

El siguiente resultado, denominado teorema fundamental de la programación lineal, nos permite conocer otro método de solucionar un programa con dos variables.

En un programa lineal con dos variables, si existe una solución única que optimice la función objetivo, ésta se encuentra en un punto extremo (vértice) de la región factible acotada, nunca en el interior de dicha región.

Si la función objetivo toma el mismo valor óptimo en dos vértices, también toma idéntico valor en los puntos del segmento que determinan.

En el caso de que la región factible no es acotada, la función lineal objetivo no alcanza necesariamente un valor óptimo concreto, pero, si lo hace, éste se encuentra en uno de los vértices de la región

La evaluación de la función objetivo en los vértices de la región factible nos va a permitir encontrar el valor óptimo (máximo o mínimo) en alguno de ellos.

Veámoslo con un ejemplo:

Maximizar Z = f(x,y) = 3x + 8y

sujeto a: 4x + 5y 40

  2x + 5y 30

  x 0 , y 0

1) Hallar los puntos de corte de las rectas asociadas a las restricciones:

Calculamos las soluciones de cada uno de los seis sistemas de dos ecuaciones con dos incógnitas que se pueden formar con las cuatro restricciones:

{ 4x + 5y = 40 , 2x + 5y = 30}. Solución A(5,4) { 4x + 5y = 40 , x = 0 } Solución:B (0,8)

{ 4x + 5y = 40 , y = 0}. Solución: C(10,0) { 2x + 5y = 30 , x = 0} Solución: D(0,6)

{ 2x + 5y = 30 , y = 0}. Solución : E(15,0) { x = 0, y = 0} Solución: O(0,0)

2) Determinar los vértices de la región factible:

Los vértices de la región factible son aquellos puntos que cumplen todas las restricciones.

Si sustituimos los puntos en cada una de las desigualdades tenemos que:

16

B no cumple la segunda restricción 2x + 5y 30 , ya que 2·0 + 5·8 = 40 . Por tanto, el punto B no es un vértice de la región factible.

E no cumple la primera restricción 4x + 5y 40 , ya que 4·15 + 5·0 = 60 . Por tanto, el punto E no es un vértice de la región factible.

Los puntos A, C, D y O verifican todas las desigualdades, son los vértices de la región factible.

3) Calcular los valores de la función objetivo en los vértices:

f(A) = f(5,4) = 3·5 + 8·4 = 47 f(C) = f(10,0) = 3·10 + 8· 0 = 30

f(D) = f(0,6) = 3·0 + 8·6 = 48 f(O) = f(0,0) = 3·0 + 8·0 = 0

La solución óptima corresponde al vértice para el que la función objetivo toma el valor máximo. En este caso es el vértice D(0,6).

Este método es el menos utilizado de los tres que veremos

 Esquema práctico 

Los problemas de programación lineal pueden presentarse en la forma estándar, dando la función objetivo y las restricciones, o bien plantearlos mediante un enunciado. Si éste es el caso, puede seguirse el camino que indicamos a continuación, ejemplificado con el siguiente problema:

En un almacén se guarda aceite de girasol y de oliva. Para atender a los clientes se han de tener almacenados un mínimo de 20 bidones de aceite de girasol y 40 de aceite de oliva y, además, el número de bidones de aceite de oliva no debe ser inferior a la mitad del número de bidones de aceite de girasol. La capacidad total del almacén es de 150 bidones. Sabiendo que el gasto de almacenaje es el mismo para los dos tipos de aceite (1 unidad monetaria) . ¿Cuántos bidones de cada tipo habrá que almacenar para que el gasto sea máximo?

Obs: Puede parecer algo absurdo maximizar los gastos , pero se ha enunciado de esta forma para que el ejemplo sea lo más completo posible

Paso 1º: Leer detenidamente el enunciado: determinar el objetivo, definir las variables y escribir la función objetivo.

El objetivo es: halla cuántos bidones de cada tipo hay que almacenar para maximizar los gastos

Suponemos que tal objetivo se consigue almacenado x bidones de aceite de girasol e y de aceite de oliva

Cómo cada bidón de aceite de girasol cuesta almacenarlo 1 unidad monetaria y lo mismo para uno de aceite, los gastos serán x + y

Luego, la función objetivo es:

17

Maximizar la función Z = f(x,y) = x + y

Paso 2º: Reordenar los datos del problema y a partir de las cantidades decididas, x e y, escribir el sistema de inecuaciones que determinan las restricciones.

Un mínimo de 20 bidones de aceite de girasol: x 20

Un mínimo de 40 bidones de aceite de oliva: y 40

El número de bidones de aceite de oliva no debe ser inferior a la mitad del número de bidones de aceite de girasol: y x/2

La capacidad total del almacén es de 150 bidones: x + y 150

Además, los números de bidones deben ser cantidades positivas: x 0 ; y 0

Obs.: Como veremos en ejemplos posteriores en algunas ocasiones puede interesar utilizar una tabla para recopilar toda la información y hacer los dos primeros apartados

Paso 3º: Expresar el problema en la forma estándar.

Siguiendo con el ejemplo, sería:

Maximizar: Z = f(x,y) = x + ysujeto a: x + y 150  y x/2

  x 20 ; y 40

Aquí termina el planteamiento del problema. Para su resolución hay que continuar con :

Paso 4º: Representar gráficamente las restricciones y marcar claramente la región factible.

Para las restricciones anteriores debemos representar las rectas: x + y = 150 , y = x/2 , x = 20 e y = 40, obteniéndose la región factible que en la figura se encuentra coloreada.

 

Paso 5º: Hallar las coordenadas de los vértices del polígono obtenido.18

Resolviendo los sistemas : { x = 20, y = 40 } , { y = x/2 , y = 40 } , { y = x/2 , x + y = 150} , { x + y = 150, x = 20}; se obtienen los vértices: A(20,40) , B(80,40) , C(100, 50) , D(20,130)

 

Paso 6º: Sustituir las coordenadas de esos puntos en la función objetivo y hallar el valor máximo o mínimo.

Sustituyendo en f(x,y) = x + y, se tiene:

f(20,40) = 60 , f(80,40) = 120 , f(100, 50) = 150 , f(20,130) = 150

Como el valor máximo se obtiene en los puntos C y D, puede optarse por cualquiera de los dos, o por cualquier punto perteneciente al segmento que los une. Así, por ejemplo, se obtendría el mismo gasto con 40 bidones de aceite girasol y 110 bidones de aceite de oliva; o 90 y 60 respectivamente.

Paso 7º: También es conveniente representar las rectas de nivel para comprobar que la solución gráfica coincide con la encontrada. Esta conveniencia se convierte en necesidad cunado la región factible es no acotada.

En nuestro caso, puede comprobarse que las rectas de nivel tienen la misma pendiente que la recta límite de la restricción x + y 150 ; por tanto, hay múltiples soluciones.

Paso 8º: Por último, como en la resolución de todo problema es necesario criticar la solución: cerciorarse de que la solución hallada es lógica y correcta.

En este ejemplo, no todos los puntos del segmento CD son soluciones válidas, ya que no podemos admitir valores de x e y no enteros , como ocurriría en el punto (90.5,59.5) .

Obs.: Si un problema en la forma estándar no indica que se debe realizar por el método analítico o gráfico , seguiremos para su resolución los pasos del 4º al 8º

 Tipos de soluciones 

Los programas lineales con dos variables suelen clasificarse atendiendo al tipo de solución que presentan. Éstos pueden ser:

Factibles Si existe el conjunto de soluciones o valores que satisfacen las restricciones. A su vez, pueden ser:

     

  Con solución única  

  En una urbanización se van a construir casas de dos tipos: A y B. La empresa constructora dispone para ello de un máximo de 1800 millones de pesetas, siendo el coste de cada tipo de casa de 30 y 20 millones, respectivamente. El Ayuntamiento exige que el número total de casas no sea

19

superior a 80.Sabiendo que el beneficio obtenido por la venta de una casa de tipo A es 4 millones y de 3 millones por una de tipo B, ¿cuántas casas deben construirse de cada tipo para obtener el máximo beneficio?

Variables: x = nº de casas tipo A ; y = nº de casas tipo B Función objetivo: Maximizar Z = f(x,y) = 4x + 3y

Conjunto de restricciones: El coste total 30x + 20y 1800 . El Ayuntamiento impone x + y 80 . De no negatividad: x 0 , y

0.

Tiene por región factible la región coloreada.Si hallamos los valores de la función objetivo en cada uno de los vértices :f(O) = f(0,0) = 0 ; f(C)=f(60,0) = 240 ;f(D) = f(20,60) = 260 ; f(E) = f(0,80) = 240La solución es única, y corresponde al vértice para el que la función objetivo toma el valor máximo. En este caso es el vértice D(20,60). Por tanto se deben construir 20 casas de tipo A y 60 de tipo B con un coste de 260 millones de pesetas.

 

  Con solución múltiple Si existe más de una solución.......................................................................................

 

Maximizar la función Z = f(x,y) = 4x + 2y sujeta a las restricciones 2x + y 4 , x - y 1 , x 0 , y 0.

Los valores de la fucnión objetivo en cada uno de los vértices son:f(O)=f(0,0) = 0 , f(A) = f(1,0) = 4 ; f(B)=f(5/3,2/3) = 8 , f(C) = f(0,4) = 8La función objetivo alcanza el valor máximo en los vértices B y C, por tanto, en todos los puntos del segmento BC.Hay infinitas soluciones, solución múltiple, que corresponden a los puntos del segmento situado entre dos vértices de la región factible.En estos casos, como ya vimos en el capítulo anterior, la función objetivo es paralela a una de las restricciones.

 

  Con solución no acotada Cuando no existe límite para la función objetivo

 

Maximizar la función Z = f(x,y) = x + y sujeta a las restricciones y 2x , y x/2 .

Tiene por región factible la zona coloreada que aparece en la figura, que es una región no acotada.La función crece indefinidamente para valores crecientes de x e y.En este caso no existe un valor extremo para la función objetivo, por lo que puede decirse que el problema carece de solución.Para que suceda esta situación la región factible debe estar no acotada.

 

No factibles

Cuando no existe el conjunto de soluciones que cumplen las restricciones, es decir, las restricciones son inconsistentes.

20

 

Maximizar la función Z = f(x,y) = 3x + 8y sujeta a las restricciones x + y 6 , x + y 2 , x 0 , y 0.

No existe la región factible, ya que las zonas coloreadas que aparecen en la figura son únicamente soluciones de alguna de las inecuaciones .Por tanto, el conjunto de soluciones del sistema de desigualdades no determina ninguna región factible.Este tipo de problemas carece de solución.

     

 Método del SimplexEs un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

El método del simplex fue creado en 1947 por el

matemático George Dantzig .

El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen

tres o más variables.

El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales

constituyen la base del método simplex.

Vamos a resolver mediante el método del simplex el siguiente problema: 

Maximizar

Z= f(x,y)= 3x + 2y

sujeto a: 2x + y  18

  2x + 3y  42

  3x + y  24

  x 0 , y 0

Se consideran las siguientes fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 

21

2x + y + h = 182x + 3y + s = 423x +y + d = 24

2. Igualar la función objetivo a cero

- 3x - 2y + Z = 0

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo: 

Tabla I . Iteración nº 1 Base Variable de decisión Variable de holgura Valores solución

  x y h s d  h 2 1 1 0 0 18

s 2 3 0 1 0 42

d 3 1 0 0 1 24

Z -3 -2 0 0 0 0

4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base

A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).  En nuestro caso, la variable x de coeficiente - 3.

  Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.

  Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.

La columna de la variable que entra en la base se llama columna pivote (En color verde).  

B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso:      18/2 [=9] , 42/2 [=21] y 24/3 [=8]

22

 Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.

  El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color verde).

  Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.    

C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.

5. Encontrar los coeficientes de la nueva tabla.

Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.

A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z. 

También se puede hacer utilizando el siguiente esquema:

Fila del pivote:

Nueva fila del pivote= (Vieja fila del pivote) : (Pivote)

Resto de las filas:

Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote)

Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en la Tabla II):  

Vieja fila de s 2 3 0 1 0 42  - - - - - -Coeficiente 2 2 2 2 2 2  x x x x x xNueva fila pivote 1 1/3 0 0 1/3 8  = = = = = =Nueva fila de s 0 7/3 0 1 -2/3 26

23

 

Tabla II . Iteración nº 2Base Variable de decisión Variable de holgura Valores solución

  x y h s d  h 0 1/3 1 0 -2/3 2

s 0 7/3 0 1 -2/3 26

x 1 1/3 0 0 1/3 8

Z 0 -1 0 0 1 24

Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:

2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.

C. El elemento pivote, que ahora hay que hacer 1, es 1/3.

Operando de forma análoga a la anterior obtenemos la tabla: 

Tabla III . Iteración nº 3Base Variable de decisión Variable de holgura Valores solución

  x y h s d  y 0 1 3 0 -2 6

s 0 0 -7 0 4 12

x 1 0 -1 0 1 6

Z 0 0 3 0 -1 30

Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:

6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.

C. El elemento pivote, que ahora hay que hacer 1, es 4.

24

Obtenemos la tabla: 

Tabla IV . Final del procesoBase Variable de decisión Variable de holgura Valores solución

  x y h s d  y 0 1 -1/2 0 0 12

d 0 0 -7/4 0 1 3

x 1 0 -3/4 0 0 3

Z 0 0 5/4 0 0 33

Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.

Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12) 

* Si en el problema de maximizar apareciesen como restricciones inecuaciones de la forma: ax + by  c; multiplicándolas por - 1 se transforman en inecuaciones de la forma - ax - by  - c y estamos en el caso anterior

* Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos 

  Interpretación geométrica del método del simplex 

Las sucesivas tablas que hemos construido van proporcionando el valor de la función objetivo en los distintos vértices, ajustándose, a la vez, los coeficientes de las variables iniciales y de holgura.

En la primera iteración (Tabla I) han permanecido todos los coeficientes iguales, se ha calculado el valor de la función objetivo en el vértice A(0,0), siendo este 0.

A continuación se desplaza por la arista AB, calculando el valor de f , hasta llegar a B.  Este paso aporta la Tabla II. En esta segunda iteración se ha calculado el valor que corresponde al vértice B(8,0): Z=f(8,0) = 24

Sigue por la arista BC, hasta llegar a C, donde se para y despliega los datos de la Tabla III. En esta tercera iteración se ha calculado el valor que corresponde al vértice C(6,6) : Z=f(6,6)=30.

25

Continua haciendo cálculos a través de la arista CD, hasta llegar al vértice D. Los datos que se reflejan son los de la Tabla IV. Concluye con esta tabla, advirtiendo que ha terminado (antes ha comprobado que la solución no mejora al desplazarse por la arista DE) El valor máximo de la función objetivo es 33, y corresponde a x = 3 e y = 12 (vértice D).

Si calculas el valor de la función objetivo en el vértice E(0,14), su valor no supera el valor 33.

26